%0 Journal Article %J ACM Trans. Comput. Log. %D 2013 %T Complexities of Horn Description Logics %A Markus Krötzsch %A Sebastian Rudolph %A Pascal Hitzler %K computational complexity %K description logics %K Horn logic %X Description Logics (DLs) have become a prominent paradigm for representing knowledge bases in a variety of application areas. Central to leveraging them for corresponding systems is the provision of a favourable balance between expressivity of the knowledge representation formalism on the one hand, and runtime performance of reasoning algorithms on the other. Due to this, Horn description logics (Horn DLs) have attracted attention since their (worst-case) data complexities are in general lower than their overall (i.e. combined) complexities, which makes them attractive for reasoning with large sets of instance data (ABoxes). However, the natural question whether Horn DLs also provide advantages for schema (TBox) reasoning has hardly been addressed so far. In this paper, we therefore provide a thorough and comprehensive analysis of the combined complexities of Horn DLs. While the combined complexity for many Horn DLs studied herein turns out to be the same as for their non-Horn counterparts, we identify subboolean DLs where Hornness simplifies reasoning. We also provide convenient normal forms for Horn DLs. %B ACM Trans. Comput. Log. %V 14 %P 2 %G eng %U http://doi.acm.org/10.1145/2422085.2422087 %R 10.1145/2422085.2422087 %0 Conference Paper %B Proceedings of the 9th International Workshop on Scalable Semantic Web Knowledge Base Systems, co-located with the International Semantic Web Conference (ISWC 2013) %D 2013 %T DistEL: A Distributed EL+ Ontology Classifier %A Raghava Mutharaju %A Pascal Hitzler %A Prabhaker Mateti %E Thorsten Liebig %E Achille Fokoue %K Classification %K DistEL %K Distributed Reasoning %K EL+ %K OWL %K Scalability %X OWL 2 EL ontologies are used to model and reason over data from diverse domains such as biomedicine, geography and road traffic. Data in these domains is increasing at a rate quicker than the increase in main memory and computation power of a single machine. Recent efforts in OWL reasoning algorithms lead to the decrease in classification time from several hours to a few seconds even for large ontologies like SNOMED CT. This is especially true for ontologies in the description logic EL+ (a fragment of the OWL 2 EL profile). Reasoners such as Pellet, Hermit, ELK etc. make an assumption that the ontology would fit in the main memory, which is unreasonable given projected increase in data volumes. Increase in the data volume also necessitates an increase in the computation power. This lead us to the use of a distributed system, so that memory and computation requirements can be spread across machines. We present a distributed system for the classification of EL+ ontologies along with some results on its scalability and performance. %B Proceedings of the 9th International Workshop on Scalable Semantic Web Knowledge Base Systems, co-located with the International Semantic Web Conference (ISWC 2013) %I CEUR-WS.org %C Sydney, Australia %V 1046 %P 17-32 %8 10/2013 %0 Journal Article %J Semantic Web %D 2013 %T Paraconsistent OWL and Related Logics %A Frederick Maier %A Yue Ma %A Pascal Hitzler %K Automated Deduction %K Complexity %K Description Logic %K OWL %K Paraconsistency %K Semantic Web %K Web Ontology Language %X The Web Ontology Language OWL is currently the most prominent formalism for representing ontologies in Semantic Web applications. OWL is based on description logics, and automated reasoners are used to infer knowledge implicitly present in OWL ontologies. However, because typical description logics obey the classical principle of explosion, reasoning over inconsistent ontologies is impossible in OWL. This is so despite the fact that inconsistencies are bound to occur in many realistic cases, e.g., when multiple ontologies are merged or when ontologies are created by machine learning or data mining tools. In this paper, we present four-valued paraconsistent description logics which can reason over inconsistencies. We focus on logics corresponding to OWL DL and its profiles. We present the logic SROIQ4, showing that it is both sound relative to classical SROIQ and that its embedding into SROIQ is consequence preserving. We also examine paraconsistent varieties of EL++, DL-Lite, and Horn-DLs. The general framework described here has the distinct advantage of allowing classical reasoners to draw sound but nontrivial conclusions from even inconsistent knowledge bases. Truth-value gaps and gluts can also be selectively eliminated from models (by inserting additional axioms into knowledge bases). If gaps but not gluts are eliminated, additional classical conclusions can be drawn without affecting paraconsistency. %B Semantic Web %V 4 %P 395–427 %G eng %U http://dx.doi.org/10.3233/SW-2012-0066 %R 10.3233/SW-2012-0066 %0 Conference Paper %B Proceedings of the 24th International Workshop on Description Logics (DL 2011), Barcelona, Spain, July 13-16, 2011 %D 2011 %T Local Closed World Semantics: Keep it simple, stupid! %A Adila Krisnadhi %A Kunal Sengupta %A Pascal Hitzler %E Riccardo Rosati %E Sebastian Rudolph %E Michael Zakharyaschev %K circumscription %K closed world %K decidability %K Description Logic %X A combination of open and closed-world reasoning (usually called local closed world reasoning) is a desirable capability of knowledge representation formalisms for Semantic Web applications. However, none of the proposals made to date for extending description logics with local closed world capabilities has had any significant impact on applications. We believe that one of the key reasons for this is that current proposals fail to provide approaches which are intuitively accessible for application developers and at the same time are applicable, as extensions, to expressive description logics such as SROIQ, which underlies the Web Ontology Language OWL. In this paper we propose a new approach which overcomes key limitations of other major proposals made to date. It is based on an adaptation of circumscriptive description logics which, in contrast to previously reported circumscription proposals, is applicable to SROIQ without rendering reasoning over the resulting language undecidable. %B Proceedings of the 24th International Workshop on Description Logics (DL 2011), Barcelona, Spain, July 13-16, 2011 %I CEUR-WS.org %V 745 %8 07/2011 %G eng %U http://ceur-ws.org/Vol-745/paper_12.pdf %0 Journal Article %J International Journal of Software and Informatics %D 2010 %T Computational Complexity and Anytime Algorithm for Inconsistency Measurement %A Yue Ma %A Guilin Qi %A Guohui Xiao %A Pascal Hitzler %A Zuoquan Lin %K algorithm %K computational complexity %K inconsistency measurement %K Knowledge representation %K multi-valued logic %X

