Vorträge und Posterpräsentationen (mit Tagungsband-Eintrag):
J. Fichte, M. Hecher, I. Schindler:
"Default Logic and Bounded Treewidth";
Vortrag: Language and Automata Theory and Applications (LATA),
Ramat Gan, Israel;
09.04.2018
- 11.04.2018; in: "12th International Conference Language and Automata theory and Applications (LATA)",
Springer,
10792
(2018),
ISBN: 978-3-319-77312-4;
S. 130
- 142.
Kurzfassung englisch:
In this paper, we study Reiter´s propositional default logic when the treewidth of a certain graph representation (semi-primal graph) of the input theory is bounded. We establish a dynamic programming algorithm on tree decompositions that decides whether a theory has a consistent stable extension (Ext). Our algorithm can even be used to enumerate all generating defaults (EnumSE) that lead to stable extensions. We show that our algorithm decides Ext in linear time in the input theory and triple exponential time in the treewidth (so-called fixed-parameter linear algorithm). Further, our algorithm solves EnumSE with a pre-computation step that is linear in the input theory and triple exponential in the treewidth followed by a linear delay to output solutions.
Schlagworte:
Parameterized algorithms; Tree decompositions; Dynamic programming; Reiter´s default logic; Propositional logic
"Offizielle" elektronische Version der Publikation (entsprechend ihrem Digital Object Identifier - DOI)
http://dx.doi.org/10.1007/978-3-319-77313-1_10
Elektronische Version der Publikation:
https://publik.tuwien.ac.at/files/publik_273220.pdf
Zugeordnete Projekte:
Projektleitung Stefan Woltran:
START
Erstellt aus der Publikationsdatenbank der Technischen Universität Wien.