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

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • oxford
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
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, p. 341-357Article 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, p. 341-357
Keywords [en]
modal logic, poor man's logic, computational complexity, disjunction
National Category
Computer Sciences
Identifiers
URN: urn:nbn:se:liu:diva-22145DOI: 10.3166/jancl.15.341-357Local ID: 1253OAI: oai:DiVA.org:liu-22145DiVA, id: diva2:242458
Available from: 2009-10-07 Created: 2009-10-07 Last updated: 2018-01-13

Open Access in DiVA

No full text in DiVA

Other links

Publisher's full text

Authority records BETA

Jonsson, Peter

Search in DiVA

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

Search outside of DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetric score

doi
urn-nbn
Total: 54 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • oxford
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf