Strong completeness for Markovian logics

Dexter Kozen, Radu Mardare, Prakash Panangaden

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

9 Citations (Scopus)

Abstract

In this paper we present Hilbert-style axiomatizations for three logics for reasoning about continuous-space Markov processes (MPs): (i) a logic for MPs defined for probability distributions on measurable state spaces, (ii) a logic for MPs defined for sub-probability distributions and (iii) a logic defined for arbitrary distributions. These logics are not compact so one needs infinitary rules in order to obtain strong completeness results. We propose a new infinitary rule that replaces the so-called Countable Additivity Rule (CAR) currently used in the literature to address the problem of proving strong completeness for these and similar logics. Unlike the CAR, our rule has a countable set of instances; consequently it allows us to apply the Rasiowa-Sikorski lemma for establishing strong completeness. Our proof method is novel and it can be used for other logics as well.

Original languageEnglish
Title of host publicationMathematical Foundations of Computer Science 2013
EditorsK. Chatterjee, J. Sgall
Place of PublicationBerlin
PublisherSpringer-Verlag
Pages655-666
Number of pages12
ISBN (Print)9783642403125
DOIs
Publication statusPublished - 15 Oct 2013
Event38th International Symposium on Mathematical Foundations of Computer Science, MFCS 2013 - Klosterneuburg, Austria
Duration: 26 Aug 201330 Aug 2013

Publication series

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

Conference

Conference38th International Symposium on Mathematical Foundations of Computer Science, MFCS 2013
CountryAustria
CityKlosterneuburg
Period26/08/1330/08/13

Keywords

  • markov process
  • logics
  • probability distributions
  • sub-probability distributions
  • arbitrary distributions

Fingerprint Dive into the research topics of 'Strong completeness for Markovian logics'. Together they form a unique fingerprint.

  • Cite this

    Kozen, D., Mardare, R., & Panangaden, P. (2013). Strong completeness for Markovian logics. In K. Chatterjee, & J. Sgall (Eds.), Mathematical Foundations of Computer Science 2013 (pp. 655-666). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 8087 LNCS). Springer-Verlag. https://doi.org/10.1007/978-3-642-40313-2_58