2026-07-21T20:03:26Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:10676 2024-03-06T10:46:26Z ddc:004 open_access

Minimizing GFG Transition-Based Automata (Track B: Automata, Logic, Semantics, and Theory of Programming) Abu Radi, Bader Kupferman, Orna Minimization Deterministic co-Büchi Automata While many applications of automata in formal methods can use nondeterministic automata, some applications, most notably synthesis, need deterministic or good-for-games automata. The latter are nondeterministic automata that can resolve their nondeterministic choices in a way that only depends on the past. The minimization problem for nondeterministic and deterministic Büchi and co-Büchi word automata are PSPACE-complete and NP-complete, respectively. We describe a polynomial minimization algorithm for good-for-games co-Büchi word automata with transition-based acceptance. Thus, a run is accepting if it traverses a set of designated transitions only finitely often. Our algorithm is based on a sequence of transformations we apply to the automaton, on top of which a minimal quotient automaton is defined. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Bader Abu Radi and Orna Kupferman 2019 Is Part Of LIPIcs, Volume 132, 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2019.100 urn:nbn:de:0030-drops-106761 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2019.100 eng https://creativecommons.org/licenses/by/3.0/legalcode