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

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

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

Определение

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

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

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

Примеры

Система D0L

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

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

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

  1. ^ а б c d Lothaire (2005) стр. 524
  2. ^ Lothaire (2011) стр. 10
  3. ^ Хонкала (2010) стр.505
  4. ^ а б Lothaire (2011) стр. 11
  5. ^ а б c 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.

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