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
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) | Request a copy
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.
|Item Type:||Book Section (Book Chapter)|
|Division/Institute:||08 Faculty of Science > Institute of Computer Science (INF)
08 Faculty of Science > Institute of Computer Science (INF) > Logic and Theory Group (LTG)
|UniBE Contributor:||Kokkinis, Ioannis|
|Subjects:||000 Computer science, knowledge & systems
500 Science > 510 Mathematics
|Series:||Lecture Notes in Computer Science|
|Date Deposited:||09 May 2016 16:01|
|Last Modified:||20 Mar 2017 13:49|