Морфическое слово

В математике и информатике морфное слово или слово-заместитель представляет собой бесконечную последовательность символов, построенную на основе определенного класса эндоморфизма свободного моноида .

Любая автоматическая последовательность морфична.

Определение

Пусть f — эндоморфизм свободного моноида A ^∗ в алфавите A со свойством, что существует буква a такая, что f ( a ) = как и для непустой строки s : мы говорим, что f является продолжаемой в a . Слово

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

— чисто морфическое или чисто замещающее слово . Заметим, что это предел последовательности a , f ( a ), f ( f ( a )), f ( f ( f ( a )))),...Очевидно, это неподвижная точка эндоморфизма f : единственная такая последовательность, начинающаяся с буквы a . В общем, морфическое слово — это образ чистого морфного слова под кодировкой, то есть морфизм, отображающий букву в букву.

Если морфное слово построено как неподвижная точка продолжаемого k - равномерного морфизма на A ^∗ тогда слово k - автоматическое . n - й член такой последовательности может быть получен конечным автоматом, считывающим цифры n по базе k .

Примеры

• Последовательность Туэ–Морса порождается над {0,1} 2-равномерным эндоморфизмом 0 → 01, 1 → 10.
• Слово Фибоначчи порождается над { a , b } эндоморфизмом a → ab , b → a .
• Слово трибоначчи порождается над { a , b , c } эндоморфизмом a → ab , b → ac , c → a .
• Последовательность Рудина–Шапиро получается из неподвижной точки 2-равномерного морфизма a → ab , b → ac , c → db , d → dc с последующим кодированием a , b → 0, c , d → 1.
• Регулярная последовательность складывания бумаги получается из неподвижной точки 2-равномерного морфизма a → ab , b → cb , c → ad , d → cd с последующим кодированием a , b → 0, c , d → 1.

Система Д0Л

Система D0L (детерминированная контекстно-свободная система Линденмайера ) задается словом w свободного моноида A ^∗ на алфавите A вместе с морфизмом σ, продолжаемым в w . Система генерирует бесконечное слово D0L ω = lim _{n →∞} σ ^н ( ш ). Чисто морфические слова являются словами D0L, но не наоборот. Однако если ω = u ν — бесконечное слово D0L с начальным отрезком u длины | ты | ≥ | w |, то z ν — чисто морфное слово, где z — буква, не принадлежащая A .

См. также

• Последовательность резки
• Линдон слово
• Слово Холла
• Штурмовское слово

Ссылки

• Аллуш, Жан-Поль; Шалит, Джеффри (2003). Автоматические последовательности: теория, приложения, обобщения . Издательство Кембриджского университета . ISBN  978-0-521-82332-6 . Збл   1086.11015 .
• Хонкала, Юха (2010). «Проблема равенства чисто замещающих слов». В Берте, Валери ; Риго, Мишель (ред.). Комбинаторика, автоматы и теория чисел . Энциклопедия математики и ее приложений. Том. 135. Кембридж: Издательство Кембриджского университета . стр. 505–529. ISBN  978-0-521-51597-9 . Збл   1216.68209 .
• Лотер, М. (2005). Прикладная комбинаторика к словам . Энциклопедия математики и ее приложений. Том. 105. Коллективная работа Жана Берстеля , Доминика Перрена, Максима Крошмора , Эрика Лапорта, Мехрияра Мори , Нади Пизанти, Мари-Франс Саго, Жезины Рейнерт , Софи Шбат , Михаэля Уотермана , Филиппа Жаке, Войцеха Шпанковского , Доминика Пулалона, Жиля Шеффера, Роман Колпаков, Григорий Кучеров, Жан-Поль Аллуш и Валери Берте . Кембридж: Издательство Кембриджского университета . ISBN  0-521-84802-4 . Збл   1133.68067 .
• Лотер, М. (2011). Алгебраическая комбинаторика на словах . Энциклопедия математики и ее приложений. Том. 90. С предисловием Жана Берстеля и Доминика Перрена (перепечатка издания 2002 г. в твердом переплете). Издательство Кембриджского университета. ISBN  978-0-521-18071-9 . Артикул   1221.68183 .

Дальнейшее чтение

• Кассень, Жюльен; Кархумяки, Юхани (1997). «Слова Тёплица, обобщенная периодичность и периодически повторяющиеся морфизмы» . Европейский журнал комбинаторики . 18 (5): 497–510. дои : 10.1006/eujc.1996.0110 . Збл   0881.68065 .