Adding Clauses to Poor Man's Logic (Without Increasing the Complexity)
2005 (English)In: Journal of applied non-classical logics, ISSN 1166-3081, Vol. 15, no 3, 341-357 p.Article in journal (Refereed) Published
Partly motivated by description logics, poor man's logics have been proposed as an interesting fragment of modal logics. A poor man's logic is a propositional modal logic where only literals and the connectives , , and are allowed. It is known that the complexity of the satisfiability problem may drop dramatically when going from a full modal logic to the corresponding poor man's logic, e.g., in the case of modal logic K one goes from PSPACEcomplete to coNP-complete. We prove that it is sometimes possible to extend poor man's logics with restricted disjunctions (i.e., clauses) without increasing the computational complexity. For Horn and Krom clauses, we provide necessary and sufficient conditions for when the resulting logic is polynomial-time. Such extensions correspond to allowing a restricted use of the union operator in description logics.
Place, publisher, year, edition, pages
2005. Vol. 15, no 3, 341-357 p.
modal logic, poor man's logic, computational complexity, disjunction
IdentifiersURN: urn:nbn:se:liu:diva-22145DOI: 10.3166/jancl.15.341-357Local ID: 1253OAI: oai:DiVA.org:liu-22145DiVA: diva2:242458