The Complexity of Probabilistic Justification Logic

Abstract

Probabilistic justification logic is a modal logic with two kind of modalities: probability measures and explicit justification terms. We present a tableau procedure that can be used to decide the satisfiability problem for this logic in polynomial space. We show that this upper complexity bound is tight.

presented to the 11th Panhellenic Logic Symposium (http://pls11.cs.ntua.gr/)