On the quantifier-free dynamic complexity of reachability

DOI10.1016/j.ic.2014.09.011zbMath1312.68085OpenAlexW2093618122MaRDI QIDQ2514150

Thomas Zeume, Thomas Schwentick

Publication date: 30 January 2015

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ic.2014.09.011

Mathematics Subject Classification ID

Database theory (68P15) Logic in computer science (03B70)

Related Items (5)

Dynamic conjunctive queries ⋮ Reachability is in DynFO ⋮ The dynamic descriptive complexity of \(k\)-clique ⋮ Unnamed Item ⋮ Dynamic complexity of expansion

Cites Work

• Unnamed Item
• Unnamed Item
• Arity bounds in first-order incremental evaluation and definition of polynomial time database queries
• Dyn-FO: A parallel, dynamic complexity class
• The dynamic complexity of transitive closure is in DynTC\(^{0}\).
• Incremental recomputation in local languages.
• Dynamic conjunctive queries
• Dynamic complexity theory revisited
• On the Quantifier-Free Dynamic Complexity of Reachability
• The dynamic complexity of formal languages
• Multiply-Recursive Upper Bounds with Higman’s Lemma
• Lower bounds for dynamic connectivity
• SEPARATING AUXILIARY ARITY HIERARCHY OF FIRST-ORDER INCREMENTAL EVALUATION SYSTEMS USING (3K+1)-ary INPUT RELATIONS

This page was built for publication: On the quantifier-free dynamic complexity of reachability