A4 Vertaisarvioitu artikkeli konferenssijulkaisussa
One-way simulation of two-way finite automata over small alphabets
Tekijät: Viliam Geffert, Alexander Okhotin
Toimittaja: S Bensch, F Drewes, R Freund, F Otto
Julkaisuvuosi: 2013
Kokoomateoksen nimi: Fifth Worskshop on Non-Classical Models of Automata and Applications (NCMA 2013)
Sarjan nimi: books@ocg.at
Aloitussivu: 151
Lopetussivu: 162
ISBN: 978-3-85403-294-6
Tiivistelmä
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.
Turun yliopiston Tutkimustietojärjestelmän portaali