Skip to Content

TU Wien Fakultät für Informatik Knowledge-Based Systems Group
Top-level Navigation: Current-level Navigation:

Path: KBS > research > projects > mhex >

Tools: Drucken

Modular HEX-Programs

supported by the Austrian Science Funds (FWF) under project number P20841.

Contents

Project team

Motivation and Background

A notable extension of ASP are HEX-programs [eist2005, eist2006], which allow to specify meta-reasoning tasks through higher order atoms, and accommodate a universal interface for arbitrary sources of external computation through the notion of external atoms. For example, an external atom of the form &reach[g,n](X) might be used to access and reason about all nodes of a graph g that are reachable from node n, where the task of determining reachability is delegated to an external source of computation, respectively information source. By the extensibility of HEX-programs, we can thus easily access very different kinds of information resources and reason about them, hence a flexible approach for knowledge integration is supported. Moreover, HEX-programs have been successfully used in various kinds of applications like the SPARQL Query Language for RDF, which can be conveniently translated to HEX-programs (see [polleres2007b]), in planning [nev2007], and in ontology integration [hlkh2007, eite-etal-wi06]. These results show the effectiveness of incorporating external knowledge by means of external atoms.

An important observation is that a HEX-program might also use another HEX-program as an external source of computation, i.e., the HEX-semantics is capable of handling knowledge spread over more than one logic program—an ensemble of HEX-programs. This encourages the view of HEX-programs as modules, where each program holds only part of the encoded knowledge. Users would benefit from such a modularization, since each module in a modularized logic program is easier to build and maintain.

Along with the modularization of HEX-programs, another important aspect is the possibility to install HEX-programs on distributed machines connected via network links. Then, every HEX-program may incorporate additional knowledge from remote HEX-programs. The potential to modularize logic programs across machine boundaries into a distributed programming framework might be conceived as a web of programs. This kind of interacting logic programs are a very promising technique for representing and processing knowledge, since many applications naturally arise in this setting. Some examples include multi-agent systems, data integration, rule-base policy specification, distributed SPARQL processing, Networked RDF Graphs, multi-context systems.

If one aims at exploiting modular, possibly distributed, HEX-programs for advanced applications, e.g., in the above mentioned domains, several issues need to be resolved, that currently pose challenging research problems:

  1. How to evaluate a collection of HEX-programs efficiently?
  2. How to deal with inconsistency?
  3. How to deal with incomplete information?

Furthermore, optimization issues are interesting in this setting. In real-world environments, we face limited resources like bounds on the acceptable computation time, or the amount of data allowed to be transferred over a network link, etc. Thus, even in a perfectly working network, the total cost for computing the models of modular HEX-programs may be too high. Therefore, semantic weakenings and/or optimizations that yield scalable reasoning algorithms wrt. particular resources, e.g., communication cost, are of practical value.

Goal of the project

The goal of this project is to research and implement formalisms and reasoning techniques for providing a powerful reasoning framework in the context of modular logic programming and distributed reasoning by using declarative knowledge representation.

In particular, we shall investigate the use of logic programming under the Answer-Set Semantics for realizing languages and tools which extend the capabilities of current approaches, in order to support modular knowledge bases under this semantics for local and distributed evaluation.

Special attention will be given to the study of suitable models and algorithms for dealing with inconsistent and incomplete information of different kinds. Approximation-based reasoning methods shall be devised to speed up the evaluation of such kind of logic programs.

Furthermore, we shall provide an implementation of the envisaged reasoning platform using the conceived approaches. The modules for advanced reasoning that will be developed may be useful for applications in several domains such as in multi-agent and multi-context systems, for information integration, or for particular applications of Semantic Web reasoning. We will demonstrate the ability of the reasoning platform to support applications that access different sources of knowledge in a modular way and reason about them by means of a reference application in one of the domains mentioned.

State of the Project and Outlook

We started our project by defining a logic programming semantics, which allows for mutual (positive) recursion between modules—a novelty among modular logic programming formalisms. The Modular Nonmonotonic Logic Program (MLP) formalism has been introduced in [defk2009-iclp].

A naïve approach for evaluating MLPs by instantiating all modules is infeasible in practice. We have introduced an MLP fragment for which a better evaluation strategy is possible (see [defk2009-lpnmr]).

Software

Publications

2010

