88 citations
- École Normale Supérieure Paris-SaclayFR90 papers
- Centre National de la Recherche ScientifiqueFR87 papers
- Institut national de recherche en sciences et technologies du numériqueFR29 papers
- Université Paris-SaclayFR16 papers
- Chennai Mathematical InstituteIN10 papers
- Laboratoire Bordelais de Recherche en InformatiqueFR9 papers
- Institute of Science and Technology AustriaAT8 papers
- Université Libre de BruxellesBE7 papers
- Aalborg UniversityDK6 papers
- Université Paris CitéFR6 papers
- University of MonsBE6 papers
- Centre Inria de l'Université de RennesFR5 papers
14 papers · 1 filter
A Robust Class of Data Languages and an Application to Learning
Benedikt Bollig, Peter Habermehl, Martin Leucker +1
We introduce session automata, an automata model to process data words, i.e., words over an infinite alphabet. Session automata support the notion of fresh data values, which are w…
Quantified CTL: Expressiveness and Complexity
François Laroussinie, Nicolas Markey
While it was defined long ago, the extension of CTL with quantification over atomic propositions has never been studied extensively. Considering two different semantics (depending…
Reachability in Two-Dimensional Vector Addition Systems with States is PSPACE-complete
Michael Blondin, Alain Finkel, Stefan Göller +2
Determining the complexity of the reachability problem for vector addition systems with states (VASS) is a long-standing open problem in computer science. Long known to be decidabl…
Stochastic Timed Automata
Nathalie Bertrand, Patricia Bouyer, Thomas Brihaye +4
A stochastic timed automaton is a purely stochastic process defined on a timed automaton, in which both delays and discrete choices are made randomly. We study the almost-sure mode…
The Odds of Staying on Budget
Christoph Haase, Stefan Kiefer
Given Markov chains and Markov decision processes (MDPs) whose transitions are labelled with non-negative integer costs, we study the computational complexity of deciding whether t…
Integer Vector Addition Systems with States
Christoph Haase, Simon Halfon
This paper studies reachability, coverability and inclusion problems for Integer Vector Addition Systems with States (ZVASS) and extensions and restrictions thereof. A ZVASS compri…