Morfik so'z - Morphic word

Matematika va informatika fanida a morfik so'z yoki o'rnini bosuvchi so'z ning ma'lum bir sinfidan tuzilgan cheksiz belgilar qatori endomorfizm a bepul monoid.

Har bir avtomatik ketma-ketlik morfik^[1]

Ta'rif

Ruxsat bering f erkin monoidning endomorfizmi bo'lishi mumkin A^∗ alifboda A xat bo'lgan mulk bilan a shu kabi f(a) = kabi bo'sh bo'lmagan mag'lubiyat uchun s: biz buni aytamiz f bu uzaytirilishi mumkin da a. So'z

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

a sof morfik yoki sof o'rnini bosuvchi so'z. E'tibor bering, bu ketma-ketlikning chegarasi a, f(a), f(f(a)), f(f(f(a))), ... Bu aniq endomorfizmning sobit nuqtasidir f: harf bilan boshlanadigan noyob bunday ketma-ketlik a.^[2][3] Umuman olganda morfik so'z - bu sof morfik so'zning kodlash ostidagi obrazidir.^[1]

Agar morfik so'z uzaytiriladigan narsaning sobit nuqtasi sifatida tuzilgan bo'lsa k-bir xil morfizm kuni A^∗ unda so'z k-avtomatik. The n- bunday ketma-ketlikdagi uchinchi muddat a tomonidan ishlab chiqarilishi mumkin cheklangan holatdagi avtomat raqamlarini o'qish n bazada k.^[1]

Misollar

• The Thue-Morse ketma-ketligi 0-dan 01-gacha, 1-dan 10-gacha bo'lgan 2-darajali endomorfizm orqali {0,1} dan yuqori hosil bo'ladi.^[4][5]
• The Fibonachchi so'zi {dan ortiq hosil qilingana,b} endomorfizm bilan a → ab, b → a.^[1][4]
• The tribonachchi so'zi {dan ortiq hosil qilingana,b,v} endomorfizm bilan a → ab, b → ak, v → a.^[5]
• The Rudin-Shapiro ketma-ketligi 2-shaklli morfizmning sobit nuqtasidan olinadi a → ab, b → ak, v → db, d → DC keyin kodlash a,b → 0, v,d → 1.^[5]
• The muntazam qog'oz qog'ozlarini ketma-ketligi 2-shaklli morfizmning sobit nuqtasidan olinadi a → ab, b → cb, v → reklama, d → CD keyin kodlash a,b → 0, v,d → 1.^[6]

D0L tizimi

A D0L tizimi (deterministik kontekstsiz) Lindenmayer tizimi ) so'z bilan berilgan w bepul monoid A^∗ alifboda A morfizm bilan birgalikda σ at cho'zilishi mumkin w. Tizim cheksiz D0L so'zini ω = lim hosil qiladi_n→∞ σⁿ(w). Sof morfik so'zlar D0L so'zlar, ammo aksincha emas. Ammo, agar ω = bo'lsa sizν - boshlang'ich segmenti bo'lgan cheksiz D0L so'zi siz uzunligi |siz| ≥ |w|, keyin zν bu sof morfik so'z, bu erda z bu xat emas A.^[7]

Shuningdek qarang

• Kesish ketma-ketligi
• Lyndon so'zi
• Zal so'zi
• Sturmcha so'z

Adabiyotlar

• 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.
• Honkala, Juha (2010). "Faqat o'rnini bosadigan so'zlar uchun tenglik muammosi". Yilda Berti, Valeri; Rigo, Mishel (tahrir). Kombinatorika, avtomatika va raqamlar nazariyasi. Matematika entsiklopediyasi va uning qo'llanilishi. 135. Kembrij: Kembrij universiteti matbuoti. 505-529 betlar. ISBN  978-0-521-51597-9. Zbl  1216.68209.
• Lotari, M. (2005). So'zlar bo'yicha qo'llaniladigan kombinatorika. Matematika entsiklopediyasi va uning qo'llanilishi. 105. Tomonidan kollektiv ish Jan Berstel, Dominik Perrin, Maksim Krohemor, Erik Laport, Mehryar Mohri, Nadiya Pisanti, Mari-Frans Sagot, Gesine Reinert, Sofi Shbat, Maykl Waterman, Filipp Jak, Voytsex Shpankovski, Dominik Poulxon, Gill Sheffer, Roman Kolpakov, Gregori Kucherov, Jan-Pol Alloush va Valeri Berthe. Kembrij: Kembrij universiteti matbuoti. ISBN  0-521-84802-4. Zbl  1133.68067.
• 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.

Qo'shimcha o'qish

• Kasseyn, Julien; Karxumaki, Juxani (1997). "Toeplitz so'zlari, umumlashtirilgan davriylik va davriy takrorlanadigan morfizmlar". Evropa Kombinatorika jurnali. 18: 497–510. doi:10.1006 / eujc.1996.0110. Zbl  0881.68065.