Publikation: Structural Decompositions of Epistemic ...
Stammdaten
Titel: | Structural Decompositions of Epistemic Logic Programs |
Untertitel: | |
Kurzfassung: | Epistemic logic programs (ELPs) are a popular generalization of standard Answer Set Programming (ASP) providing means for reasoning over answer sets within the language. This richer formalism comes at the price of higher computational complexity reaching up to the fourth level of the polynomial hierarchy. However, in contrast to standard ASP, dedicated investigations towards tractability have not been undertaken yet. In this paper, we give first results in this direction and show that central ELP problems can be solved in linear time for ELPs exhibiting structural properties in terms of bounded treewidth. We also provide a full dynamic programming algorithm that adheres to these bounds. Finally, we show that applying treewidth to a novel dependency structure---given in terms of epistemic literals---allows to bound the number of ASP solver calls in typical ELP solving procedures. |
Schlagworte: |
Publikationstyp: | Abstract (Autorenschaft) |
Erscheinungsdatum: | 18.09.2020 (Online) |
Erschienen in: |
ICLP20WS 2020
ICLP20WS 2020
(
CEUR-Workshop Proceedings;
)
zur Publikation |
Titel der Serie: | - |
Bandnummer: | - |
Heftnummer: | - |
Erstveröffentlichung: | Ja |
Version: | - |
Seite: | S. 1 - 2 |
Versionen
Keine Version vorhanden |
Erscheinungsdatum: | 18.09.2020 |
ISBN (e-book): | - |
eISSN: | - |
DOI: | - |
Homepage: | http://ceur-ws.org/Vol-2678/short1.pdf |
Open Access |
|
AutorInnen
Zuordnung
Organisation | Adresse | ||||
---|---|---|---|---|---|
Fakultät für Technische Wissenschaften
Institut für Artificial Intelligence und Cybersecurity
|
AT - A-9020 Klagenfurt |
Kategorisierung
Sachgebiete | |
Forschungscluster | Kein Forschungscluster ausgewählt |
Peer Reviewed |
|
Publikationsfokus |
Klassifikationsraster der zugeordneten Organisationseinheiten:
|
Arbeitsgruppen | Keine Arbeitsgruppe ausgewählt |
Kooperationen
Organisation | Adresse | ||
---|---|---|---|
Technische Universität Wien
|
AT - 1040 Wien |
Forschungsaktivitäten
(Achtung: Externe Aktivitäten werden im Suchergebnis nicht mitangezeigt)
Projekte: | Keine verknüpften Projekte vorhanden |
Publikationen: | Keine verknüpften Publikationen vorhanden |
Veranstaltungen: |
|
Vorträge: |
|