×
de Bakker, J. W.; de Vink, E. P.

Denotational models for programming languages: Applications of Banach’s fixed point theorem. (English) Zbl 0933.68086

Topology Appl. 85, No. 1-3, 35-52 (1998).
Summary: For an abstract programming language both a linear and a branching denotational semantics are developed. The main instrument for the construction of the two models and for the semantical operators involved is the classical Banach fixed point theorem. Via higher-order transformations the various semantical definitions are justified by their characterization as – necessarily unique – fixed points of contractions on a complete metric space. Additionally the Banach theorem proves itself useful in relating the two models presented.

Cited in 14 Documents

MSC:

68Q55 Semantics in the theory of computing
03B70 Logic in computer science
68Q10 Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.)
PDFBibTeX XMLCite
\textit{J. W. de Bakker} and \textit{E. P. de Vink}, Topology Appl. 85, No. 1--3, 35--52 (1998; Zbl 0933.68086)
Full Text: DOI

References:

[1] Arnold, A.; Naudin, P.; Nivat, M., On semantics of nondeterministic recursive program schemes, (Nivat, M.; Reynolds, J. C., Algebraic Methods in Semantics (1985), Cambridge University Press), 1-33 · Zbl 0577.68032
[2] America, P.; Rutten, J. J.M. M., A parallel object-oriented language: design and semantic foundations, (Ph.D. Thesis (1989), Vrije Universiteit Amsterdam) · Zbl 0760.68044
[3] America, P.; Rutten, J. J.M. M., Solving reflexive domain equations in a category of complete metric spaces, J. Comput. System Sci., 39, 343-375 (1989) · Zbl 0717.18002
[4] Baire, R., Sur la représentation des fonctions discontinues, Acta Math., 32, 97-176 (1909) · JFM 40.0443.03
[5] Banach, S., Sur les opérations dans les ensembles abstraits et leurs applications aux équations intégrales, Fund. Math., 3, 133-181 (1922) · JFM 48.0201.01
[6] (de Bakker, J. W.; Rutten, J. J.M. M., Ten Years of Concurrency Semantics, Selected papers of the Amsterdam Concurrency Group (1992), World Scientific)
[7] van Breugel, F. C., Topological models in comparative semantics, (Ph.D. Thesis (1994), Vrije Universiteit Amsterdam)
[8] de Bakker, J. W.; de Vink, E. P., Control Flow Semantics (1996), MIT Press · Zbl 0971.68099
[9] de Bakker, J. W.; de Vink, E. P., A metric approach to control flow semantics, (Proc. 11th Summer Conference on General Topology and Applications. Proc. 11th Summer Conference on General Topology and Applications, Ann. New York Acad. Sci. (1997)) · Zbl 0971.68099
[10] de Bakker, J. W.; Zucker, J. I., processes and the denotational semantics of concurrency, Inform. and Control, 54, 70-120 (1982) · Zbl 0508.68011
[11] Eliëns, A., DLP: A Language for Distributed Logic Programming: Design, Semantics and Implementation (1992), Wiley
[12] Hausdorff, F., Grundzüge der Mengenlehre (1914), Leipzig · JFM 45.0123.01
[13] Horita, E., Fully abstract models for concurrent languages, (Ph.D. Thesis (1993), Vrije Universiteit Amsterdam) · Zbl 0824.68060
[14] Hennessy, M.; Plotkin, G. D., Full abstraction for a simple parallel programming language, (Bečvář, J., Proc. 8th Symposium on Mathematical Foundations of Computer Science. Proc. 8th Symposium on Mathematical Foundations of Computer Science, Lecture Notes in Computer Science, 74 (1979), Springer: Springer Berlin), 108-120 · Zbl 0457.68006
[15] Knaster, B., Un théorème sur les fonctions d’ensembles, Ann. Soc. Math. Polonae, 6, 133-134 (1928) · JFM 54.0091.04
[16] Kok, J. N., Semantic models for parallel computation in data flow, logic- and object-oriented programming, (Ph.D. Thesis (1989), Vrije Universiteit Amsterdam)
[17] Kok, J. N.; Rutten, J. J.M. M., Contractions in comparing concurrency semantics, Theoret. Comput. Sci., 76, 179-222 (1990) · Zbl 0707.68054
[18] Kuratowski, K., Sur une méthode de métrisation complète des certains espaces d’ensembles compacts, Fund. Math., 43, 114-138 (1956) · Zbl 0071.38402
[19] Majster-Cederbaum, M. E.; Zetzsche, F., Towards a foundation for semantics in complete metric spaces, Inform. and Comput., 90, 217-243 (1991) · Zbl 0773.68050
[20] Reed, G. M.; Roscoe, A. W., A timed model for communicating sequential processes, Theoret. Comput. Sci., 58, 249-261 (1988) · Zbl 0655.68031
[21] Tarski, A., A lattice-theoretical fixpoint theorem and its applications, Pacific J. Math., 5, 285-309 (1955) · Zbl 0064.26004
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.