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

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

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

Определение

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

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

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

Основные вклады

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

Узоры

Закономерности в словах

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

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

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

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

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

Закономерности в алфавитах

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

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

Иерархия языка

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

Типы слов

Штурмовские слова

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

слово Линдона

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

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

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

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

Теория групп

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

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

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

Рассмотренные проблемы

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

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

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

Другие приложения

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

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

• Слово Фибоначчи
• последовательность Колакоски
• Лемма Леви
• Частичное слово
• Сдвиг пространства
• Метрика слов
• Текстовая задача (вычислимость)
• Текстовая задача (математика)
• Текстовая задача для групп
• Решетка Юнга–Фибоначчи

Ссылки

1. Берстель, Жан; Доминик Перрен (апрель 2007 г.). «Истоки комбинаторики слов». Европейский журнал комбинаторики . 28 (3): 996–1022. CiteSeerX  10.1.1.361.7000 . doi : 10.1016/j.ejc.2005.07.019 .
2. Jäger, Gerhard; James Rogers (июль 2012 г.). «Формальная теория языка: уточнение иерархии Хомского». Philosophical Transactions of the Royal Society B . 367 (1598): 1956–1970. doi :10.1098/rstb.2012.0077. PMC 3367686 . PMID  22688632. 
3. Моралес-Буэно, Рафаэль; Баэна-Гарсия, Мануэль; Кармона-Сехудо, Хосе М.; Кастильо, Глэдис (2010). «Подсчет факторов, избегающих слов». Электронный журнал математики и технологий . 4 (3): 251.

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

• Истоки комбинаторики слов, Жан Берстель, Доминик Перрен , Европейский журнал комбинаторики 28 (2007) 996–1022
• Комбинаторика слов – учебник, Жан Берстель и Юхани Кархумаки. Bull. Eur. Assoc. Theor. Comput. Sci. 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, MR  0675953, Zbl  0514.20045
• Лотер, М. (2002), Алгебраическая комбинаторика слов , Энциклопедия математики и ее приложений, т. 90, Cambridge University Press , ISBN 978-0-521-81220-7, MR  1905123, Zbl  1001.68093
• «Бесконечные слова: автоматы, полугруппы, логика и игры», Доминик Перрен, Жан Эрик Пэн, Academic Press, 2004, ISBN 978-0-12-532111-2 . 
• Лотер, М. (2005), Прикладная комбинаторика слов , Энциклопедия математики и ее приложений, т. 105, Cambridge University Press , ISBN 978-0-521-84802-2, MR  2165687, Zbl  1133.68067
• « Алгоритмическая комбинаторика частичных слов », Франсин Бланше-Садри, CRC Press, 2008, ISBN 978-1-4200-6092-8 . 
• Berstel, Jean; Lauve, Aaron; Reutenauer, Christophe; Saliola, Franco V. (2009), Комбинаторика слов. Слова Кристоффеля и повторения в словах, CRM Monograph Series, т. 27, Providence, RI: American Mathematical Society , 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. Кембридж: Cambridge University Press . ISBN 978-0-521-51597-9. Збл  1197.68006.
• Берстель, Жан; Ройтенауэр, Кристоф (2011). Некоммутативные рациональные ряды с приложениями . Энциклопедия математики и ее приложений. Том 137. Кембридж: Cambridge University Press . ISBN 978-0-521-19022-0. Збл  1250.68007.
• «Закономерности в перестановках и словах», Сергей Китаев , Springer, 2011, ISBN 9783642173325 
• «Распределение по модулю один и диофантово приближение», Ян Бюжо, Cambridge University Press, 2012, ISBN 9780521111690 

Внешние ссылки

• Страница Жана Берстеля
• Страница Теро Харью
• Страница Гая Мелансона