Distributed Open Answer Set Programming

The Semantic Web envisions a Web where information is represented by means of formal vocabularies called ontologies, for enabling automatic processing and retrieval of information. Ontologies are described using logical formalisms. Typically, ontology languages are based either on Description Logics or on non-monotonic rule-based formalisms. Recently, there is an intensive research interest for the development of hybrid representation formalisms, which bring together some of the advantages of both approaches, like non-monotonic reasoning from the LP side and the Open World Assumption from the DL side. Among these, Open Answer Set Programming is a language which extends the Logic Programming language Answer Set Programming with open domains, which are supersets of a program`s constants, which can be used in grounding the program. The abundance and diversity of information on the Web translates in the presence of different ontologies, some of them with overlapping content. Ontologies are interconnected by mappings, which are logical axioms that relate elements of one ontology to elements of another, and these interconnections give rise to so-called ontology networks. One of the challenges concerning the usage of such ontology networks for formal representation of practical knowledge is the development of scalable reasoning methods. The local model semantics which was introduced in order to reason with Multi-Contextual Systems (MCS) seems to be a promising approach in this direction which serves as the basis of many representation formalisms for modeling distributed knowledge bases. So far, none of the existent distributed formalisms which adopts this kind of semantics is based on a hybrid language. Given the increasing interest in hybrid knowledge representation formalisms as basis of the Semantic Web, we propose the development of a new representation and inference system for the Semantic Web, called Distributed Open Answer Set Programming (DOASP), which is an extension of the hybrid formalism OASP in the direction of distributedness. DOASP will allow the representation of ontology networks, where ontologies and mappings are OASP theories. The semantics of DOASP will be a combination between the local model semantics and the OASP semantics. We plan to identify fragments of DOASP for which reasoning is decidable and to devise efficient algorithms for reasoning with those fragments. Our algorithms will try to exploit the distributedness of the knowledge base (the ontology network), that is, to answer queries by calls to local reasoning procedures associated with each ontology, and subsequent combination of the results. While there are algorithms for reasoning with contextual default theories and contextual ASP, reasoning with DOASP is not a trivial task as there are no algorithms even for local reasoning, i.e., reasoning with some of the decidable fragments of OASP. Thus, an important component in our research will be the definition of efficient (local) inference procedures for OASP itself.

Semantic Technologies encompass a wide range of different knowledge representation languages: the Resource Description Framework (RDF and RDF(S)), the Web Ontology Language (OWL), the Rule Interchange Framework (RIF), and many more. Two of the aforementioned technologies rely on fundamentally different logical formalisms: OWL-(DL) on Description Logics and RIF on rule-based approaches. As such the use of those 2 language families is different. Ontology languages such as OWL are used to describe terminological knowledge (concepts and relationships between those concepts), while rule-based approaches deal in most cases with more dynamic knowledge (for example, in the form of business rules). This interplay between terminologies and dynamic reasoning over these terminologies calls for a formal integration of ontology- and rule languages. Or, taking the vantage point of some of its underlying logical formalisms, an integration of Description Logics and Logic Programming. The proposal of such a framework was the result of Dr. Heymans`s Ph.D. research: Open Answer Set Programming. Open Answer Set Programming combines the best of both worlds: open domains and decidability from the Description Logics world and nonmonotonic rule-based expression of knowledge from Logic Programming. In that work, complexity and decidability was investigated as well as its use for representing hybrid integration approaches. In the FWF project `Distributed Open Answer Set Programming`, we focused on defining reasoning algorithms for Open Answer Set Programming. Indeed, up to the point of the FWF project no reasoning algorithms were available for Open Answer Set Programming, hampering the way to adoption of the framework. Specifying reasoning algorithms for Open Answer Set Programming proved to be a notoriously difficult task, that we successfully managed. It is complicated due to the inherent differences of the underlying frameworks: Description Logic tableaux algorithms deal with open domains but do not cater for the nonmonotonicity of the language. Vice versa, Logic Programming approaches deal with nonmonotonicity but they deal not with the open domains. We successfully defined reasoning algorithms for expressive decidable fragments of Open Answer Set Programming, thus enabling adoption of the integrating approach.