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

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

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

Определение

Позволять $(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}$ являются полулинейными множествами . ^{[ 1 ]}

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

Теорема Макнайта утверждает, что если $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)$ не закрывается при дополнении , как показано в следующем примере. ^{[ 2 ]} Позволять $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 конечно порождено. ^{[ 3 ]}

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

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

См. также

Ссылки

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

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

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

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

[1] Математические основы теории автоматов

[2] см . Жан-Эрик Пен, Математические основы теории автоматов , с. 76, пример 1.3

[Campbell2007-3] Джон Микин (2007). «Группы и полугруппы: связи и контрасты». В CM Кэмпбелл; мистер Квик; Э. Ф. Робертсон; Г. К. Смит (ред.). Группы Сент-Эндрюс 2005 Том 2 . Издательство Кембриджского университета. п. 376. ИСБН 978-0-521-69470-4 . препринт

[4] Хоффманн, Майкл; Куске, Дитрих; Отто, Фридрих; Томас, Ричард М. (2002). «Некоторые родственники автоматических и гиперболических групп». В Гомесе, Грасинда М.С. (ред.). Полугруппы, алгоритмы, автоматы и языки. Материалы семинаров, проведенных в Международном центре математики CIM, Коимбра, Португалия, май, июнь и июль 2001 г. Сингапур: World Scientific. стр. 379–406. Збл 1031.20047 .

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]