The number of states in two-way deterministic finite automata (2DFAs) is considered. It is shown that the state complexity of basic operations is: at least m + n - o(m + n) and at most Am + n + 1 for union; at least m + n - o(m + n) and at most m + n+1 for intersection; at least n and at most 4n for complementation; at least Ω(m) + 2~(Ω(n)/log m) and at most 2m~(m+1) · 2~(n~(n+1)) for concatenation; at least 1 2~(n/2-1) and at most 2~(O(n~(n+1))) for both star and square; between n and n + 2 for reversal; exactly 2n for inverse homomorphism. In each case m and n denote the number of states in 2DFAs for the arguments.
展开▼
