Рациональный набор - Rational set

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

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

Определение

Позволять ${\displaystyle (N,\cdot )}$ быть моноид с элементом идентичности ${\displaystyle e}$. Набор ${\displaystyle \mathrm {RAT} (N)}$ рациональных подмножеств ${\displaystyle N}$ это наименьшее множество, которое содержит каждое конечное множество и замкнуто относительно

• союз: если ${\displaystyle A,B\in \mathrm {RAT} (N)}$ тогда ${\displaystyle A\cup B\in \mathrm {RAT} (N)}$
• продукт: если ${\displaystyle A,B\in \mathrm {RAT} (N)}$ тогда ${\displaystyle A\cdot B=\{a\cdot b\mid a\in A,b\in B\}\in \mathrm {RAT} (N)}$
• Клини звезда если ${\displaystyle A\in \mathrm {RAT} (N)}$ тогда ${\displaystyle A^{*}=\bigcup _{i=0}^{\infty }A^{i}\in \mathrm {RAT} (N)}$ куда ${\displaystyle A^{0}=\{e\}}$ - синглтон, содержащий элемент идентичности, и где ${\displaystyle A^{n+1}=A^{n}\times A}$.

Это означает, что любое рациональное подмножество ${\displaystyle N}$ можно получить, взяв конечное число конечных подмножеств ${\displaystyle N}$ и применяя операции объединения, произведения и звезды Клини конечное число раз.

В общем случае рациональное подмножество моноида не является подмоноидом.

Пример

Позволять ${\displaystyle A}$ быть алфавит, набор ${\displaystyle A^{*}}$ слов над ${\displaystyle A}$ моноид. Рациональное подмножество ${\displaystyle A^{*}}$ точно обычные языки. Действительно, регулярные языки могут быть определены конечным регулярное выражение.

Рациональные подмножества ${\displaystyle \mathbb {N} }$ - в конечном итоге периодические наборы целых чисел. В более общем смысле, рациональные подмножества ${\displaystyle \mathbb {N} ^{k}}$ являются полулинейные множества.^[1]

Характеристики

Теорема Макнайта заявляет, что если ${\displaystyle N}$ конечно порожден, то его узнаваемое подмножество являются рациональными множествами. В общем случае это неверно, так как все ${\displaystyle N}$ всегда узнаваем, но не рационально, если ${\displaystyle N}$ бесконечно порожден.

Рациональные множества замкнуты относительно морфизма: дано ${\displaystyle N}$ и ${\displaystyle M}$ два моноида и ${\displaystyle \phi :N\rightarrow M}$ морфизм, если ${\displaystyle S\in \mathrm {RAT} (N)}$ тогда ${\displaystyle \phi (S)=\{\phi (x)\mid x\in S\}\in \mathrm {RAT} (M)}$.

${\displaystyle \mathrm {RAT} (N)}$ не закрывается под дополнять как показано в следующем примере.^[2] Позволять ${\displaystyle N=\{a\}^{*}\times \{b,c\}^{*}}$, наборы ${\displaystyle R=(a,b)^{*}(1,c)^{*}=\{(a^{n},b^{n}c^{m})\mid n,m\in \mathbb {N} \}}$ и ${\displaystyle S=(1,b)^{*}(a,c)^{*}=\{(a^{n},b^{m}c^{n})\mid n,m\in \mathbb {N} \}}$ рациональны, но ${\displaystyle R\cap S=\{(a^{n},b^{n}c^{n})\mid n\in \mathbb {N} \}}$ не потому, что его проекция на второй элемент ${\displaystyle \{b^{n}c^{n}\mid n\in \mathbb {N} \}}$ не рационально.

Пересечение рационального подмножества и узнаваемого подмножества рационально.

Для конечных групп хорошо известен следующий результат А. Анисимова и А. В. Зейферта: подгруппа ЧАС из конечно порожденная группа грамм узнаваема тогда и только тогда, когда ЧАС имеет конечный индекс в грамм. В отличие, ЧАС рационально тогда и только тогда, когда ЧАС конечно порожден.^[3]

Рациональные отношения и рациональные функции

А бинарное отношение между моноидами M и N это рациональное отношение если график отношения, рассматриваемый как подмножество M×N - рациональное множество в моноиде произведений. Функция от M к N это рациональная функция если график функции - рациональное множество.^[4]

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

• Рациональная серия
• Узнаваемый набор
• Рациональный моноид

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

• Дикерт, Фолькер; Куфлейтнер, Манфред; Розенберг, Герхард; Хертрампф, Ульрих (2016). «Глава 7: Автоматы». Дискретные алгебраические методы. Берлин / Бостон: Walter de Gruyther GmbH. ISBN  978-3-11-041332-8.
• Жан-Эрик Пин, Математические основы теории автоматов, Глава IV: Узнаваемые и рациональные множества
• Сэмюэл Эйленберг и М. П. Шютценбергер, Рациональные множества в коммутативных моноидах, Журнал алгебры, 1969.

1. Математические основы теории автоматов
2. ср. Жан-Эрик Пин, Математические основы теории автоматов, п. 76, Пример 1.3
3. Джон Микин (2007). «Группы и полугруппы: связи и противопоставления». В C.M. Кэмпбелл; М.Р. Квик; Э. Ф. Робертсон; G.C. Смит (ред.). Группы Сент-Эндрюс 2005 Том 2. Издательство Кембриджского университета. п. 376. ISBN  978-0-521-69470-4. препринт
4. Хоффманн, Майкл; Куске, Дитрих; Отто, Фридрих; Томас, Ричард М. (2002). «Некоторые родственники автоматических и гиперболических групп». В Гомесе, Грасинда М. С. (ред.). Полугруппы, алгоритмы, автоматы и языки. Материалы семинаров, проведенных в Международном центре математики, CIM, Коимбра, Португалия, май, июнь и июль 2001 г.. Сингапур: World Scientific. С. 379–406. Zbl  1031.20047.

дальнейшее чтение

• Сакарович, Жак (2009). Элементы теории автоматов. Перевод с французского Рувима Томаса. Кембридж: Издательство Кембриджского университета. Часть II: Сила алгебры. ISBN  978-0-521-84425-3. Zbl  1188.68177.