Свободный моноид

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

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

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

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

Примеры

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

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

звезда Клини

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

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

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

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

Существуют глубокие связи между теорией полугрупп и теорией автоматов . Например, каждый формальный язык имеет синтаксический моноид , который распознает этот язык. Для случая регулярного языка этот моноид изоморфен моноиду перехода, связанному с полуавтоматом некоторого детерминированного конечного автомата, который распознает этот язык. Регулярные языки над алфавитом A являются замыканием конечных подмножеств A*, свободным моноидом над A, относительно объединения, произведения и порождения подмоноида. ^[6]

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

Спрягать слова

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

Мы определяем пару слов в A ^∗ вида uv и vu как сопряженные : сопряженные слова, таким образом, являются его циклическими сдвигами . ^[7] Два слова сопряжены в этом смысле, если они сопряжены в смысле теории групп как элементы свободной группы, порожденной A. [ ^8]

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

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

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

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

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

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

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

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

Коды

Набор свободных генераторов для свободного моноида P называется базисом для P : набор слов C является кодом , если C * является свободным моноидом, а C является базисом. ^[3] Набор слов X в A ^∗ является префиксом или имеет свойство префикса , если он не содержит собственного (строкового) префикса любого из своих элементов. Каждый префикс в A ⁺ является кодом, на самом деле префиксным кодом . ^{[3] [13]}

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

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

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

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

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

Теорема о дефекте ^{[15] [16] [17]} утверждает, что если X конечно и C является базисом свободной оболочки X , то либо X является кодом и C = X , либо

| С | ≤ | Х | − 1 .

Морфизмы

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

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

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

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

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

Карта и сложение

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

• f ( x ₁ ... x _n ) = f ( x ₁ ) • ... • f ( x _n )
• ф () = е

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

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

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

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

Проекция струны

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

${\displaystyle 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}}}$

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

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

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

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

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

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

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

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

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

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

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

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

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

^{ ε , а , аб , а2б , аб3с4 ^, ... } ^.

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

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

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

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

• Операции со строками

Примечания

1. Лотар (1997, стр. 2–3), [1]
2. Пифей Фогг (2002, стр. 2)
3. Лотер (1997, стр. 5)
4. Поскольку сложение натуральных чисел ассоциативно, результат не зависит от порядка вычисления, что обеспечивает четкость отображения.
5. Сакарович (2009) стр.382
6. Боровик, Александр (2005-01-01). Группы, языки, алгоритмы: AMS-ASL Совместная специальная сессия по взаимодействию между логикой, теорией групп и компьютерной наукой, 16-19 января 2003 г., Балтимор, Мэриленд. Американское математическое общество. ISBN 9780821836187.
7. Сакарович (2009) стр.27
8. Пифей Фогг (2002, стр. 297)
9. Sakarovitch (2009) стр.26
10. Альдо де Лука; Стефано Варриккио (1999). Конечность и регулярность в полугруппах и формальных языках . Springer Berlin Heidelberg. стр. 2. ISBN 978-3-642-64150-3.
11. Берстель, Перрин и Ройтенауэр (2010, стр. 61)
12. Берстель, Перрин и Ройтенауэр (2010, стр. 62)
13. Берстель, Перрин и Ройтенауэр (2010, стр. 58)
14. Лотер (1997, стр. 15)
15. Лотер (1997, стр. 6)
16. Lothaire (2011, стр. 204)
17. Берстель, Перрин и Ройтенауэр (2010, стр. 66)
18. Лотер (1997, стр. 7)
19. Sakarovitch (2009, стр. 25)
20. Lothaire (1997, стр. 164)
21. Саломаа (1981, стр. 77)
22. Лотер (2005, стр. 522)
23. Берстель, Жан; Ройтенауэр, Кристоф (2011). Некоммутативные рациональные ряды с приложениями . Энциклопедия математики и ее приложений. Т. 137. Кембридж: Cambridge University Press . С. 103. ISBN 978-0-521-19022-0. Збл  1250.68007.
24. Аллуш и Шалит (2003, стр. 9)
25. Саломаа (1981, стр. 72)
26. Лотар (1997, стр. 178–179)
27. Лотер (2011, стр. 451)
28. Саломаа, А. (октябрь 1985 г.). «Гипотеза Эренфойхта: доказательство для теоретиков языка». Бюллетень EATCS (27): 71–82.
29. Лотер (2011, стр. 450)
30. Аллуш и Шалит (2003) стр.10

Ссылки

• Аллуш, Жан-Поль; Шаллит, Джеффри (2003), Автоматические последовательности: теория, приложения, обобщения , Cambridge University Press , ISBN 978-0-521-82332-6, Збл  1086.11015
• Берстель, Жан ; Перрен, Доминик ; Ройтенауэр, Кристоф (2010), Коды и автоматы , Энциклопедия математики и ее приложений, т. 129, Кембридж: Cambridge University Press , ISBN 978-0-521-88831-8, ЗБЛ  1187.94001
• Lothaire, M. (1997), Комбинаторика слов , Cambridge Mathematical Library, т. 17, Соавторы: Perrin, D.; Reutenauer, C.; Berstel, J.; Pin, JE; Pirillo, G.; Foata, D.; Sakarovitch, J.; Simon, I.; Schützenberger, MP; Choffrut, C.; Cori, R. Редакторы серии: Lyndon, Roger; Rota, Gian-Carlo. Предисловие Roger Lyndon (2-е изд.), Cambridge University Press , doi : 10.1017/CBO9780511566097, ISBN 0-521-59924-5, MR  1475463, Zbl  0874.20040
• Лотер, М. (2011), Алгебраическая комбинаторика слов , Энциклопедия математики и ее приложений, т. 90, с предисловием Жана Берстеля и Доминика Перрена (переиздание издания 2002 года в твердом переплете), Cambridge University Press , ISBN 978-0-521-18071-9, ЗБЛ  1221.68183
• Лотер, М. (2005), Прикладная комбинаторика слов , Энциклопедия математики и ее приложений, том. 105, Коллективная работа Жана Берстеля, Доминика Перрена, Максима Крошмора, Эрика Ляпорта, Мехрияра Мори, Нади Пизанти, Мари-Франс Саго, Жезины Рейнерт , Софи Шбат , Михаэля Уотермана, Филиппа Жаке, Войцеха Шпанковского , Доминика Пулалона, Жиля Шеффера, Роман Колпаков, Григорий Кучеров, Жан-Поль Аллуш и Валери Берте , Кембридж: Издательство Кембриджского университета , 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

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

• Медиа, связанные с Free monoid на Wikimedia Commons