17 citations · 49 across the 23 of their papers we have counts for
10 papers · 1 filter
When do modal definability and preservation theorems transfer to the finite?
Johan van Benthem, Balder ten Cate, Xi Yang
We study which classic modal definability and preservation results survive when attention is restricted to finite structures, where many first-order transfer theorems are known to…
How Expressive Are Graph Neural Networks in the Presence of Node Identifiers?
Arie Soeteman, Michael Benedikt, Martin Grohe +1
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…
Six Proofs of Interpolation for the Modal Logic K
Nick Bezhanishvili, Balder ten Cate, Rosalie Iemhoff
In this chapter, we present six different proofs of Craig interpolation for the modal logic K, each using a different set of techniques (model-theoretic, proof-theoretic, syntactic…
Interpolation in First-Order Logic
Balder ten Cate, Jesse Comer
In this chapter we give a basic overview of known results regarding Craig interpolation for first-order logic as well as for fragments of first-order logic. Our aim is to provide a…
Adaptive Query Algorithms for Relational Structures Based on Homomorphism Counts
Balder ten Cate, Phokion G. Kolaitis, Arnar Á. Kristjánsson
A query algorithm based on homomorphism counts is a procedure to decide membership for a class of finite relational structures using only homomorphism count queries. A left query a…
On the Power and Limitations of Examples for Description Logic Concepts
Balder ten Cate, Raoul Koudijs, Ana Ozaki
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 co…