Abstract
The purpose of the theory of domains is to give models for spaces on which to define computable functions. The kinds of spaces needed for denotational sematics involve not only spaces of higher type (e.g. function spaces) but also spaces defined recursively (e.g. reflexive domains). Also required are many special domain constructs (or functors) in order to create the desired structures. There are several choices of a suitable category of domains, but the basic one which has the simplest properties is the one sometimes called consistently complete algebraic cpo's. This category of domains is studied in this paper from a new, and it is to be hoped, simpler point of view incorporating the approaches of many authors into a unified presentation. Briefly, the domains of elements are represented set theoretically with the aid of structures called information systems. These systems are very familiar from mathematical logic, and their use seems to accord well with intuition. Many things that were done previously axiomatically can now be proved in a straightfoward way as theorems. The present paper discusses many examples in an informal way that should serve as an introduction to the subject.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Bibliography
Barendregt, H.P. 1981 The Lambda Calculus: Its Syntax And Semantics. Studies in Logic, vol. 103, North Holland, New York (1981), xiv+615pp.
Berry, G. and Curien, P.L. 1981 Sequential algorithms on concrete data structures. Report of Ecole Nationale Supérience des Mines de Paris, Centre de Mathematiques Appliquées, Sophia Antipolis (1981).
Engeler, E. 1979 Algebras and combinators. Berichte des Instituts fur Informatik, Nr. 32, ETH Zurich, 12pp.
Gierz, G., Hofmann, K. H., Keimel, K., Lawson, J. D., Mislove, M. and Scott, D.S. 1980 A Compendium of Continuous Lattices. Springer-Verlag (1980), 371 pp.
Gordon, M. J., Milner, A.J.R. and Wadsworth, C.P. 1979 Edinburgh LCF. Springer-Verlag Lecture Notes in Computer Science, vol. 78 (1979), 159 pp.
Gordon, M. 1979 The Denotational Description of Programming Languages, An Introduction. Springer-Verlag (1979).
Greibach, S. A. 1981 Formal languages: origins and directions. Annals of the History of Computing, vol. 3 (1981), pp. 14–41.
Kahn, G. and Plotkin, G. 1978 Domaines Concrètes. Rapport IRIA-LABORIA, No. 336 (1978).
Longo, G. 1982 Set-theoretical models of lambda-calculus: theories, expansions, isomorphisms. Preprint, Pisa (1982), 46pp.
Meyer, A. R. 1981 What is a model of the lambda calculus?. (Expanded version) Preprint, MIT (1981), 40 pp.
Nielsen, M., Plotkin, G. and Winskel, G. 1981 Petri nets, event structures and domains. Theoretical Computer Science, vol. 13(1981), pp.85–108.
Plotkin, G.D. 1972 A set-theoretical definition of application. Memorandum MIP-R-95, School of Artificial Intelligence, University of Edinburgh, 32pp.
1978 The category of complete partial orders: a tool for making meanings. In: Proc. Summer School on Foundations of Artificial Intelligence and Computer Science. Institute di Scienze dell' Informazione, Universita di Pisa (June 1978).
Rabin, M. O. and Scott, D. S. 1959 Finite automata and their decision problems. IBM Journal Research and Development, vol. 3 (1959), pp. 114–125.
Scott, D.S. 1972 Continuous lattices. Springer Lecture Notes in Mathematics, vol. 274 (1972), pp. 97–136.
Scott, D.S. 1976 Data types as lattices. SIAM Journal on Computing, vol. 5 (1976), pp. 522–587.
1980a Lambda calculus: some models, some philosophy. The Kleene Symposium. Barwise, J., et al., eds., Studies in Logic 101, North Holland (1980), pp. 381–421.
1980b Relating theories of the λ-calculus. To H. B. Curry: Essays on Combinatory Logic, Lambda Calculus and Formalism. Seldin, J. P. and Hindley, J. R., eds., Academic Press (1980), pp. 403–450.
1980c Lectures on a mathematical theory of computation. Oxford University Computing Laboratory Technical Monograph PRG-19 (1981), 148pp.
1982 Some ordered sets in computer science. In: Ordered Sets. I. Rival, ed., D. Reidel (1982), pp. 677–718.
Smyth, M. and Plotkin, G. D. 1981 The categorical solution of recursive domain equations. SIAM Journal on Computation.. To appear (1981).
Stoy, J.E. 1977 Denotational Semantics: The Scott-Strachey Approach to Programming Language Theory. M.I.T. Press, Cambridge, Mass., xxx–414pp.
Tennent, R.D. 1981 Principles of Programming languages. Prentice-Hall (1981), 271 pp.6.
Wadsworth, C. 1976 The relation between computational and denotational properties for Scott's Dt8-models of the lambdacalculus. SIAM Journal of Computing, vol. 5, pp. 488–521.
Wilnskel, G. 1980 Events in Computation. Ph.D thesis, University of Edinburgh (1980).
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1982 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Scott, D.S. (1982). Domains for denotational semantics. In: Nielsen, M., Schmidt, E.M. (eds) Automata, Languages and Programming. ICALP 1982. Lecture Notes in Computer Science, vol 140. Springer, Berlin, Heidelberg. https://doi.org/10.1007/BFb0012801
Download citation
DOI: https://doi.org/10.1007/BFb0012801
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-11576-2
Online ISBN: 978-3-540-39308-5
eBook Packages: Springer Book Archive