Jump to content

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

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

Определение [ править ]

Рассмотрим моноид 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]

Свойства [ править ]

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

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

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

Ссылки [ править ]

  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 .
Arc.Ask3.Ru: конец переведенного документа.
Arc.Ask3.Ru
Номер скриншота №: c7d482bcc3b6fc5b8b2b8f7bc37c34eb__1639021080
URL1:https://arc.ask3.ru/arc/aa/c7/eb/c7d482bcc3b6fc5b8b2b8f7bc37c34eb.html
Заголовок, (Title) документа по адресу, URL1:
Rational monoid - Wikipedia
Данный printscreen веб страницы (снимок веб страницы, скриншот веб страницы), визуально-программная копия документа расположенного по адресу URL1 и сохраненная в файл, имеет: квалифицированную, усовершенствованную (подтверждены: метки времени, валидность сертификата), открепленную ЭЦП (приложена к данному файлу), что может быть использовано для подтверждения содержания и факта существования документа в этот момент времени. Права на данный скриншот принадлежат администрации Ask3.ru, использование в качестве доказательства только с письменного разрешения правообладателя скриншота. Администрация Ask3.ru не несет ответственности за информацию размещенную на данном скриншоте. Права на прочие зарегистрированные элементы любого права, изображенные на снимках принадлежат их владельцам. Качество перевода предоставляется как есть. Любые претензии, иски не могут быть предъявлены. Если вы не согласны с любым пунктом перечисленным выше, вы не можете использовать данный сайт и информация размещенную на нем (сайте/странице), немедленно покиньте данный сайт. В случае нарушения любого пункта перечисленного выше, штраф 55! (Пятьдесят пять факториал, Денежную единицу (имеющую самостоятельную стоимость) можете выбрать самостоятельно, выплаичвается товарами в течение 7 дней с момента нарушения.)