2026-07-21T14:10:58Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:22779 2026-06-10T14:08:49Z ddc:004 open_access

On the Minimisation of Deterministic and History-Deterministic Generalised (Co)Büchi Automata Casares, Antonio Idir, Olivier Kuperberg, Denis Mascle, Corto Prakash, Keya Automata minimisation omega-regular languages good-for-games automata We present a polynomial-time algorithm minimising the number of states of history-deterministic generalised coBüchi automata, building on the work of Abu Radi and Kupferman on coBüchi automata. On the other hand, we establish that the minimisation problem for both deterministic and history-deterministic generalised Büchi automata is NP-complete, as well as the problem of minimising at the same time the number of states and colours of history-deterministic generalised coBüchi automata. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Antonio Casares and Olivier Idir and Denis Kuperberg and Corto Mascle and Keya Prakash 2025 Is Part Of LIPIcs, Volume 326, 33rd EACSL Annual Conference on Computer Science Logic (CSL 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CSL.2025.22 urn:nbn:de:0030-drops-227798 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CSL.2025.22 eng https://creativecommons.org/licenses/by/4.0/legalcode