A theory of testing for ACP | SpringerLink
Skip to main content
Springer Nature Link
Log in

A theory of testing for ACP

  • 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

This paper introduces a process algebra which incorporates the auxiliary operators of ACP, [BK85], and is tailored towards algebraic verifications in the theory of testing equivalence. The process algebra we consider is essentially a version of ACP with the empty process in which the nondeterministic choice operators familiar from TCSP, [BHR84], and TCCS, [DH87], are used in lieu of the internal action τ and the single choice operator favoured by CCS, [Mil89], and ACP. We present a behavioural semantics for the language based upon a natural notion of testing equivalence, [DH84], and show that, contrary to what happens in a setting with the internal action τ, the left-merge operator is compatible with it. A complete equational characterization of the behavioural semantics is given for finite processes, thus providing an algebraic theory supporting the use of the auxiliary operators of ACP in algebraic verifications for testing equivalence. Finally we give a fully-abstract denotational model for finite processes with respect to the testing preorder based on a variation on Hennessy's Acceptance Trees suitable for our language.

This work has been supported by a grant from the United Kingdom Science and Engineering Research Council and by the Esprit BRA project CONCUR.

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

6 References

  1. D. Austry and G. Boudol, Algebre de Processus et synchronisations, TCS 30(1), pp. 91–131

    Google Scholar 

  2. L. Aceto, A theory of Testing for ACP, Report 3/90, Dept. of Computer Science, University of Sussex, May 1990

    Google Scholar 

  3. L. Aceto and M. Hennessy, Termination, Deadlock and Divergence, Report 6/88, Dept. of Computer Science, University of Sussex, 1988. To appear in the Journal of the ACM.

    Google Scholar 

  4. J. C. M. Baeten and R. J. van Glabbeek, Abstraction and Empty Process in Process Algebra, Report CS-R8721, CWI Amsterdam, 1987 (to appear in Fundamenta Informaticae)

    Google Scholar 

  5. S. D. Brookes, C. A. R. Hoare and A. W. Roscoe, A Theory of Communicating Sequential Processes, JACM 31,3, pp. 560–599, 1984

    Google Scholar 

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

    Google Scholar 

  7. J. A. Bergstra, J. W. Klop and E.-R. Olderog, Failures Without Chaos: a New Process Semantics for Fair Abstraction, Formal Description of Programming Concepts-III (M. Wirsing ed.), North-Holland, 1987

    Google Scholar 

  8. J. C. M. Baeten and F. Vaandrager, An Algebra for Process Creation, Report CS-R8907, CWI, Amsterdam, 1989

    Google Scholar 

  9. I. Castellani and M. Hennessy, Distributed Bisimulations, JACM, October 1989

    Google Scholar 

  10. R. de Nicola, Two Complete Sets of Axioms for a Theory of Communicating Sequential Processes, Information and Control 64(1–3), pp. 136–176, 1985

    Google Scholar 

  11. R. De Nicola and M. Hennessy, Testing Equivalences for Processes, TCS 34,1, pp. 83–134, 1987

    Google Scholar 

  12. R. de Nicola and M. Hennessy, CCS without r's, in Proceedings TAPSOFT 87, LNCS 249, pp. 138–152, Springer-Verlag, 1987

    Google Scholar 

  13. R. van Glabbeek and F. Vaandrager, Modular Specifications in Process Algebra-with Curious Queues, Report CS-R8821, CIW, Amsterdam, 1988

    Google Scholar 

  14. I. Guessarian, Algebraic Semantics, LNCS 99, Springer-Verlag, 1981

    Google Scholar 

  15. M. Hennessy, Algebraic Theory of Processes, MIT Press, 1988

    Google Scholar 

  16. M. Hennessy and A. Ingólfsdóttir, A Theory of Communicating Processes with Value Passing, Report 3/89, University of Sussex, 1989

    Google Scholar 

  17. M. Hennessy and R. Milner, Algebraic Laws for Nondeterminism and Concurrency, JACM 32,1, pp. 137–161, 1985

    Google Scholar 

  18. C. A. R. Hoare, Communicating Sequential Processes, Prentice-Hall, 1985

    Google Scholar 

  19. R. Keller, Formal Verification of Parallel Programs, C. ACM 19,7, pp. 561–572, 1976

    Google Scholar 

  20. R. Milner, Communication and Concurrency, Prentice-Hall, 1989

    Google Scholar 

  21. F. Moller, Axioms for Concurrency, Ph. D. Thesis, University of Edinburgh, 1989

    Google Scholar 

  22. D. Park, Concurrency and Automata on Infinite Sequences, Lecture Notes in Computer Science vol. 104, Springer-Verlag, 1981

    Google Scholar 

  23. G. Plotkin, A Structural Approach to Operational Semantics, Report DAIMI FN-19, Computer Science Dept., Aarhus University, 1981

    Google Scholar 

  24. F. Vaandrager, Process Algebra Semantics of POOL, to appear in Applications of Process Algebra (J.C.M. Baeten ed.), pp. 173–236, 1990

    Google Scholar 

  25. F. Vaandrager, Two Simple Protocols, to appear in Applications of Process Algebra (J.C.M. Baeten ed.), pp. 237–260, 1990

    Google Scholar 

  26. J. L. M. Vrancken, The Algebra of Communicating Processes with Empty Process, Report FVI 86-01, Dept. of Computer Science, University of Amsterdam, 1986

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. INRIA-Sophia Antipolis, F-06560, Valbonne Cedex, France

    Luca Aceto

  2. Aalborg University Centre, Aalborg, Denmark

    Anna Ingólfsdóttir

Authors
  1. Luca Aceto
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Anna Ingólfsdóttir
    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

Aceto, L., Ingólfsdóttir, A. (1991). A theory of testing for ACP. 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_82

Download citation

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

  • 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