Reachability is in DynFO

DOI10.1007/978-3-662-47666-6_13zbMath1440.68107OpenAlexW1930553816MaRDI QIDQ3449473

Samir Datta, Anish Mukherjee, Thomas Zeume, Raghav Kulkarni, Thomas Schwentick

Publication date: 4 November 2015

Published in: Automata, Languages, and Programming (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-662-47666-6_13

Mathematics Subject Classification ID

Database theory (68P15) Descriptive complexity and finite models (68Q19)

Related Items (6)

On the Expressive Power of Query Languages for Matrices ⋮ Unnamed Item ⋮ Dynamic Complexity of the Dyck Reachability ⋮ Unnamed Item ⋮ Derandomizing Isolation in Space-Bounded Settings ⋮ Maintenance of datalog materialisations revisited

Cites Work

• Unnamed Item
• Unnamed Item
• Dynamic matrix rank
• Matching is as easy as matrix inversion
• 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 and decremental evaluation of transitive closure by first- order queries
• Isolation, matching, and counting uniform and nonuniform upper bounds
• On the quantifier-free dynamic complexity of reachability
• On Dynamic Algorithms for Algebraic Problems
• Dynamic Complexity of Directed Reachability and Other Problems

This page was built for publication: Reachability is in DynFO