LIPIcs.CSL.2020.37.pdf
- Filesize: 0.57 MB
- 16 pages
Document
Dynamic Complexity of Parity Exists Queries
Authors
-
Part of:
Volume:
28th EACSL Annual Conference on Computer Science Logic (CSL 2020)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: Computer Science Logic (CSL) - License:
Creative Commons Attribution 3.0 Unported license
- Publication Date: 2020-01-06
File
Document Identifiers
Acknowledgements
We are grateful to Samir Datta, Raghav Kulkarni, Anish Mukherjee and Thomas Schwentick for illuminating discussions.
Cite AsGet BibTex
Nils Vortmeier and Thomas Zeume. Dynamic Complexity of Parity Exists Queries. In 28th EACSL Annual Conference on Computer Science Logic (CSL 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 152, pp. 37:1-37:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/LIPIcs.CSL.2020.37
https://doi.org/10.4230/LIPIcs.CSL.2020.37
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.
Subject Classification
ACM Subject Classification
- Theory of computation → Logic and databases
- Theory of computation → Complexity theory and logic
Keywords
- Dynamic complexity
- parity quantifier
- arity hierarchy
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
-
Serge Abiteboul, Richard Hull, and Victor Vianu. Foundations of databases, volume 8. Addison-Wesley Reading, 1995.
- Miklós Ajtai. Σ¹₁-Formulae on finite structures. Annals of Pure and Applied Logic, 24(1):1-48, 1983. URL: https://doi.org/10.1016/0168-0072(83)90038-6.
- David A. Mix Barrington, Neil Immerman, and Howard Straubing. On Uniformity within NC¹. J. Comput. Syst. Sci., 41(3):274-306, 1990. URL: https://doi.org/10.1016/0022-0000(90)90022-D.
- Samir Datta, Raghav Kulkarni, Anish Mukherjee, Thomas Schwentick, and Thomas Zeume. Reachability Is in DynFO. J. ACM, 65(5):33:1-33:24, August 2018. URL: https://doi.org/10.1145/3212685.
- Samir Datta, Anish Mukherjee, Thomas Schwentick, Nils Vortmeier, and Thomas Zeume. A Strategy for Dynamic Programs: Start over and Muddle through. Logical Methods in Computer Science, Volume 15, Issue 2, May 2019. URL: https://doi.org/10.23638/LMCS-15(2:12)2019.
- Guozhu Dong and Jianwen Su. Arity Bounds in First-Order Incremental Evaluation and Definition of Polynomial Time Database Queries. J. Comput. Syst. Sci., 57(3):289-308, 1998. URL: https://doi.org/10.1006/jcss.1998.1565.
- Guozhu Dong and Louxin Zhang. Separating Auxiliary Arity Hierarchy of First-Order Incremental Evaluation Systems Using (3k+1)-ary Input Relations. Int. J. Found. Comput. Sci., 11(4):573-578, 2000. URL: https://doi.org/10.1142/S0129054100000302.
- Kousha Etessami. Dynamic Tree Isomorphism via First-Order Updates. In Alberto O. Mendelzon and Jan Paredaens, editors, Proceedings of the Seventeenth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, pages 235-243. ACM Press, 1998. URL: https://doi.org/10.1145/275487.275514.
- Merrick L. Furst, James B. Saxe, and Michael Sipser. Parity, Circuits, and the Polynomial-Time Hierarchy. Mathematical Systems Theory, 17(1):13-27, 1984. URL: https://doi.org/10.1007/BF01744431.
- Wouter Gelade, Marcel Marquardt, and Thomas Schwentick. The dynamic complexity of formal languages. ACM Trans. Comput. Log., 13(3):19, 2012. URL: https://doi.org/10.1145/2287718.2287719.
-
William Hesse. Dynamic Computational Complexity. PhD thesis, University of Massachusetts Amherst, 2003.
- Neil Immerman. Descriptive complexity. Graduate texts in computer science. Springer, 1999. URL: https://doi.org/10.1007/978-1-4612-0539-5.
- Sushant Patnaik and Neil Immerman. Dyn-FO: A parallel, dynamic complexity class. J. Comput. Syst. Sci., 55(2):199-209, 1997. URL: https://doi.org/10.1006/jcss.1997.1520.
- Thomas Schwentick, Nils Vortmeier, and Thomas Zeume. Dynamic Complexity under Definable Changes. ACM Trans. Database Syst., 43(3):12:1-12:38, 2018. URL: https://doi.org/10.1145/3241040.
- Thomas Schwentick and Thomas Zeume. Dynamic complexity: recent updates. SIGLOG News, 3(2):30-52, 2016. URL: https://doi.org/10.1145/2948896.2948899.
- Thomas Zeume. The dynamic descriptive complexity of k-clique. Inf. Comput., 256:9-22, 2017. URL: https://doi.org/10.1016/j.ic.2017.04.005.
- Thomas Zeume and Thomas Schwentick. On the quantifier-free dynamic complexity of Reachability. Inf. Comput., 240:108-129, 2015. URL: https://doi.org/10.1016/j.ic.2014.09.011.