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

Сложность состояния - область теоретической информатики. имея дело с размером абстрактных автоматов, например, различные виды конечных автоматов . Классический результат в этой области состоит в том, что имитирующий $n$ -состояние недетерминированный конечный автомат детерминированным конечным автоматом требуется именно $2^{n}$ государства в худшем случае.

Преобразование между вариантами конечных автоматов

Конечные автоматы могут быть детерминированный и недетерминированный , в одну сторону (DFA, NFA) и двусторонний (2ДФА, 2НФА). Другие связанные классы: однозначный (УФА), самопроверка (SVFA) и альтернирующие (AFA) конечные автоматы. Эти автоматы могут быть и двусторонними (2УФА, 2СВФА, 2АФА).

Все эти машины могут принимать именно обычные языки . Однако размеры автоматов разных типов необходимо принять тот же язык (измеряется в количестве их состояний) может быть разным. Для любых двух типов конечных автоматов между компромисс между сложностью состояния ними целочисленная функция $f$ где $f(n)$ – наименьшее число состояний в автоматах второго типа достаточно, чтобы распознавать каждый язык признан $n$ -автомат первого типа. Известны следующие результаты.

NFA в DFA: $2^{n}$ государства. Это конструкция Рабина , и Скотта подмножества ^[1] оказался оптимальным Лупановым . ^[2]

УФА – ДФА: $2^{n}$ говорится, см. Люнг , ^[3] Более ранняя нижняя оценка Шмидта ^[4] был меньше.
НФА в УФА: $2^{n}-1$ штаты, см. Люнг. ^[3] Ранее Шмидт предложил меньшую нижнюю оценку. ^[4]
SVFA в DFA: $\Theta (3^{n/3})$ штаты, см. Йираскова и Пигиццини. ^[5]
2DFA в DFA: $n(n^{n}-(n-1)^{n})$ говорится, см. Капуцис . ^[6] Ранее постройка Шепердсона ^[7] использовал больше штатов и более раннюю нижнюю границу Мура ^[8] был меньше.
2DFA в NFA: ${\binom {2n}{n+1}}=O({\frac {4^{n}}{\sqrt {n}}})$ , см. Капуцис. ^[6] Ранее постройка Биргета ^[9] использовал больше штатов.
2NFA в NFA: ${\binom {2n}{n+1}}$ ${\binom {2n}{n+1}}$ , см. Капуцис. ^[6]
- 2NFA к NFA, принимающему дополнение: $O(4^{n})$ штаты, см. Варди . ^[10]
От AFA до DFA: $2^{2^{n}}$ говорится, см. Чандра , Козен и Стокмейер . ^[11]
От АФА до НФА: $2^{n}$ государства, см. Fellah, Jürgensen and Yu. ^[12]
2AFA в DFA: $2^{n2^{n}}$ см. Ладнер , Липтон и Стокмейер . ^[13]
2AFA в NFA: $2^{\Theta (n\log n)}$ , see Geffert and Okhotin. ^[14]

Проблема 2DFA против 2NFA и логарифмическое пространство

Нерешенная задача в информатике :

Каждый ли

n

-state 2NFA имеет эквивалент

\operatorname {poly} (n)

-состояние 2DFA?

(еще нерешенные проблемы по информатике)

Вопрос о том, можно ли преобразовать все 2NFA в 2DFA, остается открытым. с полиномиальным числом состояний, т.е. существует ли полином $p(n)$ такой, что для каждого $n$ -состояние 2NFA существует $p(n)$ -состояние 2DFA. Проблему подняли Сакода и Сипсер . ^[15] кто сравнил это с P против NP проблемой в теории сложности вычислений . Берман и Лингас ^[16] обнаружил формальную связь между этой проблемой и открытая проблема L против NL . Это соотношение было далее развито Капуцисом . ^[17]

Состояние сложности операций для конечных автоматов

Дана бинарная операция, сохраняющая регулярность на языках. $\circ$ и семейство автоматов X (DFA, NFA и т. д.), государственная сложность $\circ$ целочисленная функция $f(m,n)$ такой, что

для каждого X-автомата A с m-состояниями и X-автомата B с n-состояниями существует $f(m,n)$ -state X-автомат для $L(A)\circ L(B)$ , и
для всех целых m, n существует X-автомат A с m состояниями и X-автомат B с n состояниями такие, что каждый X-автомат для $L(A)\circ L(B)$ должен иметь по крайней мере $f(m,n)$ государства.

Аналогичное определение применимо для операций с любым количеством аргументов.

Первые результаты по состоянию сложности операций для DFA были опубликованы Масловым ^[18] and by Yu, Zhuang and Salomaa . ^[19] Хольцер и Кутриб ^[20] впервые установил государственную сложность операций по NFA. Ниже приведены известные результаты для основных операций.

Союз

