Дополнение автоматов

В теоретической информатике и формального языка дополнение автомата теории ^{[ объяснить ]} — это задача вычисления автомата, который принимает именно те слова, которые отвергает другой автомат. Формально, имея автомат A , который распознает регулярный язык L , мы хотим вычислить автомат, который точно распознает слова, которых нет в L , т. е дополнение к L. .

Изучаются несколько вопросов по операции дополнения, такие как:

Его вычислительная сложность : какова сложность вычисления автомата для дополнительного языка с учетом автомата?
Сложность его состояний : каково наименьшее число состояний автомата, распознающего дополнение?

С детерминированными конечными автоматами

С недетерминированными конечными автоматами

В случае недетерминированного конечного автомата сложность состояния дополняющего автомата может быть экспоненциальной. ^[1] Нижние оценки известны и в случае однозначных автоматов . ^[2]

С двусторонними автоматами

Дополнение также изучалось для двусторонних автоматов . ^[3]

С автоматами Бюхи

См. также

Государственная сложность

Ссылки

^ Бирже, Жан-Камиль (1993). «Частичный порядок слов, минимальные элементы обычных языков и сложность состояний». Теоретическая информатика . 119 (2): 267–291. дои : 10.1016/0304-3975(93)90160-У . ISSN 0304-3975 .
^ Гёос, Мика; Кифер, Стефан; Юань, Вэйцян (12 февраля 2022 г.). «Нижние границы однозначных автоматов через сложность связи». arXiv : 2109.09155 [ cs.FL ].
^ Гефферт, Вильям; Мерегетти, Карло; Пигиццини, Джованни (1 августа 2007 г.). «Дополняющие двусторонние конечные автоматы» . Информация и вычисления . 205 (8): 1173–1187. дои : 10.1016/j.ic.2007.01.008 . ISSN 0890-5401 .

[Birget1993b-1] Бирже, Жан-Камиль (1993). «Частичный порядок слов, минимальные элементы обычных языков и сложность состояний». Теоретическая информатика . 119 (2): 267–291. дои : 10.1016/0304-3975(93)90160-У . ISSN 0304-3975 .

[GoosKieferYuan2022-2] Гёос, Мика; Кифер, Стефан; Юань, Вэйцян (12 февраля 2022 г.). «Нижние границы однозначных автоматов через сложность связи». arXiv : 2109.09155 [ cs.FL ].

[3] Гефферт, Вильям; Мерегетти, Карло; Пигиццини, Джованни (1 августа 2007 г.). «Дополняющие двусторонние конечные автоматы» . Информация и вычисления . 205 (8): 1173–1187. дои : 10.1016/j.ic.2007.01.008 . ISSN 0890-5401 .

[1]

[2]

[3]