A lower bound on the state complexity of transforming two-way nondeterministic finite automata to unambiguous finite automata

Abstract

This paper establishes a lower bound on the number of states necessary in the worst case to simulate an $n$-state two-way nondeterministic finite automaton (2NFA) by a one-way unambiguous finite automaton (UFA). It is proved that for every $n$, there is a language recognized by an $n$-state 2NFA that requires a UFA with at least ${\sum }_{k=1}^n(k-1)!\cdot k!\cdot stirling2(n,k)\cdot stirling2(n+1,k)$ = $\hat{I}\text{c◯}(n^{2n+2}/e^{2n})$ states, where $stirling2(n,k)$ denotes Stirling's numbers of the second kind. This result is proved by estimating the rank of a certain matrix, which is constructed for the universal language for $n$-state 2NFAs, and describes every possible behaviour of these automata during their computation.

31 pages, 7 figures