WASP WP3 Report: Language Extensions for ASP

Ilkka Niemelä (Ed.)

November 9, 2003

WASP: European Working group on Answer Set Programming (funded by the European commission, FET "Future Emerging Technologies" initiative)
Work package 3: Language Extensions and Software Engineering for ASP
Participating nodes: HUT, UCY, UNILEIPZIG, VUB, BATH, UNIPOTSDAM, TUWIEN, UNIJC, KULEUVEN, UNICAL, UNIRC, UNINA

Introduction

The work on ASP systems started from implementations of normal programs [53] but in the end of the 90s extensions to this basic language started to emerge. Below is a catalogue of most important extensions with emphasis on work done within the WASP research groups.

Language Extensions

Disjunctions

One of the first extensions studied was disjunctive logic programs and the state of the art implementation is the DLV system [36] (http://www.dbai.tuwien.ac.at/proj/dlv/). Another available implementation is the GnT procedure [42,43] (http://www.tcs.hut.fi/Software/gnt/) built on top of Smodels (http://www.tcs.hut.fi/Software/smodels/)

Disjunctive logic programs have been extended by parametric connectives (OR and AND) [48]. These connectives allow to represent compactly the disjunction/conjunction of a set of atoms having a given property.

Nested Programs

Disjunctive programs have been further extended to nested programs [49]. Nested logic programs are (normal) logic programs where the bodies and heads of rules contain arbitrary Boolean formulas.

Implementations of this idea are being developed [60,56,51,52].

For implementations, see nlp http://www.cs.uni-potsdam.de/~torsten/nlp/ and NoMoRe http://www.cs.uni-potsdam.de/~linke/nomore

Cardinality and weight constraints

Smodels (http://www.tcs.hut.fi/Software/smodels/) supports cardinality and weight constraints as well as optimization [63].

Aggregates

There are some simple properties, often arising in real-world applications, which cannot be encoded in a simple and natural manner using ASP. Especially properties that require the use of arithmetic operators (like sum, count, or min) on a set of elements satisfying some conditions, cannot be naturally expressed in classic ASP. To overcome this deficiency, ASP has been extended by aggregate functions by means of a generalization of the Gelfond-Lifschitz transformation [30,31]. This approach has been implemented in the DLV system (http://www.dbai.tuwien.ac.at/proj/dlv/).

Partial stable semantics for logic programs with arbitrary aggregate relations has been defined in [58] and a translation to normal logic programs which preserves the semantics in [57].

Templates

Answer Set Programming languages can be extended with template predicate's definitions by introducing a well-suited form of second order logics, and an unfolding semantics [41]. The aim is to enchance code reusability in ASP.

Finitary and open programs

Finitary programs [3,6] support function symbols and recursion, without affecting decidability. This extension is mainly motivated by the need of representing and reasoning about recursive data structures (such as XML documents) in a natural and uniform way, without resorting to external preprocessors.

Current prototypes [2] comprise a finitary program recognizer and a relevant program constructor. They can be downloaded from http://people.na.infn.it/~bonatti/ricerca/software/index.html.

In open programs [4,5] the definition of certain predicates is not complete (or exhaustive), and can be integrated by more rules. Open programs have been introduced for program module analysis, as well as reasoning with open domains. A combination of finitary programs and open programs supports abduction with unbounded, possibly open domains [7].

ID-logic

ID-logic [32,33] is defined as an extension of classical logic with non-monotone inductive definitions. An inductive definition in an ID-logic theory is represented as a set of rules defining a subset of defined predicates in terms of other, open predicates, which makes ID-logic formally an extension of Abductive Logic Programming and a relative of open programs [4,5]. The Asystem [44] is an abductive reasoning system for a sublogic of ID-logic. In this system, a finite domain constraint solver CLP(FD) is integrated. It is available on http://www.cs.kuleuven.ac.be/~bertv/Asystem/

Abduction

Abduction with penalization in the logic programming framework has been proposed [59]. This form of abductive reasoning, which has not been previously analyzed in logic programming, turns out to represent several relevant problems, including optimization problems, very naturally.

Preferences

There has been a substantial amount of work on extending logic programs with preferences. Below are some main directions studied within the WASP community

Rule preferences [64,37,47,18,17,62,61,28,46,45,29,54,55]
An ordered logic program is a pair (P,O) where P is a logic program and O is a a strict partial order on rules of P such that r O s expresses that rule r has higher priority than rule s.
For implementations, see plp http://www.cs.uni-potsdam.de/~torsten/plp/ and GCplp http://www.cs.uni-potsdam.de/~konczak/system/GCplp/.
For an approach to handle preference by meta-interpretation in answer set programming [35], see http://www.dbai.tuwien.ac.at/proj/dlv/preferred/
Ordered disjunctions [13,11,14,15]
For an implementation, see psmodels http://www.tcs.hut.fi/Software/smodels/priority/
Answer set optimization [16,12]
Ordered choice logic programs [21,23,22,24,25,20,10]
OCLP is a framework for decision making with the possibility to express circumstance-dependent preferences among different alternatives for a decision. We propose both a skeptical and a credulous answer set semantics, corresponding to appropriate ways of reasoning, depending on the application.
For an implementation, see http://www.cs.bath.ac.uk/~mdv/oct/
CP-networks using ASP [9,8]
CP-nets were designed to make the process of preference elicitation simpler and more intuitive for lay users by graphically structuring a set of Ceteris Paribus (CP) preference statements - preference statements that most people find natural and intuitive. This work presents an extended semantics for CP-networks with cycles. It also provides a translation of CP-networks in answer set programming and studies its relation to other existing ASP frameworks for representing preferences.

Actions and Change

The use of ASP for planning has been advocated [50]. For example, DLV contains a front-end for the planning language K (http://www.dbai.tuwien.ac.at/proj/dlv/K/).

For another approach to reasoning about actions and change, see [34], which establishes a link between an action language called E and answer set programming. It studies how several versions of the language E, of varying complexity, can be translated into answer set programming, and studies the computational complexity of these sublanguages of E.

Description logics

There are a number of approaches to handle description logics using ASP techniques [40,39,38,1].

Ontologies

An extension of disjunctive logic programming, named OntoDLP, for Ontology representation and reasoning has been proposed [19]. OntoDLP is a formalism which combines the full computational power of disjunctive logic programming with suitable abstraction mechanisms for the representation of Ontologies, including complex objects, inheritance, and default reasoning.

1: G. Alsaç and C. Baral.
Reasoning in Description Logics using Declarative Logic Programming, 2002.
http://www.public.asu.edu/~guray/dlreasoning.pdf.
2: P. A. Bonatti.
Prototypes for reasoning with infinite stable models and function symbols.
In Proceedings of Logic Programming and Nonmonotonic Reasoning, 6th International Conference, LPNMR 2001, number 2173 in LNCS, pages 416-419. Springer, 2001.
[Link].
3: P. A. Bonatti.
Reasoning with infinite stable models.
In Proceedings of the Seventeenth International Joint Conference on Artificial Intelligence, IJCAI 2001, pages 603-610. Morgan Kaufmann, 2001.
[Link].
4: P. A. Bonatti.
Reasoning with open logic programs.
In Proceedings of Logic Programming and Nonmonotonic Reasoning, 6th International Conference, LPNMR 2001, number 2173 in LNCS, pages 147-159. Springer, 2001.
[Link].
5: P. A. Bonatti.
Abduction, asp and open logic programs.
In Proceedings of NMR'02, 2002.
[Link].
6: P. A. Bonatti.
Reasoning with infinite stable models II: Disjunctive programs.
In Proceedings of the 18th International Conference on Logic Programming, ICLP 2002, number 2401 in LNCS, pages 333-346. Springer, 2002.
[Link].
7: P. A. Bonatti.
Finitary open logic programs.
In Proceedings of Answer Set Programming: Advances in Theory and Implementation, NMR'02, number 78 in CEUR Workshop Proceedings, pages 84-97, 2003.
[Link].
8: Ronen Brafman and Yannis Dimopoulos.
Extended semantics and optimization algorithms for CP-neworks.
Submitted for journal publication, 2003.
9: Ronen Brafman and Yannis Dimopoulos.
A new look at the semantics and optimization methods of CP-networks.
In Proc. International Joint Conference on Artificial Intelligence(IJCAI 2003). Morgan Kaufman, 2003.
10: Martin Brain and Marina De Vos.
Implementing OCLP as a front-end for Answer Set Solvers: From Theory to Practice.
In ASP03: Answer Set Programming: Advances in Theory and Implementation. Ceur-WS, September 2003.
online CEUR-WS.org/Vol-78/asp03-final-brain.ps; [ps.gz].
11: G. Brewka.
Logic programming with ordered disjunction.
In Proc. AAAI-02, pages 100-105. AAAI Press, 2002.
12: G. Brewka.
Answer sets: From constraint programming towards qualitative optimization.
In article submitted to LPNMR. Springer, 2004.
13: G. Brewka, S. Benferhat, and D. Le Berre.
Qualitative choice logic.
In Proc. Principles of Knowledge Representation and Reasoning, KR-02. Morgan Kaufmann, 2002.
14: G. Brewka, I. Niemelä, and T. Syrjänen.
Implementing ordered disjunction using answer set solvers for normal programs.
In Proc. 8th European Conference on Logics in Artificial Intelligence (JELIA 2002). Springer Verlag, 2002.
[PS].
15: G. Brewka, I. Niemelä, and T. Syrjänen.
Logic programs with ordered disjunction.
Computational Intelligence, special issue on preferences in AI, 2004.
16: G. Brewka, I. Niemelä, and M. Truszczynski.
Answer set optimization.
In Proc. International Joint Conference on Artificial Intelligence(IJCAI 2003). Morgan Kaufman, 2003.
[PS].
17: Gerhard Brewka and Thomas Eiter.
Preferred answer sets for extended logic programs.
Artificial Intelligence, 109(1-2):297-356, April 1999.
18: Francesco Buccafurri, Wolfgang Faber, and Nicola Leone.
Disjunctive logic programs with inheritance.
Journal of the Theory and Practice of Logic Programming, 2(3), 2002.
19: F. Calimeri, S. Galizia, M. Ruffolo, and P.Rullo.
Ontodlp: a logic formalism for knowledge representation.
In Answer Set Programming: Advances in Theory and Implementation (ASP03), Messina, Italy, 2003.
20: Marina De Vos.
An Ordered Choice Logic Programming Front-end for Answer Set Solvers.
In Francesco Buccafurri, editor, APPIA-GULP-PRODE 2003: 2003 Joint Conference on Declaritive Programming, pages 362-373, Reggio Calabria, Italy, September 2003.
[ps.gz].
21: Marina De Vos and Dirk Vermeir.
Dynamically Ordered Probabilistic Choice Logic Programming.
In Proceedings of Foundations of Software Technology and Theoretical Computer Science Conference (FST TCS 2000), number 1974 in Lecture Notes in Computer Science, pages 227-239, New Delhi, India, December 2000. Springer-Verlag.
[ps.gz].
22: Marina De Vos and Dirk Vermeir.
Decisions, Agents and Games.
In Johan van Benthem, editor, Theoretical Aspects of Rationality and Knowledge (TarkVII), pages 219-232, Siena, Italy, July 2001. Morgan Kaufmann.
[ps.gz].
23: Marina De Vos and Dirk Vermeir.
Logic Programming Agents and Game Theory.
In Answer Set Programming: Towards Efficient and Scalable Knowledge Representation and Reasoning, pages 27-33, Stanford (Palo Alto), California, US, March 2001. American Association for Artificial Intelligence Press.
[ps.gz].
24: Marina De Vos and Dirk Vermeir.
Dynamic Decision Making in Logic Programming and Game Theory.
In AI2002: Advances in Artificial Intelligence, Lecture Notes in Artificial Intelligence, pages 36-47. Springer, December 2002.
[ps.gz].
25: Marina De Vos and Dirk Vermeir.
Logic Programming Agents Playing Games.
In Research and Development in Intelligent Systems XIX (ES2002), BCS Conference Series, pages 323-336. Springer, December 2002.
[ps.gz].
26: J. Delgrande and T. Schaub.
Reasoning credulously and skeptically within a single extension.
Journal of Applied Non-Classical Logics, 12(2):259-285, 2002.
[PDF].
27: J. Delgrande and T. Schaub.
On the relation between Reiter's default logic and its (major) variants.
In Th. Nielsen and N. Zhang, editors, Proceedings of the Seventh European Conference on Symbolic and Quantitative Approaches to Reasoning with Uncertainty, volume 2711 of Lecture Notes in Artificial Intelligence, pages 452-463. Springer-Verlag, 2003.
[PDF].
28: J. Delgrande, T. Schaub, and H. Tompits.
A framework for compiling preferences in logic programs.
Theory and Practice of Logic Programming, 3(2):129-187, March 2003.
[PDF].
29: J. Delgrande, T. Schaub, H. Tompits, and K. Wang.
Towards a classification of preference handling approaches in nonmonotonic reasoning.
In U. Junker, editor, Proceedings of the Workshop on Preferences in Artificial Intelligence and Constraint Programming: Symbolic Approaches, pages 16-24. AAAI Press, 2002.
[PDF].
30: Tina Dell'Armi, Wolfgang Faber, Giuseppe Ielpa, Nicola Leone, and Gerald Pfeifer.
Aggregate Functions in Disjunctive Logic Programming: Semantics, Complexity, and Implementation in DLV.
In Proceedings of the 18th International Joint Conference on Artificial Intelligence (IJCAI) 2003, Acapulco, Mexico, August 2003. Morgan Kaufmann Publishers.
31: Tina Dell'Armi, Wolfgang Faber, Giuseppe Ielpa, Nicola Leone, and Gerald Pfeifer.
Aggregate Functions in DLV.
In Marina de Vos and Alessandro Provetti, editors, Proceedings ASP03 - Answer Set Programming: Advances in Theory and Implementation, pages 274-288, Messina, Italy, September 2003.
Online at http://CEUR-WS.org/Vol78/.
32: M. Denecker.
Extending classical logic with inductive definitions.
In C. Baral and M. Truszczynski, editors, 8th Intl. Workshop on Non-Monotonic Reasoning (NMR2000), pages 1-15, Breckendridge, Colorado, USA, April 9-11 2000.
[Link].
33: Marc Denecker and Eugenia Ternovska.
A logic of non-monotone inductive definitions and its modularity properties.
In Vladimir Lifschitz and Ilkka Niemelä, editors, 7th International Conference on Logic Programming and Nonmonotonic Reasoning, 2004.
[Link].
34: Yannis Dimopoulos, Antonis Kakas, and Loizos Michael.
Reasoning about actions and change in answer set programming.
To appear in the Proceedings of the 7th International Conference on Logic Programming and Nonmonotonic Reasoning, 2003.
35: Thomas Eiter, Wolfgang Faber, Nicola Leone, and Gerald Pfeifer.
Computing Preferred Answer Sets by Meta-Interpretation in Answer Set Programming.
Theory and Practice of Logic Programming, 3:463-498, July/September 2003.
36: Eiter, T., Leone, N., Pfeifer G., Mateis C., and Scarcello, F.
The kr system dlv: Progress report, comparisons and benchmarks.
In Proceedings of the 6th International Conference on Principles of Knowledge Representation and Reasoning, pages 406-417. Morgan Kaufmann Publishers, 1998.
37: D. Gabbay, E. Laenens, and D. Vermeir.
Credulous vs. Sceptical Semantics for Ordered Logic Programs.
In J. Allen, R. Fikes, and E. Sandewall, editors, Proceedings of the 2nd International Conference on Principles of Knowledge Representation and Reasoning, pages 208-217, Cambridge, Mass, 1991.
38: B. N. Grosof, I. Horrocks, R. Volz, and S. Decker.
Description Logic Programs: Combining Logic Programs with Description Logic.
In Proceedings of Twelfth International World Wide Web Conference (WWW 2003), pages 48-57. ACM, 2003.
http://www.cs.man.ac.uk/~horrocks/Publications/download/2003/p117-grosof.pdf.
39: S. Heymans and D. Vermeir.
Integrating Description Logics and Answer Set Programming.
In Workshop on Principles and Practice of Semantic Web Reasoning (PPSWR), December 2003.
To appear. http://tinf2.vub.ac.be/~sheymans/publications/ppswr2003.ps.
40: S. Heymans and D. Vermeir.
Integrating Ontology Languages and Answer set Programming.
In Fourteenth International Workshop on Database and Expert Systems Applications, pages 584-588, Prague, Czech Republic, September 2003. IEEE Computer Society.
http://tinf2.vub.ac.be/~sheymans/publications/webs2003.ps.
41: G. Ianni, G. Ielpa, A. Pietramala, and M.C. Santoro.
Answer set programming with templates.
In Answer Set Programming: Advances in Theory and Implementation (ASP03), pages 239-252, Messina, Italy, 2003.
[Link].
42: T. Janhunen, I. Niemelä, P. Simons, and J. You.
Unfolding partiality and disjunctions in stable model semantics.
In A.G. Cohn, F. Guinchiglia, and B. Selman, editors, Proceedings of the Seventh International Conference on Principles of Knowledge Representation and Reasoning, pages 411-419, Breckenridge, Colorado, USA, April 2000. Morgan Kaufmann Publishers.
43: Tomi Janhunen, Ilkka Niemelä, Dietmar Seipel, Patrik Simons, and Jia-Huai You.
Unfolding partiality and disjunctions in stable model semantics.
CoRR: cs.AI/0303009, March 2003.
Submitted for publication.
44: Anthonis C. Kakas, Bert Van Nuffelen, and Marc Denecker.
A-system : Problem solving through abduction.
In B. Nebel, editor, Proceedings of IJCAI'01 - Seventeenth International Joint Conference on Artificial Intelligence, volume 1, pages 591-596. Morgan Kaufmann Publishers, Inc., 2001.
[Link].
45: K. Konczak, T. Schaub, and T. Linke.
Graphs and colorings for answer set programming with preferences.
Fundamenta Informaticae, 57(2-4):393-421, 2003.
[PDF].
46: K. Konczak, T. Schaub, and T. Linke.
Graphs and colorings for answer set programming with preferences: Preliminary report.
In M. De Vos and A. Provetti, editors, Proceedings of the Second International Workshop on Answer Set Programming (ASP'03), volume 78, pages 43-56. CEUR Workshop Proceedings, 2003.
[Link], [PDF].
47: Els Laenens and Dirk Vermeir.
Assumption-free semantics for ordered logic programs: On the relationship between well-founded and stable partial models.
Journal of Logic and Computation, 2(2):133-172, 1992.
48: N. Leone and S. Perri.
Parametric connectives in disjunctive logic programming.
In Answer Set Programming: Advances in Theory and Implementation (ASP03), pages 124-135, Messina, Italy, 2003.
49: V. Lifschitz, L. Tang, and H. Turner.
Nested expressions in logic programs.
Annals of Mathematics and Artificial Intelligence, 25(3-4):369-389, 1999.
50: Vladimir Lifschitz.
Answer set programming and plan generation.
Journal of Artificial Intelligence, 138(1-2):39-54, 2002.
51: T. Linke.
Using nested logic programs for answer set programming.
In M. de Vos and A. Provetti, editors, Proceedings of the Second International Workshop on Answer Set Programming (ASP'03), volume 78, pages 181-194. CEUR Workshop Proceedings, 2003.
[Link], [PDF].
52: T. Linke, A. Bösel, and C. Anger.
noMoRe a graph-based system for non-monotonic reasoning with logic programs under answer set semantics, 2000-2003.
[PDF].
53: I. Niemelä and P. Simons.
Efficient implementation of the well-founded and stable model semantics.
In M. Maher, editor, Proceedings of the Joint International Conference and Symposium on Logic Programming, pages 289-303, Bonn, Germany, September 1996. The MIT Press.
54: D. Van Nieuwenborgh and D. Vermeir.
Preferred answer sets for ordered logic programs.
In Logic in Artificial Intelligence, JELIA 2002, pages 432-443, Cosenza, Italy, September 2002.
http://tinfpc2.vub.ac.be/papers/jelia2002.ps.gz.
55: D. Van Nieuwenborgh and D. Vermeir.
Order and Negation as Failure.
In Proceedings of the 19'th International Conference on Logic Programming (ICLP 2003), Lecture Notes in Computer Science, page to appear. Springer Verlag, 2003.
56: D. Pearce, V. Sarsakov, T. Schaub, H. Tompits, and S. Woltran.
A polynomial translation of logic programs with nested expressions into disjunctive logic programs.
In P. Stuckey, editor, Proceedings of the International Conference on Logic Programming, volume 2401, pages 405-420. Springer-Verlag, 2002.
[PDF].
57: Nikolay Pelov, Marc Denecker, and Maurice Bruynooghe.
Translation of aggregate programs to normal logic programs.
In Marina De Vos and Alessandro Provetti, editors, Answer Set Programming: Advances in Theory and Implementation, volume 78 of CEUR Workshop Proceedings, pages 29-42, 2003.
[Link].
58: Nikolay Pelov, Marc Denecker, and Maurice Bruynooghe.
Partial stable semantics for logic programs with aggregates.
In Vladimir Lifschitz and Ilkka Niemelä, editors, 7th International Conference on Logic Programming and Nonmonotonic Reasoning, 2004.
[Link].
59: S. Perri, F. Scarcello, and N.Leone.
Abductive logic programs with penalization: Semantics, complexity and implementation.
Journal of the Theory and Practice of Logic Programming (TPLP), Forthcoming.
[PDF].
60: V. Sarsakov, T. Schaub, H. Tompits, and S. Woltran.
nlp: A compiler for nested logic programming.
In V. Lifschitz and I. Niemelä, editors, Proceedings of the Seventh International Conference on Logic Programming and Nonmonotonic Reasoning (LPNMR'04), volume 2923 of Lecture Notes in Computer Science, pages 361 - 364. Springer-Verlag Heidelberg, 2003.
[PDF].
61: T. Schaub and K. Wang.
A semantic framework for preference handling in answer set programming.
Theory and Practice of Logic Programming, 3(4-5):569-607, 2003.
[PDF].
62: Torsten Schaub and Kewen Wang.
A comparative study of logic programs with preference.
In Bernhard Nebel, editor, Proceedings of the Seventeenth International Joint Conference on Artificial Intelligence (IJCAI) 2001, pages 597-602, Seatle, Washington, USA, August 2001.
[PDF].
63: P. Simons, I. Niemelä, and T. Soininen.
Extending and implementing the stable model semantics.
Artificial Intelligence, 138(1-2):181-234, 2002.
64: D. Vermeir, E. Laenens, and D. Sacca.
Extending logic programming.
In Proceedings of the SIGMOD Conference, pages 184-193. ACM, 1990.

About this document ...

WASP WP3 Report: Language Extensions for ASP

This document was generated using the LaTeX2HTML translator Version 2K.1beta (1.48)

The command line arguments were:
latex2html -split 0 -no_navigation wasp-wp3-web

The translation was initiated by Ilkka Niemel{ on 2004-01-27

Ilkka Niemel{ 2004-01-27