Бесплатный моноид

В абстрактной алгебре свободный моноид в множестве — это моноид , элементами которого являются все конечные последовательности (или строки) нуля или более элементов из этого набора, с конкатенацией строк в качестве операции моноида и с уникальной последовательностью нулевых элементов, часто называется пустой строкой и обозначается ε или λ как единичный элемент . Свободный моноид на множестве A обычно обозначается A ^∗ . полугруппа Свободная на A подполугруппа A. это — ^∗ содержащий все элементы, кроме пустой строки. Обычно его обозначают А. ⁺ .

В более общем смысле абстрактный моноид (или полугруппа) S описывается как свободный , если он изоморфен свободному моноиду (или полугруппе) на некотором множестве.

Как следует из названия, свободные моноиды и полугруппы — это те объекты, которые удовлетворяют обычному универсальному свойству, определяющему свободные объекты , в соответствующих категориях моноидов и полугрупп. Отсюда следует, что каждый моноид (или полугруппа) возникает как гомоморфный образ свободного моноида (или полугруппы). Изучение полугрупп как образов свободных полугрупп называется комбинаторной теорией полугрупп.

Свободные моноиды (и моноиды вообще) ассоциативны по определению; то есть они записываются без каких-либо скобок, чтобы показать группировку или порядок работы. Неассоциативный эквивалент — свободная магма .

Примеры

Натуральные числа

Моноид ( N ₀ ,+) натуральных чисел (включая ноль) при сложении является свободным моноидом на одноэлементном свободном генераторе, в данном случае натуральном числе 1. Согласно формальному определению, этот моноид состоит из всех последовательностей типа «1», «1+1», «1+1+1», «1+1+1+1» и т. д., включая пустую последовательность. Сопоставление каждой такой последовательности с результатом ее оценки и пустая последовательность, равная нулю, устанавливает изоморфизм множества таких последовательностей с N ₀ .Этот изоморфизм совместим с «+», то есть для любых двух последовательностей s и t , если s отображается (т.е. оценивается) в число m и t в n , то их конкатенация s + t отображается в сумму m + н .

Клини звезда

В теории формального языка конечный набор «символов» A (иногда называемый алфавитом обычно рассматривается ). Конечная последовательность символов называется «словом над А », а свободный моноид А ^∗ называется « Звездой Клини А » .Таким образом, абстрактное изучение формальных языков можно рассматривать как изучение подмножеств конечно порожденных свободных моноидов.

Например, если предположить, что алфавит A = { a , b , c }, его звезда Клини A ^∗ содержит все конкатенации a , b и c :

{ε, a , ab , ba , ca , cccbabbc , ...}.

Если A — любое множество, функция длины слова на A ^∗ — единственный моноидный гомоморфизм из A ^∗ в ( N ₀ ,+), который отображает каждый элемент A в 1. Таким образом, свободный моноид является градуированным моноидом . (Градуированный моноид $M$ является моноидом, который можно записать как $M=M_{0}\oplus M_{1}\oplus M_{2}\cdots$. Каждый $M_{n}$ это сорт; оценка здесь - это просто длина строки. То есть, $M_{n}$ содержит строки длины $n.$ $\oplus$ символ здесь можно понимать как «объединение множеств»; он используется вместо символа $\cup$ потому что, как правило, объединения множеств могут не быть моноидами, поэтому используется отдельный символ. По соглашению градации всегда пишутся с помощью $\oplus$ символ.)

Между теорией полугрупп и теорией автоматов существуют глубокие связи . Например, каждый формальный язык имеет синтаксический моноид , распознающий этот язык. В случае регулярного языка этот моноид изоморфен моноиду перехода, ассоциированному с полуавтоматом некоторого детерминированного конечного автомата, распознающего этот язык. Регулярные языки над алфавитом А представляют собой замыкание конечных подмножеств А*, свободного моноида над А при объединении, произведении и порождении субмоноида.

В случае параллельных вычислений , то есть систем с блокировками , мьютексами или объединениями потоков , вычисления могут быть описаны с помощью моноидов истории и моноидов трассировки . Грубо говоря, элементы моноида могут коммутировать (например, разные потоки могут выполняться в любом порядке), но только до блокировки или мьютекса, которые предотвращают дальнейшую коммутацию (например, сериализовать доступ потока к какому-либо объекту).

Сопряженные слова

