Showing 2024Show all
3 papers · 1 filter
cs.FL2024
Mostowski Index via extended register games
Olivier Idir, Karoliina Lehtinen
The parity index problem of tree automata asks, given a regular tree language L, what is the least number of priorities of a nondeterministic parity tree automaton that recognises…
cs.FL2024
Explorable Parity Automata
Emile Hazard, Olivier Idir, Denis Kuperberg
We define the class of explorable automata on finite or infinite words. This is a generalization of History-Deterministic (HD) automata, where this time non-deterministic choices c…
cs.FL2024
On the Minimisation of Deterministic and History-Deterministic Generalised (co)Büchi Automata
Antonio Casares, Olivier Idir, Denis Kuperberg +2
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ü…