Если язык $L_{1}$ требует m состояний и язык $L_{2}$ требует n состояний, сколько штатов имеет $L_{1}\cup L_{2}$ требовать?

ДФА: $mn$ states, see Maslov ^[18]и Ю, Чжуан и Саломаа. ^[19]
ДЕЛА: $m+n+1$ говорится, см. Хольцер и Кутриб. ^[20]
УФА: минимум $\min(n,m)^{\Omega (\log(\min(n,m)))}$ ; ^[21] между $mn+m+n$ и $m+nm2^{0.79m}$ штаты, см. Йирасек, Йираскова и Шебей. ^[22]
СВФА: $mn$ государства см. Йирасек, Йираскова и Сабари. ^[23]
2DFA: между $m+n$ и $4m+n+4$ states, see Kunc and Okhotin. ^[24]
2НФА: $m+n$ states, see Kunc and Okhotin. ^[25]

Пересечение

Сколько штатов имеет $L_{1}\cap L_{2}$ требовать?

ДФА: $mn$ states, see Maslov ^[18]и Ю, Чжуан и Саломаа. ^[19]
ДЕЛА: $mn$ говорится, см. Хольцер и Кутриб. ^[20]
УМИРАТЬ: $mn$ штаты, см. Йирасек, Йираскова и Шебей. ^[22]
СВФА: $mn$ государства см. Йирасек, Йираскова и Сабари. ^[23]
2DFA: между $m+n$ и $m+n+1$ states, see Kunc and Okhotin. ^[24]
2NFA: между $m+n$ и $m+n+1$ states, see Kunc and Okhotin. ^[25]

Дополнение

Если язык L требует n состояний тогда сколько штатов требуется для его дополнения ?

ДФА: $n$ состояний путем обмена принимающими и отвергающими состояниями.
ДЕЛА: $2^{n}$ говорится, см. Биргет. ^[26] или Йираскова ^[27]
УФА: минимум $n^{{\tilde {\Omega }}(\log n)}$ государства, см. Гёэса, Кифера и Юаня, ^[21] (это следует за более ранней оценкой Раскина ^[28]); и самое большее ${\sqrt {n+1}}\cdot 2^{0.5n}$ государства см. Инджев и Кифер. ^[29]
СВФА: $n$ состояний путем обмена принимающими и отвергающими состояниями.
2DFA: как минимум $n$ и самое большее $4n$ штаты, см. Гефферт, Мерегетти и Пигиццини. ^[30]

Конкатенация

Сколько штатов имеет $L_{1}L_{2}=\{w_{1}w_{2}\mid w_{1}\in L_{1},w_{2}\in L_{2}\}$ требовать?

ДФА: $m\cdot 2^{n}-2^{n-1}$ states, see Maslov ^[18]и Ю, Чжуан и Саломаа. ^[19]
ДЕЛА: $m+n$ говорится, см. Хольцер и Кутриб. ^[20]
УМИРАТЬ: ${\frac {3}{4}}2^{m+n}-1$ штаты, см. Йирасек, Йираскова и Шебей. ^[22]
СВФА: $\Theta (3^{n/3}2^{m})$ государства см. Йирасек, Йираскова и Сабари. ^[23]
2DFA: как минимум ${\frac {2^{\Omega (n)}}{\log m}}$ и самое большее $2m^{m+1}\cdot 2^{n^{n+1}}$ государства, см. Йираскова и Охотин. ^[31]

Клини звезда

ДФА: ${\frac {3}{4}}2^{n}$ states, see Maslov ^[18]и Ю, Чжуан и Саломаа. ^[19]
ДЕЛА: $n+1$ говорится, см. Хольцер и Кутриб. ^[20]
УМИРАТЬ: ${\frac {3}{4}}2^{n}$ штаты, см. Йирасек, Йираскова и Шебей. ^[22]
СВФА: ${\frac {3}{4}}2^{n}$ государства см. Йирасек, Йираскова и Сабари. ^[23]
2DFA: как минимум ${\frac {1}{n}}2^{{\frac {n}{2}}-1}$ и самое большее $2^{O(n^{n+1})}$ государства, см. Йираскова и Охотин. ^[31]

Разворот

ДФА: $2^{n}$ говорится, см. Миркин, ^[32] Лейсс, ^[33]и Ю, Чжуан и Саломаа. ^[19]
ДЕЛА: $n+1$ говорится, см. Хольцер и Кутриб. ^[20]
УМИРАТЬ: $n$ государства.
СВФА: $2n+1$ государства см. Йирасек, Йираскова и Сабари. ^[23]
2DFA: между $n+1$ и $n+2$ государства, см. Йираскова и Охотин. ^[31]

Конечные автоматы над унарным алфавитом

Государственная сложность конечных автоматов с однобуквенным ( унарным ) алфавитом, впервые предложенным Хробаком , ^[34] отличается от многобуквенного регистра.

