Skip to main content
SpringerLink
Log in

Rule-Based Refinement of Petri Nets: A Survey

  • Chapter
Petri Net Technology for Communication-Based Systems

Part of the book series: Lecture Notes in Computer Science ((LNCS,volume 2472))

Abstract

This contribution provides a thorough survey of our work on rule-based refinement. Rule-based refinement comprises the transformation of Petri nets using rules while preserving certain system properties. Petri net rules and transformations are expressed by morphisms and pushouts. This allows an abstract formulation of our notions independent of a specific Petri net class, as place/transition nets, elementary nets, predicate/transition nets etc. Hence, it is adequate to consider our approach as rule-based refinement of Petri nets in general. We have presented various results in recent years at different conferences. So this contribution gives an overview of our work in a compact form leaving out the technical details.

This work is part of the joint research project “DFG- Forschergruppe Petrinetz-Technologie” between H. Weber (Coordinator), H. Ehrig (both from the Technical University Berlin) and W. Reisig (Humboldt-University Berlin), supported by the German Research Council (DFG).

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
$34.99 /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
USD 29.95
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
USD 39.99
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
USD 54.99
Price excludes VAT (USA)
  • 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. Best, E., Devillers, R., Hall, J.: The Box Calculus: a new causal algebra with multi-label communication. In: Rozenberg, G. (ed.) APN 1992. LNCS, vol. 609, pp. 21–69. Springer, Heidelberg (1992)

    Google Scholar 

  2. Brauer, W., Gold, R., Vogler, W.: A Survey of Behaviour and Equivalence Preserving Refinements of Petri Nets. In: Rozenberg, G. (ed.) APN 1990. LNCS, vol. 483, pp. 1–46. Springer, Heidelberg (1991)

    Google Scholar 

  3. Bradfield, J., Stirling, C.: Verifying temporal properties of processes. In: Baeten, J.C.M., Klop, J.W. (eds.) CONCUR 1990. LNCS, vol. 458, pp. 115–125. Springer, Heidelberg (1990)

    Google Scholar 

  4. Chen, Y., Tsai, W.T.: An algebraic approach to Petri net reduction and its application to protocol analysis. Technical report, University of Minnesota (1990)

    Google Scholar 

  5. David, R., Alla, H. (eds.): Petri Nets and Grafcet. Prentice Hall, Englewood Cliffs (1992)

    MATH  Google Scholar 

  6. Damm, W., Döhmen, G., Gerstner, V., Josko, B.: Modular verification of petri nets: The temporal logic approach. In: de Bakker, J.W., de Roever, W.-P., Rozenberg, G. (eds.) REX 1989. LNCS, vol. 430, pp. 180–207. Springer, Heidelberg (1990)

    Google Scholar 

  7. Desel, J., Merceron, A.: Vicinity Respecting Net Morphisms. In: Rozenberg, G. (ed.) APN 1990. LNCS, vol. 483, pp. 165–185. Springer, Heidelberg (1991)

    Google Scholar 

  8. Ehrig, H., et al.: Integration von Techniken der Software Spezifikation für ingenieuwissenschaftliche Anwendungen. Antrag für ein Schwerpunkprogramm an die DFG (akzeptiert als DFG-SPP von January 1998 bis December 2003) (1997), http://tfs.cs.tu-berlin.de/SPP/index.html

  9. Ehrig, H., Mahr, B.: Fundamentals of Algebraic Specification 1: Equations and Initial Semantics. EATCS Monographs on Theoretical Computer Science, vol. 6. Springer, Heidelberg (1985)

    MATH  Google Scholar 

  10. Ehrig, H., Reisig, W., Weber, H., et al.: The Petri Net Baukasten of the DFG-Forschergruppe PETRI NET TECHNOLOGY. In: Ehrig, H., Reisig, W., Rozenberg, G., Weber, H. (eds.) Advances in Petri Nets: Petri Net Technologies for Modeling Communication Based Systems. LNCS, Springer, Heidelberg (2002) (to appear)

    Google Scholar 

  11. Esparza, J., Silva, M.: On the analysis and synthesis of free choice systems. In: Rozenberg, G. (ed.) APN 1990. LNCS, vol. 483, pp. 243–286. Springer, Heidelberg (1991)

    Google Scholar 

  12. Esparza, J.: Model checking using net unfoldings. Science of Computer Programming 23, 151–195 (1994)

    Article  MATH  MathSciNet  Google Scholar 

  13. Favrel, J., Wu, H., Lee, K.H.: Reduction method of coloured Petri nets. In: Proc. IEEE Int. Conf. on Systems, Man, and Cybernetics

    Google Scholar 

  14. Genrich, H.J.: Predicate/Transition Nets. In: High-Level Petri Nets: Theory and Application, pp. 3–43. Springer, Heidelberg (1991)

    Google Scholar 

  15. van Glabbeck, R.J., Golz, U.: Equivalences and Refinement. In: Guessarian, I. (ed.) LITP 1990. LNCS, vol. 469, pp. 309–333. Springer, Heidelberg (1990)

    Google Scholar 

  16. Genrich, H.J., Lautenbach, K.: System Modelling with High-Level Petri Nets. Theoretical Computer Science 13, 109–136 (1981)

    Article  MATH  MathSciNet  Google Scholar 

  17. Howell, R.R., Rosier, L.E., Hsu, C.Y.: A taxonomy of fairness and temporal logic problems for Petri nets. Theoretical Computer Science 82(2), 341–372 (1991)

    Article  MATH  MathSciNet  Google Scholar 

  18. Jansen, L.: Referenzfallstudie Verkehrsleittechnik (1997), http://www.ifra.ing.tubs.de/~m33/spezi/

  19. Jensen, K., Christensen, S., Huber, P., Holla, M.: Design/CPN. A Reference Manual. Meta Software Cooperation, 125 Cambridge Park Drive, Cambridge Ma 02140, USA (1991)

    Google Scholar 

  20. Jensen, K.: Coloured Petri Nets. Basic Concepts, Analysis Methods and Practical Use: Basic Concepts. EATCS Monographs in Theoretical Computer Science edition, vol. 1. Springer, Heidelberg (1992)

    MATH  Google Scholar 

  21. Jensen, K.: Coloured Petri Nets - Basic Concepts, Analysis Methods and Practical Use: Analysis Methods. Springer Verlag, EATCS Monographs in Theoretical Computer Science edition, vol. 2. Springer, Heidelberg (1994)

    Google Scholar 

  22. Jensen, K.: Coloured Petri Nets - Basic Concepts, Analysis Methods and Practical Use: Practical Use. Springer Verlag, EATCS Monographs in Theoretical Computer Science edition, vol. 3. Springer, Heidelberg (1997)

    MATH  Google Scholar 

  23. Lamport, L.: The temporal logic of actions. ACM Transactions on Programming Languages and Systems 16(3), 872–923 (1994)

    Article  Google Scholar 

  24. Meseguer, J., Montanari, U.: Petri Nets are Monoids. Information and Computation 88(2), 105–155 (1990)

    Article  MATH  MathSciNet  Google Scholar 

  25. Manna, Z., Pnueli, A.: The Temporal Logic of Reactive and Concurrent Systems, Specification. Springer, Heidelberg (1992)

    Google Scholar 

  26. Peuker, S.: Halbordnungsbasierte Verfeinerung zur Verifikation verteiler Algorithmen. PhD thesis, Humboldt University Berlin (2001)

    Google Scholar 

  27. Peuker, S.: Concurrency based transition refinement for the verification of distributed algorithms. In: Ehrig, H., Reisig, W., Rozenberg, G., Weber, H. (eds.) Advances in Petri Nets: Petri Net Technologies for Modeling Communication Based Systems. LNCS, Springer, Heidelberg (2002) (to Appear)

    Google Scholar 

  28. Reisig, W.: Petri Nets and Algebraic Specifications. Theoretical Computer Science 80, 1–34 (1991)

    Article  MATH  MathSciNet  Google Scholar 

  29. Schmidt, K.: Symbolische Analysemethoden für algebraische Petri-Netze, vol. 4. Bertz Verlag, versal edition (1996)

    Google Scholar 

  30. Soussy, Y.: Deterministic systems of sequential processes: a class of structured Petri nets. In: Applications and Theory of Petri Nets, Gjern, pp. 62–81. Springer, Heidelberg (1991)

    Google Scholar 

  31. Vautherin, J.: Parallel System Specification with Coloured Petri Nets. In: Rozenberg, G. (ed.) APN 1987. LNCS, vol. 266, pp. 293–308. Springer, Heidelberg (1987)

    Google Scholar 

  32. van der Aalst, W.M.P.: Verification of workflow nets. In: Azéma, P., Balbo, G. (eds.) ICATPN 1997. LNCS, vol. 1248, pp. 407–426. Springer, Heidelberg (1997)

    Google Scholar 

  33. van der Aalst, W.M.P.: The Application of Petri Nets to Workflow Management. The Journal of Circuits, Systems and Computers 8, 21–66 (1998)

    Article  Google Scholar 

  34. van der Aalst, W.M.P., ter Hofstede, A.H.M.: Verification of Workflow Task Structures: A Petri-net-based approach. Forschungsberichte des AIFB 380, Universität Karlsruhe (November 1998)

    Google Scholar 

  35. Weber, H., Ehrig, H., Reisig, W. (eds.): Int. Colloquium on Petri Net Technologies for Modelling Communication Based Systems, Part II: The ”Petri Net Baukasten”. Fraunhofer Gesellschaft ISST (October 1999)

    Google Scholar 

  36. Weber, H., Ehrig, H., Reisig, W. (eds.): 2nd Int. Colloquium on Petri Net Technologies for Modelling Communication Based Systems, Researcher Group Petri Net Technology, Fraunhofer Gesellschaft ISST, Berlin, Germany (September 2001)

    Google Scholar 

  37. Weber, H., Lembke, S., Borusan, A.: Improving the Usability of Petri Nets with the Petri Net Baukasten. In: Ehrig, H., Juhás, G., Padberg, J., Rozenberg, G. (eds.) APN 2001. LNCS, vol. 2128, pp. 54–78. Springer, Heidelberg (2001)

    Chapter  Google Scholar 

  38. Ehrig, H., Gajewsky, M., Parisi-Presicce, F.: High-Level Replacement Systems with Applications to Algebraic Specifications and Petri Nets. In: Concurrency, Parallelism, and Distribution in Handbook of Graph Grammars and Computing by Graph Transformations, vol. ch. 6 (3), pp. 341–400. World Scientific, Singapore (1999)

    Google Scholar 

  39. Ehrig, H., Habel, A., Kreowski, H.-J., Parisi-Presicce, F.: From graph grammars to high level replacement systems. In: Ehrig, H., Kreowski, H.-J., Rozenberg, G. (eds.) Graph Grammars 1990. LNCS, vol. 532, pp. 269–291. Springer, Heidelberg (1991)

    Chapter  Google Scholar 

  40. Ehrig, H., Habel, A., Kreowski, H.-J., Parisi-Presicce, F.: Parallelism and concurrency in high-level replacement systems. Math. Struct. in Comp. Science 1, 361–404 (1991)

    Article  MATH  MathSciNet  Google Scholar 

  41. Ermel, C., Padberg, J., Ehrig, H.: Requirements engineering of a medical information system using rule-based refinement of petri nets. In: Proc. IDPT Conference (International Design and Process Technology), pp. 186–193 (1996)

    Google Scholar 

  42. Gajewsky, M.: Concepts and Requirements for Transformations within Petri Net Based Process Models. In: Ertas, A. (ed.) 5th World Conference on Integrated Design and Process Technology, Special Session on Model Integration. CDROM, p. 8 (2000)

    Google Scholar 

  43. Gajewsky, M., Hoffmann, K., Padberg, J.: Place Preserving and Transition Gluing Morphisms in Rule-Based Refinement of Place/Transition Systems. Technical Report 99-14, Technical University Berlin (1999)

    Google Scholar 

  44. Gajewsky, M., Parisi-Presicce, F.: On Compatibilty of Model and Class Transformations. In: Cerioli, M., Reggio, G. (eds.) WADT 2001 and CoFI WG Meeting 2001. LNCS, vol. 2267, Springer, Heidelberg (2001)

    Google Scholar 

  45. Gajewsky, M., Padberg, J., Urbás̆ek, M.: Rule-Based Refinement for Place/Transition Systems: Preserving Liveness-Properties. Technical Report 2001-8, Technical University of Berlin (2001)

    Google Scholar 

  46. Padberg, J.: Categorical Approach to Horizontal Structuring and Refinement of High-Level Replacement Systems. Applied Categorical Structures 7(4), 371–403 (1999)

    Article  MATH  MathSciNet  Google Scholar 

  47. Padberg, J., Ehrig, H., Ribeiro, L.: Algebraic high-level net transfrmation systems. Mathematical Structures in Computer Science 5, 217–256 (1995)

    Article  MATH  MathSciNet  Google Scholar 

  48. Padberg, J., Gajewsky, M.: Rule-Based Refinement of Petri Nets For Modeling Train Control Systems. In: Kozák, S̆., Huba, M. (eds.) Petri Nets in Design, Modelling and Simulation of Control Systems, Special Session at the IFAC Conference on Control Systems Design, pp. 299–304 (2000)

    Google Scholar 

  49. Padberg, J., Gajewsky, M.: Safety Preserving Transformations of Coloured Petri Nets. Technical Report 2000-13, Technical University Berlin (2000)

    Google Scholar 

  50. Padberg, J., Gajewsky, M., Ermel, C.: Rule-Based Refinement of High-Level Nets Preserving Safety Properties. In: Astesiano, E. (ed.) Fundamental Approaches to Software Engineering. LNCS, vol. 1382, pp. 221–238. Springer, Heidelberg (1998)

    Chapter  Google Scholar 

  51. Padberg, J., Gajewsky, M., Ermel, C.: Rule-based refinement of high-level nets preserving safety properties. Science of Computer Programming 40, 97–118 (2001), www.elsevier.nl/locate/scico

    Article  MATH  Google Scholar 

  52. Padberg, J., Hoffmann, K., Gajewsky, M.: Stepwise Introduction and Preservation of Safety Properties in Algebraic High-Level Net Systems. In: Maibaum, T. (ed.) FASE 2000. LNCS, vol. 1783, pp. 249–265. Springer, Heidelberg (2000)

    Chapter  Google Scholar 

  53. Urbášek, M., Padberg, J.: Preserving liveness with rule-based refinement of place/transition systems. In: Society for Design and Process Science (SDPS) (ed.) Proc. IDPT 2002: Sixth World Conference on Integrated Design and Process Technology (2002) (to appear)

    Google Scholar 

  54. Urbás̆ek, M.: Another Safety Property and Liveness Preserving Morphisms of P/T Systems. Technical Report, Technical University of Berlin (2002)

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Institute for Software Technology and Theoretical Computer Science, Technical University Berlin, Germany

    J. Padberg & M. Urbášek

