Сложность состояния - State complexity

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

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

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

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

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

• UFA в DFA: ${\displaystyle 2^{n}}$ государства, см. Leung,^[3] Ранняя нижняя оценка Шмидта^[4] был меньше.
• НФА в УФА: ${\displaystyle 2^{n}-1}$ состояния, см. Leung.^[3] Шмидт ранее использовал меньшую нижнюю границу.^[4]
• SVFA в DFA: ${\displaystyle \Theta (3^{n/3})}$ заявляет, см. Jirásková и Пигиццини^[5]
• 2DFA в DFA: ${\displaystyle n(n^{n}-(n-1)^{n})}$ государства, см. Капуцис.^[6] Ранее строительство Шепердсон^[7] использовали больше состояний, а более раннюю нижнюю границу Мура^[8] был меньше.
• 2DFA в NFA: ${\displaystyle {\binom {2n}{n+1}}=O({\frac {4^{n}}{\sqrt {n}}})}$, см. Капуцис.^[6] Ранее строительство Биргет ^[9] использовал больше состояний.
• 2NFA в NFA: ${\displaystyle {\binom {2n}{n+1}}}$, см. Капуцис.^[6]
  • 2NFA в NFA, принимая дополнение: ${\displaystyle O(4^{n})}$ государства, см. Варди.^[10]
• AFA в DFA: ${\displaystyle 2^{2^{n}}}$ государства, см. Чандра, Козен и Stockmeyer.^[11]
• AFA в NFA: ${\displaystyle 2^{n}}$ заявляет, см. Fellah, Jürgensen and Yu.^[12]
• 2AFA в DFA: ${\displaystyle 2^{n2^{n}}}$, видеть Ladner, Lipton и Stockmeyer.^[13]
• 2AFA в NFA: ${\displaystyle 2^{\Theta (n\log n)}}$, видеть Гефферт и Охотин.^[14]

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

Нерешенная проблема в информатике: Каждый ${\displaystyle n}$-состояние 2NFA имеет эквивалент ${\displaystyle \operatorname {poly} (n)}$-состояние 2DFA? (больше нерешенных проблем в информатике)

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

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

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

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

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

Первые результаты о сложности операций для ДКА опубликовал Маслов.^[18]и Ю, Чжуан и Саломаа.^[19]Хольцер и Кутриб^[20]впервые исследовал сложность состояний операций над NFA. Известные результаты для основных операций перечислены ниже.

Союз

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

• DFA: ${\displaystyle mn}$ заявляет, см. Маслов^[18] и Ю, Чжуан и Саломаа.^[19]
• NFA: ${\displaystyle m+n+1}$ состояния, см. Хольцер и Кутриб.^[20]
• УФА: между ${\displaystyle mn+m+n}$ и ${\displaystyle O(n2^{0.79m})}$ говорится, что см. Йирасек, Йираскова и Шебей.^[21]
• SVFA: ${\displaystyle mn}$ государства, см. Йирасек, Йираскова и Сабари.^[22]
• 2DFA: между ${\displaystyle m+n}$ и ${\displaystyle 4m+n+4}$ заявляет, см. Кунч и Охотин.^[23]
• 2NFA: ${\displaystyle m+n}$ заявляет, см. Кунч и Охотин.^[24]

Пересечение

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

• DFA: ${\displaystyle mn}$ заявляет, см. Маслов^[18] и Ю, Чжуан и Саломаа.^[19]
• NFA: ${\displaystyle mn}$ состояния, см. Хольцер и Кутриб.^[20]
• УФА: ${\displaystyle mn}$ говорится, что см. Йирасек, Йираскова и Шебей.^[21]
• SVFA: ${\displaystyle mn}$ государства, см. Йирасек, Йираскова и Сабари.^[22]
• 2DFA: между ${\displaystyle m+n}$ и ${\displaystyle m+n+1}$ заявляет, см. Кунч и Охотин.^[23]
• 2NFA: между ${\displaystyle m+n}$ и ${\displaystyle m+n+1}$ заявляет, см. Кунч и Охотин.^[24]

Дополнение

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

