×

All Cartesian closed categories of quasicontinuous domains consist of domains. (English) Zbl 1328.68123

Summary: Quasicontinuity is a generalisation of Scott’s notion of continuous domain, introduced in the early 80s by G. Gierz et al. [Houston J. Math. 9, 191–208 (1983; Zbl 0529.06002)]. In this paper we ask which Cartesian closed full subcategories exist in qCONT, the category of all quasicontinuous domains and Scott-continuous functions. The surprising, and perhaps disappointing, answer turns out to be that all such subcategories consist entirely of continuous domains. In other words, there are no new cartesian closed full subcategories in qCONT beyond those already known to exist in CONT.{ }To prove this, we reduce the notion of meet-continuity for dcpos to one which only involves well-ordered chains. This allows us to characterise meet-continuity by “forbidden substructures”. We then show that each forbidden substructure has a non-quasicontinuous function space.

MSC:

68Q55 Semantics in the theory of computing
06B35 Continuous lattices and posets, applications
18D15 Closed categories (closed monoidal and Cartesian closed categories, etc.)

Citations:

Zbl 0529.06002
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Abramsky, S.; Jung, A., Domain theory, (Abramsky, S.; Gabbay, D. M.; Maibaum, T. S.E., Semantic Structures. Semantic Structures, Handbook of Logic in Computer Science, vol. 3 (1994), Clarendon Press), 1-168 · Zbl 0829.68111
[2] Gierz, G.; Hofmann, K. H.; Keimel, K.; Lawson, J. D.; Mislove, M.; Scott, D. S., Continuous Lattices and Domains, Encyclopedia of Mathematics and Its Applications, vol. 93 (2003), Cambridge University Press · Zbl 1088.06001
[3] Gierz, G.; Lawson, J. D.; Stralka, A., Quasicontinuous posets, Houston J. Math., 9, 191-208 (1983) · Zbl 0529.06002
[4] Goubault-Larrecq, J., QRB-domains and the probabilistic powerdomain, Log. Methods Comput. Sci., 8, 1 (2012), paper 14, 33 pp · Zbl 1239.06002
[5] Goubault-Larrecq, J.; Jung, A., QRB, QFS, and the probabilistic powerdomain, (Jacobs, B.; Mislove, A. M.; Silva, A.; Staton, S., Proceedings of the 30th Conference on the Mathematical Foundations of Programming Semantics. Proceedings of the 30th Conference on the Mathematical Foundations of Programming Semantics, Electronic Notes in Theoretical Computer Science, vol. 308 (2014), Elsevier Science Publishers B.V.), 167-182 · Zbl 1337.68160
[6] Heckmann, R.; Keimel, K., Quasicontinuous domains and the Smyth powerdomain, (Kozen, D.; Mislove, M., Proceedings of the 29th Conference on the Mathematical Foundations of Programming Semantics. Proceedings of the 29th Conference on the Mathematical Foundations of Programming Semantics, Electronic Notes in Theoretical Computer Science, vol. 298 (2013), Elsevier Science Publishers B.V.), 215-232 · Zbl 1334.68127
[7] Iwamura, T., A lemma on directed sets, Zenkoku Shijo Sugaku Danwakai, 262, 107-111 (1944), (in Japanese)
[8] Jones, C., Probabilistic non-determinism (1990), University of Edinburgh: University of Edinburgh Edinburgh, also published as Technical Report No. CST-63-90
[9] Jones, C.; Plotkin, G., A probabilistic powerdomain of evaluations, (Proceedings of the 4th Annual Symposium on Logic in Computer Science (1989), IEEE Computer Society Press), 186-195 · Zbl 0716.06003
[10] Jung, A., Cartesian closed categories of domains, (CWI Tracts, vol. 66 (1989), Centrum voor Wiskunde en Informatica: Centrum voor Wiskunde en Informatica Amsterdam), 107 pp. · Zbl 0719.06004
[11] Jung, A., The classification of continuous domains, (Proceedings, Fifth Annual IEEE Symposium on Logic in Computer Science (1990), IEEE Computer Society Press), 35-40 · Zbl 0825.68599
[12] Kamimura, T.; Tang, A., Retracts of SFP objects, (Melton, A., Mathematical Foundations of Programming Semantics. Mathematical Foundations of Programming Semantics, Lecture Notes in Computer Science, vol. 239 (1986), Springer Verlag), 135-148 · Zbl 0609.68015
[13] Hui Kou; Liu, Ying-Ming; Luo, Mao-Kang, On meet-continuous dcpos, (Zhang, G. Q.; Lawson, J.; Liu, Y.-M.; Luo, M.-K., Domain Theory, Logic and Computation. Domain Theory, Logic and Computation, Semantic Structures in Computation, vol. 3 (2003), Springer: Springer Netherlands), 117-135
[14] Lawson, Jimmie; Xi, Xiaoyong, The equivalence of QRB, QFS, and compactness for quasicontinuous domains, Order, 31, 1-12 (2014) · Zbl 1333.06010
[15] Li, Gaolin; Xu, Luoshan, QFS-domains and their Lawson compactness, Order, 30, 233-248 (2013) · Zbl 1408.06002
[16] Markowsky, G., Chain-complete p.o. sets and directed sets with applications, Algebra Universalis, 6, 53-68 (1976) · Zbl 0332.06001
[17] Saheb-Djahromi, N., CPO’s of measures for nondeterminism, Theoret. Comput. Sci., 12, 19-37 (1980) · Zbl 0433.68017
[18] Smyth, M. B., The largest cartesian closed category of domains, Theoret. Comput. Sci., 27, 109-119 (1983) · Zbl 0556.68017
[19] Zhao, H.; Kou, H., Notes on quasicontinuous domains and their function spaces, Fuzzy Systems Math., 26, 4, 143-148 (2012), (in Chinese) · Zbl 1274.06031
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.