Authors
  1. J. Padberg
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. M. Urbášek
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Editors and Affiliations

  1. Technische Universität Berlin, Germany

    Hartmut Ehrig

  2. Institut für Informatik, Humboldt-Universität zu Berlin, Unter den Linden 6, 10099, Berlin, Germany

    Wolfgang Reisig

  3. Leiden Center of Advanced Computer Science (LIACS), Leiden University, Niels Bohrweg 1, 2333, Leiden, CA, The Netherlands

    Grzegorz Rozenberg

  4. Computergestützte InformationsSysteme (CIS), Technische Universität Berlin, Germany

    Herbert Weber

Rights and permissions

Reprints and permissions

Copyright information

© 2003 Springer-Verlag Berlin Heidelberg

About this chapter

Cite this chapter

Padberg, J., Urbášek, M. (2003). Rule-Based Refinement of Petri Nets: A Survey. In: Ehrig, H., Reisig, W., Rozenberg, G., Weber, H. (eds) Petri Net Technology for Communication-Based Systems. Lecture Notes in Computer Science, vol 2472. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-40022-6_9

Download citation

  • DOI: https://doi.org/10.1007/978-3-540-40022-6_9

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-540-20538-8

  • Online ISBN: 978-3-540-40022-6

  • eBook Packages: Springer Book Archive

Publish with us

Policies and ethics

Search

Navigation