Volker Haarslev's List of Publications


Shortcut to year 1995 and earlier 1996 1997 1998 1999 2000 2001 2002 2003 2004 2005 2006 2007 2008 2009 2010 2011 2012 2013

2017


A Consequence-based Algebraic Calculus for SHOQ

Nikoo Zolfaghar Karahroodi, Volker Haarslev

Proceedings of the 30th International Workshop on Description Logics (DL 2017), Montpellier, France, CEUR.
Acrobat file

In this paper, we present a novel consequence-based algorithm to perform subsumption reasoning in SHOQ, which support nominals and Qualified Cardinality Restrictions (QCRs). Our algorithm maps numerical restrictions imposed by QCRs or nominals to inequalities and determines the feasibility of inequality systems by means of Integer Linear Programming.


Applying Machine Learning to Enhance Optimization Techniques for OWL Reasoning

Razieh Mehri, Volker Haarslev

Proceedings of the 30th International Workshop on Description Logics (DL 2017), Montpellier, France, CEUR.
Acrobat file

Various (tableau) optimization techniques have been integrated into OWL reasoners to speed up reasoning. Many of the techniques rely on heuristics that have been manually fine tuned for achieving a good performance but might fail dramatically when encountering ontologies exhibiting unexpected design patterns. A typical example are heuristics applied to disjunctions in order to select a disjunct to be added to the tableau. Evidences indicate that the order of selecting disjuncts can have a significant impact on reasoning speed. Our approach presented in this paper applies machine learning to make the selection process more effective and removes the need for manual fine tuning. We extended the OWL reasoner JFact accordingly to control the disjunct selection process. We demonstrate that one can successfully learn to choose a disjunct based on the most effective heuristic method. As a first step we focused on propositional SAT testing. Our results show that machine learning can speed up JFact by one to two orders of magnitude.


Pushing the Boundaries of Reasoning about Qualified Cardinality Restrictions

Jelena Vlasenko, Volker Haarslev, Brigitte Jaumard

Proceedings of the 11th International Symposium on Frontiers of Combining Systems (FroCoS 2017), Brasília, Brazil, LNAI 10483, pp. 95-112.
Acrobat file (preprint)

We present a novel hybrid architecture for reasoning about description logics supporting role hierarchies and qualified cardinality restrictions (QCRs). Our reasoning architecture is based on saturation rules and integrates integer linear programming. Deciding  the numerical satisfiability of a set of QCRs is reduced to solving a corresponding system of linear inequalities. If such a system is infeasible then the QCRs are unsatisfiable. Otherwise the numerical restrictions of the QCRs are satisfied but unknown entailments between qualifications can still lead to unsatisfiability. Our integer linear programming (ILP) approach is highly scalable due to integrating learned knowledge about concept subsumption and disjointness into a column generation model and a decomposition algorithm to solve it. Our experiments indicate that this hybrid architecture offers a better scalability for reasoning about QCRs than approaches combining both tableaux and ILP or applying traditional (hyper)tableau methods.


A Parallel Shared-Memory Architecture for OWL Ontology Classification

Zixi Quan, Volker Haarslev

Proceedings of the Tenth International Workshop on Parallel Programming Models and Systems Software for High-End Computing (P2S2) at the 46th International Conference on Parallel Processing (ICPP-2017), Bristol, UK, IEEE, pp. 200-209.
Acrobat file (preprint)

The Web Ontology Language (OWL) plays an important role in the {\em semantic web} to represent domain knowledge using classes, properties, and individuals. OWL reasoners analyze ontologies and offer inference services such as class satisfiability and subsumption. Ontology classification is an important and widely used service that computes a taxonomy of all classes occurring in an ontology. It can require significant amounts of runtime but most  OWL reasoners do not support any kind of parallel processing. We present a novel thread-level parallel architecture for ontology classification that is ideally suited for shared-memory SMP servers, where each thread can be mapped to a core on a one-to-one basis. We evaluated our prototype implementation with a set of real-world ontologies. Our experiments demonstrate a very good scalability resulting in a speedup that is linear to the number of available cores.


2016


A Saturation-based Algebraic Reasoner for ELQ

Jelena Vlasenko, Maryam Daryalal, Volker Haarslev, Brigitte Jaumard

Proceedings of the 5th Workshop on Practical Aspects of Automated Reasoning (PAAR 2016), Coimbra, Portugal, CEUR, pp. 110-124.
Acrobat file

We present a reasoning architecture for deciding subsumption for the description logic ELQ. Our architecture combines saturation rules with algebraic reasoning based on Integer Linear Programming (ILP). Deciding the so-called numerical satisfiability of a set of qualified cardinality restrictions is reduced to constructing a corresponding system of linear inequalities and applying ILP methods in order to determine whether this system is feasible. Our preliminary experiments indicate that this calculus offers a better scalability for qualified cardinality restrictions than approaches combining both tableaux and ILP as well as traditional (hyper)tableau methods.


2015


Abductive Conjunctive Query Answering w.r.t. Ontologies

Abductive Conjunctive Query Answering w.r.t. Ontologies

Ralf Möller, Özgür Özçep, Volker Haarslev, Anahita Nafissi, Michael Wessel

Künstliche Intelligenz, Vol. 30, 2015, pp. 177-182.
Acrobat file (preprint)

In this article we investigate abductive conjunctive query answering w.r.t. ontologies and show how use cases can benefit from this kind of query answering service. While practical reasoning systems such as Racer have supported abductive conjunctive query answering for 10 years now, and many projects have exploited this feature, few publications deal with A-box abduction from an implementation perspective. This article gives a generalized overview on features provided by practical systems and also explains optimization techniques needed to meet practical requirements.


Managing Changes in Distributed Biomedical Ontologies using Hierarchical Distributed Graph Transformation

Arash Shaban-Nejad, Volker Haarslev

International Journal of Data Mining and Bioinformatics, Vol. 11, No. 1, 2015, pp. 53-83.
Acrobat file (preprint)

Ontologies play a crucial role in current web-based biomedical applications for capturing contextual knowledge in the domain of life sciences. They are continuously evolving in order to fix the problems and provide valid knowledge. As our knowledge improves, the related definitions in the ontologies will be altered. This issue is inadequately addressed by available tools and algorithms, mostly due to the lack of suitable knowledge representation formalisms to deal with temporal abstract notations, and the over-reliance on human factors. Also most of the current approaches have been focused on changes within the internal structure of ontologies, and interactions with other existing ontologies have been widely neglected. In our research, after revealing and classifying some of the common alterations in a number of popular biomedical ontologies, we present a novel agent-based framework, RLR (Represent, Legitimate, and Reproduce), to semi-automatically manage the evolution of bio-ontologies, with emphasis on the FungalWeb Ontology, with minimal human intervention. RLR assists and guides ontology engineers through the change management process in general, and aids in tracking and representing the changes, particularly through the use of category theory. We have also employed rule-based hierarchical graph transformation to propose a more specific semantics for analyzing ontological changes and transformations between different versions of an ontology, as well as tracking the effects of a change in different levels of abstractions.


2013


Parallel OWL Reasoning: Merge Classification

Kejia WuVolker Haarslev 

Proceedings of the 3rd Joint International Semantic Technology (JIST) Conference, Seoul, Korea, November 28-30, 2013, LNCS 8388, pp. 211-227.
Acrobat file (preprint)

Our research is motivated by the ubiquitous availability of multiprocessor computers and the observation that available Web Ontology Language (OWL) reasoners  only make use of a single processor. This becomes rather frustrating for users working in ontology development, especially if their ontologies are complex and require long processing times using these OWL reasoners. We present a novel algorithm that uses a divide and conquer strategy for parallelizing OWL TBox classification, a key task in description logic reasoning.  We discuss some interesting properties of our algorithm, e.g., its suitability for distributed reasoning, and present an empirical study using a set of benchmark ontologies, where a speedup of up to a factor of 4 has been observed when using 8 workers in parallel.


Intelligent Tableau Algorithm for DL Reasoning

Ming Zuo, Volker Haarslev 

Proceedings of the 22nd International Conference on Automated Reasoning with Analytic Tableaux and Related Methods, Nancy, France, September 16-19, 2013, pp. 273-287.
Acrobat file (preprint)

Although state-of-the-art description logic (DL) reasoners are equipped with a comprehensive set of optimizations, reasoning performance is still a major bottleneck in both research and real world applications. In this paper, we propose a sound and complete algorithm called the intelligent tableau algorithm by incorporating comprehensive learning techniques to tackle all DL reasoning tasks. We also provide a reference implementation reasoner called LIGHT for the DL ALC dialect based on the algorithm we developed. Preliminary tests indicate that significant improvements can be achieved, i.e., compared to other state-of-the-art reasoners, LIGHT is up to two orders of magnitude faster for simple problems and several orders of magnitude faster for more difficult problems. Even though in this work our discussion is restricted to the ALC reasoning problem, our conjecture is that the algorithm developed can easily be extended to super-logics of ALC.


Exploring Parallelization of Conjunctive Branches in Tableau-based Description Logic Reasoning

Kejia Wu, Volker Haarslev 

Proceedings of the 2013 International Workshop on Description Logics (DL-2013), Ulm, Germany, July 23-26, 2013, pp. 1011-1023.
Acrobat file

Multiprocessor equipment is cheap and ubiquitous now, but users of description logic (DL) reasoners have to face the awkward fact that the major tableau-based DL reasoners can make use only one of the available processors. Recently, researchers have started investigating how concurrent computing can play a role in tableau-based DL reasoning with the intention of fully exploiting the processing resources of multiprocessor computers. The published research mostly focuses on utilizing disjunctive branches, the or-part of tableau expansion trees. We investigated the possibility and the role of concurrently processing conjunctive branches, the and-part of tableau expansion trees. In this work, we present an algorithm to process conjunctive branches in parallel and address the key implementation aspects of the algorithm. A research prototype to execute this algorithm has been developed and empirically evaluated. The experimental results are presented and analyzed. We found that parallelizing the processing of conjunctive branches of tableau expansion trees is auspicious and can partly evolve into a scalable solution for DL reasoning.


2012


When Mommy Blogs are Semantically Tagged

Jinan El-Hachem, Volker Haarslev

Proceedings of the 2nd Joint International Semantic Technology Conference (JIST), Dec. 2 - 4, 2012, Nara, Japan, pp. 313-318.
Acrobat file (preprint)

OWL 2-supported Semantic Tagging is a non compulsory yet decisive and highly influential component of a multidisciplinary knowledge architecture framework which synergetically combines the Semantic and the Social Webs. The facility consists of a semantic tagging layer based on OWL 2 axioms and expressions enticing social network users, typically mommy bloggers, to annotate their chaos of textual data with natural language verbalized versions of ontological elements. This paper provides a comprehensive short summary of the overall framework along with its backbone metamodel and its parenting analysis and surveillance ontology ParOnt, laying a particular emphasis on its semantic expression-based tagging feature, and accordingly highlighting the attained gains and improvements in terms of effective results, services and recommendations, all falling in the scope of public parenting orientation and awareness.


An OWL 2-Based Knowledge Platform Combining the Social and Semantic Webs for an Ambient Childhood Obesity Prevention System

Jinan El-Hachem, Arash Shaban-Nejad, Volker Haarslev, Laurette Dubé, David L. Buckeridge Microsoft Word - ANT_122_El-hachem

Proceedings of the 3rd International Conference on Ambient Systems, Networks and Technologies (ANT), Aug. 27-29, 2012, Niagara Falls, Ontario, Canada, Procedia Computer Science, volume 10, pages 110–119, 2012.
Acrobat file (preprint)

Amid the extremely active Semantic Web community and the Social Web's exceptionally rising popularity, experts believe that an amplified fusion between the two webs will give rise to the next huge advancement in Web intelligence. Such advances can particularly be translated into ambient and ubiquitous systems and applications. In this paper, we delve into the recent advances in knowledge representation, semantic web, natural language processing and online social networking data and concepts, to propose an inclusive platform and framework defining ambient recommender and decision support systems that aim at facilitating cross-sectional analysis of the domain of childhood obesity and generating both generic and customized preventive recommendations.


A Parallel Reasoner for the Description Logic ALC

Kejia Wu, Volker Haarslev 

Proceedings of the 2012 International Workshop on Description Logics (DL-2012), Rome, Italy, June 7-10, 2012, pp. 378-388.
Acrobat file

Multi-processor/core systems have become ubiquitous but the vast majority of OWL reasoners can process ontologies only sequentially. This observation motivates our work on the design and evaluation of Deslog, a parallel tableau-based description logic reasoner for ALC. A first empirical evaluation for TBox classification demonstrates that Deslog's architecture supports a speedup factor that is linear to the number of utilized processors/cores.


Algebraic Reasoning for SHIQ

Laleh Roosta Pour, Volker Haarslev 

Proceedings of the 2012 International Workshop on Description Logics (DL-2012), Rome, Italy, June 7-10, 2012, 530-540.
Acrobat file

We present a hybrid tableau calculus for the description logic SHIQ that decides ABox consistency and uses an algebraic approach for more informed reasoning about qualified number restrictions (QNRs). Benefiting from integer linear programming and several optimization techniques to deal with the interaction of QNRs and inverse roles, our approach provides a more informed calculus. A prototype reasoner based on the hybrid calculus has been implemented that decides concept satisfiability for ALCHIQ. We provide a set of benchmarks that demonstrate the effectiveness of our hybrid reasoner.


Concurrent Classification of OWL Ontologies - An Empirical Evaluation

Mina Aslani, Volker Haarslev 

Proceedings of the 2012 International Workshop on Description Logics (DL-2012), Rome, Italy, June 7-10, 2012, pp. 400-410.
Acrobat file

This paper describes our progress in developing algorithms for concurrent classification of OWL ontologies. We refactored the architecture of our research prototype and its employed algorithms by integrating lock-free data structures and adopting various optimizations to reduce overhead. In comparison to our earlier work we increased the size of classified ontologies by one order of magnitude, i.e., the size of processed ontologies is now beyond a quarter million of OWL classes. The main focus of this paper is an empirical evaluation with huge ontologies that demonstrates an excellent speedup that almost directly corresponds to the number of used processors or cores.


A User and NLP-Assisted Strategic Workflow for a Social Semantic OWL 2-Based Knowledge Platform

Jinan El-Hachem, Volker Haarslev 

Proceedings of the 2012 EACL 2012 Workshop on Semantic Analysis in Social Media at the 13th Conference of the European Chapter of the Association for Computational Linguistics (EACL), April 23-27, Avignon, France, 2012, pp. 37-45.
Acrobat file (preprint)

Originating from a multidisciplinary research project that gathers, around the Semantic Web standards and principles, Social Networking and Natural Language Processing along with some Bioinformatics notions, this paper sheds the light on some of the most critical aspects of the correspondingly adopted framework and real- time knowledge architecture and modeling platform. It recognizes the considerable profits of an appropriate fusion between the aforementioned disciplines, especially via the proper exploitation of OWL 2 (Web Ontology Language) features and novelties, typically OWL 2 language profiles. Accordingly, it proposes a distinctive workflow with well-defined strategies for an ontology-aware user and NLP-assisted flexible and multidimensional approach for the management of the abundantly available Social data. Application scenarios related to awareness and orientation recommender systems based on biomedical domain ontologies for childhood obesity prevention and surveillance are explored as typical proof of concept application areas.


An Enhanced Graph-Oriented Approach for Change Management in Distributed Biomedical Ontologies and Linked Data

Arash Shaban-Nejad, Volker Haarslev

Proc. of the 2011 IEEE International Workshop on Biomedical and Health Informatics (BHI) in BIBM 2011, 12-13 November, 2011, Atlanta, GA, USA, pp. 615-622.
Acrobat file (preprint)

untitled

This paper reports the summary and results of our research on providing a graph oriented formalism to represent, analyze and validate the evolution of bio-ontologies, with emphasis on the FungalWeb Ontology. In this approach Category theory along with rule-based hierarchical distributed (HD) graph transformation have been employed to propose a more specific semantics for analyzing ontological changes and transformations between different versions of an ontology, as well as tracking the effects of a change in different levels of abstractions.


The RacerPro Knowledge Representation and Reasoning System

Volker Haarslev , Kay Hidde, Ralf Möller, Michael Wessel

Semantic Web, Volume 3, No. 3 (2012), pages 267-277.
Acrobat file

RacerPro is a software system for building applications based on ontologies. The backbone of RacerPro is a description logic reasoner. It provides inference services for terminological knowledge as well as for representations of knowledge about individuals. Based on new optimization techniques and techniques that have been developed in the research field of description logics throughout the years, a mature architecture for typical-case reasoning tasks is provided. The system has been used in hundreds of research projects and industrial contexts throughout the last twelve years. W3C standards as well as detailed feedback reports from numerous users have influenced the design of the system architecture in general, and have also shaped the RacerPro knowledge representation and interface languages. With its query and rule languages, RacerPro goes well beyond standard inference services provided by other OWL reasoners.




2011


Automated Reasoning in ALCQ via SMT

Volker Haarslev, Roberto Sebastiani, Michele Vescovi

Proceedings of CADE – the 23rd International Conference on Automated Deduction, Wroclaw, Poland, July 31-Aug. 5, 2011, LNCS, Volume 6803/2011, pp. 283-298.
Acrobat file (preprint)

Reasoning techniques for qualified number restrictions (QNRs) in Description Logics (DLs) have been investigated in the past but they mostly do not make use of the arithmetic knowledge implied by QNRs. In this paper we propose and investigate a novel approach for concept satisfiability in acyclic ALCQ ontologies. It is based on the idea of encoding an ALCQ ontology into a formula in Satisfiability Modulo the Theory of Costs (SMT(C)), which is a specific and computationally much cheaper subcase of Linear Arithmetic under the Integers, and to exploit the power of modern SMT solvers to compute every concept-satisfiability query on a given ontology. We implemented and tested our approach, which includes a very effective individuals-partitioning technique, on a wide set of synthesized benchmark formulas, comparing the approach with the main state-of-the-art DL reasoners available. Our empirical evaluation confirms the potential of the approach.


