liu.seSearch for publications in DiVA
Change search
ReferencesLink to record
Permanent link

Direct link
Adding Clauses to Poor Man's Logic (Without Increasing the Complexity)
Linköping University, Department of Computer and Information Science, TCSLAB - Theoretical Computer Science Laboratory. Linköping University, The Institute of Technology.
2005 (English)In: Journal of applied non-classical logics, ISSN 1166-3081, Vol. 15, no 3, 341-357 p.Article in journal (Refereed) Published
Abstract [en]

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.
Keyword [en]
modal logic, poor man's logic, computational complexity, disjunction
National Category
Computer Science
URN: urn:nbn:se:liu:diva-22145DOI: 10.3166/jancl.15.341-357Local ID: 1253OAI: diva2:242458
Available from: 2009-10-07 Created: 2009-10-07 Last updated: 2010-04-20

Open Access in DiVA

No full text

Other links

Publisher's full text

Search in DiVA

By author/editor
Jonsson, Peter
By organisation
TCSLAB - Theoretical Computer Science LaboratoryThe Institute of Technology
Computer Science

Search outside of DiVA

GoogleGoogle Scholar
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Altmetric score

Total: 43 hits
ReferencesLink to record
Permanent link

Direct link