Carsten Lutz
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Research Subjects
Carsten Lutz has a total of 6 co-authors. Here are the top co-authors by number of shared publications:
- Jean Christoph Jung
TU Dortmund University
4 shared publications - Maurice Funk
Leipzig University
3 shared publications - Balder Ten Cate
Institute for Logic, Language and Computation (ILLC) University of Amsterdam
2 shared publications - Quentin Manière
Department of Computer Science Leipzig University Germany
2 shared publications - Simon Hosemann
Leipzig University
2 shared publications - Sebastian Rudolph
TU Dresden
1 shared publication
Latest Publications
- Open Access
- 1 November 2025
- Published by International Joint Conferences on Artificial Intelligence
- Vol. 22 (1) , 407-416
Fitting Ontologies and Constraints to Relational Structures
We study the problem of fitting ontologies and constraints to positive and negative examples that take the form of a finite relational structure. As ontology and constraint languages, we consider the description logics EL and ELI as well as several classes of tuple-generating dependencies (TGDs): full, guarded, frontier-guarded, frontier-one, and unrestricted TGDs as well as inclusion dependencies. We pinpoint the exact computational complexity, design algorithms, and analyze the size of fitting ontologies and TGDs. We also investigate the related problem of constructing a finite basis of concept inclusions / TGDs for a given set of finite structures. While finite bases exist for EL, ELI, guarded TGDs, and inclusion dependencies, they in general do not exist for full, frontier-guarded and frontier-one TGDs.
- 1 November 2025
- Published by International Joint Conferences on Artificial Intelligence
- Vol. 22 (1) , 407-416
Open AccessFitting Ontologies and Constraints to Relational Structures
We study the problem of fitting ontologies and constraints to positive and negative examples that take the form of a finite relational structure. As ontology and constraint languages, we consider the description logics EL and ELI as well as several classes of tuple-generating dependencies (TGDs): full, guarded, frontier-guarded, frontier-one, and unrestricted TGDs as well as inclusion dependencies. We pinpoint the exact computational complexity, design algorithms, and analyze the size of fitting ontologies and TGDs. We also investigate the related problem of constructing a finite basis of concept inclusions / TGDs for a given set of finite structures. While finite bases exist for EL, ELI, guarded TGDs, and inclusion dependencies, they in general do not exist for full, frontier-guarded and frontier-one TGDs.
- Open Access
- 1 November 2024
- Published by International Joint Conferences on Artificial Intelligence
- Vol. 21 (1) , 531-541
Adding Circumscription to Decidable Fragments of First-Order Logic: A Complexity Rollercoaster
We study extensions of expressive decidable fragments of first-order logic with circumscription, considering in particular the two-variable fragment FO^2, its extension C^2 with counting quantifiers, and the guarded fragment GF. We prove that if only unary predicates are minimized (or fixed) during circumscription, then decidability of logical consequence is preserved. For FO^2 the complexity increases from NExp to NExp^NP-complete, for GF it (remarkably!) increases from 2Exp to Tower-complete, and for C^2 it remains open. We also consider querying circumscribed knowledge bases whose ontology is a GF sentence, showing that the problem is decidable for unions of conjunctive queries, Tower-complete in combined complexity, and elementary in data complexity. Already for atomic queries and ontologies that are sets of guarded existential rules, however, for every k > 0 there is an ontology and query that are k-Exp-hard in data complexity.
- 1 November 2024
- Published by International Joint Conferences on Artificial Intelligence
- Vol. 21 (1) , 531-541
Open AccessAdding Circumscription to Decidable Fragments of First-Order Logic: A Complexity Rollercoaster
We study extensions of expressive decidable fragments of first-order logic with circumscription, considering in particular the two-variable fragment FO^2, its extension C^2 with counting quantifiers, and the guarded fragment GF. We prove that if only unary predicates are minimized (or fixed) during circumscription, then decidability of logical consequence is preserved. For FO^2 the complexity increases from NExp to NExp^NP-complete, for GF it (remarkably!) increases from 2Exp to Tower-complete, and for C^2 it remains open. We also consider querying circumscribed knowledge bases whose ontology is a GF sentence, showing that the problem is decidable for unions of conjunctive queries, Tower-complete in combined complexity, and elementary in data complexity. Already for atomic queries and ontologies that are sets of guarded existential rules, however, for every k > 0 there is an ontology and query that are k-Exp-hard in data complexity.
- Open Access
Adding Circumscription to Decidable Fragments of First-Order Logic: A Complexity Rollercoaster
We study extensions of expressive decidable fragments of first-order logic with circumscription, in particular the two-variable fragment FO$^2$, its extension C$^2$ with counting quantifiers, and the guarded fragment GF. We prove that if only unary predicates are minimized (or fixed) during circumscription, then decidability of logical consequence is preserved. For FO$^2$ the complexity increases from $\textrm{coNexp}$ to $\textrm{coNExp}^\textrm{NP}$-complete, for GF it (remarkably!) increases from $\textrm{2Exp}$ to $\textrm{Tower}$-complete, and for C$^2$ the complexity remains open. We also consider querying circumscribed knowledge bases whose ontology is a GF sentence, showing that the problem is decidable for unions of conjunctive queries, $\textrm{Tower}$-complete in combined complexity, and elementary in data complexity. Already for atomic queries and ontologies that are sets of guarded existential rules, however, for every $k \geq 0$ there is an ontology and query that are $k$-$\textrm{Exp}$-hard in data complexity.Open AccessAdding Circumscription to Decidable Fragments of First-Order Logic: A Complexity Rollercoaster
We study extensions of expressive decidable fragments of first-order logic with circumscription, in particular the two-variable fragment FO$^2$, its extension C$^2$ with counting quantifiers, and the guarded fragment GF. We prove that if only unary predicates are minimized (or fixed) during circumscription, then decidability of logical consequence is preserved. For FO$^2$ the complexity increases from $\textrm{coNexp}$ to $\textrm{coNExp}^\textrm{NP}$-complete, for GF it (remarkably!) increases from $\textrm{2Exp}$ to $\textrm{Tower}$-complete, and for C$^2$ the complexity remains open. We also consider querying circumscribed knowledge bases whose ontology is a GF sentence, showing that the problem is decidable for unions of conjunctive queries, $\textrm{Tower}$-complete in combined complexity, and elementary in data complexity. Already for atomic queries and ontologies that are sets of guarded existential rules, however, for every $k \geq 0$ there is an ontology and query that are $k$-$\textrm{Exp}$-hard in data complexity. - Open Access
Towards Ontology Construction with Language Models
We present a method for automatically constructing a concept hierarchy for a given domain by querying a large language model. We apply this method to various domains using OpenAI's GPT 3.5. Our experiments indicate that LLMs can be of considerable help for constructing concept hierarchies.
Open AccessTowards Ontology Construction with Language Models
We present a method for automatically constructing a concept hierarchy for a given domain by querying a large language model. We apply this method to various domains using OpenAI's GPT 3.5. Our experiments indicate that LLMs can be of considerable help for constructing concept hierarchies.
- Open Access
- 1 August 2023
- Published by International Joint Conferences on Artificial Intelligence
- Vol. 3, 3347-3355
SAT-Based PAC Learning of Description Logic Concepts
We propose bounded fitting as a scheme for learning description logic concepts in the presence of ontologies. A main advantage is that the resulting learning algorithms come with theoretical guarantees regarding their generalization to unseen examples in the sense of PAC learning. We prove that, in contrast, several other natural learning algorithms fail to provide such guarantees. As a further contribution, we present the system SPELL which efficiently implements bounded fitting for the description logic ELHr based on a SAT solver, and compare its performance to a state-of-the-art learner.
- 1 August 2023
- Published by International Joint Conferences on Artificial Intelligence
- Vol. 3, 3347-3355
Open AccessSAT-Based PAC Learning of Description Logic Concepts
We propose bounded fitting as a scheme for learning description logic concepts in the presence of ontologies. A main advantage is that the resulting learning algorithms come with theoretical guarantees regarding their generalization to unseen examples in the sense of PAC learning. We prove that, in contrast, several other natural learning algorithms fail to provide such guarantees. As a further contribution, we present the system SPELL which efficiently implements bounded fitting for the description logic ELHr based on a SAT solver, and compare its performance to a state-of-the-art learner.
- Open Access
SAT-Based PAC Learning of Description Logic Concepts
We propose bounded fitting as a scheme for learning description logic concepts in the presence of ontologies. A main advantage is that the resulting learning algorithms come with theoretical guarantees regarding their generalization to unseen examples in the sense of PAC learning. We prove that, in contrast, several other natural learning algorithms fail to provide such guarantees. As a further contribution, we present the system SPELL which efficiently implements bounded fitting for the description logic $\mathcal{ELH}^r$ based on a SAT solver, and compare its performance to a state-of-the-art learner.Open AccessSAT-Based PAC Learning of Description Logic Concepts
We propose bounded fitting as a scheme for learning description logic concepts in the presence of ontologies. A main advantage is that the resulting learning algorithms come with theoretical guarantees regarding their generalization to unseen examples in the sense of PAC learning. We prove that, in contrast, several other natural learning algorithms fail to provide such guarantees. As a further contribution, we present the system SPELL which efficiently implements bounded fitting for the description logic $\mathcal{ELH}^r$ based on a SAT solver, and compare its performance to a state-of-the-art learner.