Invited Talks


P ≠ P: Why Some Reasoning Problems are More Tractable Than Others

Markus Krötzsch
Department of Computer Science, Technical University of Dresden

Knowledge representation and reasoning leads to a wide range of computational problems, and it is of great interest to understand the difficulty of these problems. Today this question is mainly studied using computational complexity theory and algorithmic complexity analysis. For example, entailment in propositional Horn logic is P-complete and a specific algorithm is known that runs in linear time.

Unfortunately, tight algorithmic complexity bounds are rare and often based on impractical algorithms (e.g., O(n2.373) transitive closure by matrix multiplication), whereas computational complexity results abound but are very coarse-grained (e.g., many P-complete problems cannot be solved in linear time).

In this talk, we therefore advocate another approach of gauging the difficulty of a computation: we reformulate computational problems as query answering problems, and then ask how powerful a query language is needed to solve these problems. This reduces reasoning problems to a computational model -- query answering -- that is supported by many efficient implementations. It is of immediate practical interest to know if a problem can be reduced to query answering in an existing database system. On the theoretical side, it allows us to distinguish problems in a more-fine grained manner than computational complexity without being specific to a particular algorithm. We provide several examples of this approach and discuss its merits and limitations.

Is the Web of Data turning into a self-organising complex system? And what does that mean for our tools and theories?

Frank van Harmelen
Computer Science Department of the VU University Amsterdam

The Web of Data has become the largest knowledge base ever built, and is used by companies like Yahoo and Google to better serve their customers. With thousands of datasets worldwide, and with billions of facts, it is the first knowledge-base large enough to begin displaying Complex System behaviour. We can observe that the WoD graph contains densely connected clusters which are only sparsely connected to each other, that the connectivity of the graph depends on a small number of nodes, that the degree distribution of the WoD graph is highly skewed, and that its structure varies between aggregation levels. These observations raise important questions: is the meaning of a node dependent on the cluster ("context") in which it appears? Is the pathlength between two nodes related to their "semantic distance"? Is the meaning of densely connected nodes more "important" or more "certain"? Properties such as clustering, connectivity and path length are not even described, let alone explained by traditional model-theoretic semantics. Do such properties contribute to the meaning of a knowledge graph? Unfortunately, the classical model-theoretic account of knowledge graphs doesn't have anything to say about any of these properties. It doesn't even describe them, let alone explain them. With its scale, context dependency, noise and dynamics it has outgrown its traditional model-theoretic semantics. We need to move towards a new paradigm for knowledge representation, where the traditional model-theoretic understanding of meaning is combined with models from information theory, from the theory of large scale networks and from self-organising complex systems. This talk will contain more questions than answers, but we will present some of our early results on scale-free properties of large knowledge graphs, on algorithms that exploit the graph structure using data compression techniques, and on methods to improve the graph's coherence.

Semantic Technologies in Selected Industrial Applications

Stephan Grimm
Siemens Corporate Technology, Munich

Semantic technology around knowledge representation and reasoning offers promising methods and tools for industrial applications. This talk will give an insight into selected projects where semantic technology has been successfully applied in innovative technology fields. It will illustrate that research on reasoning, rule-based systems and ontologies does have an impact in areas like power generation, industrial automation or health care, to name just a few.

Web Reasoning for Cultural Heritage

Nasos Drosopoulos, Ilianna Kollia
National Technical University of Athens, Greece

Cultural Heritage is the focus of a great and continually increasing number of R&D initiatives, aiming at efficiently managing and disseminating cultural resources on the Web. As more institutions make their collections available online and, proceed to aggregate them in domain repositories, knowledge-based management and retrieval becomes a necessary evolution from simple syntactic data exchange. In the process of aggregating heterogeneous resources and publishing them for retrieval and creative reuse, networks such as Europeana and DPLA invest in technologies that achieve semantic data integration. The resulting repositories join the Linked Open Data cloud, allowing to link cultural heritage domain knowledge to existing datasets. Integration of diverse information is achieved through the use of formal ontologies, enabling reasoning services to offer powerful semantic search and navigation mechanisms.