Hostname: page-component-78c5997874-j824f Total loading time: 0 Render date: 2024-11-19T05:18:47.013Z Has data issue: false hasContentIssue false
  • English
  • Français

Transition systems for model generators—A unifying approach

Published online by Cambridge University Press:  06 July 2011

YULIYA LIERLER  and
MIROSLAW TRUSZCZYNSKI
YULIYA LIERLER
Affiliation:
Department of Computer Science, University of Kentucky, Lexington, KY 40506-0633, USA (e-mail: [email protected], [email protected])
MIROSLAW TRUSZCZYNSKI
Affiliation:
Department of Computer Science, University of Kentucky, Lexington, KY 40506-0633, USA (e-mail: [email protected], [email protected])
Get access Rights & Permissions [Opens in a new window]

Abstract

A fundamental task for propositional logic is to compute models of propositional formulas. Programs developed for this task are called satisfiability solvers. We show that transition systems introduced by Nieuwenhuis, Oliveras, and Tinelli to model and analyze satisfiability solvers can be adapted for solvers developed for two other propositional formalisms: logic programming under the answer-set semantics, and the logic PC(ID). We show that in each case the task of computing models can be seen as “satisfiability modulo answer-set programming,” where the goal is to find a model of a theory that also is an answer set of a certain program. The unifying perspective we develop shows, in particular, that solvers clasp and minisat(id) are closely related despite being developed for different formalisms, one for answer-set programming and the latter for the logic PC(ID).