Пример для первого случая равноделимости: m="UNCLE", n="ANLY", p="UN", q="CLEANLY" и s="CLE"

Определим пару слов в A ^∗ формы uv и vu как сопряженные : таким образом, сопряженные слова представляют собой его круговые сдвиги . Два слова сопряжены в этом смысле, если они сопряжены в смысле теории групп как элементы свободной группы, порожденной A .

Равноделимость

Свободный моноид является равноделимым : если выполняется уравнение mn = pq , то существует s такой, что либо m = ps , sn = q (пример см. изображение), либо ms = p , n = sq . Этот результат также известен как лемма Леви .

Моноид свободен тогда и только тогда, когда он градуирован (в сильном смысле, что только тождество имеет градуировку 0) и равноделим.

Бесплатные генераторы и ранг

Члены множества A называются свободными образующими для A. ^∗ и А ⁺ . Надстрочный индекс * обычно понимается как звезда Клини . В более общем смысле, если S — абстрактный свободный моноид (полугруппа), то набор элементов, который отображается на множество однобуквенных слов при изоморфизме в моноид A. ^∗ (полугруппа А ⁺ ) называется набором свободных образующих для S .

Каждый свободный моноид (или полугруппа) S набор свободных образующих, мощность которого называется рангом S имеет ровно один .

Два свободных моноида или полугруппы изоморфны тогда и только тогда, когда они имеют одинаковый ранг. Фактически, каждый набор генераторов свободного моноида или полугруппы S содержит свободные генераторы, поскольку свободный генератор имеет длину слова 1 и, следовательно, может быть сгенерирован только сам по себе. Отсюда следует, что свободная полугруппа или моноид конечно порождена тогда и только тогда, когда она имеет конечный ранг.

Субмоноид ​ N из A ^∗ стабильно , если u , v , ux , xv в N подразумевают x в N. вместе Субмоноид A ^∗ стабильна тогда и только тогда, когда она свободна. Например, используя набор битов { "0", "1" } в качестве A , набор N всех битовых строк, содержащих четное количество "1", является стабильным субмоноидом, потому что, если u содержит четное количество "1" "s", а ux также , то x также должно содержать четное количество "1". Хотя N не может быть свободно сгенерировано каким-либо набором одиночных битов, оно может быть свободно сгенерировано набором битовых строк { "0", "11", "101", "1001", "10001", ... } – набор струн вида «10 ^н 1» для некоторого неотрицательного целого числа n (вместе со строкой «0»).

Коды

Набор свободных образующих свободного моноида P называется базисом для P : набор слов C является кодом , если C * — свободный моноид и C — базис. Набор X слов из A ^∗ является префиксом или имеет свойство prefix , если он не содержит правильного (строкового) префикса ни для одного из своих элементов. Каждый префикс в A ⁺ это код, точнее, префиксный код .

Субмоноид N из A ^∗ является унитарным справа, x , xy в N влечет за собой y в N. если Субмоноид порождается префиксом тогда и только тогда, когда он унитарен справа.

Факторизация

Основная статья: Факторизация моноида

Факторизация свободного моноида — это последовательность подмножеств слов, обладающая тем свойством, что каждое слово в свободном моноиде может быть записано как конкатенация элементов, взятых из подмножеств. Теорема Чена-Фокса-Линдона утверждает, что слова Линдона обеспечивают факторизацию. В более общем смысле слова Холла обеспечивают факторизацию; слова Линдона представляют собой особый случай слов Холла.

Свободный корпус

Пересечение свободных подмоноидов свободного моноида A ^∗ снова бесплатно. Если S — подмножество свободного моноида A *, то пересечение всех свободных подмоноидов A *, содержащих S, корректно определено, поскольку A * само по себе свободно и содержит S ; это свободный моноид, оболочкой S. свободной называемый Основой этого пересечения является код.

Теорема о дефектах утверждает, что если X конечно и C является базой свободной оболочки X , то либо X является кодом и C = X , либо

| С | ≤ | Х | − 1 .

Морфизмы

Морфизм моноида f из свободного моноида B ^∗ в моноид M — это отображение такое, что f ( xy ) = f ( x )⋅ f ( y ) для слов x , y и f (ε) = ι, где ε и ι обозначают единичные элементы B ^∗ и М соответственно. Морфизм f определяется его значениями на буквах B , и наоборот, любое отображение из B в M расширяется до морфизма. Морфизм не стирается или непрерывный если ни одна буква B не отображается в ι, и тривиально, если каждая буква B отображается в ι.

