11 papers · 1 filter
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…
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…