[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ skip to main content
research-article

Polynomial Sufficient Conditions of Well-Behavedness and Home Markings in Subclasses of Weighted Petri Nets

Published: 28 July 2014 Publication History

Abstract

Join-Free Petri nets, whose transitions have at most one input place, model systems without synchronizations, while Choice-Free Petri nets, whose places have at most one output transition, model systems without conflicts. These classes respectively encompass the state machines (S-systems) and the marked graphs (T-systems).
Whereas a structurally bounded and structurally live Petri net is said to be “well-formed”, a bounded and live Petri net is said to be “well-behaved”. Necessary and sufficient conditions for the well-formedness of Join-Free and Choice-Free nets have been known for some time, yet the behavioral properties of these classes are still not well understood. In particular polynomial sufficient conditions for liveness, that is, polynomial in time and with a polynomial initial number of tokens, have not been found until now. Besides, home markings, which can be reached from every reachable marking thus allowing for the construction of systems that can return to their initial data distribution, are not well apprehended either for these subclasses.
We extend results on weighted T-systems to the class of weighted Petri nets and present transformations which preserve the language of the system and reduce the initial marking. We introduce a notion of balancing that makes possible the transformation of conservative systems into so-called “token-conservative” systems, whose number of tokens is invariant, while retaining the feasible transition sequences. This transformation is pertinent for all well-formed Petri nets and leads to polynomial sufficient conditions of liveness for well-formed Join-Free and Choice-Free nets. Finally, we also provide polynomial live and home markings for Fork-Attribution systems.

References

[1]
Paola Alimonti, Esteban Feuerstein, Luigi Laura, and Umberto Nanni. 2011. Linear time analysis of properties of conflict-free and general Petri nets. Theor. Comput. Sci. 412, 4--5 (2011), 320--38.
[2]
Chérif Amer-Yahia and Noureddine Zerhouni. 1999. Structure theory of choice-free Petri nets based on eigenvalues. J. Franklin Institute (1999).
[3]
Chérif Amer-Yahia, Noureddine Zerhouni, Abdellah El Moudni, and Michel Ferney. 1999. Some subclasses of Petri nets and the analysis of their structural properties: A new approach. IEEE Trans. Syst. Man Cybernet., Part A 29, 2 (1999), 164--172.
[4]
Kamel Barkaoui and Michel Minoux. 1992. A polynomial-time graph algorithm to decide liveness of some basic classes of bounded Petri nets. In Proceedings of the 13th International Conference on Application and Theory of Petri Nets. 62--75.
[5]
Kamel Barkaoui and Jean-François Pradat-Peyre. 1996. On liveness and controlled siphons in Petri nets. In Application and Theory of Petri Nets 1996, J. Billington and W. Reisig (Eds.), Lecture Notes in Computer Science, vol. 1091, Springer, Berlin Heidelberg, 57--72.
[6]
Daniel Y. Chao and Jose A. Nicdao. 2001. Liveness for synchronized choice Petri nets. Comput. J. 44, 2 (2001), 124--136.
[7]
Jean-Marc Delosme, Thomas Hujsa, and Alix Munier-Kordon. 2013. Polynomial sufficient conditions of well-behavedness for weighted join-free and choice-free systems. In Proceedings of the 13th International Conference on Application of Concurrency to System Design (ACSD'13). 90--99.
[8]
Jörg Desel and Javier Esparza. 1995. Free Choice Petri Nets. Cambridge Tracts in Theoretical Computer Science, vol. 40, Cambridge University Press, New York, NY.
[9]
Marc Engels, Greet Bilsen, Rudy Lauwereins, and Jean A. Peperstraete. 1994. Cycle-static dataflow: Model and implementation. In Proceedings of the 20th Asilomar Conference on Signals, Systems and Computers. 503--507.
[10]
Javier Esparza. 1997. Petri nets, commutative context-free grammars, and basic parallel processes. Fundamenta Informaticae 31, 1 (1997), 13--26.
[11]
Javier Esparza. 1998. Decidability and complexity of Petri net problems - an introduction. In Lectures on Petri Nets I: Basic Models, W. Reisig and G. Rozenberg (Eds.), Lecture Notes in Computer Science, vol. 1491, Springer, Berlin Heidelberg, 374--428.
[12]
Andreas Frommer and Daniel B. Szyld. 2000. On asynchronous iterations. J. Comput. Appl. Math. 123, 1--2 (2000), 201--216.
[13]
Li Jiao, To-Yat Cheung, and Weiming Lu. 2004. On liveness and boundedness of asymmetric choice nets. Theor. Comput. Sci. 311, 1--3 (2004), 165--197.
[14]
Neil D. Jones, Lawrence H. Landweber, and Y. Edmund Lien. 1977. Complexity of some problems in Petri nets. Theor. Comput. Sci. 4, 3 (1977), 277--299.
[15]
Edward A. Lee and David G. Messerschmitt. 1987. Synchronous data flow. Proc. IEEE 75, 9 (1987), 1235--1245.
[16]
Olivier Marchetti and Alix Munier-Kordon. 2009. A sufficient condition for the liveness of weighted event graphs. Eur. J. Oper. Res. 197, 2 (2009), 532--540.
[17]
Richard Mayr. 2000. Process rewrite systems. Inform. Comput. 156, 1--2 (2000), 264--286.
[18]
Nimrod Megiddo. 1987. On the complexity of linear programming. In Proceedings of the 5th World Congress on Advances in Economic Theory. 225--268.
[19]
Gérard Memmi and Gérard Roucairol. 1980. Linear algebra in net theory. In Net Theory and Applications, W. Brauer (Ed.), Lecture Notes in Computer Science, vol. 84, Springer, Berlin Heidelberg, 213--223.
[20]
Tadao Murata. 1989. Petri nets: Properties, analysis and applications. Proc. IEEE 77, 4 (1989), 541--580.
[21]
Laura Recalde, Enrique Teruel, and Manuel Silva. 1995. On well-formedness analysis: The case of deterministic systems of sequential processes. In Structures in Concurrency Theory, J. Desel (Ed.), Springer London, 279--293.
[22]
Laura Recalde, Enrique Teruel, and Manuel Silva. 1996. SC*ECS: A class of modular and hierarchical cooperating systems. In Application and Theory of Petri Nets 1996, J. Billington and W. Reisig (Eds.), Lecture Notes in Computer Science, vol. 1091, Springer, Berlin Heidelberg, 440--459.
[23]
Laura Recalde, Enrique Teruel, and Manuel Silva. 1998. Modeling and analysis of sequential processes that cooperate through buffers. IEEE Trans. Robot. Autom. 14, 2 (1998), 267--277.
[24]
Joseph Sifakis. 1978. Structural properties of Petri nets. In Mathematical Foundations of Computer Science, J. Winkowski (Ed.), Lecture Notes in Computer Science, vol. 64, Springer, Berlin Heidelberg, 474--483.
[25]
Manuel Silva, Enrique Teruel, and José Manuel Colom. 1998. Linear algebraic and linear programming techniques for the analysis of place/transition net systems. In Lectures on Petri Nets I: Basic Models, W. Reisig and G. Rozenberg (Eds.), Lecture Notes in Computer Science, vol. 1491, Springer, Berlin Heidelberg, 309--373.
[26]
Enrique Teruel, Piotr Chrzastowski-Wachtel, José Manuel Colom, and Manuel Silva. 1992. On weighted T-systems. In Application and Theory of Petri Nets 1992, K. Jensen (Ed.), Lecture Notes in Computer Science, vol. 616, Springer, Berlin Heidelberg, 348--367.
[27]
Enrique Teruel, José Manuel Colom, and Manuel Silva. 1997. Choice-free Petri nets: A model for deterministic concurrent systems with bulk services and arrivals. IEEE Trans. Syst. Man Cybernet. Part A 27, 1 (1997), 73--83.
[28]
Enrique Teruel and Manuel Silva. 1993. Liveness and home states in equal conflict systems. In Application and Theory of Petri Nets 1993, M. Ajmone Marsan (Ed.), Lecture Notes in Computer Science, vol. 691, Springer, Berlin Heidelberg, 415--432.
[29]
Enrique Teruel and Manuel Silva. 1996. Structure theory of equal conflict systems. Theor. Comput. Sci. 153, 1&2 (1996), 271--300.
[30]
Maarten Wiggers, Marco Jan Gerrit Bekooij, Pierre G. Jansen, and Gerard J. M. Smit. 2007. Efficient computation of buffer capacities for cyclo-static dataflow graphs. In Proceedings of the 44th Design Automation Conference. 658--663.

Cited By

View all
  • (2021)Efficient Synthesis of Weighted Marked Graphs with Circular Reachability Graph, and BeyondTransactions on Petri Nets and Other Models of Concurrency XV10.1007/978-3-662-63079-2_4(75-100)Online publication date: 25-Feb-2021
  • (2020)Presynthesis of bounded choice-free or fork-attribution netsInformation and Computation10.1016/j.ic.2019.104482271:COnline publication date: 1-Jul-2020
  • (2019)Synthesis of Weighted Marked Graphs from Constrained Labelled Transition Systems: A Geometric ApproachTransactions on Petri Nets and Other Models of Concurrency XIV10.1007/978-3-662-60651-3_7(172-191)Online publication date: 21-Nov-2019
  • Show More Cited By

Recommendations

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on Embedded Computing Systems
ACM Transactions on Embedded Computing Systems  Volume 13, Issue 4s
Special Issue on Real-Time and Embedded Technology and Applications, Domain-Specific Multicore Computing, Cross-Layer Dependable Embedded Systems, and Application of Concurrency to System Design (ACSD'13)
July 2014
571 pages
ISSN:1539-9087
EISSN:1558-3465
DOI:10.1145/2601432
Issue’s Table of Contents
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Journal Family

Publication History

Published: 28 July 2014
Accepted: 01 February 2014
Received: 01 November 2013
Published in TECS Volume 13, Issue 4s

Permissions

Request permissions for this article.

Check for updates

Author Tags

  1. Balancing
  2. S-system
  3. T-system
  4. boundedness
  5. choice-free
  6. event graph
  7. fork-attribution
  8. home marking
  9. join-free
  10. liveness
  11. polynomial sufficient condition
  12. reversible
  13. state machine
  14. synchronous dataflow
  15. token-conservative
  16. transformation
  17. weighted Petri net
  18. well-behavedness
  19. well-formedness

Qualifiers

  • Research-article
  • Research
  • Refereed

Funding Sources

  • Digiteo

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)4
  • Downloads (Last 6 weeks)0
Reflects downloads up to 27 Dec 2024

Other Metrics

Citations

Cited By

View all
  • (2021)Efficient Synthesis of Weighted Marked Graphs with Circular Reachability Graph, and BeyondTransactions on Petri Nets and Other Models of Concurrency XV10.1007/978-3-662-63079-2_4(75-100)Online publication date: 25-Feb-2021
  • (2020)Presynthesis of bounded choice-free or fork-attribution netsInformation and Computation10.1016/j.ic.2019.104482271:COnline publication date: 1-Jul-2020
  • (2019)Synthesis of Weighted Marked Graphs from Constrained Labelled Transition Systems: A Geometric ApproachTransactions on Petri Nets and Other Models of Concurrency XIV10.1007/978-3-662-60651-3_7(172-191)Online publication date: 21-Nov-2019
  • (2017)On Liveness and Deadlockability in Subclasses of Weighted Petri NetsApplication and Theory of Petri Nets and Concurrency10.1007/978-3-319-57861-3_16(267-287)Online publication date: 5-May-2017
  • (2014)On the Reversibility of Well-Behaved Weighted Choice-Free SystemsApplication and Theory of Petri Nets and Concurrency10.1007/978-3-319-07734-5_18(334-353)Online publication date: 2014

View Options

Login options

Full Access

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Media

Figures

Other

Tables

Share

Share

Share this Publication link

Share on social media