Комбинаторика по словам

Построение бесконечного слова Туэ–Морса.

Комбинаторика слов — довольно новая область математики , ответвленная от комбинаторики , которая фокусируется на изучении слов и формальных языков . Испытуемый смотрит на буквы или символы и последовательности , которые они образуют. Комбинаторика слов затрагивает различные области математического изучения, включая алгебру и информатику . В этой области был внесен широкий спектр вкладов. Некоторые из первых работ по словам без квадратов были написаны Акселя Туэ в начале 1900-х годов. Он и его коллеги наблюдали закономерности в словах и пытались их объяснить. Со временем комбинаторика слов стала полезна при изучении алгоритмов и кодирования . Это привело к развитию абстрактной алгебры и ответам на открытые вопросы.

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

Комбинаторика – это область дискретной математики . Дискретная математика – это изучение счетных структур. Эти объекты имеют определенное начало и конец. Изучение перечислимых объектов является противоположностью таких дисциплин, как анализ , где исчисление и бесконечные изучаются структуры. Комбинаторика изучает, как считать эти объекты, используя различные представления. Комбинаторика слов — это недавнее развитие в этой области, которое фокусируется на изучении слов и формальных языков. Формальный язык — это любой набор символов и комбинаций символов, которые люди используют для передачи информации. ^[1]

Сначала следует объяснить некоторую терминологию, имеющую отношение к изучению слов. Прежде всего, слово — это, по сути, последовательность символов или букв в конечном наборе . ^[1]Один из этих наборов известен широкой публике как алфавит . Например, слово «энциклопедия» — это последовательность символов английского алфавита , конечный набор из двадцати шести букв. Поскольку слово можно описать как последовательность, можно применить и другие основные математические описания. Алфавит — это множество , поэтому, как и следовало ожидать, пустое множество — это подмножество . Другими словами, существует единственное слово нулевой длины. Длина слова $w$ определяется количеством символов, составляющих последовательность, и обозначается $|w|$ . ^[1] Опять глядя на пример "энциклопедии", $|w|=12$ , поскольку в энциклопедии двенадцать букв. Идея факторизации больших чисел может быть применена к словам, где фактор слова представляет собой блок последовательных символов. ^[1] Таким образом, «циклоп» является фактором «энциклопедии».

Помимо изучения последовательностей самих по себе, еще одна область комбинаторики слов, которую следует учитывать, — это то, как их можно представить визуально. В математике для кодирования данных используются различные структуры. Общей структурой, используемой в комбинаторике, является древовидная структура . Древовидная структура — это граф которого , вершины соединены одной линией, называемой путем или ребром . Деревья могут не содержать циклов и могут быть полными или неполными. Можно закодировать слово, поскольку слово состоит из символов, а данные закодировать с помощью дерева. ^[1] Это дает визуальное представление об объекте.

Основные вклады [ править ]

Первые книги по комбинаторике со словами, обобщающими происхождение предмета, были написаны группой математиков под общим именем М. Лотара . Их первая книга была опубликована в 1983 году, когда комбинаторика слов получила более широкое распространение. ^[1]

Узоры [ править ]

Образцы в словах [ править ]

Основным вкладчиком в развитие комбинаторики слов был Аксель Туэ (1863–1922); он исследовал повторение. Главным вкладом Туэ было доказательство существования бесконечных слов без квадратов . Слова без квадратов не имеют соседних повторяющихся множителей. ^[1]Чтобы уточнить, «обеденный» не свободен от квадратов, поскольку «in» повторяется последовательно, а «servers» не свободен от квадратов, и его два фактора «er» не являются соседними. Туэ доказывает свою гипотезу о существовании бесконечных слов без квадратов с помощью подстановок . Замена – это способ взять символ и заменить его словом. Он использует эту технику для описания другого своего вклада — последовательности Туэ-Морса или слова Туэ-Морса. ^[1]

Туэ написал две статьи о словах без квадратов, вторая из которых была посвящена слову Туэ-Морса. Марстон Морс включен в название, потому что он обнаружил тот же результат, что и Туэ, но они работали независимо. Туэ также доказал существование слова без перекрытия. Слово без перекрытий – это когда для двух символов $x$ и $y$ , шаблон $xyxyx$ не существует в слове. В своей второй статье он продолжает доказывать связь между бесконечными словами без перекрытий и словами без квадратов. Он берет слова без перекрытий, созданные с использованием двух разных букв, и демонстрирует, как их можно преобразовать в слова из трех букв без квадратов с помощью замены. ^[1]

