Морфическое слово

You can help expand this article with text translated from the corresponding article in French. (June 2021) Click [show] for important translation instructions. Machine translation, like DeepL or Google Translate, is a useful starting point for translations, but translators must revise errors as necessary and confirm that the translation is accurate, rather than simply copy-pasting machine-translated text into the English Wikipedia. Consider adding a topic to this template: there are already 1,808 articles in the main category, and specifying|topic= will aid in categorization. Do not translate text that appears unreliable or low-quality. If possible, verify the text with references provided in the foreign-language article. You must provide copyright attribution in the edit summary accompanying your translation by providing an interlanguage link to the source of your translation. A model attribution edit summary is Content in this edit is translated from the existing French Wikipedia article at [[:fr:Mot morphique]]; see its history for attribution. You may also add the template {{Translated|fr|Mot morphique}} to the talk page. For more guidance, see Wikipedia:Translation.

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

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

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

${\displaystyle asf(s)f(f(s))\cdots f^{(n)}(s)\cdots \ }$

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

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

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

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

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

• Allouche, Jean-Paul; Shallit, Jeffrey (2003). Автоматические последовательности: теория, приложения, обобщения . Cambridge University Press . ISBN 978-0-521-82332-6. Збл  1086.11015.
• Honkala, Juha (2010). "Проблема равенства для чисто замещающих слов". В Berthé, Valérie ; Rigo, Michel (ред.). Комбинаторика, автоматы и теория чисел . Энциклопедия математики и ее приложений. Том 135. Кембридж: Cambridge University Press . С.  505–529 . ISBN 978-0-521-51597-9. Збл  1216.68209.
• Лотер, М. (2005). Прикладная комбинаторика к словам . Энциклопедия математики и ее приложений. Том. 105. Коллективная работа Жана Берстеля , Доминика Перрена, Максима Крошмора , Эрика Лапорта, Мехрияра Мори , Нади Пизанти, Мари-Франс Саго, Жезины Рейнерт , Софи Шбат , Михаэля Уотермана , Филиппа Жаке, Войцеха Шпанковского , Доминика Пулалона, Жиля Шеффера, Роман Колпаков, Григорий Кучеров, Жан-Поль Аллуш и Валери Берте . Кембридж: Издательство Кембриджского университета . ISBN 0-521-84802-4. Збл  1133.68067.
• Лотер, М. (2011). Алгебраическая комбинаторика слов . Энциклопедия математики и ее приложений. Т. 90. С предисловием Жана Берстеля и Доминика Перрена (Переиздание издания 2002 года в твердом переплете). Cambridge University Press. ISBN 978-0-521-18071-9. Збл  1221.68183.

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