Из Википедии, бесплатной энциклопедии
  (Перенаправлен из Prolongable morphism )
Перейти к навигации Перейти к поиску

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

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

Определение [ править ]

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

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

Если морфическое слово строятся как неподвижная точка могущего быть продленными к - однородный морфизм на A * , то слово к - автоматическому . П -й член в такой последовательности может быть получен с помощью конечного автомата чтения цифр п в базовых к . [1]

Примеры [ править ]

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

Система D0L [ править ]

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

См. Также [ править ]

Ссылки [ править ]

  1. ^ Б с д Lothaire (2005) p.524
  2. ^ Lothaire (2011) стр. 10
  3. ^ Хонкала (2010) p.505
  4. ^ a b Lothaire (2011) стр. 11
  5. ^ Б с Lothaire (2005) P.525
  6. ^ Lothaire (2005) P.526
  7. ^ Хонкала (2010) p.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 . Коллективный работа Жан Berstel Доминик Перрен, Максим Крошемор , Эрик Лапорта, Меряр Мори , Надя Pisanti, Мари-Франс Sagot, Гезине Рейнертом , Софи Schbath , Майкл Waterman , Филипп Жаке, Войцех Szpankowski , Доминик Poulalhon, Жиль Шеффера, Роман Колпаков , Грегори Кушеров, Жан-Поль Аллуш и Валери Берте . Кембридж: Издательство Кембриджского университета . ISBN 0-521-84802-4. Zbl  1133.68067 . CS1 maint: обескураженный параметр ( ссылка )
  • Лотэр, М. (2011). Алгебраическая комбинаторика слов . Энциклопедия математики и ее приложений. 90 . С предисловием Жана Берштеля и Доминика Перрена (перепечатка издания 2002 года в твердом переплете). Издательство Кембриджского университета. ISBN 978-0-521-18071-9. Zbl  1221.68183 . CS1 maint: обескураженный параметр ( ссылка )

Дальнейшее чтение [ править ]

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