Volker Haarslev's List of Publications

2010

Algebraic Tableau Reasoning for the Description Logic SHOQ

Logic Journal of the IGPL, Special Issue on Hybrid Logics, accepted for publication, January 2010, 30 pages.
Acrobat file

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 uninformedness 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 K_m) 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.

2009

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

AI Communications, Special Issue on Practical Aspects of Automated Reasoning, accepted for publication, July 2009, 37 pages.
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.

Tableau-based Reasoning

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

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

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

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.

Algebraic Tableau Algorithm for ALCOQ

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

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

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

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

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.

Human Factors in Dynamic E-Health Systems and Digital Libraries 

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, 2009, 13 pages, accepted for publication, Jan. 2009.
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.

2008

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

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

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

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

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

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

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 

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 

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

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

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

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

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

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

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

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é

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

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

Towards a framework for requirement change management in healthcare software applications 

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

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

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

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

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 

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

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

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

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

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

Measuring Inconsistencies in Ontologies

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Resolution Based Explanations for Reasoning in the Description Logic ALC

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.

Semantic Web Uncertainty Management

To appear in: Encyclopedia of Information Science & Technology, 2nd edition, IDEA Group, 2006.

Ontoligent Interactive Query Tool

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

Uncertainty Reasoning in Description Logics: A Generic Approach

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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)

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

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

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

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

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

Racer: A Core Inference Engine for the Semantic Web

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

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

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

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

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

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

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

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)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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 ALCNH_R+. Prominent language features of ALCNH_R+ 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

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

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

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

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

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

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

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

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

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

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

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 -

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 -

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

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

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

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

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

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

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-

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

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

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

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:

