×

zbMATH — the first resource for mathematics

Testing equivalences for processes. (English) Zbl 0985.68518
Summary: Given a set of processes and a set of tests on these processes we show how to define in a natural way three different equivalences on processes. These equivalences are applied to a particular language CCS. We give associated complete proof systems and fully abstract models. These models have a simple representation in terms of trees.

MSC:
68Q55 Semantics in the theory of computing
68Q10 Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.)
Software:
Ada95
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Bloom, S.: Varieties of ordered algebras. J. comput. Systems sci. 13, 200-212 (1976) · Zbl 0337.06008
[2] Brinch-Hansen, P.: The programming language concurrent Pascal. Ieee tsi 1, 99-205 (1975) · Zbl 0304.68008
[3] Brinch-Hansen, P.: Distributed processes: A concurrent programming concept. Comm. ACM 21, No. 11, 934-941 (1978) · Zbl 0393.68028
[4] Courcelle, B.; Nivat, M.: Algebraic families of interpretations. Proc. 17th FOCS ann. Symp. (1976) · Zbl 0384.68016
[5] Darondeau, Ph.: An enlarged definition and complete axiomatization of observational congruence of finite processes. Lecture notes in computer science 137, 47-62 (1982) · Zbl 0482.68025
[6] De Nicola, R.: A complete set of axioms for a theory of communicating sequential processes. Lecture notes in computer science 158, 115-126 (1983)
[7] R. De Nicola, Ph.D. Thesis, Dept. of Computer Science, Univ. of Edinburgh, forthcoming.
[8] Francez, N.; Hoare, C. A. R.; Lehmann, D. J.; De Roever, W. -P.: Semantics of nondeterminism, concurrency and communication. J. comput. System sci. 19, 290-308 (1979) · Zbl 0434.68066
[9] Gordon, M.: The denotational description of programming languages. (1979) · Zbl 0412.68004
[10] Goguen, J. A.; Thatcher, J. W.; Wright, J. B.: Initial algebra semantics and continuous algebras. J. ACM 24, No. 1, 68-95 (1977) · Zbl 0359.68018
[11] Guessarian, I.: Algebraic semantics. Lecture notes in computer science 99 (1981) · Zbl 0474.68010
[12] Hennessy, M.: Powerdomains and nondeterministic recursive definitions. Lecture notes in computer science 137, 178-193 (1982) · Zbl 0486.68009
[13] Hennessy, M.; Plotkin, G.: A term model for CCS. Lecture notes in computer science 88, 261-274 (1980) · Zbl 0479.68011
[14] Hennessy, M.: A term model for synchronous process. Information and control 51, No. 1, 58-75 (1981) · Zbl 0503.68022
[15] Hennessy, M.; Milner, R.: On observing nondeterminism and concurrency. Lecture notes in computer science 85, 299-309 (1980) · Zbl 0441.68018
[16] Hoare, C. A. R.: Communicating sequential processes. Comm. ACM 21, No. 8 (1978) · Zbl 0383.68028
[17] Hoare, C. A. R.: A model for communicating sequential processes. Tech. monograph prg-22 (1981) · Zbl 0485.68025
[18] Hoare, C. A. R.; Brookes, S. D.; Roscoe, A. D.: A theory of communicating sequential processes. Tech. monograph prg-16 (1981) · Zbl 0628.68025
[19] Ichbiah, J. D.: Reference manual for the ADA programming language. (July 1980)
[20] Kennaway, J. K.; Hoare, C. A. R.: A theory of nondeterminism. Lecture notes in computer science 85, 338-350 (1980) · Zbl 0444.68027
[21] Kennaway, J. K.: Formal semantics of nondeterminism and parallelism. Ph.d. thesis (1981)
[22] Lampson, B. W.; Redell, D. D.: Experience with processes and monitors in mesa. Comm. ACM 23, No. 2, 105-107 (1980)
[23] Milner, E.: A calculus of communicating systems. Lecture notes in computer science 92 (1980) · Zbl 0452.68027
[24] Plotkin, G.: A powerdomain construction. SIAM J. Comput. 5, 452-486 (1976) · Zbl 0355.68015
[25] Rounds, W. C.; Brookes, S. D.: Possible futures, acceptances, refusals and communicating processes. Proc. 22nd FOCS ann. Symp. (1981)
[26] Scott, D. S.: Data types as lattices. SIAM J. Comput. 5, No. 3 (1973) · Zbl 0337.02018
[27] Smyth, M. B.: Power domains. J. comput. System sci. 2, 23-26 (1978) · Zbl 0391.68011
[28] Stoy, J.: Denotational semantics: the Scott-strachey approach to programming language theory. (1977) · Zbl 0503.68059
[29] Wirth, N.: Programming in module-2. (1983) · Zbl 0513.68006
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.