2 papers
cs.FL2026
From Ramsey-Based to Congruence-Based Constructions for Büchi Complementation
Yih-Kuen Tsay, Moshe Y. Vardi
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 cons…
cs.FL2021
Congruence Relations for Büchi Automata
Yong Li, Yih-Kuen Tsay, Andrea Turrini +2
We revisit here congruence relations for Büchi automata, which play a central role in the automata-based verification. The size of the classical congruence relation is in $3^{\math…