Морфизм f свободного моноида B ^∗ к свободному моноиду A ^∗ является тотальным , если каждая буква A встречается в каком-либо слове по образу f ; циклический или периодический если образ f содержится в { w } ^∗ для некоторого слова w из A ^∗ . Морфизм f является k -равномерным, если длина | ж ( а )| является постоянным и равным k для всех a в A . 1-однородный морфизм строго алфавитный. или кодировка .

Морфизм f свободного моноида B ^∗ к свободному моноиду A ^∗ является упрощенным, если существует алфавит C мощности меньше, чем у B, такой морфизм f , проходящий через C ^∗ , т. е. является композицией морфизма из B ^∗ до С ^∗ и морфизм от него к A ^∗ ; в противном f элементарна случае . Морфизм f называется кодом , если образ алфавита B под действием f является кодом. Каждый элементарный морфизм является кодом.

Тестовые наборы

Для L подмножество B ^∗ конечное подмножество T в L является тестовым множеством для L, если морфизмы f и g на B ^∗ договорятся о L тогда и только тогда, когда они договорятся о T . Гипотеза Эренфойхта состоит в том, что любое подмножество L имеет тестовый набор: это было доказано независимо Альбертом и Лоуренсом; Макнотон; и Губа. Доказательства опираются на базисную теорему Гильберта .

Карта и сложить

Вычислительным воплощением морфизма моноида является карта , за которой следует складка . В этом случае свободный моноид на множестве A соответствует спискам элементов из A с конкатенацией в качестве бинарной операции. Гомоморфизм моноида свободного моноида в любой другой моноид ( M ,•) — это функция f такая, что

• ж ( Икс ₁ ... Икс _п ) знак равно ж ( Икс ₁ ) • ... • ж ( Икс _п )
• е () = е

где e тождество на M. — В вычислительном отношении каждый такой гомоморфизм соответствует операции отображения , применяющей f ко всем элементам списка, за которой следует операция свертывания , которая объединяет результаты с помощью бинарного оператора •. Эта вычислительная парадигма (которая может быть обобщена на неассоциативные бинарные операторы) легла в основу программной среды MapReduce .

Эндоморфизмы

Эндоморфизм ​ A ​ ^∗ является морфизмом из A ^∗ самому себе. Тождественное отображение I является эндоморфизмом A ^∗ , а эндоморфизмы образуют моноид относительно композиции функций .

Эндоморфизм f является продолжаемым , если существует буква a такая, что f ( a ) = как для непустой строки s .

Струнная проекция

Операция проекции струны является эндоморфизмом. То есть, учитывая букву a ∈ Σ и строку s ∈ Σ ^∗ строковая проекция pa _s ( из удаляет каждое вхождение a ; s ) формально определяется

$p_{a}(s)={\begin{cases}\varepsilon &{\text{if }}s=\varepsilon ,{\text{ the empty string}}\\p_{a}(t)&{\text{if }}s=ta\\p_{a}(t)b&{\text{if }}s=tb{\text{ and }}b\neq a.\end{cases}}$

Обратите внимание, что проекция строки четко определена, даже если ранг моноида бесконечен, поскольку приведенное выше рекурсивное определение работает для всех строк конечной длины. Струнная проекция — это морфизм в категории свободных моноидов, так что

$p_{a}\left(\Sigma ^{*}\right)=\left(\Sigma -a\right)^{*}$

где $p_{a}\left(\Sigma ^{*}\right)$ понимается свободный моноид всех конечных строк, не содержащих букву a . Проекция коммутирует с операцией конкатенации строк, так что $p_{a}(st)=p_{a}(s)p_{a}(t)$ для всех строк s и t . Существует много правых обратных проекций строк, поэтому это расщепляемый эпиморфизм .

Тождественный морфизм $p_{\varepsilon },$ определяется как $p_{\varepsilon }(s)=s$ для всех строк s и $p_{\varepsilon }(\varepsilon )=\varepsilon$.

Проекция струн коммутативна, что очевидно.

$p_{a}(p_{b}(s))=p_{b}(p_{a}(s)).$

Для свободных моноидов конечного ранга это следует из того, что свободные моноиды одного и того же ранга изоморфны, поскольку проекция снижает ранг моноида на единицу.

