Hostname: page-component-cd9895bd7-gvvz8 Total loading time: 0 Render date: 2024-12-23T10:57:55.098Z Has data issue: false hasContentIssue false
  • English
  • Français

The third open answer set programming competition

Published online by Cambridge University Press:  06 September 2012

FRANCESCO CALIMERI ,
GIOVAMBATTISTA IANNI  and
FRANCESCO RICCA
FRANCESCO CALIMERI
Affiliation:
Dipartimento di Matematica, Università della Calabria, Italy (email: [email protected], [email protected], [email protected]
GIOVAMBATTISTA IANNI
Affiliation:
Dipartimento di Matematica, Università della Calabria, Italy (email: [email protected], [email protected], [email protected]
FRANCESCO RICCA
Affiliation:
Dipartimento di Matematica, Università della Calabria, Italy (email: [email protected], [email protected], [email protected]
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

Answer Set Programming (ASP) is a well-established paradigm of declarative programming in close relationship with other declarative formalisms such as SAT Modulo Theories, Constraint Handling Rules, FO(.), PDDL and many others. Since its first informal editions, ASP systems have been compared in the now well-established ASP Competition. The Third (Open) ASP Competition, as the sequel to the ASP Competitions Series held at the University of Potsdam in Germany (2006–2007) and at the University of Leuven in Belgium in 2009, took place at the University of Calabria (Italy) in the first half of 2011. Participants competed on a pre-selected collection of benchmark problems, taken from a variety of domains as well as real world applications. The Competition ran on two tracks: the Model and Solve (M&S) Track, based on an open problem encoding, and open language, and open to any kind of system based on a declarative specification paradigm; and the System Track, run on the basis of fixed, public problem encodings, written in a standard ASP language. This paper discusses the format of the competition and the rationale behind it, then reports the results for both tracks. Comparison with the second ASP competition and state-of-the-art solutions for some of the benchmark domains is eventually discussed.

Keywords

answer set programminglogic programmingdeclarative languagesartificial intelligence competitions
Type
Regular Papers
Information
Theory and Practice of Logic Programming , Volume 14 , Issue 1 , January 2014 , pp. 117 - 135
Copyright
Copyright © Cambridge University Press 2012 

References

Aclasp 2011. Aclasp Sources. https://potassco.svn.sourceforge.net/svnroot/potassco/branches/adaptive-restarts/adapt-to-avgdl.Google Scholar
Anger, C., Gebser, M., Linke, T., Neumann, A. and Schaub, T. 2005. The nomore++ approach to answer set solving. In LPAR 2005. LNCS 3835, 95–109.Google Scholar
ASP-Draft 2004. Core language for ASP solver competitions. Steering committee meeting at LPNMR 2004. https://www.mat.unical.it/aspcomp2011/files/Corelang2004.pdf.Google Scholar
Balduccini, M. 2009a. A general method to solve complex problems by combining multiple answer set programs. In ASPOCP Workshop at ICLP 2009).Google Scholar
Balduccini, M. 2009c. Representing constraint satisfaction problems in answer set programming. In ASPOCP Workshop at ICLP 2009.Google Scholar
Balduccini, M., Gelfond, M., Watson, R. and Nogeira, M. 2001. The USA-Advisor: A case study in answer set planning. In LPNMR 2001. LNCS 2173, 439–442.Google Scholar
Bancilhon, F., Maier, D., Sagiv, Y. and Ullman, J. D. 1986. Magic sets and other strange ways to implement logic programs. In PODS 1986. 1–15.CrossRefGoogle Scholar
Baral, C. 2003. Knowledge Representation, Reasoning and Declarative Problem Solving. Cambridge University Press, Cambridge, UK.Google Scholar
Baral, C. and Gelfond, M. 2000. Reasoning agents in dynamic domains. Logic-Based Artificial Intelligence, 257–279.Google Scholar
Baral, C. and Uyan, C. 2001. Declarative specification and solution of combinatorial auctions using logic programming. In LPNMR 2001. LNAI 2173, 186–199.Google Scholar
Bardadym, V. A. 1996. Computer-aided school and university Timetabling: The new wave. In Practice and Theory of Automated Timetabling. LNCS, vol. 1153. 22–45.Google Scholar
Bell, C., Nerode, A., Ng, R. T. and Subrahmanian, V. 1994. Mixed integer programming methods for computing nonmonotonic deductive databases. JACM 41, 1178–1215.Google Scholar
Ben-Eliyahu-Zohary, R. and Palopoli, L. 1997. Reasoning with minimal models: Efficient algorithms and applications. AI 96, 421–449.Google Scholar
Bomze, I. M., Budinich, M., Pardalos, P. M. and Pelillo, M. 1999. The maximum clique problem. In Handbook of Combinatorial Optimization. Kluwer Academic Publishers, Boston, MA, 1–74.Google Scholar
Boppana, R. and Halldórsson, M. M. 1992. Approximating maximum independent sets by excluding subgraphs. BIT 32, 180–196.Google Scholar
CADE-ATP 2011. The CADE ATP System Competition. http://www.cs.miami.edu/~tptp/CASC.Google Scholar
Cadoli, M., Eiter, T. and Gottlob, G. 1997. Default logic as a query language. IEEE TKDE 9, 3, 448–463.Google Scholar
Calimeri, F., Ianni, G., Ricca, F. et al. 2010. The third answer set programming competition homepage. http://www.mat.unical.it/aspcomp2011/.Google Scholar
Calimeri, F., Ianni, G. and Ricca, F. 2011. 3rd ASP Competition, file and language formats. http://www.mat.unical.it/aspcomp2011/files/LanguageSpecifications.pdf.Google Scholar
Calimeri, F., Ianni, G., Ricca, F. et al. 2011. The third answer set programming competition: Preliminary report of the system competition track. In LPNMR 2011. LNCS 6645, 388–403.Google Scholar
Chen, W. and Warren, D. S. 1996. Tabled evaluation with delaying for general logic programs. Journal of The ACM 43, 20–74.Google Scholar
CHR 2004. Constraint handling rules. Since 2004. http://dtai.cs.kuleuven.be/CHR/.Google Scholar
CPLEX 2011. IBM ILOG CPLEX. http://www-01.ibm.com/software/integration/optimization/cplex-optimizer/.Google Scholar
Dal, Palù, A., Dovier, A., Pontelli, E. and Rossi, G. 2009. GASP: Answer set programming with lazy grounding. FI 96, 3, 297–322.Google Scholar
Dantsin, E., Eiter, T., Gottlob, G. and Voronkov, A. 2001. Complexity and expressive power of logic programming. ACM Computing Surveys 33, 3, 374–425.Google Scholar
Dao-Tran, M., Eiter, T., Fink, M. and Krennwallner, T. 2010. Distributed nonmonotonic multi-context systems. In KR 2010. AAAI Press, 60–70.Google Scholar
de Moura, L. M. and Bjørner, N. 2008. Z3: An efficient SMT solver. In TACAS. LNCS 4963, 337–340.Google Scholar
Denecker, M. and Ternovska, E. 2008. A logic of nonmonotone inductive definitions. ACM TOCL 9, 14:1–:52.Google Scholar
Denecker, M., Vennekens, J., Bond, S., Gebser, M. and Truszczynski, M. 2009. The second answer set programming competition. In LPNMR 2009. LNCS 5753, 637–654.Google Scholar
Dovier, A. 2011. Recent constraint/logic programming based advances in the solution of the protein folding problem. Intelligenza Artificiale 5, 1, 113–117.CrossRefGoogle Scholar
Drescher, C., Gebser, M., Grote, T., Kaufmann, B., König, A., Ostrowski, M. and Schaub, T. 2008. Conflict-driven disjunctive answer set solving. In KR 2008. AAAI Press, 422–432.Google Scholar
Eén, N. and Sörensson, N. 2003. An extensible SAT-solver. In SAT. LNCS 2919, 502–518.Google Scholar
Eén, N. and Sörensson, N. 2006. Translating Pseudo-Boolean constraints into sat. Journal on Satisfiability, Boolean Modeling and Computation 2, 1–26.CrossRefGoogle Scholar
Eiter, T., Ianni, G. and Krennwallner, T. 2009. Answer set programming: A primer. In Reasoning Web. LNCS 5689, 40–110.Google Scholar
Ellguth, E., Gebser, M., Gusowski, M., Kaminski, R., Kaufmann, B., Liske, S., Schaub, T., Schneidenbach, L. and Schnor, B. 2009. A simple distributed conflict-driven answer set solver. In LPNMR 2009. LNAI 5753, 490–495.Google Scholar
Faber, W., Leone, N. and Pfeifer, G. 2004. Recursive aggregates in disjunctive logic programs: Semantics and complexity. In JELIA 2004. LNAI 3229, 200–212.Google Scholar
Fages, F. 1994. Consistency of Clark's completion and existence of stable models. Journal of Methods of Logic in Computer Science 1, 1, 51–60.Google Scholar
Falkner, A., Haselböck, A. and Schenner, G. 2010. Modeling technical product configuration problems. In ECAI 2010 Workshop on Configuration. 40–46.Google Scholar
Feige, U. 2005. Approximating maximum clique by removing subgraphs. SIAM Journal on Discrete Mathematics 18, 219–225.CrossRefGoogle Scholar
Fodor, P., Liang, S. and Kifer, M. 2011. OpenRuleBench: Report 2011. Computing, 1–14.Google Scholar
Franconi, E., Palma, A. L., Leone, N. et al. 2001. Census data repair: A challenging application of disjunctive logic programming. In LPAR 2001. LNCS 2250, 561–578.Google Scholar
Friedrich, G. and Ivanchenko, V. 2008. Diagnosis from First Principles for Workflow Executions. Technical rep. ISBI research group, Alpen-Adria-Universität Klagenfurt. http://proserver3-iwas.uni-klu.ac.at/download_area/Technical-Reports/technical_report_2008_02.pdf.Google Scholar
Gange, G., Stuckey, P. J. and Marriott, K. 2010. Optimal k-level planarization and crossing minimization. In Graph Drawing. LNCS, vol. 6502. 238–249.Google Scholar
Garcia-Molina, H., Ullman, J. D. and Widom, J. 2000. Database System Implementation. Prentice Hall, Upper Saddle River, New Jersey.Google Scholar
Gebser, M., Kaminski, R., Kaufmann, B., Schaub, T., Schneider, M. T. and Ziller, S. 2011. A portfolio solver for answer set programming: Preliminary report. In LPNMR 2011. LNCS 6645, 352–357.Google Scholar
Gebser, M., Kaufmann, B., Kaminski, R., Ostrowski, M., Schaub, T. and Schneider, M. since 2007. Potassco, the Potsdam answer set solving collection - homepage. http://potassco.sourceforge.net/.Google Scholar
Gebser, M., Kaufmann, B., Neumann, A. and Schaub, T. 2007. Conflict-driven answer set solving. In IJCAI 2007, 386–392.Google Scholar
Gebser, M., Kaufmann, B. and Schaub, T. 2009. The conflict-driven answer set solver clasp: Progress report. In LPNMR 2009. LNCS 5753, 509–514.Google Scholar
Gebser, M., Liu, L., Namasivayam, G., Neumann, A., Schaub, T. and Truszczyński, M. 2007. The first answer set programming system competition. In LPNMR 2007. LNCS 4483, 3–17.Google Scholar
Gebser, M., Schaub, T. and Thiele, S. GrinGo : A new grounder for answer set programming. In LPNMR 2007. LNCS 4483, 266–271.Google Scholar
Gebser, M., Schaub, T., Thiele, S. and Veber, P. 2011. Detecting inconsistencies in large biological networks with answer set programming. TPLP 11, 323–360.Google Scholar
GECODE 2011. GECODE - An open, free, efficient constraint solving toolkit - Homepage. http://www.gecode.org/.Google Scholar
Gelfond, M. and Lifschitz, V. 1991. Classical negation in logic programs and disjunctive databases. NGC 9, 365–385.Google Scholar
Gerevini, A. and Long, D. 2005. Plan Constraints and Preferences in PDDL3 - The Language of the Fifth International Planning Competition. Technical rep. http://cs-www.cs.yale.edu/homes/dvm/papers/pddl-ipc5.pdf.Google Scholar
Gibbons, L. E., Hearn, D. W., Pardalos, P. M. and Ramana, M. V. 1996. Continuous characterizations of the maximum clique problem. Mathematics of Operations Research 22, 754–768.CrossRefGoogle Scholar
Graphviz 2011. Graphviz - Graph Visualization Software. http://www.graphviz.org/.Google Scholar
Grasso, G., Iiritano, S., Leone, N. and Ricca, F. 2009. Some DLV applications for knowledge management. In LPNMR 2009. LNCS 5753, 591–597.Google Scholar
Grasso, G., Leone, N., Manna, M. and Ricca, F. 2010. ASP at Work: Spin-off and Applications of the DLV System. Logic Programming, Knowledge Representation, and Nonmonotonic Reasoning, Lecture Notes in AI (LNAI), vol. 6565. Springer-Verlag, Berlin.Google Scholar
Gusfield, D. and Irving, R. W. 1989. The Stable Marriage Problem: Structure and Algorithms. MIT Press, Cambridge, MA, USA.Google Scholar
Gutin, G. 2004. Independent sets and cliques. Handbook of Graph Theory, Boca Raton, Florida, 389.Google Scholar
Healy, P. and Kuusik, A. 1999. The vertex-exchange graph: A new concept for multi-level crossing minimisation. In Graph Drawing. LNCS 1731, 205–216.Google Scholar
Helmert, M. 2006. The fast downward planning system. JAIR 26, 191–246.Google Scholar
Hentenryck, P. V. 1989. Constraint Satisfaction in Logic Programming, Logic Programming series I–XXVI, MIT Press, Cambridge, MA, 224 pp.Google Scholar
Jaffar, J. and Lassez, J. 1987. Constraint logic programming. In POPL 1987. 111–119.Google Scholar
Janhunen, T. 2006. Some (in)translatability results for normal logic programs and propositional theories. Journal of Applied Non-Classical Logics 16, 1–2, 35–86.Google Scholar
Janhunen, T. and Niemelä, I. 2004. Gnt - A solver for disjunctive logic programs. In LPNMR 2004. LNAI 2923, 331–335.Google Scholar
Janhunen, T., Niemelä, I. and Sevalnev, M. 2009. Computing stable models via reductions to difference logic. In LPNMR 2009. LNCS 5753, 142–154.Google Scholar
Johnson, D. and Trick, M. 1996. Cliques, coloring, and satisfiability: Second DIMACS implementation challenge, 11-13, 1993. DIMACS series in discrete mathematics and theoretical computer science. American Mathematical Society, Boston, MA.Google Scholar
Jünger, M., Lee, E. K., Mutzel, P. and Odenthal, T. 1997. A polyhedral approach to the multi-layer crossing minimization problem. In International Symposium on Graph Drawing. LNCS 1353, 13–24.Google Scholar
Lee, J. and Lifschitz, V. 2003. Loop formulas for disjunctive logic programs. In ICLP 2003. 451–465.Google Scholar
Lefèvre, C. and Nicolas, P. 2009a. A first order forward chaining approach for answer set computing. In LPNMR 2009. LNCS 5753, 196–208.Google Scholar
Lefèvre, C. and Nicolas, P. 2009b. The first version of a new asp solver: Asperix. In LPNMR 2009. LNCS 5753, 522–527.Google Scholar
Leone, N., Greco, G., Ianni, G., Lio, V., Terracina, G., Eiter, T., Faber, W., Fink, M., Gottlob, G., Rosati, R., Lembo, D., Lenzerini, M., Ruzzi, M., Kalka, E., Nowicki, B. and Staniszkis, W. 2005. The INFOMIX system for advanced integration of incomplete and inconsistent data. In SIGMOD 2005. 915–917.Google Scholar
Leone, N., Pfeifer, G., Faber, W., Eiter, T., Gottlob, G., Perri, S. and Scarcello, F. 2006. The DLV system for knowledge representation and reasoning. ACM TOCL 7, 3 (July), 499–562.Google Scholar
Lierler, Y. 2008. Abstract answer set solvers. In ICLP 2008. LNCS 5366, 377–391.Google Scholar
Lierler, Y. and Maratea, M. 2004. Cmodels-2: SAT-based answer set solver enhanced to non-tight programs. In LPNMR 2004. LNAI 2923, 346–350.Google Scholar
Lin, F. and Zhao, Y. 2004. ASSAT: Computing answer sets of a logic program by SAT solvers. Artificial Intelligence 157, 1–2, 115–137.Google Scholar
Marek, V. W. and Truszczyński, M. 1999. Stable models and an alternative logic programming paradigm. In The Logic Programming Paradigm – A 25-Year Perspective, Apt, K. R., Marek, V. W., Truszczyński, M. and Warren, D. S., Eds. Springer Verlag, 375–398.Google Scholar
Mariën, M., Wittocx, J., Denecker, M. and Bruynooghe, M. 2008. SAT(ID): Satisfiability of propositional logic extended with inductive definitions. In SAT 2008. LNCS 4996, 211–224.Google Scholar
Marileo, M. C. and Bertossi, L. E. 2010. The consistency extractor system: Answer set programs for consistent query answering in databases. DKE 69, 6, 545–572.Google Scholar
Mutzel, P. 2000. An alternative method to crossing minimization on hierarchical graphs. SIAM Journal on Optimization 11, 1065–1080.Google Scholar
Niemelä, I. 1999. Logic programming with stable model semantics as constraint programming paradigm. Annals of Mathematics and Artificial Intelligence 25, 3–4, 241–273.Google Scholar
Nieuwenhuis, R. and Oliveras, A. 2005. DPLL(T) with exhaustive theory propagation and its application to difference logic. In CAV 2005. LNCS 3576, 321–334.Google 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, 937–977.Google Scholar
Niskanen, S. since 2003. Cliquer Homepage. http://users.tkk.fi/pat/cliquer.html.Google Scholar
Nogueira, M., Balduccini, M., Gelfond, M., Watson, R. and Barry, M. 2001 An A-Prolog decision support system for the space shuttle. In PADL 2001. LNCS 1990, 169–183.Google Scholar
Östergård, P. R. J. 2002. A fast algorithm for the maximum clique problem. Discrete Applied Mathematics 120, 1–3, 197–207.Google Scholar
Palopoli, L., Rombo, S. E. and Terracina, G. 2005. Flexible pattern discovery with (extended) disjunctive logic programming. In ISMIS 2005. 504–513.Google Scholar
Papadimitriou, C. H. 1994. Computational Complexity. Addison-Wesley, Boston, MA.Google Scholar
PDDL 3.1 2008. Changes in PDDL 3.1. http://ipc.informatik.uni-freiburg.de/PddlExtension.Google Scholar
Ricca, F., Dimasi, A., Grasso, G., Ielpa, S. M., Iiritano, S., Manna, M. and Leone, N. 2010. A logic-based system for e-Tourism. FI 105, 1–2, 35–55.Google Scholar
Simons, P., Niemelä, I. and Soininen, T. 2002. Extending and implementing the stable model semantics. AI 138, 181–234.Google Scholar
smt-lib-web . 2011. The satisfiability modulo theories library. http://www.smtlib.org/.Google Scholar
Subrahmanian, V., Nau, D. and Vago, C. 1995. WFS + Branch and Bound = Stable Models. IEEE TKDE 7, 3 (June), 362–377.Google Scholar
WASP. Wasp showcase. Since 2003. http://www.kr.tuwien.ac.at/research/projects/WASP/showcase.html.Google Scholar
Wittocx, J., Mariën, M. and Denecker, M. 2008. GidL: A grounder for FO+. In NMR 2008.Google Scholar
Wittocx, J., Mariën, M. and Denecker, M. 2008. The idp system: A model expansion system for an extension of classical logic. In Logic and Search (LaSh 2008). 153–165.Google Scholar
XSB. 2011. The Home of XSB. http://xsb.sourceforge.net/.Google Scholar
Xu, K. since 2004. BHOSLIB: Benchmarks with hidden optimum solutions for graph problems. http://www.nlsde.buaa.edu.cn/~kexu/benchmarks/graph-benchmarks.htm.Google Scholar
Zhou, N.-F. 2011. The language features and architecture of B-Prolog. arXiv:1103.0812v1. Submitted to TPLP Special Issue on Prolog Systems.Google Scholar
Supplementary material: PDF

Calimeri Supplementary Material

Appendix.pdf

Download Calimeri Supplementary Material(PDF)
PDF 3.5 MB