Opakující se slovo - Recurrent word

V matematice, a opakující se slovo nebo sekvence je nekonečné slovo nad konečnou abecedou, ve kterém se každý faktor vyskytuje nekonečně mnohokrát.[1][2][3] Nekonečné slovo se opakuje právě tehdy, pokud jde o a sesquipower.[4][5]

A rovnoměrně se opakující slovo je opakující se slovo, ve kterém pro daný faktor X v pořadí je nějaká délka nX (často mnohem delší než délka X) takové, že X se objeví v každý blok délky nX.[1][6][7] Podmínky minimální sekvence[8] a téměř periodická posloupnost (Muchnik, Semenov, Ushakov 2003).

Příklady

  • Nejjednodušší způsob, jak vytvořit opakující se sekvenci, je vytvořit a periodická posloupnost, kde se sekvence zcela opakuje za daným číslem m kroků. Taková sekvence je potom jednotně opakující se a nX lze nastavit na libovolný násobek m to je větší než dvojnásobek délky X. Opakující se posloupnost, která je nakonec periodická, je čistě periodická.[2]
  • The Sekvence Thue – Morse je rovnoměrně opakující se bez být periodický, nebo dokonce nakonec periodický (tj. periodický po nějakém neperiodickém počátečním segmentu).[9]
  • Všechno Sturmian slova jsou rovnoměrně opakující se.[10]

Reference

  1. ^ A b Lothaire (2011) str. 30
  2. ^ A b Allouche & Shallit (2003), str. 325
  3. ^ Pytheas Fogg (2002) str.2
  4. ^ Lothaire (2011) str. 141
  5. ^ Berstel et al (2009), s. 133
  6. ^ Berthé & Rigo (2010) str.7
  7. ^ Allouche & Shallit (2003), str. 328
  8. ^ Pytheas Fogg (2002), s. 6
  9. ^ Lothaire (2011) s. 31
  10. ^ Berthé & Rigo (2010), s. 177
  • 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.
  • 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.
  • An. Muchnik, A. Semenov, M. Ushakov, Téměř periodické sekvence, Theoret. Comput. Sci. sv. 304 č. 1-3 (2003), 1-33.