Balder Ten Cate
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Research Subjects
Balder Ten Cate has a total of 15 co-authors. Here are the top co-authors by number of shared publications:
- Jean Christoph Jung
TU Dortmund University
3 shared publications - Carsten Lutz
Leipzig University
2 shared publications - Maurice Funk
Leipzig University
2 shared publications - Ana Ozaki
University of Oslo
1 shared publication - Arie Soeteman
Fermioniq B.V Amsterdam NL
1 shared publication - Bart Bogaerts
KU Leuven
1 shared publication
Latest Publications
- Open Access
- 5 November 2026
- Published by Ubiquity Press, Ltd.
Theory and Applications of Craig Interpolation
Craig Interpolation and Beth Definability have played a central role in modern logic since the mid-twentieth century. Originating in William Craig’s and Evert Willem Beth’s pioneering work, they provide fundamental tools for understanding logical systems and how information can be transferred, transformed, or restricted within formal languages. Their impact extends across proof theory, model theory, philosophical logic, and computer science, where they illuminate both the power and the limitations of logical systems. This volume brings together leading researchers to offer a comprehensive and contemporary account of developments in interpolation and definability. The chapters range from classical insights to recent advances, covering a wide spectrum of topics. Readers will find in-depth investigations of interpolation in modal and superintuitionistic logics, algebraic perspectives on definability, and constructive approaches grounded in proof systems. Several contributions examine uniform interpolation and forgetting, shedding light on how logical content can be systematically simplified without losing relevant consequences. Others explore the crucial role of interpolation in automated reasoning, model checking, database querying, and ontology engineering, where interpolants serve as abstractors, separators, and explainers. A major theme of the volume is the meeting point between theory and application. While the contributors develop sophisticated mathematical techniques, they also demonstrate how these ideas support practical algorithms used in verification, querying, automated reasoning, and knowledge representation. The volume also pays tribute to Larisa Maksimova, whose groundbreaking work on interpolation in nonclassical logics continues to guide and inspire research in the field. Her contributions resonate through the topics discussed and the methods employed by many of the authors. Accessible to graduate students yet rich in material for specialists, this book offers an authoritative overview of Craig Interpolation and Beth Definability. It presents a broad and evolving research landscape, demonstrating how classical concepts remain essential in addressing contemporary questions about logical inference, expressiveness, and computation.
- 5 November 2026
- Published by Ubiquity Press, Ltd.
Open AccessTheory and Applications of Craig Interpolation
Craig Interpolation and Beth Definability have played a central role in modern logic since the mid-twentieth century. Originating in William Craig’s and Evert Willem Beth’s pioneering work, they provide fundamental tools for understanding logical systems and how information can be transferred, transformed, or restricted within formal languages. Their impact extends across proof theory, model theory, philosophical logic, and computer science, where they illuminate both the power and the limitations of logical systems. This volume brings together leading researchers to offer a comprehensive and contemporary account of developments in interpolation and definability. The chapters range from classical insights to recent advances, covering a wide spectrum of topics. Readers will find in-depth investigations of interpolation in modal and superintuitionistic logics, algebraic perspectives on definability, and constructive approaches grounded in proof systems. Several contributions examine uniform interpolation and forgetting, shedding light on how logical content can be systematically simplified without losing relevant consequences. Others explore the crucial role of interpolation in automated reasoning, model checking, database querying, and ontology engineering, where interpolants serve as abstractors, separators, and explainers. A major theme of the volume is the meeting point between theory and application. While the contributors develop sophisticated mathematical techniques, they also demonstrate how these ideas support practical algorithms used in verification, querying, automated reasoning, and knowledge representation. The volume also pays tribute to Larisa Maksimova, whose groundbreaking work on interpolation in nonclassical logics continues to guide and inspire research in the field. Her contributions resonate through the topics discussed and the methods employed by many of the authors. Accessible to graduate students yet rich in material for specialists, this book offers an authoritative overview of Craig Interpolation and Beth Definability. It presents a broad and evolving research landscape, demonstrating how classical concepts remain essential in addressing contemporary questions about logical inference, expressiveness, and computation.
- Open Access
How Expressive Are Graph Neural Networks in the Presence of Node Identifiers?
Graph neural networks (GNNs) are a widely used class of machine learning models for graph-structured data, based on local aggregation over neighbors. GNNs have close connections to logic. In particular, their expressive power is linked to that of modal logics and bounded-variable logics with counting. In many practical scenarios, graphs processed by GNNs have node features that act as unique identifiers. In this work, we study how such identifiers affect the expressive power of GNNs. We initiate a study of the key-invariant expressive power of GNNs, inspired by the notion of order-invariant definability in finite model theory: which node queries that depend only on the underlying graph structure can GNNs express on graphs with unique node identifiers? We provide answers for various classes of GNNs with local max- or sum-aggregation.
Open AccessHow Expressive Are Graph Neural Networks in the Presence of Node Identifiers?
Graph neural networks (GNNs) are a widely used class of machine learning models for graph-structured data, based on local aggregation over neighbors. GNNs have close connections to logic. In particular, their expressive power is linked to that of modal logics and bounded-variable logics with counting. In many practical scenarios, graphs processed by GNNs have node features that act as unique identifiers. In this work, we study how such identifiers affect the expressive power of GNNs. We initiate a study of the key-invariant expressive power of GNNs, inspired by the notion of order-invariant definability in finite model theory: which node queries that depend only on the underlying graph structure can GNNs express on graphs with unique node identifiers? We provide answers for various classes of GNNs with local max- or sum-aggregation.
- Open Access
- 29 August 2025
- Published by Centre pour la Communication Scientifique Directe (CCSD) in Logical Methods in Computer Science
- Vol. ume 21, Is
Craig Interpolation for Decidable First-Order Fragments
We show that the guarded-negation fragment is, in a precise sense, the smallest extension of the guarded fragment with Craig interpolation. In contrast, we show that full first-order logic is the smallest extension of both the two-variable fragment and the forward fragment with Craig interpolation. Similarly, we also show that all extensions of the two-variable fragment and of the fluted fragment with Craig interpolation are undecidable.
- 29 August 2025
- Published by Centre pour la Communication Scientifique Directe (CCSD) in Logical Methods in Computer Science
- Vol. ume 21, Is
Open AccessCraig Interpolation for Decidable First-Order Fragments
We show that the guarded-negation fragment is, in a precise sense, the smallest extension of the guarded fragment with Craig interpolation. In contrast, we show that full first-order logic is the smallest extension of both the two-variable fragment and the forward fragment with Craig interpolation. Similarly, we also show that all extensions of the two-variable fragment and of the fluted fragment with Craig interpolation are undecidable.
- Open Access
On the Power and Limitations of Examples for Description Logic Concepts
Labeled examples (i.e., positive and negative examples) are an attractive medium for communicating complex concepts. They are useful for deriving concept expressions (such as in concept learning, interactive concept specification, and concept refinement) as well as for illustrating concept expressions to a user or domain expert. We investigate the power of labeled examples for describing description-logic concepts. Specifically, we systematically study the existence and efficient computability of finite characterisations, i.e. finite sets of labeled examples that uniquely characterize a single concept, for a wide variety of description logics between EL and ALCQI, both without an ontology and in the presence of a DL-Lite ontology. Finite characterisations are relevant for debugging purposes, and their existence is a necessary condition for exact learnability with membership queries.
Open AccessOn the Power and Limitations of Examples for Description Logic Concepts
Labeled examples (i.e., positive and negative examples) are an attractive medium for communicating complex concepts. They are useful for deriving concept expressions (such as in concept learning, interactive concept specification, and concept refinement) as well as for illustrating concept expressions to a user or domain expert. We investigate the power of labeled examples for describing description-logic concepts. Specifically, we systematically study the existence and efficient computability of finite characterisations, i.e. finite sets of labeled examples that uniquely characterize a single concept, for a wide variety of description logics between EL and ALCQI, both without an ontology and in the presence of a DL-Lite ontology. Finite characterisations are relevant for debugging purposes, and their existence is a necessary condition for exact learnability with membership queries.
- Open Access
- 4 September 2024
- Published by Centre pour la Communication Scientifique Directe (CCSD) in Logical Methods in Computer Science
- Vol. ume 20, Is (3)
Preservation theorems for Tarski's relation algebra
We investigate a number of semantically defined fragments of Tarski's algebra of binary relations, including the function-preserving fragment. We address the question whether they are generated by a finite set of operations. We obtain several positive and negative results along these lines. Specifically, the homomorphism-safe fragment is finitely generated (both over finite and over arbitrary structures). The function-preserving fragment is not finitely generated (and, in fact, not expressible by any finite set of guarded second-order definable function-preserving operations). Similarly, the total-function-preserving fragment is not finitely generated (and, in fact, not expressible by any finite set of guarded second-order definable total-function-preserving operations). In contrast, the forward-looking function-preserving fragment is finitely generated by composition, intersection, antidomain, and preferential union. Similarly, the forward-and-backward-looking injective-function-preserving fragment is finitely generated by composition, intersection, antidomain, inverse, and an `injective union' operation.
- 4 September 2024
- Published by Centre pour la Communication Scientifique Directe (CCSD) in Logical Methods in Computer Science
- Vol. ume 20, Is (3)
Open AccessPreservation theorems for Tarski's relation algebra
We investigate a number of semantically defined fragments of Tarski's algebra of binary relations, including the function-preserving fragment. We address the question whether they are generated by a finite set of operations. We obtain several positive and negative results along these lines. Specifically, the homomorphism-safe fragment is finitely generated (both over finite and over arbitrary structures). The function-preserving fragment is not finitely generated (and, in fact, not expressible by any finite set of guarded second-order definable function-preserving operations). Similarly, the total-function-preserving fragment is not finitely generated (and, in fact, not expressible by any finite set of guarded second-order definable total-function-preserving operations). In contrast, the forward-looking function-preserving fragment is finitely generated by composition, intersection, antidomain, and preferential union. Similarly, the forward-and-backward-looking injective-function-preserving fragment is finitely generated by composition, intersection, antidomain, inverse, and an `injective union' operation.
- 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.