13:00
14:00

In 2019, Abu Radi and Kupferman gave a polynomial-time algorithm to minimise transition-based history-deterministic co-Büchi automata.
In this talk, I will present an extension of their results to generalised co-Büchi automata, where transitions are coloured and runs should eventually avoid at least one colour. We will see that the number of states of those automata can also be minimised in polynomial time.
By contrast, we show that the minimisation of (history-)deterministic generalised Büchi and deterministic generalised coBüchi automata are NP-complete problems (while the complexity of the corresponding problems for non-generalised automata is open).
This is joint work with Antonio Casares, Denis Kuperberg, Olivier Idir and Aditya Prakash.

salle 178, zoom: https://bordeaux-inp-fr.zoom.us/j/89508306159