文章基本信息

标题：Dynamic Complexity of Parity Exists Queries
本地全文：下载
作者：Nils Vortmeier ; Thomas Zeume
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2020
卷号：152
页码：1-16
DOI：10.4230/LIPIcs.CSL.2020.37
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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.
关键词：Dynamic complexity; parity quantifier; arity hierarchy