https://www.dagstuhl.de/02381

September 15 – 20 , 2002, Dagstuhl Seminar 02381

Nonmonotonic Reasoning, Answer Set Programming and Constraints

Organizers

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

Documents

List of Participants
Dagstuhl's Impact: Documents available
Dagstuhl-Seminar-Report 354

Scientific Highlights of the Event

Answer set programming is an emerging programming/problem solving paradigm. The fundamental underlying idea is to describe a problem declaratively in such a way that models of the description provide solutions to problems. One particular instance of this paradigm are logic programs under stable model semantics (respectively answer set semantics if an extended class of logic programs is used). Tremendous progress has been made recently in this area concerning both the theoretical foundations of the approach and implementation issues. Several highly efficient systems are available now which make it possible to investigate some serious applications.

The talks of the workshop were centered around the following main research topics:

  1. Useful language extensions and their theoretical foundations, with a particular focus on cardinality, weight and other types of constraints.
  2. Preferences in answer set programming and their implementation, where the preferences considered are among rules, among literals, or among disjuncts in heads of rules.
  3. Implementation techniques for answer set solvers. Several new methods or improvements of existing methods were presented, some of them based on highly efficient existing satisfiability solvers.
  4. New attempts to handle programs with variables. Existing solvers produce the ground instantiation of a program before computing answer sets and disallow function symbols. More flexible and less space consuming techniques are needed for large applications.
  5. Applications of the answer set paradigm in planning, scheduling, linguistics etc.

In addition to the talks a system competition took place during the workshop. Five systems participated in the competition, namely dlv (TU Vienna/Univ. Calabria), Smodels (Helsinki UT), ASSAT (UST HongKong), cmodels (UT Austin) and aspps (University of Kentucky). In a meeting at the beginning of the seminar the participants agreed about the benchmark problems to be used in the competition. The problems were encoded and tested and results presented in a plenary session at the end of the week.

Another topic of interest was standardization. There was an panel on the subject followed by open discussion. A general feeling was that the matter of standardization is a topic that requires a thorough attention on the part of the community in the near future.

Training

Among the participants of the workshop were 11 young researchers, most of them PhD students. The students were allotted the same amount of time as everybody else for their talks to make sure they received enough attention from senior scientists. For many of the students it was the first time they presented their results/projects to an international audience. The students had a chance to discuss with world leading researchers in their area. This will certainly have an impact on their future work.

European added value

It is fair to say that in the field of answer set programming, and in particular in implementing advanced answer set solvers, Europe is currently on par with research in North America, if not leading. There is a number of European research groups active in this area. The EC just started to fund a Working Group on Answer Set Programming. The major goals of the Working group are the further advancement of the theoretical understanding of ASP (this includes the investigation of new potentially useful language constructs and their semantics), the further development of efficient advanced reasoning systems which make ASP techniques widely available (this includes the development of front ends for specific application problems), and the investigation of the applicability of ASP to areas such as planning, configuration, encryption, verification, knowledge extraction and others.

During the seminar the kickoff meeting of the working group took place, and the members had an excellent opportunity to get first hand information about current research developments in each group.

Given the numerous application areas for which promising answer set programming solutions already exist today, we expect tremendous economic benefit of this research. The seminar was important to keep Europe at the forefront of research in this area.

Public Outreach

Answer set programming is a new declarative programming methodology. The basic idea is that programmers, rather than having to specify how a computer should solve a problem, just describe what the problem is. Each model of the problem description then provides a possible solution to the problem. The exact notion of a model used here depends on the language used for describing problems, but in all cases the models (also called answer sets in this context) can be thought of as sets of facts representing what is true and what is false.

Although theoretical foundations have been laid and some highly efficient implemented systems are available, there are still numerous challenging scientific questions which need to be answered: improved implementation techniques, extensions of the declarative languages which facilitate the problem description, methods for applying these techniques to problems like planning, scheduling, configuration etc. Contributions to all of these topics were presented and discussed during the seminar.

Documentation

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).

Publications

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

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.