Slovo bez čtverců - Square-free word
v kombinatorika, a slovo bez čtverce je slovo (sekvence symbolů), která neobsahuje žádné čtverce. A náměstí je slovo z formuláře XX, kde X není prázdný. Slovo bez čtverců lze tedy také definovat jako slovo, které vyhýbá se vzoru XX.
Konečná slova bez čtverce
Binární abeceda
Přes binární abeceda , jediné slovo bez čtverce je prázdné slovo , a .
Ternární abeceda
Přes ternární abecedu , existuje nekonečně mnoho slov bez čtverců. Je možné spočítat počet ternárních čtvercových slov délky n.
n | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
---|---|---|---|---|---|---|---|---|---|---|---|---|---|
1 | 3 | 6 | 12 | 18 | 30 | 42 | 60 | 78 | 108 | 144 | 204 | 264 |
Toto číslo je ohraničeno , kde [2]. Horní hranice na lze najít prostřednictvím Feketeho lemma a aproximace automaty. Dolní mez lze najít nalezením substituce, která zachovává squarefreeness[2].
Abeceda s více než třemi písmeny
Protože nad třípísmennými abecedami je nekonečně mnoho slov bez čtverců, znamená to, že nad abecedou s více než třemi písmeny je také nekonečně mnoho slov bez čtverců.
Následující tabulka ukazuje přesnou míru růstu k-ary slova bez čtverce:
velikost abecedy (k) | 4 | 5 | 6 | 7 | 8 | 9 |
---|---|---|---|---|---|---|
tempo růstu | 2.6215080 | 3.7325386 | 4.7914069 | 5.8284661 | 6.8541173 | 7.8729902 |
velikost abecedy (k) | 10 | 11 | 12 | 13 | 14 | 15 |
tempo růstu | 8.8874856 | 9.8989813 | 10.9083279 | 11.9160804 | 12.9226167 | 13.9282035 |
2-dimenzionální slova
Zvažte mapu z na A, kde A je abeceda a se nazývá dvourozměrné slovo. Nechat být vstupem . Slovo je řada pokud existuje takhle , a pro [3].
Carpi[4] dokazuje, že existuje dvourozměrné slovo přes 16písmennou abecedu, takže každý řádek je bez čtverce. Počítačové vyhledávání ukazuje, že neexistují žádná dvourozměrná slova přes sedmimístnou abecedu, takže každý řádek je bez čtverce.
Generování konečných slov bez čtverců
Shur[5] navrhuje nazývaný algoritmus R2F (random-t (w) o-free), který může generovat slovo bez čtverce délky n nad jakoukoli abecedu se třemi nebo více písmeny. Tento algoritmus je založen na modifikaci komprese entropie: náhodně vybere písmena z abecedy k-písmen k vygenerování a - slovo bez čtverce.
algoritmus R2F je vstup: velikost abecedy , délka slova výstup: A - slovo bez čtverce wdélky n. (Všimněte si, že je abeceda s písmeny .) (Na slovo.) , je permutace takhle A předchází b v pokud je nejvíce vpravo poloha A v w je napravo od pozice zcela vpravo od b v w. Například, má .) Vybrat v rovnoměrně náhodně soubor na následovaná všemi ostatními písmeny ve vzestupném pořadí soubor číslo N iterací na 0 zatímco dělat Vybrat j v rovnoměrně náhodně připojit do konce roku w Aktualizace řazení první j prvky vpravo a nastavení přírůstek N podle 1 -li w končí čtvercem hodnosti r pak smazat poslední r dopisy z w vrátit se w
Každé (k + 1) - každé slovo bez čtverce může být výstupem algoritmu R2F, protože při každé iteraci může připojit libovolné písmeno kromě posledního písmene w.
Očekávaný počet náhodných písmen písmene k, který používá algoritmus R2F ke konstrukci a - dlouhé čtvercové slovo délky n je
Nekonečná čtvercová slova
V každém existují libovolně dlouhá slova bez čtverců abeceda se třemi nebo více písmeny, jak dokazuje Axel Thue[9].
Příklady
První rozdíl Sekvence Thue – Morse
Jedním z příkladů nekonečného čtvercového slova nad abecedou o velikosti 3 je slovo nad abecedou získáno převzetím první rozdíl z Sekvence Thue – Morse [9]. To znamená ze sekvence Thue – Morse
jeden tvoří novou posloupnost, ve které je každý člen rozdílem dvou po sobě jdoucích členů posloupnosti Thue – Morse. Výsledné slovo bez čtverců je
Pijavice je morfismus
Další příklad nalezený uživatelem John Leech[10] je definován rekurzivně nad abecedou . Nechat být jakékoli slovo bez čtverce začínající písmenem 0. Definujte slova rekurzivně takto: slovo se získává z jejich nahrazením 0 v s 0121021201210, každý 1 s 1202102012021a každý 2 s 2010210120102. Je možné dokázat, že posloupnost konverguje k nekonečnému slovu bez čtverců
- 0121021201210120210201202120102101201021202102012021...
Generování nekonečných slov bez čtverců
Nekonečná slova bez čtverců lze generovat pomocí čtvercový morfismus. Morfismus se nazývá squarefree, pokud je obraz každého slova squarefree bez squarefree. Morfismus se nazývá k – squarefree, pokud je obraz každého slova bez čtverce délky k k squarefree.
Crochemore[11] dokazuje, že jednotný morfismus h je squarefree právě tehdy, pokud je 3-squarefree. Jinými slovy, h je squarefree právě tehdy je squarefree pro všechny squarefree w délky 3. Je možné najít morfismus bez čtverců pomocí vyhledávání hrubou silou.
algoritmus squarefree_morphism je výstup: morfismus bez čtverců s nejnižší možnou hodností k. soubor zatímco Skutečný dělat soubor k_sf_words na seznam všech čtvercových slov délky k přes ternární abecedu pro každého v k_sf_words dělat pro každého v k_sf_words dělat pro každého v k_sf_words dělat -li pak přestávka z aktuální smyčky (postup do další ) -li a pak -li je bez čtverce pro bez čtverců w délky 3 pak vrátit se přírůstek k podle 1
Přes ternární abecedu existuje přesně 144 jednotných morfismů bez čtverce úrovně 11 a žádné jednotné morfismy bez čtverce s nižší úrovní než 11.
Chcete-li získat nekonečná slova bez čtverců, začněte libovolným slovem bez čtverců, například 0, a postupně aplikovat morfismus bez čtverců h k tomu. Výsledná slova zachovávají vlastnost squarefreeness. Například nechte h být morfismem bez čtverce, pak jako , je nekonečné slovo bez čtverců.
Všimněte si, že pokud morfismus nad ternární abecedou není jednotný, pak je tento morfismus bez čtverců, pokud a pouze pokud je 5 čtverců[11].
Kombinace písmen slovy bez čtverců
![](http://upload.wikimedia.org/wikipedia/commons/thumb/b/b0/Squarefreeness-3--Bound.png/289px-Squarefreeness-3--Bound.png)
Nepoužívejte kombinace dvou písmen
Na ternární abecedě obsahuje slovo bez čtverců o délce více než 13 všechny kombinace dvou písmen bez čtverců[12].
To lze dokázat vytvořením slova bez čtverců bez kombinace dvou písmen ab. Jako výsledek, bcbacbcacbaca je nejdelší slovo bez čtverce bez kombinace ab a jeho délka je rovna 13.
Všimněte si, že ve více než třípísmenné abecedě jsou slova bez čtverců jakékoli délky bez libovolné kombinace dvou písmen.
Nepoužívejte kombinace tří písmen
Na ternární abecedě obsahuje slovo bez čtverců o délce více než 36 všechny kombinace tří písmen se čtyřmi písmeny[12].
Existují však slova bez čtverce libovolné délky bez kombinace tří písmen aba.
Všimněte si, že ve více než třípísmenné abecedě jsou čtvercová slova libovolné délky bez libovolné kombinace tří písmen.
Hustota dopisu
Hustota písmene A konečným slovem w je definován jako kde je počet výskytů A v a je délka slova. Hustota písmene A v nekonečném slově je kde je předpona slova w délky l[13].
Minimální hustota písmene A v nekonečném ternárním čtvercovém slovu se rovná [13].
Maximální hustota písmene A v nekonečném ternárním čtvercovém slovu se rovná [14].
Poznámky
- ^ „A006156 - OEIS“. oeis.org. Citováno 2019-03-28.
- ^ A b C Shur, Arseny (2011). "Růstové vlastnosti bezmocných jazyků". Recenze informatiky. 6 (5–6): 28–43. doi:10.1016 / j.cosrev.2012.09.001.
- ^ Berthe, Valerie; Rigo, Michel, eds. (2016), „Předmluva“, Kombinatorika, slova a symbolická dynamika, Cambridge University Press, s. Xi – xviii, doi:10.1017 / cbo9781139924733.001, ISBN 9781139924733
- ^ Carpi, Arturo (1988). Msgstr "Multidimenzionální neopakující se konfigurace". Teoretická informatika. 56 (2): 233–241. doi:10.1016/0304-3975(88)90080-1. ISSN 0304-3975.
- ^ Shur, Arseny (2015). „Efektivní generování slov bez čtverců“. Teoretická informatika. 601: 67–72. doi:10.1016 / j.tcs.2015.07.027.
- ^ Apostolico, A .; Preparata, F.P. (Únor 1983). Msgstr "Optimální off-line detekce opakování v řetězci". Teoretická informatika. 22 (3): 297–315. doi:10.1016/0304-3975(83)90109-3. ISSN 0304-3975.
- ^ Crochemore, Max (říjen 1981). Msgstr "Optimální algoritmus pro výpočet opakování slovem". Dopisy o zpracování informací. 12 (5): 244–250. doi:10.1016/0020-0190(81)90024-7. ISSN 0020-0190.
- ^ Hlavní, Michael G; Lorentz, Richard J (září 1984). Msgstr "Algoritmus O (n log n) pro vyhledání všech opakování v řetězci". Journal of Algorithms. 5 (3): 422–432. doi:10.1016 / 0196-6774 (84) 90021-x. ISSN 0196-6774.
- ^ A b Berstel, Jean (1994). Články Axel Thue o opakováních slov a překladu. Départements de mathématiques et d'informatique, Université du Québec à Montréal. ISBN 978-2892761405. OCLC 494791187.
- ^ Leech, J. (1957). "Problém na provázcích". Matematika. Úřední list. 41: 277–278. doi:10.1017 / S0025557200236115. Zbl 0079.01101.
- ^ A b Berstel, Jean (duben 1984). „Několik posledních výsledků u slov bez čtverce“. Výroční sympozium o teoretických aspektech informatiky. Přednášky z informatiky. 166: 14–25. doi:10.1007/3-540-12920-0_2. ISBN 978-3-540-12920-2.
- ^ A b Zolotov, Boris (2015). "Další řešení problému thue neopakujících se slov". arXiv:1505.00019 [math.CO ].
- ^ A b Khalyavin, Andrey (2007). „Minimální hustota písmene v nekonečném slovu bez ternárních čtverců je 883/3215“ (PDF). Journal of Integer Sequences. 10 (2): 3. Bibcode:2007JIntS..10 ... 65K.
- ^ Ochem, Pascal (2007). "Četnost písmen v nekonečných slovech bez opakování". Teoretická informatika. 380 (3): 388–392. doi:10.1016 / j.tcs.2007.03.027. ISSN 0304-3975.
Reference
- 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.
- Lothaire, M. (1997). Kombinatorika slov. Cambridge: Cambridge University Press. ISBN 978-0-521-59924-5..
- 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, Anne (eds.). Substituce v dynamice, aritmetice a kombinatorice. Přednášky z matematiky. 1794. Berlín: Springer-Verlag. ISBN 978-3-540-44141-0. Zbl 1014.11015.