Endre søk
RefereraExporteraLink to record
Permanent link

Direct link
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Annet format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annet språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf
Complexity of propositional abduction for restricted sets of Boolean functions
Laboratoire d’Informatique Fondamentale, CNRS Universit ́ e d’Aix-Marseille, France.
Laboratoire d’Informatique Fondamentale, CNRS Universit ́ e d’Aix-Marseille, France.
Institut für Theoretische Informatik Gottfried Wilhelm Leibniz Universität, Hannover, Germany.
2010 (engelsk)Inngår i: Proceedings of the Twelfth International Conference on the Principles of Knowledge Representation and Reasoning (KR 2010), AAAI Press, 2010Konferansepaper, Publicerat paper (Fagfellevurdert)
Abstract [en]

Abduction is a fundamental and important form of non-monotonic reasoning. Given a knowledge base explaining how the world behaves it aims at finding an explanation for some observed manifestation. In this paper we focus on propositional abduction, where the knowledge base and the manifestation are represented by propositional formulae. The problem of deciding whether there exists an explanation has been shown to beΣp2-complete in general. We consider variants obtained by restricting the allowed connectives in the formulae to certain sets of Boolean functions. We give a complete classification of the complexity for all considerable sets of Boolean functions. In this way, we identify easier cases, namely NP-complete and polynomial cases; and we highlight sources of intractability. Further, we address the problem of counting the explanations and draw a complete picture for the counting complexity.

sted, utgiver, år, opplag, sider
AAAI Press, 2010.
HSV kategori
Identifikatorer
URN: urn:nbn:se:hj:diva-31624OAI: oai:DiVA.org:hj-31624DiVA, id: diva2:957167
Konferanse
The Twelfth International Conference on the Principles of Knowledge Representation and Reasoning, May 9 – 13, 2010, Toronto, Canada
Tilgjengelig fra: 2016-09-01 Laget: 2016-09-01 Sist oppdatert: 2018-01-10bibliografisk kontrollert

Open Access i DiVA

Fulltekst mangler i DiVA

Andre lenker

Fulltext

Person

Schmidt, Johannes

Søk i DiVA

Av forfatter/redaktør
Schmidt, Johannes

Søk utenfor DiVA

GoogleGoogle Scholar

urn-nbn

Altmetric

urn-nbn
Totalt: 75 treff
RefereraExporteraLink to record
Permanent link

Direct link
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Annet format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annet språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf