DROPS

Document

DOI: 10.4230/LIPIcs.STACS.2015.211

Tractable Probabilistic mu-Calculus That Expresses Probabilistic Temporal Logics

Authors: Pablo Castro, Cecilia Kilmurray, and Nir Piterman

Published in: LIPIcs, Volume 30, 32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015)

Abstract

We revisit a recently introduced probabilistic \mu-calculus and study an expressive fragment of it. By using the probabilistic quantification as an atomic operation of the calculus we establish a connection between the calculus and obligation games. The calculus we consider is strong enough to encode well-known logics such as pctl and pctl^*. Its game semantics is very similar to the game semantics of the classical mu-calculus (using parity obligation games instead of parity games). This leads to an optimal complexity of NP\cap co-NP for its finite model checking procedure. Furthermore, we investigate a (relatively) well-behaved fragment of this calculus: an extension of pctl with fixed points. An important feature of this extended version of pctl is that its model checking is only exponential w.r.t. the alternation depth of fixed points, one of the main characteristics of Kozen's mu-calculus.

Cite as

Pablo Castro, Cecilia Kilmurray, and Nir Piterman. Tractable Probabilistic mu-Calculus That Expresses Probabilistic Temporal Logics. In 32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 30, pp. 211-223, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{castro_et_al:LIPIcs.STACS.2015.211,
  author =	{Castro, Pablo and Kilmurray, Cecilia and Piterman, Nir},
  title =	{{Tractable Probabilistic mu-Calculus That Expresses Probabilistic Temporal Logics}},
  booktitle =	{32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015)},
  pages =	{211--223},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-78-1},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{30},
  editor =	{Mayr, Ernst W. and Ollinger, Nicolas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2015.211},
  URN =		{urn:nbn:de:0030-drops-49155},
  doi =		{10.4230/LIPIcs.STACS.2015.211},
  annote =	{Keywords: mu-calculus, probabilistic logics, model checking, game semantics}
}

Search Results

Documents authored by Kilmurray, Cecilia

Tractable Probabilistic mu-Calculus That Expresses Probabilistic Temporal Logics

Abstract

Cite as

Thanks for your feedback!

Could not send message