Sesquipower - Sesquipower
V matematice, a sesquipower nebo Zimin slovo je tětiva přes abecedu se shodnými předpona a přípona. Sesquipowers jsou nevyhnutelné vzory, v tom smyslu, že všechny dostatečně dlouhé řetězce obsahují jeden.
Formální definice
Formálně, pojďme A být abeceda a A∗ být volný monoid konečných řetězcůA. Každé neprázdné slovo w v A+ je sesquipower řádu 1. Pokud u je sesquipower řádu n pak jakékoli slovo w = uvu je sesquipower řádu n + 1.[1] The stupeň neprázdného slova w je největší celé číslo d takhle w je sesquipower řádu d.[2]
Bi-ideální sekvence
A bi-ideální sekvence je sled slov Fi kde F1 je v A+ a
pro některé Gi v A∗ a i ≥ 1. Stupeň slova w je tedy délka nejdelší bi-ideální sekvence končící na w.[2]
Pro konečnou abecedu A na k písmena, existuje celé číslo M záleží na k a n, tak, že jakékoli slovo délky M má faktor, který je minimálně sesquipower řádu n. Vyjádříme to tím, že říkáme, že sesquipowery jsou nevyhnutelné vzory.[3][4]
Sesquipowers v nekonečných sekvencích
Vzhledem k nekonečné bi-ideální posloupnosti si všimneme, že každý Fi je předpona Fi+1 a tak Fi konvergovat do nekonečné sekvence
Definujeme nekonečné slovo jako sesquipower, pokud je to limit nekonečné bi-ideální posloupnosti.[5] Nekonečné slovo je sesquipower právě tehdy, když je opakující se slovo,[5][6] to znamená, že každý faktor se vyskytuje nekonečně často.[7]
Opravte konečnou abecedu A a předpokládejme a celková objednávka na dopisech. Pro zadaná celá čísla str a n, každé dostatečně dlouhé slovo A∗ má buď faktor, který je a str- síla nebo faktor, který je n-sequipower; v druhém případě má faktor hodnotu n-faktorizace do Lyndonova slova.[6]
Viz také
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. (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 3-540-44141-7. Zbl 1014.11015.