ML Anthology

A Simple Probabilistic Extension of Modal Mu-Calculus

Wanwei Liu, Lei Song, Ji Wang, Lijun Zhang
IJCAI 2015 pp. 882-888
/ijcai/2015/liu2015ijcai-simple/

Abstract

Probabilistic systems are an important theme in AI domain. As the specification language, PCTL is the most frequently used logic for reasoning about probabilistic properties. In this paper, we present a natural and succinct probabilistic extension of Mu-calculus, another prominent logic in the concurrency theory. We study the relationship with PCTL. Surprisingly, the expressiveness is highly orthogonal with PCTL. The proposed logic captures some useful properties which cannot be expressed in PCTL. We investigate the model checking and satisfiability problem, and show that the model checking problem is in UP and co-UP, and the satisfiability checking can be decided via reducing into solving parity games. This is in contrast to PCTL as well, whose satisfiability checking is still an open problem.

PDF IJCAI Semantic Scholar

Cite

Text

Liu et al. "A Simple Probabilistic Extension of Modal Mu-Calculus." International Joint Conference on Artificial Intelligence, 2015.

Markdown

[Liu et al. "A Simple Probabilistic Extension of Modal Mu-Calculus." International Joint Conference on Artificial Intelligence, 2015.](https://mlanthology.org/ijcai/2015/liu2015ijcai-simple/)

BibTeX

@inproceedings{liu2015ijcai-simple,
  title     = {{A Simple Probabilistic Extension of Modal Mu-Calculus}},
  author    = {Liu, Wanwei and Song, Lei and Wang, Ji and Zhang, Lijun},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year      = {2015},
  pages     = {882-888},
  url       = {https://mlanthology.org/ijcai/2015/liu2015ijcai-simple/}
}