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

Investor logo

Warning

This publication doesn't include Faculty of Economics and Administration. It includes Faculty of Science. Official publication website can be found on muni.cz.
Authors

KUNC Michal OKHOTIN Alexander

Year of publication 2011
Type Article in Proceedings
Conference Descriptional Complexity of Formal Systems: 13th International Workshop, DCFS 2011, Gießen/Limburg, Germany, July 25-27, 2011. Proceedings
MU Faculty or unit

Faculty of Science

Citation
Doi http://dx.doi.org/10.1007/978-3-642-22600-7_18
Field General mathematics
Keywords finite automata; two-way automata; state complexity
Description The paper determines the number of states in a two-way deterministic finite automaton (2DFA) over a one-letter alphabet sufficient and in the worst case necessary to represent the results of the following operations: (i) intersection of an m-state 2DFA and an n-state 2DFA requires between m + n and m + n + 1 states; (ii) union of an m-state 2DFA and an n-state 2DFA, between m + n and 2m + n + 4 states; (iii) Kleene star of an n-state 2DFA, (g(n) + O(n))^2 states, where g(n) = e^(sqrt(n.ln(n))(1 + o(1))) is the maximum value of lcm(p1,...,pk) for p1 +...+ pk <= n, known as Landau’s function; (iv) k-th power of an n-state 2DFA, between (k - 1)g(n) - k and k.(g(n) + n) states; (v) concatenation of an m-state and an n-state 2DFAs, e^((1 + o(1)).sqrt((m + n).ln(m + n))) states.
Related projects:

You are running an old browser version. We recommend updating your browser to its latest version.