Función de complejidad

En informática , la función de complejidad de una palabra o cadena (una secuencia finita o infinita de símbolos de un alfabeto ) es la función que cuenta el número de factores distintos (subcadenas de símbolos consecutivos) de dicha cadena. De forma más general, la función de complejidad de un lenguaje formal (un conjunto de cadenas finitas) cuenta el número de palabras distintas de una longitud dada.

Sea u una secuencia (posiblemente infinita) de símbolos de un alfabeto. Definimos la función p _u ( n ) de un entero positivo n como el número de factores diferentes (subcadenas consecutivas) de longitud n de la cadena u . ^{[ 1 ] [ 2 ] [ 3 ] [ 4 ] [ 5 ]} 

Para una cadena u de longitud al menos n sobre un alfabeto de tamaño k, claramente tenemos

${\displaystyle 1\leq p_{u}(n)\leq k^{n}\ ,}$

los límites se alcanzan mediante la palabra constante y una palabra disyuntiva , ^{[ 6 ]} por ejemplo, la palabra de Champernowne respectivamente. ^{[ 7 ]} Para palabras infinitas u , tenemos p _u ( n ) acotado si u es finalmente periódico (una secuencia finita, posiblemente vacía, seguida de un ciclo finito). Recíprocamente, si p _u ( n ) ≤ n para algún n , entonces u es finalmente periódico. ^{[ 3 ] [ 8 ]}

Una secuencia aperiódica es aquella que no es periódica en última instancia. Una secuencia aperiódica tiene una función de complejidad estrictamente creciente (este es el teorema de Morse-Hedlund ), ^{[ 9 ] [ 10 ]} por lo que p ( n ) es al menos n +1. ^{[ 11 ]}

Un conjunto S de palabras binarias finitas es equilibrado si para cada n el subconjunto S _n de palabras de longitud n tiene la propiedad de que el peso de Hamming de las palabras en S _n toma como máximo dos valores distintos. Una secuencia equilibrada es aquella para la cual el conjunto de factores es equilibrado. ^{[ 12 ]} Una secuencia equilibrada tiene una función de complejidad de como máximo n +1. ^{[ 13 ]}

Una palabra de Sturm sobre un alfabeto binario es aquella con función de complejidad n  +  1. ^{[ 14 ]} Una secuencia es de Sturm si y solo si es equilibrada y aperiódica. ^{[ 2 ] [ 15 ]} Un ejemplo es la palabra de Fibonacci . ^{[ 14 ] [ 16 ]} De manera más general, una palabra de Sturm sobre un alfabeto de tamaño k es aquella con complejidad n + k −1. Una palabra de Arnoux-Rauzy sobre un alfabeto ternario tiene complejidad 2 n  +  1: ^{[ 14 ]} un ejemplo es la palabra de Tribonacci . ^{[ 17 ]}

Para las palabras recurrentes , aquellas en las que cada factor aparece infinitamente a menudo, la función de complejidad casi caracteriza el conjunto de factores: si s es una palabra recurrente con la misma función de complejidad que t , entonces s tiene el mismo conjunto de factores que t o δ t, donde δ denota el morfismo de duplicación de letras a → aa . ^{[ 18 ]}

Sea L un lenguaje sobre un alfabeto y definamos la función p _L ( n ) de un entero positivo n como el número de palabras diferentes de longitud n en L ^{[ 9 ].} La función de complejidad de una palabra es, por lo tanto, la función de complejidad del lenguaje que consta de los factores de esa palabra.

La función de complejidad de un lenguaje está menos restringida que la de una palabra. Por ejemplo, puede estar acotada pero no ser eventualmente constante: la función de complejidad del lenguaje regular${\displaystyle a(bb)^{*}a}$toma valores 3 y 4 en n ≥2 impares y pares respectivamente. Hay un análogo del teorema de Morse-Hedlund: si la complejidad de L satisface p _L ( n ) ≤ n para algún n , entonces p _L está acotada y hay un lenguaje finito F tal que ^{[ 9 ]}

${\displaystyle L\subseteq \{xy^{k}z:x,y,z\in F,\ k\in \mathbb {N} \}\ .}$

Un lenguaje polinomial o disperso es aquel para el cual la función de complejidad p ( n ) está acotada por una potencia fija de n . Un lenguaje regular que no es polinomial es exponencial : existen infinitos n para los cuales p ( n ) es mayor que k ⁿ para algún k > 1 fijo. ^{[ 19 ]}

La entropía topológica de una secuencia infinita u se define por

${\displaystyle H_{\mathrm {top} }(u)=\lim _{n\rightarrow \infty }{\frac {\log p_{u}(n)}{n\log k}}\ .}$

El límite existe ya que el logaritmo de la función de complejidad es subaditivo . ^{[ 20 ] [ 21 ]} Todo número real entre 0 y 1 aparece cuando la entropía topológica de alguna secuencia es aplicable, ^{[ 22 ]} que puede considerarse uniformemente recurrente ^{[ 23 ]} o incluso unívocamente ergódica. ^{[ 24 ]}

Para x un número real y b un entero ≥ 2, la función de complejidad de x en base b es la función de complejidad p ( x , b , n ) de la secuencia de dígitos de x escrita en base b . Si x es un número irracional, entonces p ( x , b , n ) ≥ n +1; si x es racional, entonces p ( x , b , n ) ≤ C para alguna constante C que depende de x y b . ^{[ 6 ]} Se conjetura que para x irracional algebraico la complejidad es b ⁿ (lo que se seguiría si todos esos números fueran normales ) pero todo lo que se sabe en este caso es que p crece más rápido que cualquier función lineal de n . ^{[ 25 ]}

La función de complejidad abeliana p ^ab ( n ) cuenta de manera similar el número de ocurrencias de factores distintos de longitud n dada , donde ahora identificamos factores que difieren solo por una permutación de las posiciones. Claramente, p ^ab ( n ) ≤ p ( n ). La complejidad abeliana de una secuencia de Sturm satisface p ^ab ( n ) = 2. ^{[ 26 ]}

• Allouche, Jean-Paul; Shallit, Jeffrey (2003). Automatic Sequences: Theory, Applications, Generalizations . Cambridge University Press . ISBN 978-0-521-82332-6. Zbl 1086.11015 . 
• Berstel, Jean; Lauve, Aaron; Reutenauer, Christophe; Saliola, Franco V. (2009). Combinatoria de palabras. Palabras de Christoffel y repeticiones en palabras . Serie de monografías CRM. Vol.  27. Providence, RI: American Mathematical Society . ISBN 978-0-8218-4480-9. Zbl 1161.68043 . 
• Berthé, Valérie ; Rigo, Michel, eds. (2010). Combinatoria, autómatas y teoría de números . Enciclopedia de Matemáticas y sus Aplicaciones. Vol.  135. Cambridge: Cambridge University Press . ISBN 978-0-521-51597-9. Zbl 1197.68006 . 
• Bugeaud, Yann (2012). Distribución módulo uno y aproximación diofántica . Cambridge Tracts in Mathematics. Vol.  193. Cambridge: Cambridge University Press . ISBN 978-0-521-11169-0. Zbl 1260.11001 . 
• Cassaigne, Julien; Nicolas, François (2010). «Complejidad factorial». En Berthé, Valérie ; Rigo, Michel (eds.). Combinatoria, autómatas y teoría de números . Enciclopedia de matemáticas y sus aplicaciones. Vol.  135. Cambridge: Cambridge University Press . pp. 163–247 . ISBN  978-0-521-51597-9. Zbl 1216.68204 . 
• Lothaire, M. (2011). Combinatoria algebraica en palabras . Enciclopedia de Matemáticas y sus Aplicaciones. Vol.  90. Con prólogo de Jean Berstel y Dominique Perrin (Reimpresión de la  edición en tapa dura de 2002). Cambridge University Press. ISBN 978-0-521-18071-9. Zbl 1221.68183 . 
• Pytheas Fogg, N. (2002). Berthé, Valérie ; Ferenczi, Sébastien; Mauduit, cristiano; Siegel, A. (eds.). Sustituciones en dinámica, aritmética y combinatoria . Apuntes de conferencias de matemáticas. vol.  1794. Berlín: Springer-Verlag . ISBN 3-540-44141-7. Zbl 1014.11015 .