An Abstract Representation Model for Evolutionary Analysis of Multi-Agent Interactions 

Arash Shaban-Nejad, Volker Haarslev

Proceedings of the IEEE Congress on Evolutionary Computation (IEEE CEC 2011), New Orleans, USA, June 5-8, 2011, pp. 2002-2009.
Acrobat file (preprint)

Intelligent agents are able to assist humans in managing highly dynamic and complex systems in various knowledge intensive domains. The communication between different agents interacting in an integrated multi-agents system can be managed through a set of steering rules, which together form interaction protocols. To support the negotiation, communication and interaction between different intelligent agents, using an appropriate knowledge representation formalism is crucial. This paper introduces the potential of category theory as a formal representation vehicle to facilitate evolutionary analysis of agent interaction and negotiation for managing evolving ontologies in the domain of biomedicine. Utilizing categories supports agents’ communication, negotiation, state transitions, compositions and transformations in different levels of abstractions.


2010


2010 International Workshop on Description Logics (DL2010)

Volker Haarslev,  David Toman, Grant Weddell (editors)

Proceedings of the 2010 International Workshop on Description Logics (DL2010), Waterloo, Ontario, Canada, May 4–7, 2010, 510 pages.
Electronically available as CEUR publication
(Vol-573) here.


Strategic Health Information Management and Forecast: The BirdWatching Approach 

Arash Shaban-Nejad, Volker Haarslev

Proceedings of the 2nd International Conference on Computational Collective Intelligence: Semantic Web, Social Networks & Multi-agent Systems (ICCCI 2010), 10-12 Nov 2010, Taiwan, LNCS Springer, Vol. 6423, pp. 457-468.
Acrobat file (preprint)

To facilitate communication and the exchange of information between patients, nurses, lab technicians, health insurers, physicians, policy makers, and existing knowledge-based systems, a set of shared standard terminologies and controlled vocabularies are necessary. In modern health information management systems, these vocabularies are defined within formal representations called ontologies, where terminologies are only meaningful once linked to a descriptive dataset. When the datasets and their conveyed knowledge are changed, the ontological structure is altered accordingly. Despite the importance of this topic, the problem of managing evolving ontological structures is inadequately addressed by available tools and algorithms, partly because handling ontological change is not a purely computational affair. In this paper, we propose a framework inspired by a social activity, birdwatching. Using this model, the evolving ontological structures can be monitored and analyzed based on their state at a given time. Moreover, patterns of changes can be derived and used to predict and approximate a system’s behavior based on potential future changes.


Parallel TBox Classification in Description Logics - First Experimental Results

Mina Aslani, Volker Haarslev 

Proceedings of the 19th European Conference on Artificial Intelligence - ECAI 2010, Lisbon, Portugal, Aug. 16-20, 2010, pp. 485-490.
Acrobat file (preprint)

One of the most frequently used inference services of description logic reasoners classifies all named classes of OWL ontologies into a subsumption hierarchy. Due to emerging OWL ontologies from the web community consisting of up to hundreds of thousand of named classes and the increasing availability of multi-processor and multi- or many-core computers, we extend our work on parallel TBox  classification and propose a new algorithm that is sound and complete and demonstrates in a first  experimental evaluation a low overhead w.r.t. subsumption tests (less than 3%) if compared with sequential classification.


Optimizing Algebraic Tableau Reasoning for SHOQ: First Experimental Results

Jocelyne FaddoulVolker Haarslev 

Proceedings of the 2010 International Workshop on Description Logics (DL-2010), Waterloo, Canada, May 4-7, 2010, pp. 161-172.
Acrobat file

In this paper we outline an algebraic tableau algorithm for the DL SHOQ, which supports more informed reasoning due to the use of semantic partitioning and integer programming. We introduce novel and adapt known optimization techniques and show their effectiveness on the basis of a prototype reasoner implementing the optimization techniques for the algebraic approach. Our first set of benchmarks clearly indicates the effectiveness of our approach and a comparison with the DL reasoners Pellet and HermiT demonstrates a runtime improvement of several orders of magnitude.


Human Factors in Dynamic E-Health Systems and Digital Libraries 

Arash Shaban-Nejad, Volker Haarslev

Book chapter in Biomedical Knowledge Management: Infrastructures and Processes for E-Health Systems, W. Pease, M. Cooper, R. Gururajan (eds), Information Science Reference, ISR series, IGI Global, 2010, pp. 192-202.
Acrobat file (preprint)

E-health systems and digital libraries deal with human health, requiring fast responses and real-time decision-making. Human intervention can be seen in the whole life cycle of biomedical systems. In fact, relations between patients, nurses, lab technicians, health insurers, and physicians are crucial in such systems, and should be encouraged when necessary. However, there are some issues that affect the successful implementation of such infrastructures. Man-machine interaction problems are not purely computational and need a deep understanding of human behavior. Many integrated health knowledge management systems, have employed various knowledgebases and ontologies as their conceptual backbone to facilitate human-machine communication. Ontologies facilitate sharing knowledge between human and machine; they try to capture knowledge from a domain of interest; when the knowledge changes, the definitions will be altered to provide meaningful and valid information. In this chapter, we review and survey the potential issues related to the human factor in an integrated dynamic e-health system composed of several interrelated knowledgebases, bio-ontologies and digital libraries by looking at different theories in social science, psychology, and cognitive science. We also investigate the potential of some advanced formalisms in the semantic web context such as employing intelligent agents to assist the human user in dealing with changes.


TBox Classification in Parallel: Design and First Evaluation

Mina Aslani, Volker Haarslev 

Proceedings of the 2010 International Workshop on Description Logics (DL-2010), Waterloo, Canada, May 4-7, 2010, pp. 336-347.
Acrobat file

One of the most frequently used inference services of description logic reasoners classifies all named classes of OWL ontologies into a subsumption hierarchy. Due to emerging OWL ontologies from the web community consisting of up to hundreds of thousand of named classes and the increasing availability of multi-processor and multi- or many-core computers, we extend the work on parallel TBox  classification and propose a new algorithm that is sound and complete and demonstrates in a first  experimental evaluation a low overhead in the number of subsumption tests due to parallel execution.


Algebraic Tableau Reasoning for the Description Logic SHOQ

Jocelyne Faddoul, Volker Haarslev

Journal of Applied Logic, Special Issue on Hybrid Logics, Volume 8, Issue 4, December 2010, pp. 334-355 (doi:10.1016/j.jal.2010.08.009).
Acrobat file (preprint)

Semantic web applications based on the web ontology language (OWL) often require the use of numbers in class descriptions for expressing cardinality restrictions on properties or even classes. Some of these cardinalities are specified explicitly but quite a few are entailed and need to be discovered by reasoning procedures. Due to the description logic (DL) foundation of OWL those reasoning services are offered by DL reasoners which employ reasoning procedures that are arithmetically uninformed and substitute arithmetic reasoning by "don't know" non-determinism in order to cover all possible cases. This lack of information about arithmetic problems dramatically degrades the performance of DL reasoners in many cases, especially with ontologies relying on the use of nominals (O) and qualified cardinality restrictions (Q). In this article we present a new algebraic tableau reasoning procedure for the DL SHOQ that combines tableau procedures and algebraic methods, namely linear integer programming, to ensure arithmetically better informed reasoning procedures. SHOQ extends the standard DL ALC (which is equivalent to the multi-modal logic Km) with transitive roles, role hierarchies, qualified cardinality restrictions, and nominals, and forms an expressive subset of the web ontology language OWL 2. Although the proposed algebraic tableau (in analogy to standard tableau) is still double exponential in the worst case, it deals with cardinalities in a very informed way due to its arithmetic component and can be considered as a novel foundation for informed reasoning procedures addressing cardinality restrictions.


Practical Reasoning with Qualified Number Restrictions: A Hybrid Abox Calculus for the Description Logic SHQ

Nasim Farsiniamarj, Volker Haarslev

AI Communications, Special Issue on Practical Aspects of Automated Reasoning, Vol. 23, No. 2-3 (2010), pp. 205-240
Acrobat file (preprint)

This article presents a hybrid Abox tableau calculus for SHQ which extends the basic description logic ALC with role hierarchies, transitive roles, and qualified number restrictions. The prominent feature of our hybrid calculus is that it reduces reasoning about qualified number restrictions to integer linear programming. The calculus decides SHQ Abox consistency w.r.t. a Tbox containing general axioms. The presented approach ensures a more informed calculus which adequately handles the interaction between numerical and logical restrictions in SHQ concept and individual descriptions. A prototype reasoner for deciding ALCHQ concept satisfiability has been implemented.  An empirical evaluation of our hybrid reasoner and its integrated optimization techniques for a set of synthesized benchmarks featuring qualified number restrictions clearly demonstrates the effectiveness of our hybrid calculus.


2009


Tableau-based Reasoning

Ralf Möller, Volker Haarslev 

Book chapter in Handbook on Ontologies, S. Staab, R. Studer (eds), 2nd edition, Springer-Verlag 2009, pp. 509-528.
Acrobat file (preprint)

As part of the infrastructure for working with ontologies, reasoning systems are required. Reasoning is used at ontology development or maintenance time as well as at the time ontologies are used for solving application problems. In this section we will review so-called tableau-based decision procedures for inference problems arising in both contexts. We start with the satisfiability problem for a set of logical formulae. Speaking about ontologies, we focus on description logics, which provide the basis for standardized practical ontology languages. In this context, the set of formulae mentioned above is usually divided into a Tbox and an Abox for the intensional and extensional part of the ontology, respectively. For introductory purposes, here we focus on satisfiability checking in basic description logics, however.


Bio-medical Ontologies Maintenance and Change Management

Arash Shaban-Nejad, Volker Haarslev

Book chapter in Biomedical Data and Applications, A.S. Sidhu, T.S. Dillon (eds), Studies in Computational Intelligence, vol.  224, Springer-Verlag 2009, pp. 143-168.
Acrobat file (preprint)

Things change. Words change, meanings and context change. To manage a large volume of evolving bio-medical data of various types, one needs to employ several techniques from areas such as knowledge representation, semantic web and databases. Many of these techniques require a formal description of a part of the real world. Ontologies can provide a set  of shared and precisely defined terms in various degrees of formality to describe a particular domain of interest. When the knowledge changes, then the related definitions will be altered. Changes to ontologies may occur for many reasons. The issues arising from ontological change can affect the validity of information in applications that are tightly bound to concepts in a particular ontological context. Many knowledge-based systems are now reaching a stage where they need a change management strategy to update their ontological knowledge. This area is becoming increasingly important in science as high throughput techniques frequently necessitate updates to existing scientific ’truths’. In this chapter, we survey and review state of the art change management in bio-ontologies as well as some of the available tools and techniques in this area. We also survey various potential changes in biomedical ontologies, with actual examples from some of the most popular ontologies in the biomedical domain. In addition we investigate the potential of some of the advanced formalisms in this context by proposing our formal method for analyzing and supporting ontology evolution and change management.


Expressive Description Logics via SAT: The Story so Far

Francis Gasse, Volker Haarslev 

Proceedings of the 7th International Workshop on Satisfiability Modulo Theories (SMT 2009), CADE 2009 Workshop, Montreal, Canada, Aug. 2-3, 2009.
Acrobat file

The Boolean Satisfiability (SAT) problem is widely researched and the performance of such solvers largely benefits from it. Satisfiability Modulo Theory (SMT) solvers aim to leverage the good performance toward other formalisms with large propositional content.  Description logics are an expressive subset of first-order logic with high complexity reasoning that could benefit from this approach.  In this paper, we present a SMT-based description logic reasoner, its reasoning techniques, architecture, and some first experimental results. 


Optimizing Reasoning with Qualified Number Restrictions in SHQ

Nasim Farsiniamarj, Volker Haarslev

Proceedings of the 2009 International Workshop on Description Logics (DL-2009), Oxford, United Kingdom, July 27–30, 2009.
Acrobat file

We present a hybrid Abox tableau calculus for SHQ which extends the basic description logic ALC with role hierarchies, transitive roles, and qualified number restrictions. The prominent feature of our hybrid calculus is that it reduces reasoning about qualified number restrictions to integer linear programming. The calculus decides SHQ Abox consistency w.r.t. a Tbox containing general axioms. The presented approach ensures a more informed calculus which adequately handles the interaction between numerical and logical restrictions in SHQ concept and individual descriptions. A prototype reasoner for deciding ALCHQ concept satisfiability has been implemented.  An empirical evaluation of our hybrid reasoner and its integrated optimization techniques for a set of synthesized benchmarks featuring qualified number restrictions clearly demonstrates the effectiveness of our hybrid calculus.


Semantic Web Uncertainty Management

Volker Haarslev, Hsueh-Ieng Pai, Nematollaah Shiri

Encyclopedia of Information Science & Technology, 2nd edition, IGI Global, 2009, pp. 3439-3444.
Acrobat file (preprint)


Algebraic Tableau Algorithm for ALCOQ

Jocelyne Faddoul, Volker Haarslev, Ralf Möller

Proceedings of the 2009 International Workshop on Description Logics (DL-2009), Oxford, United Kingdom, July 27–30, 2009.
Acrobat file

Semantic web applications based on OWL ontologies often require the use of numbers in class descriptions for expressing cardinality restrictions on properties or even classes. Most of these cardinalities are specified explicitly but quite a few are entailed and need to be discovered by reasoning procedures. Due to the description logic (DL) foundation of OWL those reasoning services are offered by DL reasoners which deal with these numbers in a completely uninformed way causing a severe performance degradation in many cases. In this contribution we show how one can extend a standard DL reasoning algorithm with an algebraic component and still maintain termination, soundness and completeness. The result is a hybrid tableau algorithm which deals with cardinalities in a very informed way and can be considered as a novel foundation for more informed reasoning procedures addressing cardinality restrictions.


A Formal Framework for Description Logics with Uncertainty

Volker Haarslev, Hsueh-Ieng Pai, Nematollaah Shiri

International Journal of Approximate Reasoning, Vol. 50, No. 9 (Nov. 2009), pp. 1399-1415.
Acrobat file (preprint)

Description Logics (DLs) play an important role in the Semantic Web as the foundation of ontology language OWL DL. On the other hand, uncertainty is a form of deficiency or imperfection commonly found in real-world information/data. In this paper, we present a framework for knowledge bases with uncertainty expressed in the Description Logic ALCu, which is a propositionally complete representation language providing conjunction, disjunction, existential and universal quantifications, and full negation. The proposed framework is equipped with a constraint-based reasoning procedure that derives a collection of assertions as well as a set of linear/nonlinear constraints that encode the semantics of the uncertainty knowledge base. The interesting feature of our approach is that, by simply tuning the combination functions that generate the constraints, different notions of uncertainty can be modeled and reasoned with, using a single reasoning procedure. We establish soundness, completeness, and termination of the reasoning procedure. Detailed explanations and examples are included to describe the proposed completion rules.


Managing Requirement Volatility in an Ontology-Driven Clinical LIMS Using Category Theory

Arash Shaban-Nejad, Olga Ormandjieva, Mohamad Kassab, Volker Haarslev

International Journal of Telemedicine and Applications, Volume 2009, Article ID 917826, 14 pages, PubMed ID: 19343191, March 2009.
Acrobat file

Requirement volatility is an issue in software engineering in general, and in Web-based clinical applications in particular, which often originates from an incomplete knowledge of the domain of interest. With advances in the health science, many features and functionalities need to be added to, or removed from, existing software applications in the biomedical domain. At the same time, the increasing complexity of biomedical systems makes them more difficult to understand, and consequently it is more difficult to define their requirements, which contributes considerably to their volatility. In this paper, we present a novel agent-based approach for analyzing and managing volatile and dynamic requirements in an ontology-driven laboratory information management system (LIMS) designed for Web-based case reporting in medical mycology. The proposed framework is empowered with ontologies and formalized using category theory to provide a deep and common understanding of the functional and nonfunctional requirement hierarchies and their interrelations, and to trace the effects of a change on the conceptual framework.


An Empirical Comparison of Ontology Matching Techniques

Ahmed Alasoud, Volker Haarslev, Nematollaah Shiri

Journal of Information Science, 35 (4) 2009, pp. 379-397.
Acrobat file (preprint)

Ontology matching aims to find semantic correspondences between a pair of input ontologies. A number of matching techniques have been proposed recently, however, we may benefit more from a combination of such techniques as opposed to just a single method. This is more appropriate, but very often the user has no prior knowledge about which technique is more suitable for the task at hand.  However, it remains a labour intensive and expensive task to perform. Further, the complexity of the matching process as well as the quality of the result is affected by the choice of the applied matching techniques. We study this problem and propose a framework for finding suitable matches.  A main feature of this is that it improves the structure matching techniques and the end result accordingly.  We have developed a running prototype of the proposed framework and conducted experiments to compare our results with existing techniques. While being comparable in efficiency, the experimental results indicate our proposed technique produces better quality matches.


2008


Ontological Approach for the Semantic Recovery of Traceability Links between Software Artifacts

Yonggang Zhang, René Witte, Jürgen Rilling, Volker Haarslev 

IET Software (Special Issue on Language Engineering), Vol. 2, No. 3, June 2008, pp. 185-203.
Acrobat file (preprint)

