Esponente critico
In dinamica simbolica, l'esponente critico di una successione infinita di simboli è una quantità che descrive quante volte una stringa può ripetersi all'interno della sequenza.
Definizione
Data una stringa infinita w di simboli dell'alfabeto A, e una stringa finita x sullo stesso alfabeto, x occorre in w con esponente α (con α>0) se e solo se esiste una stringa y all'interno di w tale che y = xax0, dove x0 è un prefisso di x e a è la parte intera di α, e la lunghezza di y l(y)≥ α·l(x). Ad esempio, la stringa occorre con un esponente di 2.75 in . y è detta un'α-potenza, e w è priva di α-potenze se non contiene nessuna sottostringa che è un'α-potenza.
L'esponente critico di w è il massimo numero reale α per il quale w presenta almeno un'α-potenza, oppure il minimo numero reale per cui non ne presenta.
Proprietà
L'esponente critico di una successione può assumere qualsiasi valore reale maggiore di 1. L'esponente critico di una parola morfica su un alfabeto di n simboli è un numero algebrico di grado minore o uguale ad n
Esempi
- L'esponente critico della successione di Thue-Morse è pari a 2.
- L'esponente critico della parola di Fibonacci è (5 + √5)/2 ≈ 3.618.
- L'esponente critico dell'espansione decimale della costante di Champernowne è infinito.
Note
- 1 2 3 Dalia Krieger, On critical exponents in fixed points of non-erasing morphisms, in Oscar H. Ibarra e Zhe Dang (a cura di), Developments in Language Theory: Proceedings 10th International Conference, DLT 2006, Santa Barbara, CA, USA, 26–29 giugno 2006, Lecture Notes in Computer Science, vol. 4036, Springer-Verlag, 2006, pp. 280–291, ISBN 3-540-35428-X, Zbl 1227.68074.
- ↑ Krieger, Dalia, Every real number greater than one is a critical exponent, in Theor. Comput. Sci., vol. 381, 2007, pp. 177–182, DOI:10.1016/j.tcs.2007.04.037.
- ↑ Jean-Paul Allouche, Jeffrey Shallit, Automatic Sequences: Theory, Applications, Generalizations, Cambridge University Press, 2003, ISBN 978-0-521-82332-6, Zbl 1086.11015.