Measuring inconsistency degrees of inconsistent knowledge bases is an important problem as it provides context information for facilitating inconsistency handling. Many methods have been proposed to solve this problem and a main class of them is based on some kind of paraconsistent semantics. In this paper, we consider the computational aspects of inconsistency degrees of propositional knowledge bases under 4-valued semantics. We first give a complete analysis of the computational complexity of computing inconsistency degrees. As it turns out that computing the exact inconsistency degree is intractable, we then propose an anytime algorithm that provides tractable approximations of the inconsistency degree from above and below. We show that our algorithm satisfies some desirable properties and give experimental results of our implementation of the algorithm

%B International Journal of Software and Informatics %V 4 %P 3–21 %G eng %U http://www.ijsi.org/ch/reader/view_abstract.aspx?file_no=i41&flag=1 %0 Conference Paper %B Scientific and Statistical Database Management, 22nd International Conference, SSDBM 2010 %D 2010 %T Provenance Context Entity (PaCE): Scalable Provenance Tracking for Scientific RDF Data %A Satya S. Sahoo %A Olivier Bodenreider %A Pascal Hitzler %A Amit Sheth %A Krishnaprasad Thirunarayan %E Michael Gertz %E Bertram Ludäscher %K Biomedical knowledge repository %K Context theory %K Provenance context entity %K Provenance Management Framework. %K Provenir ontology %K RDF reification %X

The Semantic Web Resource Description Framework (RDF) format is being used by a large number of scientific applications to store and disseminate their datasets. The provenance information, describing the source or lineage of the datasets, is playing an increasingly significant role in ensuring data quality, computing trust value of the datasets, and ranking query results. Current Semantic Web provenance tracking approaches using the RDF reification vocabulary suffer from a number of known issues, including lack of formal semantics, use of blank nodes, and application-dependent interpretation of reified RDF triples that hinders data sharing. In this paper, we introduce a new approach called Provenance Context Entity (PaCE) that uses the notion of provenance context to create provenance-aware RDF triples without the use of RDF reification or blank nodes. We also define the formal semantics of PaCE through a simple extension of the existing RDF(S) semantics that ensures compatibility of PaCE with existing Semantic Web tools and implementations. We have implemented the PaCE approach in the Biomedical Knowledge Repository (BKR) project at the US National Library of Medicine to support provenance tracking on RDF data extracted from multiple sources, including biomedical literature and the UMLS Metathesaurus. The evaluations demonstrate a minimum of 49% reduction in total number of provenancespecific RDF triples generated using the PaCE approach as compared to RDF reification. In addition, using the PACE approach improves the performance of complex provenance queries by three orders of magnitude and remains comparable to the RDF reification approach for simpler provenance queries. 

%B Scientific and Statistical Database Management, 22nd International Conference, SSDBM 2010 %I Springer %C Heidelberg, Germany %V 6187 %P 461–470 %G eng %U http://dx.doi.org/10.1007/978-3-642-13818-8_32 %R 10.1007/978-3-642-13818-8_32