Esponente critico

Da Wikipedia, l'enciclopedia libera.

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[modifica | modifica sorgente]

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 abcd occorre con un esponente di 2.75 in wzabcdabcdabcrkw. 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à[modifica | modifica sorgente]

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[modifica | modifica sorgente]

Note[modifica | modifica sorgente]

  1. ^ 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.
  2. ^ 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.
  3. ^ Jean-Paul Allouche, Jeffrey Shallit, Automatic Sequences: Theory, Applications, Generalizations, Cambridge University Press, 2003. ISBN 978-0-521-82332-6, Zbl 1086.11015.
Matematica Portale Matematica: accedi alle voci di Wikipedia che trattano di Matematica