Behavioural notions for elementary net systems | Distributed Computing Skip to main content
Springer Nature Link
Log in

Behavioural notions for elementary net systems

  • Original Articles
  • Published:
Distributed Computing Aims and scope Submit manuscript

Abstract

We study the relationships between a number of behavioural notions that have arisen in the theory of distributed computing. In order to sharpen the under-standing of these relationships we apply the chosen behavioural notions to a basic net-theoretic model of distributed systems called elementary net systems. The behavioural notions that are considered here are trace languages, non-sequential processes, unfoldings and event structures. The relationships between these notions are brought out in the process of establishing that for each elementary net system, the trace language representation of its behaviour agrees in a strong way with the event structure representation of its behaviour.

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

Access this article

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

Price includes VAT (Japan)

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Aalbersberg IJ Rozenberg G (1986) Theory of traces. Technical report no. 86-16, Institute of Applied Mathematics and Computer Science, University of Leiden, Leiden, The Netherlands

    Google Scholar 

  2. Bednarczyk M (1988) Categories of asynchronous systems. Ph.D. thesis, Computer Science Department, University of Susex. Brighton, G.B.

    Google Scholar 

  3. Best E, Devillers R (1987) Sequential and concurrent behaviour in Petri net theory. TCS 55:87–136

    Google Scholar 

  4. best E, Fernandez C (1988) Non-sequential processes: a Petri net view. EATCS Monographs on Theoretical Computer Science 13. Springer, Berlin Heidelberg New York

    Google Scholar 

  5. Brauer W, Reisig W, Rozenberg G (1987) Advances in Petri nets 1986 part I. Lect Notes Comput Sci 254

  6. Brauer W, Reisig W, Rozenberg G (1987) Advances in Petri nets 1986 part II, Lect Notes Comput Sci 255

  7. Kiehn A (1988) On the interrelation between synchronized and non-synchronized behaviour of Petri nets. J Inf Process Cybern 2:3–18

    Google Scholar 

  8. Mac Lane S (1971) Categories for the working mathematician. Springer, Berlin Heidelberg New York

    Google Scholar 

  9. Mazurkiewicz A (1978) Concurrent program schemes and their interpretation. DAIMI report PB-78. Computer Science Department, Aarhus University, Aarhus, Denmark

    Google Scholar 

  10. Mazurkiewicz A (1989) Basic notions of trace theory. Lect Notes Comput Sci 354:285–363

    Google Scholar 

  11. Nielsen M, Plotkin G, Winskel G (1981) Petri nets, event structures and domains, Part I. TCS 13:85–108

    Google Scholar 

  12. Petri CA (1962) Kommunikation mit Automaten. Institut für Instrumentelle Mathematik, Schriften des IIM Nr 2

  13. Reisig W (1984) Partial order semantics versus interleaving semantics for CSP-like languages and its impact of fainrness. Lect Notes Comput Sci 172:403–413

    Google Scholar 

  14. Rozenberg G (1987) Behaviour of elementary net systems. Lect Notes Comput Sci 254:60–94

    Google Scholar 

  15. Rozoy B, Thiagarajan PS (1987) Event structures and trace monoids. Technical report 87-47. Laboratoire d'Informatique Théorique et Programmation University of Paris VII Paris, France

    Google Scholar 

  16. Shields MN (1989) Behavioural presentations. Lect Notes Comput Sci 354:673–689

    Google Scholar 

  17. Stark EW (1987) Concurrent transition systems and semantics of process networks. 14th ACM Conference on Principles of Programming Languages 199–210

  18. Thiagarajan PS (1987) Elementary net systems. Lect Notes Comput Sci 254:26–59

    Google Scholar 

  19. Thiagarajan PS (1988) Some behavioural aspects of net theory. Lect Notes Comput Sci 317:630–653

    Google Scholar 

  20. Winskel G (1987) Event structures. Lect Notes Comput Sci 255:325–392

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Computer Science Department, Aarhus University, Ny Munkegade, DK-8000, Aarhus, Denmark

    M. Nielsen

  2. Department of Mathematics, University of Leiden, NL-2300 RA, Leiden, The Netherlands

    G. Rozenberg

  3. School of Mathematics, SPIC Science Foundation, 600017, Madras, India

    P. S. Thiagarajan

Authors
  1. M. Nielsen
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. G. Rozenberg
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. P. S. Thiagarajan
    View author publications

    You can also search for this author in PubMed Google Scholar

Additional information

M. Nielsen received a Master of Science degree in mathematics and computer science in 1973, and a Ph.D. degree in computer science in 1976 both from Aarhus University, Denmark. He has held academic positions at Department of Computer Science, Aarhus University, Denmark since 1976, and was visiting researcher at Computer Science Department, University of Edinburgh, U.K., 1977–79, and Computer Laboratory, Cambridge University, U.K., 1986. His research interest is in the theory of distributed computing.

Grzegorz Rozenberg received a master of engineering degree from the Department of Electronics (section computers) of the Technical University of Warsaw in 1964 and a Ph.D. in mathematics from the Institute of Mathematics of the Polish Academy of Science in 1968. He has held acdeemic positions at the Institute of Mathematics of the Polish Academy of Science, the Department of Mathematics of Utrecht University, the Department of Computer Science at SUNY at Buffalo, and the Department of Mathematics of the University of Antwerp. He is currently Professor at the Department of Computer Science of Leiden University and Adjoint Professor at the Department of Computer Science of the University of Colorado at Boulder. His research interests include formal languages and automata theory, theory of graph transformations, and theory of concurrent systems. He is currently President of the European Association for Theoretical Computer Science (EATCS).

P.S. Thiagarajan received the Bachelor of Technology degree from the Indian Institute of Technology, Madras, India in 1970. He was awarded the Ph.D. degree by Rice University, Houston Texas, U.S.A, in 1973. He has been a Research Associate at the Massachusetts Institute of Technology, Cambridge a Staff Scientist at the Geosellschaft für Mathematik und Datenverarbeitung, St. Augustin, a Lektor at Århus University, Århus and an Associate Professor at the Institute of Mathematical Sciences, Madras. He is currently a Professor at the School of Mathematics, SPIC Science Foundation, Madras. He research intest is in the theory of distributed computing.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Nielsen, M., Rozenberg, G. & Thiagarajan, P.S. Behavioural notions for elementary net systems. Distrib Comput 4, 45–57 (1990). https://doi.org/10.1007/BF01783665

Download citation

  • Received:

  • Revised:

  • Issue Date:

  • DOI: https://doi.org/10.1007/BF01783665

Key words

Search

Navigation