April 24 – 29 , 2005, Dagstuhl Seminar 05171

Nonmonotonic Reasoning, Answer Set Programming and Constraints


Gerhard Brewka (Universität Leipzig, DE)
Ilkka Niemelä (Helsinki University of Technology, FI)
Torsten Schaub (Universität Potsdam, DE)
Miroslaw Truszczynski (University of Kentucky – Lexington, US)

For support, please contact

Dagstuhl Service Team


Dagstuhl Seminar Proceedings DROPS
List of Participants
Dagstuhl's Impact: Documents available


The seminar took place from April 24 to 29, 2005. It was organized by Gerhard Brewka (Univ. Leipzig, DE), Ilkka Niemelä (Helsinki Univ. of Technology, FI), Torsten Schaub (Univ. Potsdam, DE), and Miroslaw Truszczynski (Univ. of Kentucky, US). The seminar was attended by 58 participants from Europe, North America, Asia and Australia.

The technical program consisted of

  • Three invited talks:
    Tomi Janhunen: Translating NLPs into Propositional Theories
    Thomas Eiter: Extending Answer Set Programming for the Semantic Web
    David Mitchell: Progress and Problems in SAT Solving
  • 38 contributed talks given by the participants
  • Panel discussion on the future of the answer-set programming. The panel was mod- erated by Ilkka Niemelä. Marc Denecker, Yannis Dimopoulos, Michael Gelfond and Nicola Leone were panelists.
  • Special session on the benchmarking system asparagus led by Christian Anger and Miroslaw Truszczynski

The technical program of the seminar demonstrated that since our first meeting in Dagstuhl in September 2002, substantial scientific progress has been achieved in several areas:

  • Theory of answer-set programming . Much progress has been obtained in understanding encodings of programs as propositional theories through research on the concepts of completion and loop formula. Logic programming with nested expressions and logic of here-and-there and its relatives solidified their position as fundamental formalisms for the development of the theory of answer-set programming. Other notable developments include ID-logic, which expands classical logic with inductive definitions represented as a logic programs, new results on program equivalence and proof systems for programs with cardinality constraints.
  • Software for answer-set programming . Dlv emerged as an "almost" production- grade package of answer-set programming tools supporting program grounding, answer- set computation and integration with database environments. Several new solvers were introduced: cmodels enhanced to handle disjunctive programs, pbmodels , which uses pseudo-boolean solvers to compute stable models of programs with weight atoms, and nomore++ - a system implementing new branching and propagation techniques. Asparagus, an environment for systematic and objective testing of answer-set solvers has grown and matured significantly since it was first proposed at the Dagstuhl Seminar 02381 in September 2002. Researchers also have been investigating and developing tools for distributed processing of answer-set programs (Platypus project). Finally, the workshop presented research on program development tools supporting static program analysis and debugging.
  • Applications . The seminar demonstrated that answer-set programming becomes a viable software tool in several application domains including: semantic web, data integration, systems of boolean equations, planning, security engineering, social modeling, and qualitative decision theory.
  • Strong connections to propositional satisfiability . It has been clear for quite some time that our field can benefit from closer collaboration with researchers in the SAT community. This seminar had several talks that emphasized that connection, most notably the invited talk by David Mitchell, which will undoubtedly have major impact on the development and implementation of new answer-set programming solvers.

General conclusions from the seminar are very positive. The seminar was dominated by young researchers and students, about 25 of whom delivered presentations. Our community is branching out to related communities of propositional satisfiability and constraint satisfaction, both theory and software development are actively pursued, and there is a strong push towards practical applications.


In the series Dagstuhl Reports each Dagstuhl Seminar and Dagstuhl Perspectives Workshop is documented. The seminar organizers, in cooperation with the collector, prepare a report that includes contributions from the participants' talks together with a summary of the seminar.


Download overview leaflet (PDF).

Dagstuhl's Impact

Please inform us when a publication was published as a result from your seminar. These publications are listed in the category Dagstuhl's Impact and are presented on a special shelf on the ground floor of the library.


Furthermore, a comprehensive peer-reviewed collection of research papers can be published in the series Dagstuhl Follow-Ups.