Funkce složitosti - Complexity function

v počítačová věda, funkce složitosti řetězce, konečné nebo nekonečné posloupnosti písmen z nějaké abecedy, je funkce, která počítá počet odlišných faktorů (podřetězce po sobě jdoucích symbolů) z tohoto řetězce. Obecněji řečeno, funkce složitosti jazyka, množina konečných slov nad abecedou, počítá počet odlišných slov dané délky.

Složitost funkce slova

Nechat u být (možná nekonečná) posloupnost symbolů z abecedy. Definujte funkcip_u(n) kladného celého čísla n být počet různých faktorů (po sobě jdoucích podřetězců) délky n z řetězceu.^{[1][2][3][4][5]}

Pro řetězec u alespoň délky n přes abecedu velikosti k jasně máme

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

hranice jsou dosaženy konstantním slovem a disjunktivní slovo,^[6] například Champernowne slovo resp.^[7] Pro nekonečná slova u, my máme p_u(n) ohraničené, pokud u je nakonec periodický (konečná, případně prázdná posloupnost následovaná konečným cyklem). Naopak, pokud p_u(n) ≤ n pro některé n, pak u je nakonec periodický.^[3][8]

An neperiodická posloupnost je ten, který není nakonec periodický. Aperiodická sekvence má přísně rostoucí složitostní funkci (to je Morse – Hedlundova věta),^[9][10] tak p(n) je minimálně n+1.^[11]

Sada S konečných binárních slov je vyrovnaný pokud pro každého n podmnožina S_n slov délky n má vlastnost, kterou Hammingova hmotnost slov v S_n trvá maximálně dvě odlišné hodnoty. A vyvážená sekvence je faktor, u kterého je vyvážen soubor faktorů.^[12] Vyvážená sekvence má nanejvýš složitou funkci n+1.^[13]

A Sturmian slovo nad binární abecedou je jedna s funkcí složitosti n + 1.^[14] Sekvence je Sturmian, jen když je vyvážená a neperiodická.^[2][15] Příkladem je Fibonacciho slovo.^[14][16] Obecněji řečeno, šturmské slovo nad velikostí abecedy k je jeden se složitostí n+k-1. Slovo Arnoux-Rauzy nad ternární abecedou má složitost 2n + 1:^[14] příkladem je Tribonacciho slovo.^[17]

Pro opakující se slova, u nichž se každý faktor objevuje nekonečně často, funkce složitosti téměř charakterizuje množinu faktorů: pokud s je opakující se slovo se stejnou funkcí složitosti jako t jsou tedy s má stejnou sadu faktorů jako t nebo 5t kde δ označuje písmeno zdvojnásobující morfismus A → aa.^[18]

Funkce složitosti jazyka

Nechat L být jazykem abecedy a definovat funkci p_L(n) kladného celého čísla n být počet různých slov délky n v L^[9] Funkce složitosti slova je tedy funkcí složitosti jazyka, která se skládá z činitelů daného slova.

Složitost funkce jazyka je méně omezená než u slova. Například může být ohraničený, ale ne nakonec konstantní: složitost funkce běžný jazyk ${ displaystyle a (bb) ^ {*} a}$ nabývá hodnot 3 a 4 na lichých a sudých n≥2 příslušně. Existuje analogie Morse-Hedlundovy věty: pokud je složitost L splňuje p_L(n) ≤ n pro některé n, pak p_L je omezený a existuje konečný jazyk F takhle^[9]

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

A polynomiální nebo řídký jazyk je ten, pro který je funkce složitosti p(n) je omezen pevnou silou n. A běžný jazyk což není polynom je exponenciální: je jich nekonečně mnoho n pro který p(n) je větší než kⁿ pro některé pevné k > 1.^[19]

Související pojmy

The topologická entropie nekonečné sekvence u je definováno

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

Limita existuje, protože je logaritmus funkce složitosti subadditivní.^[20][21] Každé reálné číslo mezi 0 a 1 se vyskytuje, protože je použitelná topologická entropie nějaké posloupnosti,^[22] které lze považovat za rovnoměrně se opakující^[23] nebo dokonce jedinečně ergodický.^[24]

Pro X skutečné číslo a b celé číslo ≥ 2 pak funkce složitosti X v základně b je funkce složitosti p(X,b,n) posloupnosti číslic X napsáno v základně b.Li X je iracionální číslo pak p(X,b,n) ≥ n+1; -li X je Racionální pak p(X,b,n) ≤ C pro nějakou konstantu C záleží na X a b.^[6] Předpokládá se, že pro algebraické iracionální X složitost je bⁿ (který by následoval, kdyby všechna taková čísla byla normální ), ale vše, co je v tomto případě známo, je to p roste rychleji než jakákoli lineární funkce n.^[25]

The abelianská funkce složitosti p^ab(n) podobně počítá počet výskytů odlišných faktorů dané délky nkde nyní identifikujeme faktory, které se liší pouze permutací pozic. Jasně p^ab(n) ≤ p(n). Abelianova složitost Sturmianovy sekvence vyhovuje p^ab(n) = 2.^[26]

Reference

• Allouche, Jean-Paul; Shallit, Jeffrey (2003). Automatické sekvence: Teorie, Aplikace, Zobecnění. Cambridge University Press. ISBN  978-0-521-82332-6. Zbl  1086.11015.
• Berstel, Jean; Lauve, Aaron; Reutenauer, Christophe; Saliola, Franco V. (2009). Kombinatorika slov. Christoffel slova a opakování slov. Série monografií CRM. 27. Providence, RI: Americká matematická společnost. ISBN  978-0-8218-4480-9. Zbl  1161.68043.
• Berthé, Valérie; Rigo, Michel, eds. (2010). Kombinatorika, automaty a teorie čísel. Encyklopedie matematiky a její aplikace. 135. Cambridge: Cambridge University Press. ISBN  978-0-521-51597-9. Zbl  1197.68006.
• Bugeaud, Yann (2012). Distribuce modulo one a diofantická aproximace. Cambridge Tracts v matematice. 193. Cambridge: Cambridge University Press. ISBN  978-0-521-11169-0. Zbl  1260.11001.
• Cassaigne, Julien; Nicolas, François (2010). "Složitost faktorů". v Berthé, Valérie; Rigo, Michel (eds.). Kombinatorika, automaty a teorie čísel. Encyklopedie matematiky a její aplikace. 135. Cambridge: Cambridge University Press. 163–247. ISBN  978-0-521-51597-9. Zbl  1216.68204.
• Lothaire, M. (2011). Algebraická kombinatorika slov. Encyklopedie matematiky a její aplikace. 90. S předmluvou Jean Berstel a Dominique Perrin (Dotisk vázané knihy z roku 2002, ed.). Cambridge University Press. ISBN  978-0-521-18071-9. Zbl  1221.68183.
• Pytheas Fogg, N. (2002). Berthé, Valérie; Ferenczi, Sébastien; Mauduit, Christian; Siegel, A. (eds.). Substituce v dynamice, aritmetice a kombinatorice. Přednášky z matematiky. 1794. Berlín: Springer-Verlag. ISBN  3-540-44141-7. Zbl  1014.11015.