Как было описано ранее, слова изучаются путем изучения последовательностей, составленных символами. Закономерности найдены, и их можно описать математически. Паттерны могут быть либо шаблонами, которых можно избежать, либо неизбежными. Значительный вклад в исследование неизбежных закономерностей или закономерностей внес Фрэнк Рэмси в 1930 году. Его важная теорема утверждает, что для целых чисел $k$ , $m\geq 2$ , существует наименьшее положительное целое число $R(k,m)$ так что, несмотря на то, что полный граф раскрашен в два цвета, всегда будет существовать подграф сплошного цвета каждого цвета. ^[1]

Среди других авторов, внесших вклад в изучение неизбежных закономерностей, — ван дер Варден . Его теорема утверждает, что если положительные целые числа разбить на $k$ классы, то существует класс $c$ такой, что $c$ содержит арифметическую прогрессию некоторой неизвестной длины. Арифметическая прогрессия – это последовательность чисел, в которой разница между соседними числами остается постоянной. ^[1]

При рассмотрении неизбежных закономерностей полуторные степени изучаются также . Для некоторых шаблонов $x$ , $y$ , $z$ , полуторная степень имеет вид $x$ , $xyx$ , $xyxzxyx$ , $\ldots ~$ . Это еще один шаблон, такой как бесквадратный или неизбежный шаблон. Кудрэн и Шютценбергер в основном изучали эти полуторастепенные степени для приложений теории групп . Кроме того, Зимин доказал, что все полуторные степени неизбежны. Независимо от того, проявляется ли весь паттерн или периодически проявляется только некоторая часть полуторной степени, избежать этого невозможно. ^[1]

Шаблоны в алфавитах [ править ]

Ожерелья состоят из слов, состоящих из круговых последовательностей. Чаще всего они используются в музыке и астрономии . Флай Сент-Мари в 1894 году доказал существование $2^{2^{n-1}-n}$ бинарные de Bruijn длинные ожерелья $2^{n}$ . Ожерелье де Брейна содержит множители, состоящие из слов длины n из определенного количества букв. Слова появляются в ожерелье только один раз. ^[1]

В 1874 году Бодо разработал код, который в конечном итоге заменил азбуку Морзе, применив теорию бинарных ожерелий де Брейна. Проблема продолжалась от Сент-Мари до Мартина в 1934 году, который начал искать алгоритмы составления слов структуры де Брейна. Затем в 1943 году над ним работал Постум . ^[1]

Иерархия языков [ править ]

Возможно, наиболее прикладным результатом комбинаторики слов является иерархия Хомского , разработанная Ноамом Хомским . Он изучал формальный язык в 1950-х годах. ^[2]Его взгляд на язык упрощал предмет. Он игнорирует фактическое значение слова, не учитывает определенные факторы, такие как частота и контекст, и применяет шаблоны коротких терминов ко всем длинным терминам. Основная идея работы Хомского — разделить язык на четыре уровня, или языковую иерархию . Четыре уровня: обычный , контекстно-свободный , контекстно-зависимый и вычислимо перечислимый или неограниченный. ^[2]Регулярный — наименее сложный, а вычислимо перечислимый — самый сложный. Хотя его работа выросла из комбинаторики слов, она радикально повлияла на другие дисциплины, особенно на информатику . ^[3]

Типы слов [ править ]

Штурмовские слова [ править ]

Штурмовские слова , созданные Франсуа Штурмом, имеют корни в комбинаторике слов. Существует несколько эквивалентных определений слов Штурма. Например, бесконечное слово является штурмовским тогда и только тогда, когда оно имеет $n+1$ отдельные факторы длины $n$ , для каждого неотрицательного целого числа $n$ . ^[1]

Линдон Ворд [ править ]

Слово Линдона — это слово в заданном алфавите, записанное в простейшей и наиболее упорядоченной форме из соответствующего класса сопряженности . Слова Линдона важны, потому что для любого данного слова Линдона $x$ , существуют слова Линдона $y$ и $z$ , с $y<z$ , $x=yz$ . Кроме того, существует теорема Чена, Фокса и Линдона , которая утверждает, что любое слово имеет уникальную факторизацию слов Линдона, где слова факторизации не возрастают . Благодаря этому свойству слова Линдона используются для изучения алгебры , в частности теории групп . Они составляют основу идеи коммутаторов . ^[1]

Визуальное представление [ править ]

Кобэм внес работу, касающуюся Эжена Пруэ работы с конечными автоматами . Математический граф состоит из ребер и узлов . В конечных автоматах ребра помечены буквами алфавита. Чтобы использовать граф, нужно начать с узла и двигаться по ребрам, чтобы достичь конечного узла. Путь, пройденный по графу, образует слово. Это конечный граф, поскольку существует счетное число узлов и ребер, и только один путь соединяет два различных узла. ^[1]

