Characterizing the Polynomial-Time Minimizable $ω$-Automata
Bader Abu Radi, Rüdiger Ehlers · arXiv (Cornell University) · 2025
A central question in the theory of automata is which classes of automata can be minimized in polynomial time. We close the remaining gaps for deterministic and history-deterministic automata over infinite words by proving that deterministic co-Büchi automata with transition-based acceptance are NP-hard to minimize, as are history-deterministic Büchi automata with transition-based acceptance.