QRB-Domains and the Probabilistic Powerdomain

2012/02/27 by Jean Goubault-Larrecq · 3 citations
Computer Science · #cs.PL

paper · pdf · doi:10.2168/lmcs-8(1:14)2012

published as Logical Methods in Computer Science, Volume 8, Issue 1 (February 29, 2012) lmcs:956 · 32 pages, 7 figures. An extended abstract already appeared in Proc. 25th Annual IEEE Symposium on Logic in Computer Science (LICS'10)

arxiv created 2012/02/27 · arxiv updated 2015/07/01

Abstract

Is there any Cartesian-closed category of continuous domains that would be closed under Jones and Plotkin's probabilistic powerdomain construction? This is a major open problem in the area of denotational semantics of probabilistic higher-order languages. We relax the question, and look for quasi-continuous dcpos instead. We introduce a natural class of such quasi-continuous dcpos, the omega-QRB-domains. We show that they form a category omega-QRB with pleasing properties: omega-QRB is closed under the probabilistic powerdomain functor, under finite products, under taking bilimits of expanding sequences, under retracts, and even under so-called quasi-retracts. But... omega-QRB is not Cartesian closed. We conclude by showing that the QRB domains are just one half of an FS-domain, merely lacking control.

Cited by

• Forbidden substructures for coherence of domains
• A note on probabilistic powerdomains, RB-domains, and bc-domains
• Finite-valuation approximable structures: a solution to the Jung--Tix problem of probabilistic powerdomains

Related

• Probabilistic Powerdomains and Quasi-Continuous Domains
• A Probabilistic and Non-Deterministic Call-by-Push-Value Language
• The Directed Probabilistic Powerspace
• A note on probabilistic powerdomains, RB-domains, and bc-domains
• Probabilistic Stable Functions on Discrete Cones are Power Series (long version)