Проекция струн идемпотентна , так как

$p_{a}(p_{a}(s))=p_{a}(s)$

для всех строк s . Таким образом, проекция является идемпотентной коммутативной операцией и поэтому образует ограниченную полурешетку или коммутативную полосу .

Свободный коммутативный моноид

Для данного набора A свободный . коммутативный моноид на A — это набор всех конечных мультимножеств с элементами, взятыми из A , причем операция моноида представляет собой сумму мультимножеств, а единица моноида — пустое мультимножество

Например, если A = { a , b , c }, элементы свободного коммутативного моноида на A имеют вид

{е, а , аб , а ² б , аб ³ с ⁴ , ...}.

Основная теорема арифметики утверждает, что моноид натуральных чисел при умножении является свободным коммутативным моноидом на бесконечном наборе образующих простых чисел .

Свободная коммутативная полугруппа — это подмножество свободного коммутативного моноида, которое содержит все мультимножества с элементами, взятыми из A, кроме пустого мультимножества.

Свободный частично коммутативный моноид , или моноид следа , — это обобщение, которое охватывает как свободные, так и свободные коммутативные моноиды в качестве примеров. Это обобщение находит применение в комбинаторике и при изучении параллелизма в информатике .

См. также

• Строковые операции

Ссылки

• Аллуш, Жан-Поль; Шалит, Джеффри (2003), Автоматические последовательности: теория, приложения, обобщения , издательство Кембриджского университета , ISBN  978-0-521-82332-6 , Збл   1086.11015
• Берстель, Жан ; Перрен, Доминик ; Ройтенауэр, Кристоф (2010), Коды и автоматы , Энциклопедия математики и ее приложений, том. 129, Кембридж: Издательство Кембриджского университета , ISBN  978-0-521-88831-8 , Збл   1187.94001
• Лотер, М. (1997), Комбинаторика слов , Кембриджская математическая библиотека, том. стр. 17. Авторы: Перрен, Д.; Ройтенауэр, К.; Берстель, Дж.; Пин, Дж. Э.; Пирилло, Г.; Фоата, Д.; Сакарович Дж.; Саймон, И.; Шютценбергер, член парламента; Шоффрут, К.; Кори, Р. Редакторы серии: Линдон, Роджер; Рота, Джан-Карло. Предисловие Роджера Линдона (2-е изд.), Cambridge University Press , doi : 10.1017/CBO9780511566097 , ISBN  0-521-59924-5 , МР   1475463 , Збл   0874.20040
• Лотер, М. (2011), Алгебраическая комбинаторика слов , Энциклопедия математики и ее приложений, том. 90, с предисловием Жана Берстеля и Доминика Перрена (перепечатка издания в твердом переплете 2002 г.), Cambridge University Press , ISBN  978-0-521-18071-9 , Збл   1221,68183
• Лотер, М. (2005), Прикладная комбинаторика слов , Энциклопедия математики и ее приложений, том. 105, Коллективная работа Жана Берстеля, Доминика Перрена, Максима Крошмора, Эрика Ляпорта, Мехрияра Мори, Нади Пизанти, Мари-Франс Саго, Жезины Рейнерт , Софи Шбат , Михаэля Уотермана, Филиппа Жаке, Войцеха Шпанковского , Доминика Пулалона, Жиля Шеффера, Роман Колпаков, Григорий Кучеров, Жан-Поль Аллуш и Валери Берте , Кембридж: Cambridge University Press , ISBN  0-521-84802-4 , Збл   1133.68067
• Пифей Фогг, Н. (2002), Берте, Валери ; Ференци, Себастьен; Модуит, Кристиан; Сигел, А. (ред.), Замены в динамике, арифметике и комбинаторике , Конспекты лекций по математике, том. 1794, Берлин: Springer-Verlag , ISBN.  3-540-44141-7 , Збл   1014.11015
• Сакарович, Жак (2009), Элементы теории автоматов , Перевод с французского Рубена Томаса, Кембридж: Cambridge University Press , ISBN  978-0-521-84425-3 , Збл   1188,68177
• Саломаа, Арто (1981), Драгоценности теории формального языка , Pitman Publishing, ISBN  0-273-08522-0 , Збл   0487.68064

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

• СМИ, связанные со свободным моноидом, на Викискладе?