Non-atomic Transition Firing in Contextual Nets | SpringerLink
Skip to main content
Springer Nature Link
Log in

Non-atomic Transition Firing in Contextual Nets

  • Conference paper
  • First Online:
Application and Theory of Petri Nets and Concurrency (PETRI NETS 2015)

Part of the book series: Lecture Notes in Computer Science ((LNTCS,volume 9115))

Abstract

The firing rule for Petri nets assumes instantaneous and simultaneous consumption and creation of tokens. In the context of ordinary Petri nets, this poses no particular problem because of the system’s asynchronicity, even if token creation occurs later than token consumption in the firing. With read arcs, the situation changes, and several different choices of semantics are possible. The step semantics introduced by Janicki and Koutny can be seen as imposing a two-phase firing scheme: first, the presence of the required tokens is checked, then consumption and production of tokens happens. Pursuing this approach further, we develop a more general framework based on explicitly splitting the phases of firing, allowing to synthesize coherent steps. This turns out to define a more general non-atomic semantics, which has important potential for safety as it allows to detect errors that were missed by the previous semantics. Then we study the characterization of partial-order processes feasible under one or the other semantics.

This work is partially supported by the UK EPSRC project UNCOVER.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
JPY 3498
Price includes VAT (Japan)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
JPY 5719
Price includes VAT (Japan)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
JPY 7149
Price includes VAT (Japan)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. Allen, J.F.: Maintaining knowledge about temporal intervals. Commun. ACM 26(11), 832–843 (1983)

    Article  MATH  Google Scholar 

  2. Baldan, P., Bruni, A., Corradini, A., König, B., Rodríguez, C., Schwoon, S.: Efficient unfolding of contextual Petri nets. Theor. Comput. Sci. 449, 2–22 (2012)

    Article  MATH  Google Scholar 

  3. Baldan, P., Corradini, A., Montanari, U.: Contextual Petri nets, asymmetric event structures, and processes. Information and Computation 171(1), 1–49 (2001)

    Article  MATH  MathSciNet  Google Scholar 

  4. Busi, N., Pinna, G.M.: Non sequential semantics for contextual P/T nets. In: Billington, J., Reisig, W. (eds.) ICATPN 1996. LNCS, vol. 1091, pp. 113–132. Springer, Heidelberg (1996)

    Chapter  Google Scholar 

  5. Christensen, S., Hansen, N.D.: Coloured Petri nets extended with place capacities, test arcs and inhibitor arcs. In: Ajmone Marsan, M. (ed.) ICATPN 1993. LNCS, vol. 691, pp. 186–205. Springer, Heidelberg (1993)

    Chapter  Google Scholar 

  6. Engelfriet, J.: Branching processes of Petri nets. Acta Informatica 28(6), 575–591 (1991)

    Article  MATH  MathSciNet  Google Scholar 

  7. Fernandes, J., Koutny, M., Pietkiewicz-Koutny, M., Sokolov, D., Yakovlev, A.: Step persistence in the design of GALS systems. In: Colom, J.-M., Desel, J. (eds.) PETRI NETS 2013. LNCS, vol. 7927, pp. 190–209. Springer, Heidelberg (2013)

    Chapter  Google Scholar 

  8. Gaifman, H., Pratt, V.R.: Partial order models of concurrency and the computation of functions. In: Proceedings, Symposium on Logic in Computer Science, pp. 72–85. IEEE Computer Society (1987)

    Google Scholar 

  9. Janicki, R.: Relational structures model of concurrency. Acta Inf. 45(4), 279–320 (2008)

    Article  MATH  MathSciNet  Google Scholar 

  10. Janicki, R., Koutny, M.: Invariants and paradigms of concurrency theory. In: Aarts, E.H.L., van Leeuwen, J., Rem, M. (eds.) PARLE 1991. LNCS, vol. 506, pp. 59–74. Springer, Heidelberg (1991)

    Chapter  Google Scholar 

  11. Janicki, R., Koutny, M.: Structure of concurrency. Theoretical Computer Science 112(1), 5–52 (1993)

    Article  MATH  MathSciNet  Google Scholar 

  12. Janicki, R., Koutny, M.: Semantics of inhibitor nets. Inf. Comput. 123(1), 1–16 (1995)

    Article  MATH  MathSciNet  Google Scholar 

  13. Janicki, R., Koutny, M.: Fundamentals of modelling concurrency using discrete relational structures. Acta Inf. 34, 367–388 (1997)

    Article  MATH  MathSciNet  Google Scholar 

  14. Juhás, G., Lorenz, R., Mauser, S.: Synchronous + concurrent + sequential = earlier than + not later than. In: Sixth International Conference on Application of Concurrency to System Design (ACSD 2006), pp. 261–272. IEEE Computer Society (2006)

    Google Scholar 

  15. Juhás, G., Lorenz, R., Mauser, S.: Causal semantics of algebraic Petri nets distinguishing concurrency and synchronicity. Fundam. Inform. 86(3), 255–298 (2008)

    MATH  Google Scholar 

  16. Kleijn, H.C.M., Koutny, M.: Process semantics of general inhibitor nets. Inf. Comput. 190(1), 18–69 (2004)

    Article  MATH  MathSciNet  Google Scholar 

  17. Kleijn, J., Koutny, M.: Causality in extensions of Petri nets. T. Petri Nets and Other Models of Concurrency 7, 225–254 (2013)

    Google Scholar 

  18. Kleijn, J., Koutny, M., Pietkiewicz-Koutny, M., Rozenberg, G.: Step semantics of boolean nets. Acta Informatica 50(1), 15–39 (2013)

    Article  MATH  MathSciNet  Google Scholar 

  19. Lamport, L.: The mutual exclusion problem: part I - a theory of interprocess communication. J. ACM 33(2), 313–326 (1986)

    Article  MATH  MathSciNet  Google Scholar 

  20. Meseguer, J., Montanari, U., Sassone, V.: On the semantics of place/transition Petri nets. Mathematical Structures in Computer Science 7(4), 359–397 (1997)

    Article  MATH  MathSciNet  Google Scholar 

  21. Monica, D.D., Goranko, V., Montanari, A., Sciavicco, G.: Expressiveness of the interval logics of allen’s relations on the class of all linear orders: complete classification. In: Proceedings of the 22nd International Joint Conference on Artificial Intelligence, IJCAI/AAAI 2011, pp. 845–850 (2011)

    Google Scholar 

  22. Montanari, U., Rossi, F.: Contextual nets. Acta Inf. 32(6), 545–596 (1995)

    Article  MATH  MathSciNet  Google Scholar 

  23. Nebel, B., Bürckert, H.: Reasoning about temporal relations: A maximal tractable subclass of allen’s interval algebra. J. ACM 42(1), 43–66 (1995)

    Article  MATH  Google Scholar 

  24. Rodríguez, C.: Verification Based on Unfoldings of Petri Nets with Read Arcs. PhD thesis, Laboratoire Spécification et Vérification, ENS Cachan, France, December 2013

    Google Scholar 

  25. Rodríguez, C., Schwoon, S.: Verification of Petri nets with read arcs. In: Koutny, M., Ulidowski, I. (eds.) CONCUR 2012. LNCS, vol. 7454, pp. 471–485. Springer, Heidelberg (2012)

    Chapter  Google Scholar 

  26. Vogler, W.: A generalization of trace theory. RAIRO Infornatique théorique et Applications 25(2), 147–156 (1991)

    MATH  MathSciNet  Google Scholar 

  27. Vogler, W.: Fairness and partial order semantics. Inf. Process. Lett. 55(1), 33–39 (1995)

    Article  MATH  MathSciNet  Google Scholar 

  28. Vogler, W.: Partial order semantics and read arcs. Theoretical Computer Science 286(1), 33–63 (2002)

    Article  MATH  MathSciNet  Google Scholar 

  29. Vogler, W., Semenov, A., Yakovlev, A.: Unfolding and finite prefix for nets with read arcs. In: Sangiorgi, D., de Simone, R. (eds.) CONCUR 1998. LNCS, vol. 1466, pp. 501–516. Springer, Heidelberg (1998)

    Chapter  Google Scholar 

  30. Wiener, N.: A contribution to the theory of relative position. Proc. of the Cambridge Philosophical Society 33(2), 313–326 (1914)

    Google Scholar 

  31. Winkowski, J.: Processes of contextual nets and their characteristics. Fundamenta Informaticae 36(1) (1998)

    Google Scholar 

  32. Winkowski, J.: Reachability in contextual nets. Fundamenta Informaticae 51(1–2), 235–250 (2002)

    MATH  MathSciNet  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. INRIA and LSV, CNRS and ENS Cachan, Cachan, France

    Thomas Chatain, Stefan Haar & Stefan Schwoon

  2. University of Newcastle-upon-Tyne, Newcastle upon Tyne, UK

    Maciej Koutny

Authors
  1. Thomas Chatain
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Stefan Haar
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Maciej Koutny
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Stefan Schwoon
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Thomas Chatain .

Editor information

Editors and Affiliations

  1. Université Libre de Bruxelles, Brussels, Belgium

    Raymond Devillers

  2. Tampere University of Technology, Tampere, Finland

    Antti Valmari

Rights and permissions

Reprints and permissions

Copyright information

© 2015 Springer International Publishing Switzerland

About this paper

Cite this paper

Chatain, T., Haar, S., Koutny, M., Schwoon, S. (2015). Non-atomic Transition Firing in Contextual Nets. In: Devillers, R., Valmari, A. (eds) Application and Theory of Petri Nets and Concurrency. PETRI NETS 2015. Lecture Notes in Computer Science(), vol 9115. Springer, Cham. https://doi.org/10.1007/978-3-319-19488-2_6

Download citation

  • DOI: https://doi.org/10.1007/978-3-319-19488-2_6

  • Published:

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-319-19487-5

  • Online ISBN: 978-3-319-19488-2

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation