complexity analysis 1explorable automata 1history-deterministic automata 1infinite-word acceptance 1parity automata 1
From the 1 of 3 linked papers with an AI index.
3 papers
cs.FL2026
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…
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…