Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску
Построение бесконечного слова Туэ – Морса

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

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

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

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

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

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

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

Выкройки [ править ]

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

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

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

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

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

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

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

Ожерелья состоят из слов, имеющих круговую последовательность. Чаще всего они используются в музыке и астрономии . Flye Sainte-Marie в 1894 году доказал, что существует 2 2 n −1 - n бинарных ожерелий де Брейна длиной 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]

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

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

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

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

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

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

  1. ^ Б с д е е г ч я J к л м п о р а Q R сек т у V ш х у Berstel, Jean; Доминик Перрен (апрель 2007 г.). «Истоки комбинаторики слов». Европейский журнал комбинаторики . 28 (3): 996–1022. DOI : 10.1016 / j.ejc.2005.07.019 .
  2. ^ а б Ягер, Герхард; Джеймс Роджерс (июль 2012 г.). «Теория формального языка: уточнение иерархии Хомского» . Философские труды Королевского общества B . 367 (1598): 1956–1970. DOI : 10,1098 / rstb.2012.0077 . PMC 3367686 . PMID 22688632 .  
  3. ^ Моралес-Буэно, Рафаэль; Баэна-Гарсия, Мануэль; Кармона-Сехудо, Хосе М .; Кастильо, Глэдис (2010). «Подсчет факторов, избегающих слов». Электронный журнал математики и технологий . 4 (3): 251.

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

  • Истоки комбинаторики слов , Жан Берстель, Доминик Перрен , Европейский журнал комбинаторики 28 (2007) 996–1022
  • Комбинаторика слов - учебное пособие , Жан Берштель и Юхани Кархумяки. Бык. Евро. Доц. Теор. Comput. Sci. EATCS, 79: 178–228, 2003.
  • Комбинаторика слов: новая сложная тема , Юхани Кархумяки.
  • Чоффрут, Кристиан; Кархумяки, Юхани (1997). «Комбинаторика слов». В Розенберге, Гжегоже; Саломаа, Арто (ред.). Справочник формальных языков . 1 . Springer. 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 , Zbl  0514.20045 CS1 maint: обескураженный параметр ( ссылка )
  • Лотэр, М. (2002), Алгебраическая комбинаторика слов , Энциклопедия математики и ее приложений, 90 , Cambridge University Press , ISBN 978-0-521-81220-7, Руководство по ремонту  1905123 , Zbl  1001.68093 CS1 maint: обескураженный параметр ( ссылка )
  • «Бесконечные слова: автоматы, полугруппы, логика и игры», Доминик Перрен, Жан Эрик Пин, Academic Press, 2004, ISBN 978-0-12-532111-2 . 
  • Лотэр, М. (2005), Прикладная комбинаторика слов , Энциклопедия математики и ее приложений, 105 , Cambridge University Press , ISBN 978-0-521-84802-2, Руководство по ремонту  2165687 , Zbl  1133.68067 CS1 maint: обескураженный параметр ( ссылка )
  • « Алгоритмическая комбинаторика частичных слов », Франсин Бланше-Садри, CRC Press, 2008, ISBN 978-1-4200-6092-8 . 
  • Берстель, Жан; Лаув, Аарон; Ройтенауэр, Кристоф; Салиола, Франко В. (2009), Комбинаторика слов. Слова Кристоффеля и повторения в словах , Серия монографий CRM, 27 , Провиденс, Род-Айленд: Американское математическое общество , ISBN 978-0-8218-4480-9, Zbl  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. Zbl  1197.68006 .
  • Берстель, Жан; Ройтенауэр, Кристоф (2011). Некоммутативные рациональные ряды с приложениями . Энциклопедия математики и ее приложений. 137 . Кембридж: Издательство Кембриджского университета . ISBN 978-0-521-19022-0. Zbl  1250,68007 .
  • «Паттерны в перестановках и словах», Сергей Китаев, Springer, 2011, ISBN 9783642173325 
  • «Распределение по модулю один и диофантово приближение», Ян Бюжо, Cambridge University Press, 2012, ISBN 9780521111690 

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

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