A Simple Probabilistic Extension of Modal Mu-calculus

Liu, Wanwei; Song, Lei; Wang, Ji; Zhang, Lijun

A Simple Probabilistic Extension of Modal Mu-calculus

Wanwei Liu, Lei Song, Ji Wang, Lijun Zhang

Download BibTeX Cite

Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence. Main Track. Pages 882-887.

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.

Wanwei Liu, Lei Song, Ji Wang, and Lijun Zhang. 2015. A Simple Probabilistic Extension of Modal Mu-calculus. In Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence, IJCAI-15. IJCAI, 882–887. https://ijcai.org/proceedings/2015/129

@inproceedings{ijcai2015p129,
  title     = {A Simple Probabilistic Extension of Modal Mu-calculus},
  author    = {Liu, Wanwei and Song, Lei and Wang, Ji and Zhang, Lijun},
  booktitle = {Proceedings of the Twenty-Fourth International Joint Conference on
               Artificial Intelligence, {IJCAI-15}},
  publisher = {International Joint Conferences on Artificial Intelligence},
  editor    = {Qiang Yang and Michael Wooldridge},
  pages     = {882--887},
  year      = {2015},
  month     = {7},
  note      = {Main Track},
  url       = {https://ijcai.org/proceedings/2015/129},
}

TY  - CPAPER
TI  - A Simple Probabilistic Extension of Modal Mu-calculus
AU  - Liu, Wanwei
AU  - Song, Lei
AU  - Wang, Ji
AU  - Zhang, Lijun
T2  - Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence, IJCAI-15
PB  - International Joint Conferences on Artificial Intelligence
PY  - 2015
SP  - 882
EP  - 887
UR  - https://ijcai.org/proceedings/2015/129
ER  -