On the Quantifier-Free Dynamic Complexity of Reachability

DOI10.1007/978-3-642-40313-2_73MaRDI QIDQ2849966zbMATH OpenOpenAlexFDO

Authors Thomas Zeume, Thomas Schwentick

Publication date 20 September 2013

Published in Mathematical Foundations of Computer Science 2013 (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1306.3056

Mathematics Subject Classification ID

Database theory (68P15)

Abstract: The dynamic complexity of the reachability query is studied in the dynamic complexity framework of Patnaik and Immerman, restricted to quantifier-free update formulas. It is shown that, with this restriction, the reachability query cannot be dynamically maintained, neither with binary auxiliary relations nor with unary auxiliary functions, and that ternary auxiliary relations are more powerful with respect to graph queries than binary auxiliary relations. Further inexpressibility results are given for the reachability query in a different setting as well as for a syntactical restriction of quantifier-free update formulas. Moreover inexpressibility results for some other queries are presented.

Recommendations

• On the quantifier-free dynamic complexity of reachability
• Dynamic complexity of directed reachability and other problems
• Dynamic complexity of the Dyck reachability
• On the complexity of L-reachability
• On the complexity of L-reachability
• scientific article; zbMATH DE number 4179344
• Complexity of reachability problems for finite discrete dynamical systems
• The cost of exactness in quantitative reachability
• On the quantifier complexity of \(\Delta_{n+1}(T)\)-induction

Cited in

(13)

• Dynamic conjunctive queries
• Dynamic complexity of the Dyck reachability
• Reachability is in DynFO
• The dynamic descriptive complexity of k-clique
• Dynamic complexity of directed reachability and other problems
• Reachability is in DynFO
• scientific article; zbMATH DE number 2044758 (Why is no real title available?)
• Dynamic graph queries
• Exponential space complexity for OBDD-based reachability analysis
• Decidability and complexity for quiescent consistency and its variations
• The dynamic descriptive complexity of \(k\)-clique
• On the quantifier-free dynamic complexity of reachability
• Dynamic complexity under definable changes

This page was built for publication: On the Quantifier-Free Dynamic Complexity of Reachability

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2849966)