On Domain Theory over Girard Quantales

• Autorzy: Waszkiewicz P.
• Języki publikacji: EN

Abstrakty

EN

This paper is about a generalization of Scott's domain theory in such a way that its definitions and theorems become meaningful in quasimetric spaces. The generalization is achieved by a change of logic: the fundamental concepts of original domain theory (order, way-below relation, Scott-open sets, continuous maps, etc.) are interpreted as predicates that are valued in an arbitrary completely distributive Girard quantale (a CDG quantale). Girard quantales are known to provide a sound and complete semantics for commutative linear logic, and complete distributivity adds a notion of approximation to our setup. Consequently, in this paper we speak about domain theory based on commutative linear logic with some additional reasoning principles following from approximation between truth values. Concretely, we: (1) show how to define continuous Q-domains, i.e. continuous domains over a CDG quantale Q; (2) study their way-below relation, and (3) study the rounded ideal completion of Q-abstract bases. As a case study, we (4) demonstrate that the domain-theoretic construction of the Hoare, Smyth and Plotkin powerdomains of a continuous dcpo can be straightforwardly adapted to yield corresponding constructions for continuous Q-domains.

Słowa kluczowe

EN

(generalized) continuous domains; (generalized) way-below relation; rounded ideal completion

• Wydawca: Polskie Towarzystwo Matematyczne
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2009
• Tom: Vol. 92, nr 1-2
• Strony: 169--192
• Opis fizyczny: Bibliogr. 28 poz.

Twórcy

autor

Waszkiewicz P.

• Theoretical Computer Science Jagiellonian University ul. Gronostajowa 3, 30-387 Kraków, Poland,

Bibliografia

• [AJ94] Abramsky, S. and Jung, A. (1994) Domain Theory. In S. Abramsky, D.M. Gabbay and T.S.E. Maibaum, editors, Handbook of Logic in Computer Science 3, pp. 1-168, Oxford University Press.
• [AR89] America, P. and Rutten, J.J.M.M (1989) Solving Reflexive Domain Equations in a Category of Complete Metric Spaces, J. Comput. Syst. Sci. 39(3), pp. 343-375.
• [BBR98] Bonsangue, M.M., van Breugel, F. and Rutten, J.J.M.M. (1998)Generalized Metric Spaces: Completion, Topology, and Power domains via the Yoneda Embedding, Theoretical Computer Science 193(1-2), pp. 1-51.
• [Fl97] Flagg, R.C. (1997) Quantales and continuity spaces, Algebra Universalis 37, pp. 257-276.
• [FK95] Flagg, R.C., Kopperman, R. (1995) Fixed points and reflexive domain equations in categories of continuity spaces. Electronic Notes in Theoretical Computer Science 1.
• [FK97] Flagg, R.C., Kopperman, R. (1997) Continuity Spaces: Reconciling Domains and Metric Spaces, Theoretical Computer Science 177(1), pp. 111-138.
• [FS02] Flagg, R.C., Sünderhauf, P. (2002) The essence of ideal completion in quantitative form. Theoretical Computer Science 278(1-2), pp. 141-158.
• [FSW96] Flagg, R.C., Sünderhauf, P. and Wagner, K.R. (1996) A Logical Approach to Quantitative Domain Theory, Topology Atlas Preprint no. 23, available on-line at: http://at.yorku.ca/e/a/p/p/23.htm
• [GHK+03] Gierz, G., Hofmann, K.H., Keimel, K., Lawson, J.D., Mislove, M. and Scott, D.S. (2003) Continuous lattices and domains. Volume 93 of Encyclopedia of mathematics and its applications.
• [Gir87] Girard, J.-Y. (1987) Linear Logic, Theoretical Computer Science 50, pp. 1-102.
• [Hec07] Heckmann, R. (2007) Similarity, Topology, and Uniformity, presented at Dagstuhl workshop "Logic, Computability and Topology in Computer Science: A New Perspective for Old Disciplines", submitted. Available on-line at: http://rw4.cs.uni-sb.de/ heckmann/domains.html
• [Hof07] Hofmann, D. (2007) Topological theories and closed objects, Adv. Math. 215, pp. 789-824.
• [Joh82] Johnstone, P. and Joyal, A. (1982) Continuous categories and exponentiable toposes, J. Pure Appl. Algebra 25, pp. 255-296.
• [LZ06] Lai, Hongliang and Zhang, Dexue (2006) Many-valued complete distributivity. On-line: http://arxiv.org/abs/math/0603590v1
• [LZ07] Lai, Hongliang and Zhang, Dexue (2007) Complete and directed complete Omega-categories. Theoretical Computer Science 388(1-3),pp. 1-25.
• [Law02] Lawvere, F.W. (2002)Metric Spaces, Generalized Logic and Closed Categories, Reprints in Theory and Applications of Categories 1, pp. 1-37.
• [PTh04] Pedicchio,M.C. and Tholen,W. Eds. (2004) Categorical Foundations: Special Topics in Order, Topology, Algebra, and Sheaf Theory. Encyclopaedia of Mathematics and Its Applications 97, Cambridge University Press, 440 pp.
• [Ran52] Raney, G.N. (1952) Completely Distributive Complete Lattices, Proceedings of the American Mathematical Society, 3(5), pp. 677-680.
• [Ran53] Raney, G.N. (1953) A Subdirect-Union Representation for Completely Distributive Complete Lattices Proceedings of the American Mathematical Society, 4(4), pp. 518-522.
• [Rut96] Rutten, J.J.M.M. (1996) Elements of generalized ultrametric domain theory, Theoretical Computer Science 170, pp. 349-381.
• [Smy88] Smyth, M.B. (1988) Quasi-uniformities: Reconciling Domains and Metric Spaces. Lecture Notes in Computer Science 298, pp. 236-253.
• [Smy91] Smyth, M.B. (1991) Totally bounded spaces and compact ordered spaces as domains of computation. In G.M. Reed, A. W. Roscoe, and R. F. Wachter, editors, Topology and Category Theory in Computer Science, pp. 207-229. Clarendon Press.
• [Smy94] Smyth, M.B. (1994) Completeness of quasi-uniform and syntopological spaces. Journal of the London Mathematical Society 49, pp. 385-400.
• [Stu05] Stubbe, I. (2005) Towards dynamic domains: totally continuous co complete Q-categories, preprint, arXive: math.CT/0501489.
• [Vic05] Vickers, S. (2005) Localic Completion of Generalized Metric Spaces I, Theory and Applications of Categories 14, pp. 328-356.
• [Wag94] Wagner, K.R. (1994) Solving Recursive Domain Equations with Enriched Categories, PhD Thesis, Carnegie Mellon University.
• [Yet90] Yetter, D.N. (1990)Quantales and (Noncommutative)Linear Logic, The Journal of Symbolic Logic, 55(1), pp. 41-64.
• [ZF05] Zhang, Q.-Y., Fan, L. (2005) Continuity in quantitative domains Fuzzy Sets and Systems 154(1), pp. 118-131.