Algebraic formulations of trace theory | SpringerLink
Skip to main content
Springer Nature Link
Log in

Algebraic formulations of trace theory

  • Selected Presentations
  • Conference paper
  • First Online:
CONCUR '91 (CONCUR 1991)

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

Included in the following conference series:

Abstract

In this paper mathematical models are given for Trace Theory as described in [Rem85] and [Kal86]. They model a process by a trace structure: a pair consisting of an alphabet and a trace set over this alphabet. We show that in fact two incompatible process models are used, and we devise a new model that has all essential characteristics of the two former models. A complete axiomatization of this model is given. It is shown that a distinction between successful and unsuccessful termination is needed to effectuate associativity of parallel composition with communication in the presence of sequential composition. Two operators generating infinite processes are added, which makes a verification of the alternating bit protocol possible.

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

Access this chapter

Log in via an institution

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. Aceto, L., and M. Hennessy: Termination, Deadlock and Divergence. Report 6/88, Computer Science, Univ. of Sussex, Brighton BN1 9QH. 1988.

    Google Scholar 

  2. Baeten, J.M.C. and W.P. Weijland: Process Algebra. Cambridge University Press, Cambridge, 1990.

    Google Scholar 

  3. Baeten, J.M.G. and R.J. van Glabbeek: Abstraction and Empty Process in Process Algebra. Fund. Inf. XII, pp. 221–241. 1989.

    Google Scholar 

  4. Bakker, J.W. de, and J.-J.Ch. Meyer: Metric Semantics for Concurrency. BIT 28, pp. 504–529. 1988.

    Google Scholar 

  5. Bergstra, J.A., and J.W. Klop: The algebra of Recursively Defined Processes and the the Algebra of Regular Processes. Proceedings 11th ICALP, LNCS 172, pp. 82–95. 1984.

    Google Scholar 

  6. Bergstra, J.A., and J.W. Klop: Verification of an Alternating Bit Protocol by means of Process Algebra. CWI report CS-R8404, Amsterdam. 1984.

    Google Scholar 

  7. Bergstra, J.A., and J.W. Klop: Algebra of Communicating Processes with Abstraction. TCS 37(1): pp. 77–121. 1985.

    Google Scholar 

  8. Bergstra, J.A., J.W. Klop, and E.-R. Olderog: Readies and Failures in the Algebra of Communicating Processes. Siam J. Comput. 17(6): pp. 1134–1177. 1988.

    Google Scholar 

  9. Drost, N.: Algebraic Formulations of Trace Theory. Report P9004, Programming Research Group, Dept. of Math. and Comp. Sci., Univ. of Amsterdam. 1990.

    Google Scholar 

  10. Glabbeek, R.J. van: Comparative Concurrency Semantics, with Refinement of Actions. Ph.D.Thesis, Free University, Amsterdam. 1990.

    Google Scholar 

  11. Hoare, C.A.R.: Communicating Sequential Processes. Prentice Hall, London. 1985.

    Google Scholar 

  12. Kaldewaij, A.: A Formalism for Concurrent Processes. Ph.D.Thesis, Technical University, Eindhoven. 1986.

    Google Scholar 

  13. Milner, R.: Communication and Concurrency. Prentice Hall, London. 1989.

    Google Scholar 

  14. Olderog, E.-R. and C.A.R. Hoare: Specification-Oriented Semantics for Communicating Processes. Acta Inf. 23, pp. 9–66. 1986.

    Google Scholar 

  15. Rem, M.: Concurrent Computations and VLSI Circuits. in: M. Broy (ed.): Control Flow and Data Flow: Concepts of Distributed Programming, pp. 399–437. Springer, Berlin. 1985.

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Programming Research Group, University of Amsterdam, P.O.Box 41882, 1009 DB, Amsterdam, The Netherlands

    N. J. Drost

Authors
  1. N. J. Drost
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Jos C. M. Baeten Jan Frisco Groote

Rights and permissions

Reprints and permissions

Copyright information

© 1991 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Drost, N.J. (1991). Algebraic formulations of trace theory. In: Baeten, J.C.M., Groote, J.F. (eds) CONCUR '91. CONCUR 1991. Lecture Notes in Computer Science, vol 527. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-54430-5_87

Download citation

  • DOI: https://doi.org/10.1007/3-540-54430-5_87

  • Published:

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-540-54430-2

  • Online ISBN: 978-3-540-38357-4

  • eBook Packages: Springer Book Archive

Publish with us

Policies and ethics

Search

Navigation