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.[1]
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[1].
Proprietà
L'esponente critico di una successione può assumere qualsiasi valore reale maggiore di 1[2]. L'esponente critico di una parola morfica su un alfabeto di n simboli è un numero algebrico di grado minore o uguale ad n[1]
Esempi
- L'esponente critico della successione di Thue-Morse è pari a 2.
- L'esponente critico della parola di Fibonacci è (5 + √5)/2 ≈ 3.618[3].
- L'esponente critico dell'espansione decimale della costante di Champernowne è infinito.
Note
- ^ a b c 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.
![](http://upload.wikimedia.org/wikipedia/commons/thumb/a/af/Crystal128-kmplot.svg/25px-Crystal128-kmplot.svg.png)