Takroriy so'z - Recurrent word

Matematikada a takrorlanadigan so'z yoki ketma-ketlik har qanday omil cheksiz ko'p marta sodir bo'ladigan cheklangan alifbo ustidagi cheksiz so'zdir.[1][2][3] Cheksiz so'z takrorlanadi, agar u a bo'lsa sesquipower.[4][5]

A bir xilda takrorlanadigan so'z har qanday omil uchun takrorlanadigan so'zdir X ketma-ketlikda bir oz uzunlik mavjud nX (ko'pincha uzunligidan ancha uzunroq) X) shu kabi X ichida paydo bo'ladi har bir uzunlik bloki nX.[1][6][7] Shartlar minimal ketma-ketlik[8] va deyarli davriy ketma-ketlik (Muchnik, Semenov, Ushakov 2003) ham ishlatiladi.

Misollar

  • Takrorlanadigan ketma-ketlikni tuzishning eng oson yo'li bu davriy ketma-ketlik, ketma-ketlik berilgan sondan keyin to'liq takrorlanadigan m qadamlar. Keyinchalik bunday ketma-ketlik bir xilda takrorlanadi va nX ning har qanday ko'paytmasiga o'rnatilishi mumkin m uzunligidan ikki baravar katta X. Oxir oqibat davriy bo'lgan takroriy ketma-ketlik faqat davriydir.[2]
  • The Thue-Morse ketma-ketligi bir xilda takrorlanadi holda davriy va hatto oxir-oqibat davriy (ba'zi bir davriy bo'lmagan boshlang'ich segmentdan keyin davriy degani).[9]
  • Hammasi Sturmcha so'zlar bir xilda takrorlanadi.[10]

Adabiyotlar

  1. ^ a b Lothaire (2011) p. 30
  2. ^ a b Allouche & Shallit (2003) 325-bet
  3. ^ Pytheas Fogg (2002) 2-bet
  4. ^ Lothaire (2011) p. 141
  5. ^ Berstel va boshq (2009) p.133
  6. ^ Berthé & Rigo (2010) s.7
  7. ^ Allouche & Shallit (2003) 328-bet
  8. ^ Pytheas Fogg (2002) 6-bet
  9. ^ Lothaire (2011) s.31
  10. ^ Berthé & Rigo (2010) p.177
  • Alloush, Jan-Pol; Shallit, Jefri (2003). Avtomatik ketma-ketliklar: nazariya, qo'llanmalar, umumlashtirish. Kembrij universiteti matbuoti. ISBN  978-0-521-82332-6. Zbl  1086.11015.
  • Berstel, Jan; Lauve, Aaron; Reutenauer, Christophe; Saliola, Franko V. (2009). So'zlar bo'yicha kombinatorika. Christoffel so'zlari va takroriy so'zlar. CRM monografiya seriyasi. 27. Providence, RI: Amerika matematik jamiyati. ISBN  978-0-8218-4480-9. Zbl  1161.68043.
  • Berti, Valeri; Rigo, Mishel, nashr. (2010). Kombinatorika, avtomatika va sonlar nazariyasi. Matematika entsiklopediyasi va uning qo'llanilishi. 135. Kembrij: Kembrij universiteti matbuoti. ISBN  978-0-521-51597-9. Zbl  1197.68006.
  • Lotari, M. (2011). So'zlar bo'yicha algebraik kombinatorika. Matematika entsiklopediyasi va uning qo'llanilishi. 90. Jan Berstel va Dominik Perrinning muqaddimasi bilan (2002 yilgi nashrning qayta nashr etilishi). Kembrij universiteti matbuoti. ISBN  978-0-521-18071-9. Zbl  1221.68183.
  • Pytheas Fogg, N. (2002). Berti, Valeri; Ferentszi, Sebastyan; Mod, nasroniy; Siegel, Anne (tahrir). Dinamikada, arifmetikada va kombinatorikada almashtirishlar. Matematikadan ma'ruza matnlari. 1794. Berlin: Springer-Verlag. ISBN  3-540-44141-7. Zbl  1014.11015.
  • An. Muchnik, A. Semenov, M. Ushakov, Deyarli davriy ketma-ketliklar, Nazariy. Hisoblash. Ilmiy ish. vol.304 № 1-3 (2003), 1-33.