Traceability links provide support for software engineers in understanding relations and dependencies among software artefacts created during the software development process. The authors focus on re-establishing traceability links between existing source code and documentation to support software maintenance. They present a novel approach that addresses this issue by creating formal ontological representations for both documentation and source code artefacts. Their approach recovers traceability links at the semantic level, utilising structural and semantic information found in various software artefacts. These linked ontologies are supported by ontology reasoners to allow the inference of implicit relations among these software artefacts.


Hybrid Reasoning for Description Logics with Nominals and Qualified Number Restrictions

Jocelyne Faddoul, Volker Haarslev, Ralf Möller

Technical report, Institute for Software Systems (STS), Hamburg University of Technology, Germany, 2008, 29 pages. See also http://www.sts.tu-harburg.de/tech-reports/papers.html.
Acrobat file

Semantic web applications based on OWL ontologies often require the use of numbers in class descriptions for expressing cardinality restrictions on properties or even classes. Most of these cardinalities are specified explicitly but quite a few are entailed and need to be discovered by reasoning procedures. Due to the description logic (DL) foundation of OWL those reasoning services are offered by DL reasoners which deal with these numbers in a completely uninformed way causing a severe performance degradation in many cases. The focus of our research is to design a more informed reasoning algorithm to efficiently handle reasoning with nominals and number restrictions in Description Logic. We do this using a hybrid reasoning approach where we combine tableau-based reasoning with arithmetic reasoning. In this report we extend a standard DL reasoning algorithm with an arithmetic component for the logic ALCOQ which extends the basic DL ALC with nominals (or enumerated classes) and qualified cardinality restrictions on properties and forms a basic subset of OWL 2. The proposed hybrid tableau algorithm deals with cardinalities in a very informed way due to its arithmetic component and can be considered as a novel foundation for better optimized reasoning procedures addressing cardinality restrictions.


On the Scalability of Description Logic Instance Retrieval

Volker Haarslev, Ralf Möller 

Journal of Automated Reasoning, Vol. 41, No. 2, Aug. 2008, pp. 99-142.
Acrobat file (Preprint)

Practical description logic systems play an ever-growing role for knowledge representation and reasoning research even in distributed environments. In particular, the ontology layer of the often-discussed semantic web is based on description logics (DLs) and defines important challenges for current system implementations. The article introduces and evaluates optimization techniques for the instance retrieval problem w.r.t. the description logic SHIQ(Dn)-, which covers large parts of the Web Ontology Language (OWL). We demonstrate that sound and complete query engines for OWL-DL can be built for practically significant query classes. Experience with ontologies derived from database content has shown that it is often necessary to effectively solve instance retrieval problems with respect to huge amounts of data descriptions that make up major parts of ontologies. We present and analyze the main results about how to address this kind of scalability problem.


Uncertainty Reasoning for Ontologies with General TBoxes in Description Logic

Volker Haarslev, Hsueh-Ieng Pai, Nematollaah Shiri

Uncertainty Reasoning for the Semantic Web I, ISWC International Workshops, URSW 2005-2007, Revised Selected and Invited Papers, LNCS, Vol. 5327, Springer-Verlag, 2008, pp. 385-402.
Acrobat file

We present a reasoning procedure for ontologies with uncertainty described in Description Logic (DL) which include General TBoxes, i.e., include cycles and General Concept Inclusions (GCIs). For this, we consider the description language ALCu, in which uncertainty parameters are associated with ABoxes and TBoxes, and which allows General TBoxes. Using this language as a basis, we then present a tableau algorithm which encodes the semantics of the input knowledge base as a set of assertions and linear and/or nonlinear arithmetic constraints on certainty variables. By tuning the uncertainty parameters in the knowledge base, different notions of uncertainty can be modeled and reasoned with, within the same framework. Our reasoning procedure is deterministic, and hence avoids possible empirical intractability in standard DL with General TBoxes. We further illustrate the need for blocking when reasoning with General TBoxes in the context of ALCu.


Ontology-inferred phylogeny reconstruction for analyzing the evolutionary relationships between species: Ontological inference versus cladistics 

Arash Shaban-Nejad, Volker Haarslev

Proceedings of the 8th IEEE International Conference on Bioinformatics and Bioengineering, BIBE 2008, Oct. 8-10, 2008, Athens, Greece, IEEE, 2008, pp. 1-7.
Acrobat file

We propose the use of formal ontological inferencing, rather than cladistics, to reconstruct phylogeny trees and to analyze the evolutionary relationships between species. For this experiment, we focused on the phylogeny of fungi. Lexical chaining technique has been used for incremental population of evolving ontological elements. Also category theory has been employed to provide an underlying formalism for capturing and analyzing the evolutionary behavior of the system.


An ontology-empowered model for annotating protein-protein interaction data: a case study for budding yeast 

Arash Shaban-Nejad, Volker Haarslev

Proceedings of the IEEE International Conference on Information Reuse and Integration, IRI 2008, 13-15 July 2008, Las Vegas, Nevada, USA, IEEE Systems, Man, and Cybernetics Society, 2008, pp. 357-362.
Acrobat file

This paper reports on our experience in modeling and employing ontology-inferred knowledge to support and improve data mining tasks of yeast protein interactions for knowledge discovery. This objective has been accomplished by providing simplified access to units of intersecting proteome data and information from different biological databases and bio-ontologies, and utilizing a logical framework to answer questions from biologists.


Web-based dynamic learning through lexical chaining: a step forward towards knowledge-driven education 

Arash Shaban-Nejad, Volker Haarslev

Proceedings of the 13th Annual SIGCSE Conference on Innovation and  Technology in Computer Science Education, ITiCSE 2008, Madrid, Spain, June 30 - July 2, ACM  Press, 2008, pp. 375.
Acrobat file

In this paper we report on our experience using a linguistic technique, called lexical chaining, in assisting the dynamic hierarchical learning of sequentially accessible information for both human and software agents.


A Hybrid Tableau Algorithm for ALCQ

Jocelyne Faddoul, Nasim Farsinia, Volker Haarslev, Ralf Möller

Proceedings of the 18th European Conference on Artificial Intelligence (ECAI 2008), Patras, Greece, July 21-25, 2008, pp. 725-726.
Acrobat file

We propose an approach for extending a tableau-basedsatisfiability algorithm by an arithmetic component. The result is a hybrid concept satisfiability algorithm for the Description Logic (DL) ALCQ which extends ALC with qualified number restrictions. The hybrid approach ensures a more informed calculus which, on the one hand, adequately handles the interaction between numerical and logical restrictions  of descriptions, and on the other hand, when applied is a very promising framework for average case optimizations.


The revival of structural subsumption in tableau-based reasoners

Volker Haarslev, Ralf Möller, Sebastian Wandelt 

Proceedings of the 2008 International Workshop on Description Logics (DL-2008), Dresden, Germany, May 13–16, 2008.
Acrobat file

The paper summarizes our experiences with optimization techniques for well-known tableau-based description logic reasoning systems, and analyzes the performance of very simple techniques to cope with Tboxes whose bulk axioms just use a less expressive language such as ELH, whereas some small parts of the Tbox use a language as expressive as SHIQ. The techniques analyzed in this paper have been tested with RacerPro, but they can be embedded into other tableau-based reasoners such as, e.g., Fact++ or Pellet in a seamless way.


Planning of Axiom Absorption

Jiewen Wu, Volker Haarslev 

Proceedings of the 2008 International Workshop on Description Logics (DL-2008), Dresden, Germany, May 13-16, 2008.
Acrobat file

Absorptions are generally employed in Description Logics (DL) reasoners in a uniform way regardless of the structure of an input knowledge base. In this paper we present an approach to encode some state-of-the-art absorption techniques into a state space planner, aiming to achieve a better solution. The planner applies appropriate operators to general axioms and produces a solution with a minimized cost to automatically organize these absorptions in a certain sequence to facilitate DL reasoning. Compared to predetermined or fixed applications of established absorptions, such a solution is more flexible and probable to absorb more general axioms into an unfoldable TBox.


Towards Parallel Classifcation of TBoxes

Mina Aslani, Volker Haarslev 

Proceedings of the 2008 International Workshop on Description Logics (DL-2008), Dresden, Germany, May 13-16, 2008.
Acrobat file

One of the most frequently used inference services of description logic reasoners is the classification of TBoxes with a subsumption hierarchy of all named concepts as the result. In response to (i) emerging TBoxes from the semantic web community consisting of up to hundreds of thousand of named concepts and (ii) the increasing availability of multi-processor and multi- or many-core computers, we propose a parallel approach for TBox classification. First experiments on parallelizing well-known algorithms for TBox classification were conducted to study the trade-off between incompleteness and speed improvement. 


Rewriting Rules into SROIQ Axioms

Francis Gasse, Ulrike Sattler, Volker Haarslev 

Proceedings of the 2008 International Workshop on Description Logics (DL-2008), Dresden, Germany, May 13-16, 2008.
Acrobat file

Description Logics are a family of very expressive logics but some forms of knowledge are much more intuitive to formulate otherwise, say, as rules. Rules in DL can be dealt with two approaches: (i) use rules as they are knowing that it leads to undecidability. (ii) or make the rules DL-safe, which will restrict their semantic impact and, e.g., loose the nice ”car owners are engine owners” inference. Here, we offer a third possibility: we rewrite the rule, if it satisfies certain restrictions, into a set of axioms which preserves the nice inferences. In this paper, we describe the rewriting technique and prove that it does really preserve the semantics of the rule. We have implemented the rewriting algorithm and have practical results. 


A Hybrid Tableau Algorithm for ALCQ

Jocelyne Faddoul, Nasim Farsinia, Volker Haarslev, Ralf Möller

Proceedings of the 2008 International Workshop on Description Logics (DL-2008), Dresden, Germany, May 13-16, 2008.
Acrobat file

We propose an approach for extending a tableau-based satisfiability algorithm by an arithmetic component. The result is a hybrid satisfiability algorithm for the Description Logic ALCQ which extends ALC with qualified number restrictions. The hybrid approach ensures a more informed calculus which, on the one hand, adequately handles the interaction between numerical and logical restrictions of descriptions, and on the other hand, when applied is a very promising framework for average case optimizations.


An Effective Ontology Matching Technique

Ahmed Alasoud, Volker Haarslev, Nematollaah Shiri

