The Complexity of Non-Iterated Probabilistic Justification Logic

Kokkinis, Ioannis (2016). The Complexity of Non-Iterated Probabilistic Justification Logic. In: Gyssens, Marc; Simari, Guillermo (eds.) Foundations of Information and Knowledge Systems - 9th International Symposium, FoIKS 2016, Linz, Austria, March 7-11, 2016. Proceedings. Lecture Notes in Computer Science: Vol. 9616 (pp. 292-310). Cham: Springer 10.1007/978-3-319-30024-5_16

Text chp%3A10.1007%2F978-3-319-30024-5_16.pdf - Published Version Restricted to registered users only Available under License Publisher holds Copyright. Download (537kB)

The logic PJ is a probabilistic logic defined by adding (noniterated) probability operators to the basic justification logic J. In this paper we establish upper and lower bounds for the complexity of the derivability problem in the logic PJ. The main result of the paper is that the complexity of the derivability problem in PJ remains the same as the complexity of the derivability problem in the underlying logic J, which is π[p/2] -complete. This implies that the probability operators do not increase the complexity of the logic, although they arguably enrich the expressiveness of the language.

Interest & Impact

Downloads

3 since deposited on 09 May 2016
0 in the past 12 months

Citations

5 Citations in Web of Science ®
6 Citations in Scopus

Search

in Google Scholar™

Services

Actions (login required)

Edit item

Actions (login required)

Edit item