2025/04/29 by Radi, Bader Abu, Ehlers, Rüdiger · 2 citations
#FOS: Computer and information sciences #Formal Languages and Automata Theory (cs.FL) #Logic in Computer Science (cs.LO)
paper · doi:10.48550/arxiv.2504.20553
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.