Recent Publications

For older publications, see DBLP or Google Scholar.

Note: Most of my publications have been in venues and research communities where it is common for the list of authors to be sorted alphabetically (in which case, according to Dutch customs, the surname “ten Cate” is sorted under C), while others are in venues or areas (such as machine learning) where the author list is ordered by contribution, similarly as in the life sciences.

Under submission

• A. Soeteman, B. ten Cate, M. Funk, B. Kumelfeld, C. Lutz, M. Schönherr. Neuro-Relational Programs: Unifying Queries and Neural Computation over Structured Data. Under submission (arxiv)
• M. Schönherr, B. ten Cate, M. Funk, B. Kimelfeld and C. Lutz, A. Soeteman. Expressive Power of Deep Homomorphism Networks over Relational Databases. Under submission. (arxiv)
• A. Soeteman, M. Benedikt, M. Grohe and B. ten Cate (2026). How Expressive Are Graph Neural Networks in the Presence of Node Identifiers? Under submission (arxiv)
• J. van Benthem, B. ten Cate and X. Yang (2026). When do modal definability and preservation theorems transfer to the finite? Under submission (arxiv)
• N. Bezhanishvili, B. ten Cate, A. Ganguly, A. Meier (2026). Modal Fragments. Under submission (arxiv)

To appear in 2026:

• B. ten Cate, V. Dalmau, M. Funk, and C. Lutz (2026). Extremal Fitting Problems for Conjunctive Queries. Communications of the ACM (Research Highlights)
• B. ten Cate, J. Ch. Jung, P. Koopmann, Ch. Wernhard and and F. Wolter, eds (2026). Theory and Applications of Craig Interpolation. Ubiquity Press. (announcement, preprints)
• B. ten Cate and J. Comer. Interpolation in First-Order Logic. In: Theory and Applications of Craig Interpolation. Ubiquity Press. (arxiv)
• N. Bezhanishvili, B. ten Cate, and R. Iemhoff. Six Proofs of Interpolation for the Modal Logic K. In: Theory and Applications of Craig Interpolation. Ubiquity Press. (arxiv)
• J. van Benthem, B. ten Cate and X. Yang. Modal definability questions in the finite. In: K. Bimbo and E. Mares (eds.), In Honor of Rob Goldblatt: Papers on Algebraic and Philosophical Logic. College Publications.

2026:

• B. ten Cate, L. Kuijer and F. Wolter (2026). The Size of Interpolants in Modal Logics. Proceedings of LICS 2026. (arxiv)
• B. ten Cate, D. Fisman, R. Ohayon, P. Sestic (2026). Characterizing LTL Formulas by Examples. Proceedings of MFCS 2025. (arxiv)

2025:

• A. Soeteman and B. ten Cate (2025). Logical Expressiveness of Graph Neural Networks with Hierarchical Node Individualization. NeurIPS 2025.
• B. ten Cate, Ph. Kolaitis, and A. Kristjánsson (2025). Adaptive Query Algorithms for Relational Structures Based on Homomorphism Counts. Proceedings of MFCS 2025 (arxiv full version).
• B. ten Cate, Ph. Kolaitis, and C. Lutz (2025). Query Repairs. Proceedings of ICDT 2025. (arxiv full version).
• B. ten Cate and T. Kappé (2025). Algebras for Deterministic Computation are Inherently Incomplete. Proceedings of the ACM on Programming Languages 9:25 (POPL 2025).
• B. ten Cate and J. Comer (2025). Craig Interpolation for Decidable First-Order Fragments. Logical Methods in Computer Science 21(3): 22:1-22:23.

2024:

