41 citations · 104 across the 19 of their papers we have counts for
3 papers · 2 filters
A Note on the Complexity of Model-Checking Bounded Multi-Pushdown Systems
Kshitij Bansal, Stéphane Demri
In this note, we provide complexity characterizations of model checking multi-pushdown systems. Multi-pushdown systems model recursive concurrent programs in which any sequential p…
Petri Net Reachability Graphs: Decidability Status of First Order Properties
Philippe Darondeau, Stephane Demri, Roland Meyer +1
We investigate the decidability and complexity status of model-checking problems on unlabelled reachability graphs of Petri nets by considering first-order and modal languages with…
Taming Past LTL and Flat Counter Systems
Stéphane Demri, Amit Kumar Dhar, Arnaud sangnier
Reachability and LTL model-checking problems for flat counter systems are known to be decidable but whereas the reachability problem can be shown in NP, the best known complexity u…