On the Minimisation of Deterministic and History-Deterministic Generalised (co)Büchi Automata
For researchers in automata theory, this work provides complexity results and algorithms for minimization problems of generalized (co)Büchi automata, extending prior results.
The paper presents a polynomial-time algorithm for minimizing the number of states of history-deterministic generalized coBüchi automata, and proves NP-completeness for minimizing deterministic and history-deterministic generalized Büchi automata, as well as simultaneous state and color minimization for history-deterministic generalized coBüchi 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.