Позволять $g(n)=e^{\Theta ({\sqrt {n\ln n}})}$ быть функцией Ландау .

Трансформация между моделями

Для однобуквенного алфавита преобразования между разными типами конечных автоматов иногда оказываются более эффективными, чем в общем случае.

NFA в DFA: $g(n)+O(n^{2})$ говорится, см. Хробак. ^[34]
2DFA в DFA: $g(n)+O(n)$ государства, см. Хробака ^[34] and Kunc and Okhotin. ^[35]
2NFA в DFA: $O(g(n))$ штатах, см. Мерегетти и Пигиццини . ^[36] и Гефферт , Мерегетти и Пигиццини. ^[37]
от NFA до 2DFA: максимум $O(n^{2})$ говорится, см. Хробак. ^[34]
от 2NFA до 2DFA: максимум $n^{O(\log n)}$ состояния, доказанные с помощью метода теоремы Савича , см. Гефферта, Мерегетти и Пигиццини. ^[37]
УФА – ДФА: $e^{\Theta ({\sqrt[{3}]{n(\ln n)^{2}}})}$ , see Okhotin. ^[38]
НФА в УФА: $g(n)+O(n^{2})$ , see Okhotin. ^[38]

Союз

ДФА: $mn$ государства см. Ю, Чжуан и Соломон. ^[19]
ДЕЛА: $m+n+1$ говорится, см. Хольцер и Кутриб. ^[20]
2DFA: между $m+n$ и $2m+n+4$ states, see Kunc and Okhotin. ^[24]
2НФА: $m+n$ states, see Kunc and Okhotin. ^[25]

Пересечение

ДФА: $mn$ государства см. Ю, Чжуан и Соломон. ^[19]
ДЕЛА: $mn$ говорится, см. Хольцер и Кутриб. ^[20]
2DFA: между $m+n$ и $m+n+1$ states, see Kunc and Okhotin. ^[24]
2NFA: между $m+n$ и $m+n+1$ states, see Kunc and Okhotin. ^[25]

Дополнение

ДФА: $n$ государства.
ДЕЛА: $g(n)+O(n^{2})$ говорится, см. Хольцер и Кутриб. ^[20]
УФА: минимум $n^{(\log \log \log n)^{\Theta (1)}}$ говорится, см. Раскин, ^[39] и самое большее $e^{\Theta ({\sqrt[{3}]{n(\ln n)^{2}}})}$ states, see Okhotin. ^[38]
2DFA: как минимум $n$ и самое большее $2n+3$ states, see Kunc and Okhotin. ^[24]
2НФА: как минимум $n$ и самое большее $O(n^{8})$ государства. Верхняя граница достигается путем реализации метода теоремы Иммермана – Селепшени , см. Гефферта, Мерегетти и Пигиццини. ^[30]

Конкатенация

ДФА: $mn$ государства см. Ю, Чжуан и Соломон. ^[19]
НФА: между $m+n-1$ и $m+n$ говорится, см. Хольцер и Кутриб. ^[20]
2ДФА: $e^{\Theta ({\sqrt {(m+n)\log(m+n)}})}$ states, see Kunc and Okhotin. ^[24]
2НФА: $e^{\Theta ({\sqrt {(m+n)\log(m+n)}})}$ states, see Kunc and Okhotin. ^[24]

Клини звезда

ДФА: $(n-1)^{2}+1$ государства см. Ю, Чжуан и Соломон. ^[19]
ДЕЛА: $n+1$ говорится, см. Хольцер и Кутриб. ^[20]
УМИРАТЬ: $(n-1)^{2}+1$ states, see Okhotin. ^[38]
2ДФА: $\Theta ((g(n))^{2})$ states, see Kunc and Okhotin. ^[24]
2НФА: $\Theta (g(n))$ states, see Kunc and Okhotin. ^[24]

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

Обследования государственной сложности были написаны Хольцером и Кутрибом ^[40]^[41] и Гао и др. ^[42]

Новое исследование сложности состояний обычно представляется на ежегодных семинарах по Описательная сложность формальных систем (DCFS), в Конференция по внедрению и применению автоматов (CIAA), и на различных конференциях по теоретической информатике в целом.

Ссылки