Коды Гаусса , созданные Карлом Фридрихом Гауссом в 1838 году, разработаны на основе графиков. В частности, замкнутая кривая на плоскости необходима . Если кривая пересекает себя только конечное число раз, то точки пересечения помечаются буквами используемого алфавита. Путешествуя по кривой, слово определяется путем записи каждой буквы при прохождении пересечения. Гаусс заметил, что расстояние между моментами появления одного и того же символа в слове является четным целым числом . ^[1]

Теория групп [ править ]

Вальтер Франц Антон фон Дейк начал работу по комбинаторике слов в теории групп в своих опубликованных работах в 1882 и 1883 годах. Он начал с использования слов в качестве групповых элементов. Лагранж также внес свой вклад в 1771 году своей работой над группами перестановок . ^[1]

Одним из аспектов комбинаторики слов, изучаемых в теории групп, являются сокращенные слова. Группа состоит из слов некоторого алфавита, включая образующие и обратные элементы , исключая факторы, которые появляются в форме aā или āa для некоторого a в алфавите. Сокращенные слова образуются, когда коэффициенты aā, āa используются для сокращения элементов до тех пор, пока не будет получено уникальное слово. ^[1]

преобразования Нильсена Также были разработаны . Для множества элементов свободной группы преобразование Нильсена достигается тремя преобразованиями; замена элемента его обратным, замена элемента произведением самого себя и другого элемента и исключение любого элемента, равного 1. Путем применения этих преобразований Нильсена образуются сокращенные множества. Сокращенный набор означает, что ни один элемент не может быть умножен на другие элементы для полной компенсации. Имеются также связи с преобразованиями Нильсена со словами Штурма. ^[1]

Рассмотренные проблемы [ править ]

Одна из проблем, рассматриваемых при изучении комбинаторики слов в теории групп, заключается в следующем: для двух элементов $x$ , $y$ полугруппы ли , имеет $x=y$ модулю определяющих соотношений по $x$ и $y$ . Пост и Марков изучили эту проблему и определили ее неразрешимой , а это означает, что не существует алгоритма, который мог бы ответить на вопрос во всех случаях (потому что любой такой алгоритм может быть закодирован в словесную задачу, которую этот алгоритм не сможет решить). ^[1]

Вопрос Бернсайда был доказан с использованием существования бесконечного бескубного слова . Этот вопрос спрашивает, является ли группа конечной, если группа имеет определенное количество образующих и соответствует критериям $x^{n}=1$ , для $x$ в группе. ^[1]

Многие текстовые задачи неразрешимы на основе проблемы почтовой переписки . Любые два гомоморфизма $g,h$ с общим доменом и общим кодоменом образуют пример проблемы соответствия сообщений, в которой задается вопрос, существует ли слово $w$ в области такой, что $g(w)=h(w)$ . Пост доказал, что эта проблема неразрешима; следовательно, любая словесная задача, которую можно свести к этой основной проблеме, также неразрешима. ^[1]

Другие приложения [ править ]

Комбинаторика слов имеет приложения к уравнениям . Маканин доказал, что можно найти решение конечной системы уравнений, если уравнения составлены из слов. ^[1]

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

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

^ Перейти обратно: ^а ^б ^с ^д ^Это ^ж ^г ^час ^я ^дж ^к ^л ^м ^н ^О ^п ^д ^р ^с ^т ^в ^v ^В ^Икс ^и Берстель, Жан; Доминик Перрен (апрель 2007 г.). «Истоки комбинаторики о словах» . Европейский журнал комбинаторики . 28 (3): 996–1022. CiteSeerX 10.1.1.361.7000 . дои : 10.1016/j.ejc.2005.07.019 .
^ Перейти обратно: ^а ^б Ягер, Герхард; Джеймс Роджерс (июль 2012 г.). «Теория формального языка: уточнение иерархии Хомского» . Философские труды Королевского общества Б. 367 (1598): 1956–1970. дои : 10.1098/rstb.2012.0077 . ПМК 3367686 . ПМИД 22688632 .
^ Моралес-Буэно, Рафаэль; Баэна-Гарсия, Мануэль; Кармона-Сехудо, Хосе М.; Кастильо, Глэдис (2010). «Подсчет факторов, избегающих слов». Электронный журнал математики и технологий . 4 (3): 251.

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

