Palabra de parámetro

En el estudio matemático de la combinatoria de palabras , una palabra de parámetro es una cadena sobre un alfabeto dado que tiene una cierta cantidad de caracteres comodín . ^[1] El conjunto de cadenas que coinciden con una palabra de parámetro dada se denomina conjunto de parámetros o cubo combinatorio . Las palabras de parámetro se pueden componer para producir subcubos más pequeños de un cubo combinatorio dado. Tienen aplicaciones en la teoría de Ramsey y en la informática en la detección de código duplicado .

Definiciones y notación

Formalmente, una palabra con -parámetros de longitud , sobre un alfabeto dado , es una secuencia de caracteres, algunos de los cuales pueden extraerse de y los otros son caracteres comodín distintos . Cada carácter comodín debe aparecer al menos una vez, pero puede aparecer varias veces, y los caracteres comodín deben aparecer en el orden dado por sus índices: el primer carácter comodín en la palabra debe ser , el siguiente que sea diferente de debe ser , etc. Como caso especial, una palabra sobre el alfabeto dado, sin ningún carácter comodín, se dice que es una palabra de 0 parámetros. Para palabras de 1 parámetro, los subíndices pueden omitirse, ya que no hay ambigüedad entre los diferentes caracteres comodín. El conjunto de todas las palabras con -parámetros sobre , de longitud , se denota . ^[1] ${\displaystyle k}$ ${\displaystyle n}$ ${\displaystyle A}$ ${\displaystyle n}$ ${\displaystyle A}$ ${\displaystyle k}$ ${\displaystyle *_{1},*_{2},\ldots ,*_{k}}$ ${\displaystyle *_{1}}$ ${\displaystyle *_{1}}$ ${\displaystyle *_{2}}$ ${\displaystyle k}$ ${\displaystyle A}$ ${\displaystyle n}$ ${\displaystyle A{\tbinom {n}{k}}}$

Una palabra con un parámetro representa un conjunto de cadenas (palabras con 0 parámetros) que se obtienen sustituyendo un símbolo de por cada carácter comodín. Este conjunto de cadenas se denomina conjunto de parámetros de cubo combinatorio y se denomina dimensión. Un cubo combinatorio unidimensional puede denominarse línea combinatoria . ^[1] ${\displaystyle k}$ ${\displaystyle |A|^{k}}$ ${\displaystyle A}$ ${\displaystyle k}$

En un cubo combinatorio, cada copia de un carácter comodín particular debe tener el mismo reemplazo. Una generalización de palabras de parámetro permite que diferentes copias del mismo carácter comodín sean reemplazadas por diferentes caracteres del alfabeto, de una manera controlada. Si es un alfabeto y es un grupo con una acción en , entonces una palabra de parámetro etiquetada es una palabra de parámetro junto con una asignación de un elemento de grupo a cada carácter comodín en la palabra. La primera aparición de cada carácter comodín debe tener asignado el elemento de identidad del grupo. Luego, las cadenas representadas por una palabra de parámetro etiquetada se obtienen eligiendo un carácter de para cada carácter comodín y sustituyendo el resultado de combinar ese carácter con el elemento de grupo que etiqueta cada copia de ese carácter. El conjunto de todas las palabras de parámetro etiquetadas sobre , de longitud , se denota . ^[1] ${\displaystyle A}$ ${\displaystyle G}$ ${\displaystyle A}$ ${\displaystyle G}$ ${\displaystyle k}$ ${\displaystyle A}$ ${\displaystyle G}$ ${\displaystyle k}$ ${\displaystyle A}$ ${\displaystyle n}$ ${\displaystyle [A,G]{\tbinom {n}{k}}}$

Ejemplo

