Authors: Philippe Darondeau ; Stephane Demri ; Roland Meyer ; Christophe Morvan

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 without labels on transitions or atomic propositions on markings. We consider several parameters to separate decidable problems from undecidable ones. Not only are we able to provide precise borders and a systematic analysis, but we also demonstrate the robustness of our proof techniques.

• 03B25 - Decidability of theories and sets of sentences
• 68Q60 - Specification and verification (program logics, model checking, etc.)
• 68Q85 - Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.)