{"id":91,"date":"2022-06-13T11:23:52","date_gmt":"2022-06-13T11:23:52","guid":{"rendered":"https:\/\/staff.fnwi.uva.nl\/b.d.tencate\/?page_id=91"},"modified":"2026-04-17T11:53:23","modified_gmt":"2026-04-17T11:53:23","slug":"publications","status":"publish","type":"page","link":"https:\/\/staff.fnwi.uva.nl\/b.d.tencate\/publications\/","title":{"rendered":"Recent Publications"},"content":{"rendered":"\n<p class=\"has-small-font-size\">For older publications, see <a href=\"https:\/\/dblp.org\/pid\/91\/5696.html?view=by-year\">DBLP<\/a> or <a href=\"https:\/\/scholar.google.com\/citations?user=DeFaEH8AAAAJ&amp;hl=nl\">Google Scholar<\/a>.<\/p>\n\n\n\n<p class=\"has-small-font-size\">Note: Most of my publications have been in venues and research communities where it is common for the list of authors to be sorted <em>alphabetically<\/em> (in which case, according to Dutch customs, the surname &#8220;ten Cate&#8221; 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.<\/p>\n\n\n\n<p class=\"has-small-font-size\">Under submission <\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li class=\"has-small-font-size\">A. Soeteman, M. Benedikt, M. Grohe and B. ten Cate (2026). <strong>How Expressive Are Graph Neural Networks in the Presence of Node Identifiers?<\/strong> Under submission (<a href=\"https:\/\/arxiv.org\/abs\/2601.21882\" data-type=\"link\" data-id=\"https:\/\/arxiv.org\/abs\/2601.21882\">arxiv<\/a>)<\/li>\n\n\n\n<li class=\"has-small-font-size\">J. van Benthem, B. ten Cate and X. Yang (2026). <strong>When do modal definability and preservation theorems transfer to the finite? <\/strong>Under submission (<a href=\"https:\/\/arxiv.org\/pdf\/2603.12171\">arxiv<\/a>).<\/li>\n\n\n\n<li class=\"has-small-font-size\">N. Bezhanishvili, B. ten Cate, A. Ganguly, A. Meier (2026). <strong>Modal Fragments<\/strong>. Under submission (<a href=\"https:\/\/arxiv.org\/pdf\/2603.05055\">arxiv<\/a>)<\/li>\n<\/ul>\n\n\n\n<p class=\"has-small-font-size\">2026:<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li class=\"has-small-font-size\">B. ten Cate, L. Kuijer and F. Wolter (2026). <strong>The Size of Interpolants in Modal Logics<\/strong>. <em>LICS 2026, to appear<\/em>. (<a href=\"https:\/\/arxiv.org\/abs\/2511.04577\" data-type=\"link\" data-id=\"https:\/\/arxiv.org\/abs\/2511.04577\">arxiv<\/a>)<\/li>\n<\/ul>\n\n\n\n<p class=\"has-small-font-size\">2025:<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li class=\"has-small-font-size\">A. Soeteman and B. ten Cate (2025). <strong>Logical Expressiveness of Graph Neural Networks with Hierarchical Node Individualization<\/strong>. <em><a href=\"https:\/\/openreview.net\/pdf\/6cfd19a72b630a4f75244b37e5c5fcf9470121e5.pdf\">NeurIPS 2025<\/a><\/em>.<\/li>\n\n\n\n<li class=\"has-small-font-size\">B. ten Cate, Ph. Kolaitis, and A. Kristj\u00e1nsson (2025). <strong>Adaptive Query Algorithms for Relational Structures Based on Homomorphism Counts<\/strong>. <em><a href=\"https:\/\/drops.dagstuhl.de\/entities\/document\/10.4230\/LIPIcs.MFCS.2025.34\">Proceedings of MFCS 2025<\/a> <\/em>(<a href=\"https:\/\/arxiv.org\/pdf\/2504.16567\">arxiv full version<\/a>).<\/li>\n\n\n\n<li class=\"has-small-font-size\">B. ten Cate, Ph. Kolaitis, and C. Lutz (2025). <strong>Query Repairs<\/strong>. <em><a href=\"https:\/\/drops.dagstuhl.de\/storage\/00lipics\/lipics-vol328-icdt2025\/LIPIcs.ICDT.2025.15\/LIPIcs.ICDT.2025.15.pdf\">Proceedings of ICDT 2025<\/a><\/em>. (<a href=\"https:\/\/arxiv.org\/abs\/2501.11162\">arxiv full version<\/a>).<\/li>\n\n\n\n<li class=\"has-small-font-size\">B. ten Cate and T. Kapp\u00e9 (2025). <strong>Algebras for Deterministic Computation are Inherently&nbsp;Incomplete<\/strong>. <em><a href=\"https:\/\/dl.acm.org\/doi\/10.1145\/3704861\">Proceedings of the ACM on Programming Languages 9:25<\/a> (POPL 2025)<\/em>.<\/li>\n\n\n\n<li class=\"has-small-font-size\">B. ten Cate and J. Comer (2025). <strong>Craig Interpolation for Decidable First-Order Fragments<\/strong>. <em><a href=\"https:\/\/lmcs.episciences.org\/16436\">Logical Methods in Computer Science<\/a><\/em> <em>21(3): 22:1-22:23.<\/em><\/li>\n<\/ul>\n\n\n\n<p class=\"has-small-font-size\">2024:<\/p>\n\n\n\n<ul class=\"wp-block-list has-small-font-size\">\n<li>B. Bogaerts, B. ten Cate, B. McLean, and J. Van den Bussche (2024). <strong>Preservation theorems for Tarski&#8217;s relation algebra<\/strong>. <em><a href=\"https:\/\/doi.org\/10.46298\/lmcs-20(3:20)2024\">Logical Methods in Computer Science<\/a><\/em> 20(3): 20:1\u201320:17.<\/li>\n\n\n\n<li>B. ten Cate and R. Koudijs (2024).<strong> Characterising Modal Formulas with Examples<\/strong>. <em><a href=\"https:\/\/maestro.acm.org\/trk\/clickp?ref=z16l2snue3_2-2edaa_0x33ae25x0596&amp;doi=3649461\" data-type=\"URL\" data-id=\"https:\/\/maestro.acm.org\/trk\/clickp?ref=z16l2snue3_2-2edaa_0x33ae25x0596&amp;doi=3649461\">ACM Transactions on Computational Logic<\/a> 25(2): 12:1 &#8211; 12:27.<\/em><\/li>\n\n\n\n<li>B. ten Cate, M. Funk, J. Ch. Jung, and C. Lutz (2024). <strong>On the Non-Efficient PAC Learnability of Conjunctive Queries<\/strong>. <em><a href=\"https:\/\/www.sciencedirect.com\/science\/article\/pii\/S0020019023000741\" data-type=\"URL\" data-id=\"https:\/\/www.sciencedirect.com\/science\/article\/pii\/S0020019023000741\">Information Processsing Letters 183: 106431<\/a>.<\/em><\/li>\n\n\n\n<li>B. ten Cate, R. Koudijs, and A. Ozaki (2024). <strong>On the Power and Limitations of Examples for Description Logic Concepts<\/strong>. <em><a href=\"https:\/\/www.ijcai.org\/proceedings\/2024\/395\">Proceedings of IJCAI 2024<\/a><\/em>.<\/li>\n\n\n\n<li>B. ten Cate, V. Dalmau, and J. Opr\u0161al (2024). <strong>Right-Adjoints for Datalog Programs<\/strong>. <em><a href=\"https:\/\/drops.dagstuhl.de\/entities\/document\/10.4230\/LIPIcs.ICDT.2024.10\">Proceedings of ICDT 2024<\/a><\/em>. (<a href=\"https:\/\/staff.fnwi.uva.nl\/b.d.tencate\/wp-content\/uploads\/2025\/05\/icdt24-datalog-adjoints-full.pdf\">full version pdf<\/a>).<\/li>\n\n\n\n<li>B. ten Cate, V. Dalmau, Ph. Kolaitis, W. Wu (2024). <strong>When do Homomorphism Counts Help in Query Algorithms?<\/strong> <em><a href=\"https:\/\/doi.org\/10.4230\/LIPIcs.ICDT.2024.8\">Proceedings of ICDT 2024<\/a>.<\/em> <\/li>\n\n\n\n<li>B. ten Cate and J. Comer (2024). <strong>Craig Interpolation for Decidable First-Order Fragments<\/strong>. <em><a href=\"https:\/\/link.springer.com\/chapter\/10.1007\/978-3-031-57231-9_7\">Proceedings of FOSSACS 2024<\/a><\/em>. <strong>\ud83e\udd47<\/strong><mark style=\"background-color:#ffdf27\" class=\"has-inline-color\"><a href=\"https:\/\/etaps.org\/awards\/best-paper\/\">ETAPS<\/a><\/mark><mark style=\"background-color:#ffdf27\" class=\"has-inline-color\"><a href=\"https:\/\/etaps.org\/awards\/best-paper\/\"> <\/a><\/mark><mark style=\"background-color:#ffdf27\" class=\"has-inline-color\"><a href=\"https:\/\/etaps.org\/awards\/best-paper\/\">Best Paper Nomination<\/a><\/mark> <\/li>\n\n\n\n<li>B. ten Cate (2024). <strong>Craig Interpolation for Decidable Fragments of First-Order Logic<\/strong>. <em><a href=\"https:\/\/drops.dagstuhl.de\/entities\/document\/10.4230\/LIPIcs.CSL.2024.2\">Proceedings of CSL 2024<\/a>.<\/em> <strong>\ud83e\udd47<\/strong><mark style=\"background-color:#ffdf27\" class=\"has-inline-color\">Invited Lecture<\/mark><\/li>\n\n\n\n<li>B. ten Cate, R. Koudijs, and A. Ozaki (2024). <strong>On the Power and Limitations of Examples for Description Logic Concepts (Extended Abstract)<\/strong>. <em><a href=\"https:\/\/ceur-ws.org\/Vol-3739\/abstract-9.pdf\">Description Logic Workshop 2024<\/a><\/em>.<\/li>\n\n\n\n<li>B. ten Cate and A. Ganguly (2024). <strong>Characterizing Formulas via Post&#8217;s Lattice<\/strong>.<em> <a href=\"https:\/\/iiia.csic.es\/tacl2024\/abstracts\/conference\/book_abstracts_TACL24.pdf\">Extended abstract presented at TACL 2024<\/a>. <\/em><\/li>\n<\/ul>\n\n\n\n<p class=\"has-small-font-size\">2023:<\/p>\n\n\n\n<ul class=\"wp-block-list has-dark-gray-color has-text-color has-small-font-size\">\n<li>B. ten Cate, M. Funk, J. Ch. Jung, and C. Lutz (2023). <strong>Fitting Algorithms for Conjunctive Queries<\/strong>. <em><a href=\"https:\/\/sigmodrecord.org\/publications\/sigmodRecord\/2312\/pdfs\/03_Principles_tenCate.pdf\">SIGMOD Record 52(4): 6-18 (Database Principles column)<\/a>.<\/em><strong>\ud83e\udd47<\/strong><mark style=\"background-color:#ffdf27\" class=\"has-inline-color\"><a href=\"https:\/\/sigmod.org\/sigmod-awards\/sigmod-research-highlights\/\">ACM SIGMOD Research Highlights Award Paper<\/a><\/mark><\/li>\n\n\n\n<li>B. ten Cate, M. Funk, J. Ch. Jung, and C. Lutz (2023). <strong>SAT-Based PAC Learning of Description Logic Concepts<\/strong>.  <em><a href=\"https:\/\/www.ijcai.org\/proceedings\/2023\/373\" data-type=\"URL\" data-id=\"https:\/\/www.ijcai.org\/proceedings\/2023\/373\">Proceedings of IJCAI 2023<\/a>.<\/em> (<a href=\"https:\/\/arxiv.org\/abs\/2305.08511\">arxiv<\/a>).   <strong>\ud83e\udd47<\/strong><mark style=\"background-color:#ffdf27\" class=\"has-inline-color\"><a href=\"https:\/\/ijcai-23.org\/distinguished-paper-awards\/\">Distinguished Paper Award<\/a><\/mark><\/li>\n\n\n\n<li>B. ten Cate, V. Dalmau, M. Funk, and C. Lutz (2023). <strong>Extremal Fitt\u001ding Problems for Conjunctive Queries<\/strong>. <em><a href=\"https:\/\/dl.acm.org\/doi\/10.1145\/3584372.3588655\">Proceedings of PODS 2023<\/a><\/em> (<a href=\"https:\/\/arxiv.org\/pdf\/2206.05080.pdf\">arxiv<\/a>).  <strong> \ud83e\udd47<\/strong><mark style=\"background-color:#ffdf27\" class=\"has-inline-color\"><a href=\"https:\/\/sigmod.org\/pods-home\/pods-best-paper-awards\/\">Best Paper Award<\/a><\/mark><\/li>\n\n\n\n<li>B. ten Cate, M. Funk, J. Ch. Jung, and C. Lutz. (2023) <strong>SAT-Based PAC Learning of Description Logic Concepts (Extended Abstract)<\/strong>. <em><a href=\"https:\/\/ceur-ws.org\/Vol-3515\/\">Description Logic Workshop 2023<\/a>. <\/em><\/li>\n\n\n\n<li>B. Bogaerts, B. ten Cate, B. McLean, and J. Van den Bussche (2023). <strong>Preservation theorems for Tarski&#8217;s relation algebra<\/strong>. <em>Presentation at DaL\u00ed 2023<\/em>. (<a href=\"https:\/\/arxiv.org\/abs\/2305.04656\">arxiv<\/a>). <\/li>\n\n\n\n<li>B. ten Cate and J. Comer (2023). <strong>Craig Interpolation for Guarded Fragments<\/strong>. <em>Presentation at the LICS Workshop on the Decision Problem in First-Order Logic (DPFO 2023)<\/em> (<a href=\"https:\/\/arxiv.org\/abs\/2304.08086\">arxiv<\/a>).<\/li>\n\n\n\n<li>B. ten Cate, M. Funk, J. Ch. Jung, and C. Lutz (2023). <strong>Extremal Fitting CQs do not Generalize<\/strong>. <em>Technical Report<a href=\"https:\/\/arxiv.org\/abs\/2312.03407\"> arXiv cs.DB 2312.03407<\/a><\/em>.<\/li>\n\n\n\n<li>B. ten Cate, V. Dalmau, and J. Opr\u0161al (2023) <strong>Right-Adjoints for Datalog Programs, and Homomorphism Dualities over Restricted Classes<\/strong>. <em>Technical Report <a href=\"https:\/\/arxiv.org\/pdf\/2302.06366.pdf\">arXiv cs.LO 2302.06366<\/a><\/em>.<\/li>\n<\/ul>\n\n\n\n<p class=\"has-text-color has-link-color has-small-font-size wp-elements-a7f40faa5cca29d2901db904c71a7a0e\" style=\"color:#aaaaaa\">2022:<\/p>\n\n\n\n<ul class=\"wp-block-list has-small-font-size\">\n<li class=\"has-text-color has-link-color wp-elements-91918040ca58daad36f02c714769e90c\" style=\"color:#aaaaaa\">B. ten Cate and V. Dalmau (2022). <strong>Conjunctive Queries: Unique Characterizations and Exact Learnability<\/strong>. <em><a href=\"https:\/\/dl.acm.org\/doi\/10.1145\/3559756\">ACM Transactions on Database Systems 47(4): 14:1 &#8211; 14:41<\/a>. <\/em>(<a href=\"https:\/\/arxiv.org\/abs\/2008.06824\">arxiv<\/a>).<\/li>\n\n\n\n<li class=\"has-text-color has-link-color wp-elements-ede1e4e6c14449ae8162822afecf476a\" style=\"color:#aaaaaa\">J. van Benthem, B. ten Cate, and R. Koudijs (2022). <strong>Local Dependence and Guarding<\/strong>. <em><a href=\"http:\/\/www.collegepublications.co.uk\/aiml\/?00011\">Proceedings of AIML 2022<\/a><\/em>:&nbsp;135-154 (<a href=\"https:\/\/arxiv.org\/abs\/2206.06046\">arxiv<\/a>).<\/li>\n\n\n\n<li class=\"has-text-color has-link-color wp-elements-0d928cb79373502fcc90dbaaac74940c\" style=\"color:#aaaaaa\">B. ten Cate and R. Koudijs (2022). <strong>Characterising Modal Formulas with Examples<\/strong>. <em>Short presentation at AIML 2022<\/em> (<a href=\"https:\/\/arxiv.org\/abs\/2206.06049\">arxiv<\/a>).<\/li>\n\n\n\n<li class=\"has-text-color has-link-color wp-elements-050024b9e9cb1551898717b5e348d242\" style=\"color:#aaaaaa\">B. ten Cate (2022). <strong>Lyndon Interpolation for Modal Logic via Type Elimination Sequences<\/strong>. <em>ILLC Technical Report <a href=\"https:\/\/eprints.illc.uva.nl\/id\/eprint\/1869\/4\/interpolation_mosaics%20%285%29.pdf\">X-2022-01<\/a><\/em>.<\/li>\n<\/ul>\n\n\n\n<p class=\"has-text-color has-link-color has-small-font-size wp-elements-2db21b036c3902e5e9ec52284d837350\" style=\"color:#cccccc\">2021:<\/p>\n\n\n\n<ul class=\"wp-block-list has-small-font-size\">\n<li class=\"has-text-color has-link-color wp-elements-b6e28c838877bf864a35009b95fdf5b6\" style=\"color:#cccccc\">B. ten Cate and V. Dalmau (2021). <strong>Conjunctive Queries: Unique Characterizations and Exact Learnability<\/strong>. <a href=\"https:\/\/drops.dagstuhl.de\/opus\/volltexte\/2021\/13717\/\"><em>Proceedings of ICDT 2021<\/em><\/a>:9:1-9:24.<\/li>\n\n\n\n<li class=\"has-text-color has-link-color wp-elements-47fca4a84f055b075593a45a5c3e8709\" style=\"color:#cccccc\">M. Benedikt, P. Bourhis, B. ten Cate, G. Puppis, and M. Vanden Boom (2021). <strong>Inference from Visible Information and Background Knowledge<\/strong>. <a href=\"https:\/\/dl.acm.org\/doi\/10.1145\/3452919\"><em>ACM Transactions on Computational Logic<\/em> <em>22(2): 13:1-13:69<\/em><\/a>.<\/li>\n<\/ul>\n\n\n\n<p class=\"has-small-font-size\"><\/p>\n\n\n\n<p><\/p>\n","protected":false},"excerpt":{"rendered":"<p>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 &#8220;ten Cate&#8221; is sorted under C), while others are in venues or areas [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"parent":0,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"","meta":{"footnotes":""},"class_list":["post-91","page","type-page","status-publish","hentry","post-preview"],"_links":{"self":[{"href":"https:\/\/staff.fnwi.uva.nl\/b.d.tencate\/wp-json\/wp\/v2\/pages\/91","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/staff.fnwi.uva.nl\/b.d.tencate\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/staff.fnwi.uva.nl\/b.d.tencate\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/staff.fnwi.uva.nl\/b.d.tencate\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/staff.fnwi.uva.nl\/b.d.tencate\/wp-json\/wp\/v2\/comments?post=91"}],"version-history":[{"count":160,"href":"https:\/\/staff.fnwi.uva.nl\/b.d.tencate\/wp-json\/wp\/v2\/pages\/91\/revisions"}],"predecessor-version":[{"id":597,"href":"https:\/\/staff.fnwi.uva.nl\/b.d.tencate\/wp-json\/wp\/v2\/pages\/91\/revisions\/597"}],"wp:attachment":[{"href":"https:\/\/staff.fnwi.uva.nl\/b.d.tencate\/wp-json\/wp\/v2\/media?parent=91"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}