Search Results

Documents authored by ten Cate, Balder


Document
Invited Talk
Craig Interpolation for Decidable Fragments of First-Order Logic (Invited Talk)

Authors: Balder ten Cate

Published in: LIPIcs, Volume 288, 32nd EACSL Annual Conference on Computer Science Logic (CSL 2024)


Abstract
The Craig Interpolation Property (CIP) is a property of logics. It states that, for all formulas φ and ψ, if φ ⊧ ψ, then there exists an "interpolant" ϑ such that φ ⊧ ϑ and ϑ ⊧ ψ, and such that all non-logical symbols occurring in ϑ occur both in φ and in ψ. Craig [Craig, 1957] proved in 1957 that first-order logic (FO) has this property. Since then, many refinements of Craig’s result have been obtained (e.g., [Otto, 2000; Benedikt et al., 2016]). These have found applications in various areas of computer science and AI, including formal verification, modular hard/software specification and automated deduction [McMillan, 2018; Calvanese et al., 2020; Hoder et al., 2012], and more recently prominently in databases [Toman and Weddell, 2011; Benedikt et al., 2016] and knowledge representation [Lutz and Wolter, 2011; ten Cate et al., 2013; Koopmann and Schmidt, 2015]. In this invited talk, we will survey recent work pertaining to Craig interpolation for various important decidable fragment of first-order logic, including guarded fragments, finite-variable fragments, and ordered fragments. Most of these fragments lack the CIP (the guarded-negation fragment GNFO being a notable exception [Bárány et al., 2013]). We will discuss strategies that have been proposed in recent literature to deal with this lack of CIP, as well as recent results that shed light on where, within the landscape of decidable fragment of first-order logic, one may find logics that enjoy CIP [Jung and Wolter, 2021; ten Cate and Comer, 2023].

Cite as

Balder ten Cate. Craig Interpolation for Decidable Fragments of First-Order Logic (Invited Talk). In 32nd EACSL Annual Conference on Computer Science Logic (CSL 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 288, pp. 2:1-2:2, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)


Copy BibTex To Clipboard

@InProceedings{tencate:LIPIcs.CSL.2024.2,
  author =	{ten Cate, Balder},
  title =	{{Craig Interpolation for Decidable Fragments of First-Order Logic}},
  booktitle =	{32nd EACSL Annual Conference on Computer Science Logic (CSL 2024)},
  pages =	{2:1--2:2},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-310-2},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{288},
  editor =	{Murano, Aniello and Silva, Alexandra},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CSL.2024.2},
  URN =		{urn:nbn:de:0030-drops-196488},
  doi =		{10.4230/LIPIcs.CSL.2024.2},
  annote =	{Keywords: First-Order Logic, Decidable Fragments, Craig Interpolation}
}
Document
Conjunctive Queries: Unique Characterizations and Exact Learnability

Authors: Balder ten Cate and Victor Dalmau

Published in: LIPIcs, Volume 186, 24th International Conference on Database Theory (ICDT 2021)


Abstract
We answer the question of which conjunctive queries are uniquely characterized by polynomially many positive and negative examples, and how to construct such examples efficiently. As a consequence, we obtain a new efficient exact learning algorithm for a class of conjunctive queries. At the core of our contributions lie two new polynomial-time algorithms for constructing frontiers in the homomorphism lattice of finite structures. We also discuss implications for the unique characterizability and learnability of schema mappings and of description logic concepts.

Cite as

Balder ten Cate and Victor Dalmau. Conjunctive Queries: Unique Characterizations and Exact Learnability. In 24th International Conference on Database Theory (ICDT 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 186, pp. 9:1-9:24, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)


Copy BibTex To Clipboard

@InProceedings{tencate_et_al:LIPIcs.ICDT.2021.9,
  author =	{ten Cate, Balder and Dalmau, Victor},
  title =	{{Conjunctive Queries: Unique Characterizations and Exact Learnability}},
  booktitle =	{24th International Conference on Database Theory (ICDT 2021)},
  pages =	{9:1--9:24},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-179-5},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{186},
  editor =	{Yi, Ke and Wei, Zhewei},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2021.9},
  URN =		{urn:nbn:de:0030-drops-137172},
  doi =		{10.4230/LIPIcs.ICDT.2021.9},
  annote =	{Keywords: Conjunctive Queries, Homomorphisms, Frontiers, Unique Characterizations, Exact Learnability, Schema Mappings, Description Logic}
}
Document
Declarative Probabilistic Programming with Datalog

Authors: Vince Barany, Balder ten Cate, Benny Kimelfeld, Dan Olteanu, and Zografoula Vagena

Published in: LIPIcs, Volume 48, 19th International Conference on Database Theory (ICDT 2016)


Abstract
Probabilistic programming languages are used for developing statistical models, and they typically consist of two components: a specification of a stochastic process (the prior), and a specification of observations that restrict the probability space to a conditional subspace (the posterior). Use cases of such formalisms include the development of algorithms in machine learning and artificial intelligence. We propose and investigate an extension of Datalog for specifying statistical models, and establish a declarative probabilistic-programming paradigm over databases. Our proposed extension provides convenient mechanisms to include common numerical probability functions; in particular, conclusions of rules may contain values drawn from such functions. The semantics of a program is a probability distribution over the possible outcomes of the input database with respect to the program. Observations are naturally incorporated by means of integrity constraints over the extensional and intensional relations. The resulting semantics is robust under different chases and invariant to rewritings that preserve logical equivalence.

Cite as

Vince Barany, Balder ten Cate, Benny Kimelfeld, Dan Olteanu, and Zografoula Vagena. Declarative Probabilistic Programming with Datalog. In 19th International Conference on Database Theory (ICDT 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 48, pp. 7:1-7:19, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2016)


