Deterministic One-Way Simulation of Two-Way Deterministic Finite Automata Over Small Alphabets

It is shown that a two-way deterministic finite automaton (2DFA) with Formula: see text states over an alphabet Formula: see text can be transformed to an equivalent one-way automaton (1DFA) with Formula: see text states, where Formula: see text. This reflects the fact that, by keeping the last processed symbol Formula: see text in memory, the simulating 1DFA can remember one of Formula: see text states in which the automaton moves by Formula: see text to the right, and a function that maps Formula: see text states moving to the left to Formula: see text states moving to the right; cf. ca. Formula: see text functions in the classical construction. A close lower bound of Formula: see text states is established using a 2-symbol alphabet, with witness languages defined by direction-determinate 2DFA. The same lower bound is also achieved with witness languages defined by sweeping 2DFA, at the expense of using a 5-symbol alphabet. In addition, the complexity of transforming a sweeping or a direction-determinate 2DFA to a 1DFA is shown to be exactly Formula: see text.