15 papers
Neuro-Relational Programs: Unifying Queries and Neural Computation over Structured Data
Arie Soeteman, Balder ten Cate, Maurice Funk +3
The conventional approach to deep learning over relational databases applies neural models, such as Graph Neural Networks (GNNs), to a graph representation of the database. Recent…
Expressive Power of Deep Homomorphism Networks over Relational Databases
Moritz Schönherr, Balder ten Cate, Maurice Funk +3
The expressive limitations of message-passing Graph Neural Networks (GNNs) have motivated a wide range of more powerful graph learning architectures. We advocate Deep Homomorphism…
The Size of Interpolants in Modal Logics
Balder ten Cate, Louwe Kuijer, Frank Wolter
We start a systematic investigation of the size of Craig interpolants, uniform interpolants, and strongest implicates for (quasi-)normal modal logics. Our main upper bound states t…
Characterizing LTL Formulas by Examples (full version)
Balder ten Cate, Dana Fisman, Roi Ohayon +1
We investigate the extent to which Linear Temporal Logic (LTL) formulas can be uniquely characterized by a finite set of labeled examples. We consider different types of examples,…
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…
Modal Fragments
Nick Bezhanishvili, Balder ten Cate, Arunavo Ganguly +1
We survey systematic approaches to basis-restricted fragments of propositional logic and modal logics, with an emphasis on how expressive power and computational complexity depend…