Computing Reviews
Today's Issue Hot Topics Search Browse Recommended My Account Log In
Review Help
Search
The logical view on continuous Petri nets
Blondin M., Finkel A., Haase C., Haddad S. ACM Transactions on Computational Logic18 (3):1-28,2017.Type:Article
Date Reviewed: Nov 17 2017

The reachability problem for standard Petri nets is EXPSPACE hard, and the coverability problem is EXPSPACE complete. However, more efficient algorithms exist for variants of the standard nets. Continuous Petri nets are such a variant that allows the number of tokens to be a rational number. As in other problems, replacing integers by rationals leads to easier problems. For this class, the reachability problem can be defined in the first-order theory of the rationals with addition and order. This leads to a polynomial-time algorithm for checking reachability. The computation for continuous Petri nets can be used as an over-approximation for standard Petri nets.

In this paper, the authors exploit the encoding in the theory of the rationals further to establish the complexity class for additional problems, like inclusion, epsilon liveness, and the home state problem, about continuous Petri nets. As an application of this encoding, the authors show that it can be used as a pruning criterion for the backward algorithm to decide coverability for standard Petri nets.

The authors recall all relevant definitions and known results, so the general reader might get a good overview. However, to fully grasp the details, the reader has to be familiar with recent results for Petri nets, including the previous work of the authors. For the benefit of this group, detailed proofs are included.

Reviewer:  Andreas Schaefer Review #: CR145662 (1801-0013)
Bookmark and Share
 
Automata (F.1.1 ... )
 
 
Parallelism And Concurrency (F.1.2 ... )
 
 
Petri Nets (D.2.2 ... )
 
 
Complexity Measures And Classes (F.1.3 )
 
 
Nonnumerical Algorithms And Problems (F.2.2 )
 
Would you recommend this review?
yes
no
Other reviews under "Automata": Date
The congruence theory of closure properties of regular tree languages
Tirri S. Theoretical Computer Science 76(2-3): 261-271, 2001. Type: Article
Jun 1 1991
Distribution and synchronized automata
Petit A. Theoretical Computer Science 76(2-3): 285-308, 2001. Type: Article
Feb 1 1992
Efficient simulation of finite automata by neural nets
Alon N., Dewdney A., Ott T. Journal of the ACM 38(2): 495-514, 1991. Type: Article
Dec 1 1991
more...

E-Mail This Printer-Friendly
Send Your Comments
Contact Us
Reproduction in whole or in part without permission is prohibited.   Copyright 1999-2024 ThinkLoud®
Terms of Use
| Privacy Policy