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

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

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

Определение

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

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

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

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

Пример

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

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

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

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

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

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

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

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

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

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

См. также

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

Ссылки

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

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

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