An Exact Factor-Two Witness for Two-Way Deterministic Complementation
This preprint establishes an unconditional lower bound for complementing two-way deterministic finite automata. For every n ≥ 22, it constructs a language K_n over a fixed three-letter alphabet whose source state complexity is exactly n and whose complement state complexity is exactly 2n. These exact counts use accepta...