Name
Abstract | ||
|---|---|---|
In this paper we initiate the study of discrete random variables over domains. Our work is inspired by that of Daniele Varacca, who devised indexed valuations as models of probabilistic computation within domain theory. Our approach relies on new results about commutative monoids defined on domains that also allow actions of the non-negative reals. Using our approach, we define two such families of real domain monoids, one of which allows us to recapture Varacca's construction of the Plotkin indexed valuations over a domain. Each of these families leads to the construction of a family of discrete random variables over domains, the second of which forms the object level of a continuous endofunctor on the categories RB (domains that are retracts of bifinite domains), and on FS (domains where the identity map is the directed supremum of deflations finitely separated from the identity). The significance of this last result lies in the fact that there is no known category of continuous domains that is closed under the probabilistic power domain, which forms the standard approach to modelling probabilistic choice over domains. The fact that RB and FS are Cartesian closed and also are closed under a power domain of discrete random variables means we can now model, e.g. the untyped lambda calculus extended with a probabilistic choice operator, implemented via random variables. |
Year | DOI | Venue |
|---|---|---|
2007 | 10.1016/j.tcs.2007.02.061 | Theor. Comput. Sci. |
Keywords | Field | DocType |
discrete random variable,domain theory,probabilistic computation,probabilistic choice operator,probabilistic choice,bifinite domain,probabilistic power domain,continuous domain,power domain,real domain monoids,indexation,random variable,lambda calculus | Identity function,Discrete mathematics,Random variable,Lambda calculus,Power domains,Infimum and supremum,Domain theory,Cartesian closed category,Probabilistic logic,Mathematics | Journal |
Volume | Issue | ISSN |
380 | 1-2 | Theoretical Computer Science |
ISBN | Citations | PageRank |
3-540-27580-0 | 6 | 0.69 |
References | Authors | |
14 | 2 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Michael Mislove | 1 | 96 | 8.78 |
| MW Mislove | 2 | 6 | 0.69 |