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

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

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

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

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

Примеры

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

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

Клини звезда

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

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

{ε, а, ab, ба, caa, cccbabbc, ...}.

Если А любой набор, длина слова функционировать на А^∗ уникальный моноидный гомоморфизм из А^∗ к (N₀, +), который отображает каждый элемент А к 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"

Определим пару слов в А^∗ формы УФ и ву в качестве сопрягать: конъюгаты слова, таким образом, являются его круговые смены.^[7] В этом смысле два слова являются сопряженными, если они сопряжены в смысле теории групп как элементы свободная группа создано А.^[8]

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

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

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

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

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

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

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

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

Коды

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

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

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

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

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

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

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

В теорема о дефекте^[15][16][17] заявляет, что если Икс конечно и C лежит в основе свободной оболочки Икс, то либо Икс это код и C = Икс, или же

|C| ≤ |Икс| − 1 .

Морфизмы

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

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

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

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

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

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

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

• ж(Икс₁...Икс_п) = ж(Икс₁) • ... • ж(Икс_п)
• ж() = е

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

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

An эндоморфизм из А^∗ это морфизм из А^∗ себе.^[29] В карта идентичности я является эндоморфизмом А^∗, а эндоморфизмы образуют моноид под состав функций.

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

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

Работа струнная проекция это эндоморфизм. То есть дано письмо а ∈ Σ и строка s ∈ Σ^∗, проекция струны п_а(s) удаляет все вхождения а из 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)^{*}}$

куда ${\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}$ для всех струн 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. Таким образом, проекция - это идемпотентная коммутативная операция, поэтому она образует ограниченную полурешетка или коммутативный группа.

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

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

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

{ε, а, ab, а²б, ab³c⁴, ...}.

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

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

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

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

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

Примечания

1. Лотар (1997), стр. 2–3), [1]
2. Пифей Фогг (2002), п. 2)
3. Лотар (1997), п. 5)
4. Поскольку сложение натуральных чисел является ассоциативным, результат не зависит от порядка вычисления, что обеспечивает точное определение отображения.
5. Сакарович (2009) с.382
6. Боровик, Александр (01.01.2005). Группы, языки, алгоритмы: совместная специальная сессия AMS-ASL по взаимодействию между логикой, теорией групп и компьютерными науками, 16-19 января 2003 г., Балтимор, Мэриленд. American Mathematical Soc. ISBN  9780821836187.
7. Сакарович (2009) стр.27
8. Пифей Фогг (2002), п. 297)
9. Сакарович (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. Сакарович (2009 г., п. 25)
20. Лотар (1997), п. 164)
21. Саломаа (1981) с.77
22. Лотар (2005), п. 522)
23. Берстель, Жан; Ройтенауэр, Кристоф (2011). Некоммутативные рациональные ряды с приложениями. Энциклопедия математики и ее приложений. 137. Кембридж: Издательство Кембриджского университета. п. 103. ISBN  978-0-521-19022-0. Zbl  1250.68007.
24. Аллуш и Шаллит (2003), п. 9)
25. Саломаа (1981) стр.72
26. Лотар (1997), стр. 178–179).
27. Lothaire (2011 г.), п. 451)
28. Саломаа, А. (Октябрь 1985 г.). «Гипотеза Эренфойхта: доказательство для теоретиков языка». Бюллетень EATCS (27): 71–82.
29. Lothaire (2011 г.), п. 450)
30. Аллуш и Шаллит (2003) стр.10

Рекомендации

• Аллуш, Жан-Поль; Шаллит, Джеффри (2003), Автоматические последовательности: теория, приложения, обобщения, Издательство Кембриджского университета, ISBN  978-0-521-82332-6, Zbl  1086.11015
• Берстель, Жан; Перрен, Доминик; Ройтенауэр, Кристоф (2010), Коды и автоматы, Энциклопедия математики и ее приложений, 129, Кембридж: Издательство Кембриджского университета, ISBN  978-0-521-88831-8, Zbl  1187.94001
• Лотэр, М. (1997), Комбинаторика слов, Кембриджская математическая библиотека, 17, Авторы: Perrin, D .; Reutenauer, C .; Berstel, J .; Pin, J. E .; Pirillo, G .; Foata, D .; Sakarovitch, J .; Саймон, I .; Schützenberger, M. P .; Choffrut, C .; Кори, Р. Редакторы серии: Линдон, Роджер; Рота, Джан-Карло. Предисловие Роджера Линдона (2-е изд.), Издательство Кембриджского университета, Дои:10.1017 / CBO9780511566097, ISBN  0-521-59924-5, МИСТЕР  1475463, Zbl  0874.20040
• Лотэр, М. (2011), Алгебраическая комбинаторика слов, Энциклопедия математики и ее приложений, 90, С предисловием Жана Берштеля и Доминика Перрена (Перепечатка издания 2002 года в твердом переплете), Издательство Кембриджского университета, ISBN  978-0-521-18071-9, Zbl  1221.68183
• Лотэр, М. (2005), Прикладная комбинаторика слов, Энциклопедия математики и ее приложений, 105, Коллективная работа Жана Берштеля, Доминика Перрена, Максима Крошмора, Эрика Ляпорта, Мериара Мори, Нади Пизанти, Мари-Франс Саго, Гезин Райнерт, Софи Шбат, Майкл Уотерман, Филипп Жаке, Войцех Шпанковски, Доминик Пулалон, Жиль Шеффер, Роман Колпаков, Грегори Кушеров, Жан-Поль Аллуш и Валери Берте, Кембридж: Издательство Кембриджского университета, ISBN  0-521-84802-4, Zbl  1133.68067
• Пифей Фогг, Н. (2002), Берте, Валери; Ференци, Себастьен; Mauduit, Christian; Сигель, А. (ред.), Подстановки в динамике, арифметике и комбинаторике, Конспект лекций по математике, 1794, Берлин: Springer-Verlag, ISBN  3-540-44141-7, Zbl  1014.11015
• Сакарович, Жак (2009), Элементы теории автоматов, Перевод с французского Рубена Томаса, Кембридж: Издательство Кембриджского университета, ISBN  978-0-521-84425-3, Zbl  1188.68177
• Саломаа, Арто (1981), Драгоценности теории формального языка, Pitman Publishing, ISBN  0-273-08522-0, Zbl  0487.68064

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

• СМИ, связанные с Бесплатный моноид в Wikimedia Commons