Characterizing the Polynomial-Time Minimizable $\omega$-Automata

Bader Abu Radi, Rüdiger Ehlers

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-determinist…