TY - JOUR T1 - Complexities of Horn Description Logics JF - ACM Trans. Comput. Log. Y1 - 2013 A1 - Markus Krötzsch A1 - Sebastian Rudolph A1 - Pascal Hitzler KW - computational complexity KW - description logics KW - Horn logic AB - 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. VL - 14 UR - http://doi.acm.org/10.1145/2422085.2422087 ER - TY - CONF T1 - DistEL: A Distributed EL+ Ontology Classifier T2 - Proceedings of the 9th International Workshop on Scalable Semantic Web Knowledge Base Systems, co-located with the International Semantic Web Conference (ISWC 2013) Y1 - 2013 A1 - Raghava Mutharaju A1 - Pascal Hitzler A1 - Prabhaker Mateti ED - Thorsten Liebig ED - Achille Fokoue KW - Classification KW - DistEL KW - Distributed Reasoning KW - EL+ KW - OWL KW - Scalability AB - 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. JF - Proceedings of the 9th International Workshop on Scalable Semantic Web Knowledge Base Systems, co-located with the International Semantic Web Conference (ISWC 2013) PB - CEUR-WS.org CY - Sydney, Australia VL - 1046 ER - TY - JOUR T1 - Paraconsistent OWL and Related Logics JF - Semantic Web Y1 - 2013 A1 - Frederick Maier A1 - Yue Ma A1 - Pascal Hitzler KW - Automated Deduction KW - Complexity KW - Description Logic KW - OWL KW - Paraconsistency KW - Semantic Web KW - Web Ontology Language AB - 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. VL - 4 UR - http://dx.doi.org/10.3233/SW-2012-0066 ER - TY - CONF T1 - Local Closed World Semantics: Keep it simple, stupid! T2 - Proceedings of the 24th International Workshop on Description Logics (DL 2011), Barcelona, Spain, July 13-16, 2011 Y1 - 2011 A1 - Adila Krisnadhi A1 - Kunal Sengupta A1 - Pascal Hitzler ED - Riccardo Rosati ED - Sebastian Rudolph ED - Michael Zakharyaschev KW - circumscription KW - closed world KW - decidability KW - Description Logic AB - 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. JF - Proceedings of the 24th International Workshop on Description Logics (DL 2011), Barcelona, Spain, July 13-16, 2011 PB - CEUR-WS.org VL - 745 UR - http://ceur-ws.org/Vol-745/paper_12.pdf ER - TY - JOUR T1 - Computational Complexity and Anytime Algorithm for Inconsistency Measurement JF - International Journal of Software and Informatics Y1 - 2010 A1 - Yue Ma A1 - Guilin Qi A1 - Guohui Xiao A1 - Pascal Hitzler A1 - Zuoquan Lin KW - algorithm KW - computational complexity KW - inconsistency measurement KW - Knowledge representation KW - multi-valued logic AB -

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

VL - 4 UR - http://www.ijsi.org/ch/reader/view_abstract.aspx?file_no=i41&flag=1 ER - TY - CONF T1 - Provenance Context Entity (PaCE): Scalable Provenance Tracking for Scientific RDF Data T2 - Scientific and Statistical Database Management, 22nd International Conference, SSDBM 2010 Y1 - 2010 A1 - Satya S. Sahoo A1 - Olivier Bodenreider A1 - Pascal Hitzler A1 - Amit Sheth A1 - Krishnaprasad Thirunarayan ED - Michael Gertz ED - Bertram Ludäscher KW - Biomedical knowledge repository KW - Context theory KW - Provenance context entity KW - Provenance Management Framework. KW - Provenir ontology KW - RDF reification AB -

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. 

JF - Scientific and Statistical Database Management, 22nd International Conference, SSDBM 2010 PB - Springer CY - Heidelberg, Germany VL - 6187 UR - http://dx.doi.org/10.1007/978-3-642-13818-8_32 ER -