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

Direct link
Cite
Citation style
  • apa
  • 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
Navigating and Querying Answer Sets: How Hard Is It Really and Why?
TU Dresden.
Massachusetts Institute of Technology.ORCID iD: 0000-0003-0131-6771
University of Klagenfurt.
TU Dresden.
Show others and affiliations
2024 (English)In: Proceedings of the 21st International Conference on Principles of Knowledge Representation and Reasoning (KR'24) / [ed] Pierre Marquis, Magdalena Ortiz, Maurice Pagnucco, IJCAI Organization , 2024, p. 642-653Conference paper, Published paper (Refereed)
Abstract [en]

Answer set programming is a popular declarative paradigm with countless applications for modeling and solving combinatorial problems. We can view a program as a knowledge database compactly representing conditions for solutions. Often we are interested in reasoning about solutions of filtering answer sets. At the heart of these questions is brave and cautious reasoning. For browsing answer sets, we combine both as restricting atoms of answer sets is only meaningful for atoms called facets that belong to some (brave) but not to all answer sets (cautious). Surprisingly, the precise computational complexity of facet problems remained widely open so far. In this paper, we study the complexity of answer set facets. We establish tight results for reasoning with facets, deciding upper and lower bounds as well as the exact number of facets, and comparing facets. Facet reasoning seems to be a natural problem formalism, residing in complexity families ΣP , ΠP , DP , and ΘP, up to the third level. Moreover, our study considers quantitative importance questions on facets and generalizing from facets to conjunctions, disjunctions, and arbitrary queries. We complete our results by an experimental evaluation.

Place, publisher, year, edition, pages
IJCAI Organization , 2024. p. 642-653
Keywords [en]
Computational aspects of knowledge representation-General, Knowledge compilation, automated reasoning, satisfiability and model counting-General, Logic programming, answer set programming-General
National Category
Computer Sciences
Identifiers
URN: urn:nbn:se:liu:diva-207045DOI: 10.24963/kr.2024/60ISBN: 9781956792058 (print)OAI: oai:DiVA.org:liu-207045DiVA, id: diva2:1893144
Conference
21st International Conference on Principles of Knowledge Representation and Reasoning, Hanoi, Vietnam. November 2-8, 2024
Funder
ELLIIT - The Linköping‐Lund Initiative on IT and Mobile CommunicationsAvailable from: 2024-08-28 Created: 2024-08-28 Last updated: 2024-11-04Bibliographically approved

Open Access in DiVA

No full text in DiVA

Other links

Publisher's full text

Authority records

Fichte, Johannes Klaus

Search in DiVA

By author/editor
Hecher, MarkusFichte, Johannes Klaus
By organisation
Software and SystemsFaculty of Science & Engineering
Computer Sciences

Search outside of DiVA

GoogleGoogle Scholar

doi
isbn
urn-nbn

Altmetric score

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

Direct link
Cite
Citation style
  • apa
  • 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