Birte Glimm

ECAI Conference 2025 Conference Paper

Calculating Optimal Corrections for Unsolvable Planning Problems

• Michael Welt
• Alexander Lodemann
• Conny Olz
• Pascal Bercher
• Birte Glimm

Detecting and resolving unsolvable planning problems is an active research area that has recently received increased attention. Nevertheless, unsolvability remains a significant challenge, particularly when it comes to efficiently identifying potential causes for a problem’s unsolvability. To address this challenge, we propose a method that computes modifications to the planning task. Specifically, given an unsolvable planning problem, our approach identifies a cardinality-minimal set of state variables whose removal renders the problem solvable. Existing literature typically relies on subset enumeration to identify such sets. While effective for small variable sets, we find that this approach becomes impractical for larger sets due to its high computational cost. To overcome this limitation, we introduce a novel method based on hitting set duality, a well-established technique for solving various combinatorial problems. Our results show that this new approach consistently outperforms subset enumeration for medium-sized and large result sets. We validate the effectiveness of our method through experiments on modified problems from the 2016 International Planning Competition on Unsolvability.

IJCAI Conference 2022 Conference Paper

Computing Concept Referring Expressions for Queries on Horn ALC Ontologies

• Moritz Illich
• Birte Glimm

Classical instance queries over an ontology only consider explicitly named individuals. Concept referring expressions (CREs) also allow for returning answers in the form of concepts that describe implicitly given individuals in terms of their relation to an explicitly named one. Existing approaches, e. g. , based on tree automata, can neither be integrated into state-of-the-art OWL reasoners nor are they directly amenable for an efficient implementation. To address this, we devise a novel algorithm that uses highly optimized OWL reasoners as a black box. In addition to the standard criteria of singularity and certainty for CREs, we devise and consider the criterion of uniqueness of CREs for Horn ALC ontologies. The evaluation of our prototypical implementation shows that computing CREs for the most general concept (Top) can be done in less than one minute for ontologies with thousands of individuals and concepts.

ICAPS Conference 2020 Conference Paper

New Developments for Robert - Assisting Novice Users Even Better in DIY Projects

• Gregor Behnke
• Pascal Bercher
• Matthias Kraus 0001
• Marvin R. G. Schiller
• Kristof Mickeleit
• Timo Häge
• Michael Dorna
• Michael Dambier

Do-It-Yourself (DIY) home improvement projects require a combination of specific knowledge and practical abilities. Novice users often lack both and thus tend to fail or be frightful of performing DIY projects – even though they would like to. By providing suitable and individualised assistance in the form of step-by-step instructions, the assistant Robert allows even novice users to successfully complete their DIY projects. Simultaneously, Robert allows its users to learn how to perform these steps themselves and thus enables them to become more independent in the future. In this paper, we report on the latest progress with Robert. Compared to earlier versions, Robert is now able to adaptively change its instructions based on the wishes and preferences of the user. Further, Robert is now able to use connected tools – i. e. tools that are able to sense and communicate their status – to check whether the user is performing the project's steps correctly and to provide further assistance in the case of failure. Lastly, we present the results of an empirical study conducted to show Robert's effectiveness.

IJCAI Conference 2018 Conference Paper

Embracing Change by Abstraction Materialization Maintenance for Large ABoxes

• Markus Brenner
• Birte Glimm

