DROPS

Document

DOI: 10.4230/LIPIcs.CSL.2026.10

Disjunctions of Two Dependence Atoms

Authors: Nicolas Fröhlich, Phokion G. Kolaitis, and Arne Meier

Published in: LIPIcs, Volume 363, 34th EACSL Annual Conference on Computer Science Logic (CSL 2026)

Abstract

Dependence logic is a formalism that augments the syntax of first-order logic with dependence atoms asserting that the value of a variable is determined by the values of some other variables, i.e., dependence atoms express functional dependencies in relational databases. On finite structures, dependence logic captures NP, hence there are sentences of dependence logic whose model-checking problem is NP-complete. In fact, it is known that there are disjunctions of three dependence atoms whose model-checking problem is NP-complete. Motivated from considerations in database theory, we study the model-checking problem for disjunctions of two unary dependence atoms and establish a trichotomy theorem, namely, for every such formula, one of the following is true for the model-checking problem: (i) it is NL-complete; (ii) it is L-complete; (iii) it is first-order definable (hence, in AC⁰). Furthermore, we classify the complexity of the model-checking problem for disjunctions of two arbitrary dependence atoms, and also characterize when such a disjunction is coherent, i.e., when it satisfies a certain small-model property. Along the way, we identify a new class of 2CNF-formulas whose satisfiability problem is L-complete.

Cite as

Nicolas Fröhlich, Phokion G. Kolaitis, and Arne Meier. Disjunctions of Two Dependence Atoms. In 34th EACSL Annual Conference on Computer Science Logic (CSL 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 363, pp. 10:1-10:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{frohlich_et_al:LIPIcs.CSL.2026.10,
  author =	{Fr\"{o}hlich, Nicolas and Kolaitis, Phokion G. and Meier, Arne},
  title =	{{Disjunctions of Two Dependence Atoms}},
  booktitle =	{34th EACSL Annual Conference on Computer Science Logic (CSL 2026)},
  pages =	{10:1--10:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-411-6},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{363},
  editor =	{Guerrini, Stefano and K\"{o}nig, Barbara},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CSL.2026.10},
  URN =		{urn:nbn:de:0030-drops-254343},
  doi =		{10.4230/LIPIcs.CSL.2026.10},
  annote =	{Keywords: Dependence logic, coherence, model-checking, complexity, functional dependencies}
}

Document

DOI: 10.4230/DagRep.14.3.31

Logics for Dependence and Independence: Expressivity and Complexity (Dagstuhl Seminar 24111)

Authors: Juha Kontinen, Jonni Virtema, Heribert Vollmer, Fan Yang, and Nicolas Fröhlich

Published in: Dagstuhl Reports, Volume 14, Issue 3 (2024)

Abstract

This report documents the programme and outcomes of Dagstuhl Seminar "Logics for Dependence and Independence: Expressivity and Complexity" (24111). This seminar served as a follow-up seminar to the highly successful seminars "Dependence Logic: Theory and Applications" (13071), "Logics for Dependence and Independence" (15261) and "Logics for Dependence and Independence" (19031). A key objective of the seminar was to bring together researchers working in dependence logic and in application areas (for this edition with a particular emphasis on the areas of hyperproperties and formal linguistics), so that they can communicate state-of-the-art advances and embark on a systematic interaction. The goal was especially to reach those researchers who have recently started working in this thriving area, as well as researchers working on several aspects of complexity studies of team-based logics as well as expressivity issues, in particular in the just mentioned application areas. In particular, bringing together researchers from areas of theoretical studies with the application areas aimed at enhancing the synergy between the different communities working on dependence logic.

Cite as

Juha Kontinen, Jonni Virtema, Heribert Vollmer, Fan Yang, and Nicolas Fröhlich. Logics for Dependence and Independence: Expressivity and Complexity (Dagstuhl Seminar 24111). In Dagstuhl Reports, Volume 14, Issue 3, pp. 31-51, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@Article{kontinen_et_al:DagRep.14.3.31,
  author =	{Kontinen, Juha and Virtema, Jonni and Vollmer, Heribert and Yang, Fan and Fr\"{o}hlich, Nicolas},
  title =	{{Logics for Dependence and Independence: Expressivity and Complexity (Dagstuhl Seminar 24111)}},
  pages =	{31--51},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2024},
  volume =	{14},
  number =	{3},
  editor =	{Kontinen, Juha and Virtema, Jonni and Vollmer, Heribert and Yang, Fan and Fr\"{o}hlich, Nicolas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagRep.14.3.31},
  URN =		{urn:nbn:de:0030-drops-211827},
  doi =		{10.4230/DagRep.14.3.31},
  annote =	{Keywords: finite model theory, formal linguistics, hyperproperties, information theory, team semantics}
}

Search Results

Documents authored by Fröhlich, Nicolas

Disjunctions of Two Dependence Atoms

Abstract

Cite as

Logics for Dependence and Independence: Expressivity and Complexity (Dagstuhl Seminar 24111)

Abstract

Cite as

Thanks for your feedback!

Could not send message