Strong completeness for Markovian logics

Dexter Kozen, Radu Mardare, Prakash Panangaden

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

10 Citations (Scopus)


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
Number of pages12
ISBN (Print)9783642403125
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


Conference38th International Symposium on Mathematical Foundations of Computer Science, MFCS 2013


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


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

Cite this