2026-07-22T14:19:52Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:11680 2024-03-06T10:48:46Z ddc:004 open_access

Dynamic Complexity of Parity Exists Queries Vortmeier, Nils Zeume, Thomas Dynamic complexity parity quantifier arity hierarchy 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Nils Vortmeier and Thomas Zeume 2020 Is Part Of LIPIcs, Volume 152, 28th EACSL Annual Conference on Computer Science Logic (CSL 2020) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CSL.2020.37 urn:nbn:de:0030-drops-116805 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CSL.2020.37 eng https://creativecommons.org/licenses/by/3.0/legalcode