22 citations · 22 across the 3 of their papers we have counts for
3 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…
cs.FL2014★ 22 cited
State of Büchi Complementation
Ming-Hsien Tsai, Seth Fogarty, Moshe Y. Vardi +1
Complementation of Büchi automata has been studied for over five decades since the formalism was introduced in 1960. Known complementation constructions can be classified into Rams…