[bdefk2010-nmr]
Seif El-Din Bairakdar, Minh Dao-Tran, Thomas Eiter, Michael Fink, and Thomas Krennwallner. Decomposition of Distributed Nonmonotonic Multi-Context Systems. In Tommie Meyer and Eugenia Ternovska, editors, 13th International Workshop on Non-Monotonic Reasoning (NMR 2010), Toronto, Canada, May 14-16, 2010, CEUR Workshop Proceedings. CEUR-WS.org, May 2010, to appear.
[defk2010-kr]
Minh Dao-Tran, Thomas Eiter, Michael Fink, and Thomas Krennwallner. Distributed Nonmonotonic Multi-Context Systems. In Fangzhen Lin and Uli Sattler, editors, Proceedings of the 12th International Conference on Principles of Knowledge Representation and Reasoning (KR 2010), Toronto, Canada, 9-13 May, 2010, to appear.

2009

[ikmp2009-iswc]
Giovambattista Ianni, Thomas Krennwallner, Alessandra Martello, and Axel Polleres. Dynamic Querying of Mass-Storage RDF Data with Rule-Based Entailment Regime. In Abraham Bernstein, David R. Karger, Tom Heath, Lee Feigenbaum, Diana Maynard, Enrico Motta, and Krishnaprasad Thirunarayan, editors, 8th International Semantic Web Conference (ISWC 2009), Washington D.C., USA, 25-29 October, 2009, LNCS. Springer, October 2009.
[deiklm2009-rewerse]
Wlodzimierz Drabent, Thomas Eiter, Giovambattista Ianni, Thomas Krennwallner, Thomas Lukasiewicz, and Jan Maluszynski. Hybrid Reasoning with Rules and Ontologies. In Francois Bry and Jan Maluszynski, editors, Semantic Techniques for the Web: The REWERSE Perspective, volume 5500 of LNCS. Springer. To appear.
[ebdfik2009-frocos]
Thomas Eiter, Gerhard Brewka, Minh Dao-Tran, Michael Fink, Giovambattista Ianni, and Thomas Krennwallner. Combining Nonmonotonic Knowledge Bases with External Sources. In Silvio Ghilardi and Roberto Sebastiani, editors, 7th International Symposium on Frontiers of Combining Systems (FroCos 2009), Trento, Italy, September 16-18, 2009, volume 5749 of LNAI, pages 18-42. Springer, September 2009.
[defk2009-lpnmr]
Minh Dao-Tran, Thomas Eiter, Michael Fink, and Thomas Krennwallner. Relevance-driven Evaluation of Modular Nonmonotonic Logic Programs. In Fangzhen Lin and Torsten Schaub, editors, Proceedings of the 10th International Conference on Logic Programming and Nonmonotonic Reasoning (LPNMR 2009), Potsdam, Germany, 14-18 September, 2009, volume 5753 of LNCS, pages 87-100. Springer, September 2009.
[eik2009-rw]
Thomas Eiter, Giovambattista Ianni, and Thomas Krennwallner. Answer Set Programming: A Primer. In Enrico Franconi and Sergio Tessaris, editors, 5th International Reasoning Web Summer School (RW 2009), Brixen/Bressanone, Italy, August 30-September 4, 2009, volume 5689 of LNCS, pages 40-110. Springer, September 2009. Slides available at http://www.kr.tuwien.ac.at/staff/tkren/pub/2009/rw2009-lecture.zip.
[defk2009-iclp]
Minh Dao-Tran, Thomas Eiter, Michael Fink, and Thomas Krennwallner. Modular Nonmonotonic Logic Programming Revisited. In Patricia Hill and David S. Warren, editors, Proceedings of the 25th International Conference on Logic Programming (ICLP 2009), Pasadena, California, USA, July 14-17, 2009, volume 5649 of LNCS, pages 145-159. Springer, July 2009.
[efk2009-ijcai]
Thomas Eiter, Michael Fink, and Thomas Krennwallner. Decomposition of Declarative Knowledge Bases with External Functions. In Craig Boutilier, editor, Proceedings of the Twenty-first International Joint Conference on Artificial Intelligence (IJCAI-09), Pasadena, California, USA, July 11-17, 2009. AAAI Press, July 2009.
[dek2009-ecsqaru]
Minh Dao-Tran, Thomas Eiter, and Thomas Krennwallner. Realizing Default Logic over Description Logic Knowledge Bases. In Claudio Sossai and Gaetano Chemello, editors, Proceedings of the 10th European Conference on Symbolic and Quantitative Approaches to Reasoning with Uncertainty (ECSQARU 2009), Verona, Italy, July 1-3, 2009, volume 5590 of LNAI, pages 602-613. Springer, July 2009.
[ikmp2009-eswc]
Giovambattista Ianni, Thomas Krennwallner, Alessandra Martello, and Axel Polleres. A Rule System for Querying Persistent RDFS Data. In Lora Arroyo, Paolo Traverso, Fabio Ciravegna, Philipp Cimiano, Tom Heath, Eero Hyvönen, Riichiro Mizoguchi, Eyal Oren, Marta Sabou, and Elena Simperl, editors, The Semantic Web: Research and Applications, 6th European Semantic Web Conference, ESWC 2009, Heraklion, Greece, May 31-June 4, 2009, Proceedings, volume 5554 of LNCS, pages 857-862. Springer, June 2009.

