A machine learning approach for optimizing heuristic decision-making in Web Ontology Language reasoners
A Framework for Parallelizing OWL Classification in Description Logic Reasoners
Web Ontology Language (OWL) reasoners are used to infer new
logical relations from ontologies. While inferring new facts,
these reasoners can be further optimized, e.g., by properly
ordering disjuncts in disjunction expressions of ontologies for
satisfiability testing of concepts. Different expansion-ordering
heuristics have been developed for this purpose. The built-in
heuristics in these reasoners determine the order for branches in
search trees while each heuristic choice causes different effects
for various ontologies depending on the ontologies' syntactic
structure and probably other features as well. A learning-based
approach that takes into account the features aims to select an
appropriate expansion-ordering heuristic for each ontology. The
proper choice is expected to accelerate the reasoning process for
the reasoners. In this paper, the effect of our methodology is
investigated on a well-known reasoner that is JFact. Our
experiments show the average speedup by a factor of one to two
orders of magnitude for satisfiability testing after applying
learning methodology for selecting the right expansion-ordering
heuristics.
Optimization techniques play a significant role in improving
description logic reasoners covering the Web Ontology Language
(OWL). These techniques are essential to speed up these reasoners.
Many of the optimization techniques are based on heuristic
choices. Optimal heuristic selection makes these techniques more
effective. The FaCT++ OWL reasoner and its Java version JFact
implement an optimization technique called ToDo list which is a
substitute for a traditional top-down approach in tableau-based
reasoners. The ToDo list mechanism allows one to arrange the order
of applying different rules by giving each a priority. Compared to
a top-down approach, the ToDo list technique has a better control
over the application of expansion rules. Learning the proper
heuristic order for applying rules in ToDo list will have a great
impact on reasoning speed. We use a binary SVM technique to build
our learning model. The model can help to choose ontology-specific
order sets to speed up OWL reasoning. On average, our learning
approach tested with 40 selected ontologies achieves a speedup of
two orders of magnitude when compared to the worst rule ordering
choice.
Handling Nominals and Inverse Roles using Algebraic Reasoning
In this paper, we present a novel consequence-based algorithm to
perform subsumption reasoning in SHOQ, which support nominals and
Qualified Cardinality Restrictions (QCRs). Our algorithm maps
numerical restrictions imposed by QCRs or nominals to inequalities
and determines the feasibility of inequality systems by means of
Integer Linear Programming.
Various (tableau) optimization techniques have been integrated
into OWL reasoners to speed up reasoning. Many of the techniques
rely on heuristics that have been manually fine tuned for
achieving a good performance but might fail dramatically when
encountering ontologies exhibiting unexpected design patterns. A
typical example are heuristics applied to disjunctions in order to
select a disjunct to be added to the tableau. Evidences indicate
that the order of selecting disjuncts can have a significant
impact on reasoning speed. Our approach presented in this paper
applies machine learning to make the selection process more
effective and removes the need for manual fine tuning. We extended
the OWL reasoner JFact accordingly to control the disjunct
selection process. We demonstrate that one can successfully learn
to choose a disjunct based on the most effective heuristic method.
As a first step we focused on propositional SAT testing. Our
results show that machine learning can speed up JFact by one to
two orders of magnitude.
Proceedings of the 11th International Symposium on Frontiers
of Combining Systems (FroCoS 2017), Brasília, Brazil, LNAI
10483, pp. 95-112.
Acrobat file (preprint)
We present a novel hybrid architecture for reasoning about
description logics supporting role hierarchies and qualified
cardinality restrictions (QCRs). Our reasoning architecture is
based on saturation rules and integrates integer linear
programming. Deciding the numerical satisfiability of a set
of QCRs is reduced to solving a corresponding system of linear
inequalities. If such a system is infeasible then the QCRs are
unsatisfiable. Otherwise the numerical restrictions of the QCRs
are satisfied but unknown entailments between qualifications can
still lead to unsatisfiability. Our integer linear programming
(ILP) approach is highly scalable due to integrating learned
knowledge about concept subsumption and disjointness into a column
generation model and a decomposition algorithm to solve it. Our
experiments indicate that this hybrid architecture offers a better
scalability for reasoning about QCRs than approaches combining
both tableaux and ILP or applying traditional (hyper)tableau
methods.
Proceedings of the Tenth International Workshop on Parallel
Programming Models and Systems Software for High-End Computing
(P2S2) at the 46th International Conference on Parallel
Processing (ICPP-2017), Bristol, UK, IEEE, pp. 200-209.
Acrobat file (preprint)
The Web Ontology Language (OWL) plays an important role in the
{\em semantic web} to represent domain knowledge using classes,
properties, and individuals. OWL reasoners analyze ontologies and
offer inference services such as class satisfiability and
subsumption. Ontology classification is an important and widely
used service that computes a taxonomy of all classes occurring in
an ontology. It can require significant amounts of runtime but
most OWL reasoners do not support any kind of parallel
processing. We present a novel thread-level parallel architecture
for ontology classification that is ideally suited for
shared-memory SMP servers, where each thread can be mapped to a
core on a one-to-one basis. We evaluated our prototype
implementation with a set of real-world ontologies. Our
experiments demonstrate a very good scalability resulting in a
speedup that is linear to the number of available cores.
Proceedings of the 5th Workshop on Practical Aspects of
Automated Reasoning (PAAR 2016), Coimbra, Portugal, CEUR,
pp. 110-124.
Acrobat file
We present a reasoning architecture for deciding subsumption for
the description logic ELQ. Our architecture combines saturation
rules with algebraic reasoning based on Integer Linear Programming
(ILP). Deciding the so-called numerical satisfiability of a set of
qualified cardinality restrictions is reduced to constructing a
corresponding system of linear inequalities and applying ILP
methods in order to determine whether this system is feasible. Our
preliminary experiments indicate that this calculus offers a
better scalability for qualified cardinality restrictions than
approaches combining both tableaux and ILP as well as traditional
(hyper)tableau methods.
Abductive Conjunctive Query Answering w.r.t. Ontologies
Künstliche Intelligenz, Vol. 30, 2015, pp. 177-182.
Acrobat file (preprint)
In this article we investigate abductive conjunctive query
answering w.r.t. ontologies and show how use cases can benefit
from this kind of query answering service. While practical
reasoning systems such as Racer have supported abductive
conjunctive query answering for 10 years now, and many projects
have exploited this feature, few publications deal with A-box
abduction from an implementation perspective. This article gives a
generalized overview on features provided by practical systems and
also explains optimization techniques needed to meet practical
requirements.
International Journal of Data
Mining and Bioinformatics, Vol. 11, No. 1, 2015, pp. 53-83.
Acrobat file (preprint)
Ontologies play a crucial role in current web-based biomedical
applications for capturing contextual knowledge in the domain of
life sciences. They are continuously evolving in order to fix the
problems and provide valid knowledge. As our knowledge improves,
the related definitions in the ontologies will be altered. This
issue is inadequately addressed by available tools and algorithms,
mostly due to the lack of suitable knowledge representation
formalisms to deal with temporal abstract notations, and the
over-reliance on human factors. Also most of the current
approaches have been focused on changes within the internal
structure of ontologies, and interactions with other existing
ontologies have been widely neglected. In our research, after
revealing and classifying some of the common alterations in a
number of popular biomedical ontologies, we present a novel
agent-based framework, RLR (Represent, Legitimate, and Reproduce),
to semi-automatically manage the evolution of bio-ontologies, with
emphasis on the FungalWeb Ontology, with minimal human
intervention. RLR assists and guides ontology engineers through
the change management process in general, and aids in tracking and
representing the changes, particularly through the use of category
theory. We have also employed rule-based hierarchical graph
transformation to propose a more specific semantics for analyzing
ontological changes and transformations between different versions
of an ontology, as well as tracking the effects of a change in
different levels of abstractions.
Proceedings of the 3rd Joint International
Semantic Technology (JIST) Conference, Seoul, Korea,
November 28-30, 2013, LNCS 8388, pp. 211-227.
Acrobat file (preprint)
Our research is motivated by the ubiquitous
availability of multiprocessor computers and the
observation that available Web Ontology Language (OWL)
reasoners only make use of a single processor.
This becomes rather frustrating for users working in
ontology development, especially if their ontologies
are complex and require long processing times using
these OWL reasoners. We present a novel algorithm that
uses a divide and conquer strategy for
parallelizing OWL TBox classification, a key task in
description logic reasoning. We discuss some
interesting properties of our algorithm, e.g., its
suitability for distributed reasoning, and present an
empirical study using a set of benchmark ontologies,
where a speedup of up to a factor of 4 has been
observed when using 8 workers in parallel.
Proceedings of the 22nd International Conference on
Automated Reasoning with Analytic Tableaux and Related
Methods, Nancy, France, September 16-19, 2013, pp.
273-287.
Acrobat file (preprint)
Although state-of-the-art description logic (DL) reasoners
are equipped with a comprehensive set of optimizations,
reasoning performance is still a major bottleneck in both
research and real world applications. In this paper, we
propose a sound and complete algorithm called the
intelligent tableau algorithm by incorporating comprehensive
learning techniques to tackle all DL reasoning tasks. We
also provide a reference implementation reasoner called
LIGHT for the DL ALC dialect based on the algorithm we
developed. Preliminary tests indicate that significant
improvements can be achieved, i.e., compared to other
state-of-the-art reasoners, LIGHT is up to two orders of
magnitude faster for simple problems and several orders of
magnitude faster for more difficult problems. Even though in
this work our discussion is restricted to the ALC reasoning
problem, our conjecture is that the algorithm developed can
easily be extended to super-logics of ALC.
Proceedings of the 2013 International Workshop
on Description Logics (DL-2013), Ulm, Germany, July
23-26, 2013, pp. 1011-1023.
Acrobat file
Multiprocessor equipment is cheap and ubiquitous now, but users
of description logic (DL) reasoners have to face the awkward fact
that the major tableau-based DL reasoners can make use only one of
the available processors. Recently, researchers have started
investigating how concurrent computing can play a role in
tableau-based DL reasoning with the intention of fully exploiting
the processing resources of multiprocessor computers. The
published research mostly focuses on utilizing disjunctive
branches, the or-part of tableau expansion trees. We
investigated the possibility and the role of concurrently
processing conjunctive branches, the and-part of tableau
expansion trees. In this work, we present an algorithm to process
conjunctive branches in parallel and address the key
implementation aspects of the algorithm. A research prototype to
execute this algorithm has been developed and empirically
evaluated. The experimental results are presented and analyzed. We
found that parallelizing the processing of conjunctive branches of
tableau expansion trees is auspicious and can partly evolve into a
scalable solution for DL reasoning.
Proceedings of the 2nd Joint International Semantic Technology
Conference (JIST), Dec. 2 - 4, 2012, Nara, Japan, pp. 313-318.
Acrobat file (preprint)
OWL 2-supported Semantic Tagging is a non compulsory yet decisive
and highly influential component of a multidisciplinary knowledge
architecture framework which synergetically combines the Semantic
and the Social Webs. The facility consists of a semantic tagging
layer based on OWL 2 axioms and expressions enticing social
network users, typically mommy bloggers, to annotate their chaos
of textual data with natural language verbalized versions of
ontological elements. This paper provides a comprehensive short
summary of the overall framework along with its backbone metamodel
and its parenting analysis and surveillance ontology ParOnt,
laying a particular emphasis on its semantic expression-based
tagging feature, and accordingly highlighting the attained gains
and improvements in terms of effective results, services and
recommendations, all falling in the scope of public parenting
orientation and awareness.
Proceedings of the 3rd International Conference on Ambient
Systems, Networks and Technologies (ANT), Aug. 27-29, 2012,
Niagara Falls, Ontario, Canada, Procedia Computer Science,
volume 10, pages 110–119, 2012.
Acrobat file (preprint)
Amid the extremely active Semantic Web community and the Social
Web's exceptionally rising popularity, experts believe that an
amplified fusion between the two webs will give rise to the next
huge advancement in Web intelligence. Such advances can
particularly be translated into ambient and ubiquitous systems and
applications. In this paper, we delve into the recent advances in
knowledge representation, semantic web, natural language
processing and online social networking data and concepts, to
propose an inclusive platform and framework defining ambient
recommender and decision support systems that aim at facilitating
cross-sectional analysis of the domain of childhood obesity and
generating both generic and customized preventive recommendations.
Proceedings of the 2012 International Workshop
on Description Logics (DL-2012), Rome, Italy, June 7-10,
2012, pp. 378-388.
Acrobat file
Multi-processor/core systems have become ubiquitous but the vast
majority of OWL reasoners can process ontologies only
sequentially. This observation motivates our work on the design
and evaluation of Deslog, a parallel tableau-based description
logic reasoner for ALC. A first empirical evaluation for TBox
classification demonstrates that Deslog's architecture supports a
speedup factor that is linear to the number of utilized
processors/cores.
Proceedings of the 2012 International Workshop
on Description Logics (DL-2012), Rome, Italy, June 7-10,
2012, 530-540.
Acrobat file
We present a hybrid tableau calculus for the description logic
SHIQ that decides ABox consistency and uses an algebraic approach
for more informed reasoning about qualified number restrictions
(QNRs). Benefiting from integer linear programming and several
optimization techniques to deal with the interaction of QNRs and
inverse roles, our approach provides a more informed calculus. A
prototype reasoner based on the hybrid calculus has been
implemented that decides concept satisfiability for ALCHIQ. We
provide a set of benchmarks that demonstrate the effectiveness of
our hybrid reasoner.
Proceedings of the 2012 International Workshop
on Description Logics (DL-2012), Rome, Italy, June 7-10,
2012, pp. 400-410.
Acrobat file
This paper describes our progress in developing algorithms for
concurrent classification of OWL ontologies. We refactored the
architecture of our research prototype and its employed algorithms
by integrating lock-free data structures and adopting various
optimizations to reduce overhead. In comparison to our earlier
work we increased the size of classified ontologies by one order
of magnitude, i.e., the size of processed ontologies is now beyond
a quarter million of OWL classes. The main focus of this paper is
an empirical evaluation with huge ontologies that demonstrates an
excellent speedup that almost directly corresponds to the number
of used processors or cores.
Proceedings of the 2012 EACL 2012 Workshop on Semantic
Analysis in Social Media at the 13th Conference of the
European Chapter of the Association for Computational
Linguistics (EACL), April 23-27, Avignon, France, 2012,
pp. 37-45.
Acrobat file (preprint)
Originating from a multidisciplinary research project that
gathers, around the Semantic Web standards and principles, Social
Networking and Natural Language Processing along with some
Bioinformatics notions, this paper sheds the light on some of the
most critical aspects of the correspondingly adopted framework and
real- time knowledge architecture and modeling platform. It
recognizes the considerable profits of an appropriate fusion
between the aforementioned disciplines, especially via the proper
exploitation of OWL 2 (Web Ontology Language) features and
novelties, typically OWL 2 language profiles. Accordingly, it
proposes a distinctive workflow with well-defined strategies for
an ontology-aware user and NLP-assisted flexible and
multidimensional approach for the management of the abundantly
available Social data. Application scenarios related to awareness
and orientation recommender systems based on biomedical domain
ontologies for childhood obesity prevention and surveillance are
explored as typical proof of concept application areas.
Proc. of the 2011 IEEE
International Workshop on Biomedical and Health Informatics
(BHI) in BIBM 2011, 12-13 November, 2011, Atlanta, GA, USA, pp.
615-622.
Acrobat file (preprint)
This paper reports the summary and results of our research on
providing a graph oriented formalism to represent, analyze and
validate the evolution of bio-ontologies, with emphasis on the
FungalWeb Ontology. In this approach Category theory along with
rule-based hierarchical distributed (HD) graph transformation have
been employed to propose a more specific semantics for analyzing
ontological changes and transformations between different versions
of an ontology, as well as tracking the effects of a change in
different levels of abstractions.
Semantic Web, Volume 3, No. 3 (2012), pages 267-277.
Acrobat file
RacerPro
is a software system for building applications based on
ontologies. The backbone of RacerPro
is a description logic reasoner. It provides inference services
for terminological knowledge as well as for representations of
knowledge about individuals. Based on new optimization techniques
and techniques that have been developed in the research field of
description logics throughout the years, a mature architecture for
typical-case reasoning tasks is provided. The system has been used
in hundreds of research projects and industrial contexts
throughout the last twelve years. W3C standards as well as
detailed feedback reports from numerous users have influenced the
design of the system architecture in general, and have also shaped
the RacerPro
knowledge representation and interface languages. With its query
and rule languages, RacerPro
goes well beyond standard inference services provided by other OWL
reasoners.
Proceedings of CADE – the 23rd
International Conference on Automated Deduction, Wroclaw,
Poland, July 31-Aug. 5, 2011, LNCS, Volume 6803/2011, pp.
283-298.
Acrobat file (preprint)
Reasoning techniques for qualified number restrictions (QNRs) in
Description Logics (DLs) have been investigated in the past but
they mostly do not make use of the arithmetic knowledge implied by
QNRs. In this paper we propose and investigate a novel approach
for concept satisfiability in acyclic ALCQ ontologies. It is based
on the idea of encoding an ALCQ ontology into a formula in
Satisfiability Modulo the Theory of Costs (SMT(C)), which is a
specific and computationally much cheaper subcase of Linear
Arithmetic under the Integers, and to exploit the power of modern
SMT solvers to compute every concept-satisfiability query on a
given ontology. We implemented and tested our approach, which
includes a very effective individuals-partitioning technique, on a
wide set of synthesized benchmark formulas, comparing the approach
with the main state-of-the-art DL reasoners available. Our
empirical evaluation confirms the potential of the approach.
Proceedings of the IEEE Congress
on Evolutionary Computation (IEEE CEC 2011), New Orleans, USA,
June 5-8, 2011, pp.
2002-2009.
Acrobat file (preprint)
Intelligent agents are able to assist humans in managing highly
dynamic and complex systems in various knowledge intensive
domains. The communication between different agents interacting in
an integrated multi-agents system can be managed through a set of
steering rules, which together form interaction protocols. To
support the negotiation, communication and interaction between
different intelligent agents, using an appropriate knowledge
representation formalism is crucial. This paper introduces the
potential of category theory as a formal representation vehicle to
facilitate evolutionary analysis of agent interaction and
negotiation for managing evolving ontologies in the domain of
biomedicine. Utilizing categories supports agents’ communication,
negotiation, state transitions, compositions and transformations
in different levels of abstractions.
Proceedings of the 2010 International Workshop on Description
Logics (DL2010), Waterloo, Ontario, Canada, May 4–7, 2010,
510 pages.
Electronically available as CEUR
publication (Vol-573) here.
Proceedings of the 2nd International Conference
on Computational Collective Intelligence: Semantic Web, Social
Networks & Multi-agent Systems (ICCCI 2010), 10-12 Nov 2010,
Taiwan, LNCS Springer, Vol. 6423, pp. 457-468.
Acrobat file (preprint)
To facilitate communication and the exchange of information
between patients, nurses, lab technicians, health insurers,
physicians, policy makers, and existing knowledge-based systems, a
set of shared standard terminologies and controlled vocabularies
are necessary. In modern health information management systems,
these vocabularies are defined within formal representations
called ontologies, where terminologies are only meaningful once
linked to a descriptive dataset. When the datasets and their
conveyed knowledge are changed, the ontological structure is
altered accordingly. Despite the importance of this topic, the
problem of managing evolving ontological structures is
inadequately addressed by available tools and algorithms, partly
because handling ontological change is not a purely computational
affair. In this paper, we propose a framework inspired by a social
activity, birdwatching. Using this model, the evolving ontological
structures can be monitored and analyzed based on their state at a
given time. Moreover, patterns of changes can be derived and used
to predict and approximate a system’s behavior based on potential
future changes.
Proceedings of the 19th European Conference on
Artificial Intelligence - ECAI 2010, Lisbon, Portugal, Aug.
16-20, 2010, pp. 485-490.
Acrobat file (preprint)
One of the most frequently used inference services of description
logic reasoners classifies all named classes of OWL ontologies
into a subsumption hierarchy. Due to emerging OWL ontologies from
the web community consisting of up to hundreds of thousand of
named classes and the increasing availability of multi-processor
and multi- or many-core computers, we extend our work on parallel
TBox classification and propose a new algorithm that is
sound and complete and demonstrates in a first experimental
evaluation a low overhead w.r.t. subsumption tests (less than 3%)
if compared with sequential classification.
Proceedings of the 2010 International Workshop
on Description Logics (DL-2010), Waterloo, Canada, May
4-7, 2010, pp. 161-172.
Acrobat file
In this paper we outline an algebraic tableau algorithm for the
DL SHOQ, which supports more informed reasoning due to the use of
semantic partitioning and integer programming. We introduce novel
and adapt known optimization techniques and show their
effectiveness on the basis of a prototype reasoner implementing
the optimization techniques for the algebraic approach. Our first
set of benchmarks clearly indicates the effectiveness of our
approach and a comparison with the DL reasoners Pellet and HermiT
demonstrates a runtime improvement of several orders of magnitude.
Book chapter in Biomedical Knowledge Management:
Infrastructures and Processes for E-Health Systems, W. Pease, M.
Cooper, R. Gururajan (eds), Information Science Reference, ISR
series, IGI Global, 2010, pp. 192-202.
Acrobat
file (preprint)
E-health systems and digital libraries deal with human health,
requiring fast responses and real-time decision-making. Human
intervention can be seen in the whole life cycle of biomedical
systems. In fact, relations between patients, nurses, lab
technicians, health insurers, and physicians are crucial in such
systems, and should be encouraged when necessary. However, there
are some issues that affect the successful implementation of such
infrastructures. Man-machine interaction problems are not purely
computational and need a deep understanding of human behavior.
Many integrated health knowledge management systems, have employed
various knowledgebases and ontologies as their conceptual backbone
to facilitate human-machine communication. Ontologies facilitate
sharing knowledge between human and machine; they try to capture
knowledge from a domain of interest; when the knowledge changes,
the definitions will be altered to provide meaningful and valid
information. In this chapter, we review and survey the potential
issues related to the human factor in an integrated dynamic
e-health system composed of several interrelated knowledgebases,
bio-ontologies and digital libraries by looking at different
theories in social science, psychology, and cognitive science. We
also investigate the potential of some advanced formalisms in the
semantic web context such as employing intelligent agents to
assist the human user in dealing with changes.
Proceedings of the 2010 International Workshop
on Description Logics (DL-2010), Waterloo, Canada, May
4-7, 2010, pp. 336-347.
Acrobat file
One of the most frequently used inference services of description
logic reasoners classifies all named classes of OWL ontologies
into a subsumption hierarchy. Due to emerging OWL ontologies from
the web community consisting of up to hundreds of thousand of
named classes and the increasing availability of multi-processor
and multi- or many-core computers, we extend the work on parallel
TBox classification and propose a new algorithm that is
sound and complete and demonstrates in a first experimental
evaluation a low overhead in the number of subsumption tests due
to parallel execution.
Journal of Applied Logic, Special Issue on Hybrid Logics,
Volume 8, Issue 4, December 2010, pp. 334-355 (doi:10.1016/j.jal.2010.08.009).
Acrobat file (preprint)
Semantic web applications based on the web ontology language
(OWL) often require the use of numbers in class descriptions for
expressing cardinality restrictions on properties or even classes.
Some of these cardinalities are specified explicitly but quite a
few are entailed and need to be discovered by reasoning
procedures. Due to the description logic (DL) foundation of OWL
those reasoning services are offered by DL reasoners which employ
reasoning procedures that are arithmetically uninformed and
substitute arithmetic reasoning by "don't know" non-determinism in
order to cover all possible cases. This lack of information about
arithmetic problems dramatically degrades the performance of DL
reasoners in many cases, especially with ontologies relying on the
use of nominals (O) and qualified cardinality restrictions (Q). In
this article we present a new algebraic tableau reasoning
procedure for the DL SHOQ that combines tableau procedures and
algebraic methods, namely linear integer programming, to ensure
arithmetically better informed reasoning procedures. SHOQ extends
the standard DL ALC (which is equivalent to the multi-modal logic
Km) with transitive roles, role hierarchies, qualified
cardinality restrictions, and nominals, and forms an expressive
subset of the web ontology language OWL 2. Although the proposed
algebraic tableau (in analogy to standard tableau) is still double
exponential in the worst case, it deals with cardinalities in a
very informed way due to its arithmetic component and can be
considered as a novel foundation for informed reasoning procedures
addressing cardinality restrictions.
AI Communications, Special
Issue on Practical Aspects of Automated Reasoning, Vol.
23, No. 2-3 (2010), pp. 205-240
Acrobat
file (preprint)
This article presents a hybrid Abox tableau calculus for SHQ
which extends the basic description logic ALC with role
hierarchies, transitive roles, and qualified number restrictions.
The prominent feature of our hybrid calculus is that it reduces
reasoning about qualified number restrictions to integer linear
programming. The calculus decides SHQ Abox consistency w.r.t. a
Tbox containing general axioms. The presented approach ensures a
more informed calculus which adequately handles the interaction
between numerical and logical restrictions in SHQ concept and
individual descriptions. A prototype reasoner for deciding ALCHQ
concept satisfiability has been implemented. An empirical
evaluation of our hybrid reasoner and its integrated optimization
techniques for a set of synthesized benchmarks featuring qualified
number restrictions clearly demonstrates the effectiveness of our
hybrid calculus.
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.
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.
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.
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.
Encyclopedia of Information
Science & Technology, 2nd edition, IGI Global,
2009, pp. 3439-3444.
Acrobat file (preprint)
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.
International Journal of
Approximate Reasoning,
Vol. 50, No. 9 (Nov. 2009), pp. 1399-1415.
Acrobat file (preprint)
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.
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.
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.
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.
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 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
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
Proceeding of the The First International Workshop on Question
Answering (QA2007) associated with the Third \International
Conference on Semantics, Knowledge, and Grid (SKG'07), Oct.
29-31, 2007, Xi'an, China, IEEE, 218-223.
Acrobat file
This paper describes an approach to resolve quantifiers and
number restrictions in natural language questions to query
ontologies. Incorporating this feature enables natural language
query interfaces to capture a wider range of user queries. To deal
with quantifiers and number restrictions, we analyzed a corpus of
such questions and derived constraints at the syntactic level to
recognize and parse them. The approach was implemented and
evaluated through a system called ONLI+. Our method has been
evaluated by conducting different experiments using the mean
reciprocal rank (MRR) measure. Experimental results show that this
feature has been incorporated into ONLI+ without degrading its
performance in terms of transforming natural language queries into
the nRQL queries, but definitely increases the expressivity of the
user. To the best of our knowledge no other natural language
interface to query ontologies can deal with quantifiers and number
restrictions.
Proceedings of the 2007 International Workshop on Description
Logics (DL2007), Brixen-Bressanone, near Bozen-Bolzano,
Italy, June 8-10, 2007, 558 pages.
Electronically available as CEUR
publication (Vol-250) here.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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
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.
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
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.
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
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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 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.
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.
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.
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).
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.
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
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.
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.
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.
In: KI - Zeitschrift für
Künstliche Intelligenz (special issue on Semantic Web), No.3,
July 2003, pp. 10-15.
Acrobat file (for preview)
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.
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.
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.
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.
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.
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.
Proceedings of the International KI-2002 Workshop on
Applications of Description Logics (ADL-2002), Aachen, Germany,
16. September 2002.
CEUR
Online Proceedings (Postscript files)
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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).
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 .
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).
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.
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
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.
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.
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.
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.
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.
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.
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.
Technical Report No.FBI-HH-M-288/99, University of
Hamburg,Computer Science Department , March 2000 (revised
version).
Postscript
file
Acrobat
file (for preview)
We present a new tableaux calculus deciding the ABox consistency problem for the expressive description logic ALCNHR+. Prominent language features of ALCNHR+ are number restrictions, role hierarchies, transitively closed roles, and generalized concept inclusions. The ABox description logic system RACE is based on the calculus for ALCNHR+.
Keywords---description logic, TBox and ABox reasoning, ABox tableaux calculus, RACE.
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.
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.
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.
In: Proc. of DL99 , International Workshop on Description Logics , Linköping, 1999, pp. 130-132.
Postscript
file
Acrobat
file (for preview)
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.
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.
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.
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.
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.
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.
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 .
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.
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)
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.