State complexity of operations on two-way deterministic finite automata over a unary alphabet

Logo poskytovatele

Varování

Publikace nespadá pod Ekonomicko-správní fakultu, ale pod Přírodovědeckou fakultu. Oficiální stránka publikace je na webu muni.cz.
Název česky Stavová složitost operací na dvoucestných deterministických konečných automatech nad unární abecedou
Autoři

KUNC Michal OKHOTIN Alexander

Rok publikování 2011
Druh Článek ve sborníku
Konference Descriptional Complexity of Formal Systems: 13th International Workshop, DCFS 2011, Gießen/Limburg, Germany, July 25-27, 2011. Proceedings
Fakulta / Pracoviště MU

Přírodovědecká fakulta

Citace
Doi http://dx.doi.org/10.1007/978-3-642-22600-7_18
Obor Obecná matematika
Klíčová slova finite automata; two-way automata; state complexity
Popis V článku je určen počet stavů v dvoucestném deterministickém konečném automatu (2DFA) nad jednopísmennou abecedou dostatečný a v nejhorším případě nutný k reprezentování výsledků následujících operací: (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(n) = e^(sqrt(n.ln(n))(1 + o(1))) je největší hodnota lcm(p1,...,pk) pro p1 +...+ pk <= n, známá jako Landauova funkce; (iv) k-tá mocnina 2DFA o n stavech mezi (k - 1)g(n) - k a k.(g(n) + n) stavy; (v) zřetězení 2DFA o m stavech a o n stavech e^((1 + o(1)).sqrt((m + n).ln(m + n))) stavů.
Související projekty:

Používáte starou verzi internetového prohlížeče. Doporučujeme aktualizovat Váš prohlížeč na nejnovější verzi.