A Factor-Two Lower Bound for Complementing Two-Way Deterministic Finite Automata

Sudais Arif

For every $n\ge 22$, we construct a language over a fixed three-letter alphabet whose two-way deterministic state complexity is $n$ and whose complement has state complexity $2n$. A…