Abstract
In denotational semantics the meaning of a construct of a programming language is modelled by an element of a (semantic) domain. Domains are essentially ordered sets, in which every element may be approximated by a directed set of compact elements.
We propose a new approach to domain construction using directed systems of certain finite subsets of a domain called sprouts. Every element of the domain can be considered as growing out from the sprouts, i.e. it can be uniquely approximated by an element of any given sprout. Sprouts consist only of compact elements and every compact element is contained in some of the sprouts.
The directed system of sprouts fits neatly to the usual domain constructions, so we are able to describe the approximations of an element of a composed domain by the corresponding approximations in the component domains very exactly. Furthermore, we get a constructive and less abstract description of profinite domains than given by C. Gunter with one added feature: Given a domain functional τ, the inverse limit of the retraction sequence 1, τ[1], τ2[1], ... is indeed the least of a certain subset of fixed points of τ, namely of those being the vertex of a cone that is „definable” in some sense.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
References
Gunter C.A.: Profinite Solutions for Recursive Domain Equations. CMU-CS-85-107, Carnegie-Mellon University, Pittsburgh, Pa. (1985)
Schmidt G.: Semantik der Programmiersprachen. Vorlesungsskriptum, Wintersemester 1985/86
Schmidt G., Berghammer R., Zierer H.: Beschreibung semantischer Bereiche mit Keimen. In: Radermacher F.J., Wirsing M. (eds.): Berichte aus den Informatikinstituten, 9. Jahrestagung der österreichischen Gesellschaft für Informatik, 27./28. Februar 1986. Conference Report MIP-8604, Universität Passau (1986), 199–216
Schmidt G., Berghammer R., Zierer H.: Describing Semantic Domains with Sprouts. Technical Report TUM-I8611, Institut für Informatik, Technische Universität München (1986)
Scott D.S.: Domains for Denotational Semantics. In: Nielsen M., Schmidt E.M. (eds.): 9th Int. Coll. on Automata, Languages and Programming. Lecture Notes in Computer Science 140, Springer (1982), 577–613
Smyth M.B.: The Largest Cartesian Closed Category of Domains. Theoretical Computer Science 27 (1983), 109–119
Smyth M.B., Plotkin G.D.: The Category-Theoretic Solution of Recursive Domain Equations. SIAM Journal on Computing 11 (1982), 761–783
Winskel G., Larsen K.G.: Using Information Systems to Solve Recursive Domain Equations Effectively. In: Kahn G., MacQueen D.B., Plotkin G. (eds.): Semantics of Data Types. Lecture Notes in Computer Science 173, Springer (1984), 109–130
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1987 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Schmidt, G., Berghammer, R., Zierer, H. (1987). Describing semantic domains with sprouts. In: Brandenburg, F.J., Vidal-Naquet, G., Wirsing, M. (eds) STACS 87. STACS 1987. Lecture Notes in Computer Science, vol 247. Springer, Berlin, Heidelberg. https://doi.org/10.1007/BFb0039614
Download citation
DOI: https://doi.org/10.1007/BFb0039614
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-17219-2
Online ISBN: 978-3-540-47419-7
eBook Packages: Springer Book Archive