^ Рабин, Миссури; Скотт, Д. (1959). «Конечные автоматы и проблемы их решения». Журнал исследований и разработок IBM . 3 (2): 114–125. дои : 10.1147/рд.32.0114 . ISSN 0018-8646 .
^ Лупанов, Олег Борисович (1963). «Сравнение двух типов конечных источников». Проблемы Кибернетики . 9 : 321–326.
^ Jump up to: ^а ^б Люнг, Хинг (2005). «Описательная сложность НКА различной неоднозначности». Международный журнал основ компьютерных наук . 16 (5): 975–984. дои : 10.1142/S0129054105003418 . ISSN 0129-0541 .
^ Jump up to: ^а ^б Шмидт, Эрик М. (1978). Краткость описания контекстно-свободных, регулярных и однозначных языков (доктор философии). Корнелльский университет.
^ Йираскова, Галина; Пигиццини, Джованни (2011). «Оптимальное моделирование самопроверяющихся автоматов детерминированными автоматами». Информация и вычисления . 209 (3): 528–535. дои : 10.1016/j.ic.2010.11.017 . ISSN 0890-5401 .
^ Jump up to: ^а ^б ^с Капуцис, Христос (2005). «Удаление двунаправленности из недетерминированных конечных автоматов». Математические основы информатики 2005 . Конспекты лекций по информатике. Том. 3618. стр. 544–555. дои : 10.1007/11549345_47 . ISBN 978-3-540-28702-5 . ISSN 0302-9743 .
^ Шепердсон, Дж. К. (1959). «Сведение двусторонних автоматов к односторонним автоматам». Журнал исследований и разработок IBM . 3 (2): 198–200. дои : 10.1147/рд.32.0198 . ISSN 0018-8646 .
^ Мур, Франция (1971). «О границах размера набора состояний в доказательствах эквивалентности детерминированных, недетерминированных и двусторонних конечных автоматов». Транзакции IEEE на компьютерах . С-20 (10): 1211–1214. дои : 10.1109/TC.1971.223108 . ISSN 0018-9340 . S2CID 206618275 .
^ Бирже, Жан-Камиль (1993). «Сложность состояний конечных устройств, сжимаемость и несжимаемость состояний». Теория математических систем . 26 (3): 237–269. дои : 10.1007/BF01371727 . ISSN 0025-5661 . S2CID 20375279 .
^ Варди, Моше Ю. (1989). «Заметка о приведении двусторонних автоматов к односторонним». Письма об обработке информации . 30 (5): 261–264. CiteSeerX 10.1.1.60.464 . дои : 10.1016/0020-0190(89)90205-6 . ISSN 0020-0190 .
^ Чандра, Ашок К.; Козен, Декстер К.; Стокмейер, Ларри Дж. (1981). «Чередование» . Журнал АКМ . 28 (1): 114–133. дои : 10.1145/322234.322243 . ISSN 0004-5411 . S2CID 238863413 .
^ Феллах, А.; Юргенсен, Х.; Ю, С. (1990). «Конструкции попеременных конечных автоматов∗». Международный журнал компьютерной математики . 35 (1–4): 117–132. дои : 10.1080/00207169008803893 . ISSN 0020-7160 .
^ Ладнер, Ричард Э.; Липтон, Ричард Дж.; Стокмейер, Ларри Дж. (1984). «Попеременные автоматы с выталкиванием и стекированием». SIAM Journal по вычислительной технике . 13 (1): 135–155. дои : 10.1137/0213010 . ISSN 0097-5397 .
^ Гефферт, Вильям; Охотин, Александр (2014). Преобразование двусторонних попеременных конечных автоматов в односторонние недетерминированные автоматы . Конспекты лекций по информатике. Том. 8634. стр. 291–302. дои : 10.1007/978-3-662-44522-8_25 . ISBN 978-3-662-44521-1 . ISSN 0302-9743 .
^ Сакода, Уильям Дж.; Сипсер, Майкл (1978). «Недетерминизм и размер двусторонних конечных автоматов». Материалы десятого ежегодного симпозиума ACM по теории вычислений - STOC '78 . СТОК 1978. ACM. стр. 275–286. дои : 10.1145/800133.804357 .
^ Берман, Петр; Лингас, Анджей (1977). О сложности регулярных языков в терминах конечных автоматов . Том. Отчет 304. Польская академия наук.
^ Капуцис, Христос А. (2014). «Двусторонние автоматы против логарифмического пространства». Теория вычислительных систем . 55 (2): 421–447. дои : 10.1007/s00224-013-9465-0 . S2CID 14808151 .
^ Jump up to: ^а ^б ^с ^д ^и Маслов А.Н. (1970). «Оценки числа состояний конечных автоматов». Советская математика — Доклады . 11 : 1373–1375.
^ Jump up to: ^а ^б ^с ^д ^и ^ж ^г ^час ^я ^дж Ю, Шэн; Чжуан, Цинъюй; Саломаа, Кай (1994). «Состояние сложностей некоторых основных операций на обычных языках». Теоретическая информатика . 125 (2): 315–328. дои : 10.1016/0304-3975(92)00011-F . ISSN 0304-3975 .
^ Jump up to: ^а ^б ^с ^д ^и ^ж ^г ^час ^я ^дж ^к Хольцер, Маркус; Кутриб, Мартин (2003). «Недетерминированная описательная сложность регулярных языков» . Международный журнал основ компьютерных наук (представлена рукопись). 14 (6): 1087–1102. дои : 10.1142/S0129054103002199 . ISSN 0129-0541 .
^ Jump up to: ^а ^б Гёос, Мика; Кифер, Стефан; Юань, Вэйцян (12 февраля 2022 г.). «Нижние границы однозначных автоматов через сложность связи». arXiv : 2109.09155 [ cs.FL ].
^ Jump up to: ^а ^б ^с ^д Йирасек, Йозеф; Йираскова, Галина; Шебей, Юрай (2016). Операции над однозначными конечными автоматами . Конспекты лекций по информатике. Том. 9840. стр. 243–255. дои : 10.1007/978-3-662-53132-7_20 . ISBN 978-3-662-53131-0 . ISSN 0302-9743 .
^ Jump up to: ^а ^б ^с ^д ^и Йирасек, Йозеф Штефан; Жираскова Галина; Сабари, Александр (2015). Информатика – теория и приложения . Конспекты лекций по информатике. Том. 9139.стр. 231–261. дои : 10.1007/978-3-319-20297-6_16 . ISBN 978-3-319-20296-9 . ISSN 0302-9743 .
^ Jump up to: ^а ^б ^с ^д ^и ^ж ^г ^час ^я Кунц, Михал; Охотин, Александр (2012). «Состояние сложности операций над двусторонними конечными автоматами над унарным алфавитом» . Теоретическая информатика . 449 : 106–118. дои : 10.1016/j.tcs.2012.04.010 . ISSN 0304-3975 .
^ Jump up to: ^а ^б ^с ^д Кунц, Михал; Охотин, Александр (2011). «Состояние сложности объединения и пересечения двусторонних недетерминированных конечных автоматов». Фундамента информатики . 110 (1–4): 231–239. дои : 10.3233/FI-2011-540 .
^ Бирже, Жан-Камиль (1993). «Частичный порядок слов, минимальные элементы обычных языков и сложность состояний». Теоретическая информатика . 119 (2): 267–291. дои : 10.1016/0304-3975(93)90160-У . ISSN 0304-3975 .
^ Йираскова, Галина (2005). «Укажите сложность некоторых операций на бинарных регулярных языках» . Теоретическая информатика . 330 (2): 287–298. дои : 10.1016/j.tcs.2004.04.011 . , Теорема 5
^ Раскин, Михаил (2018). «Суперполиномиальная нижняя граница размера недетерминированного дополнения однозначного автомата» . DROPS-IDN/V2/Document/10.4230/LIPIcs.ICALP.2018.138 . Шлосс-Дагштуль - Центр информатики Лейбница. doi : 10.4230/LIPIcs.ICALP.2018.138 .
^ Инджев, Эмиль; Кифер, Стефан (1 августа 2022 г.). «О дополнении однозначных автоматов и графов многими кликами и кокликами» . Письма об обработке информации . 177 : 106270. arXiv : 2105.07470 . дои : 10.1016/j.ipl.2022.106270 . ISSN 0020-0190 . S2CID 234741832 . Проверено 29 мая 2022 г.
^ Jump up to: ^а ^б Гефферт, Вильям; Мерегетти, Карло; Пигиццини, Джованни (2007). «Дополняющие двусторонние конечные автоматы» . Информация и вычисления . 205 (8): 1173–1187. дои : 10.1016/j.ic.2007.01.008 . ISSN 0890-5401 .
^ Jump up to: ^а ^б ^с Йираскова, Галина; Охотин, Александр (2008). О государственной сложности операций над двусторонними конечными автоматами . Конспекты лекций по информатике. Том. 5257. стр. 443–454. дои : 10.1007/978-3-540-85780-8_35 . ISBN 978-3-540-85779-2 . ISSN 0302-9743 .
^ Миркин, Борис Георгиевич (1966). «О двойственных автоматах». Кибернетика . 2 :6–9. дои : 10.1007/bf01072247 . S2CID 123186223 .
^ Лейсс, Эрнст (1985). «Краткое представление регулярных языков булевыми автоматами II». Теоретическая информатика . 38 : 133–136. дои : 10.1016/0304-3975(85)90215-4 . ISSN 0304-3975 .
^ Jump up to: ^а ^б ^с ^д Хробак, Марек (1986). «Конечные автоматы и унарные языки». Теоретическая информатика . 47 : 149–158. дои : 10.1016/0304-3975(86)90142-8 . ISSN 0304-3975 .
^ Кунц, Михал; Охотин, Александр (2011). Развитие теории языка . Конспекты лекций по информатике. Том. 6795. стр. 324–336. CiteSeerX 10.1.1.616.8835 . дои : 10.1007/978-3-642-22321-1_28 . ISBN 978-3-642-22320-4 . ISSN 0302-9743 .
^ Мерегетти, Карло; Пигиццини, Джованни (2001). «Оптимальное моделирование унарных автоматов». SIAM Journal по вычислительной технике . 30 (6): 1976–1992. дои : 10.1137/S009753979935431X . hdl : 2434/35121 . ISSN 0097-5397 .
^ Jump up to: ^а ^б Гефферт, Вильям; Мерегетти, Карло; Пигиццини, Джованни (2003). «Преобразование двусторонних недетерминированных унарных автоматов в более простые автоматы». Теоретическая информатика . 295 (1–3): 189–203. дои : 10.1016/S0304-3975(02)00403-6 . ISSN 0304-3975 .
^ Jump up to: ^а ^б ^с ^д Охотин, Александр (2012). «Однозначные конечные автоматы над унарным алфавитом» . Информация и вычисления . 212 : 15–36. дои : 10.1016/j.ic.2012.01.003 . ISSN 0890-5401 .
^ Раскин, Майкл (2018). «Суперполиномиальная нижняя граница размера недетерминированного дополнения однозначного автомата». Учеб. ИКП 2018 . стр. 138:1–138:11. doi : 10.4230/LIPIcs.ICALP.2018.138 .
^ Хольцер, Маркус; Кутриб, Мартин (2009). «Недетерминированные конечные автоматы - последние результаты по сложности описания и вычислений». Международный журнал основ компьютерных наук . 20 (4): 563–580. дои : 10.1142/S0129054109006747 . ISSN 0129-0541 .
^ Хольцер, Маркус; Кутриб, Мартин (2011). «Описательная и вычислительная сложность конечных автоматов — обзор». Информация и вычисления . 209 (3): 456–470. дои : 10.1016/j.ic.2010.11.013 . ISSN 0890-5401 .
^ Гао, Юань; Морейра, Нельма; Рейс, Рожерио; Ю, Шэн (2015). «Обзор сложности оперативного состояния». arXiv : 1509.03254v1 [ cs.FL ].

