On the state complexity of operations on two-way finite automata

The paper investigates the effect of basic language-theoretic operations on the number of states in two-way deterministic finite automata (2DFAs). If m and n are the number of states in the 2DFAs recognizing the arguments of the following operations, then their result requires the following number of states: at least m + n - o(m + n) and at most 4m + n + const for union; at least m + n - o(m + n) and at most m + n + I for intersection; at least Omega(m/n) + 2(Omega(n))/log m and at most 2m(m+1). 2(nn+1) for concatenation; at least 1/n2(n/2-1) and at most 2(o(nn+1)) for Kleene star, square and projections; between n + 1 and n + 2 for reversal; exactly 2n for inverse homomorphisms. All results are obtained by first establishing high lower bounds on the number of states in any 1DFAs recognizing these languages, and then using these bounds to reason about the size of any equivalent 2DFAs. (C) 2016 Elsevier Inc. All rights reserved.