A complexity question in justification logic

作者：

Highlights：

• We examine the complexity of satisfiability for justification logic JD4.

• We prove completeness of this logic with respect to Fitting models of two states.

• Based on these semantics we give a tableau procedure for JD4.

• We conclude that satisfiability is in Σ2p under reasonable conditions.

• We thus tighten the lower bound by Buss and Kuznets.

摘要

•We examine the complexity of satisfiability for justification logic JD4.•We prove completeness of this logic with respect to Fitting models of two states.•Based on these semantics we give a tableau procedure for JD4.•We conclude that satisfiability is in Σ2p under reasonable conditions.•We thus tighten the lower bound by Buss and Kuznets.

论文关键词：Justification logic,Computational complexity,Satisfiability

论文评审过程：Received 4 January 2012, Revised 16 April 2013, Accepted 3 February 2014, Available online 3 April 2014.

论文官网地址：https://doi.org/10.1016/j.jcss.2014.03.009