Taking it to the limit: approximate reasoning for markov processes

Kim Guldstrand Larsen, Radu Mardare, Prakash Panangaden

Research output: Chapter in Book/Report/Conference proceedingConference contribution book

17 Citations (Scopus)

Abstract

We develop a fusion of logical and metrical principles for reasoning about Markov processes. More precisely, we lift metrics from processes to sets of processes satisfying a formula and explore how the satisfaction relation behaves as sequences of processes and sequences of formulas approach limits. A key new concept is dynamically-continuous metric bisimulation which is a property of (pseudo)metrics. We prove theorems about satisfaction in the limit, robustness theorems as well as giving a topological characterization of various classes of formulas. This work is aimed at providing approximate reasoning principles for Markov processes.

Original languageEnglish
Title of host publicationMathematical Foundations of Computer Science 2012. MFCS 2012.
EditorsB. Rovan, V. Sassone, P. Widmayer
Place of PublicationBerlin
PublisherSpringer-Verlag
Pages681-692
Number of pages12
ISBN (Print)9783642325885
DOIs
Publication statusPublished - 20 Aug 2012
Event37th International Symposium on Mathematical Foundations of Computer Science 2012, MFCS 2012 - Bratislava, Slovakia
Duration: 27 Aug 201231 Aug 2012

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume7464 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference37th International Symposium on Mathematical Foundations of Computer Science 2012, MFCS 2012
CountrySlovakia
CityBratislava
Period27/08/1231/08/12

Keywords

  • Markov process
  • convergent sequence
  • logical formula
  • approximate reasoning
  • Markov kernel

Fingerprint Dive into the research topics of 'Taking it to the limit: approximate reasoning for markov processes'. Together they form a unique fingerprint.

  • Cite this

    Larsen, K. G., Mardare, R., & Panangaden, P. (2012). Taking it to the limit: approximate reasoning for markov processes. In B. Rovan, V. Sassone, & P. Widmayer (Eds.), Mathematical Foundations of Computer Science 2012. MFCS 2012. (pp. 681-692). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 7464 LNCS). Springer-Verlag. https://doi.org/10.1007/978-3-642-32589-2_59