Abstraction Refinement is a recently introduced technique which allows for reducing materialization of an ontology with a large ABox to materialization of a smaller (compressed) `abstraction' of this ontology. In this paper, we show how Abstraction Refinement can be adopted for incremental ABox materialization by combining it with the well-known DRed algorithm for materialization maintenance. Such a combination is non-trivial and to preserve soundness and completeness, already Horn ALCHI requires more complex abstractions. Nevertheless, we show that significant benefits can be obtained for synthetic and real-world ontologies.

IJCAI Conference 2018 Conference Paper

Instructing Novice Users on How to Use Tools in DIY Projects

• Gregor Behnke
• Marvin Schiller
• Matthias Kraus
• Pascal Bercher
• Mario Schmautz
• Michael Dorna
• Wolfgang Minker
• Birte Glimm

Novice users require assistance when performing handicraft tasks. Adequate instruction ensures task completion and conveys knowledge and abilities required to perform the task. We present an assistant teaching novice users how to operate electronic tools, such as drills, saws, and sanders, in the context of Do-It-Yourself (DIY) home improvement projects. First, the actions that need to be performed for the project are determined by a planner. Second, a dialogue manager capable of natural language interaction presents these actions as instructions to the user. Third, questions on these actions and involved objects are answered by generating appropriate ontology-based explanations.

AAAI Conference 2017 Conference Paper

Ontology Materialization by Abstraction Refinement in Horn SHOIF

• Birte Glimm
• Yevgeny Kazakov
• Trung-Kien Tran

Abstraction refinement is a recently introduced technique using which reasoning over large ABoxes is reduced to reasoning over small ‘abstract’ ABoxes. Although the approach is sound for any classical Description Logic such as SROIQ, it is complete only for Horn ALCHOI. In this paper, we propose an extension of this method that is now complete for Horn SHOIF and also handles role- and equalitymaterialization. To show completeness, we use a tailored set of materialization rules that loosely decouple the ABox from the TBox. An empirical evaluation demonstrates that, despite the new features, the abstractions are still significantly smaller than the original ontologies and the materialization can be computed efficiently.

ECAI Conference 2016 Conference Paper

Exploring Parallel Tractability of Ontology Materialization

• Zhangquan Zhou
• Guilin Qi
• Birte Glimm

Materialization is an important reasoning service for applications built on the Web Ontology Language (OWL). To make materialization efficient in practice, current research focuses on deciding tractability of an ontology language and designing parallel reasoning algorithms. However, some well-known large-scale ontologies, such as YAGO, have been shown to have good performance for parallel reasoning, but they are expressed in ontology languages that are not parallelly tractable, i. e. , the reasoning is inherently sequential in the worst case. This motivates us to study the problem of parallel tractability of ontology materialization from a theoretical perspective. That is, we aim to identify the ontologies for which materialization is parallelly tractable, i. e. , in NC complexity. In this work, we focus on datalog rewritable ontology languages. We identify several classes of datalog rewritable ontologies (called parallelly tractable classes) such that materialization over them is parallelly tractable. We further investigate the parallel tractability of materialization of a datalog rewritable OWL fragment DHL (Description Horn Logic) and an extension of DHL that allows complex role inclusion axioms. Based on the above results, we analyze real-world datasets and show that many ontologies expressed in DHL or its extension belong to the parallelly tractable classes.

IJCAI Conference 2015 Conference Paper

Coherence Across Components in Cognitive Systems - One Ontology to Rule Them All

• Gregor Behnke
• Denis Ponomaryov
• Marvin Schiller
• Pascal Bercher
• Florian Nothdurft
• Birte Glimm
• Susanne Biundo

The integration of the various specialized components of cognitive systems poses a challenge, in particular for those architectures that combine planning, inference, and human-computer interaction (HCI). An approach is presented that exploits a single source of common knowledge contained in an ontology. Based upon the knowledge contained in it, specialized domain models for the cognitive systems’ components can be generated automatically. Our integration targets planning in the form of hierarchical planning, being well-suited for HCI as it mimics planning done by humans. We show how the hierarchical structures of such planning domains can be (partially) inferred from declarative background knowledge. The same ontology furnishes the structure of the interaction between the cognitive system and the user. First, explanations of plans presented to users are enhanced by ontology explanations. Second, a dialog domain is created from the ontology coherent with the planning domain. We demonstrate the application of our technique in a fitness training scenario.

AAAI Conference 2015 Conference Paper

Lower and Upper Bounds for SPARQL Queries over OWL Ontologies

• Birte Glimm
• Yevgeny Kazakov
• Ilianna Kollia
• Giorgos Stamou

The paper presents an approach for optimizing the evaluation of SPARQL queries over OWL ontologies using SPARQL’s OWL Direct Semantics entailment regime. The approach is based on the computation of lower and upper bounds, but we allow for much more expressive queries than related approaches. In order to optimize the evaluation of possible query answers in the upper but not in the lower bound, we present a query extension approach that uses schema knowledge from the queried ontology to extend the query with additional parts. We show that the resulting query is equivalent to the original one and we use the additional parts that are simple to evaluate for restricting the bounds of subqueries of the initial query. In an empirical evaluation we show that the proposed query extension approach can lead to a significant decrease in the query execution time of up to four orders of magnitude.

JAIR Journal 2015 Journal Article

Pay-As-You-Go Description Logic Reasoning by Coupling Tableau and Saturation Procedures

• Andreas Steigmiller
• Birte Glimm

Nowadays, saturation-based reasoners for the OWL EL profile of the Web Ontology Language are able to handle large ontologies such as SNOMED very efficiently. However, it is currently unclear how saturation-based reasoning procedures can be extended to very expressive Description Logics such as SROIQ--the logical underpinning of the current and second iteration of the Web Ontology Language. Tableau-based procedures, on the other hand, are not limited to specific Description Logic languages or OWL profiles, but even highly optimised tableau-based reasoners might not be efficient enough to handle large ontologies such as SNOMED. In this paper, we present an approach for tightly coupling tableau- and saturation-based procedures that we implement in the OWL DL reasoner Konclude. Our detailed evaluation shows that this combination significantly improves the reasoning performance for a wide range of ontologies.

IJCAI Conference 2013 Conference Paper

Nominal Schema Absorption

• Andreas Steigmiller
• Birte Glimm
• Thorsten Liebig

Nominal schemas have recently been introduced as a new approach for the integration of DL-safe rules into the Description Logic framework. The efficient processing of knowledge bases with nominal schemas remains, however, challenging. We address this by extending the well-known optimisation of absorption as well as the standard tableau calculus to directly handle the (absorbed) nominal schema axioms. We implement the resulting extension of standard tableau calculi in a novel reasoning system and we integrate further optimisations. In our empirical evaluation, we show the effect of these optimisations and we find that the proposed approach performs well even when compared to other DL reasoners with dedicated rule support.

IJCAI Conference 2011 Conference Paper

Reasoning-Supported Interactive Revision of Knowledge Bases

• Nadeschda Nikitina
• Sebastian Rudolph
• Birte Glimm

Quality control is an essential task within ontology development projects especially when the knowledge formalization is partially automatized. In this paper, we propose a reasoning-based, interactive approach to support the revision of formalized knowledge. We state consistency criteria for revision states and introduce the notion of revision closure, based on which the revision of ontologies is partially automatized. Additionally, we propose a notion of axiom impact which is used to determine a beneficial order of axiom evaluation in order to further increase the effectiveness of ontology revision. Finally, we develop the notion of decision spaces, which are structures for calculating and updating the revision closure and axiom impact. The use of decision spaces saves on average 75% of the costly reasoning operations during a revision.

KR Conference 2010 Conference Paper

Status QIO: Conjunctive Query Entailment is Decidable

• Birte Glimm
• Sebastian Rudolph

Description Logics (DLs) are knowledge representation formalisms that provide, for example, the logical underpinning of the W3C OWL standards. Conjunctive queries (CQs), the standard query language in databases, have recently gained significant attention for querying DL knowledge bases. Several different techniques are available for a wide range of DLs. Nevertheless, for OWL 1 DL and OWL 2 DL, decidability of CQ entailment is an open problem. So far, the combination of nominals, inverse roles, and number restrictions caused unsolvable problems. We tackle this problem and present a decidability result for entailment of unions of CQs in a DL with all three problematic constructors. For queries with only simple roles, our result also shows decidability in the logic that underpins OWL 1 DL and we believe that the presented results will pave the way for further progress towards CQ entailment decision procedures for OWL.

LPAR Conference 2008 Conference Paper

Role Conjunctions in Expressive Description Logics

• Birte Glimm
• Yevgeny Kazakov

Abstract We show that adding role conjunctions to the Description Logics (DLs) \(\mathcal{SHI}\) and \(\mathcal{SHOIF}\) causes a jump in the computational complexity of the standard reasoning tasks from ExpTime -complete to 2ExpTime -complete and from NExpTime -complete to N2ExpTime -hard respectively. We further show that this increase is due to a subtle interaction between inverse roles, role hierarchies, and role transitivity in the presence of role conjunctions and that for the DL \(\mathcal{SHQ}\) a jump in the computational complexity cannot be observed.

KR Conference 2008 Conference Paper

Unions of Conjunctive Queries in SHOQ

• Birte Glimm
• Ian Horrocks
• Ulrike Sattler

Conjunctive queries play an important role as an expressive query language in Description Logics (DLs). Decision procedures for expressive Description Logics are, however, only recently emerging and it is still an open question whether answering conjunctive queries is decidable for the DL SHOIQ that underlies the OWL DL standard. In fact, no decision procedure was known for expressive DLs that contain nominals. In this paper, we close this gap by providing a decision procedure for entailment of unions of conjunctive queries in SHOQ. Our algorithm runs in deterministic time single exponential in the size of the knowledge base and double exponential in the size of the query, which is the same as for SHIQ. Our procedure also shows that SHOQ knowledge base consistency is indeed ExpTime-complete, which was, to the best of our knowledge, always conjectured but never proved.

IJCAI Conference 2007 Conference Paper

• Birte Glimm
• Ian Horrocks
• Carsten Lutz
• Ulrike Sattler

Conjunctive queries play an important role as an expressive query language for Description Logics (DLs). Although modern DLs usually provide for transitive roles, it was an open problem whether conjunctive query answering over DL knowledge bases is decidable if transitive roles are admitted in the query. In this paper, we consider conjunctive queries over knowledge bases formulated in the popular DL SHIQ and allow transitive roles in both the query and the knowledge base. We show that query answering is decidable and establish the following complexity bounds: regarding combined complexity, we devise a deterministic algorithm for query answering that needs time single exponential in the size of the KB and double exponential in the size of the query. Regarding data complexity, we prove co-NP-completeness.