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

В абстрактной алгебре , то свободный моноид на множестве является моноид , элементы которого являются всеми конечными последовательностями (или строка) из нуля или более элементов из этого набора, при конкатенации строк в качестве моноидной операции и с уникальной последовательностью нулевых элементов, часто называется пустой строкой и обозначается через ε или λ как единичный элемент . Свободный моноид на множестве 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 .

Kleene star [ править ]

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

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

{ε, , абы , ба , 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]

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

Спряжение слов [ править ]

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

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

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

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

Бесплатные генераторы и ранг [ править ]

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

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

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

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

Коды [ править ]

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

Подмоноида N из А ^* является право унитарным , если х , х в N означает у в N . Субмоноид порождается префиксом тогда и только тогда, когда он унитарен справа. ^[14]

Факторизация [ править ]

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

Свободный корпус [ править ]

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

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

| C | ≤ | X | - 1.

Морфизмы [ править ]

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

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

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

Наборы тестов [ править ]

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

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

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

• f ( x ₁ ... x _n ) = f ( x ₁ ) • ... • f ( x _n )
• f () = e

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

Эндоморфизмы [ править ]

Эндоморфизм из А ^* морфизм из А ^* к себе. ^[29] тождественное отображение Я являюсь эндоморфизмом А ^* , а эндоморфизмы образуют моноид по составу функций .

Эндоморфизм 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)^{*}}$

где понимается свободный моноид всех конечных строк, не содержащих буквы а . Проекция коммутирует с операцией конкатенации строк, так что для всех строк 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 , b , c }, элементы свободного коммутативного моноида на A имеют вид

{ε, a , ab , a ² b , ab ³ c ⁴ , ...}.

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

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

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

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

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

Заметки [ править ]

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

• Аллуш, Жан-Поль; Шаллит, Джеффри (2003), Автоматические последовательности: теория, приложения, обобщения , Cambridge University Press , ISBN 978-0-521-82332-6, Zbl  1086,11015
• Берстель, Жан ; Перрен, Доминик ; Reutenauer, Christophe (2010), Коды и автоматы , Энциклопедия математики и ее приложений, 129 , Кембридж: Cambridge University Press , ISBN 978-0-521-88831-8, Zbl  1187,94001
• Lothaire, M. (1997), Комбинаторика слов , Кембриджская математическая библиотека, 17 , авторы: Perrin, D .; Reutenauer, C .; Berstel, J .; Пин, JE; Pirillo, G .; Foata, D .; Сакарович, Дж .; Саймон, I .; Шютценбергер, депутат; Choffrut, C .; Кори, Р. Редакторы серии: Линдон, Роджер; Рота, Джан-Карло. Предисловие Роджера Линдона (2-е изд.), Cambridge University Press , doi : 10.1017 / CBO9780511566097 , ISBN 0-521-59924-5, MR  1475463 , Zbl  0874.20040 CS1 maint: discouraged parameter (link)
• Лотар, М. (2011), Алгебраическая комбинаторика слов , Энциклопедия математики и ее приложений, 90 , с предисловием Жана Берштеля и Доминика Перрена (Перепечатка издания в твердом переплете 2002 г.), Cambridge University Press , ISBN 978-0-521-18071-9, Zbl  1221,68183 CS1 maint: discouraged parameter (link)
• Lothaire, M. (2005), Прикладная комбинаторика на словах , энциклопедии математики и ее приложения 105 , коллективная работа Жана Berstel, Доминик Перрен, Максим Крошемор, Эрик Лапорта, Меряр Мори, Надя Pisanti, Мари-Франс Sagot, Гезине Райнерт , Софи Шбат , Майкл Уотерман, Филипп Жаке, Войцех Шпанковски , Доминик Пулалхон, Жиль Шеффер, Роман Колпаков, Грегори Кушеров, Жан-Поль Аллуш и Валери Берте , Кембридж: Cambridge University Press , ISBN 0-521-84802-4, Zbl  1133,68067 CS1 maint: discouraged parameter (link)
• Питеас Фогг, Н. (2002), Берте, Валери ; Ференци, Себастьен; Mauduit, Christian; Зигель А. (ред.), Замены в динамике, арифметике и комбинаторике , Лекционные заметки по математике, 1794 , Берлин: Springer-Verlag , ISBN 3-540-44141-7, Zbl  1014,11015
• Сакарович, Жак (2009), Элементы теории автоматов , Перевод с французского Рубена Томаса, Кембридж: Cambridge University Press , ISBN 978-0-521-84425-3, Zbl  1188,68177
• Саломаа, Арто (1981), драгоценности теории формального языка , издательство Pitman Publishing, ISBN 0-273-08522-0, Zbl  0487,68064 CS1 maint: discouraged parameter (link)

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

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