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

[img] 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) | 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
ISSN: 0302-9743
ISBN: 978-3-319-30023-8
Series: Lecture Notes in Computer Science
Publisher: Springer
Language: English
Submitter: Lukas Jaun
Date Deposited: 09 May 2016 16:01
Last Modified: 20 Mar 2017 13:49
Publisher DOI: 10.1007/978-3-319-30024-5_16
BORIS DOI: 10.7892/boris.79973
URI: http://boris.unibe.ch/id/eprint/79973

Actions (login required)

Edit item Edit item
Provide Feedback