Wissenschaftliche Berichte:
C. Feier:
"Worst-Case Optimal Reasoning with Forest Logic Programs";
Bericht für Institut für Informationssysteme ArbeitsBereich Wissenbasierte Systeme;
Berichts-Nr. INFSYS RR-1843-11-07,
2011;
40 S.
Kurzfassung englisch:
Abstract. This report describes a new worst-case optimal tableau algorithm for reasoning with Forest Logic Programs (FoLPs), a decidable fragment of Open Answer Set Programming. FoLPs are a
useful device for tight integration of the Description Logic and the Logic Programming worlds: reasoning with the DL SHOQ can be simulated within the fragment. The algorithm improves on previous results concerning reasoning with the fragment by decreasing the worst-case running time with one exponential level. The decrease in complexity is mainly due to the usage of a new caching rule, whose introduction is highly non-trivial: this has been made possible by employing a different strategy for reducing an infinite model to a model of finite bounded size. The algorithm also reuses a knowledge compilation technique introduced in previous work.
Schlagworte:
Forest Logic Programs, Open Answer Set Programming, tableau algorithm, optimization, knowledge compilation
Erstellt aus der Publikationsdatenbank der Technischen Universität Wien.