55 citations · 114 across the 15 of their papers we have counts for
16 papers
Fitting and Learning Basis-Restricted Propositional Formulas
Balder ten Cate
For a finite set of Boolean functions, we consider the class of propositional formulas built using the functions in as connectives. We determine, for each possible choice o…
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,…
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…
Craig Interpolation for Decidable First-Order Fragments
Balder ten Cate, Jesse Comer
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-ord…
Preservation theorems for Tarski's relation algebra
Bart Bogaerts, Balder ten Cate, Brett McLean +1
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…
Craig Interpolation for Guarded Fragments
Balder ten Cate, Jesse Comer
We show that the guarded-negation fragment (GNFO) is, in a precise sense, the smallest extension of the guarded fragment (GFO) with Craig interpolation. In contrast, %we show that…
Characterising Modal Formulas with Examples
Balder ten Cate, Raoul Koudijs
We study the existence of finite characterisations for modal formulas. A finite characterisation of a modal formula is a finite collection of positive and negative examples tha…
Characterising Modal Formulas with Examples
Balder ten Cate, Raoul Koudijs
We initiate the study of finite characterizations and exact learnability of modal languages. A finite characterization of a modal formula w.r.t. a set of formulas is a finite set o…
Local Dependence and Guarding
Johan van Benthem, Balder ten Cate, Raoul Koudijs
We study LFD, a base logic of functional dependence introduced by Baltag and van Benthem (2021) and its connections with the guarded fragment GF of first-order logic. Like other lo…
Conjunctive Queries: Unique Characterizations and Exact Learnability
Balder ten Cate, Victor Dalmau
We answer the question which conjunctive queries are uniquely characterized by polynomially many positive and negative examples, and how to construct such examples efficiently. As…
High-Level Why-Not Explanations using Ontologies
Balder ten Cate, Cristina Civili, Evgeny Sherkhonov +1
We propose a novel foundational framework for why-not explanations, that is, explanations for why a tuple is missing from a query result. Our why-not explanations leverage concepts…
Unary negation
Luc Segoufin, Balder ten Cate
We study fragments of first-order logic and of least fixed point logic that allow only unary negation: negation of formulas with at most one free variable. These logics generalize…
Ontology-based Data Access: A Study through Disjunctive Datalog, CSP, and MMSNP
Meghyn Bienvenu, Balder ten Cate, Carsten Lutz +1
Ontology-based data access is concerned with querying incomplete data sources in the presence of domain-specific knowledge provided by an ontology. A central notion in this setting…
Complete Axiomatizations of Fragments of Monadic Second-Order Logic on Finite Trees
Amélie Gheerbrant, Balder ten Cate
We consider a specific class of tree structures that can represent basic structures in linguistics and computer science such as XML documents, parse trees, and treebanks, namely, f…
Queries with Guarded Negation (full version)
Vince Barany, Balder ten Cate, Martin Otto
A well-established and fundamental insight in database theory is that negation (also known as complementation) tends to make queries difficult to process and difficult to reason ab…
Lindstrom theorems for fragments of first-order logic
Johan van Benthem, Balder ten Cate, Jouko Vaananen
Lindström theorems characterize logics in terms of model-theoretic conditions such as Compactness and the Löwenheim-Skolem property. Most existing characterizations of this kind co…