Arrow Research search

Author name cluster

Michael Mislove

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

18 papers
1 author row

Possible papers

18

TCS Journal 2020 Journal Article

Domains and stochastic processes

  • Michael Mislove

Domain theory has a long history of applications in theoretical computer science and mathematics. In this article, we explore the relation of domain theory to probability theory and stochastic processes. The goal is to establish a theory in which Polish spaces are replaced by domains, and measurable maps are replaced by Scott-continuous functions. We illustrate the approach by recasting one of the fundamental results of stochastic process theory – Skorohod's Representation Theorem – in domain-theoretic terms. We anticipate the domain-theoretic version of results like Skorohod's Theorem will improve our understanding of probabilistic choice in computational models, and help devise models of probabilistic programming, with its focus on programming languages that support sampling from distributions where the results are applied to Bayesian reasoning.

Details DOI

TCS Journal 2014 Journal Article

Anatomy of a domain of continuous random variables I

  • Michael Mislove

In this paper we study the family of thin probability measures on the domain A ∞ of finite and infinite words over a finite alphabet A. This structure is inspired by work of Jean Goubault-Larrecq and Daniele Varacca, who recently proposed a model of continuous random variables over bounded complete domains. Their presentation leaves out many details, and also misses some motivations. In this and a related paper we attempt to fill in some of these details, and in the process, we reveal some features of their model. Our approach to constructing the thin probability measures uses domain theory, and we show the family forms a bounded complete algebraic domain over A ∞. In the second paper in this series, we explore using the thin probability measures to reconstruct the bounded complete domain of continuous random variables over any bounded complete domain due originally to Goubault-Larrecq and Varacca.

Details DOI

TCS Journal 2012 Journal Article

Preface

  • Samson Abramsky
  • Michael Mislove
  • Catuscia Palamidessi
Details DOI

TCS Journal 2007 Journal Article

Discrete random variables over domains

  • Michael Mislove

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.

Details DOI

TCS Journal 2005 Journal Article

Domain theory, testing and simulation for labelled Markov processes

  • Franck van Breugel
  • Michael Mislove
  • Joël Ouaknine
  • James Worrell

This paper presents a fundamental study of similarity and bisimilarity for labelled Markov processes (LMPs). The main results characterize similarity as a testing preorder and bisimilarity as a testing equivalence. In general, LMPs are not required to satisfy a finite-branching condition—indeed the state space may be a continuum, with the transitions given by arbitrary probability measures. Nevertheless we show that to characterize bisimilarity it suffices to use finitely-branching labelled trees as tests. Our results involve an interaction between domain theory and measure theory. One of the main technical contributions is to show that a final object in a suitable category of LMPs can be constructed by solving a domain equation D ≅ V ( D ) Act, where V is the probabilistic powerdomain. Given an LMP whose state space is an analytic space, bisimilarity arises as the kernel of the unique map to the final LMP. We also show that the metric for approximate bisimilarity introduced by Desharnais, Gupta, Jagadeesan and Panangaden generates the Lawson topology on the domain D.

Details DOI

TCS Journal 2004 Journal Article

Measuring the probabilistic powerdomain

  • Keye Martin
  • Michael Mislove
  • James Worrell

In this paper we initiate the study of measurements on the probabilistic powerdomain. We show how measurements on an underlying domain naturally extend to its probabilistic powerdomain, so that the kernel of the extension consists of exactly those normalized measures on the kernel of the measurement on the underlying domain. This result is combined with now-standard results from the theory of measurements to obtain a new proof that the fixed point associated with a weakly hyperbolic IFS with probabilities is the unique invariant measure whose support is the attractor of the underlying IFS.

Details DOI

TCS Journal 2002 Journal Article

A truly concurrent semantics for a process algebra using resource pomsets

  • Paul Gastin
  • Michael Mislove

In this paper we study a process algebra whose semantics is based on true concurrency. In our model, actions are defined in terms of the resources they need to execute, which allows a simple definition of a weak sequential composition operator. This operator allows actions which do not share any resources to execute concurrently, while dependent actions have to occur sequentially. This weak sequential composition operator may be used to automatically parallelize a sequential process. We add the customary (strict) sequential composition and a parallel composition operator allowing synchronization on specified actions. Our language also supports a hiding operator that allows the hiding of actions and even of individual resources used by actions. Strict sequential composition and hiding require that we generalize from the realm of Mazurkiewicz traces to that of pomsets, since these operations introduce “over-synchronized” traces—ones for which a pair of independent actions may occur sequentially. Our language also supports recursion and our semantics makes the unwinding of recursion visible by the use of special resources used to label unwindings. This is done on purpose in order to make divergence observable, but the usual semantics that does not observe unwindings can be obtained by using the hiding operator to abstract away from these special resources. We give both an SOS-style operational semantics for our language, as well as a denotational semantics based on resource pomsets. Generalizing results from our earlier work in this area, we derive a congruence theorem for our language which shows that the SOS-style operational rules induce the same equivalence relation on the language as the denotational semantic map does. A corollary is that our denotational model is both adequate and fully abstract relative to the behavior function defined from our operational semantics. This behavior consists naturally of the strings of actions the process can perform. This work continues our study into modelling concurrency in the absence of nondeterminism. In particular, our language is deterministic.

Details DOI
v2026.09.13