• V. Haarslev, " Formal Semantics of Visual Languages Using Spatial Reasoning ", in Proceedings of the 11th IEEE Symposium on Visual Languages 1995 , V. Haarslev (ed.), Sept. 5-9, Darmstadt, Germany, IEEE Press 1995, pp. 156-163. ( HTML version )
• D. Fahrenholtz, V. Haarslev, " Visualization of Strand Processes ", in Proceedings of the 11th IEEE Symposium on Visual Languages 1995 , V. Haarslev (ed.), Sept. 5-9, Darmstadt, Germany, IEEE Press 1995, pp. 114-115.( HTML Version )
• V. Haarslev, " Spatial Reasoning with Description Logics ", in KI-95 Activities: Workshops, Posters, Demos, L.S. Dreschler-Fischer, S. Pribbenow (Eds.), 19th Annual German Conference on Artificial Intelligence, KI-95, Bielefeld, Sept. 11-13, 1995, pp. 101--102, GI, Bonn, 1995.
• V. Haarslev, R. Möller, and C. Schröder, " Combining Spatial and Terminological Reasoning ", in KI-94: Advances in Artificial Intelligence -- Proc. 18th German Annual Conference on Artificial Intelligence, Saarbrücken, Sept. 18--23, 1994, B. Nebel and L. Dreschler-Fischer, Eds. Sept. 1994, vol. 861 of Lecture Notes in Artificial Intelligence, pp. 142--153, Springer Verlag, Berlin.
• V. Haarslev and R. Möller, " Visualization and Graphical Layout in Object-Oriented Systems ", Journal of Visual Languages and Computing, vol. 3, no. 1, pp. 1--23, Mar. 1992. ( HTML Version )
• K.M. Kahn, V.A. Saraswat, and V. Haarslev, " Pictorial Janus: A Completely Visual Programming Language and its Environment (in German) ", in GI-Fachgespräch Programmieren multimedialer Anwendungen der GI-Jahrestagung 1991, Darmstadt, Oktober 1991, J. Encarnacao, Ed. 1991, pp. 427--436, Springer Verlag, Berlin.
• V. Haarslev and R. Möller, "VIPEX: Visual Programming of Experimental Systems", in Visual Languages and Visual Programming , S.K. Chang, Ed., pp. 185--212. Plenum Press, New York and London, 1990.
• V. Haarslev and R. Möller, " A Framework for Visualizing Object-Oriented Systems ", in ECOOP/OOPSLA'90, European Conference on Object-Oriented Programming and Object Oriented Programming: Systems, Languages and Applications, Oct. 21-25, 1990, Ottawa/Canada. Oct. 1990, vol. 25, pp. 237--244, ACM Press.
• V. Haarslev and R. Möller, " Visualization and Graphical Layout in Object-Oriented Systems ", Tech. Rep. SSL-90-53 [P90-00134], Xerox Palo Alto Research Center, 1990.
• R. Möller and V. Haarslev, " Layoutspezifikationen für komplexe graphische Objekte ", in GI-Fachgespräch Graphik und KI, Königswinter 3./4. April 1990, K. Kansy and P. Wikirchen, Eds. Apr. 1990, number 239 in Informatik Fachberichte, pp. 78--91, Springer Verlag, Berlin.
• V. Haarslev and R. Möller, " A Declarative Formalism for Specifying Graphical Layout ", In 1990 IEEE Workshop on Visual Languages, Skokie, Illinois, Oct. 4-6, IEEE Computer Society Press, Oct. 1990, pp. 54--59.
• V. Haarslev and R. Möller, "Visualisierungen beim Entwicklungsproze experimenteller Programmsysteme", in Software-Ergonomie '89, Hamburg, 29.-31. Mar. 1989, H. Oberquelle and S. Maaß, Eds., Stuttgart, Mar. 1989, Berichte des German Chapter ACM und GI, pp. 427--436, Teubner-Verlag.
• V. Haarslev and R. Möller, "VIPEX: Ein Dialograhmen zum visuellen Programmentwurf", in Fachtagung Benutzerschnittstellen -- Werkzeuge und Techniken zur Gestaltung interaktiver Systeme, Darmstadt, 8.-9. Okt. 1988 , H.J. Hoffmann, Ed. TH Darmstadt, Oct. 1989, number Heft 17 in 2. Tagungsheft, Notizen zu Interaktiven Systemen.
• H. Faasch and V. Haarslev, "Eine graphische ADA-Programmierumgebung für modulare Experimentalsysteme", in GI-Workshop Sprachspezifische Programmierumgebungen, TH Darmstadt, 6.--8. April 1988, G. Snelting, Ed., Apr. 1988, pp. 196--205.
• V. Haarslev and R. Möller, "Visualisierung und Animation in der experimentellen Bildauswertung", in GI/ÖCG-Fachgespräch Visualisierungstechniken und Algorithmen, Wien, 26.--27. Sep. 1988 , W. Barth, Ed. Sept. 1988, number Nr. 182 in Informatik-Fachberichte, pp. 213--223, Springer Verlag, Berlin.
• V. Haarslev and R. Möller, "Eine graphische Umgebung zur experimentellen Bildverarbeitung", in Mustererkennung, 10. DAGM-Symposium Zürich, 27.--29. Sep. 1988, H. Bunke, O. Kübler, and P. Stucki, Eds. Sept. 1988, vol. 180 of Informatik-Fachberichte , pp. 319--325, Springer Verlag, Berlin.
• V. Haarslev and R. Möller, "Visualization of Experimental Systems", In 1988 IEEE Workshop on Visual Languages , Pittsburgh/PA, Oct. 10-12, IEEE Computer Society Press, Oct. 1988, pp. 175--182.
• V. Haarslev, "Eine ergonomische Benutzerschnittstelle für den Anwendungsbereich der Bildfolgenauswertung", in Software-Ergonomie '87, Berlin, 27.-29. Apr. 1987, W. Schönpflug and M. Wittstock, Eds., Stuttgart, Apr. 1987, Berichte des German Chapter of the ACM, pp. 176--186, Teubner-Verlag.
• V. Haarslev, "Human Factors in Computer Vision Systems: Design of an Interactive User Interface", in Second IFIP Conference on Human-Computer Interaction -- INTERACT '87, Stuttgart, F.R. Germany, 1-4 September, 1987 , H.-J. Bullinger and B. Shackel, Eds., Amsterdam, Sept. 1987, pp. 1021--1026, North-Holland.
• V. Haarslev, Interaktion in Systemen zur Bildfolgenauswertung basierend auf einem objektorientierten Ansatz, PhD thesis, University of Hamburg, Computer Science Department, July 1986, Available as Technical Report FBI-HH-B-125/86.
• L.S. Dreschler Fischer and V. Haarslev, "Konzeption für ein Bildverarbeitungssystem zur Lösung des Korrespondenzproblems bei Stereo-Bildfolgen im Rahmen einer komfortablen ADA-Programmierumgebung", Robotersysteme , vol. 1, pp. 29--34, 1985.
• H. Faasch, V. Haarslev, and H.-H. Nagel, "Erfahrungen mit dem Ada-HH Übersetzer, Ada-HH Compiler Projekt, Abschlubericht zum DFG-Forschungsvorhaben", Tech. Rep., University of Hamburg, Computer Science Department, May 1985.
• H. Faasch and V. Haarslev, "Konzeption einer neuen Ada-Programmierumgebung für die Bildfolgenauswertung", in Mustererkennung, 7. DAGM-Symposium Erlangen, 24.-26. Sep. 1985, H. Niemann, Ed. Sept. 1985, vol. 107 of Informatik-Fachberichte, pp. 191--196, Springer Verlag, Berlin.
• H. Faasch, V. Haarslev, and H.-H. Nagel, "Ada on a Minicomputer-Network for Image Sequence Analysis: An Investigative Implementation", ACM Ada Letters, vol. 2, no. 4, pp. 92--96, Feb. 1983.