Type
Regular Papers
Information
Theory and Practice of Logic Programming , Volume 11 , Special Issue 4-5: 27th International Conference on Logic Programming , July 2011 , pp. 629 - 646
Copyright
Copyright © Cambridge University Press 2011

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Clark, K. 1978. Negation as failure. In Logic and Data Bases, Gallaire, H. and Minker, J., Eds. Plenum, New York, 293–322.CrossRefGoogle Scholar
Cook, S. A. and Reckhow, R. A. 1979. The relative efficiency of propositional proof systems. Journal of Symbolic Logic 44, 36–50.CrossRefGoogle Scholar
Davis, M., Logemann, G. and Loveland, D. 1962. A machine program for theorem proving. Communications of the ACM 5 (7), 394–397.CrossRefGoogle Scholar
Denecker, M. 2000. Extending classical logic with inductive definitions. In Proc. of 1st International Conference on Computational Logic (CL '00). Lecture Notes in Computer Science, vol. 1861. Springer, Berlin, 703–717.Google Scholar
Eiter, T., Leone, N., Mateis, C., Pfeifer, G. and Scarcello, F. 1997. A deductive system for nonmonotonic reasoning. In Proc. of 4th International Conference on Logic Programming and Nonmonotonic Reasoning (LPNMR '97). Lecture Notes in Computer Science, vol. 1265. Springer, Berlin, 363–374.CrossRefGoogle Scholar
Ferraris, P. and Lifschitz, V. 2005. Weight constraints as nested expressions. Theory and Practice of Logic Programming 5, 45–74.CrossRefGoogle Scholar
Gebser, M., Kaufmann, B., Neumann, A. and Schaub, T. 2007. Conflict-driven answer set solving. In Proc. of 20th International Joint Conference on Artificial Intelligence (IJCAI '07), 386–392.Google Scholar
Gebser, M. and Schaub, T. 2006. Tableau calculi for answer set programming. In Proc. of 22nd International Conference on Logic Programming (ICLP '06). Lecture Notes in Computer Science, vol. 4079. Springer, Berlin, 11–25.Google Scholar
Gelfond, M. and Lifschitz, V. 1988. The stable model semantics for logic programming. In Proc. of 5th International Logic Programming Conference and Symposium, Kowalski, R. and Bowen, K., Eds. MIT Press, Cambridge, MA, 1070–1080.Google Scholar
Giunchiglia, E., Leone, N. and Maratea, M. 2008. On the relation among answer set solvers. Annals of Mathematics and Artificial Intelligence 53 (1–4), 169–204.CrossRefGoogle Scholar
Giunchiglia, E., Lierler, Y. and Maratea, M. 2004. SAT-based answer set programming. In Proc. of 19th National Conference on Artificial Intelligence (AAAI '04). AAAI Press, Menlo Park, CA, 61–66.Google Scholar
Giunchiglia, E. and Maratea, M. 2005. On the relation between answer set and SAT procedures (or, between smodels and cmodels). In Proc. of the 21st International Conference on Logic Programming (ICLP '05). Lecture Notes in Computer Science, vol. 3668. Springer, Berlin, 37–51.Google Scholar
Lee, J. 2005. A model-theoretic counterpart of loop formulas. In Proc. of 19th International Joint Conference on Artificial Intelligence (IJCAI '05). Professional Book Center, 503–508.Google Scholar
Leone, N., Rullo, P. and Scarcello, F. 1997. Disjunctive stable models: Unfounded sets, fixpoint semantics, and computation. Information and Computation 135 (2), 69–112.CrossRefGoogle Scholar
Lierler, Y. 2010. Sat-Based Answer Set Programming. PhD Thesis, University of Texas, Austin, TX.Google Scholar
Lierler, Y. 2011. Abstract answer set solvers with backjumping and learning. Theory and Practice of Logic Programming 11, 135–169.CrossRefGoogle Scholar
Lifschitz, V., Tang, L. R. and Turner, H. 1999. Nested expressions in logic programs. Annals of Mathematics and Artificial Intelligence 25, 369–389.CrossRefGoogle Scholar
Lin, F. and Zhao, Y. 2004. ASSAT: Computing answer sets of a logic program by SAT solvers. Artificial Intelligence 157, 115–137.CrossRefGoogle Scholar
Marek, V. and Truszczyński, M. 1999. Stable models and an alternative logic programming paradigm. In The Logic Programming Paradigm: A 25-Year Perspective. Springer Verlag, Berlin, 375–398.CrossRefGoogle Scholar
Mariën, M. 2009. Model Generation for ID-Logic. PhD Thesis, Katholieke Universiteit Leuven, Belgium.Google Scholar
Mariën, M., Gilis, D. and Denecker, M. 2004. On the relation between ID-logic and answer set programming. In Proc. of 9th European Conference on Logics in Artificial Intelligence (JELIA '04). Lecture Notes in Computer Science, vol. 3229. Springer, Berlin, 108–120.Google Scholar
Mariën, M., Wittocx, J., Denecker, M. and Bruynooghe, M. 2008. SAT(ID): Satisfiability of propositional logic extended with inductive definitions. In Proc. of 11th International Conference on Theory and Applications of Satisfiability Testing (SAT '08). Lecture Notes in Computer Science, vol. 4996. Springer, Berlin, 211–224.Google Scholar
Niemelä, I. 1999. Logic programs with stable model semantics as a constraint programming paradigm. Annals of Mathematics and Artificial Intelligence 25, 241–273.CrossRefGoogle Scholar
Niemelä, I. and Simons, P. 2000. Extending the Smodels system with cardinality and weight constraints. In Logic-Based Artificial Intelligence, Minker, J., Ed. Kluwer, Dordrecht, 491–521.CrossRefGoogle Scholar
Nieuwenhuis, R., Oliveras, A. and Tinelli, C. 2006. Solving SAT and SAT modulo theories: From an abstract Davis-Putnam-Logemann-Loveland procedure to DPLL(T). Journal of the ACM 53 (6), 937–977.CrossRefGoogle Scholar
Oikarinen, E. and Janhunen, T. 2006. Modular equivalence for normal logic programs. In Proc. of 17th European Conference on Artificial Intelligence (ECAI '06). IOS Press, Amsterdam, 412–416.Google Scholar
Van Gelder, A., Ross, K. and Schlipf, J. 1991. The well-founded semantics for general logic programs. Journal of ACM 38 (3), 620–650.CrossRefGoogle Scholar
Ward, J. and Schlipf, J. 2004. Answer set programming with clause learning. In Proc. of 7th International Conference on Logic Programming and Nonmonotonic Reasoning (LPNMR '04). Lecture Notes in Computer Science, vol. 2923. Springer, Berlin, 302–313.Google Scholar
Supplementary material: PDF

LIERLER and TRUSZCZYNSKI supplementary material

Appendix

Download LIERLER and TRUSZCZYNSKI supplementary material(PDF)
PDF 180.9 KB