Budva, Montenegro, June 11th 2006. Co-located with the 3d European Semantic Web Conference

Tutorial

Slides, exercises and hands-on will be available soon.

• TableOfContents

Purpose

The purpose of this tutorial is to get the audience familiar with the Answer Set Programming (ASP) Paradigm in the perspective of its fruitful usage for Semantic Web applications.

Tutorial Contents and Tentative Schedule

• Part one - Morning session (9:00-12:30)
  • Interactive session 1: Introduction to the ASP basics
  • Interactive session 2: ASP Semantic Web extensions
• Part two - Afternoon session (14:00-17:30)
  • Current and Future direction of ASP in the Semantic Web field
  • Hands-on session

What is ASP ?

ASP is a declarative logic programming paradigm with its roots in Knowledge Representation and Logic Programming. Its semantics relies on the notion of Stable Model, which is also the preferred semantics for Disjunctive Logic Programming. Although different, these three notions are sometimes considered as synonims: indeed they have, in a sense, an overlapping meaning. Systems and languages based on ASP are ready for tackling many of the challenges the Semantic Web offers, and in particular, are good candidates for solving a variety of issues which have been delegated to the Rule/Logic Layers in the Semantic Web vision. ASP systems are scalable, allow to mix monotonic with nonmonotonic reasoning, permit to combine rules with ontologies, and can interface external reasoners. Moreover, ASP is especially tailored at solving configuration and matchmaking problems involving reasoning with preferences by featuring easy to use, fully declarative soft & hard constraint specification languages.

Benefits of ASP

• Fully declarative. ASP is fully declarative. The order of rules and atoms in a logic program is not important, and in general, no knowledge of the operational semantics a specific solver adopts is required.

• Decidable. ASP programs are, in their basic flavor, naturally decidable. No special restrictions are needed in order to keep this important property.

• Monotonic and nonmonotonic. ASP supports strong negation as well as negation as failure. By means of the latter default reasoning and nonmonotonic inheritance are enabled.

• Nondeterministic. It is possible to define concepts ranging over a space of choices without any particular restriction. Extension of the basic semantics with preferences, soft and hard constraint, enable the compact specification of search and optimization problems.

• Scalable. Despite the computational expressiveness of ASP, state-of-the-art solvers currently reached the maturity for dealing with large datasets.

ASP and the Semantic Web

Many lines of research currently mix ASP, and other related rule based languages, and Semantic Web. They can be divided in three categories:

• Reductions from description logics to ASP programs.

  • Reasoning under description logics semantics can be reduced to reasoning under ASP. This approach, currently being thoroughly investigated, would lead to the development of systems much closer to completeness than the current ones, and more efficient in tasks, such as querying which state-of-the-art description logic solvers are not aimed at.

• Interaction with rules with strict semantic separation.

  • In this setting ASP should play its role in the Rule layer, while OWL/RDF flavors would keep their purpose of description languages, not aimed at intensive reasoning jobs, in the underlying Ontology layer. The two layers are kept strictly distinguished. From the Rule Layer point of view, ontologies are dealt with as an external source of information whose semantics is treated separately. Nonmonotonic reasoning and rules are allowed in a decidable setting, as well as arbitrary mixing of closed and open world reasoning.

• Interaction with rules with strict semantic Integration with the Ontology Layer.

  • Rules are introduced by adapting existing semantics for rule languages directly in the Ontology layer. This approach is peculiar of SWRL and DLP, but there are also similar attempts in the ASP field.

• Semantic Web applications.

  • A variety of upcoming application justifies the adoption of ASP as suitable formalism for implementing the Rule Layer. The inherent nondeterminism and the possibility to enrich the semantics with soft and weak constraint, make ASP a good candidate for applications like web service matchmaking and ontology alignment.

Outline of the tutorial content

• Under Construction.

Intended audience and prerequisites

The tutorial is mainly directed to two categories of attendees:

• Beginners. Attendees with minimal knowledge about logic programming and/or ASP will especially take advantage of Part 1 of the tutorial.

• Expert and intermediate. The researcher with good general background in logic programming, or with a background in description logics, wishing to consider ASP as a potential new line of research will benefitfrom the Interactive session 2 and of Part 2.

Although no specific know-how is needed as a prerequisite, basic knowledge about ontologies, web services, rule languages will allow attendees to better understand and follow the tutorial.

The presenters

