Složitost státu - State complexity - Wikipedia

Složitost státu je oblast teoretická informatika zabývající se velikostí abstraktních automatů, jako jsou různé druhy konečné automaty Klasickým výsledkem v této oblasti je simulace ${ displaystyle n}$-Státnedeterministické konečný automat podle a deterministický konečný automat vyžaduje přesně ${ displaystyle 2 ^ {n}}$ státy v nejhorším případě.

Transformace mezi variantami konečných automatů

Konečné automaty mohou býtdeterministický anedeterministické, jednosměrné (DFA, NFA) a obousměrný (2DFA, 2NFA). Další související třídy jsoujednoznačný (UFA),sebeověřování (SVFA) a střídavý (AFA) konečné automaty. Tyto automaty mohou být také obousměrné (2UFA, 2SVFA, 2AFA).

Všechny tyto stroje mohou přesně přijímat běžné jazyky Velikost různých typů automatů nezbytných k přijetí stejného jazyka (měřeno počtem jejich stavů) se však může lišit. U jakýchkoli dvou typů konečných automatů lze kompromis stavu státu mezi nimi je celočíselná funkce ${ displaystyle f}$kde ${ displaystyle f (n)}$ je nejmenší počet stavů v automatech druhého typu dostačující k rozpoznání každého jazyka rozpoznaného znakem ${ displaystyle n}$-státní automat prvního typu. Jsou známy následující výsledky.

• NFA až DFA: ${ displaystyle 2 ^ {n}}$ státy. To je konstrukce podmnožiny podle Rabine a Scott,^[1] se ukázalo jako optimální Lupanov.^[2]

• UFA až DFA: ${ displaystyle 2 ^ {n}}$ státy, viz Leung,^[3] Dřívější spodní hranice Schmidt^[4] byl menší.
• NFA až UFA: ${ displaystyle 2 ^ {n} -1}$ státy, viz Leung.^[3] Schmidt měl dřívější menší dolní hranici.^[4]
• SVFA až DFA: ${ displaystyle Theta (3 ^ {n / 3})}$ státy, viz Jirásková a Pighizzini^[5]
• 2DFA až DFA: ${ displaystyle n (n ^ {n} - (n-1) ^ {n})}$ státy, viz Kapoutsis.^[6] Dřívější výstavba od Shepherdson^[7] použil více států a dřívější dolní mez Moora^[8] byl menší.
• 2DFA až NFA: ${ displaystyle { binom {2n} {n + 1}} = O ({ frac {4 ^ {n}} { sqrt {n}}})}$, viz Kapoutsis.^[6] Dřívější výstavba od Birget ^[9] používá více států.
• 2 NFA až NFA: ${ displaystyle { binom {2n} {n + 1}}}$, viz Kapoutsis.^[6]
  • 2 NFA až NFA přijímající doplněk: ${ displaystyle O (4 ^ {n})}$ státy, viz Vardi.^[10]
• AFA až DFA: ${ displaystyle 2 ^ {2 ^ {n}}}$ státy, viz Chandra, Kozen a Stockmeyer.^[11]
• AFA až NFA: ${ displaystyle 2 ^ {n}}$ státy, viz Fellah, Jürgensen a Yu.^[12]
• 2 AFA až DFA: ${ displaystyle 2 ^ {n2 ^ {n}}}$viz Ladner, Lipton a Stockmeyer.^[13]
• 2 AFA až NFA: ${ displaystyle 2 ^ { Theta (n log n)}}$viz Geffert a Okhotin.^[14]

Problém 2DFA vs. 2NFA a logaritmický prostor

Nevyřešený problém v informatice: Má každý ${ displaystyle n}$-state 2NFA mají ekvivalent ${ displaystyle operatorname {poly} (n)}$-state 2DFA? (více nevyřešených problémů v informatice)

Je otevřeným problémem, zda lze všechny 2NFA převést na 2DFA s polynomiálně mnoha stavy, tj. Zda existuje polynom ${ displaystyle p (n)}$tak, že pro každého ${ displaystyle n}$-state 2NFA existuje ${ displaystyle p (n)}$-state 2DFA. Problém nastolili Sakoda a Sipser,^[15]kdo to porovnal s P vs. NP problém v teorie výpočetní složitosti.Berman a Lingas^[16] objevil formální vztah mezi tímto problémem a L vs. NL otevřený problém. Tento vztah dále rozvinul Kapoutsis.^[17]

Stavová složitost operací pro konečné automaty

Vzhledem k operaci zachování binární pravidelnosti v jazycích ${ displaystyle circ}$a rodina automatů X (DFA, NFA atd.), stavová složitost ${ displaystyle circ}$je celočíselná funkce ${ displaystyle f (m, n)}$ takhle

• pro každý m-stavový X-automat A a n-stavový X-automat B existuje ${ displaystyle f (m, n)}$-státní X-automat pro ${ displaystyle L (A) cirkus L (B)}$, a
• pro všechna celá čísla m, n existuje m-stavový X-automat A a n-stavový X-automat B takový, že každý X-automat pro ${ displaystyle L (A) cirkus L (B)}$ musí mít alespoň ${ displaystyle f (m, n)}$ státy.

Analogická definice platí pro operace s libovolným počtem argumentů.

První výsledky o stavové složitosti operací pro DFA zveřejnil Maslov^[18]a Yu, Zhuang a Salomaa.^[19]Holzer a Kutrib^[20]propagoval stavovou složitost operací na NFA. Známé výsledky pro základní operace jsou uvedeny níže.

svaz

Pokud jazyk ${ displaystyle L_ {1}}$ vyžaduje více států a jazyk ${ displaystyle L_ {2}}$ vyžaduje n států, kolik států ${ displaystyle L_ {1} pohár L_ {2}}$ vyžaduje?

• DFA: ${ displaystyle mn}$ státy, viz Maslov^[18] a Yu, Zhuang a Salomaa.^[19]
• NFA: ${ displaystyle m + n + 1}$ státy, viz Holzer a Kutrib.^[20]
• UFA: mezi ${ displaystyle mn + m + n}$ a ${ displaystyle O (n2 ^ {0,79 m})}$ státy, viz Jirásek, Jirásková a Šebej.^[21]
• SVFA: ${ displaystyle mn}$ státy, viz Jirásek, Jirásková a Szabari.^[22]
• 2DFA: mezi ${ displaystyle m + n}$ a ${ displaystyle 4m + n + 4}$ státy, viz Kunc a Okhotin.^[23]
• 2NFA: ${ displaystyle m + n}$ státy, viz Kunc a Okhotin.^[24]

Průsečík

Kolik států ${ displaystyle L_ {1} čepice L_ {2}}$ vyžaduje?

• DFA: ${ displaystyle mn}$ státy, viz Maslov^[18] a Yu, Zhuang a Salomaa.^[19]
• NFA: ${ displaystyle mn}$ státy, viz Holzer a Kutrib.^[20]
• UFA: ${ displaystyle mn}$ státy, viz Jirásek, Jirásková a Šebej.^[21]
• SVFA: ${ displaystyle mn}$ státy, viz Jirásek, Jirásková a Szabari.^[22]
• 2DFA: mezi ${ displaystyle m + n}$ a ${ displaystyle m + n + 1}$ státy, viz Kunc a Okhotin.^[23]
• 2NFA: mezi ${ displaystyle m + n}$ a ${ displaystyle m + n + 1}$ státy, viz Kunc a Okhotin.^[24]

Doplnění

Pokud jazyk L vyžaduje n statest, kolik uvádí jeho doplněk vyžaduje?

• DFA: ${ displaystyle n}$ státy, výměnou přijímajících a odmítajících států.
• NFA: ${ displaystyle 2 ^ {n}}$ státy, viz Birget.^[25]
• UFA: alespoň ${ displaystyle n ^ {2-o (1)}}$ a nanejvýš ${ displaystyle O (2 ^ {0,79n})}$ státy, viz Okhotin^[26] pro dolní hranici a Jirásek, Jirásková a Šebej^[21] pro horní hranici. Raskin^[27] nedávno se ukázal jako superpolynomiální dolní mez.
• SVFA: ${ displaystyle n}$ státy, výměnou přijímajících a odmítajících států.
• 2DFA: alespoň ${ displaystyle n}$ a nanejvýš ${ displaystyle 4n}$ státy, viz Geffert, Mereghetti a Pighizzini.^[28]

Zřetězení

Kolik států ${ displaystyle L_ {1} L_ {2} = {w_ {1} w_ {2} střední w_ {1} v L_ {1}, w_ {2} v L_ {2} }}$ vyžaduje?

• DFA: ${ displaystyle m cdot 2 ^ {n} -2 ^ {n-1}}$ státy, viz Maslov ^[18] a Yu, Zhuang a Salomaa.^[19]
• NFA: ${ displaystyle m + n}$ státy, viz Holzer a Kutrib.^[20]
• UFA: ${ displaystyle { frac {3} {4}} 2 ^ {m + n} -1}$ státy, viz Jirásek, Jirásková a Šebej.^[21]
• SVFA: ${ displaystyle Theta (3 ^ {n / 3} 2 ^ {m})}$ státy, viz Jirásek, Jirásková a Szabari.^[22]
• 2DFA: alespoň ${ displaystyle { frac {2 ^ { Omega (n)}} { log m}}}$ a nanejvýš ${ displaystyle 2m ^ {m + 1} cdot 2 ^ {n ^ {n + 1}}}$ státy, viz Jirásková a Okhotin.^[29]

Kleene hvězda

• DFA: ${ displaystyle { frac {3} {4}} 2 ^ {n}}$ státy, viz Maslov^[18] a Yu, Zhuang a Salomaa.^[19]
• NFA: ${ displaystyle n + 1}$ státy, viz Holzer a Kutrib.^[20]
• UFA: ${ displaystyle { frac {3} {4}} 2 ^ {n}}$ státy, viz Jirásek, Jirásková a Šebej.^[21]
• SVFA: ${ displaystyle { frac {3} {4}} 2 ^ {n}}$ státy, viz Jirásek, Jirásková a Szabari.^[22]
• 2DFA: alespoň ${ displaystyle { frac {1} {n}} 2 ^ {{ frac {n} {2}} - 1}}$ a nanejvýš ${ displaystyle 2 ^ {O (n ^ {n + 1})}}$ státy, viz Jirásková a Okhotin.^[29]

Obrácení

• DFA: ${ displaystyle 2 ^ {n}}$ státy, viz Mirkin,^[30] Leiss,^[31] a Yu, Zhuang a Salomaa.^[19]
• NFA: ${ displaystyle n + 1}$ státy, viz Holzer a Kutrib.^[20]
• UFA: ${ displaystyle n}$ státy.
• SVFA: ${ displaystyle 2n + 1}$ státy, viz Jirásek, Jirásková a Szabari.^[22]
• 2DFA: mezi ${ displaystyle n + 1}$ a ${ displaystyle n + 2}$ státy, viz Jirásková a Okhotin.^[29]

Konečné automaty přes unární abecedu

Stavová složitost konečných automatů s jedním písmenem (unární) abeceda, průkopníkem Chrobak,^[32] se liší od vícepísmenných písmen.

Nechat ${ displaystyle g (n) = e ^ { Theta ({ sqrt {n ln n}})}}$ být Landauova funkce.

Transformace mezi modely

U jednopísmenné abecedy jsou transformace mezi různými typy konečných automatů někdy efektivnější než v obecném případě.

• NFA až DFA: ${ displaystyle g (n) + O (n ^ {2})}$ státy, viz Chrobak.^[32]
• 2DFA až DFA: ${ displaystyle g (n) + O (n)}$ státy, viz Chrobak^[32] a Kunc a Okhotin.^[33]
• 2 NFA až DFA: ${ displaystyle O (g (n))}$ státy, viz Mereghetti a Pighizzini.^[34] a Geffert, Mereghetti a Pighizzini.^[35]
• NFA až 2DFA: maximálně ${ displaystyle O (n ^ {2})}$ státy, viz Chrobak.^[32]
• 2NFA až 2DFA: maximálně ${ displaystyle n ^ {O ( log n)}}$ státy, prokázáno zavedením metody Savitchova věta, viz Geffert, Mereghetti a Pighizzini.^[35]
• UFA až DFA: ${ displaystyle e ^ { Theta ({ sqrt [{3}] {n ( ln n) ^ {2}}})}}$, viz Okhotin.^[26]
• NFA až UFA: ${ displaystyle g (n) + O (n ^ {2})}$, viz Okhotin.^[26]

svaz

• DFA: ${ displaystyle mn}$ státy, viz Yu, Zhuang a Salomaa.^[19]
• NFA: ${ displaystyle m + n + 1}$ státy, viz Holzer a Kutrib.^[20]
• 2DFA: mezi ${ displaystyle m + n}$ a ${ displaystyle 2m + n + 4}$ státy, viz Kunc a Okhotin.^[23]
• 2NFA: ${ displaystyle m + n}$ státy, viz Kunc a Okhotin.^[24]

Průsečík

• DFA: ${ displaystyle mn}$ státy, viz Yu, Zhuang a Salomaa.^[19]
• NFA: ${ displaystyle mn}$ státy, viz Holzer a Kutrib.^[20]
• 2DFA: mezi ${ displaystyle m + n}$ a ${ displaystyle m + n + 1}$ státy, viz Kunc a Okhotin.^[23]
• 2NFA: mezi ${ displaystyle m + n}$ a ${ displaystyle m + n + 1}$ státy, viz Kunc a Okhotin.^[24]

Doplnění

• DFA: ${ displaystyle n}$ státy.
• NFA: ${ displaystyle g (n) + O (n ^ {2})}$ státy, Holzer a Kutrib.^[20]
• UFA: alespoň ${ displaystyle n ^ {2-o (1)}}$ a nanejvýš ${ displaystyle e ^ { Theta ({ sqrt [{3}] {n ( ln n) ^ {2}}})}}$ státy, viz Okhotin.^[26]
• 2DFA: alespoň ${ displaystyle n}$ a nanejvýš ${ displaystyle 2n + 3}$ státy, viz Kunc a Okhotin.^[23]
• 2NFA: minimálně ${ displaystyle n}$ a nanejvýš ${ displaystyle O (n ^ {8})}$ státy. Horní hranice je implementací metody Immerman – Szelepcsényiho věta, viz Geffert, Mereghetti a Pighizzini.^[28]

Zřetězení

• DFA: ${ displaystyle mn}$ státy, viz Yu, Zhuang a Salomaa.^[19]
• NFA: mezi ${ displaystyle m + n-1}$ a ${ displaystyle m + n}$ státy, viz Holzer a Kutrib.^[20]
• 2DFA:${ displaystyle e ^ { Theta ({ sqrt {(m + n) log (m + n)}})}}$ státy, viz Kunc a Okhotin.^[23]
• 2NFA:${ displaystyle e ^ { Theta ({ sqrt {(m + n) log (m + n)}})}}$ státy, viz Kunc a Okhotin.^[23]

Kleene hvězda

• DFA: ${ displaystyle (n-1) ^ {2} +1}$ státy, viz Yu, Zhuang a Salomaa.^[19]
• NFA: ${ displaystyle n + 1}$ státy, viz Holzer a Kutrib.^[20]
• UFA: ${ displaystyle (n-1) ^ {2} +1}$ státy, viz Okhotin.^[26]
• 2DFA:${ displaystyle Theta ((g (n)) ^ {2})}$ státy, viz Kunc a Okhotin.^[23]
• 2NFA:${ displaystyle Theta (g (n))}$ státy, viz Kunc a Okhotin.^[23]

Další čtení

Průzkumy státní složitosti sepsali Holzer a Kutrib^[36][37]a Gao et al.^[38]

Nový výzkum složitosti státu je běžně prezentován na výročních seminářích dnePopisná složitost formálních systémů (DCFS), na Konference o implementaci a aplikaci automatů (CIAA) a na různých konferencích dne teoretická informatika obecně.

Reference