Lower complexity bounds in justification logic

Buss, Samuel R.; Kuznets, Roman (2012). Lower complexity bounds in justification logic. Annals of pure and applied logic, 163(7), pp. 888-905. Amsterdam: Elsevier 10.1016/j.apal.2011.09.010

Full text not available from this repository.

Justification Logic studies epistemic and provability phenomena by introducing justifications/proofs into the language in the form of justification terms. Pure justification logics serve as counterparts of traditional modal epistemic logics, and hybrid logics combine epistemic modalities with justification terms. The computational complexity of pure justification logics is typically lower than that of the corresponding modal logics. Moreover, the so-called reflected fragments, which still contain complete information about the respective justification logics, are known to be in~NP for a wide range of justification logics, pure and hybrid alike. This paper shows that, under reasonable additional restrictions, these reflected fragments are NP-complete, thereby proving a matching lower bound. The proof method is then extended to provide a uniform proof that the corresponding full pure justification logics are $\Pi^p_2$-hard, reproving and generalizing an earlier result by Milnikel.

Item Type:	Journal Article (Original Article)
Division/Institute:	08 Faculty of Science > Institute of Computer Science (INF) > Logic and Theory Group (LTG) 08 Faculty of Science > Institute of Computer Science (INF)
UniBE Contributor:	Kuznets, Roman
ISSN:	0168-0072
Publisher:	Elsevier
Language:	English
Submitter:	Factscience Import
Date Deposited:	04 Oct 2013 14:42
Last Modified:	05 Dec 2022 14:13
Publisher DOI:	10.1016/j.apal.2011.09.010
Web of Science ID:	000301964400011
URI:	https://boris.unibe.ch/id/eprint/17286 (FactScience: 225044)