Reasoning with Forest Logic Programs Using Fully Enriched Automata

Cristina Feier, Thomas Eiter

Abstract

This paper addresses the computational complexity of reasoning with Forest Logic Programs (FoLPs), a fragment of Open Answer Set Programming (OASP) that combines the strengths of Description Logics and Answer Set Programming. By reducing the problem to the emptiness checking of Fully Enriched Automata (FEAs), the authors prove that satisfiability in FoLPs is EXPTIME-complete. This result demonstrates that adding expressive rule-based structures to description logics like $SHOQ$ does not increase worst-case complexity.

Introduction

In the field of Knowledge Representation, researchers strive to bridge two distinct paradigms: Description Logics (DL), which excel at defining hierarchies and open-world concepts, and Answer Set Programming (ASP), which is optimized for rule-based reasoning and closed-world negation. Open Answer Set Programming (OASP) attempts to unify these approaches. Within OASP, Forest Logic Programs (FoLPs) are a particularly significant fragment due to their "forest model property"—the principle that if a solution exists, it can be represented as a collection of trees (a forest).

Illustration of the forest model property in FoLPs, showing how a graph structure (a) can be represented as a forest (b).

While FoLPs are expressive enough to simulate complex description logics like $SHOQ$, their exact computational complexity remained an open question for years. Previous algorithmic approaches suggested bounds as high as NEXPTIME or 2NEXPTIME, creating a gap between the known EXPTIME-hard lower bound and the best available upper bounds. This paper closes that gap by establishing an optimal EXPTIME upper bound.

Methodology: An Automata-Theoretic Approach

The authors move away from traditional tableau-based algorithms, which are often difficult to optimize for worst-case complexity, and instead employ an automata-theoretic approach.

  1. Fully Enriched Automata (FEAs): These sophisticated automata operate on infinite forests and support features such as graded modalities (counting successors) and nominals (referring to specific root nodes).
  2. The Reduction: The core of the paper is a mathematical reduction that translates a FoLP into an FEA. The FEA is designed to accept a forest if and only if that forest represents a "well-supported" model of the logic program.
  3. Handling Well-Supportedness: A key challenge in ASP is ensuring that every fact is derived through a finite chain of rules, avoiding circular reasoning. The authors map this requirement to the parity acceptance condition of the FEA. If the automaton detects an infinite loop of dependencies, it rejects the input.
  4. Successor Addressing: Unlike standard automata, FEAs do not naturally distinguish between different branches of a tree. The authors developed a specific addressing mechanism to ensure rules correctly identify which successor variable corresponds to which node in the forest.

Key Insights and Ideas

  • Complexity Parity: A major finding is that reasoning with FoLP rules is no more complex than reasoning with the description logic $SHOQ$ itself. This suggests that expressive rules can be added to ontologies "for free" in terms of worst-case complexity.
  • Parity as Support: Utilizing the parity condition of an automaton to enforce the "well-supportedness" of an answer set is an elegant method for handling the non-monotonic nature of ASP within a framework typically used for monotonic logics.
  • Constants as Roots: The paper treats constants in the logic program as roots of the forest. This allows the FEA to use its nominal capabilities to jump back to specific individuals from anywhere in the forest, effectively modeling how constants break a pure tree structure.

Key Results

The paper formally proves that checking the satisfiability of a unary predicate in a FoLP is EXPTIME-complete. By providing a reduction to FEA emptiness (which is solvable in EXPTIME), the authors established a new, tighter upper bound that matches the existing lower bound. This result also implies that reasoning with "f-hybrid knowledge bases"—which combine $SHOQ$ ontologies and FoLP rules without restrictions on term sharing—is also EXPTIME-complete.

Conclusion and Future Work

While the paper settles the theoretical complexity, several practical hurdles remain. Automata-theoretic reductions are often worst-case optimal but can be difficult to implement efficiently for real-world problems compared to tableau methods. The authors suggest that the next step is to determine if insights from this automata approach can improve AND/OR tableau algorithms, which are generally more practical for software tools. Additionally, streamlining the complex successor addressing mechanism remains an area for potential improvement.

Summary updated

Abstract

Forest Logic Programs (FoLP) are a decidable fragment of Open Answer Set Programming (OASP) which have the forest model property. OASP extends Answer Set Programming (ASP) with open domains—a feature which makes it possible for FoLPs to simulate reasoning with the description logic \(\mathcal {SHOQ}\). In the past, several tableau algorithms have been devised to reason with FoLPs, the most recent of which established a NExpTime upper bound for reasoning with the fragment. While known to be ExpTime-hard, the exact complexity characterization of reasoning with FoLPs was still unknown. In this paper we settle this open question by a reduction of reasoning with FoLPs to emptiness checking of fully enriched automata which are known to be ExpTime-complete.
BibTeX
@inproceedings{feier2015reasoning,
  author = {Cristina Feier and Thomas Eiter},
  title = {{Reasoning with Forest Logic Programs Using Fully Enriched Automata}},
  booktitle = {LPNMR},
  year = {2015},
  doi = {10.1007/978-3-319-23264-5\_29},
}
Figure