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: [#unit1 Unit 1].
  • Interactive session 2. ASP extensions and Application Showcase: [#unit2 units 2 and 3].
• Part two - Afternoon session (14:00-17:30)
  • Interactive session 3. Current and Future direction of ASP in the Semantic Web field: [#unit4 Units 4, 5 and 6].
  • Interactive session 4. Hands-on session: [#unit7 Unit7].

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.

• Versatile. ASP languages support extended constructs such as soft and weak constraints, aggregates, macros, external calls, higher order features.

• 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, with Semantic Web technologies. 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

The tutorial is be divided in units: Anchor(unit1) Interactive Unit 1. ASP Basics. In this unit the attendees will become familiar with the basic notions and intuitive semantics of ASP. We will lean examples and exercises on common scenarios from the Semantic Web world, using for instance the OWL Wine ontology in order to get users familiar to ASP with known examples. On the one hand this will illustrate the additional and complementary KR capabilities of ASP in these domains, on the other hand this will show how they complement OWL with a fully declarative rule and constraint language. Users will be taught how to use ASP as a declarative KR formalism and query language involving non-determinism, disjunctive rules, strong and default negation and (hard) constraints. Examples will be accessible and executable through an online interface based on a state-of-the-art ASP solver. Anchor(unit2) Interactive Unit 2. ASP Extensions. In this unit several ASP advanced extensions will be tutored. Particularly, we will present extensions by aggregates known from database query languages; weak constraints, and how these can be used to encode preferences and priorities; rule templates which add a powerful macro-language to ASP; external function calls. Again, attendees will have the opportunity to try out their own examples through an online interface. Anchor(unit3) Unit 3. Current ASP State-of-the-Art. In this section, we will present an ASP application showcase, demonstrating an information integration scenario solved using the ASP methodology, (see for instance [http://www.kr.tuwien.ac.at/projects/WASP/showcase.html The WASP showcase]), as well as pointers to relevant past and current literature and research directions. Anchor(unit4) Unit 4. Contribution of ASP to the Semantic Web field. In the fourth and fifth unit, we will focus on new extensions of ASP aimed at Semantic Web applications. This first unit in the afternoon unit will survey and present current approaches of mixing ASP with Semantic Web technologies. We will discuss and survey different reductions from Description Logics to ASP and approaches which aim at a semantic integration of rules with the Ontology Layer. Anchor(unit5) Interactive Unit 5. ASP Semantic Web Extensions Part I. In this unit, we will present those general extensions of ASP which facilitates ASP engines with existing Description logics engines through so-called DL-atoms. We will show how this extension can be used to facilitate a clean interaction of Semantic Web languages with rules still keeping a strict semantic separation of both worlds. Attendees will be able to try out this extension through the provided online interface and experience ASP querying interleaved with reasoning over (DL) ontologies. Applications, advantages and drawbacks compared with the existing proposals from the previous unit will be presented. Anchor(unit6) Interactive Unit 6. ASP Semantic Web Extensions Part II. In this unit the notion of DL-atom is generalized to the one arbitrary external predicate. Combined with higher order reasoning, this extension can be plugged into existing ASP engines facilitating new fruitful applications, especially in the Semantic Web context. These include integration of ASP with a variety of full first-order reasoners, reification, etc. Anchor(unit7) Interactive Unit 7. Hands-on Session. Each of the previous units was accompanied with small practical examples. As a final part of the tutorial, the attendees will practice and combine their experiences from the different units with a larger test case. The session will be conducted dividing the audience in small groups which will be guided by one of the presenters through an integrated test scenario where the attendants have to solve certain modelling and problem solving tasks by applying the acquired ASP methodologies.

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 benefit from 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.