Abstract
Answer set programming (ASP) is a declarative programming paradigm based on an interpretation of logical rules as constraints. In this article, we relate answer set programming with other constraint-based solving paradigms: Boolean satisfiability checking, satisfiability modulo theories, mixed integer programming, and constraint programming. We illustrate the relationship of ASP with these alternative paradigms in terms of simple examples, and identify the main primitives and characteristics of the constraint-based languages under consideration.

Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.References
Balduccini M, Lierler Y (2017) Constraint answer set solver EZCSP and why integration schemas matter. TPLP 17(4):462–515
Banbara M, Kaufmann B, Ostrowski M, Schaub T (2017) Clingcon: the next generation. TPLP 17(4):408–461
Biere A, Heule M, van Maaren H, Walsh T (eds) (2009) Handbook of satisfiability. Frontiers in artificial intelligence and applications, vol 185. IOS Press, Amsterdam
Bomanson J, Gebser M, Janhunen T, Kaufmann B, Schaub T (2016) Answer set programming modulo acyclicity. Fundamenta Informaticae 147(1):63–91
Brewka G, Eiter T, Truszczyński M (2011) Answer set programming at a glance. Commun ACM 54(12):92–103
De Rosis A, Eiter T, Redl C, Ricca F (2015) Constraint answer set programming based on HEX-programs. Presented at the 8th Workshop on Answer Set Programming and Other Computing Paradigms (ASPOCP). https://sites.google.com/site/aspocp2015/ASPOCP2015paper7.pdf?attredirects=0
Drescher C (2015) Conflict-driven constraint answer set solving. PhD thesis, University of New South Wales, Sydney, Australia
Drescher C, Walsh T (2011) Translation-based constraint answer set solving. In: Proceedings of IJCAI 2011, AAAI Press, pp 2596–2601
Ferraris P (2005) Answer sets for propositional theories. In: Proceedings of LPNMR’05. LNAI, vol 3662. Springer, Berlin, pp 119–131
Gebser M, Kaufmann B, Schaub T (2009a) Solution enumeration for projected Boolean search problems. In: Proceedings of CPAIOR 2009. LNCS, vol 5547. Springer, Berlin, pp 71–86
Gebser M, Ostrowski M, Schaub T (2009b) Constraint answer set solving. In: Proceedings of ICLP 2009. LNCS, vol 5649. Springer, Berlin, pp 235–249
Gebser M, Janhunen T, Rintanen J (2014) Answer set programming as SAT modulo acyclicity. In: Proceedings of ECAI 2014. IOS Press, Amsterdam, pp 351–356
Gebser M, Janhunen T, Kaminski R, Schaub T, Tasharrofi S (2016) Writing declarative specifications for clauses. In: Proceedings of JELIA’16, pp 256–271
Gebser M, Kaminski R, Kaufmann B, Ostrowski M, Schaub T, Wanko P (2016) Theory solving made easy with clingo 5. In: Technical communications of ICLP 2016, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, OASICS, vol 52, pp 2:1–2:15
Huang J (2008) Universal Booleanization of constraint models. In: Proceedings of CP 2008. LNCS, vol 5202. Springer, Berlin, pp 144–158
Janhunen T (2006) Some (in)translatability results for normal logic programs and propositional theories. J Appl NonClass Log 16(1–2):35–86
Janhunen T, Niemelä I (2016) The answer set programming paradigm. AI Mag 37(3):13–24
Janhunen T, Niemelä I, Sevalnev M (2009) Computing stable models via reductions to difference logic. In: Proceedings of LPNMR 2009. LNCS, vol 5753. Springer, Berlin, pp 142–154
Janhunen T, Kaminski R, Ostrowski M, Schaub T, Schellhorn S, Wanko P (2017) Clingo goes linear constraints over reals and integers. TPLP 17(5–6):872–888
Lierler Y (2017) What is answer set programming to propositional satisfiability. Constraints 22(3):307–337
Lifschitz V, Razborov A (2006) Why are there so many loop formulas? ACM Trans Comput Log 7(2):261–268
Lin F, Zhao J (2003) On tight logic programs and yet another translation from normal logic programs to propositional logic. In: Proceedings of IJCAI 2003. Morgan Kaufmann, Burlington, pp 853–858
Liu G, Janhunen T, Niemelä I (2012) Answer set programming via mixed integer programming. In: Proceedings of KR 2012. AAAI Press, Toronto, pp 32–42
Nguyen M, Janhunen T, Niemelä I (2011) Translating answer-set programs into bit-vector logic. In: Proceedings of INAP 2011. LNCS, vol 7773. Springer, Berlin, pp 95–113
Niemelä I (1999) Logic programs with stable model semantics as a constraint programming paradigm. Ann Math Artif Intell 25(3–4):241–273
Pearce D, Sarsakov V, Schaub T, Tompits H, Woltran S (2002) A polynomial translation of logic programs with nested expressions into disjunctive logic programs: preliminary report. In: Proceedings of ICLP 2002, Springer, LNCS 2401, pp 405–420
Rossi F, van Beek P, Walsh T (eds) (2006) Handbook of constraint programming. Foundations of artificial intelligence, vol 2. Elsevier, Amsterdam
Tseitin G (1983) On the complexity of derivation in propositional calculus. In: Siekmann J, Wrightson G (eds) Automation of reasoning 2: classical papers on computational logic 1967–1970. Springer, Berlin, pp 466–483
Acknowledgements
The support from the Finnish Centre of Excellence in Computational Inference Research (COIN) funded by the Academy of Finland (under Grant #251170) is gratefully acknowledged.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Janhunen, T. Answer Set Programming. Künstl Intell 32, 125–131 (2018). https://doi.org/10.1007/s13218-018-0543-y
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s13218-018-0543-y