Hostname: page-component-586b7cd67f-dsjbd Total loading time: 0 Render date: 2024-11-28T15:21:32.232Z Has data issue: false hasContentIssue false
  • English
  • Français

Universal domains and the amalgamation property†

Published online by Cambridge University Press:  04 March 2009

Manfred Droste  and
Rüdiger Gübel
Manfred Droste
Affiliation:
Fb 6 – Mathematik und Informatik, Universität GHS Essen, D-4300 Essen 1, Germany
Rüdiger Gübel
Affiliation:
Fb 6 – Mathematik und Informatik, Universität GHS Essen, D-4300 Essen 1, Germany
Get access Rights & Permissions [Opens in a new window]

Abstract

In the theory of denotational semantics of programming languages, several authors have constructed various kinds of universal domains. We present here a categorical generalization of a well-known result in model theory, which we use to characterize large classes of reasonable categories that contain universal homogeneous objects. The existence of such objects is characterized by the condition that the finite objects in the category satisfy the amalgamation property. We derive from this the existence and uniqueness of universal homogeneous domains for several categories of bifinite domains, with embedding-projection-pairs as morphisms. We also obtain universal homogeneous objects for various categories of stable bifinite domains. In contrast, several categories of event domains and concrete domains and the category of all coherent Scott-domains do not contain universal homogeneous objects. Finally, we show that all our constructions can be performed effectively.

Type
Research Article
Information
Mathematical Structures in Computer Science , Volume 3 , Issue 2 , June 1993 , pp. 137 - 159
Copyright
Copyright © Cambridge University Press 1993

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Banaschewski, B. and Herrlich, H. (1976) Subcategories defined by implications. Houston J. Math. 2 149–171.Google Scholar
Barendregt, H. P. (1981) The Lambda Calculus: Its Syntax and Semantics. Studies in Logic and the Foundations of Mathematics 103, North Holland, Amsterdam.Google Scholar
Berry, G. (1978) Stable models of typed λ-calculi. In: Fifth International Colloquium on Automata, Languages and Programs. Lecture Notes in Computer Science 62, Springer 72–89.CrossRefGoogle Scholar
Berry, G. and Curien, P. L. (1982) Sequential algorithms on concrete data structure. Theoret. Comp. Science 20 265–321.Google Scholar
Birkhoff, G. (1973) Lattice Theory. Amer. Math. Soc. Colloq. Publ. 25, 3rd ed., Providence, R.I.Google Scholar
Bell, J. L. and Slomson, A. B. (1969) Models and Ultraproducts: An Introduction, North Holland, Amsterdam.Google Scholar
Cameron, P. (1990) Oligomorphic Permutation Groups. London Math. Soc. Lecture Note Series 152, Cambridge University Press.Google Scholar
Coquand, T., Gunter, C. and Winskel, G. (1988) DI-domains as a model of polymorphism. In: Mathematical Foundations of Programming Language Semantics (Main, M., Melton, A., Mislove, M., Schmidt, D., eds.). Lecture Notes in Computer Science 298, Springer 344–363.Google Scholar
Curien, P. L. (1986) Categorical Combinators, Sequential Algorithms and Functional Programming. Research Notes in Theoretical Computer Science, Pitman, London.Google Scholar
Droste, M. (1989a) Event structures and domains. Theoret. Comp. Science 68 37–48.Google Scholar
Droste, M. (1989b) Recursive domain equations for concrete data structures. Information and Computation 82 65–80.CrossRefGoogle Scholar
Droste, M. (1991) Universal homogeneous event structures and domains. Information and Computation 94 48–61.Google Scholar
Droste, M. (1992) Finite axiomatizations for universal domains. J. of Logic and Computation 2 119–131.Google Scholar
Droste, M. (to appear) On stable domains. Theoret. Comp. Science.Google Scholar
Droste, M. and Gobel, R. (1990a) Non-deterministic information systems and their domains. Theoret. Comp. Science 75 289–309.Google Scholar
Droste, M. and Gobel, R. (1990b) Effectively given information systems and domains. In: Computer Science Logic, Proc. Kaiserslautern 1989. Lecture Notes in Computer Science 440, Springer 116–142.Google Scholar
Droste, M. and Gobel, R. (1990) Universal domains in the theory of denotational semantics of programming languages. In: 5th IEEE Symposium on ‘Logic in Computer Science’, Philadelphia, 1990, IEEE Computer Society Press 19–34.Google Scholar
Droste, M. and Gobel, R. (1991) Universal information systems. Intern. J. of Foundations of Comp. Science 1 413–424.Google Scholar
Droste, M. and Gobel, R. (to appear) A categorical theorem on universal objects and its applications in abelian group theory and computer science. In: Contemporary Math. AMS, Proceed, of the Mai'cev-Conference in Novosibirsk 1989.Google Scholar
Fraissé, R. (1953) Sur certains relations qui généralisent l'ordre des nombres rationnels. C.R. Acad. Sci. Paris 237 540–542.Google Scholar
Fraissé, R. (1986) Theory of Relations. North Holland, Amsterdam.Google Scholar
Gunter, C. A. (1985) Profinite solutions for recursive domain equations, PhD-Thesis, University of Wisconsin, Madison, USA.Google Scholar
Gunter, C. A. (1987) Universal profinite domains. Information and Computation 72 1–30.Google Scholar
Gunter, C. A. and Jung, A. (1990) Coherence and consistency in domains. J. of Pure and Appl. Algebra 63 49–66.Google Scholar
Gunter, E. L. (1990) Pseudo-retract functors for local lattices and bifinite L-domains. In: Mathematical Foundations of Programming Semantics, Lecture Notes in Computer Science 442, Springer 351–363.Google Scholar
Jónsson, B. (1960) Homogeneous universal relational systems. Math. Scand. 8 137–142.Google Scholar
Jung, A. (1988) Cartesian closed categories of domains, Dissertation, TH Darmstadt, W. Germany.Google Scholar
Kahn, G. and Plotkin, G. (1978) Domaines concretes. Rapport de Recherche 336, IRIA, Paris.Google Scholar
Koymans, C. P. J. (1982) Models of the lambda calculus. Inform. Contr. 52 306–332.Google Scholar
MacNeille, H. (1937) Partially ordered sets. Trans. Amer. Math. Soc. 42 416–460.Google Scholar
Plotkin, G. (1976) A power domain construction. SIAM J. Comput. 5 452–488.Google Scholar
Plotkin, G. (1978) Tw as a universal domain. J. Comput. System Sci. 17 209–236.Google Scholar
Scott, D. (1976) Data types as lattices. SIAM J. Comput. 5 522–587.Google Scholar
Scott, D. (1981) Some ordered sets in computer science. In: Ordered Sets, (Rival, I., ed.), Reidel, Dordrecht677–718.Google Scholar
Smyth, M. B. (1983) The largest cartesian closed category of domains. Theoret. Comp. Science 27 109–119.Google Scholar
Smyth, M. B. and Plotkin, G. (1982) The category-theoretic solution of recursive domain equations. SIAM J. Comput. 11 761–783.Google Scholar
Winskel, G. (1981) Events in Computation, PhD-Thesis, Edinburgh.Google Scholar
Winskel, G. (1987) Event structures. In: Petri Nets: Applications and Relationships to Other Models of Concurrency (Brauer, W., Reisig, W., Rozenberg, G., eds.) Lecture Notes in Computer Science 255, Springer 325–392.Google Scholar
Zhang, G. (1989) DI-domains as information systems. In: 16th ICALP, Lecture Notes in Computer Science 372, Springer 773–788.Google Scholar