Welcome!
To use the personalized features of this site, please log in or register.
If you have forgotten your username or password, we can help.
|
 |
Two-Literal Logic Programs and Satisfiability Representation of Stable Models: A Comparison
| |
|
Two-Literal Logic Programs and Satisfiability Representation of Stable Models: A Comparison
Guan-Shieng Huang3, Xiumei Jia4, Churn-Jung Liau5 and Jia-Huai You4 
| (3) |
Department of Computer Science, National Taiwan University, Taipei, Taiwan |
| (4) |
Department of Computing Science, University of Alberta, Edmonton, Canada |
| (5) |
Institute of Information Science, Academia Sinica, Taipei, Taiwan |
Abstract
Logic programming with the stable model semantics has been proposed as a constraint programming paradigm for solving constraint
satisfaction and other combinatorial problems. In such a language one writes function-free logic programs with negation. Such
a program is instantiated to a ground program and its stable models are computed. In this paper, we identify a class of logic
programs for which the current techniques in solving SAT problems can be adopted for the computation of stable models efficiently.
These logic programs are called 2-literal programs where each rule or constraint consists of at most 2 literals. Many logic programming encodings of graph-theoretic, combinatorial
problems given in the literature fall into the class of 2-literal programs. We show that a 2-literal program can be translated
to a SAT instance in polynomial time without using extra variables. We report and compare experimental results on solving
a number of benchmarks by a stable model generator and by a SAT solver.
Fulltext Preview (Small, Large)
 References secured to subscribers.
|
|
|
|
|
|