2DFA that requires many states in equivalent DFA? Is there a 2DFA with $n$ states (where $n$ is nontrivial, say at least 4) that requires at least $2^n$ states to simulate using any DFA?


A two-way DFA (2DFA) is a deterministic finite-state automaton that is allowed to move back and forth on its read-only input tape, unlike finite-state automata that may only move the input head in one direction.

It is well-known that 2DFAs recognize precisely the same class of languages as DFAs, in other words the regular languages.  Less well-understood is the question of how efficient the simulation is.  The original constructions from the late 1950s by Rabin/Scott and Shepherdson used a notion of crossing sequences and are quite hard to analyse.  Moshe Vardi published another construction that shows an upper bound of $2^{O(n^2)}$ states, but this bound may have some slack.

I am asking whether any (families of) 2DFAs are known that require many states in any DFA simulating them, even after Myhill-Nerode minimization of the DFA.  Moreover, would there be any interesting consequences of knowing such 2DFAs?


Moshe Y. Vardi, A Note on the Reduction of Two-Way Automata to One-Way Automata, IPL 30 261–264, 1989.  doi:10.1016/0020-0190(89)90205-6 (preprint)
The tight bound is $ n(n^n -(n-1)^n) $, which was given in Removing Bidirectionality from Nondeterministic Finite Automata by Christos Kapoutsis (2005).

I am also putting a figure from this paper giving a clear picture:


To get more, I think this paper is a good starting point. To check the related recent developments, I can also recommend to check the papers listed here: dblp: Christos A. Kapoutsis.