Истоки комбинаторики слов , Жан Берстель, Доминик Перрен , Европейский журнал комбинаторики 28 (2007) 996–1022
Комбинаторика слов – учебник , Жан Берстель и Юхани Кархумяки. Бык. Евро. доц. Теор. Вычислить. наук. EATCS, 79:178–228, 2003.
Комбинаторика слов: новая сложная тема , Юхани Кархумяки.
Шоффрут, Кристиан; Кархумяки, Юхани (1997). «Комбинаторика слов». В Розенберге, Гжегоже; Саломаа, Арто (ред.). Справочник формальных языков . Том. 1. Спрингер. CiteSeerX 10.1.1.54.3135 . ISBN 978-3-540-60420-4 .
Лотер, М. (1983), Комбинаторика слов , Энциклопедия математики и ее приложений, том. 17, издательство Addison-Wesley Publishing Co., Ридинг, Массачусетс, ISBN 978-0-201-13516-9 , МР 0675953 , Збл 0514.20045
Лотер, М. (2002), Алгебраическая комбинаторика слов , Энциклопедия математики и ее приложений, том. 90, Издательство Кембриджского университета , ISBN 978-0-521-81220-7 , МР 1905123 , Збл 1001.68093
«Бесконечные слова: автоматы, полугруппы, логика и игры», Доминик Перрен, Жан Эрик Пен, Academic Press, 2004 г., ISBN 978-0-12-532111-2 .
Лотер, М. (2005), Прикладная комбинаторика слов , Энциклопедия математики и ее приложений, том. 105, Издательство Кембриджского университета , ISBN 978-0-521-84802-2 , МР 2165687 , Збл 1133.68067
« Алгоритмическая комбинаторика частичных слов », Франсин Бланше-Садри, CRC Press, 2008 г., ISBN 978-1-4200-6092-8 .
Берстель, Жан; Лауве, Аарон; Ройтенауэр, Кристоф; Салиола, Франко В. (2009), Комбинаторика слов. Слова Кристоффеля и повторы в словах , Серия монографий CRM, том. 27, Провиденс, Род-Айленд: Американское математическое общество , ISBN. 978-0-8218-4480-9 , Збл 1161.68043
«Комбинаторика композиций и слов», Сильвия Хойбах , Туфик Мансур , CRC Press, 2009 г., ISBN 978-1-4200-7267-9 .
«Словарные уравнения и смежные темы: 1-й международный семинар, IWWERT '90, Тюбинген, Германия, 1–3 октября 1990 г.: материалы», редактор: Клаус Ульрих Шульц, Springer, 1992 г., ISBN 978-3-540-55124-9
« Жемчужины стрингологии: текстовые алгоритмы », Максим Крошмор, Войцех Риттер , World Scientific, 2003 г., ISBN 978-981-02-4897-0
Берта, Валери ; Риго, Мишель, ред. (2010). Комбинаторика, автоматы и теория чисел . Энциклопедия математики и ее приложений. Том. 135. Кембридж: Издательство Кембриджского университета . ISBN 978-0-521-51597-9 . Збл 1197.68006 .
Берстель, Жан; Ройтенауэр, Кристоф (2011). Некоммутативные рациональные ряды с приложениями . Энциклопедия математики и ее приложений. Том. 137. Кембридж: Издательство Кембриджского университета . ISBN 978-0-521-19022-0 . Збл 1250.68007 .
«Шаблоны в перестановках и словах», Сергей Китаев , Springer, 2011, ISBN 9783642173325
«Распределение по модулю единицы и диофантово приближение», Ян Бюжо, издательство Кембриджского университета, 2012 г., ISBN 9780521111690

Внешние ссылки [ править ]

[Origins-1] Перейти обратно: ^а ^б ^с ^д ^Это ^ж ^г ^час ^я ^дж ^к ^л ^м ^н ^О ^п ^д ^р ^с ^т ^в ^v ^В ^Икс ^и Берстель, Жан; Доминик Перрен (апрель 2007 г.). «Истоки комбинаторики о словах» . Европейский журнал комбинаторики . 28 (3): 996–1022. CiteSeerX 10.1.1.361.7000 . дои : 10.1016/j.ejc.2005.07.019 .

[Chomsky-2] Перейти обратно: ^а ^б Ягер, Герхард; Джеймс Роджерс (июль 2012 г.). «Теория формального языка: уточнение иерархии Хомского» . Философские труды Королевского общества Б. 367 (1598): 1956–1970. дои : 10.1098/rstb.2012.0077 . ПМК 3367686 . ПМИД 22688632 .

[Word_Avoiding-3] Моралес-Буэно, Рафаэль; Баэна-Гарсия, Мануэль; Кармона-Сехудо, Хосе М.; Кастильо, Глэдис (2010). «Подсчет факторов, избегающих слов». Электронный журнал математики и технологий . 4 (3): 251.

[1]

[2]

[3]