2008

[efk2008-jcs]
Thomas Krennwallner, Thomas Eiter, and Michael Fink. Decomposing HEX-Programs: Preliminary Results. In Hans Kaiser and Raimund Kirner, editors, Proceedings of the Junior Scientist Conference 2008, pages 29-30, November 2008.
[eikp2008-rw]
Thomas Eiter, Giovambattista Ianni, Thomas Krennwallner, and Axel Polleres. Rules and Ontologies for the Semantic Web. In Cristina Baroglio, Piero A. Bonatti, Jan Maluszynski, Massimo Marchiori, Axel Polleres, and Sebastian Schaffert, editors, Reasoning Web: 4th International Summer School 2008, Venice Italy, September 7-11, 2008, Tutorial Lectures, volume 5224 of LNCS, pages 1-53. Springer, September 2008. Slides available at http://rease.semanticweb.org/.
[eiks2009-amai]
Thomas Eiter, Giovambattista Ianni, Thomas Krennwallner, and Roman Schindlauer. Exploiting conjunctive queries in description logic programs. Annals of Mathematics and Artificial Intelligence. Logic in AI: A Special Issue Dedicated to Victor W. Marek on the Occasion of His 65th birthday, 53(1-4):115-152, August 2008. Published online: 27 January 2009.

Cooperations

References

[eist2005]
Thomas Eiter, Giovambattista Ianni, Roman Schindlauer and Hans Tompits. A Uniform Integration of Higher-Order Reasoning and External Evaluations in Answer-Set Programming. In L. P. Kaelbling and A. Saffiotti, editors, Proceedings of the 19th International Joint Conference on Artificial Intelligence (IJCAI-05) Denver, USA, 2005.
[eist2006]
Thomas Eiter, Giovambattista Ianni, Roman Schindlauer and Hans Tompits. Effective Integration of Declarative Rules with External Evaluations for Semantic-Web Reasoning. In L. P. Kaelbling and A. Saffiotti, editors, Proceedings of the 3rd European Conference on Semantic Web (ESWC 2006), volume 4011 of LNCS, pages 273-287. Springer, 2009.
[polleres2007b]
Axel Polleres. From SPARQL to Rules (and back). Proceedings of the 16th World Wide Web Conference (WWW2007), pages 787-796, 2009.
[nev2007]
Davy Van Nieuwenborgh, Thomas Eiter, and Dirk Vermeir. Conditional Planning with External Functions. Proceedings of the 9th International Conference on Logic Programming and Nonmonotonic Reasoning (LPNMR 2007), volume 4483 of LNAI, pages 214-227. Springer, 2007.
[hlkh2007]
Robert Hoehndorf and Frank Loebe and Janet Kelso and Heinrich Herre. Representing default knowledge in biomedical ontologies: Application to the integration of anatomy and phenotype ontologies. BMC Bioinformatics, volume 8, pages 377, 2007.
[eite-etal-wi06]
Thomas Eiter and Giovambattista Ianni and Roman Schindlauer and Hans Tompits and Kewen Wang. Forgetting in Managing Rules and Ontologies. IEEE/WIC/ACM International Conference on Web Intelligence (WI 2006), pages 411--419. Hongkong, 2006.

Home / Kontakt / Webmaster / Offenlegung gemäß § 25 Mediengesetz: Inhaber der Website ist die Fakultät für Informatik an der Technischen Universität Wien, 1040 Wien. Die TU Wien distanziert sich von den Inhalten aller extern gelinkten Seiten und übernimmt diesbezüglich keine Haftung. / Disclaimer.