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

This contribution discusses the deterministic state complexity of the basic language-theoretic operations on deterministic two-way finite automata. The deterministic state complexity of a language~\(L\) is the least number of states required by such an automaton to recognize \(L\). The basic language-theoretic operations discussed include union, intersection, concatenation, Kleene star, square, projections, reversal, and inverse homomorphism. The state complexity of an operation describes the dependence of the (worst-case) state complexity of the resulting languages in terms of the state complexities of the input languages. Finally, a deterministic two-way automaton is a deterministic Turing machine that cannot modify the tape contents. In other words, it is a finite-state device that processes the input deterministically by moving forward and backward on the tape that contains the input. However, it can only read the tape; information can only be stored in its finitely many states. In detail, this contribution establishes the following state complexities. Suppose that the input languages have state complexity \(m\)~and~\(n\). Then their union has state complexity between \(m + n - o(m+n)\)~and~\(4m + n + c\) for a constant \(c\), their intersection has state complexity between \(m+n-o(m+n)\)~and~\(m+n+1\), their concatenation has state complexity between \(\Omega(\tfrac mn) + \tfrac{2^{\Omega(n)}}{\log m}\)~and~\(2m^{m+1} \cdot 2^{n^{n+1}}\). For Kleene star, square, and projections a state complexity between \(\tfrac 1n2^{\tfrac n2-1}\)~and~\(2^{O(n^{n+1})}\) is reported as well as the rather sharp bounds \(n+1\)~and~\(n+2\) for reversal, and the exact bound~\(2n\) for inverse homomorphism. In all these cases good lower bounds on the size of a deterministic finite automaton are first developed, for which there are established methods. These bounds are then translated by means of the known conversion constructions between deterministic two-way finite automata and deterministic finite automata. Overall, the paper is well written and easily accessible to anyone with some background in automata theory. Knowledge of the approaches classically used to establish state complexities for deterministic finite automata is helpful but not essential. Illustrations and explanations are generously provided and all proofs offer sufficient detail to easily check their validity.