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.
My Menu
Saved Items

Two-Literal Logic Programs and Satisfiability Representation of Stable Models: A Comparison

Guan-Shieng Huang3, Xiumei Jia4, Churn-Jung Liau5 and Jia-Huai YouContact Information

(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.

Contact Information Jia-Huai You
Email: you@cs.ualberta.ca
Fulltext Preview (Small, Large)
Image of the first page of the fulltext

References secured to subscribers.



Export this chapter
Export this chapter as RIS | Text
 
Remote Address: 38.107.191.109 • Server: mpweb23
HTTP User Agent: CCBot/1.0 (+http://www.commoncrawl.org/bot.html)