A4 Refereed article in a conference publication
One-way simulation of two-way finite automata over small alphabets
Authors: Viliam Geffert, Alexander Okhotin
Editors: S Bensch, F Drewes, R Freund, F Otto
Publication year: 2013
Book title : Fifth Worskshop on Non-Classical Models of Automata and Applications (NCMA 2013)
Series title: books@ocg.at
First page : 151
Last page: 162
ISBN: 978-3-85403-294-6
Abstract
It is shown that a two-way deterministic finite automaton (2DFA) with $n$ states over an alphabet $\Sigma$ can be transformed to an equivalent one-way nondeterministic finite automaton (1NFA) with $|\Sigma| \cdot \binom{n}{\lfloor n/2 \rfloor} \sim |\Sigma| \sqrt{\frac{2}{\pi n}} 2^n$ states. For small input alphabets---that is, for a fixed alphabet or for a subexponentially growing one---this simulation is more efficient than the one discovered by Kapoutsis (2005), which produces $\binom{2n}{n+1} \sim \frac{1}{\sqrt{\pi n}} 4^n$ states, irrespective of the alphabet. A close lower bound of $\binom{n-2}{\lfloor n/2 \rfloor - 1}$ %this is less than the correct value states is proved for a two-symbol alphabet.
It is shown that a two-way deterministic finite automaton (2DFA) with $n$ states over an alphabet $\Sigma$ can be transformed to an equivalent one-way nondeterministic finite automaton (1NFA) with $|\Sigma| \cdot \binom{n}{\lfloor n/2 \rfloor} \sim |\Sigma| \sqrt{\frac{2}{\pi n}} 2^n$ states. For small input alphabets---that is, for a fixed alphabet or for a subexponentially growing one---this simulation is more efficient than the one discovered by Kapoutsis (2005), which produces $\binom{2n}{n+1} \sim \frac{1}{\sqrt{\pi n}} 4^n$ states, irrespective of the alphabet. A close lower bound of $\binom{n-2}{\lfloor n/2 \rfloor - 1}$ %this is less than the correct value states is proved for a two-symbol alphabet.
UTU Research Portal