By now, Dagstuhl Castle in Germany is already well-known among computer
scientists as a superb location for top-level seminars, in which the
latest research results can be discussed in a laid-back atmosphere.
Originally built in 1760, after serving most of its time as a manor
house of a noble family it was converted into an old-age home run by
Franciscan nuns in 1959, and was finally purchased by the state of
Saarland, which opened the International Conference and Research Center
for Computer Science Schloss Dagstuhl in 1990. Located in the wooded
hills of the Saarland in central-western Germany, not far from the
border to France and Luxemburg, the castle has a reclusive character,
which makes out-of-session socialization almost a necessity and
accounts for the special flair of Dagstuhl seminars.
From April 24 to April 29, 2005, 58 researchers from America, Asia,
Australia, and Europe gathered there for Seminar 05171 “Nonmonotonic
Reasoning, Answer Set Programming and Constraints,” organized by
Gerhard Brewka (University of Leipzig), Ilkka Niemelä (Helsinki
University of Technology), Torsten Schaub (University of Potsdam), and
Mirek Truszczynski (University of Kentucky). This was actually already
the second seminar on this topic, the first one (Dagstuhl Seminar
02381) took place in September 2002.
The academic program was fairly dense, comprising 3 invited talks, 41
regular presentations, a presentation with subsequent open discussion
and a panel. In addition, WASP, the European Working Group on Answer
Set Programming, held a meeting, and an excursion was scheduled for one
afternoon. The dominant topic of this seminar was answer set
programming (ASP), which is basically function-free logic programming
under the answer set (closely related to the stable model) semantics,
but also featured related areas such as ID-logic and boolean
satisfiability (SAT).
The first day started off with
an invited talk by Tomi Janhunen, on translating normal logic programs
into propositional theories, such that models of the propositional
theories correspond to the stable models of the logic program.
In the first regular session on foundations, Joohyung Lee presented a
model-theoretic counterpart of loop formulas, which are at the core of
the current SAT-based ASP engines. Kewen Wang subsequently spoke about
relevance and forgetting in ASP, also giving computational properties.
Ending the session, John Schlipf reported on experimental work for
determining the distribution of randomly generated normal propositional
logic programs.
After lunch, Gerd Brewka presented prioritized component systems, a
framework which combines ideas from ASP, answer-set optimization, and
CP-nets. Axel Polleres then spoke about recent developments in the area
of Semantic Web Services, and the potential role of ASP in this
ever-emerging field. To end this section, Wolfgang Faber showed how
magic sets may be adapted for ASP, and how this technique can be
fruitfully exploited for data integration.
After some cake and coffee, Jeffrey Remmel explained how to extend ASP
by suitable constructs in order to reason about infinite sets. An
extension to ASP was also the topic of the next talk by Pascal Nicolas.
He dealt with adding certainty levels, arriving at possibility theory
for ASP. Paolo Ferraris then gave a novel characterization of models in
equilibrium logic for propositional theories, and explained how it can
be used to define the semantics of ASP with aggregates. The final
extension for that day was described by Giovambattista Ianni, who
presented an extension of ASP by templates.
There was also an after-dinner session, in which Christian Anger and
Mirek Truszczynski spoke about Asparagus, a benchmarking system for
ASP. After their report on the benchmarks, status, and latest results,
there was an open discussion about future directions of this effort.
The second day started with
an invited talk by Thomas Eiter. In his talk he presented how ASP can
be extended in order to be used in the semantic web, in particular for
tightly coupling ASP to other reasoning engines.
The following regular session focussed on ASP solvers. Nicola Leone
started by reporting on ongoing enhancements and applications of the
DLV system, followed by Torsten Schaub, who presented a platform for
distributed answer set solving called Platypus. Mirek Truszczynski
concluded the session by describing how to apply pseudo-boolean
constraint solvers for answer sets computation.
In the afternoon, the relationship of ASP to SAT and other logics was
discussed in detail. Yuliya Lierler started by describing how to use
SAT solvers to compute answer sets for disjunctive logic programs.
Marco Maratea followed by analyzing the relationship between Answer Set
and SAT on an algorithmic level. Eugenia Ternovska then presented a
framework for representing and solving NP search problems, which
combines ideas from SAT, constraint satisfaction, and ASP. Finally, Ken
Satoh built on computing minimal hitting sets in order to enumerate
maximal sets with respect to the monotone property.
Finally, there was a panel discussion, moderated by Ilkka Niemel¨a,
on future developments of the field. Marc Denecker, Yannis Dimopoulos,
Michael Gelfond, Nicola Leone, and Ilkka himself were the panelists.
Interesting discussions developed, which could only be stopped by the
call for dinner.
In the evening, the members of the European Community funded Working
group on Answer Set Programming (WASP) held their meeting, while the
other participants enjoyed discussions and the many leisure
opportunities offered in the castle, such as billiards, ping pong, the
music room, the wine cellar, or just had a walk to the medieval castle
ruins on a hill nearby.
The third day started with an
application session. Stijn Heymans introduced extended conceptual logic
programs and showed how they can be used to simulate description logics
and for nonmonotonic ontological reasoning in the Semantic Web. Rafal
Grabos then introduced us to the combinatorial vote problem and how it
can be solved by using logic programs with ordered disjunctions.
Conformant planning, finding plans which certainly establish a goal in
a nondeterministic environment, were the focus of Michael Gelfond’s
talk. He showed how ASP can be used to solve this problem. Finally,
Alessandra Mileo explained how to represent user profiles of persons
browsing the web by means of ASP.
The next session was again focusing on the relation between ASP, SAT
and other logics. Ilkka Niemelä started by describing how to solve
boolean equation systems by using ASP, thus being able to model check
alternating formulas of modal mu-calculus. Agustín Valverde
followed by describing how to compile propositional theories into ASP
in a modular way, giving also complexity results. Closing the session,
David Pearce focused on paraconsistent answer sets for propositional
theories, defining them as an extension of Routley semantics.
After lunch, Martin Gebser spoke about the ASP system nomore++, and its
approach of computing answer sets. Stefania Costantini outlined a
methodology for static analysis for Answer Set Programming, based on
graph cycles.
Then, most of the participants joined an excursion to the nearby city
of Trier, which is said to be the oldest city in Germany. Split into
two groups we visited the the major sights of Trier, including the
Porta Nigra, dating back to the Romans, the large basilica, the town
center and the house in which Karl Marx was born, all backed up by
eloquent explanations and anecdotes by the tour guides. The evening
ended with a nice dinner in a restaurant which also offers specialities
prepared according to ancient Roman recipes.
The fourth day was opened by
David Mitchell’s invited talk, which focused on SAT Solving, giving a
comprehensive overview of the developments and challenges in this field.
In the following session, Inna Pivkina described how Revision
Programming can be applied to computing minimal solution updates in the
von Neumann-Morgenstern approach. Marina de Vos then talked about how
to employ ASP for modelling and analysing social properties in
multi-agent systems, while Fabio Massacci reported how he used ASP in
Security Requirements Engineering.
After lunch, the focus was on equivalences of logic programs. In a
joint talk, Hans Tompits and Stefan Woltran gave an overview of their
contributions to this field, which included characterisations and
complexity of strong and uniform equivalence in ASP, as well as
generalizations of the equivalence notion, which are aimed at modular
programming. To complete the session, Kathrin Konczak introduced and
discussed strong equivalence for logic programs with preferences.
The following session, dealing with ID-Logic, was opened by Maarten
Marien, who presented an algorithm and system for model generation in
ID-Logic. Joost Vennekens followed by analyzing properties of ID-logic
by means of approximation theory.
In the final session of this day, Ramon Otero spoke about how to
represent protein folding as a dynamic process in ASP, indicating that
computationally this approach is challenging the best alternative
methods. Finally, Yuting Zhao reported on different schemes for
randomly generating ASP programs, and experiments in which hard regions
could be identified.
In the morning of the last day of
the seminar, Artur Mikitiuk started by describing a language of
propositional logic with pseudo-boolean constraints to model search
problems, along with a system that works via translations to classical
or pseudo-boolean satisfiability. Martin Brain ordered his computer to
“Do what I meant, not what I said”, describing issues and challenges in
debugging ASP. Victor Marek then defined proof schemes, and showed how
this construct can be used to prove properties of ASP.
In the final session, Emilia Oikarinen reported on a system which
translates parallel circumscription into disjunctive ASP, and finally
Loreto Bravo defined a semantics for consistent answers of peer-to-peer
systems with trust relations, and showed how to use ASP to compute
them. After her talk, the organizers took the opportunity to wrap up
the seminar and start an open discussion, after which the event was
formally closed.
As a coda, Joost Vennekens is editing a volume of Dagstuhl Seminar
Proceedings, in which papers accompanying some of the presentations
will be published.
Summarizing, the event brought together many of the researchers of the
area, and allowed for exchanging the latest developments and trends. I
believe that each participant could profit a lot of the seminar, and I
am quite sure that many great ideas and future publications have been
come up with during this get-together.
