Towards Understanding Reasoning Complexity in Practice

Martín-Recuerda Moyano, Francisco and Walther, Dirk (2011). Towards Understanding Reasoning Complexity in Practice. In: "23rd Benelux Conference on Artificial Intelligence", 03/11/2011 - 04/11/2011, Ghent, Belgica. pp. 144-151.

Description

Title: Towards Understanding Reasoning Complexity in Practice
Author/s:
  • Martín-Recuerda Moyano, Francisco
  • Walther, Dirk
Item Type: Presentation at Congress or Conference (Article)
Event Title: 23rd Benelux Conference on Artificial Intelligence
Event Dates: 03/11/2011 - 04/11/2011
Event Location: Ghent, Belgica
Title of Book: Proceedings of the 23rd Benelux Conference on Artificial Intelligence
Date: 2011
Subjects:
Faculty: Facultad de Informática (UPM)
Department: Inteligencia Artificial
Creative Commons Licenses: Recognition - No derivative works - Non commercial

Full text

[img]
Preview
PDF - Requires a PDF viewer, such as GSview, Xpdf or Adobe Acrobat Reader
Download (214kB) | Preview

Abstract

Although the computational complexity of the logic underlying the standard OWL 2 for the Web Ontology Language (OWL) appears discouraging for real applications, several contributions have shown that reasoning with OWL ontologies is feasible in practice. It turns out that reasoning in practice is often far less complex than is suggested by the established theoretical complexity bound, which reflects the worstcase scenario. State-of-the reasoners like FACT++, HERMIT, PELLET and RACER have demonstrated that, even with fairly expressive fragments of OWL 2, acceptable performances can be achieved. However, it is still not well understood why reasoning is feasible in practice and it is rather unclear how to study this problem. In this paper, we suggest first steps that in our opinion could lead to a better understanding of practical complexity. We also provide and discuss some initial empirical results with HERMIT on prominent ontologies

More information

Item ID: 13503
DC Identifier: http://oa.upm.es/13503/
OAI Identifier: oai:oa.upm.es:13503
Deposited by: Memoria Investigacion
Deposited on: 22 Nov 2012 11:18
Last Modified: 21 Apr 2016 12:49
  • Logo InvestigaM (UPM)
  • Logo GEOUP4
  • Logo Open Access
  • Open Access
  • Logo Sherpa/Romeo
    Check whether the anglo-saxon journal in which you have published an article allows you to also publish it under open access.
  • Logo Dulcinea
    Check whether the spanish journal in which you have published an article allows you to also publish it under open access.
  • Logo de Recolecta
  • Logo del Observatorio I+D+i UPM
  • Logo de OpenCourseWare UPM