859 citations
- Aix-Marseille UniversitéFR204 papers
- Centre National de la Recherche ScientifiqueFR180 papers
- Université de ToulonFR108 papers
- Institut Universitaire de FranceFR32 papers
- Centre de physique des particules de MarseilleFR30 papers
- Universitat de ValènciaES30 papers
- Commissariat à l'Énergie Atomique et aux Énergies AlternativesFR29 papers
- Université Paris-SaclayFR29 papers
- Université Paris-SudFR29 papers
- Institut Méditerranéen d’OcéanologieFR28 papers
- GéoazurFR27 papers
- Institut National de Physique Nucléaire et de Physique des ParticulesFR27 papers
20 papers · 1 filter
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…
Positional -regular languages
Antonio Casares, Pierre Ohlmann
In the context of two-player games over graphs, a language is called positional if, in all games using as winning objective, the protagonist can play optimally using positi…
From Muller to Parity and Rabin Automata: Optimal Transformations Preserving (History) Determinism
Antonio Casares, Thomas Colcombet, Nathanaël Fijalkow +1
We study transformations of automata and games using Muller conditions into equivalent ones using parity or Rabin conditions. We present two transformations, one that turns a deter…
On the Translation of Automata to Linear Temporal Logic
Udi Boker, Karoliina Lehtinen, Salomon Sickert
While the complexity of translating future linear temporal logic (LTL) into automata on infinite words is well-understood, the size increase involved in turning automata back to LT…
History Determinism vs. Good for Gameness in Quantitative Automata
Udi Boker, Karoliina Lehtinen
Automata models between determinism and nondeterminism/alternations can retain some of the algorithmic properties of deterministic automata while enjoying some of the expressivenes…
Token Games and History-Deterministic Quantitative-Automata
Udi Boker, Karoliina Lehtinen
A nondeterministic automaton is history-deterministic if its nondeterminism can be resolved by only considering the prefix of the word read so far. Due to their good compositional…