DROPS

Document

DOI: 10.4230/LIPIcs.CSL.2020.22

Guarded Teams: The Horizontally Guarded Case

Authors: Erich Grädel and Martin Otto

Published in: LIPIcs, Volume 152, 28th EACSL Annual Conference on Computer Science Logic (CSL 2020)

Abstract

Team semantics admits reasoning about large sets of data, modelled by sets of assignments (called teams), with first-order syntax. This leads to high expressive power and complexity, particularly in the presence of atomic dependency properties for such data sets. It is therefore interesting to explore fragments and variants of logic with team semantics that permit model-theoretic tools and algorithmic methods to control this explosion in expressive power and complexity. We combine here the study of team semantics with the notion of guarded logics, which are well-understood in the case of classical Tarski semantics, and known to strike a good balance between expressive power and algorithmic manageability. In fact there are two strains of guardedness for teams. Horizontal guardedness requires the individual assignments of the team to be guarded in the usual sense of guarded logics. Vertical guardedness, on the other hand, posits an additional (or definable) hypergraph structure on relational structures in order to interpret a constraint on the component-wise variability of assignments within teams. In this paper we investigate the horizontally guarded case. We study horizontally guarded logics for teams and appropriate notions of guarded team bisimulation. In particular, we establish characterisation theorems that relate invariance under guarded team bisimulation with guarded team logics, but also with logics under classical Tarski semantics.

Cite as

