Morfické slovo - Morphic word - Wikipedia

V matematice a informatice, a morfické slovo nebo substituční slovo je nekonečná posloupnost symbolů, která je vytvořena z určité třídy endomorfismus a volný monoid.

Každý automatická sekvence je morfický.^[1]

Definice

Nechat F být endomorfismem volného monoidu A^∗ na abecedě A s vlastností, že existuje dopis A takhle F(A) = tak jako pro neprázdný řetězec s: říkáme to F je prodloužitelné na A. Slovo

${ displaystyle asf (s) f (f (s)) cdots f ^ {(n)} (s) cdots }$

je čistě morfický nebo čisté substituční slovo. Všimněte si, že se jedná o limit posloupnosti A, F(A), F(F(A)), F(F(F(A))), ... Je to zjevně pevný bod endomorfismu F: jedinečná taková posloupnost začínající písmenem A.^[2][3] Obecně je morfické slovo obrazem čistého morfického slova pod kódováním.^[1]

Pokud je morfické slovo konstruováno jako pevný bod prodloužitelného k-jednotný morfismus na A^∗ pak je slovo k-automatický. The n-tý člen v takové posloupnosti může být vytvořen a konečný stavový automat čtení číslic n v základně k.^[1]

Příklady

• The Sekvence Thue – Morse je generováno nad {0,1} 2 uniformním endomorfismem 0 → 01, 1 → 10.^[4][5]
• The Fibonacciho slovo je generováno během {A,b} endomorfismem A → ab, b → A.^[1][4]
• The tribonacci slovo je generováno během {A,b,C} endomorfismem A → ab, b → ac, C → A.^[5]
• The Sekvence Rudin – Shapiro se získá z pevného bodu 2 uniformního morfismu A → ab, b → ac, C → db, d → DC následuje kódování A,b → 0, C,d → 1.^[5]
• The běžná sekvence skládání papíru se získá z pevného bodu 2 uniformního morfismu A → ab, b → cb, C → inzerát, d → CD následuje kódování A,b → 0, C,d → 1.^[6]

Systém D0L

A Systém D0L (deterministický bezkontextový Systém Lindenmayer ) je dáno slovem w volného monoidu A^∗ na abecedě A společně s morfismem σ prodloužitelným na w. Systém generuje nekonečné slovo D0L ω = lim_n→∞ σⁿ(w). Čistě morfická slova jsou slova D0L, ale ne naopak. Pokud však ω = uν je nekonečné slovo D0L s počátečním segmentem u délky |u| ≥ |w| tedy zν je čistě morfické slovo, kde z je dopis, který není v A.^[7]

Viz také

• Sekvence řezání
• Slovo Lyndon
• Hall slovo
• Sturmian slovo

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.
• Honkala, Juha (2010). Msgstr "Problém rovnosti pro čistě substituční slova". v Berthé, Valérie; Rigo, Michel (eds.). Kombinatorika, automaty a teorie čísel. Encyklopedie matematiky a její aplikace. 135. Cambridge: Cambridge University Press. 505–529. ISBN  978-0-521-51597-9. Zbl  1216.68209.
• Lothaire, M. (2005). Aplikovaná kombinatorika na slova. Encyklopedie matematiky a její aplikace. 105. Kolektivní dílo od Jean Berstel, Dominique Perrin, Maxime Crochemore Eric Laporte, Mehryar Mohri, Nadia Pisanti, Marie-France Sagot, Gesine Reinert, Sophie Schbath, Michael Waterman Philippe Jacquet, Wojciech Szpankowski, Dominique Poulalhon, Gilles Schaeffer, Roman Kolpakov, Gregory Koucherov, Jean-Paul Allouche a Valérie Berthé. Cambridge: Cambridge University Press. ISBN  0-521-84802-4. Zbl  1133.68067.
• 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.

Další čtení

• Cassaigne, Julien; Karhumäki, Juhani (1997). "Toeplitzova slova, zobecněná periodicita a periodicky iterované morfismy". European Journal of Combinatorics. 18: 497–510. doi:10.1006 / eujc.1996.0110. Zbl  0881.68065.