• [http://www.kr.tuwien.ac.at/staff/eiter Thomas Eiter]

• [http://www.gibbi.com Giovambattista Ianni]

• [http://www.polleres.net Axel Polleres]

Some references

(feel free to ask [mailto:ianni@mat.unical.it GB Ianni] if you wish your ASP/SW related work cited here)

The interactive sessions and the hands-on session will be given by taking advantage of some ASP solvers, in the development of which the presenters are directly involved:

• The [http://www.dlvsystem.com The DLV System Web site]

• The [http://www.mat.unical.it/ianni/wiki/dlt The DLT system Web site]

• The [http://www.kr.tuwien.ac.at/staff/roman/dlvhex The DLV-HEX Web site]

• The [http://www.kr.tuwien.ac.at/staff/roman/semweblp The NLP-DL Web site]

Other known ASP solvers are:

• ASSAT. F. Lin and Y. Zhao. ASSAT: computing answer sets of a logic program by SAT solvers. Artificial Intelligence, 157(1-2):115--137, 2004.

• Cmodels-3. Y. Lierler. Disjunctive Answer Set Programming via Satisfiability. LPNMR'05, Diamante, Italy, September 2005. LNCS 3662.

• dcs. D. East and M. Truszczynski. dcs: An Implementation of DATALOG with Constraints. NMR'2000, Breckenridge, Colorado, USA, April 2000.

• DeReS. P. Cholewinski, V. Marek, and M. Truszczynski. The Default Reasoning System DeReS. KR 1996, pp. 518-528, Cambridge, Massachusetts, USA, 1996.

• DisLog. D. Seipel and H. Thone. DisLog: A System for Reasoning in Disjunctive Deductive Databases. DAISD'94, pp. 325--343.

• DisLop. C. Aravindan, J. Dix, and I. Niemela. DisLoP: A Research Project on Disjunctive Logic Programming. AI Communications. 10(3/4):151-165, 1997.

• NoMoRe. C. Anger, K. Konczak, and T. Linke. NoMoRe: A System for Non-Monotonic Reasoning. LPNMR'01, Vienna, Austria, September 2001. LNAI 2173, pp. 406-410

• aspps. D. East and M. Truszczynski. Propositional Satisfiability in Answer-set Programming. KI'2001, pp. 138-153, LNAI 2174, 2001.

• SLG. W. Chen and D. Scott Warren. Computation of Stable Models and Its Integration with Logical Query Processing. IEEE TKDE, 8(5):742--757, 1996.

• [http://www.tcs.hut.fi/Software/smodels/ GnT & Smodels]. T. Janhunen, I. Niemela, D. Seipel, P. Simons, and J.H. You. Unfolding Partiality and Disjunctions in Stable Model Semantics. ACM TOCL, to appear.

• [http://wasp.unime.it WASP]. Web site of the Working Group on Answer Set Semantics.

• [http://www.kr.tuwien.ac.at/projects/WASP/showcase.html The WASP showcase]. A collection of applications of ASP in the real world.

Foundational papers about Answer Set Programming:

• M. Gelfond and V. Lifschitz. Classical Negation in Logic Programs and Disjunctive Databases. New Generation Computing, 9:365--385, 1991.

Semantic Web & ASP related papers:

• Translations from Description Logics to ASP or related formalisms:

  • P. Burek and R. Grabos. Dually structured concepts in the semantic web: Answer set programming approach. ESWC 2005, Heraklion, Crete, Greece. LNCS 3532.
  • S. Heymans, D. Van Nieuwenborgh, and D. Vermeir. Nonmonotonic ontological and rule-based reasoning with extended conceptual logic programs. ESWC 2005. LNCS 3532, pages 392-407.
  • U. Hustadt, B. Motik, and U. Sattler. Reducing shiq-description logic to disjunctive datalog programs. KR2004, Whistler, Canada, pp. 152--162, 2004.
  • T. Swift. Deduction in Ontologies via ASP. LPNMR-2004, Fort Lauderdale, Florida, USA, January 2004.

• Coupling of rules and ontologies with strict semantic integration:

  • A. Analyti, G. Antoniou, C. Viegar Damasio, and G. Wagner. Stable model theory for extended RDF ontologies. ISWC 2005, Galway, Ireland. pp. 21-36.

• Coupling of rules and ontologies with strict semantic separation:

  • T. Eiter, T. Lukasiewicz, R. Schindlauer, and H. Tompits. Combining Answer Set Programming with Description Logics for the Semantic Web. KR2004, Whistler, Canada, pp. 141-151.
  • T. Eiter, G. Ianni, R. Schindlauer, and H. Tompits. A Uniform Integration of Higher-Order Reasoning and External Evaluations in Answer Set Programming. IJCAI 2005, pp. 90-96, Edinburgh, UK.
  • S. Heymans, D. Van Nieuwenborgh, and D. Vermeir. Preferential reasoning on a web of trust. In ISWC 2005, Galway, Ireland. LNCS 3729, pp. 368-382.
  • T. Lukasiewicz. Stratified probabilistic description logic programs. ISWC 2005, Workshop 3: Uncertainty Reasoning for the Semantic Web, pages 87-97, 2005.

• Applications:

  • A. Rainer. Web Service Composition under Answer Set Programming. KI-Workshop "Planen, Scheduling und Konfigurieren, Entwerfenl" PuK, 2005.
  • K. Wang, G. Antoniou, R. W. Topor, and A. Sattar. Merging and aligning ontologies in dl-programs. RuleML 2005, Galway, Ireland. pp. 160-171, 2005.