Sesquipower

W matematyce sesquipower lub słowo Zimin to ciąg nad alfabetem z identycznym przedrostkiem i sufiksem . Sesquipowers są nieuniknionymi wzorami w tym sensie, że wszystkie wystarczająco długie ciągi zawierają jeden.

Definicja formalna

Formalnie niech A będzie alfabetem, a A ^∗ wolnym monoidem skończonych strun nad A . Każde niepuste słowo w w A ⁺ jest seskwipotą rzędu 1. Jeśli u jest seskwipotą rzędu n , to każde słowo w = uvu jest seskwipotą rzędu n + 1. Stopień niepustego słowa w to największa liczba całkowita d taka, że ​​w jest seskwipotą rzędu d .

Sekwencja biidealna

Sekwencja biidealna to _sekwencja słów fi _, gdzie f1 jest w A ⁺ i

${\ Displaystyle f_ {i + 1} = f_ {i} g_ {i} f_ {i} \}$

dla pewnego g _i w A ^∗ i i ≥ 1. Stopień słowa w jest zatem długością najdłuższej biidealnej sekwencji kończącej się na w .

Nieuniknione wzory

Dla skończonego alfabetu A na k literach istnieje liczba całkowita M zależna od k i n , taka że każde słowo o długości M ma współczynnik, który jest potęgą rzędu co najmniej n . Wyrażamy to mówiąc, że sesquipoty są wzorcami nieuniknionymi .

Sesquipowers w nieskończonych sekwencjach

Biorąc pod uwagę nieskończoną sekwencję biidealną, zauważamy, że każde f _i jest przedrostkiem f _{i +1} , a więc f _i zbiegają się w nieskończoną sekwencję

${\ Displaystyle f = f_ {1} g_ {1} f_ {1} g_ {2} f_ {1} g_ {1} f_{1}g_{3}f_{1}\cdots \ }$

Definiujemy nieskończone słowo jako potęgę seskwi, jeśli jest to granica nieskończonej sekwencji biidealnej. Nieskończone słowo jest seskwipotą wtedy i tylko wtedy, gdy jest to słowo powtarzające się , to znaczy każdy czynnik występuje nieskończenie często.

Ustal skończony alfabet A i załóż całkowity porządek liter. Dla danych liczb całkowitych p i n każde dostatecznie długie słowo w A ^∗ ma albo czynnik, który jest potęgą p , albo czynnik, który jest potęgą n -seskwi; w tym drugim przypadku czynnik ma n - faktoryzację na słowa Lyndona .

Zobacz też

• Wzór ABACABA

•    Berstel, Jan ; Lauve, Aaron; Reutenauer, Christophe; Saliola, Franco V. (2009). Kombinatoryka słów. Christoffel słowa i powtórzenia w słowach . Seria monografii CRM. Tom. 27. Providence, RI: Amerykańskie Towarzystwo Matematyczne . ISBN 978-0-8218-4480-9 . Zbl 1161.68043 .
•    Lothaire, M. (2011). Kombinatoryka algebraiczna słów . Encyklopedia matematyki i jej zastosowań . Tom. 90. Z przedmową Jeana Berstela i Dominique'a Perrina (przedruk wydania w twardej oprawie z 2002 r.). Wydawnictwo Uniwersytetu Cambridge. ISBN 978-0-521-18071-9 . Zbl 1221.68183 .
•    Pyteas Fogg, N. (2002). Berthé, Valérie ; Ferenczi, Sébastien; Mauduit, chrześcijanin; Siegel, Anne (red.). Podstawienia w dynamice, arytmetyce i kombinatoryce . Notatki z wykładów z matematyki. Tom. 1794. Berlin: Springer-Verlag . ISBN 3-540-44141-7 . Zbl 1014.11015 .