Document Open Access Logo

Dynamic Complexity of Parity Exists Queries

Authors Nils Vortmeier, Thomas Zeume

PDF

File

Thumbnail PDF
PDF
LIPIcs.CSL.2020.37.pdf
  • Filesize: 0.57 MB
  • 16 pages

Document Identifiers

Related Versions

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)
    0
    PDF Downloads
    0
    Metadata Views

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.

Cite As Get 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

Author Details

Nils Vortmeier
  • TU Dortmund University, Dortmund, Germany
Thomas Zeume
  • TU Dortmund University, Dortmund, Germany

Funding

The authors acknowledge the financial support by DFG grant SCHW 678/6-2.

Acknowledgements

We are grateful to Samir Datta, Raghav Kulkarni, Anish Mukherjee and Thomas Schwentick for illuminating discussions.

References

  1. Serge Abiteboul, Richard Hull, and Victor Vianu. Foundations of databases, volume 8. Addison-Wesley Reading, 1995. Google Scholar
  2. 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.
  3. 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.
  4. 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.
  5. 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.
  6. 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.
  7. 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.
  8. 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.
  9. 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.
  10. 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.
  11. William Hesse. Dynamic Computational Complexity. PhD thesis, University of Massachusetts Amherst, 2003. Google Scholar
  12. Neil Immerman. Descriptive complexity. Graduate texts in computer science. Springer, 1999. URL: https://doi.org/10.1007/978-1-4612-0539-5.
  13. 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.
  14. 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.
  15. Thomas Schwentick and Thomas Zeume. Dynamic complexity: recent updates. SIGLOG News, 3(2):30-52, 2016. URL: https://doi.org/10.1145/2948896.2948899.
  16. 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.
  17. 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.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact