Logic in Computer Science (LICS 1995)

Paper: Domain Theory in Stochastic Processes (at LICS 1995)

Authors: Abbas Edalat

Abstract

We establish domain-theoretic models of finite-state discrete stochastic processes, Markov processes and vector recurrent iterated function systems. In each case, we show that the distribution of the stochastic process is canonically obtained as the least upper bound of an increasing chain of simple valuations in a probabilistic power domain associated to the process. This leads to various formulas and algorithms to compute the expected values of functions which are continuous almost everywhere with respect to the distribution of the stochastic process. We also prove the existence and uniqueness of the invariant distribution of a vector recurrent iterated function system which is used in fractal image compression, and present a finite algorithm to decode the image.

BibTeX

  @InProceedings{Edalat-DomainTheoryinStoch,
    author = 	 {Abbas Edalat},
    title = 	 {Domain Theory in Stochastic Processes},
    booktitle =  {Proceedings of the Tenth Annual IEEE Symp. on Logic in Computer Science, {LICS} 1995},
    year =	 1995,
    editor =	 {Dexter Kozen},
    month =	 {June}, 
    pages =      {244-254},
    location =   {San Diego, CA, USA}, 
    publisher =	 {IEEE Computer Society Press}
  }