[Back]

C. Feier:
"Worst-Case Optimal Reasoning with Forest Logic Programs";
Report for Institut für Informationssysteme ArbeitsBereich Wissenbasierte Systeme; Report No. INFSYS RR-1843-11-07, 2011; 40 pages.

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.

Forest Logic Programs, Open Answer Set Programming, tableau algorithm, optimization, knowledge compilation