En el juego de tres en raya , las celdas del tablero de juego pueden recibir dos coordenadas enteras del alfabeto . La concatenación de estas dos coordenadas produce una cadena que representa cada celda, una de las nueve cadenas o . Hay siete palabras de un parámetro de longitud dos en este alfabeto, las palabras y . Las líneas combinatorias correspondientes forman siete de las ocho líneas de tres celdas en una fila del tablero de tres en raya; por ejemplo, la palabra de un parámetro corresponde a la línea combinatoria , y la palabra de un parámetro corresponde a la línea combinatoria . ^[2] ${\displaystyle (x,y)}$ ${\displaystyle \{1,2,3\}}$ ${\displaystyle 11,12,13,21,22,23,31,32,}$ ${\displaystyle 33}$ ${\displaystyle 1*,2*,3*,*1,*2,*3,}$ ${\displaystyle **}$ ${\displaystyle 2*}$ ${\displaystyle \{21,22,23\}}$ ${\displaystyle **}$ ${\displaystyle \{11,22,33\}}$

Sin embargo, en este conjunto de líneas combinatorias falta una de las ocho líneas ganadoras del juego del tres en raya: la línea antidiagonal . Es posible obtener esta línea como una línea combinatoria (sin incluir ninguna otra combinación de celdas que no sería válida para el tres en raya) utilizando un grupo con dos elementos y una acción en la que el elemento no identidad intercambia las letras del alfabeto y mientras deja el elemento en su lugar. Hay ocho palabras etiquetadas de un parámetro de longitud dos para esta acción, siete de las cuales se obtienen a partir de las palabras de un parámetro sin etiquetar utilizando la etiqueta de identidad para todos los comodines. Estas siete tienen las mismas líneas combinatorias que antes. La octava palabra etiquetada consiste en la palabra etiquetada por el elemento identidad para su primera y el elemento no identidad inverso para el segundo ; su línea combinatoria es la línea ganadora final del tablero del tres en raya, . ^[2] ${\displaystyle \{13,22,31\}}$ ${\displaystyle 1}$ ${\displaystyle 3}$ ${\displaystyle 2}$ ${\displaystyle **}$ ${\displaystyle *}$ ${\displaystyle *}$ ${\displaystyle \{13,22,31\}}$

Composición

Para tres parámetros enteros dados , es posible combinar dos palabras de parámetro, y , para producir otra palabra de parámetro . Para ello, simplemente reemplace cada copia del símbolo comodín n por el carácter n en . Esto producirá necesariamente una palabra de longitud que utiliza cada uno de los símbolos comodín en al menos una vez, en orden ascendente, por lo que produce una palabra de parámetro válida de longitud . Esta noción de composición también se puede extender a la composición de palabras de parámetro etiquetadas (ambas utilizando el mismo alfabeto y acción de grupo), aplicando la acción de grupo a los caracteres no sustituidos por comodines y componiendo las etiquetas de grupo para los caracteres sustituidos por comodines. Un subconjunto de un cubo combinatorio es un cubo combinatorio más pequeño si se puede obtener mediante una composición de esta manera. ^[1] ${\displaystyle n\geq m\geq k}$ ${\displaystyle f\in A{\tbinom {n}{m}}}$ ${\displaystyle g\in A{\tbinom {m}{k}}}$ ${\displaystyle f\circ g\in A{\tbinom {n}{k}}}$ ${\displaystyle i}$ ${\displaystyle f}$ ${\displaystyle i}$ ${\displaystyle g}$ ${\displaystyle n}$ ${\displaystyle g}$ ${\displaystyle k}$ ${\displaystyle n}$

Enumeración combinatoria

El número de palabras de parámetro en para un alfabeto de tamaño es un número de Stirling de segundo tipo . Estos números cuentan el número de particiones de los enteros en el rango en subconjuntos no vacíos de modo que los primeros enteros pertenecen a subconjuntos distintos. Las particiones de este tipo se pueden colocar en una equivalencia biyectiva con las palabras de parámetro, creando una palabra con un carácter para cada uno de los enteros en el rango , estableciendo este valor de carácter para que sea un entero en que pertenezca al mismo subconjunto de la partición, o un carácter comodín para cada subconjunto de la partición que no contenga un entero en . Los números de Stirling obedecen a una relación de recurrencia simple por la que se pueden calcular fácilmente. ^{[3] [4]} ${\displaystyle A{\tbinom {n}{k}}}$ ${\displaystyle r}$ ${\displaystyle r}$ ${\displaystyle \textstyle \left\{{r+n \atop r+k}\right\}_{r}}$ ${\displaystyle [1,r+n]}$ ${\displaystyle r+k}$ ${\displaystyle r}$ ${\displaystyle n}$ ${\displaystyle [r+1,n+r]}$ ${\displaystyle [1,r]}$ ${\displaystyle [1,r]}$ ${\displaystyle r}$

Aplicaciones

En la teoría de Ramsey , las palabras paramétricas y los cubos combinatorios pueden usarse para formular el teorema de Graham-Rothschild , según el cual, para cada alfabeto finito y acción de grupo, y cada combinación de valores enteros , , y , existe un número suficientemente grande tal que si a cada cubo combinatorio -dimensional sobre cadenas de longitud se le asigna uno de colores, entonces existe un cubo combinatorio -dimensional cuyos subcubos -dimensionales tienen todos el mismo color. Este resultado es una base clave para la teoría estructural de Ramsey , y se usa para definir el número de Graham , un número enorme usado para estimar el valor de para una cierta combinación de valores. ^[1] ${\displaystyle m}$ ${\displaystyle k}$ ${\displaystyle r}$ ${\displaystyle n}$ ${\displaystyle k}$ ${\displaystyle n}$ ${\displaystyle r}$ ${\displaystyle m}$ ${\displaystyle k}$ ${\displaystyle n}$

En informática , en el problema de búsqueda de código duplicado , el código fuente de una rutina o módulo determinado puede transformarse en una palabra de parámetro convirtiéndolo en una secuencia de tokens y, para cada nombre de variable o subrutina, reemplazando cada copia del mismo nombre con el mismo carácter comodín. Si el código está duplicado, las palabras de parámetro resultantes seguirán siendo iguales incluso si se han cambiado el nombre de algunas de las variables o subrutinas. Los algoritmos de búsqueda más sofisticados pueden encontrar largas secciones de código duplicado que forman subcadenas de repositorios de código fuente más grandes, al permitir que los caracteres comodín se sustituyan entre sí. ^[5]

Un caso especial importante de palabras paramétricas, bien estudiado en la combinatoria de palabras, lo constituyen las palabras parciales . Se trata de cadenas con caracteres comodín que pueden sustituirse independientemente entre sí, sin necesidad de que algunos de los caracteres sustituidos sean iguales o estén controlados por una acción de grupo. En el lenguaje de las palabras paramétricas, una palabra parcial puede describirse como una palabra paramétrica en la que cada símbolo comodín aparece exactamente una vez. Sin embargo, como no hay repetición de símbolos comodín, las palabras parciales pueden escribirse de forma más sencilla omitiendo los subíndices de los símbolos comodín. ^[6]

Véase también

• Expresión regular

Referencias

1. Prömel, Hans Jürgen (2002), "Números grandes, notación de flechas de Knuth y teoría de Ramsey", Synthese , 133 (1–2): 87–105, doi :10.1023/A:1020879709125, JSTOR  20117296, MR  1950045
2. Prömel, Hans Jürgen (2013), "Teorema de Hales-Jewett", Teoría de Ramsey para estructuras discretas , Springer International Publishing, págs. 41-51, doi :10.1007/978-3-319-01315-2_4
3. Broder, Andrei Z. (1984), "Los números de Stirling", Matemáticas discretas , 49 (3): 241–259, doi : 10.1016/0012-365X(84)90161-4 , MR  0743795 ${\displaystyle r}$
4. Benzait, A.; Voigt, B. (1989), "Una interpretación combinatoria de ", Actas de la reunión de Oberwolfach "Kombinatorik" (1986), Matemáticas discretas , 73 (1–2): 27–35, doi : 10.1016/0012-365X(88)90130-6 , MR  0974810 ${\displaystyle (1/k!)\Delta ^{k}t^{n}}$
5. Baker, Brenda S. (1997), "Duplicación parametrizada en cadenas: algoritmos y una aplicación al mantenimiento de software", SIAM Journal on Computing , 26 (5): 1343–1362, doi :10.1137/S0097539793246707, MR  1471985
6. Blanchet-Sadri, Francine (2008), Combinatoria algorítmica en palabras parciales , Matemáticas discretas y sus aplicaciones, Boca Raton, Florida: Chapman & Hall/CRC, ISBN 978-1-4200-6092-8, Sr.  2384993