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
The Complexity of Abduction for Equality Constraint Languages
Linköping University, Department of Computer and Information Science, Software and Systems. Linköping University, The Institute of Technology. (TCSLAB)
Linköping University, Department of Computer and Information Science, Software and Systems. Linköping University, The Institute of Technology. (TCSLAB)
2013 (English)In: Computer Science Logic 2013 / [ed] Simona Ronchi Della Rocca, 2013, 615-633 p.Conference paper, Published paper (Refereed)
Abstract [en]

Abduction is a form of nonmonotonic reasoning that looks for an explanation for an observed manifestation according to some knowledge base. One form of the abduction problem studied in the literature is the propositional abduction problem parameterized by a structure \Gamma over the two-element domain. In that case, the knowledge base is a set of constraints over \Gamma, the manifestation and explanation are propositional formulas. In this paper, we follow a similar route. Yet, we consider abduction over infinite domain. We study the equality abduction problem parameterized by a relational first-order structure \Gamma over the natural numbers such that every relation in \Gamma is definable by a Boolean combination of equalities, a manifestation is a literal of the form (x = y) or (x != y), and an explanation is a set of such literals. Our main contribution is a complete complexity characterization of the equality abduction problem. We prove that depending on \Gamma, it is \Sigma^P_2-complete, or NP-complete, or in P.

Place, publisher, year, edition, pages
2013. 615-633 p.
Series
Leibniz International Proceedings in Informatics, ISSN 1868-8969 ; 23
Keyword [en]
Abduction, infinite structures, equality constraint languages, computational complexity, algebraic approach
National Category
Computer Science
Identifiers
URN: urn:nbn:se:liu:diva-102674DOI: 10.4230/LIPIcs.CSL.2013.615ISBN: 978-3-939897-60-6 (print)OAI: oai:DiVA.org:liu-102674DiVA: diva2:680751
Conference
22nd EACSL Annual Conference on Computer Science Logic (CSL-2013) September 2-5, 2013, Torino, Italy
Available from: 2013-12-18 Created: 2013-12-18 Last updated: 2014-01-21Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full text

Authority records BETA

Schmidt, JohannesWrona, Michal

Search in DiVA

By author/editor
Schmidt, JohannesWrona, Michal
By organisation
Software and SystemsThe Institute of Technology
Computer Science

Search outside of DiVA

GoogleGoogle Scholar

doi
isbn
urn-nbn

Altmetric score

doi
isbn
urn-nbn
Total: 24 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