GraphIK

The main research domain of GraphIK is Knowledge Representation and Reasoning (KRR) , which studies paradigms and formalisms for representing knowledge and reasoning on these representations. We follow a logic-oriented approach of this domain: the different kinds of knowledge have a logical semantics and reasoning mechanisms correspond to inferences in this logic. However, in the field of logic-based KRR, we distinguish ourselves by using graphs and hypergraphs (in the graph-theoretic sense) as basic objects.

Indeed, we view labelled graphs as an abstract representation of knowledge that can be expressed in many KRR languages: different kinds of conceptual graphs --historically our main focus-- the Semantic Web language RDFS, expressive rules equivalent to the so-called tuple-generating-dependencies in databases, some description logics dedicated to query answering, etc. For these languages, reasoning can be based on the structure of objects (thus on graph-theoretic notions), with homomorphism as a core notion, while being sound and complete with respect to entailment in the associated logical fragments.

An important issue is to study trade-offs between the expressivity of languages and the computational tractability of reasoning in these languages.

We study KRR formalisms from three perspectives:

• theoretical (structural properties, expressiveness, translations into other languages, problem complexity, algorithm design),
• software (developing tools to implement theoretical results),
• applications (which also feed back into theoretical work).

A crucial point is that we are interested in knowledge bases for real-world applications , which means in particular that: even if logical soundness and completeness are fundamental properties of a reasoning mechanism, its empirical relevance is important too; even if the theoretical algorithmic complexity is a key criterion for evaluating the efficiency of an algorithm, practical experiments are also needed; and besides fundamental theoretical problems, we also study problems that arise in practice even if they may not be well defined from a theoretical viewpoint (as it can be the case for KB validation, KB evolution, reasoning in presence of inconsistencies, query-answering mechanisms etc.), which involves clarifying and formalizing them.

GraphIK focuses on some of the main challenges in KRR:

• ontology-based query answering , i.e., query answering taking an ontology into account and able to deal with large data sets,
• reasoning with rule-based languages,
• dealing with heterogeneous and with hybrid knowledge bases, i.e., composed of several modules that have their own formalism and reasoning mechanisms,
• representing preferences and reasoning with preferences,
• argumentative reasoning,
• dealing with inconsistencies.

GraphIK has three main scientific directions:

1. decidability, complexity and algorithms for problems in languages corresponding to first order logic fragments (with deduction being the fundamental problem),
2. representation of and reasoning with imperfect information and priorities,
3. the integration of theoretical tools to real knowledge-based systems.