[RabinScott1959-1] Рабин, Миссури; Скотт, Д. (1959). «Конечные автоматы и проблемы их решения». Журнал исследований и разработок IBM . 3 (2): 114–125. дои : 10.1147/рд.32.0114 . ISSN 0018-8646 .

[2] Лупанов, Олег Борисович (1963). «Сравнение двух типов конечных источников». Проблемы Кибернетики . 9 : 321–326.

[Leung2005-3] Jump up to: ^а ^б Люнг, Хинг (2005). «Описательная сложность НКА различной неоднозначности». Международный журнал основ компьютерных наук . 16 (5): 975–984. дои : 10.1142/S0129054105003418 . ISSN 0129-0541 .

[Schmidt1978-4] Jump up to: ^а ^б Шмидт, Эрик М. (1978). Краткость описания контекстно-свободных, регулярных и однозначных языков (доктор философии). Корнелльский университет.

[JiráskováPighizzini2011-5] Йираскова, Галина; Пигиццини, Джованни (2011). «Оптимальное моделирование самопроверяющихся автоматов детерминированными автоматами». Информация и вычисления . 209 (3): 528–535. дои : 10.1016/j.ic.2010.11.017 . ISSN 0890-5401 .

[Kapoutsis2005-6] Jump up to: ^а ^б ^с Капуцис, Христос (2005). «Удаление двунаправленности из недетерминированных конечных автоматов». Математические основы информатики 2005 . Конспекты лекций по информатике. Том. 3618. стр. 544–555. дои : 10.1007/11549345_47 . ISBN 978-3-540-28702-5 . ISSN 0302-9743 .