• B. Bogaerts, B. ten Cate, B. McLean, and J. Van den Bussche (2024). Preservation theorems for Tarski’s relation algebra. Logical Methods in Computer Science 20(3): 20:1–20:17.
• B. ten Cate and R. Koudijs (2024). Characterising Modal Formulas with Examples. ACM Transactions on Computational Logic 25(2): 12:1 – 12:27.
• B. ten Cate, M. Funk, J. Ch. Jung, and C. Lutz (2024). On the Non-Efficient PAC Learnability of Conjunctive Queries. Information Processsing Letters 183: 106431.
• B. ten Cate, R. Koudijs, and A. Ozaki (2024). On the Power and Limitations of Examples for Description Logic Concepts. Proceedings of IJCAI 2024.
• B. ten Cate, V. Dalmau, and J. Opršal (2024). Right-Adjoints for Datalog Programs. Proceedings of ICDT 2024. (full version pdf).
• B. ten Cate, V. Dalmau, Ph. Kolaitis, W. Wu (2024). When do Homomorphism Counts Help in Query Algorithms? Proceedings of ICDT 2024.
• B. ten Cate and J. Comer (2024). Craig Interpolation for Decidable First-Order Fragments. Proceedings of FOSSACS 2024. 🥇ETAPS Best Paper Nomination
• B. ten Cate (2024). Craig Interpolation for Decidable Fragments of First-Order Logic. Proceedings of CSL 2024. 🥇Invited Lecture
• B. ten Cate, R. Koudijs, and A. Ozaki (2024). On the Power and Limitations of Examples for Description Logic Concepts (Extended Abstract). Description Logic Workshop 2024.
• B. ten Cate and A. Ganguly (2024). Characterizing Formulas via Post’s Lattice. Extended abstract presented at TACL 2024.

2023:

• B. ten Cate, M. Funk, J. Ch. Jung, and C. Lutz (2023). Fitting Algorithms for Conjunctive Queries. SIGMOD Record 52(4): 6-18 (Database Principles column).🥇ACM SIGMOD Research Highlights Award Paper
• B. ten Cate, M. Funk, J. Ch. Jung, and C. Lutz (2023). SAT-Based PAC Learning of Description Logic Concepts. Proceedings of IJCAI 2023. (arxiv). 🥇Distinguished Paper Award
• B. ten Cate, V. Dalmau, M. Funk, and C. Lutz (2023). Extremal Fitting Problems for Conjunctive Queries. Proceedings of PODS 2023 (arxiv). 🥇Best Paper Award
• B. ten Cate, M. Funk, J. Ch. Jung, and C. Lutz. (2023) SAT-Based PAC Learning of Description Logic Concepts (Extended Abstract). Description Logic Workshop 2023.
• B. Bogaerts, B. ten Cate, B. McLean, and J. Van den Bussche (2023). Preservation theorems for Tarski’s relation algebra. Presentation at DaLí 2023. (arxiv).
• B. ten Cate and J. Comer (2023). Craig Interpolation for Guarded Fragments. Presentation at the LICS Workshop on the Decision Problem in First-Order Logic (DPFO 2023) (arxiv).
• B. ten Cate, M. Funk, J. Ch. Jung, and C. Lutz (2023). Extremal Fitting CQs do not Generalize. Technical Report arXiv cs.DB 2312.03407.
• B. ten Cate, V. Dalmau, and J. Opršal (2023) Right-Adjoints for Datalog Programs, and Homomorphism Dualities over Restricted Classes. Technical Report arXiv cs.LO 2302.06366.

2022:

• B. ten Cate and V. Dalmau (2022). Conjunctive Queries: Unique Characterizations and Exact Learnability. ACM Transactions on Database Systems 47(4): 14:1 – 14:41. (arxiv).
• J. van Benthem, B. ten Cate, and R. Koudijs (2022). Local Dependence and Guarding. Proceedings of AIML 2022: 135-154 (arxiv).
• B. ten Cate and R. Koudijs (2022). Characterising Modal Formulas with Examples. Short presentation at AIML 2022 (arxiv).
• B. ten Cate (2022). Lyndon Interpolation for Modal Logic via Type Elimination Sequences. ILLC Technical Report X-2022-01.

2021:

• B. ten Cate and V. Dalmau (2021). Conjunctive Queries: Unique Characterizations and Exact Learnability. Proceedings of ICDT 2021:9:1-9:24.
• M. Benedikt, P. Bourhis, B. ten Cate, G. Puppis, and M. Vanden Boom (2021). Inference from Visible Information and Background Knowledge. ACM Transactions on Computational Logic 22(2): 13:1-13:69.