Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

Notes on Algebraic Calculi of Processes

  • Conference paper
Logics and Models of Concurrent Systems

Part of the book series: NATO ASI Series ((NATO ASI F,volume 13))

Abstract

We gathered here some notes on Milner’s calculi of processes. We interpret the terms of these calculi as transition systems. We intoduce a calculus called MEIJE built on a monoid of synchronized actions and illustrate some general semantic notions:

  • we show the equivalence of this calculus with some others

  • we give an implementation in a calculus restricted to purely atomic actions

  • we show the universality of MEIJE with respect to the notion of effective transition system and sketch its expressive power with regard to synchronization operators.

Finally the concept of subcalculus is illustrated through the description in our language of the class of rational parallel place machines.

Résumé

On présente quelques notes sur la notion de calcul algébrique de processus due à Milner. Ici les terrnes de ces calculs sont interpétés comme des systèmes de transitions. Ayant introduit un calcul appelé MEIJE, qui est construit sur un monoide d’actions synchronisées, on illustre quelques définitions générales concernant la sémantique:

  • en montrant l’équivalence de ce calcul et de quelques autres,

  • en donnant und implémentation dans un calcul à actions purement atomiques,

  • en démontrant l’universalité de MEIJE par rapport à la notion de système de transition effectif et en esquissant son pouvior d’expression quant aux opérateurs de synchronization.

Enfin la notion de sous-calcul est illustrée par la description dans notre langage de la classe des machines à places rationnelles.

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 84.99
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
USD 109.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. A. Arnold & M. Nivat: “Comportements de processus”, Coll. AFCET “Les Mathématiques de l’Informatique” ( AFCET, Paris, 1981 )

    Google Scholar 

  2. D. Austry & G. Boudol: “Algébre de processus et synchronisations”, Theoret. Comput. Sci. 30 (1984) 91–131

    Article  MATH  MathSciNet  Google Scholar 

  3. G. Boudol, G. Roucairol & R. de Simone: “Petri nets and algebraic calculi of processes”, Rapport de Recherche INRIA 292 (1984)

    Google Scholar 

  4. S.D. Brookes: “On the relationship of CCS and CSP”, ICALP 83, Lecture Notes in Comput. Sci. 154 (1983) 83–96

    MathSciNet  Google Scholar 

  5. S.D. Brookes & W.C. Rounds: “Behavioural equivalence relations induced by programming logics”, ICALP 83, Lecture Notes in Comput. Sci. 154 (1983) 97–108

    MathSciNet  Google Scholar 

  6. S.D. Brookes, C.A.R. Hoare & A.W. Roscoe: “A theory of communicating sequential processes”, JACM 31 (1984) 560–599

    Article  MATH  MathSciNet  Google Scholar 

  7. Ph. Darondeau & L. Kott: “On the observational semantics of fair parallelism”, ICALP 83, Lecture Notes in Comput. Sci. 154 (1983) 147–159 s.a. Rapport de Recherche INRIA 262 (1983)

    Google Scholar 

  8. Ph. Darondeau: “Infinitary languages and fully abstract models of fair asynchrony”, Advanced Course on Logics and Models for Verification and Specification of Concurrent Systems, La Colle-sur-Loup (1984)

    Google Scholar 

  9. S. Eilenberg & M.P. Schutzenberger: “Rational sets in commutative monoids”, Journal of Algebra 13 (1969) 173–191

    Article  MATH  MathSciNet  Google Scholar 

  10. S. Eilenberg: “Automata, Languages and Machines”, vo1.A, Academic Press (1974)

    Google Scholar 

  11. J.S. Gourlay, W.C. Rounds & R. Statman: “On properties preserved by contractions of concurrent systems”, Intern. Symp. on Semantics of Concurrent Computations, Evian 79, G. Kahn Ed., Lecture Notes in Comput. Sci. -70 (1979) 51–65

    Google Scholar 

  12. M. Hennessy & R. Milner: “On observing nondeterminism and concurrency”, ICALP 80, Lecture Notes in Comput. Sci. 85 (1980) 299–309 s.a. “Algebraic laws for nondeterminism and concurrency” CSR-133–83, Computer Science Dept., Edinburgh Univ. (1983)

    Google Scholar 

  13. M. Hennessy, Wei Li & G. Plotkin: “A first attempt at translating CSP into CCS”, 2 nd Intern. Conf. on Distributed Computing Systems, Paris (1981) 105–115

    Google Scholar 

  14. M. Hennessy & R. de Nicola: “Testing equivalences for processes”, ICALP 83, Lecture Notes in Comput. Sci. 154 (1983) 548–560 s.a. CSR-123–82, Comput. Sci. Dept., Edinburgh Univ. (1982)

    Google Scholar 

  15. M. Hennessy: “Modelling finite delay operators”, CSR-153–83, Comput. Sci. Dept., Edinburgh Univ. (1983)

    Google Scholar 

  16. C.A.R. Hoare: “A model for communicating sequential processes”, Techn. Rep. PRG-22, Programming Research Group, Oxford Univ. (1981)

    Google Scholar 

  17. M. Jantzen: “The power of synchronizing operations on strings”, Theoret. Comput. Sci. 14 (1981) 127–154

    Article  MATH  MathSciNet  Google Scholar 

  18. K. Jensen: “A method to compare the descriptive power of different types of Petri nets”, MFCS B0, Lecture Notes in Comput. Sci. 88 (1980) 348–361

    Google Scholar 

  19. RM. Keller: “Formal verification of parallel programs”, CACM 19 (1976) 371–384

    MATH  Google Scholar 

  20. R Milner: “A Calculus of Communicating Systems”, Lecture Notes in Comput. Sci 92 (1980)

    Google Scholar 

  21. R Milner: “On relating synchrony and asynchrony”, CSR-75–80, Comput. Sci. Dept., Edinburgh Univ. (1981)

    Google Scholar 

  22. R. Milner: “Calculi for synchrony and asynchrony”, Theoret. Comput. Sci. 25 (1983) 267–310

    Article  MATH  MathSciNet  Google Scholar 

  23. R. Milner: “A complete inference system for a class of regular behaviour”, J. of Computer and Systems Sciences 28 (1984) 439–466

    Article  MATH  MathSciNet  Google Scholar 

  24. M. Nivat: “Synchronization of concurrent processes”, in “Formal Language Theory: Perspective and Open Problems”, R.V. Book, ed., A.P. (1980) 429454

    Google Scholar 

  25. W.F. Ogden, W.E. Riddle & W.C. Rands: “Complexity of expressions allowing concurrency”, 5 th ACM POPL (1978) 185–194

    Google Scholar 

  26. D. Park: “Concurrency and automata on infinite sequences”, 5th GI Conf., Lecture Notes in Comput. Sci. 104 (1981) 167–183

    Google Scholar 

  27. J.L. Peterson: “Petri Nets”, ACM Computing Surveys 9 (1977) 223–252

    Article  MATH  Google Scholar 

  28. G. Plotkin: “A structural approach to operational semantics”, Daimi FN-19, Comput. Sci. Dept., Aarhus Univ. (1981)

    Google Scholar 

  29. G. Plotkin: “An operational semantics for CSP”, in “Formal Description of Programming Concepts II”, D. Bjorner, ed, North- Holland (1982) 199–225

    Google Scholar 

  30. A.C. Shaw: “Software description with flow expressions”, IEEE Trans. on Software Engineering 4 (1978) 242–254

    Article  Google Scholar 

  31. J. Sifakis: “Property preserving homomorphisms of transition systems”, Logics of Programs, Lecture Notes in Comput. Sci. 164 (1984) 458–473

    MathSciNet  Google Scholar 

  32. R. de Simone: “Langages infinitaires et produit de mixage”, Theoret. Comput. Sci. 31 (1984) 83–100

    Google Scholar 

  33. R. de Simone: “Calculabilité et expressivité dans l’algèbre de processus parallèles Meije”, Thèse de 3e cycle, Univ. Paris 7 (1984)

    Google Scholar 

  34. R. de Simone: “Note on Meije and SCCS: infinite sum operators ys non-guarded definitions”, Theoret. Comput. Sci. 30 (1984) 133–138

    Google Scholar 

  35. G. Winskel: “Synchronization trees”, CMU-CS-83–139, Comput. Sci. Dept., Carnegie-Mellon Univ. (1983) s.a. ICALP 83, Lecture Notes in Comput. Sci. 154 (1983) 695–711

    MathSciNet  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. INRIA — Sophia Antipolis, 06560, Valbonne, France

    G. Boudol

Authors
  1. G. Boudol
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Editors and Affiliations

  1. L.I.T.P., Université Paris 7, 2, Place Jussieu, 75251, Paris, France

    Krzysztof R. Apt

Rights and permissions

Reprints and permissions

Copyright information

© 1985 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Boudol, G. (1985). Notes on Algebraic Calculi of Processes. In: Apt, K.R. (eds) Logics and Models of Concurrent Systems. NATO ASI Series, vol 13. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-82453-1_9

Download citation

  • DOI: https://doi.org/10.1007/978-3-642-82453-1_9

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-642-82455-5

  • Online ISBN: 978-3-642-82453-1

  • eBook Packages: Springer Book Archive

Publish with us

Policies and ethics

Search

Navigation