Рациональный моноид

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

Определение

Рассмотрим моноид M . Рассмотрим пару ( A , L ), где A — конечное подмножество M , порождающее M как моноид, а L — язык на A (то есть подмножество множества всех строк A ^∗). Пусть φ — отображение свободного моноида A ^∗ к M, путем оценки строки как произведения в M. заданному Мы говорим, что L является рациональным сечением если φ индуцирует биекцию между L и M. , Мы говорим, что ( A , L ) является рациональной структурой для M, если, кроме того, , рассматриваемое ядро φ как подмножество моноида произведения A ^∗× A ^∗ является рациональным множеством .

Квазирациональный моноид — это тот, для которого L является рациональным отношением : рациональный моноид это тот, для которого также существует рациональное функциональное сечение L. — Поскольку L является подмножеством свободного моноида, теорема Клини верна, и рациональная функция - это всего лишь такая функция, экземпляр которой может быть реализован преобразователем конечного состояния.

Примеры

Конечный моноид рационален.
Группа является рациональным моноидом тогда и только тогда , когда она конечна.
Конечно порожденный свободный моноид рационален.
Моноид M4, порожденный набором {0, e , a , b , x , y } с учетом отношений, в которых e является единицей, 0 является поглощающим элементом , каждый из a и b коммутирует с каждым из x , y и ax. = bx , ay = by = bby , xx = xy = yx = yy = 0 является рациональным, но не автоматическим.
Моноид Фибоначчи , фактор свободного моноида по двум образующим { a , b } ^∗ сравнением aab = bba .

Отношения Грина

для Соотношения Грина рационального моноида удовлетворяют D = J . ^{[ 1 ]}

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

Теорема Клини справедлива для рациональных моноидов: то есть подмножество является распознаваемым множеством тогда и только тогда, когда оно является рациональным множеством.

Рациональный моноид не обязательно является автоматическим , и наоборот. Однако рациональный моноид является асинхронно автоматическим и гиперболическим .

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

Ссылки

^ Сакарович (1987)

Фихтнер, Ина; Матиссен, Кристиан (2002). «Рациональные преобразования и теорема Клини для степенных рядов по рациональным моноидам». В Гомесе, Грасинда М.С. (ред.). Полугруппы, алгоритмы, автоматы и языки. Материалы семинаров, проведенных в Международном центре математики CIM, Коимбра, Португалия, май, июнь и июль 2001 г. Сингапур: World Scientific. стр. 94–111. Збл 1350.68191 .
Хоффманн, Майкл; Куске, Дитрих; Отто, Фридрих; Томас, Ричард М. (2002). «Некоторые родственники автоматических и гиперболических групп». В Гомесе, Грасинда М.С. (ред.). Полугруппы, алгоритмы, автоматы и языки. Материалы семинаров, проведенных в Международном центре математики CIM, Коимбра, Португалия, май, июнь и июль 2001 г. Сингапур: World Scientific. стр. 379–406. Збл 1031.20047 .
Куич, Вернер (2011). «Алгебраические системы и автоматы с понижением». В Куиче, Вернер (ред.). Алгебраические основы информатики. Очерки, посвященные Симеону Бозапалидису по случаю его выхода на пенсию . Конспекты лекций по информатике. Том. 7020. Берлин: Springer-Verlag . стр. 228–256. ISBN 978-3-642-24896-2 . Збл 1251.68135 .
Пеллетье, Мариз (1990). «Булевое замыкание и однозначность рациональных множеств». В Патерсоне, Майкл С. (ред.). Автоматы, языки и программирование, Учеб. 17-й Международный. Коллоквиум, Уорик/Великобритания, 1990 . Конспекты лекций по информатике. Том. 443. стр. 512–525. Збл 0765.68075 .
Сакарович, Жак (сентябрь 1987 г.). «Простые умножения I. Область теоремы Клини» . Информация и вычисления . 74 (3): 173–197. дои : 10.1016/0890-5401(87)90020-4 . Збл 0642.20043 .

[Sak87-1] Сакарович (1987)

[ 1 ]