3 papers
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ü…
cs.LO2024
Positive and monotone fragments of FO and LTL
Denis Kuperberg, Quentin Moreau
We study the positive logic FO+ on finite words, and its fragments, pursuing and refining the work initiated in [Kuperberg 2023]. First, we transpose notorious logic equivalences i…