• DFA: ${\displaystyle n}$ состояний путем обмена состояниями принятия и отклонения.
• NFA: ${\displaystyle 2^{n}}$ состояния, см. Биргет.^[25]
• УФА: минимум ${\displaystyle n^{2-o(1)}}$ и самое большее ${\displaystyle O(2^{0.79n})}$ заявляет, см. Охотин^[26] для нижней границы и Йирасек, Йираскова и Шебей^[21] для верхней границы. Раскин^[27] недавно доказал суперполиномиальную нижнюю оценку.
• SVFA: ${\displaystyle n}$ состояний путем обмена состояниями принятия и отклонения.
• 2DFA: не менее ${\displaystyle n}$ и самое большее ${\displaystyle 4n}$ государства, см. Geffert, Mereghetti и Pighizzini.^[28]

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

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

• DFA: ${\displaystyle m\cdot 2^{n}-2^{n-1}}$ заявляет, см. Маслов ^[18] и Ю, Чжуан и Саломаа.^[19]
• NFA: ${\displaystyle m+n}$ состояния, см. Хольцер и Кутриб.^[20]
• УФА: ${\displaystyle {\frac {3}{4}}2^{m+n}-1}$ говорится, что см. Йирасек, Йираскова и Шебей.^[21]
• SVFA: ${\displaystyle \Theta (3^{n/3}2^{m})}$ государства, см. Йирасек, Йираскова и Сабари.^[22]
• 2DFA: не менее ${\displaystyle {\frac {2^{\Omega (n)}}{\log m}}}$ и самое большее ${\displaystyle 2m^{m+1}\cdot 2^{n^{n+1}}}$ заявляет, см. Жираскова и Охотин.^[29]

Клини звезда

• DFA: ${\displaystyle {\frac {3}{4}}2^{n}}$ заявляет, см. Маслов^[18] и Ю, Чжуан и Саломаа.^[19]
• NFA: ${\displaystyle n+1}$ состояния, см. Хольцер и Кутриб.^[20]
• УФА: ${\displaystyle {\frac {3}{4}}2^{n}}$ государства, см. Йирасек, Йираскова и Шебей.^[21]
• SVFA: ${\displaystyle {\frac {3}{4}}2^{n}}$ государства, см. Йирасек, Йираскова и Сабари.^[22]
• 2DFA: не менее ${\displaystyle {\frac {1}{n}}2^{{\frac {n}{2}}-1}}$ и самое большее ${\displaystyle 2^{O(n^{n+1})}}$ заявляет, см. Жираскова и Охотин.^[29]

Разворот

• DFA: ${\displaystyle 2^{n}}$ заявляет, см. Миркин,^[30] Лейсс,^[31] и Ю, Чжуан и Саломаа.^[19]
• NFA: ${\displaystyle n+1}$ состояния, см. Хольцер и Кутриб.^[20]
• УФА: ${\displaystyle n}$ состояния.
• SVFA: ${\displaystyle 2n+1}$ государства, см. Йирасек, Йираскова и Сабари.^[22]
• 2DFA: между ${\displaystyle n+1}$ и ${\displaystyle n+2}$ заявляет, см. Жираскова и Охотин.^[29]

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

Сложность состояний конечных автоматов с одной буквой (унарный) алфавит, изобретенный Чробак,^[32] отличается от многобуквенного регистра.

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

Преобразование между моделями

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

• NFA в DFA: ${\displaystyle g(n)+O(n^{2})}$ состояния, см. Хробак.^[32]
• 2DFA в DFA: ${\displaystyle g(n)+O(n)}$ государства, см. Хробак^[32] и Кунч и Охотин.^[33]
• 2NFA в DFA: ${\displaystyle O(g(n))}$ государства, см. Мегетти и Пигиццини.^[34] и Гефферт, Мегетти и Пигиццини.^[35]
• NFA в 2DFA: не более ${\displaystyle O(n^{2})}$ состояния, см. Хробак.^[32]
• 2NFA в 2DFA: не более ${\displaystyle n^{O(\log n)}}$ состояний, доказанных реализацией метода Теорема савича см. Гефферт, Мегетти и Пигиццини.^[35]
• UFA в DFA: ${\displaystyle e^{\Theta ({\sqrt[{3}]{n(\ln n)^{2}}})}}$, см. Охотин.^[26]
• НФА в УФА: ${\displaystyle g(n)+O(n^{2})}$, см. Охотин.^[26]

Союз

• DFA: ${\displaystyle mn}$ государства, см. Ю, Чжуан и Саломаа.^[19]
• NFA: ${\displaystyle m+n+1}$ состояния, см. Хольцер и Кутриб.^[20]
• 2DFA: между ${\displaystyle m+n}$ и ${\displaystyle 2m+n+4}$ заявляет, см. Кунч и Охотин.^[23]
• 2NFA: ${\displaystyle m+n}$ заявляет, см. Кунч и Охотин.^[24]

Пересечение

• DFA: ${\displaystyle mn}$ государства, см. Ю, Чжуан и Саломаа.^[19]
• NFA: ${\displaystyle mn}$ состояния, см. Хольцер и Кутриб.^[20]
• 2DFA: между ${\displaystyle m+n}$ и ${\displaystyle m+n+1}$ заявляет, см. Кунч и Охотин.^[23]
• 2NFA: между ${\displaystyle m+n}$ и ${\displaystyle m+n+1}$ заявляет, см. Кунч и Охотин.^[24]

Дополнение

• DFA: ${\displaystyle n}$ состояния.
• NFA: ${\displaystyle g(n)+O(n^{2})}$ государства, Хольцер и Кутриб.^[20]
• УФА: минимум ${\displaystyle n^{2-o(1)}}$ и самое большее ${\displaystyle e^{\Theta ({\sqrt[{3}]{n(\ln n)^{2}}})}}$ говорится, см. Охотин.^[26]
• 2DFA: не менее ${\displaystyle n}$ и самое большее ${\displaystyle 2n+3}$ заявляет, см. Кунч и Охотин.^[23]
• 2NFA: не менее ${\displaystyle n}$ и самое большее ${\displaystyle O(n^{8})}$ состояния. Верхняя граница осуществляется путем реализации метода Теорема Иммермана – Селепсеньи см. Гефферт, Мегетти и Пигиццини.^[28]

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

• DFA: ${\displaystyle mn}$ государства, см. Ю, Чжуан и Саломаа.^[19]
• NFA: между ${\displaystyle m+n-1}$ и ${\displaystyle m+n}$ состояния, см. Хольцер и Кутриб.^[20]
• 2DFA:${\displaystyle e^{\Theta ({\sqrt {(m+n)\log(m+n)}})}}$ заявляет, см. Кунч и Охотин.^[23]
• 2NFA:${\displaystyle e^{\Theta ({\sqrt {(m+n)\log(m+n)}})}}$ заявляет, см. Кунч и Охотин.^[23]

Клини звезда

• DFA: ${\displaystyle (n-1)^{2}+1}$ государства, см. Ю, Чжуан и Саломаа.^[19]
• NFA: ${\displaystyle n+1}$ состояния, см. Хольцер и Кутриб.^[20]
• УФА: ${\displaystyle (n-1)^{2}+1}$ говорится, см. Охотин.^[26]
• 2DFA:${\displaystyle \Theta ((g(n))^{2})}$ заявляет, см. Кунч и Охотин.^[23]
• 2NFA:${\displaystyle \Theta (g(n))}$ состояния, см. Кунч и Охотин.^[23]

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

Обзоры государственной сложности написали Хольцер и Кутриб.^[36][37]и Gao et al.^[38]

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

Рекомендации

