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

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 \mathrm{s}\mathrm{t}\mathrm{i}\mathrm{r}\mathrm{l}\mathrm{i}\mathrm{n}\mathrm{g}2(n,k)\cdot \mathrm{s}\mathrm{t}\mathrm{i}\mathrm{r}\mathrm{l}\mathrm{i}\mathrm{n}\mathrm{g}2(n+1,k)$ = $\mathrm{\Omega }\left(n^{2n+2}\mathrm{/}{e}^{2n}\right)$ states, where $\mathrm{s}\mathrm{t}\mathrm{i}\mathrm{r}\mathrm{l}\mathrm{i}\mathrm{n}\mathrm{g}2(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.