Metraipolis › archive › dc_48ff7b5dad66
From Ramsey-Based to Congruence-Based Constructions for Büchi Complementation — arXiv:2609.06210
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2609.06210
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-16T15:39:59.934Z
- SHA-256 of the archived text
789e3c8d010033d0814b93477bee42299432ca2186136745d4df4df92c6b96c5- Stable URL of this page
https://metraipolis.com/documento/dc_48ff7b5dad66
How to cite
From Ramsey-Based to Congruence-Based Constructions for Büchi Complementation — arXiv:2609.06210 — arXiv (en), https://arxiv.org/abs/2609.06210 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_48ff7b5dad66 (Metraipolis archive dc_48ff7b5dad66, sha256 789e3c8d010033d0814b93477bee42299432ca2186136745d4df4df92c6b96c5)
BibTeX
@misc{dc48ff7b5dad66,
title = {From Ramsey-Based to Congruence-Based Constructions for Büchi Complementation — arXiv:2609.06210},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2609.06210},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_48ff7b5dad66; sha256 789e3c8d010033d0814b93477bee42299432ca2186136745d4df4df92c6b96c5},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.06210. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
The very first construction by J. Richard Büchi himself for complementing a Büchi automaton relies on a fundamental lemma about the division of an arbitrary infinite word into consecutive finite words, which was cleanly proven by invoking a specialized theorem of Ramsey. For that reason, constructions of similar nature have subsequently been labeled as Ramsey-based. Nevertheless, it suffices to have a weaker form of the lemma where the finite words come from a finite number of congruence classes, rather than arbitrary classes, that form a partition of the set of all finite words. The weaker lemma, with support of nicer properties from a congruence, can be proven without Ramsey's theorem. A commonly adopted improvement on such complementation constructions also requires the working of a congruence. This paper recounts the history and reviews using more contemporary terminology wherever possible the relevant concepts and results, to advocate renaming of Ramsey-based constructions as congruence-based constructions. Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-09-09 in cs.LO). Categorie arXiv: Formal Languages and Automata Theory (cs.FL) ; Logic in Computer Science (cs.LO). Pagina del lavoro: https://arxiv.org/abs/2609.06210 — 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-16T15:30:57.139Z dalla pagina https://arxiv.org/catchup/cs.LO/2026-09-09?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).