1. Рабин, М. О .; Скотт, Д. (1959). «Конечные автоматы и проблемы их решения». Журнал исследований и разработок IBM. 3 (2): 114–125. Дои:10.1147 / rd.32.0114. ISSN  0018-8646.
2. Лупанов, Олег Б. (1963). «Сравнение двух типов конечных источников». Проблемы Кибернетики. 9: 321–326.
3. Люнг, Хинг (2005). «Описательная сложность NFA разной неоднозначности». Международный журнал основ информатики. 16 (5): 975–984. Дои:10.1142 / S0129054105003418. ISSN  0129-0541.
4. Шмидт, Эрик М. (1978). Краткость описания контекстно-свободных, регулярных и однозначных языков (Кандидат наук.). Корнелл Университет.
5. Йираскова, Галина; Пигиццини, Джованни (2011). «Оптимальное моделирование самопроверяющихся автоматов детерминированными автоматами». Информация и вычисления. 209 (3): 528–535. Дои:10.1016 / j.ic.2010.11.017. ISSN  0890-5401.
6. Капуцис, Христос (2005). «Удаление двунаправленности из недетерминированных конечных автоматов». Математические основы компьютерных наук 2005. Конспект лекций по информатике. 3618. С. 544–555. Дои:10.1007/11549345_47. ISBN  978-3-540-28702-5. ISSN  0302-9743.
7. Шепердсон, Дж. К. (1959). «Сведение двусторонних автоматов к односторонним». Журнал исследований и разработок IBM. 3 (2): 198–200. Дои:10.1147 / rd.32.0198. ISSN  0018-8646.
8. Мур, Ф. (1971). «На границах для размера набора состояний в доказательствах эквивалентности между детерминированными, недетерминированными и двусторонними конечными автоматами». Транзакции IEEE на компьютерах. С-20 (10): 1211–1214. Дои:10.1109 / T-C.1971.223108. ISSN  0018-9340.
9. Бирже, Жан-Камиль (1993). «Сложность состояний конечных устройств, сжимаемость и несжимаемость состояний». Математическая теория систем. 26 (3): 237–269. Дои:10.1007 / BF01371727. ISSN  0025-5661.
10. Варди, Моше Ю. (1989). «Замечание о сведении двусторонних автоматов к односторонним». Письма об обработке информации. 30 (5): 261–264. CiteSeerX  10.1.1.60.464. Дои:10.1016/0020-0190(89)90205-6. ISSN  0020-0190.
11. Chandra, Ashok K .; Kozen, Dexter C .; Стокмейер, Ларри Дж. (1981). «Чередование». Журнал ACM. 28 (1): 114–133. Дои:10.1145/322234.322243. ISSN  0004-5411.
12. Fellah, A .; Jürgensen, H .; Ю. С. (1990). «Конструкции для знакопеременных конечных автоматов ∗». Международный журнал компьютерной математики. 35 (1–4): 117–132. Дои:10.1080/00207169008803893. ISSN  0020-7160.
13. Ladner, Ричард Э .; Липтон, Ричард Дж .; Стокмейер, Ларри Дж. (1984). «Чередование автоматов выталкивания и стека». SIAM Журнал по вычислениям. 13 (1): 135–155. Дои:10.1137/0213010. ISSN  0097-5397.
14. Гефферт, Вильям; Охотин, Александр (2014). Преобразование двусторонних чередующихся конечных автоматов в односторонние недетерминированные автоматы. Конспект лекций по информатике. 8634. С. 291–302. Дои:10.1007/978-3-662-44522-8_25. ISBN  978-3-662-44521-1. ISSN  0302-9743.
15. Сакода, Уильям Дж .; Сипсер, Майкл (1978). Недетерминизм и размер двусторонних конечных автоматов. STOC 1978. ACM. С. 275–286. Дои:10.1145/800133.804357.
16. Берман, Петр; Лингас, Анджей (1977). О сложности регулярных языков в терминах конечных автоматов. Отчет 304. Польская академия наук.
17. Капуцис, Христос А. (2014). «Двусторонние автоматы против логарифмического пространства». Теория вычислительных систем. 55 (2): 421–447. Дои:10.1007 / s00224-013-9465-0.
18. Маслов, А. Н. (1970). «Оценки числа состояний конечных автоматов». Советская математика - Доклады. 11: 1373–1375.
19. Ю, Шэн; Чжуан, Цинъюй; Саломаа, Кай (1994). «Состояние сложности некоторых основных операций на регулярных языках». Теоретическая информатика. 125 (2): 315–328. Дои:10.1016 / 0304-3975 (92) 00011-Ф. ISSN  0304-3975.
20. Хольцер, Маркус; Кутриб, Мартин (2003). «Недетерминированная описательная сложность регулярных языков». Международный журнал основ информатики (Представлена ​​рукопись). 14 (6): 1087–1102. Дои:10.1142 / S0129054103002199. ISSN  0129-0541.
21. Йирасек, Йозеф; Йираскова, Галина; Шебей, Юрай (2016). Операции над однозначными конечными автоматами. Конспект лекций по информатике. 9840. С. 243–255. Дои:10.1007/978-3-662-53132-7_20. ISBN  978-3-662-53131-0. ISSN  0302-9743.
22. Йирасек, Йозеф Штефан; Йираскова, Галина; Сабари, Александр (2015). Компьютерные науки - теория и приложения. Конспект лекций по информатике. 9139. С. 231–261. Дои:10.1007/978-3-319-20297-6_16. ISBN  978-3-319-20296-9. ISSN  0302-9743.
23. Кунч, Михал; Охотин, Александр (2012). «Сложность состояний операций над двусторонними конечными автоматами над унарным алфавитом». Теоретическая информатика. 449: 106–118. Дои:10.1016 / j.tcs.2012.04.010. ISSN  0304-3975.
24. Кунч, Михал; Охотин, Александр (2011). "Сложность состояний объединения и пересечения для двусторонних недетерминированных конечных автоматов". Fundamenta Informaticae. 110 (1–4): 231–239. Дои:10.3233 / FI-2011-540.
25. Бирже, Жан-Камиль (1993). «Частичные порядки слов, минимальные элементы регулярных языков и сложность состояний». Теоретическая информатика. 119 (2): 267–291. Дои:10.1016 / 0304-3975 (93) 90160-У. ISSN  0304-3975.
26. Охотин, Александр (2012). «Однозначные конечные автоматы над унарным алфавитом». Информация и вычисления. 212: 15–36. Дои:10.1016 / j.ic.2012.01.003. ISSN  0890-5401.
27. Раскин, Михаил (2018). «Суперполиномиальная нижняя оценка размера недетерминированного дополнения однозначного автомата». Proc. ИКАЛП 2018. С. 138: 1–138: 11. Дои:10.4230 / LIPIcs.ICALP.2018.138.
28. Гефферт, Вильям; Мегетти, Карло; Пигиццини, Джованни (2007). «Дополняющие двусторонние конечные автоматы». Информация и вычисления. 205 (8): 1173–1187. Дои:10.1016 / j.ic.2007.01.008. ISSN  0890-5401.
29. Йираскова, Галина; Охотин, Александр (2008). О сложности состояний операций над двусторонними конечными автоматами. Конспект лекций по информатике. 5257. С. 443–454. Дои:10.1007/978-3-540-85780-8_35. ISBN  978-3-540-85779-2. ISSN  0302-9743.
30. Миркин, Борис Г. (1966). «О дуальных автоматах». Кибернетика. 2: 6–9. Дои:10.1007 / bf01072247.
31. Лейсс, Эрнст (1985). «Краткое представление регулярных языков логическими автоматами II». Теоретическая информатика. 38: 133–136. Дои:10.1016/0304-3975(85)90215-4. ISSN  0304-3975.
32. Чробак, Марек (1986). «Конечные автоматы и унарные языки». Теоретическая информатика. 47: 149–158. Дои:10.1016/0304-3975(86)90142-8. ISSN  0304-3975.
33. Кунч, Михал; Охотин, Александр (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.
34. Мегетти, Карло; Пигиццини, Джованни (2001). «Оптимальное моделирование между унарными автоматами». SIAM Журнал по вычислениям. 30 (6): 1976–1992. Дои:10.1137 / S009753979935431X. ISSN  0097-5397.
35. Гефферт, Вильям; Мегетти, Карло; Пигиццини, Джованни (2003). «Преобразование двусторонних недетерминированных унарных автоматов в более простые автоматы». Теоретическая информатика. 295 (1–3): 189–203. Дои:10.1016 / S0304-3975 (02) 00403-6. ISSN  0304-3975.
36. Хольцер, Маркус; Кутриб, Мартин (2009). «Недетерминированные конечные автоматы - последние результаты по описательной и вычислительной сложности». Международный журнал основ информатики. 20 (4): 563–580. Дои:10.1142 / S0129054109006747. ISSN  0129-0541.
37. Хольцер, Маркус; Кутриб, Мартин (2011). «Описание и вычислительная сложность конечных автоматов. Обзор». Информация и вычисления. 209 (3): 456–470. Дои:10.1016 / j.ic.2010.11.013. ISSN  0890-5401.
38. Гао, Юань; Морейра, Нельма; Рейс, Роджерио; Ю, Шэн (2015). «Обзор сложности эксплуатационного состояния». arXiv:1509.03254v1 [cs.FL ].