The complexity of non-iterated probabilistic justification logic

DOI10.1007/978-3-319-30024-5_16zbMATH Open1459.03026arXiv1507.05500OpenAlexW2478189217MaRDI QIDQ2807085FDOQ2807085

Authors: Ioannis Kokkinis 

Publication date: 19 May 2016

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Abstract: The logic PJ is a probabilistic logic defined by adding (non-iterated) 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 complex- ity of the derivability problem in PJ remains the same as the complexity of the derivability problem in the underlying logic J, which is {Pi}p2-complete. This implies hat the probability operators do not increase the complex- ity of the logic, although they arguably enrich the expressiveness of the language.

Full work available at URL: https://arxiv.org/abs/1507.05500

Recommendations

• The complexity of satisfiability in non-iterated and iterated probabilistic logics
• Probabilistic justification logic
• Probabilistic justification logic
• First steps towards probabilistic justification logic
• Justification logic with approximate conditional probabilities

zbMATH Keywords

complexitysatisfiabilityjustification logicderivabilityprobabilistic logic

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Probability and inductive logic (03B48) Logics of knowledge and belief (including belief change) (03B42)

Cited In (3)

• On the Complexity of Two-Agent Justification Logic
• The complexity of satisfiability in non-iterated and iterated probabilistic logics
• Justification logic with confidence

This page was built for publication: The complexity of non-iterated probabilistic justification logic

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2807085)