[go: up one dir, main page]
More Web Proxy on the site http://driver.im/
Skip to main content
Springer Nature Link
Log in

Propositional Satisfiability in Answer-Set Programming

  • Conference paper
  • First Online:
KI 2001: Advances in Artificial Intelligence (KI 2001)

Part of the book series: Lecture Notes in Computer Science ((LNAI,volume 2174))

Included in the following conference series:

  • 452 Accesses

Abstract

We show that propositional logic and its extensions can support answer-set programming in the same way stable logic programming and disjunctive logic programming do. To this end, we introduce a logic based on the logic of propositional schemata and on a version of the Closed World Assumption. We call it the extended logic of propositional schemata with CWA (PS+, in symbols). An important feature of the logic PS+ is that it supports explicit modeling of constraints on cardinalities of sets. In the paper, we characterize the class of problems that can be solved by finite PS+ theories. We implement a programming system based on the logic PS+ and design and implement a solver for processing theories in PS+. We present encouraging performance results for our approach — we show it to be competitive with smodels, a state-of-the-art answer-set programming system based on stable logic programming.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

Reference

  1. K. Apt. Logic programming. In J. van Leeuven, editor, Handbook of theoretical computer science, pages 493–574. Elsevier, Amsterdam, 1990.

    Google Scholar 

  2. R.J. Bayardo, Jr and R.C. Schrag. Using CSP look-back techniques to solve real-world SAT instances. In Proceedings of the Fourteenth National Conference on Artificial Intelligence (AAAI-97). MIT Press, 1997.

    Google Scholar 

  3. K.L. Clark. Negation as failure. In H. Gallaire and J. Minker, editors, Logic and data bases, pages 293–322. Plenum Press, New York-London, 1978.

    Google Scholar 

  4. T. Eiter, N. Leone, C. Mateis, G. Pfeifer, and F. Scarcello. AKR system dlv: Progress report, comparisons and benchmarks. In Proceeding of the Sixth International Conference on Knowledge Representation and Reasoning (KR’ 98), pages 406–417. Morgan Kaufmann, 1998.

    Google Scholar 

  5. M.R. Garey and D.S. Johnson. Computers and intractability. A guide to the theory of NP-completeness. W.H. Freeman and Co., San Francisco, Calif., 1979.

    MATH  Google Scholar 

  6. M. Gelfond and V. Lifschitz. The stable semantics for logic programs. In R. Kowalski and K. Bowen, editors, Proceedings of the 5th International Conference on Logic Programming, pages 1070–1080. MIT Press, 1988.

    Google Scholar 

  7. M. Gelfond and V. Lifschitz. Classical negation in logic programs and disjunctive databases. New Generation Computing, 9:365–385, 1991.

    Article  Google Scholar 

  8. H.A. Kautz, D. McAllester, and B. Selman. Encoding plans in propositional logic. In Proceedings of KR-96, pages 374–384. Morgan Kaufmann, 1996.

    Google Scholar 

  9. H.A. Kautz and B. Selman. Unifying sat-based and graph-based planning. In Proceedings of IJCAI-99, San Mateo, CA, 1999. Morgan Kaufmann.

    Google Scholar 

  10. C.M. Li and M. Anbulagan. Look-ahead versus look-back for satisfiability problems. In Proceedings of the Third International Conference on Principles and Practice of Constraint Programming, 1997.

    Google Scholar 

  11. J. W. Lloyd. Foundations of logic programming. Symbolic Computation. Artificial Intelligence. Springer-Verlag, Berlin-New York, 1984.

    Google Scholar 

  12. W. Marek and J.B. Remmel. On the foundations of answer-set programming. In Answer-Set Programming: Towards Efficient and Scalable Knowledge Representation and Reasoning. AAAI Press, 2001. Papers from the 2001 AAAI Spring Symposium, Technical Report SS-01-01.

    Google Scholar 

  13. V.W. Marek and M. Truszczyński. Stable models and an alternative logic programming paradigm. In K.R. Apt, W. Marek, M. Truszczyński, and D.S. Warren, editors, The Logic Programming Paradigm: a 25-Year Perspective, pages 375–398. Springer Verlag, 1999.

    Google Scholar 

  14. I. Niemelä. Logic programming with stable model semantics as a constraint programming paradigm. Annals of Mathematics and Artificial Intelligence, 25(3-4):241–273, 1999.

    Article  MATH  MathSciNet  Google Scholar 

  15. I. Niemelä and P. Simons. Extending the smodels system with cardinality and weight constraints. In J. Minker, editor, Logic-Based Artificial Intelligence, pages 491–521. Kluwer Academic Publishers, 2000.

    Google Scholar 

  16. J. Schlipf. The expressive powers of the logic programming semantics. Journal of the Computer Systems and Science, 51(1):64–86, 1995.

    Article  MATH  MathSciNet  Google Scholar 

  17. B. Selman, H.A. Kautz, and B. Cohen. Noise strategies for improving local search. In Proceedings of the Twelfth National Conference on Artificial Intelligence (AAAI-94), Seattle, USA, 1994.

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Computer Science, University of Kentucky, Lexington, KY, 40506-0046, USA

    Deborah East & Mirosłlaw Truszczyński

Authors
  1. Deborah East
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Mirosłlaw Truszczyński
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Editors and Affiliations

  1. RWTH Aachen, Theoretical Computer Science, Ahornstrasse 55, 52074, Aachen, Germany

    Franz Baader

  2. Intelligent Systems Department, University of Leipzig, Computer Science Institute, Augustusplatz 10-11, 04109, Leipzig, Germany

    Gerhard Brewka

  3. Institute of Information Systems Knowledge-Based Systems Group, Vienna University of Technology, Favoritenstrasse 11, 1040, Wien, Austria

    Thomas Eiter

Rights and permissions

Reprints and permissions

Copyright information

© 2001 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

East, D., Truszczyński, M. (2001). Propositional Satisfiability in Answer-Set Programming. In: Baader, F., Brewka, G., Eiter, T. (eds) KI 2001: Advances in Artificial Intelligence. KI 2001. Lecture Notes in Computer Science(), vol 2174. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-45422-5_11

Download citation

  • DOI: https://doi.org/10.1007/3-540-45422-5_11

  • Published:

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-540-42612-7

  • Online ISBN: 978-3-540-45422-9

  • eBook Packages: Springer Book Archive

Publish with us

Policies and ethics

Search

Navigation