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

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

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

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

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

Примеры

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

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

Клини звезда

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

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

{ε, , абы , ба , CAA , cccbabbc , ...}.

Если A - любое множество, функция длины слова на A ∗ является единственным гомоморфизмом моноида из A ∗ в ( N 0 , +), который отображает каждый элемент A в 1. Таким образом, свободный моноид является градуированным моноидом . (Градуированный моноид - это моноид, который может быть записан как . Каждый - это степень; градация здесь - это просто длина строки. То есть, содержит эти строки длины. Здесь символ может означать «объединение множества»; он используется вместо символа, потому что, как правило, объединения множеств могут не быть моноидами, и поэтому используется отдельный символ. По соглашению градации всегда записываются с помощью символа.)

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

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

Спряжение слов

Пример 1-го случая равноделимости: 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 . Этот результат также известен как лемма Леви .

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

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

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

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

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

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

Коды

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

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

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

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

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

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

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

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

| C | ≤ | X | - 1.

Морфизмы

Моноид морфизм F из свободного моноидного B * к моноиду М является отображением таким , что F ( х ) = е ( х ) ⋅ F ( у ) для слов х , у и F (ε) = t, где ε и р о обозначает единицу B ∗ и M соответственно. Морфизм f определяется своими значениями на буквах B и, наоборот, любое отображение из B в M продолжается до морфизма. Морфизм не стирает или непрерывен, если никакая буква B не отображается в ι, и тривиален, если каждая буква B отображается в ι.

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

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

Наборы тестов

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

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

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

  • f ( x 1 ... x n ) = f ( x 1 ) • ... • f ( x n )
  • f () = e

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

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

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

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

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

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

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

где понимается свободный моноид всех конечных строк, не содержащих буквы а . Проекция коммутирует с операцией конкатенации строк, так что для всех строк s и t . У струнной проекции много правых инверсий, и поэтому это расщепленный эпиморфизм .

Морфизм идентичности определяется как для всех строк s , и .

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

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

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

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

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

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

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

{ε, a , ab , a 2 b , ab 3 c 4 , ...}.

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

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

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

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

Заметки

Ссылки

внешняя ссылка