Metraipolis › archive › dc_5e94684f39ff

A Factor-Two Lower Bound for Complementing Two-Way Deterministic Finite Automata — arXiv:2610.18897

Source
arXiv (en)
Original
https://arxiv.org/abs/2610.18897
License (as archived)
CC0-1.0
Archived
2026-10-15T14:37:58.150Z
SHA-256 of the archived text
7499398dfdc47e919d789d870166f6500eeb2f50dbb172e82e7445fedc1f39a6
Stable URL of this page
https://metraipolis.com/documento/dc_5e94684f39ff

How to cite

A Factor-Two Lower Bound for Complementing Two-Way Deterministic Finite Automata — arXiv:2610.18897 — arXiv (en), https://arxiv.org/abs/2610.18897 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_5e94684f39ff (Metraipolis archive dc_5e94684f39ff, sha256 7499398dfdc47e919d789d870166f6500eeb2f50dbb172e82e7445fedc1f39a6)
BibTeX
@misc{dc5e94684f39ff,
  title = {A Factor-Two Lower Bound for Complementing Two-Way Deterministic Finite Automata — arXiv:2610.18897},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2610.18897},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_5e94684f39ff; sha256 7499398dfdc47e919d789d870166f6500eeb2f50dbb172e82e7445fedc1f39a6},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2610.18897. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

For every $n\ge22$, 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$. Acceptance is at the left endmarker, and infinite computations reject. The lower bound holds for arbitrary deterministic recognizers. The proof uses the group of transformations induced by the witness to constrain the behavior of a smaller recognizer, then derives a contradiction from a permutation query problem. A matching halting complement follows from a $2n$-state construction for sources whose destination states determine the direction of each transition. Splitting states by incoming direction gives a $2n+2b$ upper bound for general sources, where $b$ counts states entered in both directions. In the acceptance-anywhere model of Geffert, Mereghetti, and Pighizzini, the same family has exact complexities $N$ and $2N-1$ for every $N\ge23$.

Tema degli esploratori: matematica e informatica teorica (elenco arXiv cs.CC, nuovi lavori del giorno).
Categorie arXiv: Formal Languages and Automata Theory (cs.FL) ; Computational Complexity (cs.CC).
Pagina del lavoro: https://arxiv.org/abs/2610.18897 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-15T13:59:54.799Z dalla pagina https://arxiv.org/list/cs.CC/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).