[Shepherdson1959-7] Шепердсон, Дж. К. (1959). «Сведение двусторонних автоматов к односторонним автоматам». Журнал исследований и разработок IBM . 3 (2): 198–200. дои : 10.1147/рд.32.0198 . ISSN 0018-8646 .

[Moore1971-8] Мур, Франция (1971). «О границах размера набора состояний в доказательствах эквивалентности детерминированных, недетерминированных и двусторонних конечных автоматов». Транзакции IEEE на компьютерах . С-20 (10): 1211–1214. дои : 10.1109/TC.1971.223108 . ISSN 0018-9340 . S2CID 206618275 .

[Birget1993a-9] Бирже, Жан-Камиль (1993). «Сложность состояний конечных устройств, сжимаемость и несжимаемость состояний». Теория математических систем . 26 (3): 237–269. дои : 10.1007/BF01371727 . ISSN 0025-5661 . S2CID 20375279 .

[Vardi1989-10] Варди, Моше Ю. (1989). «Заметка о приведении двусторонних автоматов к односторонним». Письма об обработке информации . 30 (5): 261–264. CiteSeerX 10.1.1.60.464 . дои : 10.1016/0020-0190(89)90205-6 . ISSN 0020-0190 .

[ChandraKozen1981-11] Чандра, Ашок К.; Козен, Декстер К.; Стокмейер, Ларри Дж. (1981). «Чередование» . Журнал АКМ . 28 (1): 114–133. дои : 10.1145/322234.322243 . ISSN 0004-5411 . S2CID 238863413 .

