2024/12/09 by Semyon Petrov, Petrov, Semyon, Alexander Okhotin +1
Computer Science · Biochemistry, Genetics and Molecular Biology · #semigroups and automata theory #DNA and Biological Computing #Machine Learning and Algorithms
paper · pdf · doi:10.48550/arxiv.2412.06283
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 ∑k=1n (k - 1)! ⋅ k! ⋅ stirling2(n, k) ⋅ stirling2(n+1, k) = Ω( n2n+2 / e2n ) 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.