Search Results

Documents authored by Bova, Simone

Document
DOI: 10.4230/LIPIcs.ICDT.2017.9
How Many Variables Are Needed to Express an Existential Positive Query?

Authors: Simone Bova and Hubie Chen

Published in: LIPIcs, Volume 68, 20th International Conference on Database Theory (ICDT 2017)

Abstract
The number of variables used by a first-order query is a fundamental measure which has been studied in numerous contexts, and which is known to be highly relevant to the task of query evaluation. In this article, we study this measure in the context of existential positive queries. Building on previous work, we present a combinatorial quantity defined on existential positive queries; we show that this quantity not only characterizes the minimum number of variables needed to express a given existential positive query by another existential positive query, but also that it characterizes the minimum number of variables needed to express a given existential positive query, over all first-order queries. Put differently and loosely, we show that for any existential positive query, no variables can ever be saved by moving out of existential positive logic to first-order logic. One component of this theorem’s proof is the construction of a winning strategy for a certain Ehrenfeucht-Fraiissé type game.
Cite as

Simone Bova and Hubie Chen. How Many Variables Are Needed to Express an Existential Positive Query?. In 20th International Conference on Database Theory (ICDT 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 68, pp. 9:1-9:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{bova_et_al:LIPIcs.ICDT.2017.9,
  author =	{Bova, Simone and Chen, Hubie},
  title =	{{How Many Variables Are Needed to Express an Existential Positive Query?}},
  booktitle =	{20th International Conference on Database Theory (ICDT 2017)},
  pages =	{9:1--9:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-024-8},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{68},
  editor =	{Benedikt, Michael and Orsi, Giorgio},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2017.9},
  URN =		{urn:nbn:de:0030-drops-70545},
  doi =		{10.4230/LIPIcs.ICDT.2017.9},
  annote =	{Keywords: existential positive queries, finite-variable logics, first-order logic, query optimization}
}
Document
DOI: 10.4230/LIPIcs.CSL.2015.41
First-Order Queries on Finite Abelian Groups

Authors: Simone Bova and Barnaby Martin

Published in: LIPIcs, Volume 41, 24th EACSL Annual Conference on Computer Science Logic (CSL 2015)

Abstract
We study the computational problem of checking whether a logical sentence is true in a finite abelian group. We prove that model checking first-order sentences on finite abelian groups is fixed-parameter tractable, when parameterized by the size of the sentence. We also prove that model checking monadic second-order sentences on finite abelian groups finitely presented by integer matrices is not fixed-parameter tractable (under standard assumptions in parameterized complexity).
Cite as

Simone Bova and Barnaby Martin. First-Order Queries on Finite Abelian Groups. In 24th EACSL Annual Conference on Computer Science Logic (CSL 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 41, pp. 41-59, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{bova_et_al:LIPIcs.CSL.2015.41,
  author =	{Bova, Simone and Martin, Barnaby},
  title =	{{First-Order Queries on Finite Abelian Groups}},
  booktitle =	{24th EACSL Annual Conference on Computer Science Logic (CSL 2015)},
  pages =	{41--59},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-90-3},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{41},
  editor =	{Kreutzer, Stephan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CSL.2015.41},
  URN =		{urn:nbn:de:0030-drops-54060},
  doi =		{10.4230/LIPIcs.CSL.2015.41},
  annote =	{Keywords: Finite Abelian Groups, First-Order Logic, Monadic Second-Order Logic}
}
Document
DOI: 10.4230/DagSemProc.09441.3
On the Expression Complexity of Equivalence and Isomorphism of Primitive Positive Formulas

Authors: Matt Valeriote, Simone Bova, and Hubie Chen

Published in: Dagstuhl Seminar Proceedings, Volume 9441, The Constraint Satisfaction Problem: Complexity and Approximability (2010)

Abstract
We study the complexity of equivalence and isomorphism on primitive positive formulas with respect to a given structure. We study these problems for various fixed structures; we present generic hardness and complexity class containment results, and give classification theorems for the case of two-element (boolean) structures.
Cite as

Matt Valeriote, Simone Bova, and Hubie Chen. On the Expression Complexity of Equivalence and Isomorphism of Primitive Positive Formulas. In The Constraint Satisfaction Problem: Complexity and Approximability. Dagstuhl Seminar Proceedings, Volume 9441, pp. 1-20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)

Copy BibTex To Clipboard

@InProceedings{valeriote_et_al:DagSemProc.09441.3,
  author =	{Valeriote, Matt and Bova, Simone and Chen, Hubie},
  title =	{{On the Expression Complexity of Equivalence and Isomorphism of Primitive Positive Formulas}},
  booktitle =	{The Constraint Satisfaction Problem: Complexity and Approximability},
  pages =	{1--20},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2010},
  volume =	{9441},
  editor =	{Andrei A. Bulatov and Martin Grohe and Phokion G. Kolaitis and Andrei Krokhin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.09441.3},
  URN =		{urn:nbn:de:0030-drops-23690},
  doi =		{10.4230/DagSemProc.09441.3},
  annote =	{Keywords: Expression complexity, equivalence, isomorphism, primitive positive formulas}
}
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
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact