×

zbMATH — the first resource for mathematics

Designing equivalent semantic models for process creation. (English) Zbl 0652.68029
This paper presents operational and denotational semantic models for languages with process creation. Systematically, two aspects of those languages are highlighted: (i) uniformity (Are the elementary actions interpreted or not?), and (ii) dynamics (Is there a fixed number of created (parallel) processes or not?), resulting in the study of four basic languages. The operational semantics are based on Hennessy & Plotkin-style transition systems; the denotational semantics employ metric structures and involve so-called continuations. The paper provides a full analysis of the relationship between the two types of semantics for the four languages considered.
Reviewer: J.-J.Ch.Meyer

MSC:
68Q99 Theory of computing
68Q60 Specification and verification (program logics, model checking, etc.)
Software:
Simula 67; POOL
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] The Programming Language Ada Reference Manual, American National Standards Institute, ANSI/MIL-STD-1815A-1983
[2] Agha, G., Semantic considerations in the actor paradigm of concurrent computations, (), 151-179
[3] America, P., Definition of the programming language POOL-T, (), Doc. No. 91
[4] America, P., Rationale for the design of POOL, (), Doc. No. 53
[5] America, P., Objected-oriented programming: a Theoretician’s introduction, EATCS bull., 29, 69-84, (June 1986)
[6] America, P.; De Bakker, J.W.; Kok, J.N.; Rutten, J.J.M.M., Conf. Rec. 13th Symp. on Principles of Programming Languages, St. Petersburg, FL, Operational semantics of a parallel object-oriented language, 194-208, (January 13-15, 1986)
[7] America, P.; De Bakker, J.W.; Kok, J.N.; Rutten, J.J.M.M., A denotational semantics of a parallel object-oriented language, () · Zbl 0695.68058
[8] America, P.; Rutten, J.J.M.M., Solving reflexive domain equations in a category of complete metric spaces, (), 254-288
[9] Apt, K.R., Recursive assertions and parallel programs, Acta inform., 15, 219-232, (1981) · Zbl 0436.68009
[10] Apt, K.R., Formal justification of a proof system for communicating sequential processes, J. ACM, 30, 1, 197-216, (1983) · Zbl 0503.68021
[11] De Bakker, J.W.; Bergstra, J.A.; Klop, J.W.; Meyer, J.-J.Ch., Linear time and branching time semantics for recursion with merge, Theoret. comput. sci., 34, 135-156, (1984) · Zbl 0985.68517
[12] De Bakker, J.W.; Kok, J.N.; Meyer, J.-J.Ch.; Olderog, E.-R.; Zucker, J.I., Contrasting themes in the semantics of imperative concurrency, (), 51-121, Lecture Notes in Computer Science · Zbl 0606.68019
[13] De Bakker, J.W.; Meyer, J.-J.Ch., Order and metric in the stream semantics of elemental concurrency, Acta inform., 24, 491-511, (1987) · Zbl 0607.68014
[14] De Bakker, J.W.; Meyer, J.-J.Ch.; Olderog, E.-R., Infinite streams and finite observations in the semantics of uniform concurrency, Theoret. comput. sci., 49, 2, 3, 87-112, (1987) · Zbl 0623.68016
[15] De Bakker, J.W.; Meyer, J.-J.Ch.; Olderog, E.-R.; Zucker, J.I., Proc. 17th ACM Symp. on the Theory of Computing, Providence, RI, Transition systems, infinitary languages and the semantics of uniform concurrency, 252-262, (1985)
[16] De Bakker, J.W.; Meyer, J.-J.Ch.; Olderog, E.-R.; Zucker, J.I., Transition systems, metric spaces and ready sets in the semantics of uniform concurrency, J. comput. system sci., 36, 158-224, (1988), (full version of [15]) · Zbl 0652.68028
[17] De Bakker, J.W.; Zucker, J.I., Processes and the denotational semantics of concurrency, Inform. and control, 54, 70-120, (1982) · Zbl 0508.68011
[18] Bergstra, J.A.; Klop, J.W., Process algebra for synchronous communication, Inform. and control, 60, 109-137, (1984) · Zbl 0597.68027
[19] De Boer, F.S., A proof rule for process creation, (), 23-50
[20] Broy, M., Fixed point theory for communication and concurrency, (), 125-146
[21] Broy, M., Applicative real-time programming, (), 259-264
[22] De Bruin, A.; Böhm, A.P.W., The denotational semantics of dynamic networks of processes, ACM trans. programming languages and systems, 7, 4, 656-679, (1985) · Zbl 0577.68041
[23] Clinger, W.D., Foundations of actor semantics, ()
[24] Dahl, O.-J.; Myhrhaug, B.; Nygaard, K., Simula 67, ()
[25] Dugundji, J., Topology, (1966), Allyn & Bacon Newton, MA
[26] Engelking, R., General topology, (1977), Polish Scientific Publishers Warsaw
[27] Gierz, G.; Hofmann, K.H.; Keimel, K.; Lawson, J.D.; Mislove, M.; Scott, D.S., A compendium of continuous lattices, (1980), Springer Berlin · Zbl 0452.06001
[28] Hahn, H., Reelle funktionen, (1948), Chelsea New York · JFM 58.0242.05
[29] Hennessy, M.; Plotkin, G.D., Full abstraction for a simple parallel programming language, (), 108-120, Lecture Notes in Computer Science · Zbl 0457.68006
[30] Hewitt, C., Viewing control structures as patterns of passing messages, Artificial intelligence, 8, 323-364, (1977)
[31] Hoare, C.A.R., Communicating sequential processes, Comm. ACM, 21, 8, 666-677, (1978) · Zbl 0383.68028
[32] Hoare, C.A.R., Communicating sequential processes, (1985), Prentice-Hall Englewood Cliffs, NJ · Zbl 0637.68007
[33] Meyer, J.-J.Ch., Merging regular processes by means of fixed point theory, Theoret. comput. sci., 45, 193-260, (1986) · Zbl 0602.68025
[34] Meyer, J.-J.Ch.; de Vink, E.P., Applications of compactness in the smyth powerdomain of streams, (), 241-255 · Zbl 0652.68027
[35] Nivat, M., Infinite words, infinite trees, infinite computations, (), 3-52 · Zbl 0423.68012
[36] Niwinski, D., Fixed point semantics for algebraic (tree) grammars, (), 384-396, Lecture Notes in Computer Science
[37] Plotkin, G.D., A powerdomain construction, SIAM J. comput., 5, 3, 452-487, (1976) · Zbl 0355.68015
[38] Plotkin, G.D., A structural approach to operational semantics, () · Zbl 0512.68012
[39] Plotkin, G.D., An operational semantics for CSP, (), 199-223 · Zbl 0512.68012
[40] Pnueli, A., Linear and branching structures in the semantics and logics of reactive systems, (), 15-32
[41] Rounds, W.C., On the relationship between Scott domains, synchronization trees and metric spaces, () · Zbl 0203.30103
[42] Saraswat, V.A., Conf. Rec. 14th Symp. on Principles of Programming Languages, München, Fed. Rep. Germany, The concurrent logic programming language CP: definition and operational semantics, 49-62, (January 21-23, 1987)
[43] Smolka, S.A.; Strom, R.E., A CCS semantics for NIL, (), 347-373
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.