Translating First-Order Theories into Logic Programs

Heng Zhang, Yan Zhang, Mingsheng Ying, Yi ZhouIJCAI 2011 · DOI

Abstract

This paper presents a formal method for translating First-Order (FO) theories under stable model semantics and circumscription into disjunctive logic programs. By leveraging finite structures and linear ordering, the authors develop the T2LP tool, which enables the use of high-performance Answer Set Programming (ASP) solvers to solve complex logical problems. Experimental results on $\Sigma_2^p$-complete benchmarks demonstrate significant performance gains, particularly when using the CLASPD solver backend.

Introduction

The trade-off between expressive naturalness and computational efficiency is a central challenge in knowledge representation. First-Order logic offers a natural way to describe complex domains but lacks efficient solvers for non-monotonic reasoning. Conversely, Answer Set Programming (ASP) provides highly optimized solvers but often requires cumbersome encodings to represent complex logical constraints, especially those involving quantifiers ($\forall, \exists$). This work bridges the gap by providing a systematic translation from FO theories to logic programs, allowing researchers to utilize existing ASP solvers like CLASPD and DLV for high-level logical problems.

Methodology

The core contribution is a translation method ($\tau$) that eliminates existential quantifiers in finite structures. Since the domain is finite and has a linear order, the search for a "witness" can be simulated by introducing auxiliary predicates that track properties across the domain. By repeatedly applying this translation, any FO sentence in prenex normal form can be reduced to a universal sentence, which is then converted into a disjunctive logic program.

Additionally, the authors discovered a mapping ($\pi_P$) that embeds circumscription into stable model semantics without requiring auxiliary predicates. These translations are implemented in the T2LP tool, which compiles FO theories into logic programs that can be executed against various input datasets.

Experimental Evaluation

The authors evaluated the T2LP approach using two $\Sigma_2^p$-complete benchmarks: 2-Clique Coloring and a modified version of QBF Satisfiability. These problems are notoriously difficult to encode naturally in standard logic programming.

Performance comparison on the 2-Clique Coloring benchmark, showing execution times in seconds.

As illustrated in Figure 1, the T2LP solver paired with the CLASPD backend significantly outperformed the DLV backend on the Clique Coloring problem. For instance, T2LP+CLASPD solved instances with 100 vertices in approximately 80 seconds, whereas the DLV backend frequently timed out (exceeding one hour) on instances with as few as 40 vertices.

Performance comparison on the QBF Satisfiability benchmark.

Figure 2 shows the results for the QBF benchmark. In this case, T2LP+CLASPD maintained scalability for larger instances (up to $n=120$), consistently outperforming the DLV-based approach which struggled with timeouts as the problem size increased.

Key Insights and Discussion

  • Necessity of Auxiliaries: The authors mathematically prove that eliminating quantifiers in FO stable model semantics requires the introduction of auxiliary predicates, justifying the complexity of their method.
  • The Power of Finite Structures: By assuming the domain is finite and has a linear order, existential quantification can be treated as a search problem unrolled into a logic program.
  • Compatibility of Formalisms: The successful embedding of circumscription into stable models suggests a deep relationship between these two non-monotonic reasoning frameworks.
  • Limitations: The conversion process can lead to an exponential increase in formula size in the worst case due to distributive laws. Furthermore, the current implementation relies on built-in successor relations in ASP solvers.

Conclusion

This work provides the first general approach for computing arbitrary first-order theories over finite structures under stable model and circumscription semantics. While the results are optimistic, future work will focus on refining the translation to minimize the size of the resulting logic programs and enhancing the tool's flexibility regarding domain structures.

Summary updated

BibTeX
@inproceedings{zhang2011translating,
  author = {Heng Zhang and Yan Zhang and Mingsheng Ying and Yi Zhou},
  title = {{Translating First-Order Theories into Logic Programs}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2011},
  doi = {10.5591/978-1-57735-516-8/ijcai11-192},
}
Figure