Nils Vortmeier ; Thomas Zeume - Dynamic Complexity of Parity Exists Queries

lmcs:6639 - Logical Methods in Computer Science, November 16, 2021, Volume 17, Issue 4 -
Dynamic Complexity of Parity Exists QueriesArticle

Authors: Nils Vortmeier ; Thomas Zeume

    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.

    Volume: Volume 17, Issue 4
    Published on: November 16, 2021
    Accepted on: September 20, 2021
    Submitted on: July 15, 2020
    Keywords: Computer Science - Logic in Computer Science
      Source : OpenAIRE Graph
    • Foundations of Factorized Data Management Systems; Funder: European Commission; Code: 682588

    1 Document citing this article

    Consultation statistics

    This page has been seen 1145 times.
    This article's PDF has been downloaded 237 times.