Back to Search
Start Over
Efficient Algorithms for Three Reachability Problems in Safe Petri Nets
- Source :
- Proceedings of the 42nd International Conference on Applications and Theory of Petri Nets and Concurrency (PETRI NETS 2021), PETRI NETS 2021-42nd International Conference on Application and Theory of Petri Nets and Concurrency, PETRI NETS 2021-42nd International Conference on Application and Theory of Petri Nets and Concurrency, Jun 2021, Paris, France. pp.339-359, ⟨10.1007/978-3-030-76983-3_17⟩, Application and Theory of Petri Nets and Concurrency ISBN: 9783030769826, Petri Nets
- Publication Year :
- 2021
- Publisher :
- HAL CCSD, 2021.
-
Abstract
- International audience; We investigate three particular instances of the marking coverability problem in ordinary, safe Petri nets: the Dead Places Problem, the Dead Transitions Problem, and the Concurrent Places Problem. To address these three problems, which are of practical interest, although not yet supported by mainstream Petri net tools, we propose a combination of static and dynamic algorithms. We implemented these algorithms and applied them to a large collection of 13,000+ Petri nets obtained from realistic systems-including all the safe benchmarks of the Model Checking Contest. Experimental results show that 95% of the problems can be solved in a few minutes using the proposed approaches.
- Subjects :
- Model checking
Theoretical computer science
Computer science
Efficient algorithm
[INFO.INFO-LO]Computer Science [cs]/Logic in Computer Science [cs.LO]
020206 networking & telecommunications
0102 computer and information sciences
02 engineering and technology
Petri net
State space exploration
01 natural sciences
concurrency theory
model checking
Coverability problem
temporal logic
010201 computation theory & mathematics
Reachability
0202 electrical engineering, electronic engineering, information engineering
Temporal logic
formal verification
Formal verification
state-space exploration
Subjects
Details
- Language :
- English
- ISBN :
- 978-3-030-76982-6
- ISBNs :
- 9783030769826
- Database :
- OpenAIRE
- Journal :
- Proceedings of the 42nd International Conference on Applications and Theory of Petri Nets and Concurrency (PETRI NETS 2021), PETRI NETS 2021-42nd International Conference on Application and Theory of Petri Nets and Concurrency, PETRI NETS 2021-42nd International Conference on Application and Theory of Petri Nets and Concurrency, Jun 2021, Paris, France. pp.339-359, ⟨10.1007/978-3-030-76983-3_17⟩, Application and Theory of Petri Nets and Concurrency ISBN: 9783030769826, Petri Nets
- Accession number :
- edsair.doi.dedup.....76eb176ca5103c5cbfd5fb84b5f8f811