Article ID Journal Published Year Pages File Type
4950613 Information and Computation 2017 28 Pages PDF
Abstract
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+1 for intersection; at least Ω(mn)+2Ω(n)log⁡m and at most 2mm+1⋅2nn+1 for concatenation; at least 1n2n2−1 and at most 2O(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.
Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics
Authors
, ,