В математике и информатике, в морфическом слове или заменяющего слове бесконечной последовательность символов , которая строится из определенного класса эндоморфизма в виде свободного моноиде .
Каждая автоматическая последовательность морфична. [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 | ≥ | ш |, то г ν чисто морфическое слово, где г этого письмо не в A . [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 . Коллективный работа Жан 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 .