State complexity of operations on two-way 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 2012
Type Article in Periodical
Magazine / Source Theoretical Computer Science
MU Faculty or unit

Faculty of Science

Citation
Doi http://dx.doi.org/10.1016/j.tcs.2012.04.010
Field General mathematics
Keywords Finite automata; Two-way automata; Regular languages; Unary languages; State complexity; Landau's function
Description The paper determines the number of states in two-way deterministic finite automata (2DFA) over a one-letter alphabet sufficient and in the worst case necessary to represent the results of basic language-theoretic operations on 2DFAs with a certain number of states. It is proved that (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 is 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 2DFA and an n-state 2DFA, exp((1+O(1))sqrt((m+n)ln(m+n))) states. It is furthermore demonstrated that the Kleene star of a two-way nondeterministic automaton (2NFA) with n states requires Theta(g(n)) states in the worst case, its k-th power requires (k g(n))^(Theta(1)) states, and the concatenation of an m-state 2NFA and an n-state 2NFA, exp(Theta(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.