Erich Grädel and Martin Otto. Guarded Teams: The Horizontally Guarded Case. In 28th EACSL Annual Conference on Computer Science Logic (CSL 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 152, pp. 22:1-22:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{gradel_et_al:LIPIcs.CSL.2020.22,
  author =	{Gr\"{a}del, Erich and Otto, Martin},
  title =	{{Guarded Teams: The Horizontally Guarded Case}},
  booktitle =	{28th EACSL Annual Conference on Computer Science Logic (CSL 2020)},
  pages =	{22:1--22:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-132-0},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{152},
  editor =	{Fern\'{a}ndez, Maribel and Muscholl, Anca},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CSL.2020.22},
  URN =		{urn:nbn:de:0030-drops-116650},
  doi =		{10.4230/LIPIcs.CSL.2020.22},
  annote =	{Keywords: Team semantics, guarded logics, bisimulation, characterisation theorems}
}

Document

DOI: 10.4230/LIPIcs.ICDT.2019.19

Additive First-Order Queries

Authors: Gerald Berger, Martin Otto, Andreas Pieris, Dimitri Surinx, and Jan Van den Bussche

Published in: LIPIcs, Volume 127, 22nd International Conference on Database Theory (ICDT 2019)

Abstract

A database query q is called additive if q(A U B) = q(A) U q(B) for domain-disjoint input databases A and B. Additivity allows the computation of the query result to be parallelised over the connected components of the input database. We define the "connected formulas" as a syntactic fragment of first-order logic, and show that a first-order query is additive if and only if it expressible by a connected formula. This characterisation specializes to the guarded fragment of first-order logic. We also show that additivity is decidable for formulas of the guarded fragment, establish the computational complexity, and do the same for positive-existential formulas. Our results hold when restricting attention to finite structures, as is common in database theory, but also hold in the unrestricted setting.

Cite as

Gerald Berger, Martin Otto, Andreas Pieris, Dimitri Surinx, and Jan Van den Bussche. Additive First-Order Queries. In 22nd International Conference on Database Theory (ICDT 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 127, pp. 19:1-19:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{berger_et_al:LIPIcs.ICDT.2019.19,
  author =	{Berger, Gerald and Otto, Martin and Pieris, Andreas and Surinx, Dimitri and Van den Bussche, Jan},
  title =	{{Additive First-Order Queries}},
  booktitle =	{22nd International Conference on Database Theory (ICDT 2019)},
  pages =	{19:1--19:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-101-6},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{127},
  editor =	{Barcelo, Pablo and Calautti, Marco},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2019.19},
  URN =		{urn:nbn:de:0030-drops-103217},
  doi =		{10.4230/LIPIcs.ICDT.2019.19},
  annote =	{Keywords: Expressive power}
}

Document

DOI: 10.4230/LIPIcs.CSL.2012.289

Pebble Games and Linear Equations

Authors: Martin Grohe and Martin Otto

Published in: LIPIcs, Volume 16, Computer Science Logic (CSL'12) - 26th International Workshop/21st Annual Conference of the EACSL (2012)

Abstract

We give a new, simplified and detailed account of the correspondence between levels of the Sherali-Adams relaxation of graph isomorphism and levels of pebble-game equivalence with counting (higher-dimensional Weisfeiler-Lehman colour refinement). The correspondence between basic colour refinement and fractional isomorphism, due to Ramana, Scheinerman and Ullman, is re-interpreted as the base level of Sherali-Adams and generalised to higher levels in this sense by Atserias and Maneva, who prove that the two resulting hierarchies interleave. In carrying this analysis further, we here give (a) a precise characterisation of the level-k Sherali-Adams relaxation in terms of a modified counting pebble game; (b) a variant of the Sherali-Adams levels that precisely match the k-pebble counting game; (c) a proof that the interleaving between these two hierarchies is strict. We also investigate the variation based on boolean arithmetic instead of real/rational arithmetic and obtain analogous correspondences and separations for plain k-pebble equivalence (without counting). Our results are driven by considerably simplified accounts of the underlying combinatorics and linear algebra.

Cite as

Martin Grohe and Martin Otto. Pebble Games and Linear Equations. In Computer Science Logic (CSL'12) - 26th International Workshop/21st Annual Conference of the EACSL. Leibniz International Proceedings in Informatics (LIPIcs), Volume 16, pp. 289-304, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2012)

Copy BibTex To Clipboard

@InProceedings{grohe_et_al:LIPIcs.CSL.2012.289,
  author =	{Grohe, Martin and Otto, Martin},
  title =	{{Pebble Games and Linear Equations}},
  booktitle =	{Computer Science Logic (CSL'12) - 26th International Workshop/21st Annual Conference of the EACSL},
  pages =	{289--304},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-42-2},
  ISSN =	{1868-8969},
  year =	{2012},
  volume =	{16},
  editor =	{C\'{e}gielski, Patrick and Durand, Arnaud},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CSL.2012.289},
  URN =		{urn:nbn:de:0030-drops-36790},
  doi =		{10.4230/LIPIcs.CSL.2012.289},
  annote =	{Keywords: Finite model theory, finite variable logics, graph isomorphism, Weisfeiler- Lehman algorithm, linear programming, Sherali–Adams hierarchy}
}

Document

DOI: 10.4230/LIPIcs.CSL.2011.2

The Freedoms of Guarded Bisimulation

Authors: Martin Otto

Published in: LIPIcs, Volume 12, Computer Science Logic (CSL'11) - 25th International Workshop/20th Annual Conference of the EACSL (2011)

Abstract

Guarded logics have been shown to be amazingly versatile and tractable logics since their inception by Andréka, van Benthem, Németi. Results to be surveyed include finite and small model properties, decidability results, complexity and expressive completeness issues, and guarded bisimulations.

Cite as

Martin Otto. The Freedoms of Guarded Bisimulation. In Computer Science Logic (CSL'11) - 25th International Workshop/20th Annual Conference of the EACSL. Leibniz International Proceedings in Informatics (LIPIcs), Volume 12, p. 2, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2011)

Copy BibTex To Clipboard

@InProceedings{otto:LIPIcs.CSL.2011.2,
  author =	{Otto, Martin},
  title =	{{The Freedoms of Guarded Bisimulation}},
  booktitle =	{Computer Science Logic (CSL'11) - 25th International Workshop/20th Annual Conference of the EACSL},
  pages =	{2--2},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-32-3},
  ISSN =	{1868-8969},
  year =	{2011},
  volume =	{12},
  editor =	{Bezem, Marc},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CSL.2011.2},
  URN =		{urn:nbn:de:0030-drops-32163},
  doi =		{10.4230/LIPIcs.CSL.2011.2},
  annote =	{Keywords: model theory, guarded logic, bisimulation, hypergraphs}
}

Search Results

Documents authored by Otto, Martin

Guarded Teams: The Horizontally Guarded Case

Abstract

Cite as

Additive First-Order Queries

Abstract

Cite as

Pebble Games and Linear Equations

Abstract

Cite as

The Freedoms of Guarded Bisimulation

Abstract

Cite as

Thanks for your feedback!

Could not send message