From the 1 of 6 linked papers with an AI index.
6 papers
Explorable Parity Automata
Emile Hazard, Olivier Idir, Denis Kuperberg
The paper introduces explorable automata, a generalization of history‑deterministic automata that resolves nondeterminism using multiple simultaneous runs, and studies their decisi…
An algebraic characterisation of Eve-positional languages
Thomas Colcombet, Olivier Idir
We present a new algebraic characterisation of Eve-positionality for -regular languages. It involves only a limited number of elementary local properties to be checked. An …
Eve-positional languages: putting order into Büchi automata
Olivier Idir
An -regular language is Eve-positional if, in all games with this language as objective, the existential player can play optimally without keeping any information from the prev…
Using games and universal trees to characterise the nondeterministic index of tree languages
Olivier Idir, Karoliina Lehtinen
The parity index problem of tree automata asks, given a regular tree language and a set of priorities , is -feasible, that is, recognised by a nondeterministic parity…
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…
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…