[FellahJürgensen1990-12] Феллах, А.; Юргенсен, Х.; Ю, С. (1990). «Конструкции попеременных конечных автоматов∗». Международный журнал компьютерной математики . 35 (1–4): 117–132. дои : 10.1080/00207169008803893 . ISSN 0020-7160 .

[LadnerLipton1984-13] Ладнер, Ричард Э.; Липтон, Ричард Дж.; Стокмейер, Ларри Дж. (1984). «Попеременные автоматы с выталкиванием и стекированием». SIAM Journal по вычислительной технике . 13 (1): 135–155. дои : 10.1137/0213010 . ISSN 0097-5397 .

[GeffertOkhotin2014-14] Гефферт, Вильям; Охотин, Александр (2014). Преобразование двусторонних попеременных конечных автоматов в односторонние недетерминированные автоматы . Конспекты лекций по информатике. Том. 8634. стр. 291–302. дои : 10.1007/978-3-662-44522-8_25 . ISBN 978-3-662-44521-1 . ISSN 0302-9743 .

[15] Сакода, Уильям Дж.; Сипсер, Майкл (1978). «Недетерминизм и размер двусторонних конечных автоматов». Материалы десятого ежегодного симпозиума ACM по теории вычислений - STOC '78 . СТОК 1978. ACM. стр. 275–286. дои : 10.1145/800133.804357 .

[16] Берман, Петр; Лингас, Анджей (1977). О сложности регулярных языков в терминах конечных автоматов . Том. Отчет 304. Польская академия наук.

[17] Капуцис, Христос А. (2014). «Двусторонние автоматы против логарифмического пространства». Теория вычислительных систем . 55 (2): 421–447. дои : 10.1007/s00224-013-9465-0 . S2CID 14808151 .

[Maslov-18] Jump up to: ^а ^б ^с ^д ^и Маслов А.Н. (1970). «Оценки числа состояний конечных автоматов». Советская математика — Доклады . 11 : 1373–1375.

[YuZhuang1994-19] Jump up to: ^а ^б ^с ^д ^и ^ж ^г ^час ^я ^дж Ю, Шэн; Чжуан, Цинъюй; Саломаа, Кай (1994). «Состояние сложностей некоторых основных операций на обычных языках». Теоретическая информатика . 125 (2): 315–328. дои : 10.1016/0304-3975(92)00011-F . ISSN 0304-3975 .

[HolzerKutrib2003-20] Jump up to: ^а ^б ^с ^д ^и ^ж ^г ^час ^я ^дж ^к Хольцер, Маркус; Кутриб, Мартин (2003). «Недетерминированная описательная сложность регулярных языков» . Международный журнал основ компьютерных наук (представлена рукопись). 14 (6): 1087–1102. дои : 10.1142/S0129054103002199 . ISSN 0129-0541 .

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

[JirásekJirásková2016-22] Jump up to: ^а ^б ^с ^д Йирасек, Йозеф; Йираскова, Галина; Шебей, Юрай (2016). Операции над однозначными конечными автоматами . Конспекты лекций по информатике. Том. 9840. стр. 243–255. дои : 10.1007/978-3-662-53132-7_20 . ISBN 978-3-662-53131-0 . ISSN 0302-9743 .

[JirásekJirásková2015-23] Jump up to: ^а ^б ^с ^д ^и Йирасек, Йозеф Штефан; Жираскова Галина; Сабари, Александр (2015). Информатика – теория и приложения . Конспекты лекций по информатике. Том. 9139.стр. 231–261. дои : 10.1007/978-3-319-20297-6_16 . ISBN 978-3-319-20296-9 . ISSN 0302-9743 .

[KuncOkhotin2012-24] Jump up to: ^а ^б ^с ^д ^и ^ж ^г ^час ^я Кунц, Михал; Охотин, Александр (2012). «Состояние сложности операций над двусторонними конечными автоматами над унарным алфавитом» . Теоретическая информатика . 449 : 106–118. дои : 10.1016/j.tcs.2012.04.010 . ISSN 0304-3975 .

[KuncOkhotin2011-25] Jump up to: ^а ^б ^с ^д Кунц, Михал; Охотин, Александр (2011). «Состояние сложности объединения и пересечения двусторонних недетерминированных конечных автоматов». Фундамента информатики . 110 (1–4): 231–239. дои : 10.3233/FI-2011-540 .

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

[27] Йираскова, Галина (2005). «Укажите сложность некоторых операций на бинарных регулярных языках» . Теоретическая информатика . 330 (2): 287–298. дои : 10.1016/j.tcs.2004.04.011 . , Теорема 5

[28] Раскин, Михаил (2018). «Суперполиномиальная нижняя граница размера недетерминированного дополнения однозначного автомата» . DROPS-IDN/V2/Document/10.4230/LIPIcs.ICALP.2018.138 . Шлосс-Дагштуль - Центр информатики Лейбница. doi : 10.4230/LIPIcs.ICALP.2018.138 .

[29] Инджев, Эмиль; Кифер, Стефан (1 августа 2022 г.). «О дополнении однозначных автоматов и графов многими кликами и кокликами» . Письма об обработке информации . 177 : 106270. arXiv : 2105.07470 . дои : 10.1016/j.ipl.2022.106270 . ISSN 0020-0190 . S2CID 234741832 . Проверено 29 мая 2022 г.

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

[JiráskováOkhotin2008-31] Jump up to: ^а ^б ^с Йираскова, Галина; Охотин, Александр (2008). О государственной сложности операций над двусторонними конечными автоматами . Конспекты лекций по информатике. Том. 5257. стр. 443–454. дои : 10.1007/978-3-540-85780-8_35 . ISBN 978-3-540-85779-2 . ISSN 0302-9743 .

[Mirkin1966-32] Миркин, Борис Георгиевич (1966). «О двойственных автоматах». Кибернетика . 2 :6–9. дои : 10.1007/bf01072247 . S2CID 123186223 .

[Leiss1985-33] Лейсс, Эрнст (1985). «Краткое представление регулярных языков булевыми автоматами II». Теоретическая информатика . 38 : 133–136. дои : 10.1016/0304-3975(85)90215-4 . ISSN 0304-3975 .

[Chrobak1986-34] Jump up to: ^а ^б ^с ^д Хробак, Марек (1986). «Конечные автоматы и унарные языки». Теоретическая информатика . 47 : 149–158. дои : 10.1016/0304-3975(86)90142-8 . ISSN 0304-3975 .

[KuncOkhotin2011b-35] Кунц, Михал; Охотин, Александр (2011). Развитие теории языка . Конспекты лекций по информатике. Том. 6795. стр. 324–336. CiteSeerX 10.1.1.616.8835 . дои : 10.1007/978-3-642-22321-1_28 . ISBN 978-3-642-22320-4 . ISSN 0302-9743 .

[MereghettiPighizzini2001-36] Мерегетти, Карло; Пигиццини, Джованни (2001). «Оптимальное моделирование унарных автоматов». SIAM Journal по вычислительной технике . 30 (6): 1976–1992. дои : 10.1137/S009753979935431X . hdl : 2434/35121 . ISSN 0097-5397 .

[GeffertMereghetti2003-37] Jump up to: ^а ^б Гефферт, Вильям; Мерегетти, Карло; Пигиццини, Джованни (2003). «Преобразование двусторонних недетерминированных унарных автоматов в более простые автоматы». Теоретическая информатика . 295 (1–3): 189–203. дои : 10.1016/S0304-3975(02)00403-6 . ISSN 0304-3975 .

[Okhotin2012-38] Jump up to: ^а ^б ^с ^д Охотин, Александр (2012). «Однозначные конечные автоматы над унарным алфавитом» . Информация и вычисления . 212 : 15–36. дои : 10.1016/j.ic.2012.01.003 . ISSN 0890-5401 .

[Raskin2018-39] Раскин, Майкл (2018). «Суперполиномиальная нижняя граница размера недетерминированного дополнения однозначного автомата». Учеб. ИКП 2018 . стр. 138:1–138:11. doi : 10.4230/LIPIcs.ICALP.2018.138 .

[HolzerKutrib2009-40] Хольцер, Маркус; Кутриб, Мартин (2009). «Недетерминированные конечные автоматы - последние результаты по сложности описания и вычислений». Международный журнал основ компьютерных наук . 20 (4): 563–580. дои : 10.1142/S0129054109006747 . ISSN 0129-0541 .

[HolzerKutrib2011-41] Хольцер, Маркус; Кутриб, Мартин (2011). «Описательная и вычислительная сложность конечных автоматов — обзор». Информация и вычисления . 209 (3): 456–470. дои : 10.1016/j.ic.2010.11.013 . ISSN 0890-5401 .

[42] Гао, Юань; Морейра, Нельма; Рейс, Рожерио; Ю, Шэн (2015). «Обзор сложности оперативного состояния». arXiv : 1509.03254v1 [ cs.FL ].

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]

[23]

[24]

[25]

[26]

[27]

[28]

[29]

[30]

[31]

[32]

[33]

[34]

[35]

[36]

[37]

[38]

[39]

[40]

[41]

[42]