License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.CSL.2020.37
URN: urn:nbn:de:0030-drops-116805
URL: https://drops.dagstuhl.de/opus/volltexte/2020/11680/
Go to the corresponding LIPIcs Volume Portal

Vortmeier, Nils ; Zeume, Thomas

Dynamic Complexity of Parity Exists Queries

pdf-format:
LIPIcs-CSL-2020-37.pdf (0.6 MB)

Abstract

Given a graph whose nodes may be coloured red, the parity of the number of red nodes can easily be maintained with first-order update rules in the dynamic complexity framework DynFO of Patnaik and Immerman. Can this be generalised to other or even all queries that are definable in first-order logic extended by parity quantifiers? We consider the query that asks whether the number of nodes that have an edge to a red node is odd. Already this simple query of quantifier structure parity-exists is a major roadblock for dynamically capturing extensions of first-order logic.
We show that this query cannot be maintained with quantifier-free first-order update rules, and that variants induce a hierarchy for such update rules with respect to the arity of the maintained auxiliary relations. Towards maintaining the query with full first-order update rules, it is shown that degree-restricted variants can be maintained.

BibTeX - Entry

@InProceedings{vortmeier_et_al:LIPIcs:2020:11680,
  author =	{Nils Vortmeier and Thomas Zeume},
  title =	{{Dynamic Complexity of Parity Exists Queries}},
  booktitle =	{28th EACSL Annual Conference on Computer Science Logic (CSL 2020)},
  pages =	{37:1--37:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-132-0},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{152},
  editor =	{Maribel Fern{\'a}ndez and Anca Muscholl},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2020/11680},
  URN =		{urn:nbn:de:0030-drops-116805},
  doi =		{10.4230/LIPIcs.CSL.2020.37},
  annote =	{Keywords: Dynamic complexity, parity quantifier, arity hierarchy}
}

Keywords: Dynamic complexity, parity quantifier, arity hierarchy
Collection: 28th EACSL Annual Conference on Computer Science Logic (CSL 2020)
Issue Date: 2020
Date of publication: 06.01.2020

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI