State complexity of operations on two-way finite automata over a unary alphabet
| Název česky | Stavová složitost operací na dvoucestných konečných automatech nad unární abecedou |
|---|---|
| Autoři | |
| Rok publikování | 2012 |
| Druh | Článek v odborném periodiku |
| Časopis / Zdroj | Theoretical Computer Science |
| Fakulta / Pracoviště MU | |
| Citace | |
| Doi | http://dx.doi.org/10.1016/j.tcs.2012.04.010 |
| Obor | Obecná matematika |
| Klíčová slova | Finite automata; Two-way automata; Regular languages; Unary languages; State complexity; Landau's function |
| Popis | Článek určuje počet stavů dvoucestných deterministických konečných automatů (2DFA) nad jednopísmennou abecedou dostatečný a v nejhorším případě nutný pro reprezentování výsledků základních operací s formálními jazyky zadanými pomocí 2DFA s jistým počtem stavů. Je dokázáno, že (i) průnik 2DFA o m stavech a 2DFA o n stavech vyžaduje mezi m+n a m+n+1 stavy; (ii) sjednocení 2DFA o m stavech a 2DFA o n stavech mezi m+n a 2m+n+4 stavy; (iii) Kleeneho hvězdička 2DFA o n stavech (g(n)+O(n))^2 stavů, kde g je Landauova funkce; (iv) k-tá mocnina n-stavového 2DFA mezi (k-1)g(n)-k a k(g(n)+n) stavy; (v) zřetězení 2DFA o m stavech a 2DFA o n stavech exp((1+O(1))sqrt((m+n)ln(m+n))) stavů. Navíc je dokázáno, že Kleeneho hvězdička dvoucestného nedeterministického automatu (2NFA) o n stavech vyžaduje v nejhorším případě Theta(g(n)) stavů, jeho k-tá mocnina vyžaduje (k g(n))^(Theta(1)) stavů a zřetězení 2NFA o m stavech a 2NFA o n stavech exp(Theta(sqrt((m+n)ln(m+n)))) stavů. |
| Související projekty: |