Рациональный набор - Википедия - Rational set

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

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

Определение

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

союз: если ${ displaystyle A, B in mathrm {RAT} (N)}$ тогда ${ Displaystyle A чашка 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 А ^ {0} = {е }}$ - синглтон, содержащий элемент идентичности, и где ${ Displaystyle А ^ {п + 1} = А ^ {п} раз А}$ .

Это означает, что любое рациональное подмножество ${ 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 в mathbb {N} }}$ и ${ Displaystyle S = (1, b) ^ {*} (a, c) ^ {*} = {(a ^ {n}, b ^ {m} c ^ {n}) mid n, m в 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]

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

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

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

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

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

[Campbell2007-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.

[1]

[2]

[3]

[4]