Copy BibTex To Clipboard

@InProceedings{barany_et_al:LIPIcs.ICDT.2016.7,
  author =	{Barany, Vince and ten Cate, Balder and Kimelfeld, Benny and Olteanu, Dan and Vagena, Zografoula},
  title =	{{Declarative Probabilistic Programming with Datalog}},
  booktitle =	{19th International Conference on Database Theory (ICDT 2016)},
  pages =	{7:1--7:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-002-6},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{48},
  editor =	{Martens, Wim and Zeume, Thomas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2016.7},
  URN =		{urn:nbn:de:0030-drops-57761},
  doi =		{10.4230/LIPIcs.ICDT.2016.7},
  annote =	{Keywords: Chase, Datalog, probability measure space, probabilistic programming}
}
Document
The Product Homomorphism Problem and Applications

Authors: Balder ten Cate and Victor Dalmau

Published in: LIPIcs, Volume 31, 18th International Conference on Database Theory (ICDT 2015)


Abstract
The product homomorphism problem (PHP) takes as input a finite collection of structures A_1, ..., A_n and a structure B, and asks if there is a homomorphism from the direct product between A_1, A_2, ..., and A_n, to B. We pinpoint the computational complexity of this problem. Our motivation stems from the fact that PHP naturally arises in different areas of database theory. In particular, it is equivalent to the problem of determining whether a relation is definable by a conjunctive query, and the existence of a schema mapping that fits a given collection of positive and negative data examples. We apply our results to obtain complexity bounds for these problems.

Cite as

Balder ten Cate and Victor Dalmau. The Product Homomorphism Problem and Applications. In 18th International Conference on Database Theory (ICDT 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 31, pp. 161-176, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)


Copy BibTex To Clipboard

@InProceedings{tencate_et_al:LIPIcs.ICDT.2015.161,
  author =	{ten Cate, Balder and Dalmau, Victor},
  title =	{{The Product Homomorphism Problem and Applications}},
  booktitle =	{18th International Conference on Database Theory (ICDT 2015)},
  pages =	{161--176},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-79-8},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{31},
  editor =	{Arenas, Marcelo and Ugarte, Mart{\'\i}n},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2015.161},
  URN =		{urn:nbn:de:0030-drops-49832},
  doi =		{10.4230/LIPIcs.ICDT.2015.161},
  annote =	{Keywords: Homomorphisms, Direct Product, Data Examples, Definability, Conjunctive Queries, Schema Mappings}
}
Document
Querying and Reasoning Under Expressive Constraints (Dagstuhl Seminar 14331)

Authors: Michael Benedikt, Carsten Lutz, and Balder Ten Cate

Published in: Dagstuhl Reports, Volume 4, Issue 8 (2015)


Abstract
This report documents the program and the outcomes of Dagstuhl Seminar 14331 "Querying and Reasoning Under Expressive Constraints" which took place from August 10th to August 14th, 2014. The seminar aimed to bring together researchers in databases, knowledge representation, decidable fragments of first-order logic, and constraint satisfaction to identify and discuss common themes and technique as well as complementary ones, identify future research issues, and foster cooperation and cross-fertilization between the communities.

Cite as

Michael Benedikt, Carsten Lutz, and Balder Ten Cate. Querying and Reasoning Under Expressive Constraints (Dagstuhl Seminar 14331). In Dagstuhl Reports, Volume 4, Issue 8, pp. 1-20, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2014)


Copy BibTex To Clipboard

@Article{benedikt_et_al:DagRep.4.8.1,
  author =	{Benedikt, Michael and Lutz, Carsten and Ten Cate, Balder},
  title =	{{Querying and Reasoning Under Expressive Constraints (Dagstuhl Seminar 14331)}},
  pages =	{1--20},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2014},
  volume =	{4},
  number =	{8},
  editor =	{Benedikt, Michael and Lutz, Carsten and Ten Cate, Balder},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagRep.4.8.1},
  URN =		{urn:nbn:de:0030-drops-47941},
  doi =		{10.4230/DagRep.4.8.1},
  annote =	{Keywords: Integrity constraints, Open-World Query Answering, Ontology-Based Data Access, Knowledge Representation, Automated Reasoning, Decidable Fragments of}
}
Document
Unary negation

Authors: Balder ten Cate and Luc Segoufin

Published in: LIPIcs, Volume 9, 28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011)


Abstract
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 many interesting known formalisms, including modal logic and the mu-calculus, as well as conjunctive queries and monadic Datalog. We show that satisfiability and finite satisfiability are decidable for both fragments, and we pinpoint the complexity of satisfiability, finite satisfiability, and model checking. We also show that the unary negation fragment of first-order logic is model-theoretically very well behaved. In particular, it enjoys Craig interpolation and the Beth property.

Cite as

Balder ten Cate and Luc Segoufin. Unary negation. In 28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011). Leibniz International Proceedings in Informatics (LIPIcs), Volume 9, pp. 344-355, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2011)


Copy BibTex To Clipboard

@InProceedings{tencate_et_al:LIPIcs.STACS.2011.344,
  author =	{ten Cate, Balder and Segoufin, Luc},
  title =	{{Unary negation}},
  booktitle =	{28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011)},
  pages =	{344--355},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-25-5},
  ISSN =	{1868-8969},
  year =	{2011},
  volume =	{9},
  editor =	{Schwentick, Thomas and D\"{u}rr, Christoph},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2011.344},
  URN =		{urn:nbn:de:0030-drops-30256},
  doi =		{10.4230/LIPIcs.STACS.2011.344},
  annote =	{Keywords: Decidability, Logic, Unary negation}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail