zbMATH — the first resource for mathematics

On reduction-based process semantics. (English) Zbl 0871.68122
Summary: A formulation of semantic theories for processes which does not rely on the notion of observables or convergence is studied. The new construction is based solely on a reduction relation and equational reasoning, but can induce meaningful theories for processes, both in weak and strong settings. The resulting theories in many cases coincide with, and sometimes generalise, observation-based formulation of behavioural equivalence. The basic construction of reduction-based theories is studied, taking a simple name passing calculus (called $$\nu$$-calculus) and its extensions as an example. Results concerning the application of our construction to other calculi are also briefly discussed.

MSC:
 68Q55 Semantics in the theory of computing
Full Text:
References:
 [1] Abramsky, S., The lazy lambda calculus, (), 65-116, 65-116 [2] Barendregt, H., The lambda calculus: its syntax and semantics, (1984), North-Holland Amsterdam · Zbl 0551.03007 [3] Berry, G.; Boudol, G., The chemical abstract machine, Theoret. comput. sci., 96, 217-248, (1992) · Zbl 0747.68013 [4] Boudol, G., Asynchrony and π-calculus, () [5] De Nicola, R.; Hennessy, M., Testing equivalences for processes, Theoret. comput. sci., 34, 1, 89-133, (1984) · Zbl 0985.68518 [6] Engberg, U.; Nielsen, M., A calculus of communicating systems with label passing, () [7] Honda, K.; Tokoro, M., An object calculus for asynchronous communication, (), 133-147 [8] Honda, K.; Yoshida, N., Combinatory representation of mobile processes, (), 348-360 [9] Honda, K.; Yoshida, N., Replication in concurrent combinators, (), 786-805 · Zbl 0942.03510 [10] Honda, K., A study of the ν-calculus and its combinatory representation, () [11] Howe, D., Equality in lazy computational systems, (), 198-203 [12] Jones, C.B., A pi-calculus semantics for an object-based design notation, (), 158-173 [13] Lévy, J.-J., Optimal reductions in the lambda-calculus, (), 159-191 [14] Longo, G., Set theoretical models of lambda calculus: theory, expansions and isomorphisms, Ann. pure appl. logic, 24, 153-188, (1983) · Zbl 0513.03009 [15] Milner, R., Fully abstract models of the λ-calculi, Theoret. comput. sci., 4, 1-22, (1977) · Zbl 0386.03006 [16] Milner, R., () [17] Milner, R., Communication and concurrency, (1989), Prentice-Hall Englewood cliffs, NJ · Zbl 0683.68008 [18] Milner, R., Functions as processes, Math. struct. comput. sci., 2, 2, 119-146, (1992) · Zbl 0773.03012 [19] Milner, R., Polyadic π-calculus: a tutorial, () [20] Milner, R.; Parrow, J.G.; Walker, D.J., A calculus of mobile processes, Inform. and comput., 100, 1, 1-77, (1992) · Zbl 0752.68037 [21] Milner, R.; Sangiorgi, D., Barbed bisimulation, (), 685-695 [22] Ong, C-H.L., The lazy lambda calculus: an investigation into the foundation of functional programming, () [23] Park, D., (), 167-183 [24] Takeuchi, K.; Honda, K.; Kubo, M., An interaction-based language and its typing system, (), 398-413 [25] Thomsen, B., A calculus of higher order communicating systems, (), 143-154 [26] Yoshida, N., Optimal reduction in weak λ-calculus with shared environemnts, (), 243-252
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.