An Exact Factor-Two Witness for Two-Way Deterministic Complementation

Abstract

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 acceptance at the designated final state on the left endmarker; every state is counted, and infinite computations reject. The lower bounds apply to arbitrary deterministic recognizers in this model. Under the acceptance-anywhere convention of Geffert, Mereghetti, and Pighizzini, the same family has exact source complexity N and complement complexity 2N − 1 for every N ≥ 23, with N = n + 1. This establishes a complementation gap in the convention of their 2007 open problem. The proof combines two independent transformation systems, interval diagrams, small actions of a product of alternating groups, and a permutation-query obstruction. The paper provides complete transition prescriptions, a matching halting complement for direction-determinate sources, and a 2n + 2b upper bound for arbitrary sources, where b counts states entered in both directions. LaTeX sources and finite verification programs are available in the linked GitHub repository. The finite checks corroborate the constructions; the lower bounds rest on the mathematical proofs. This deposit contains the preprint PDF and LaTeX source archive for version 1.0.0.