Морфическое слово - Википедия - Morphic word

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

Каждый автоматическая последовательность морфный.^[1]

Определение

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

${ Displaystyle asf (s) е (е (s)) cdots f ^ {(n)} (s) cdots }$

это чистый морфический или же чистое замещающее слово. Обратите внимание, что это предел последовательности а, ж(а), ж(ж(а)), ж(ж(ж(а))), ... Ясно, что это неподвижная точка эндоморфизма ж: уникальная такая последовательность, начинающаяся с буквы а.^[2][3] Вообще говоря, морфическое слово - это изображение чистого морфического слова при кодировании.^[1]

Если морфическое слово строится как неподвижная точка продолжаемого k-равномерный морфизм на А^∗ тогда слово k-автоматический. В п-й член в такой последовательности может быть произведен конечный автомат чтение цифр п в базе k.^[1]

Примеры

• В Последовательность Туэ – Морса порождается над {0,1} 2-равномерным эндоморфизмом 0 → 01, 1 → 10.^[4][5]
• В Слово Фибоначчи генерируется за {а,б} эндоморфизмом а → ab, б → а.^[1][4]
• В слово трибоначчи генерируется за {а,б,c} эндоморфизмом а → ab, б → ac, c → а.^[5]
• В Последовательность Рудина – Шапиро получается из неподвижной точки 2-равномерного морфизма а → ab, б → ac, c → db, d → Округ Колумбия с последующим кодированием а,б → 0, c,d → 1.^[5]
• В обычная последовательность складывания бумаги получается из неподвижной точки 2-равномерного морфизма а → ab, б → cb, c → объявление, d → CD с последующим кодированием а,б → 0, c,d → 1.^[6]

Система D0L

А Система D0L (детерминированный контекстно-свободный Система Линденмайера ) задается словом ш свободного моноида А^∗ по алфавиту А вместе с морфизмом σ, продолжаемым в ш. Система порождает бесконечное слово D0L ω = lim_п→∞ σ^п(ш). Чисто морфические слова - это слова D0L, но не наоборот. Однако если ω = тыν - бесконечное слово D0L с начальным отрезком ты длины |ты| ≥ |ш|, тогда zν - чисто морфное слово, где z это письмо не в А.^[7]

Смотрите также

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

Рекомендации

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

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

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