Proceedings of 17th International Symposium on Methodologies for Intelligent Systems (ISMIS'08), Toronto, Canada, May 20-23, LNAI, Volume 4994, Springer-Verlag, 2008, pp. 585-590.
Acrobat file

In this paper, we study the ontology matching problem and propose an algorithm, which uses as a backbone a multi-level matching technique and performs a neighbor search to find the correspondences between the entities in the given ontologies. A main feature of this algorithm is the high quality of the matches it finds. Besides, as the result of the initial search introduced, our algorithm converges fast, making it comparable to existing techniques.


DLRule: A Rule Editor plug-in for Protégé

Francis Gasse, Volker Haarslev 

Proceedings of the Fourth International Workshop on OWL: Experiences and Directions (OWLED 2008), Washington, DC, USA, April 1-2, 2008.
Acrobat file

OWL is a very expressive language, but some user obviously struggle to formulate what they want to say. Now, some of these users may find it easier to write down a SWRL rule instead of an OWL axiom. Hence, we present a rule editor plug-in for Protégé that brings something different to rule and OWL integration. We part from the two usual approaches: (i) use it as is with say, Hoolet, knowing that it leads to undecidability. (ii) Or make it DL-safe, but then it restricts the semantic impact and, e.g., looses the nice “car owners are engine owners” inference. This plug-in implements a rewriting technique that rewrites certain forms of rules into DL axioms using OWL 1.1’s new features. These rules rewritten as OWL 1.1 axioms do not require DL-safety, thus allow the extra inferences, and do not cause any undecidability. In this paper, we outline the rewriting technique, present the plug-in and give some practical results. 


Incremental Biomedical Ontology Change Management through Learning Agents

Arash Shaban-Nejad, Volker Haarslev

Proceedings of the 2nd KES International Symposium on Agent and Multi-Agent Systems: Technologies and Applications, Incheon, Korea, March 26-28, 2008, LNCS 4953, Springer-Verlag, pp. 526-535.
Acrobat file

Biomedical knowledge bases and ontologies constantly evolve to update the knowledge in the domain of interest. One problem in current change management methodologies is the over-reliance on human factors. Despite the advantages of human intervention in the process of ontology maintenance, including a relative increase of the overall rationality of the system, it does not guarantee reproducible results of a change. To overcome this issue, we propose using intelligent agents to discover and learn patterns for different changes and their consequences. In this paper, we present a novel multi-agent-based approach, to manage the evolving structure of biomedical ontologies. This framework aims to assist and guide ontology engineers through the change management process in general, and aids in tracking and representing the changes, particularly through the use of category theory. It provides an efficient way to automatically capture, validate, and implement a change. 


2007


Resolving Quantifier and Number Restriction to Question OWL Ontologies

Shamima Mithun, Leila Kosseim, Volker Haarslev

Proceeding of the The First International Workshop on Question Answering (QA2007) associated with the Third \International Conference on Semantics, Knowledge, and Grid (SKG'07), Oct. 29-31, 2007, Xi'an, China, IEEE, 218-223.
Acrobat file

This paper describes an approach to resolve quantifiers and number restrictions in natural language questions to query ontologies. Incorporating this feature enables natural language query interfaces to capture a wider range of user queries. To deal with quantifiers and number restrictions, we analyzed a corpus of such questions and derived constraints at the syntactic level to recognize and parse them. The approach was implemented and evaluated through a system called ONLI+. Our method has been evaluated by conducting different experiments using the mean reciprocal rank (MRR) measure. Experimental results show that this feature has been incorporated into ONLI+ without degrading its performance in terms of transforming natural language queries into the nRQL queries, but definitely increases the expressivity of the user. To the best of our knowledge no other natural language interface to query ontologies can deal with quantifiers and number restrictions.


2007 International Workshop on Description Logics (DL2007)

Diego Calvanese, Enrico Franconi, Volker Haarslev,  Domenico Lembo, Boris Motik, Anni-Yasmin Turhan, Sergio Tessaris (editors)

Proceedings of the 2007 International Workshop on Description Logics (DL2007), Brixen-Bressanone, near Bozen-Bolzano, Italy, June 8-10, 2007, 558 pages.
Electronically available as CEUR publication
(Vol-250) here.


Towards a framework for requirement change management in healthcare software applications 

Arash Shaban-Nejad, Volker Haarslev

Companion to the 22nd Annual ACM SIGPLAN Conference on Object-Oriented Programming, Systems, Languages, and Applications, OOPSLA 2007, October 21-25, 2007, Montreal, Quebec, Canada, ACM Press, pp. 807-808.
Acrobat file

Requirements volatility is an issue in software development life cycle which often originated from our incomplete knowledge about the domain of interest. In this paper, we propose an agent-based approach to manage evolving requirements in biomedical software applications using an integrated ontology-driven framework.


FungalWeb: A semantic web for exploring knowledge-based bioinformatics

G. Butler, V. Haarslev, C.J.O. Baker, S. Bergler, L. Kosseim, D. Precup, J. Powlowski, N. Shiri, A. Tsang

Proceedings of NETTAB 2007: A Semantic Web for Bioinformatics: Goals, Tools, Systems, Applications, June 12-15, 2007, University of Pisa, Italy.
Acrobat file (slides)

The FungalWeb project is exploring the application of ontologies, the semantic web, and intelligent agents to the field of fungal genomics, enzymology, and industrial applications of enzymes. Results: We have developed (i) a data warehouse of fungal genomes, genes, proteins and enzymes with their features and classification terms in EC, GO, InterPro, and KEGG; with mappings between the classification schemes; and homology information for proteins; (ii) a formal ontology in OWL integrating the above concepts, with additional concepts on small molecules and taxonomy, and on commercial vendors, products, and applications; (iii) a suite of Java tools for probabilistic relational models with an application to inferring gene regulation from microarray data, binding sites, and functional annotation; (iv) tools for extracting relevant paragraphs of the scientific literature on enzymes; and (v) several application scenarios for FungalWeb. Conclusions: Engineering ontologies for biomedical applications is a diffcult, iterative process. Ontologies do support data integration and can support user-friendly query interfaces which hide the underlying formal query languages. Our current work on information extraction from the literature is investigating the role of ontologies.


The Ecology of Ontologies in the Public Domain

Christopher J. O. Baker, Robert H.Warren, Volker Haarslev, Greg Butler

Monist, 90(4), 17 pages.
Acrobat file (Preprint)

In order to characterize the proliferation of ontologies in the public domain we conducted a study to assess and review the general characteristics of existing OWL ontologies paying attention to features such as their abundance, continuing availability, originating sources and domain covered. Our long-term goal is to evaluate ontologies in light of their suitability for reasoning that yields non-obvious insight or new knowledge in the corresponding domain. The next section discusses criteria and related work for ontology evaluation. We then report on the findings from our survey of ontologies in the public domain and on their domain dependent and domain independent features. The paper concludes with a summary and an outlook on future research.


A Procedure for Description Logic ALCFI

Yu Ding, Volker Haarslev 

Proceedings of TABLEAUX'2007, International Conference, Automated Reasoning with Analytic Tableaux and  Related Methods, Aix en Provence, France, 3-6 July 2007.
Acrobat file

A combination of inverse roles and functional restrictions makes the underlying description logics (DLs) lose the finite model property. Consequently, sophisticated cycle detection and termination mechanisms are employed to terminate searching of models that potentially admit only an infinite domain. In this paper, we study the logic ALCFI and present a tableau-based decision procedure that uses only a static termination condition. To achieve this nice property, a preprocessing step is to be performed to convert a source problem to a target problem. This conversion preserves equisatisfiability. As a consequence of this conversion, the tableau-based decision procedure for the concept satisfiability test w.r.t. a set of general concept inclusions (a.k.a. general axioms) is ExpTime for ALCFI.


Categorical Representation of Evolving Structure of an Ontology for Clinical Fungus

Arash Shaban-Nejad, Volker Haarslev

Proceedings of the 11th Conference on Artificial Intelligence in Medicine (AIME 07), July 7-11, Amsterdam, The Netherlands, 2007, LNCS 4594, Springer-Verlag, pp. 277-286.
Acrobat file

With increasing popularity of using ontologies, many industrial and clinical applications have employed ontologies as their conceptual backbone. Ontologies try to capture knowledge from a domain of interest and when the knowledge changes, the definitions will be altered. We study change management in the FungalWeb Ontology, which is the result of integrating numerous biological databases and web accessible textual resources. The fungal taxonomy is currently unstable and evolves over time.  This evolution can be seen in both nomenclature and the taxonomic structure. In an experiment we have focused on changes in medical species of fungus which can potentially alter the related disease name and description in an integrated clinical system. In order to address certain aspects of representation of changes in an ontology driven clinical application we propose a methodology based on category theory as a mathematical notation, which is independent of a specific choice of ontology language and any particular implementation. 


Managing Conceptual Revisions in a Temporal Fungal Taxonomy 

Arash Shaban-Nejad, Volker Haarslev

Proceedings of the 20th IEEE International Symposium on Computer-Based Medical Systems, June 20-22, 2007, Maribor, Slovenia, IEEE Press, pp. 624-632.
Acrobat file

Representing and Reasoning about time and change is one of the primary issues in the area of Artificial Intelligence (AI) and Knowledge Representation (KR). Despite the importance of time and change in ontology change management process, current ontology researches are based on time- independent models. One of the reasons is that considering time in ontologies can increase the complexity and a comprehensive and very expressive ontology language is needed to represent it. In this paper we propose using state space model along with category theory as a mathematical notation, which is independent of a specific choice of ontology language and any particular implementation to analyze and represent temporal ontological models in the domain of biomedical applications.


OntoVQL: A Graphical Query Language for OWL Ontologies

Amineh Fadhil, Volker Haarslev 

Proceedings of the 2007 International Workshop on Description Logics (DL-2007), Brixen-Bressanone, near Bozen-Bolzano, Italy, 8–10 June, 2007, pp. 267-274.
Acrobat file

The database usability experience has shown that visual query languages tend to be superior to textual languages in many aspects.  By applying this principle in the context of ontologies, we present OntoVQL, a graphical query language for OWL-DL ontologies.  OntoVQL maps diagrammatic queries to DL based query languages such as nRQL, which is offered by the OWL-DL reasoner Racer.  OntoVQL hides the complexity of the DL query language from users and allows them to query OWL ontologies with less difficulty.  A visual query system equipped with this language has been implemented and is now available.  This tool enables users to formulate queries incrementally by having more than one query simultaneously available for getting combined or broken down into new queries.  Giving instant feedback in the form of result cardinality is another important feature of the tool that helps guiding users into building meaningful queries. 


A New Mapping from ALCI to ALC

Yu Ding, Volker Haarslev, Jiewen Wu

Proceedings of the 2007 International Workshop on Description Logics (DL-2007), Brixen-Bressanone, near Bozen-Bolzano, Italy, 8–10 June, 2007, pp. 53-64.
Acrobat file

This paper studies a technique for mapping ALCI knowledge bases into ALC. By applying this mapping, a tableau-based reasoner succeeds in solving some very hard real-world problems. Worst-case optimal tableau-based procedures for the concept satisfiability and Abox consistency problem are available through such a mapping.


An ExpTime Tableau-based Decision Procedure for ALCQI

Yu Ding, Volker Haarslev 

Proceedings of the 2007 International Workshop on Description Logics (DL-2007), Brixen-Bressanone, near Bozen-Bolzano, Italy, 8–10 June, 2007, pp. 531-532.
Acrobat file

Firstly, we confirm that the algebraic method in general, according to the well-known result on integer linear programming, leads to a worst-case ExpTime tableau-based decision procedure for the concept satisfiability problem. Secondly, we extend the algebraic method to DLs with inverse roles.


Optimizing Tableau Reasoning in ALC Extended with Uncertainty

Volker Haarslev, Hsueh-Ieng Pai, Nematollaah Shiri

Proceedings of the 2007 International Workshop on Description Logics (DL-2007), Brixen-Bressanone, near Bozen-Bolzano, Italy, 8–10 June, 2007, pp. 307-314.
Acrobat file

There has been an increased interest in recent years to incorporate uncertainty in Description Logics (DLs), and a number of proposals have been put forward for modeling uncertainty in DL frameworks.  While much progress has been made on syntax, semantics, and query processing issues, optimizing queries in this context has received little attention.  In this paper, we study query processing for a tableau-based DL framework with uncertainty and focus on optimization of resolution of certainty inequality constraints, obtained from a translation in query processing phase.  We develop a running prototype which evaluates DL knowledge bases with ABoxes and TBoxes annotated with uncertainty parameters and computes the corresponding semantics encoded as a set of constraints in the form of linear and/or nonlinear inequations. We also explore various existing and new opportunities for optimizing the reasoning procedure in this context. Our experimental evaluation indicates that the optimization techniques we considered result in improved efficiency significantly.


Measuring Inconsistencies in Ontologies

Xi Deng, Volker Haarslev, Nematollaah Shiri

Proceedings of the 4th European Semantic Web Conference (ESWC 2007), June 3-7, 2007, Innsbruck, Austria, Springer-Verlag, 2007, pp. 326-340.
Acrobat file

In this paper, we propose a novel approach to measure inconsistencies in ontologies based on Shapley values, which are originally proposed for game theory. This measure can be used to identify which axioms in an input ontology or which parts of these axioms need to be removed or modified in order to make the input consistent. We also propose optimization techniques to improve the efficiency of computing Shapley values. The proposed approach is independent of a particular ontology language or a particular reasoning system used. Application of this approach can improve the quality of ontology diagnosis and repair in general.


Using Patterns to Explain Inferences in ALCHI

Xi Deng, Volker Haarslev, Nematollaah Shiri

Computational Intelligence, Volume 23, Number 3, August 2007, pp. 373-392.
Acrobat file

With the increasing number of applications of Description Logics (DLs), unsatisfiable concepts and inconsistent knowledge bases become quite common, especially when the knowledge bases are large and complex. This makes it challenging, even for experienced knowledge engineers, to identify and resolve these unsatisfiabilities and inconsistencies manually. It is thus crucial to provide services to explain how and why a result is derived. Motivated by the possibility of applying resolution technique in first-order logic to construct explanations for Description Logics, we present an algorithm that uses patterns to generate explanations for unsatisfiability and inconsistency reasoning in ALCHI, obtained by extending our previous work on ALC.  The use of resolution proofs to provide explanations for DL reasoners is due to their focus which, through literals involved in the process, contributes directly to the contradiction, hence acting as filters to discard irrelevant information. We also establish the soundness and completeness of the algorithm. The proposed solution approach is independent of the underlying DL reasoners, which suggests its potential application for any DL framework.


Applying OWL Reasoning to Genomic Data

Katherine Wolstencroft, Robert Stevens, Volker Haarslev 

Semantic Web: Revolutionizing Knowledge Discovery in the Life Sciences, Christopher J. O. Baker and Kei-Hoi Cheung, Eds., Springer Verlag, 2007, pp. 225-248 (Chapter 11).
Acrobat file

The core part of the Web Ontology Language (OWL) is based on Description Logic (DL) theory, which has been investigated for more than 20 years. OWL reasoning systems offer various DL-based inference services such as (i) checking class descriptions for consistency and automatically organizing them into classification hierarchies, (ii) checking descriptions about individuals for consistency and recognizing individuals as instances of class descriptions. These classification-based services can be easily utilized in a variety of application domains concerned with representation of and reasoning about knowledge, e.g., biological sciences. Classification is an integral part of all biological sciences, including the new discipline of genomics. Biologists not only wish to build complex descriptions of the categories of biological molecules, but also to classify instances of new molecules against these class level descriptions. In this chapter we introduce to the non-expert reader basics of OWL DL and its related reasoning patterns such as classification. We use a case study of building an ontology of a protein family and then classifying all members of that family from a genome using DL technology. We show how a technically straight-forward use of these technologies can have far-reaching effects in genomic science.


A Unified Ontology-Based Process Model for Software Maintenance and Comprehension

Jürgen Rilling, Yonggang Zhang, Wen Jun Meng, René Witte, Volker Haarslev, Philippe Charland 

Proceedings of the ACM/IEEE 9th International Conference on Model Driven Engineering Languages and Systems (MoDELS/UML 2006), T. Kühne (Ed.), LNCS 4364, Springer-Verlag, pp. 56–65, 2007.
Acrobat file

In this paper, we present a formal process model to support the comprehension and maintenance of software systems. The model provides a formal ontological representation that supports the use of reasoning services across different knowledge resources. In the presented approach, we employ our Description Logic knowledge base to support the maintenance process management, as well as detailed analyses among resources, e.g., the traceability between various software artifacts. The resulting unified process model provides users with active guidance in selecting and utilizing these resources that are context-sensitive to a particular comprehension task. We illustrate both, the technical foundation based on our existing SOUND environment, as well as the general objectives and goals of our process model.


2006


GLOO: A Graphical Query Language for OWL Ontologies

Amineh Fadhil, Volker Haarslev 

Proceedings of the 2006 International Workshop on OWL: Experiences and Directions 2006 (OWLED-2006), Athens, Georgia, USA, Nov. 10-11, 2006.
Acrobat file

The database usability experience has shown that visual query languages tend to be superior to textual languages in many aspects.  By applying this principle in the context of ontologies, we present GLOO, a graphical query language for OWL-DL ontologies.  GLOO maps diagrammatic queries to DL based query languages such as nRQL, which is offered by the OWL-DL reasoner Racer. GLOO hides the complexity of a DL query language from users and allows them to query OWL ontologies with less difficulty.


OntoKBEval: A Support Tool for DL-based Evaluation of OWL Ontologies

Qing Lu, Volker Haarslev 

Proceedings of the 2006 International Workshop on OWL: Experiences and Directions 2006 (OWLED-2006), Athens, Georgia, USA, Nov. 10-11, 2006.
Acrobat file

The Ontology Knowledge Base Evaluation Tool (OntoKBEval) supports users in evaluating ontologies with the help of the OWL-DL reasoner RacerPro. OntoKBEval offers hierarchical diagrams describing the structure of OWL-DL ontologies divided into the description logics view of TBoxes and ABoxes. The three main methods for supporting ontology evaluation are: (i) quick-view (providing a keyword search for interesting concept names), (ii) general (offering a more comprehensive TBox and ABox analysis), (iii) multi-file analysis (offering basic TBox and ABox information for a batch of files). The implementation relies on the OWL-DL reasoner RacerPro to support OWL-DL reasoning functionalities.


On the Scalability of Description Logic Instance Retrieval

Ralf Möller, Volker Haarslev , Michael Wessel

Proceedings of the 29th Annual German Conference on Artificial Intelligence, June 14-19, Bremen, Germany, LNCS, Springer Verlag, 2006, pp. 171-184.
Acrobat file

Although description logic systems can adequately be used for representing and reasoning about underspecified information (e.g., for John we know he is French or Italian), in practical applications it can be assumed that (only) for some tasks the expressivity of description logics really comes into play whereas for building complete applications, it is often necessary to effectively solve instance retrieval problems with respect to largely deterministic knowledge. In this paper we present and analyze the main results we have found about how to contribute to this kind of scalability problem. We assume familiarity with description logics in general and tableau provers in particular.


Ontology-based Program Comprehension Tool Supporting Website Architectural Evolution

Yonggang Zhang, René Witte, Jürgen Rilling, Volker Haarslev 

Proceedings of the 8th IEEE International Symposium on Web Site Evolution (WSE 2006), September 23-24, 2006, Philadelphia, PA, USA, IEEE Computer Society Press, 2006, pp. 41-49.
Acrobat file

A challenge of existing program comprehension approaches is to provide consistent and flexible representations for software systems. Maintainers have to match their mental models with the different representations these tools provide. In this paper, we present a novel approach that addresses this issue by providing a consistent ontological representation for both source code and documentation. The ontological representation unifies information from various sources, and therefore reduces the maintainers’ comprehension efforts. In addition, representing software artifacts in a formal ontology enables maintainers to formulate hypotheses about various properties of software systems. These hypotheses can be validated through an iterative exploration of information derived by our ontology inference engine. The implementation of our approach is presented in detail, and a case study is provided to demonstrate the applicability of our approach during the architectural evolution of a website content management system.


An Ontology-based Approach for Traceability Recovery

Yonggang Zhang, René Witte, Jürgen Rilling, Volker Haarslev 

Proceedings of the 3rd International Workshop on Metamodels, Schemas, Grammars, and Ontologies for Reverse Engineering (ATEM 2006), Genoa, October 1st, 2006, pp.  36-43.
Acrobat file

Traceability links provide support for software engineers in understanding the relations and dependencies among software artifacts created during the software development process. In this research, we focus on re-establishing traceability links between existing source code and documentation to support reverse engineering. We present a novel approach that addresses this issue by creating formal ontological representations for both the documentation and source code artifacts. These representations are then aligned to establish traceability links at the semantic level. Our approach recovers traceability links by utilizing the structural and semantic information in various software artifacts and the linked ontologies are also supported by ontology reasoners to infer implicit relations among these software artifacts.


Tableau Caching for Description Logics with Inverse and Transitive Roles

Yu Ding, Volker Haarslev 

Proceedings of the 2006 International Workshop on Description Logics (DL-2006), Lake District, UK, May 30 - June 1, 2006, pp. 143-149.
Acrobat file

Modern description logic (DL) reasoners are known to be less  efficient for DLs with inverse roles. The current loss of performance  is largely due to the missing applicability of some well-known  optimization techniques, especially the one for caching the  satisfiability status of modal successors. In this paper, we present  a rule synthesis technique from which an estimation of the potential  back-propagation of constraints can be made. This estimation can be  applied to both the concept classifier and the satisfiability tester.  This paper presents a tableau caching technique for SHI  as a first step to improving the performance of tableau-based DL reasoners for logics offering the use of inverse roles. The proposed  techniques underwent a first empirical evaluation with a prototype DL reasoner for SHI using a set of synthetically generated knowledge bases. The initial results indicate a significant improvement in runtime performance once caching is effectively enabled.


High Performance Absorption Algorithms for Terminological Reasoning

Ming Zuo, Volker Haarslev 

Proceedings of the 2006 International Workshop on Description Logics (DL-2006), Lake District, UK, May 30 - June 1, 2006, pp. 159-166.
Acrobat file

When reasoning with description logic (DL) knowledge bases (KBs),  performance is of critical concern in real applications, especially when these KBs contain a large number of axioms. To improve the performance, axiom absorption  has been proven to be one of the most effective optimization techniques. The well-known algorithms for axiom absorption, however, still heavily depend on the order and the format of the  axioms occurring in KBs. In addition, in many cases, there exist some restrictions in these algorithms which prevent axioms from being  absorbed. The design of absorption algorithms for  optimal reasoning is still an open problem. In this paper, we propose some new algorithms to absorb axioms in a KB to improve the reasoning performance. The experimental tests we conducted are mostly based on synthetic benchmarks derived from common cases  found in real KBs. The experimental evaluation demonstrates a significant runtime improvement.


On the Scalability of Description Logic Instance Retrieval

Ralf Möller, Volker Haarslev , Michael Wessel

Proceedings of the 2006 International Workshop on Description Logics (DL-2006), Lake District, UK, May 30 - June 1, 2006, pp. 151-158.
Acrobat file

Although description logic systems can adequately be used for representing and reasoning about underspecified information (e.g., for John we know he is French or Italian), in practical applications it can be assumed that (only) for some tasks the expressivity of description logics really comes into play whereas for building complete applications, it is often necessary to effectively solve instance retrieval problems with respect to largely deterministic knowledge. In this paper we present and analyze the main results we have found about how to contribute to this kind of scalability problem. We assume familiarity with description logics in general and tableau provers in particular.


An ontology based approach to software comprehension - Reasoning about security concerns in source code

Yonggang Zhang,  Juergen Rilling Volker Haarslev 

Proceedings of the 30th Annual International Computer Software and Applications Conference (COMPSAC 2006), IEEE Computer Society Press, 2006, pp. 333-342.
Acrobat file

There exists a large variety of techniques to detect and correct software security vulnerabilities at the source code level, including human code reviews, testing, and static analysis. In this article, we present a static analysis approach that supports both the identification of security flaws and the reasoning about security concerns. We introduce an ontology-based program representation that lets security experts and programmers specify their security concerns as part of the ontology. Within our tool implementation, we support complex queries on the underlying program model using either predefined or user-defined concepts and relations. Queries regarding security concerns, such as exception handling, object accessibility etc. are demonstrated in order to show the applicability and flexibility of our approach.


Semantic Web Infrastructure for Fungal Enzyme Biotechnologists

Christopher J.O. Baker, Arash Shaban-Nejad, Xiao Su, Volker Haarslev, Greg Butler

Journal of Web Semantics, (4)3, 2006, pp. 168-180.
Acrobat file

The FungalWeb Ontology aims to support the data integration needs of enzyme biotechnology from inception to product roll. Serving as a knowledgebase for decision support, the conceptualization seeks to link fungal species with enzymes, enzyme substrates, enzyme classifications, enzyme modifications, enzyme related intellectual property, enzyme retail and applications. The ontology, developed in the OWL language, is the result of the integration of numerous biological database schemas, web accessible text resources and components of existing ontologies. We assess the quantity of implicit knowledge in the Fungal Web ontology by analyzing the range of tags in the OWL files and along with other description logic (DL) computable metrics of the ontology, contrast it with other publicly available bio-ontologies. Thereafter we demonstrate how the FungalWeb Ontology supports its broad remit required in fungal biotechnology by (i) suggesting semantic queries typical of a fungal enzymologist involved in product development, (ii) presenting application scenarios, and (iii) presenting the conceptualizations of the ontological frame able to support these scenarios. Recognizing the complexity of the ontology query process for the non-technical manager we introduce a simplified query tool, Ontologent Interative Query (OntoIQ) that allows the user to browse and build queries from a selection of query patterns. The OntoIQ interface supports users not familiar with writing DL syntax allowing them access to the ontology with expressive description logic and automated reasoning tools. Finally we discuss the challenges encountered during the development of semantic infrastructure for fungal enzyme biotechnologists.


Completion Rules for Uncertainty Reasoning with the Description Logic ALC

Volker Haarslev, Hsueh-Ieng Pai, Nematollaah Shiri

Proceedings of the Canadian Semantic Web Working Symposium, June 6, 2006, Québec City, Québec, Canada, Series: Semantic Web and Beyond: Computing for Human Experience, Vol. 4, Springer Verlag, 2006, pp. 205-225.
Acrobat file

Description Logics (DLs) are gaining more popularity as the foundation of ontology languages for the Semantic Web. On the other hand, uncertainty is a form of deficiency or imperfection commonly found in the real-world information/data. In recent years, there has been an increasing interest in extending the expressive power of DLs to support uncertainty, for which a number of frameworks have been proposed. In this paper, we introduce an extension of DL (ALC) that unifies and/or generalizes a number of existing approaches for DLs with uncertainty. We first provide a classification of the components of existing frameworks for DLs with uncertainty in a generic way. Using this as a basis, we then discuss ways to extend these components with uncertainty, which includes the description language, the knowledge base, and the reasoning services. Detailed explanations and examples are included to describe the proposed completion rules.


Resolution Based Explanations for Reasoning in the Description Logic ALC

Xi Deng, Volker Haarslev, Nematollaah Shiri

Proceedings of the Canadian Semantic Web Working Symposium, June 6, 2006, Québec City, Québec, Canada, Series: Semantic Web and Beyond: Computing for Human Experience, Vol. 4, Springer Verlag, 2006, pp. 189-204.
Acrobat file

With the increasing number of applications of description logics (DLs), unsatisfiable concepts and inconsistent terminologies become quite common, especially when the knowledge bases are large and complex. Even for an experienced knowledge engineer, it can be extremely difficult to identify and resolve the origins of these unsatisfiabilities and inconsistencies. Thus it is crucial to provide services to explain how and why a result is derived. Motivated by the possibilities of applying resolution technique in first-order logic to construct explanations for description logics, we extend our previous work and present an algorithm that generates explanations for unsatisfiability and inconsistency reasoning in the description language ALC. The main advantage of our approach is that it is independent of any specific DL reasoners.


Ontoligent Interactive Query Tool

Christopher J. O. Baker, Xiao Su, Greg Butler, Volker Haarslev

Proceedings of the Canadian Semantic Web Working Symposium, June 6, 2006, Québec City, Québec, Canada, Series: Semantic Web and Beyond: Computing for Human Experience, Vol. 2, Springer Verlag, 2006, pp. 155-169.
Acrobat file

Recognizing the complexity of the Description Logic-based query of OWL-DL ontologies for the non-specialist, we introduce a query tool called Ontoligent Interactive Query (OntoIQ). This tool provides a well-organized user interface for a variety of users, from the beginner to the professional. Users can browse ontologies and build queries using query patterns and ontology content. OntoIQ translates queries automatically into the new RACER Query language (nRQL) syntax and presents them to description logic automated reasoner RACER which returns the query results. The tool includes import and export functions so that queries can be stored, shared, and re-imported by other users. Users are not required to learn the nRQL syntax. OntoIQ software is available for download at the FungalWeb website.


Uncertainty Reasoning in Description Logics: A Generic Approach

Volker Haarslev, Hsueh-Ieng Pai, Nematollaah Shiri

Proceedings of the 19th International FLAIRS Conference, May 11-13, 2006, Melbourne Beach, Florida, USA, AAAI Press, 2006, pp. 818-823.
Acrobat file

Description Logics (DLs) are gaining more popularity as the foundation of ontology languages for the Semantic Web. As most information in real life is imperfect, there has been an increasing interest recently in extending the expressive power of DLs with uncertainty, for which a number of frameworks have been proposed. In this paper, we introduce an extension of DL which unifies and/or generalizes a number of existing approaches for DLs with uncertainty. For this, we first provide a classification of existing frameworks for DLs with uncertainty on the basis of their underlying certainty formalisms. Using this as a basis, we introduce a generic framework for DL with uncertainty by extending components of the DL framework, i.e., the description language, the knowledge base, and the reasoning services.


2005


Visualization of Subsumption Hierarchies in Ontologies

Anis Zarrad, Volker Haarslev

Proceedings of Sciences Electroniques, Technologies de l'Information et des Telecommunications (SETIT) 2005, 27-31 March 2005, ISBN: 9973-51-546-3, 2005.
Acrobat file

The RACER system is a knowledge representation system that implements description logic reasoning. It offers reasoning and evaluation services for multiple concepts (TBox) and multiple individuals (ABox) as well. The RACER system responds to taxonomy queries related to description logic. The body of the response contains information about a relational structure called a concept hierarchy or subsumption hierarchy. In this paper, we propose an efficient algorithm to visualize the concept hierarchies by producing several geometric representations. The display of the concept hierarchy in a single screen has been proven to be useful and helpful for ontology designers. In fact they can easily identify the hidden relations that were discovered during the Tbox classification process


The FungalWeb Ontology: Semantic Web Challenges in Bioinformatics and Genomics

Arash Shaban-Nejad, Christopher J.O. Baker, Volker Haarslev, Greg Butler

Semantic Web Challenge - Proceedings of the 4th International Semantic Web Conference, Nov. 6-10, Galway, Ireland, Springer-Verlag, LNCS, Vol. 3729, 2005, pp. 1063-1066, (2. Prize in the Semantic Web Challenges competition).
Acrobat file

Bioinformatics and genomics cover a wide range of different data formats (i.e. annotations, pathways, structures, sequences) derived from experimental and in-silico biological analysis which are stored, used, and manipulated by scientists and machines. The volume of this data is huge and usually distributed in different locations, and often frequently being updated.
FungalWeb is the first project of its kind in Canada to focus on bringing semantic web technology to genomics. It aimed to bring together available expertise in ontologies, multi-agent systems, machine learning and natural language processing to build a tailored knowledgebase and semantic systems of direct use to the scientific discovery process in the domain of fungal genomics.
We describe the FungalWeb Ontology which is a large-scale integrated bio-ontology in the domain of fungal genomics using state-of-the-art semantic technologies. The ontology provides simplified access to units of intersecting information from different biological databases and existing bio-ontologies. In particular, the FungalWeb ontology is being used as a core for a semantic web system. This system can be used by human, bioinformatics applications or some intelligent systems for ontology-based information retrieval to provide extended interpretations and annotations. 


A Generic Framework for Description Logics with Uncertainty

Volker Haarslev, Hsueh-Ieng Pai, Nematollaah Shiri

Proceedings of the 2005 Workshop on Uncertainty Reasoning for the Semantic Web at the 4th International Semantic Web Conference, Nov. 7, Galway, Ireland, 2005, pp. 77-86.
Acrobat file

We propose an extension to Description Logics (DLs) with uncertainty which unifies and/or generalizes a number of existing frameworks for DLs with uncertainty. To this end, we first give a classification of these frameworks and identify the essential features as well as properties of the various combination functions allowed in the underlying uncertainty formalisms they model. This also allows us express the semantics of the DL elements in a flexible manner. We illustrate how various DLs with uncertainty can be expressed in our generic framework.


A Framework for Explaining Reasoning in Description Logics

Xi Deng, Volker Haarslev, Nematollaah Shiri

Proceedings of the 2005 International Symposium on Explanation-aware Computing, AAAI Fall Symposium - Washington, D.C.,  Nov. 3-6, 2005, AAAI Press, pp. 55-61.
Acrobat file

We present a resolution  based framework to explain reasoning in description logics and demonstrate its applicability to explain unsatisfiability and inconsistency queries w.r.t. TBoxes and ABoxes in ALC. During the construction process, a refutation graph is used as the guide to generate explanations.


Description Logic Inference Technology: Lessions Learned in the Trenches

Volker Haarslev , Ralf Möller, Michael Wessel

Proceedings of the 2005 International Workshop on Description Logics (DL-2005), Edinburgh, Scotland, UK, July 26-28, 2005, pp. 160-167.
Acrobat file

Optimized description logic systems are now available for quite a long time. Whereas initially, to a large extent only T-box reasoning was used in applications, now more and more applications also rely on A-box reasoning. In this article we summarize our experiences with the description logic reasoner Racer and perform an evaluation of the system with respect to instance retrieval benchmarks. In addition, we report on our experiences with two years of user support for OWL knowledge base development and usage. The article provides an overview over the state of the art in description logic inference technology and derives suggestions for future developments.


Towards Efficient Reasoning for Description Logics with Inverse Roles

Yu Ding, Volker Haarslev

Proceedings of the 2005 International Workshop on Description Logics (DL-2005), Edinburgh, Scotland, UK, July 26-28, 2005, 208-215.
Acrobat file

This paper presents a first proposal for improving the efficiency of modern description logic (DL) reasoners that are known to be less efficient for DLs with inverse roles. The current loss of performance is usually caused by the missing applicability of well-known optimization techniques such as caching the satisfiability status of modal successors. In order to improve this situation we propose a first version of a modified tableau algorithm for ALCI that can be considered as a basis for integrating sound caching techniques into modern reasoners supporting DLs with inverse roles.


LAS: Extending Racer by a Large Abox Store

CuiMing Chen, Volker Haarslev, JiaoYue Wang

Proceedings of the 2005 International Workshop on Description Logics (DL-2005), Edinburgh, Scotland, UK, July 26-28, 2005, pp. 200-207.
Acrobat file

Recently, several approaches have been proposed on combining description logic (DL) reasoning with database techniques. In this paper we report on the LAS (Large Abox Store) system extending the DL reasoner Racer with a database used to store and query Tbox and Abox information. LAS stores for given knowledge bases their taxonomy and their complete Abox in its database. The Aboxes may contain role assertions. LAS can answer Tbox and Abox queries by combining SQL queries with DL reasoning. The architecture of LAS is based on merging techniques for so-called individual pseudo models.


A Resolution Based Framework to Explain Reasoning in Description Logics

Xi Deng, Volker Haarslev, Nematollaah Shiri

Proceedings of the 2005 International Workshop on Description Logics (DL-2005), Edinburgh, Scotland, UK, July 26-28, 2005, p. 229.
Acrobat file (Poster)
Acrobat file (Abstract)

As more complicated applications are involved in Description Logics (DL),  it is crucial to develop explanation services for DL reasoners. We propose to use resolution proofs to construct explanations for unsatisfiability and inconsistency reasoning. Our approach is based on the observation that compared to tedious natural deduction proofs, resolution technique is more focused, as all the literals involved in a proof contribute directly to the solution. Besides resolution can easily deal with global axioms and ABoxes which facilitates providing explanations w.r.t. TBoxes and ABoxes.


Fire -- Extending Racer by an Engine for SWRL Rules

Kruthi Bhoopalam, Volker Haarslev

Proceedings of the 2005 International Workshop on Description Logics (DL-2005), Edinburgh, Scotland, UK, July 26-28, 2005, p. 230.
Acrobat file (Poster)
Acrobat file (Abstract)

In this paper we propose the Fire system, a prototype rule engine for reasoning with SWRL (Semantic Web Rules Language) rules and OWL (Ontology Web Language) ontologies. This system is intended as an extension to the reasoning services of the RACER. For ease of implementation, support is currently provided for SWRL rules that are restricted as follows: (i) Rules must be atomic (single atom in the rule consequent); (ii) Rules must have tree-shaped antecedents; (acyclic co-reference graph for antecedent atoms), (iii) Rules must be `strictly Horn' (predicates of rule atoms may only be `name' of property or class); (iv) SWRL built-ins, sameAs, differentFrom or OWL DatatypeProperty may not be used for predicates in rule atoms.


A Hybrid Approach for Ontology Integration

Ahmed Alasoud, Volker Haarslev, Nematollaah Shiri

Proceedings of the 2005 VLDB Workshop on Ontologies-based techniques for DataBases and Information Systems (ODBIS-2005), Trondheim, Norway, Sept. 2, 2005, pp. 18-23.
Acrobat file

The high proliferation of information on the World Wide Web (WWW) has made it necessary to make this huge information not only available to humans, but also to machines. Ontologies are widely being used to enrich the semantics of web, and corresponding technology developed to exploit them. Certainly, extracting information from various ontologies created independently is an important challenge for answering queries from web. In this paper, we propose a framework for ontology integration which is a hybrid of materialized (data warehouse) and virtual views. We have developed a prototype of the proposed framework. While much work is still ahead, our experiments so far indicate that the ideas used in this work are promising which may result in significant theoretical as well as practical contributions.


Applying Semantic Web Technologies to Matchmaking and Web Service Descriptions

Amer Al Shaban, Volker Haarslev

Proceedings of The Montreal Conference on eTechnologies 2005 (MCeTech2005), Jan. 20-21, 2005,
Montreal, Canada, pp. 97-104.
Acrobat file

The recent growth of using agents in representing web services is causing difficulties in finding specific types of services. This problem usually arises because matchmaking techniques for services are often based on string comparison and service providers might neglect to provide enough or appropriate keywords for the matchmaking process. In this paper we report on an approach that makes use of formal ontologies and automated reasoning services in order to improve the matchmaking process. Our approach is based on the Ontology Web Language (OWL), the OWL reasoner Racer, and the agent framework DECAF. Our use of OWL ontologies is two-fold. First, we use ontologies in order to express the particular knowledge of agents. These ontologies are grounded by referring to a so-called common upper ontology providing the necessary glue between the different agent domains. Second, with the help of OWL-S, a standard OWL ontology designed for specifying service descriptions, agents describe formally their offered web services. Our approach depends on a middle-ware agent called matchmaker which will be in charge of matching required services to proper provider agents. Due to the use of OWL ontologies the matchmaking process can be reduced to query processing and ontology reasoning implemented by the Racer system. Our approach has been demonstrated using an e-business scenario, where several buying and selling agents for various products are involved. The communication protocol is based on OWL-S and allows buying agents to adapt smoothly to dynamically changed web service descriptions of selling agents.


2004


Applying Semantic Web Technologies to Matchmaking and Web Service Descriptions

Amer Al Shaban, Volker Haarslev 

The 1ST Canadian Semantic Web Interest Group Meeting (SWIG’04), November 19, 2004, Université du Quebec a Montreal,  Montreal, Quebec, Canada.
Acrobat file

The recent expansion of representing web services using agents is causing difficulties in finding specific types of web services. The main reason for these problems is the employed matchmaking techniques. Most of the existing techniques are based on search using string comparison, so, if service providers neglect to provide sufficient or appropriate terms for the matchmaking process, the search techniques will return incomplete results. This paper addresses the problem of matching requested services to proper provider agents by making use of OWL (Ontology Web Language) ontologies and the OWL reasoner Racer. In the following we first describe the used tools, and then introduce an implemented prototype, where an agent (MatchMaker) was added to an existing agent framework (DECAF), where the new matchmaker employs OWL-S for matching requests to available services.


Ontologies, Semantic Web and Intelligent Systems for Genomics

Christopher Baker, Greg Butler, Volker Haarslev 

The 1ST Canadian Semantic Web Interest Group Meeting (SWIG’04), November 19, 2004, Université du Quebec a Montreal,  Montreal, Quebec, Canada.
Acrobat file

"Ontologies, the semantic web and intelligent systems for  genomics" is the first project of its kind in Canada to focus on bringing semantic web technology to genomics. Ontology, multi-agent systems, machine learning and natural language processing are used to build tailored  knowledge base and semantic systems of direct use to the  scientific discovery process. Major challenges of the post genomic era, namely data integration and knowledge retrieval are addressed.


The FungalWeb Ontology: The Core of a Semantic Web Application for Fungal Genomics

Arash Shaban-Nejad, Christopher Baker, Volker Haarslev 

The 1ST Canadian Semantic Web Interest Group Meeting (SWIG’04), November 19, 2004, Université du Quebec a Montreal,  Montreal, Quebec, Canada.
Acrobat file

A formal ontology design and implementation case study which serves as the core for a semantic web  application in the area of fungal genomics is  presented. Simplified semantic access to units of  intersecting information from different biological  databases is under development.


Semantic query of a fungal enzyme knowledgebase in the Ontology Web Language – Description Logics  Environment

Christopher Baker, Arash Shaban-Nejad, Volker Haarslev 

Poster presented at the conference on Standards and Ontologies for Functional Genomics 2 (SOFG2), October 23-26, 2004,  The University of  Pennsylvania  School of  Medicine, Philadelphia, Pennsylvania, USA.
Acrobat file

With the substantial increase in stored scientific data of various types, a major challenge of the post-genomic era is to access the knowledge stored in a myriad of complex databases and  other resources across the web. Making these resources available in a more structured way and achieving simplified semantic access to units of intersecting information from different databases is the motivation of this study. To this end, the FungalWeb Ontology (FWO) written in the Ontology Web Language (OWL-DL), representing fungal taxonomy (NCBI / NEWT) and enzyme attributes (BRENDA) are mapped to establish a knowledgebase of use to enzyme application scientists working in the field of fungal genomics. Semantic query of the knowledgebase to identify instances of bio-scientific literature reporting industrially relevant enzymes produced by specific fungal taxonomic groups is described. Physio-chemical and catalytic properties of Laccase enzymes (EC-Number 1.10.3.2) in the context of the fungal host are investigated. Enzyme substrates are described in the context of the chemical dictionary of small molecular entities (ChEBI). The new Racer Query Language (nRQL) is used for defining instance retrieval queries using description logics.


KI-2004 Workshop on Applications of Description Logics (ADL'04)

Sean Bechofer, Volker Haarslev , Carsten Lutz, Ralf Möller (Editors)

Proceedings of the KI-2004 International Workshop on Applications of Description Logics (ADL'04), Ulm, Germany, September 24, 2004.
Electronically available as CEUR publication (Vol-115) here.


Querying the Semantic Web with Racer + nRQL

Volker Haarslev , Ralf Möller, Michael Wessel

Proceedings of the KI-2004 International Workshop on Applications of Description Logics (ADL'04), Ulm, Germany, September 24, 2004.
Acrobat file

This paper introduces a description logic query language for retrieving A-box individuals that satisfy specific conditions. The language is substantially more expressive than traditional concept-based retrieval languages offered by previous description logic reasoning systems. The new language is implemented in the Racer system. We demonstrate the applicability of nRQL (new Racer Query Language) to OWL semantic web repositories and evaluate the performance of the current state of the art query answering engines for description logics using the Lehigh University Benchmark (LUBM).


OntoXpl - Intelligent Exploration of OWL Ontologies

Volker Haarslev, Ying Lu, Nematollah Shiri

Proceedings of the 2004 IEEE/WIC/ACM International Conference on Web Intelligence (WI 2004), Beijing, China, Sept. 20-24, 2004, pp. 624-627.
Acrobat file (for preview)

The OWL ontology explorer OntoXpl is based on the web server tomcat. Standard HTML browsers can be used to interact with OntoXpl. It is intended to complement existing ontology editors and does not offer any editing support. OntoXpl uses the OWL DL reasoner Racer via its extensive query interface in order to support the intelligent exploration of OWL ontologies.


2004 International Workshop on Description Logics (DL2004)

Volker Haarslev , Ralf Möller (editors)

Proceedings of the 2004 International Workshop on Description Logics (DL-2004), Whistler, BC, Canada, June 6-8, 2004, 222 pages.
Also electronically available as CEUR publication
(Vol-104) here.
Acrobat file


Extended Query Facilities for Racer and an Application to Software-Engineering Problems

Volker Haarslev , Ralf Möller, Ragnhild Van Der Straeten, Michael Wessel

Proceedings of the 2004 International Workshop on Description Logics (DL-2004), Whistler, BC, Canada, June 6-8, 2004, pp. 148-157.
Acrobat file

This paper reports on a pragmatic query language for Racer. The abstract syntax and semantics of this query language is defined. Next, the practical relevance of this query language is shown, applying the query answering algorithms to the problem of consistency maintenance between object-oriented design models.


OntoXPL: Exploration of OWL Ontologies

Volker Haarslev , Ying Lu, Nematollah Shiri

Proceedings of the 2004 International Workshop on Description Logics (DL-2004), Whistler, BC, Canada, June 6-8, 2004. pp. 60-69.
Acrobat file

This paper describes the OWL ontology explorer OntoXPL. It is available as a web server based on the tomcat architecture. Standard HTML browsers can be used to interact with OntoXPL. At least three potential user groups are targeted by OntoXPL's design: (i) users with a limited background of ontologies and OWL; (ii) ontology developers that are OWL experts; (iii) users interested in understanding and reusing existing ontologies. OntoXPL is intended to complement existing ontology editors and does not offer any editing support. The current implementation of OntoXPL is based on the OWL DL reasoner Racer and uses Racer's extensive query interface in order to support the exploration of OWL ontologies.


Optimization Techniques for Retrieving Resources Described in OWL/RDF Documents: First Results

Volker Haarslev , Ralf Möller

Ninth International Conference on the Principles of Knowledge Representation and Reasoning, KR 2004, Whistler, BC, Canada, June 2-5, 2004, pp. 163-173.
Acrobat file (for preview)

Practical description logic systems play an ever-growing role for knowledge representation and reasoning research even in distributed environments. In particular, the often-discussed semantic web initiative is based on description logics (DLs) and defines important challenges for current system implementations. Recently, several standards for representation languages have been proposed (RDF, OWL). By introducing optimization techniques for inference algorithms we demonstrate that sound and complete query engines for semantic web representation languages can be built for practically significant query classes. The paper introduces and evaluates optimization techniques for the instance retrieval problem w.r.t. the description logic SHIQ(Dn)-, which covers large parts of OWL. The paper discusses practical experiments with the description logic system Racer.


2003


Description Logics for the Semantic Web: Racer as a Basis for Building Agent Systems

Ralf Möller, Volker Haarslev

In: KI - Zeitschrift für Künstliche Intelligenz (special issue on Semantic Web), No.3, July 2003, pp. 10-15.
Acrobat file (for preview)

The term Semantic Web denotes a vision of a new World-Wide Web in which different kinds of resources (data, services, Web pages, etc.) are accessed and shared on the basis of formal representation structures. As a well-motivated design decision and in order to integrate Semantic Web facilities into the existing software infrastructure of the current Web, its main XML-based syntactic representation formats and their processing conventions are taken for granted. However, in contrast to the standard way of accessing current Web resources by means of surface-oriented syntactic comparison operations, the main idea of the Semantic Web is to answer different kinds of queries w.r.t. a specific conceptual data model rich enough in expressivity to adequately describe the interrelationships between basic representational units (names, symbols) on which a piece of software for a certain application domain is based. Since symbols might have different meanings in different software applications, it is important to explicitly refer to meaning definitions given as a certain instance of an underlying conceptual data model. In the context of the Semantic Web, these definitions are seen as resources themselves and, for reasons of brevity, are often called ontologies. Ontologies provide the basis for implementing specific Semantic Web resources for encapsulating computational processes. These resources are called services. Thus, ontologies play an important role for the Semantic Web. But who is responsible for building ontologies? Influenced by experiences with previous artificial intelligence approaches and motivated by the success of the current Web, many researchers argued for a decentralized logic-based approach, and it is the idea of a formal semantics on which the logic is based that led to the name of the proposed new medium: Semantic Web.

A logical semantics provides the basis not only for the meaning of the representational language but also for the meaning of the associated query and command language. In many applications the logic behind conceptual data models must be decidable but very expressive such that, in principle, query answering involves solving nontrivial logical inference problems. This article briefly introduces the foundation of Semantic Web ontology representation languages, namely description logics. For actually building systems for the Semantic Web, however, we consider practical aspects of very expressive inference systems and their integration into a distributed systems context. Using the Racer System as an example the paper sketches how description logic inference engines can be used to implement information retrieval services on the Semantic Web. The article is written for Semantic Web system developers who would like to learn about logic-based software infrastructure available off the shelf and ready for implementing ontology-based services. We will demonstrate the power of description logics and explain why they are particularly suited for the Semantic Web. However, details on the semantics of description logics in general (and the one underlying Racer in particular), are not to be repeated here. We assume the reader is largely familiar with XML Web standards and conceptual modeling techniques wellknown in the database field.


Racer: A Core Inference Engine for the Semantic Web

Volker Haarslev , Ralf Möller

Proceedings of the 2nd International Workshop on Evaluation of Ontology-based Tools (EON2003), located at the 2nd International Semantic Web Conference ISWC 2003, Sanibel Island, Florida, USA, October 20, 2003, pp. 27-36.
Acrobat file (for preview)

In this paper we describe Racer, which can be considered as a core inference engine for the semantic web. The Racer inference server offers two APIs that are already used by at least three different network clients, i.e., the ontology editor OilEd, the visualization tool RICE, and the ontology development environment Protege 2. The Racer server supports the standard DIG protocol via HTTP and a TCP based protocol with extensive query facilities. Racer currently supports the web ontology languages DAML+OIL, RDF, and OWL.


Racer: An OWL Reasoning Agent for the Semantic Web

Volker Haarslev , Ralf Möller

Proceedings of the International Workshop on Applications, Products and Services of Web-based Support Systems, in conjunction with the 2003 IEEE/WIC International Conference on Web Intelligence,  Halifax, Canada, October 13, 2003, pp. 91-95.
Acrobat file (for preview)

Racer, which can be considered as a core reasoning agent for the semantic web, is briefly described. Racer currently supports a wide range of inference services about ontologies specified in the Ontology Web Language (OWL). These services are made available to other agents via network based APIs. Racer is currently used by various clients such as ontology editors, ontology development and visualization tools, and a first web-based prototype for exploration and analysis of OWL ontologies.


Description Logic Systems with Concrete Domains: Applications for the Semantic Web

Volker Haarslev , Ralf Möller

Proceedings of the International Workshop on Knowledge Representation meets Databases (KRDB-2003), Hamburg, Germany, September 15-16, 2003.
Acrobat file (for preview)

The Semantic Web initiative defines important challenges for knowledge representation and database systems. Recently, several standards for representation languages have been proposed (RDF, DAML+OIL, OWL). We briefly discuss the logical basis of these representation languages by referring to description logic inferences systems. Then, we argue from a practical perspective that current representation languages for the Semantic Web are not sufficient for simple and well-defined representation problems that naturally arise in the context of Semantic Web applications.
In particular, we mention different kinds of algebraic constraints over various domains such as the reals or the natural numbers. We report on practical experiences with description logic reasoning systems (e.g. Racer) already supporting these representation means.


Graphical Interfaces for Racer: Querying DAML+OIL and RDF documents

 Ralf Möller, Ronald Cornet, Volker Haarslev

Proceedings of the International Workshop on Description Logics (DL-2003), Rome, Italy, September 5-7, 2003, pp. 255-259.
Acrobat file (for preview)

In this paper, we introduce RICE, a graphical application for interacting with the description logic inference server Racer. Comparing RICE with OilEd, we address the problem of visualizing and querying A-boxes w.r.t. predefined T-boxes. We discuss examples with T-boxes and A-boxes that are derived from DAML+OIL and RDF documents, respectively. Thus, the visualization tools discussed in this paper also apply to semantic web representation languages.


Incremental Query Answering for Implementing Document Retrieval Services

Volker Haarslev, Ralf Möller

Proceedings of the International Workshop on Description Logics (DL-2003), Rome, Italy, September 5-7, 2003, pp. 85-94.
Acrobat file (for preview)

Agent systems that search the Semantic Web are seen as killer applications for description logic (DL) inference engines. The guiding examples for the Semantic Web involve information and document retrieval tasks. The instance retrieval inference service of description logic inference engines can be used as a basic machinery for implementing agent-based retrieval systems. However, since information is permanently added to information sources, usually agents need to return to previously visited servers in order to get updates for their queries over time.

In this paper we present a software architecture that allows agents to register instance retrieval queries at a certain inference server. We will see how agents are notified when the result set of registered queries grows over time. The paper describes new optimization techniques for incrementally computing answers for sets of registered instance retrieval queries and reports on first experiences with an implementation as part of the Racer system.


Description Logic Systems

Ralf Möller, Volker Haarslev

In: The Description Logic Handbook , Franz Baader, Diego Calvanese, Deborah McGuinness, Daniele Nardi, Peter Patel-Schneider (Eds.), Cambridge University Press, 2003, Chapter 8, pp. 282-305.
Acrobat File (for preview)

This chapter discusses implemented description logic systems that have played or play an important role in the field. It first presents several earlier systems that, although not based on description logics, have provided important ideas. These systems include Kl-One, Krypton, Nikl, and Kandor. Then, successor systems are described by classifying them along the characteristics discussed in the previous chapters, addressing the following systems: Classic (“almost” complete, fast); Back, Loom (expressive, incomplete); Kris, Crack (expressive, complete). At last, a new optimized generation of very expressive but sound and complete DL systems is also introduced. In particular, we focus on the systems Dlp, Fact, and Racer and explain what they can and cannot do.


2002


ADL-2002: KI-2002 Workshop on Applications of Description Logics

Günther Görtz, Volker Haarslev , Carsten Lutz, Ralf Möller (Editors)

Proceedings of the International KI-2002 Workshop on Applications of Description Logics (ADL-2002), Aachen, Germany, 16. September 2002.
CEUR Online Proceedings (Postscript files)


Practical Reasoning in RACER with a Concrete Domain for Linear Inequations

Volker Haarslev, Ralf Möller

Proceedings of the International Workshop on Description Logics (DL-2002), Toulouse, France, April 19-21, 2002, pp. 91-98.
Postscript file (Preprint)
Acrobat file (for preview)

We introduce the very expressive description logic ALCQHIR+(D)− providing a limited support for concrete domains. The description logic system RACER supports TBox and ABox reasoning for ALCQHIR+(D)− using a default concrete domain for linear inequations. The adaptation of several important optimization techniques is presented. We conclude the paper with a first proposal for extending ALCQHIR+(D)− by a restricted form of feature chains.


Optimization Strategies for Instance Retrieval

Volker Haarslev , Ralf Möller

Proceedings of the International Workshop on Description Logics (DL-2002), Toulouse, France, April 19-21, 2002, pp. 83-90.
Postscript file (Preprint)
Acrobat file (for preview)

In this paper new techniques for optimizing instance retrieval in DL systems are described. The algorithms are evaluated with application examples from a natural language processing application.


Adding ternary complex roles to ALCRP(D)

Alissa Kaplunova, Volker Haarslev , Ralf Möller

Proceedings of the International Workshop on Description Logics (DL-2002), Toulouse, France, April 19-21, 2002, 45-52.
Postscript file (Preprint)
Acrobat file (for preview)

The goal of this paper is to introduce the description logic ALCRP3(D). This logic is based on the DL ALCRP(D) extended by a ternary role-forming predicate operator and by inverse roles. In order to be able to define a compositional semantics for ALCRP3(D),whic h supports n-ary relations,w e introduce a DLR-style syntax. For simplicity and from the viewpoint of the applicability in practice,only ternary relations will be discussed. The paper discusses syntactic restrictions on concepts and roles to ensure decidability of the language.


Visual Spatial Query Languages: A Semantics Using Description Logic

Volker Haarslev , Ralf Möller , Michael Wessel

In: Diagrammatic Representation and Reasoning, P. Olivier, M. Anderson, and B. Meyer, editors, Springer-Verlag, London, 2002, pp. 387-410.
Postscript file (Preprint)
Acrobat file (for preview)

We present a first treatment dealing with the semantics of visual spatial query languages for geographic information systems using a suitable description logic. This decidable space logic is described and its usefulness for geographic information systems is exemplified. The logic supports the specification of a semantics, reasoning about query subsumption and about applying default knowledge, and the specification of so-called ABox patterns.

Keywords---description logic, spatial reasoning, semantics of visual spatial queries, spatial query subsumption, theoretical foundations for GIS, ALCRP(D), concrete domains, spatioterminological default reasoning, ABox patterns.


2001


Combining Tableau and Algebraic Methods for Reasoning with Qualified Number Restrictions in Description Logics

Volker Haarslev , Martina Timmann, Ralf Möller

Proceedings of the International Workshop on Methods for Modalities 2 (M4M-2), Amsterdam, Netherlands, November 29-30,  2001.
Postscript file (Preprint)
Acrobat file (for preview)

The paper investigates an optimization technique for reasoning with qualified number restrictions in the description logic ALCQHR+ (a.k.a. SHQ), which can be seen as one of the cornerstones for reasoning technology in the context of, for instance, the semantic web activity. We present a hybrid architecture where a standard tableaux calculus is combined with a procedure deciding the satisfiability of linear inequations derived from qualified number restrictions. The advances are demonstrated by an empirical evaluation using the description logic system  RACER . The evaluation demonstrates a dramatic speed up compared to other known approaches.

Keywords---description logic, qualified number restrictions, concept satisfiability testing, constraint satisfaction, Simplex procedure, ABox tableaux calculus, RACER.


Theory and Practice of Visual Languages and Description Logics

Volker Haarslev  

Habilitation Thesis, Computer Science Department, University of Hamburg, September 2001, 240 pages.
Acrobat file (for preview)

This monograph reports on research in two major areas, visual language theory and description logics, which seem to be quite diverse. However, it will become clear to the reader of this monograph that both lines of research are intertwined with each other. The work on visual language theory gave important impetus to the author's research on description logics and the results from description logics motivated new approaches for visual language theory.

Keywords---visual languages, visual language theory, GenEd, Pictorial Janus, visual spatial query languages, VISCO, semantics of visual spatial query languages, description logic, ALCNHR+, ABox tableaux calculus, optimizations for description logic provers, RACER.


ADL-2001: KI-2001 Workshop on Applications of Description Logics

Günther Görtz, Volker Haarslev , Carsten Lutz, Ralf Möller (Editors)

Proceedings of the International KI-2001 Workshop on Applications of Description Logics (ADL-2001), Vienna, Austria, 18. September 2001.
CEUR Online Proceedings (Postscript files)
Workshop Proceedings (Acrobat file)

Recently, a growing interest in description logics and their applications can be observed. This is mainly due to the development of very expressive description logics and optimized description logic systems which support terminological and/or assertional reasoning for these logics. This workshop intended to gather researchers as well as practitioners who are interested in description logics and their applications. The primary focus of this workshop was on applications of description logics. Ian Horrocks, University of Manchester, gave a tutorial-style talk about latest developments in description logic research.


RACER User's Guide and Reference Manual Version 1.6

Volker Haarslev , Ralf Möller  

Technical Report, University of Hamburg, Computer Science Department, July 2001.
Acrobat file  

This user's guide and reference manual introduces the description logic system RACER (Reasoner for Aboxes and Concept Expressions Renamed). RACER is a highly optimized ABox reasoner for the expressive description logic ALCQHI R+.(D)-.

RACER is available for research purposes, see this link .

Keywords---description logic, TBox and ABox reasoning, ABox tableaux calculus, concrete domains, RACER.


Description of the RACER System and its Applications

Volker Haarslev , Ralf Möller

Proceedings of the International Workshop on Description Logics (DL-2001), Stanford, USA, 1.-3. August 2001, pp. 132-141.
Postscript file (Preprint)
Acrobat file (for preview)

RACER implements a TBox and ABox reasoner for the logic SHIQ. RACER was the first full-fledged ABox description logic system for a very expressive logic and is based on optimized sound and complete algorithms.


Optimizing Reasoning in Description Logics with Qualified Number Restrictions

Volker Haarslev , Ralf Möller

Proceedings of the International Workshop on Description Logics (DL-2001), Stanford, USA, 1.-3. August 2001, pp. 142-151.
Postscript file (Preprint)
Acrobat file (for preview)

In this paper an optimization technique, the so-called signature calculus, for reasoning with number restrictions in description logics is investigated. The calculus is used to speed-up ABox (and TBox) reasoning in the description logic ALCQHR+.

Keywords---description logic, qualified number restrictions, concept satisfiability testing, signature calculus, ABox tableaux calculus, RACER.


Combining Tableaux and Algebraic Methods for Reasoning with Qualified Number Restrictions

Volker Haarslev , Martina Timmann, Ralf Möller

Proceedings of the International Workshop on Description Logics (DL-2001), Stanford, USA, 1.-3. August 2001, pp. 152-161.
Postscript file (Preprint)
Acrobat file (for preview)

This paper investigates an optimization technique for reasoning with qualified number restrictions in the description logic ALCQHR+. We present a hybrid architecture where a standard tableaux calculus is combined with a procedure deciding the satisfiability of linear (in)equations derived from qualified number restrictions. The advances are demonstrated by an empirical evaluation using the description logic system RACER which implements TBox and ABox reasoning for ALCQHIR+. The evaluation demonstrates a dramatic speed up compared to other known approaches.

Keywords---description logic, qualified number restrictions, concept satisfiability testing, constraint satisfaction, Simplex procedure, ABox tableaux calculus, RACER.


Combining cardinal direction relations and relative orientation relations in Qualitative Spatial Reasoning

Amar Isli , Volker Haarslev and Ralf Möller

Technical report FBI-HH-M-304/01, Fachbereich Informatik, Universität Hamburg, 2001.
Postscript file
Acrobat file

Combining different knowledge representation languages is one of the main topics in Qualitative Spatial Reasoning (QSR). This allows the combined languages to compensate each other's representational deficiencies, and is seen as an answer to the emerging demand from real applications, such as Geographical Information Systems (GIS), robot navigation, or shape description, for the representation of more specific knowledge than is allowed by each of the languages taken separately. Knowledge expressed in such a combined language decomposes then into parts, or components, each expressed in one of the combined languages. Reasoning internally within each component of such knowledge involves only the language the component is expressed in, which is not new. The challenging question is to come with methods for the interaction of the different components of such knowledge. With these considerations in mind, we propose a calculus, cCOA, combining, thus more expressive than each of, two calculi well-known in QSR: Frank's cardinal direction calculus, CDA, and a coarser version, ROA, of Freksa's relative orientation calculus. An original constraint propagation procedure, PcS4c+(), for cCOA-CSPs is presented, which aims at (1) achieving path consistency (Pc) for the CDA projection; (2) achieving strong 4-consistency (S4c) for the ROA projection; and (3) more (+) (the "+" consists of the implementation of the interaction between the two combined calculi). Dealing with the first two points is not new, and involves mainly the CDA composition table and the ROA composition table, which can be found in, or derived from, the literature. The originality of the propagation algorithm comes from the last point. Two tables, one for each of the two directions CDA-to-ROA and ROA-to-CDA, capturing the interaction between the two kinds of knowledge, are defined, and used by the algorithm. The importance of taking into account the interaction is shown with a real example providing an inconsistent knowledge base, whose inconsistency (a) cannot be detected by reasoning separately about each of the two components of the knowledge, just because, taken separately, each is consistent, but (b) is detected by the proposed algorithm, thanks to the interaction knowledge propagated from each of the two compnents to the other.


Combining Tableaux and Algebraic Decision Procedures for Dealing with Qualified Number Restrictions in Description Logics

Volker Haarslev , Martina Timmann, Ralf Möller

Proceedings of the International Workshop on Issues in the Design and Experimental Evaluation of Systems for Modal and Temporal Logics at IJCAR-2001, E. Giunchiglia, F. Massacci (Eds.), Technical Report DII 14/01, Siena, Italy, June, 2001, pp. 39-48.
Postscript file (Preprint)
Acrobat file (for preview)

This paper investigates an optimization technique for reasoning with qualified number restrictions in the description logic ALCQHR+. We present a hybrid architecture where a standard tableaux calculus is combined with a procedure deciding the satisfiability of linear (in)equations derived from qualified number restrictions. The advances are demonstrated by an empirical evaluation using the description logic system RACER which implements TBox and ABox reasoning for ALCQHIRplus. The evaluation demonstrates a dramatic speed up compared to other known approaches.

Keywords---description logic, qualified number restrictions, concept satisfiability testing, constraint satisfaction, Simplex procedure, ABox tableaux calculus, RACER.


High Performance Reasoning with Very Large Knowledge Bases: A Practical Case Study

Volker Haarslev , Ralf Möller

Proceedings of Seventeenth International Joint  Conference on Artificial Intelligence, IJCAI-01, B. Nebel (Ed.), August 4-10, 2001, Seattle, Washington, USA, pp. 161-166.
Postscript file (Preprint)
Acrobat file (for preview)

In this contribution we present an empirical analysis of optimization techniques devised to speed up the so-called TBox classification supported by description logic systems which have to deal with very large knowledge bases (e.g. containing more than 100,000 concept introduction axioms). These techniques are integrated into the RACE architecture which implements a TBox and ABox reasoner for the description logic ALCNHR+. The described techniques consist of adaptions of previously known as well as new optimization techniques for efficiently coping with these kinds of very large knowledge bases. The empirical results presented in this paper are based on experiences with an ontology for the Unified Medical Language System and demonstrate a considerable runtime improvement. They also indicate that appropriate description logic systems based on sound and complete algorithms can be particularly useful for large but simple knowledge bases.

Keywords---description logic, very large knowledge bases, optimization of TBox and ABox reasoning, quasi definition order, domain/range restrictions for roles, clustering in TBoxes, concept disjointness, ABox tableaux calculus, RACE, medical applications, UMLS.


Exploiting Pseudo Models for TBox and ABox Reasoning in Expressive Description Logics

Volker Haarslev , Ralf Möller , Anni-Yasmin Turhan

Proceedings of International Joint Conference on Automated Reasoning, IJCAR'2001, R. Goré, A. Leitsch, T. Nipkow (Eds.),June 18-23, 2001, Siena, Italy, Springer-Verlag, Berlin,pp. 61-75.
Postscript file ©Springer-Verlag (Preprint)
Acrobat file ©Springer-Verlag (for preview)

This paper investigates optimization techniques and data structures exploiting the use of so-called pseudo models. These techniques are applied to speed-up TBox and ABox reasoning for the description logics ALCNHR+ and ALC(D). The advances are demonstrated by an empirical analysis using the description logic system RACE that implements TBox and ABox reasoning for ALCNHR+.

Keywords---description logic, deep pseudo model merging, individual pseudo model merging, optimization of TBox and ABox reasoning, ABox tableaux calculus, RACE, concrete domains, ALC(D).


The Description Logic ALCNHR+ Extended with Concrete Domains: A Practically Motivated Approach

Volker Haarslev , Ralf Möller , Michael Wessel

Proceedings of International Joint Conference on Automated Reasoning, IJCAR'2001, R. Goré, A. Leitsch, T. Nipkow (Eds.),June 18-23, 2001, Siena, Italy, Springer-Verlag, Berlin,pp. 29-44.
Postscript file ©Springer-Verlag (Preprint)
Acrobat file ©Springer-Verlag (for preview)

The paper introduces the description logic ALCNHR+(D)-. Prominent language features beyond conjunction, full negation and quantifiers, are number restrictions, role hierarchies, transitively closed roles, generalized concept inclusions and concrete domains. As in other languages based on concrete domains (e.g. ALC(D)) a so-called predicate exists restriction concept constructor is provided. However, compared to ALC(D) only features and no feature chains are allowed in this operator. This results in a limited expressivity w.r.t. concrete domains but is required to ensure the decidability of the language. We show that the results can be exploited for building practical description logic systems for solving e.g. configuration problems.  

Keywords---description logic, ALCNHR+, ALC(D), concrete domains, ABox tableaux calculus, RACE, RACER .


RACER System Description

Volker Haarslev , Ralf Möller

Proceedings of International Joint Conference on Automated Reasoning, IJCAR'2001, R. Goré, A. Leitsch, T. Nipkow (Eds.),June 18-23, 2001, Siena, Italy, Springer-Verlag, Berlin,pp. 701-705.
Postscript file ©Springer-Verlag (Preprint)
Acrobat file ©Springer-Verlag (for preview)

RACER implements a TBox and ABox reasoner for the logic ALCQHIR+ (or SHIQ). RACER was the first full-fledged ABox description logic system for a very expressive logic and is based on optimized sound and complete algorithms. RACER can also be used for solving modal logic satisfiablity problems (possibly with global axioms).


2000


Expressive Description Logics for Agent-Based Information Retrieval

Ralf Möller , Volker Haarslev , Bernd Neumann

In: Knowledge Engineering and Agent Technology, Volume 52, Frontiers in Artificial Intelligence and Applications, edited by: Cuena, J., Demazeau, Y., Garcia, A., and Treur, J., IOS Press, Amsterdam, Netherlands, 2000.

In this contribution we investigate the use of description logics (DLs) for information retrieval in a multiagent scenario. We first describe two advanced DLs and present the relevant reasoning services provided for information retrieval, in particular instance retrieval, instance checking and example-based instance retrieval. Complete and sound algorithms exist for each of these tasks in both DLs, but it is shown that a combined DL is undecidable. In order to make use of knowledge bases which use different DLs, a broker-based multiagent information retrieval scheme is presented. The main idea is to pose transformed queries to individual agents and combine the answers to obtain a correct but not necessarily complete result. The approach is illustrated with detailed examples.
 


Theory and Application of Diagrams

Michael Anderson, Peter Cheng, Volker Haarslev (Eds.)

First International Conference, Diagrams 2000, Edinburgh, Scotland, UK, September 1-3, 2000, Proceedings,  Lecture Notes in Computer Science, VOL. 1889, 504 pp.

This book constitutes the refereed proceedings of the First International Conference on the Theory and Application of Diagrams, Diagrams 2000, held in Edinburgh, Scotland, UK in September 2000. The 31 revised full papers presented together with 9 posters were carefully reviewed and selected from around 100 submissions. The papers are organized in topical sections on logic and diagrams, theoretical concerns about diagrams, human communication with diagrams, diagrammatic reasoning and proof systems, and diagrams for systems versus systems for diagrams.

Keywords---Diagrams, Conceptual Graphs, Cognition, Visual Languages, Visual Programming, Graphical Representation, Diagram Interpretation, Diagram Semantics, Diagrammatic Communication, Diagrammatic Syntax


The Description Logic ALCNHR+ Extended with Concrete Domains: Revised Version

Volker Haarslev , Ralf Möller , Michael Wessel

Technical Report No. FBI-HH-M-290/00, University of Hamburg, Computer Science Department, August 2000.
Postscript file (Preprint)
Acrobat file (for preview)

The paper introduces the description logic ALCNHR+(D)- Prominent language features beyond ALC are number restrictions, role hierarchies, transitively closed roles, generalized concept inclusions and concrete domains. As in other languages based on concrete domains, e.g. ALC(D), a so-called predicate exists restriction concept constructor is provided. However, compared to ALC(D) only features and no feature chains are allowed in this operator. This results in a limited expressivity w.r.t. concrete domains but is required to ensure the decidability of the language. We show that the results can be exploited for building practical description logic systems for solving e.g. configuration problems.

Keywords---description logic, ALCNHR+, ALC(D), concrete domains, ABox tableaux calculus, RACE.


Adapting Optimization Techniques to Description Logics with Concrete Domains

Anni-Yasmin Turhan, Volker Haarslev

In : Proceedings of the International Workshop in Description Logics 2000 (DL2000), Aachen, Germany, 2000, pp. 247-256.
Postscript file (Preprint)
Acrobat file (for preview)

In this paper, we demonstrate that the main standard optimization techniques dependency directed backtracking and model merging can be adapted to description logics with concrete domains. We propose algorithms for these techniques for the logics ALC(D) and ALCRP(D). Important results of this study are (1) a new requirement for concrete domains in order to enable dependency directed backtracking for all clash types of description logics with concrete domains, and (2) the flat and deep model merging techniques can be fully adapted to ALC(D) but their applicability to the logic ALCRP(D) is limited.

Keywords---description logic, dependency-directed backtracking, pseudo model merging, concrete domains, optimization of TBox reasoning, tableaux calculus.


Optimizing TBox and ABox Reasoning with Pseudo Models

Volker Haarslev , Ralf Möller

In : Proceedings of the International Workshop in Description Logics 2000 (DL2000), Aachen, Germany, 2000, pp. 153-162.
Postscript file (Preprint)
Acrobat file (for preview)

This paper investigates optimization techniques and data structures exploiting the use of so-called pseudo models. These techniques are applied to speed-up TBox and ABox reasoning for the description logic ALCNHR+. The advances are demonstrated by an empirical analysis using the description logic system RACE that implements TBox and ABox reasoning for ALCNHR+.

Keywords---description logic, deep pseudo model merging, individual pseudo model merging, optimization of TBox and ABox reasoning, ABox tableaux calculus, RACE.


High Performance Reasoning with Very Large Knowledge Bases

Volker Haarslev , Ralf Möller

In : Proceedings of the International Workshop in Description Logics 2000 (DL2000), Aachen, Germany, 2000, pp. 143-152.
Postscript file (Preprint)
Acrobat file (for preview)

In this contribution we present an empirical analysis of the performance of the ALCNHR+ description logic system RACE applied to TBoxes with a very large number of primitive concept definitions. Adaptions of previously known techniques as well as new optimization techniques for efficiently dealing with these kinds of knowledge bases are discussed.

Keywords---description logic, very large knowledge bases, optimization of TBox and ABox reasoning, quasi definition order, domain/range restrictions for roles, clustering in TBoxes, concept disjointness, ABox tableaux calculus, RACE, medical applications, UMLS.


ALCRA -- ALC with Role Axioms

Michael Wessel , Volker Haarslev , Ralf Möller

In : Proceedings of the International Workshop in Description Logics 2000 (DL2000), Aachen, Germany, 2000, pp. 267-276.
Postscript file (Preprint)
Acrobat file (for preview)

This paper presents a tableaux calculus for deciding the concept satisability problem of the new description logic ALCRA and discusses some open problems. ALCRA augments the description logic ALC with role inclusion axioms of the form S compose T implies R1 or ... or Rn. Additionally, all roles are interpreted as disjoint.

Keywords---description logic, role box, role inclusion axioms.


Consistency Testing: The RACE Experience

Volker Haarslev , Ralf Möller

In: Proc. of TABLEAUX'2000, International Conference, Automated Reasoning with Analytic Tableaux and  Related Methods, Roy Dyckhoff (ed.), St. Andrews, Scotland, UK, July 3-7, 2000, Springer-Verlag, 2000, pp. 57-61.
Postscript file
Acrobat file (for preview)

This paper presents the results of applying RACE, a description logic system for ALCNHR+, to modal logic SAT problems. Some aspects of the RACE architecture are discussed in detail: (i) techniques involving caching and (ii) techniques for dealing with individuals.


Expressive ABox Reasoning with Number Restrictions, Role Hierarchies, and Transitively Closed Roles

Volker Haarslev , Ralf Möller

In: Proceedings of Seventh International Conference on Principles of Knowledge Representation and Reasoning (KR2000), Fausto Giunchiglia and Bart  Selman (eds), Breckenridge, Colorado, USA, 12-15 April 2000, Morgan Kaufmann Publishers, San Francisco, CA, 2000, pp.273-284 (corrected version).

Postscript file
Acrobat file (for preview)

We present a new tableaux calculus deciding the ABox consistency problem for the expressive description logic ALCNHR+. Prominent language features beyond ALC are number restrictions, role hierarchies, transitively closed roles, and generalized concept inclusions. The ABox description logic system RACE is based on the calculus for ALCNHR+.

Keywords---description logic, TBox and ABox reasoning, ABox tableaux calculus, RACE.


Expressive ABox Reasoning with Number Restrictions, Role Hierarchies, and Transitively Closed Roles

Volker Haarslev , Ralf Möller

Technical Report No.FBI-HH-M-288/99, University of Hamburg,Computer Science Department , March 2000 (revised version).
Postscript file
Acrobat file (for preview)

We present a new tableaux calculus deciding the ABox consistency problem for the expressive description logic ALCNHR+. Prominent language features of ALCNHR+ are number restrictions, role hierarchies, transitively closed roles, and generalized concept inclusions.  The ABox description logic system RACE is based on the calculus for ALCNHR+.

Keywords---description logic, TBox and ABox reasoning, ABox tableaux calculus, RACE.


1999


RACE User's Guide and Reference Manual Version 1.1

Volker Haarslev , Ralf Möller , Anni-Yasmin Turhan

Technical Report No.FBI-HH-M-289/99, University of Hamburg,Computer Science Department , October 1999.
Postscript file
Acrobat file (for preview)

This user's guide and reference manual introduces the description logic system RACE (Reasoner for Aboxes and Concept Expressions). RACE is a highly optimized ABox reasoner for the expressive description logic ALCNH R+ .

RACE is available for research purposes, see this link .

Keywords---description logic, TBox and ABox reasoning, ABox tableaux calculus, RACE.


On Specifying Semantics of Visual Spatial Query Languages

Volker Haarslev , Ralf Möller , Michael Wessel

In: Proceedings of the 15th IEEE Symposium on Visual Languages 1999 , Sept. 13-16, Tokyo, Japan, IEEE Press 1999, pp. 4-11.
Postscript file (Preprint)
Acrobat file (for preview)

We present a first treatment dealing with semantics of visual spatial query languages for GIS using a suitable description logic. This decidable space logic is described and its usefulness for GIS exemplified. The logic supports the specification of semantics, reasoning about query subsumption and about applying default knowledge.

Keywords---description logic, spatial reasoning, semantics of visual spatial queries, spatial query subsumption, theoretical foundations for GIS, ALCRP(D), concrete domains, spatioterminological default reasoning.


On Terminological Default Reasoning about Spatial Information: Extended Abstract

Volker Haarslev , Ralf Möller , Michael Wessel , Anni-Yasmin Turhan

In: Proc. of DL99 , International Workshop on Description Logics , Linköping, 1999, pp. 155-159.
Postscript file
Acrobat file (for preview)

We extend the theory about terminological default reasoning using a logical base language that can be used to represent spatioterminological phenomena. Based on the description logic ALCRP(S2) the paper discusses an algorithm for computing extensions of a world description consisting of ALCRP(S2) assertions and a set of closed ALCRP(S2) defaults. We show that the algorithm is sound and complete and terminates if an admissibility criterion on the default rules is fulfilled.

Keywords---description logic, spatioterminological default reasoning, spatial reasoning,  theoretical foundations for GIS, ALCRP(D), concrete domains.


RACE System Description

Volker Haarslev , Ralf Möller

In: Proc. of DL99 , International Workshop on Description Logics , Linköping, 1999, pp. 130-132.

Postscript file
Acrobat file (for preview)


An Empirical Evaluation of Optimization Strategies for ABox Reasoning in Expressive Description Logics

Volker Haarslev , Ralf Möller

In: Proc. of DL99 , International Workshop on Description Logics , Linköping, 1999, pp. 115-119.
Postscript file
Acrobat file (for preview)

In this paper we present an evaluation of a new description logic reasoner called RACE which implements TBox and ABox reasoning for the description logic ALCNHR+ that supports number restrictions, role hierarchies, and transitively closed roles. Tests on benchmark ABoxes indicate a speedup of several orders of magnitude compared to previous systems.

Keywords---description logic, TBox and ABox reasoning, tableaux calculus, optimization.


A Logic-based Formalism for Reasoning about Visual Representations

Volker Haarslev

Journal of Visual Languages and Computing , Vol. 10, No. 4, 1999, pp. 421-445.
Postscript file (Preprint)
Acrobat file (for preview)

This article presents a logic-based formalism for formal reasoning about visual representations. This formalism is based on previous work about describing visual notations. However, in this article we discuss major extensions to this formalism providing decidable reasoning mechanisms that support truly spatial domains such as geographical information systems (GIS). We demonstrate the application of this formalism to specifying semantics of visual query languages for GIS and to meta reasoning about spatial queries.

Keywords---description logic, spatial reasoning, semantics of visual spatial queries, spatial query subsumption, theoretical foundations for GIS, ALCRP(D), concrete domains.


Applying an ALC ABox Consistency Tester to Modal Logic SAT Problems

Volker Haarslev , Ralf Möller

In: Proc. of TABLEAUX'99, The 6th International Conference on Theorem Proving with Analytic Tableaux and  Related Methods, Neil V. Murray (ed.), Saratoga Springs, NY/USA, June 7-11, 1999, Springer-Verlag, 1999, pp. 24-18.
Postscript file
Acrobat file (for preview)

In this paper we present the results of applying HAM-ALC, a description logic system for ALCNR, to modal logic SAT problems.


A Description Logic with Concrete Domains and a Role-forming Predicate Operator

Volker Haarslev , Carsten Lutz , Ralf Möller

Journal of Logic and Computation , Vol. 9, No.3, June 1999, pp.351-384.
Postscript file (Preprint)
Acrobat file (for preview)

This article presents the description logic ALCRP(D) with concrete domains and a role-forming predicate operator as its prominent  aspects. We demonstrate the feasibility of ALCRP(D) for reasoning about spatial objects and their qualitative spatial relationships and provide an appropriate concrete domain for spatial objects. The general significance of ALCRP(D) is demonstrated by adding temporal  reasoning to spatial and terminological reasoning using a combined concrete domain. The theory is motivated as a basis for knowledge representation and query processing in the domain of geographic information systems. In contrast to existing work in this domain, which mainly focuses either on conceptual reasoning or on reasoning about qualitative spatial relations, we integrate reasoning about spatial information with terminological reasoning.

Keywords---description logic, spatial reasoning, spatiotemporal reasoning, theoretical foundations for GIS.


1998


A Logic-based Formalism for Reasoning about Visual Representations

Volker Haarslev

In: Proceedings of the FRVDR'98 workshop "Formalizing Reasoning with Visual and Diagrammatic Representations", AAAI Fall Symposium Series 1998, Orlando, Florida/USA, Oct. 23-25, 1998, pp. 57-66.
Postscript file not yet available
Acrobat file not yet available

This paper presents a logic-based formalism for formal reasoning about visual representations. This formalism is based on previous work about describing visual notations. However, in this paper we discuss major extensions to this formalism providing decidable reasoning mechanisms that support truly spatial domains such as geographical information systems (GIS). We sketch out the application of this formalism to the specification of syntax and semantics of visual query languages for GIS and to meta reasoning about spatial queries.

Keywords--- theory of visual languages, formal semantics, diagrammatical reasoning, description logics.


Bringing Visual Spatial Querying to Reality

Michael Wessel , Volker Haarslev

In: Proceedings of the 14th IEEE Symposium on Visual Languages 1998, Sept. 1-4, Halifax, Canada, IEEE Press 1998, pp. 170-177.
Postscript File
Acrobat File (for preview)
VISCO quicktime movie (53 MB, watch while downloading if Quicktime plugin is installed)
Please visit VISCO's homepage

This paper reports on the evolution of the spatial (sketch-based) query language VISCO and its implementation. The first design of VISCO's query language was presented at VL '97. The language is based on a strong naive physics metaphor for query objects (e.g. marbles, nails, rubberbands). We shortly review the prominent aspects of the revised version of VISCO's query language. The main focus of this paper is on VISCO's implementation using city maps of Hamburg as example domain. Its innovative user interface consists of three interconnected components: a graphical (syntax-directed) query editor and visual language compiler, a browser for inspecting the query results, and a map viewer for browsing the spatial database. We also briefly report on the process of compiling, optimizing, and executing VISCO's queries.

Keywords--- visual query languages, environments and systems, graphical representation of constraints, human computer interaction (HCI), spatial information systems (SIS), graph matching, optimizing visual language compilers.


A Fully Formalized Theory for Describing Visual Notations

Volker Haarslev

In:Visual Language Theory , K. Marriott, B. Meyer (eds), Springer-Verlag, New York, 1998, pp. 261-292.
Postscript file not available, please order the book

This chapter addresses issues in visual language theory with the help of logic formalisms that were developed for reasoning tasks by the artificial intelligence and spatial databases community, especially for spatial and diagrammatical reasoning. We describe an approach based on three formal components. Topology is used to define basic geometric objects. Theory about spatial relations from the domain of spatial databases is employed to define possible relationships between visual language elements. Description logic theory from the AI community is used to combine topology and spatial relations. We prove the feasibility of our theory by describing three representative visual notations: entity-relationship diagrams, petri nets, and a pictorial language for concurrent logic programming.

Keywords--- theory of visual languages, formal semantics, diagrammatical reasoning, description logics.

This is an extended and revised version of the AVITVL'96 paper .


Implementing an ALCRP(D) ABox Reasoner - Progress Report -

Volker Haarslev , Ralf Möller , Anni-Yasmin Turhan

In: Proc. DL-98 International Description Logic Workshop 1998, June 6 - June 8, Trento, Italy, 1988, pp. 82-86.
Postscript File
Acrobat File (for preview)

This paper presents a progress report on the implementation of an ALCRP(D) ABox reasoner and a knowledge representation framework. We present an ALC ABox reasoner which has been constructed for providing a basis for an optimized ALCRP(D) implementation. We compare the implementation with the concept consistency reasoner FACT which sets the standard in current DL implementations.


HAM-ALC - Performance Measurements -

Volker Haarslev , Ralf Möller , Anni-Yasmin Turhan

In: Proc. DL-98 International Description Logic Workshop 1998, June 6 - June 8, Trento, Italy, 1988, pp. 64-65.
Postscript File
Acrobat File (for preview)


Foundations of Spatioterminological Reasoning with Description Logics

Volker Haarslev , Carsten Lutz , Ralf Möller

In: Principles of Knowledge Representation and Reasoning: Proceedings of the Sixth International Conference (KR'98), A.G. Cohn, L.K. Schubert, S.C.Shapiro, editors, June 2-5, Trento, Italy, Morgan-Kaufmann Publishers, 1998, pp. 112-123.
Postscript File
Acrobat File (for preview)

This paper presents a method for reasoning about spatial objects and their qualitative spatial relationships. In contrast to existing work, which mainly focusses on reasoning about qualitative spatial relations alone, we integrate quantitative and qualitative information with terminological reasoning. For spatioterminological reasoning we present the description logic ALCRP(D) and define an appropriate concrete domain D for polygons. The theory is motivated as a basis for knowledge representation and query processing in the domain of deductive geographic information systems.

Keywords--- Qualitative spatial reasoning, terminological reasoning, environmental geographic information systems.


Semantics-Based Information Retrieval

Ralf Möller , Volker Haarslev , Bernd Neumann

In: Proc. IT&KNOWS-98: International Conference on Information Technology and Knowledge Systems,
31. August- 4. September, Vienna, Budapest, 1998, pp. 48-61.
Postscript File
Acrobat File (for preview)

In this paper we investigate the use of conceptual descriptions based on description logics for content-based information retrieval and present several innovative contributions. We provide a query-by-examples retrieval framework which avoids the drawback of a sophisticated query language. We extend an existing DL to deal with spatial and temporal concepts. We provide a content-based similarity measure based on the least common subsumer which extracts conceptual similarities of examples.


1997



A Concept Language with Role-Forming Predicate Restrictions

Carsten Lutz, Volker Haarslev , Ralf Möller

University of Hamburg,Computer Science Department , Technical Report No. FBI-HH-M-276/97.
Postscript File
Acrobat File (for preview)

The development of language constructs for defining concept and role terms is an important goal of research on description logic formalisms. However, most decidable descriptions logics only support the definition of roles with very limited properties. For more complex roles, e.g. roles needed to represent Allen's temporal relations, a higher expressivity is required. This paper formally introduces a new description logic formalism called ALCRP(D) . It is a descendant of ALCRP(D) and thus allows one to represent abstract and concrete information. Furthermore, it contains a new operator for defining roles based on predicates over (concrete) properties of objects. In previous work by the authors, reasoning in ALCRP(D) was proven to be undecidable in general. In this report we show that reasoning in ALCRP(D) is decidable if certain restrictions are posed on the structure of terminologies. In fact, the free combinability of some operators has to be restricted. The representational expressiveness of so-called "restricted terminologies" obtained in this way is of course lower than the expressiveness of unrestricted ones. Nevertheless, the resulting formalism is still a powerful and usable tool for conceptual reasoning that supports the definition of roles with very complex properties.

Keywords--- Qualitative spatial reasoning, terminological reasoning, environmental geographic information systems.


Spatioterminological Reasoning Based on Geometric Inferences: The ALCRP(D) Approach

Ralf Möller , Volker Haarslev ,Carsten Lutz

University of Hamburg,Computer Science Department , Technical Report No. FBI-HH-M-277/97.
Postscript File
Acrobat File (for preview)

This report presents a method for reasoning about spatial objects and their qualitative spatial relationships. In contrast to existing work, which mainly focuses on reasoning about qualitative spatial relations alone, we integrate quantitative and qualitative information with terminological reasoning by providing an admissible concrete domain for the description logic ALCRP(D) . The theory is motivated as a basis for knowledge representation and query processing in the domain of environmental geographic information systems.

Keywords--- Qualitative spatial reasoning, terminological reasoning, environmental geographic information systems.


Spatioterminological Reasoning: Subsumption Based on Geometrical Inferences

Volker Haarslev , Ralf Möller

Proceedings of the International Workshop on Description Logics , M.-C. Rousset et al., editors, Sept. 27-29, Gif sur Yvette, France, Universite Paris-Sud, 1997, pp. 74-78.
Postscript File
Acrobat File (for preview)

This paper presents a theoretical basis for terminological reasoning about objects and their qualitative spatial relationships. In contrast to existing work, which mainly focuses on reasoning about qualitative spatial relations alone, we integrate quantitative and qualitative information with terminological reasoning. This theory is motivated as basis for knowledge representation and query processing for instance in the domain of deductive geographic information systems.

Keywords--- Qualitative spatial reasoning, terminological reasoning.


Querying GIS with Animated Spatial Sketches

Volker Haarslev , Michael Wessel

Proceedings of the 13th IEEE Symposium on Visual Languages 1997, Sept. 23-26, Capri, Italy, IEEE Press 1997, pp. 197-204.
Postscript File (4.2 MB)
Acrobat File (for preview)

We present the design of the visual query system VISCO that offers a sketch-based query language for defining approximate spatial constellations of objects. VISCO smoothly integrates geometrical and topological querying with deductive spatial reasoning. It is based on a strong physical metaphor visualizing semantics of query elements. Approximate queries rely on combined topological and geometrical constraints enhanced with relaxations and "don't cares" that are visualized through live animations.

Keywords--- visual query systems, visual parsing, deductive GIS, constraints.


SBox: A Qualitative Spatial Reasoner -Progress Report-

Volker Haarslev , Ralf Möller

Proceedings, 11th International Workshop on Qualitative Reasoning, L. Ironi, editor, Cortona, Tuscany, Italy, June 3-6, 1997, Pubblicazioni N. 1036, Istituto di Analisi Numerica C.N.R. Pavia (Italy), pp. 105-113.
Postscript File
Acrobat File (for preview)

This paper presents a method for reasoning about spatial objects and their qualitative spatial relationships (e.g. touches, overlaps etc.) on the basis of a description logic framework. We apply this method to the domain of deductive geographic information systems. In contrast to existing work, which mainly focuses on reasoning about qualitative spatial relations alone, we integrate quantitative and qualitative information with terminological reasoning by extending description logics with a space box reasoner which is inspired by an extension to description logics called "concrete domains.'' With the space box reasoner presented in this paper it is possible to combine qualitative spatial reasoning and description logic classification processes.

Keywords--- qualitative spatial reasoning, description logics, deductive geographical information systems.


1996


Using Description Logic for Reasoning about Diagrammatical Notations

Volker Haarslev

Proceedings of the International Workshop on Description Logics , L. Padgham et al., editors, Nov. 2-4, 1996, Cambridge, Massachusetts, AAAI Press, Menlo Park, California, 1996, Technical Report No. WS-96-05, pp. 124--128.
Postscript File
Acrobat File (for preview)

This paper summarizes research about a fully implemented logical framework to develop axiomatizations defining meaningful "constellations'' of abstract diagrammatical objects. The proposed framework is based on a spatial logic for describing qualitative spatial relationships between objects and on description logic as specification formalism. The framework was successfully applied to three representative diagrammatic notations: simple entity-relationship diagrams, place-transition petri nets, and a visual language for concurrent logic programming.

Keywords--- diagrammatical reasoning, description logics.


GenEd -- An Editor with Generic Semantics for Formal Reasoning about Visual Notations

Volker Haarslev ,Michael Wessel

Proceedings of the 12th IEEE Symposium on Visual Languages 1996, Sept. 3-6, Boulder, Colorado, USA, IEEE Press 1996, pp. 204-211.
Postscript File
HTML version
Quicktime movie of demo (10 MB, watch while downloading if Quicktime plugin is installed)

We describe the object-oriented editor GenEd supporting the design of specifications for visual notations. Prominent features of GenEd are (1) it is generic , i.e. domain-specific syntax and semantics are specified by users; (2) built-in parser for actual drawings, driven by formal specifications; (3) powerful reasoning capabilities about diagrams and their specification. GenEd's specification language is based on a fully formalized theory for describing visual notations. Three examples, place-transition petri nets, entity-relationship diagrams, and a small GIS application are presented.

Keywords--- theory of visual languages, formal semantics, diagrammatical reasoning, description logics, visual editor, visual parsing, geographical information systems.


A Fully Formalized Theory for Describing Visual Notations

Volker Haarslev

Proceedings of the AVI'96 post-conference Workshop on Theory of Visual Languages , May 30, 1996, Gubbio, Italy.
Postscript File
HTML version

This paper addresses issues in visual language theory with the help of logic formalisms that were developed for reasoning tasks by the artificial intelligence and spatial databases community, especially for spatial and diagrammatical reasoning. We describe an approach based on three formal components. Topology is used to define basic geometric objects. Theory about spatial relations from the domain of spatial databases is employed to define possible relationships between visual language elements. Description logic theory from the AI community is used to combine topology and spatial relations. The resulting theory has been successfully applied to formally specifying semantics of visual languages. The theory's application is illustrated with a specification of entity-relationship diagrams.

Keywords--- theory of visual languages, formal semantics, diagrammatical reasoning, description logics.


Older Publications:

Back to my home page