WikiDer > Сложность состояния - Википедия

State complexity - Wikipedia

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

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

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

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

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

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

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

Нерешенная проблема в информатике:

Каждый

{ displaystyle n}

-состояние 2NFA имеет эквивалент

{ displaystyle operatorname {poly} (n)}

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

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

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

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

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

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

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

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

Союз

Если язык ${ displaystyle L_ {1}}$ требует m состояний и языка ${ displaystyle L_ {2}}$ требуется n состояний, сколько состояний ${ displaystyle L_ {1} чашка 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 ^ {п}}$ состояния, см. Биргет.^[25]
УФА: минимум ${ Displaystyle п ^ {2-о (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 м cdot 2 ^ {п} -2 ^ {п-1}}$ заявляет, см. Маслов ^[18] и Ю, Чжуан и Саломаа.^[19]
NFA: ${ displaystyle m + n}$ состояния, см. Хольцер и Кутриб.^[20]
УФА: ${ displaystyle { frac {3} {4}} 2 ^ {m + n} -1}$ говорится, что см. Йирасек, Йираскова и Шебей.^[21]
SVFA: ${ Displaystyle Theta (3 ^ {п / 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 ^ {О (п ^ {п + 1})}}$ заявляет, см. Жираскова и Охотин.^[29]

Разворот

DFA: ${ Displaystyle 2 ^ {п}}$ заявляет, см. Миркин,^[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 г (п) = е ^ { Тета ({ sqrt {п пер п}})}}$ быть Функция Ландау.

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

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

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