Морфическое слово - Morphic word - Wikipedia

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

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

Определение

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

${\displaystyle asf(s)f(f(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]

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

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

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

1. Lothaire (2005) стр. 524
2. Lothaire (2011) стр. 10
3. Хонкала (2010) стр.505
4. Lothaire (2011) стр. 11
5. Lothaire (2005) стр.525
6. Lothaire (2005) стр. 526
7. Хонкала (2010) стр.506

• Аллуш, Жан-Поль; Шаллит, Джеффри (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.