Reachability is in DynFO

DOI10.1007/978-3-662-47666-6_13MaRDI QIDQ3449473zbMATH OpenOpenAlexFDO

Authors Samir Datta, Raghav Kulkarni, A. Mukherjee, Thomas Schwentick, Thomas Zeume

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)

Recommendations

• Reachability is in DynFO
• Dynamic complexity of directed reachability and other problems
• Dyn-FO: A parallel, dynamic complexity class
• On the Quantifier-Free Dynamic Complexity of Reachability
• On the quantifier-free dynamic complexity of reachability

Cites work

• Arity bounds in first-order incremental evaluation and definition of polynomial time database queries
• Dyn-FO: A parallel, dynamic complexity class
• Dynamic complexity of directed reachability and other problems
• Dynamic matrix rank
• Faster dynamic matchings and vertex connectivity
• scientific article; zbMATH DE number 1254648 (Why is no real title available?)
• Incremental and decremental evaluation of transitive closure by first- order queries
• Isolation, matching, and counting uniform and nonuniform upper bounds
• Matching is as easy as matrix inversion
• On Dynamic Algorithms for Algebraic Problems
• On the quantifier-free dynamic complexity of reachability
• The dynamic complexity of transitive closure is in DynTC\(^{0}\).

Cited in

(10)

• Dyn-FO: A parallel, dynamic complexity class
• Maintenance of datalog materialisations revisited
• On the quantifier-free dynamic complexity of reachability
• Dynamic complexity of the Dyck reachability
• On the expressive power of query languages for matrices
• Reachability is in DynFO
• Reachability and distances under multiple changes
• Dynamic complexity of directed reachability and other problems
• Derandomizing isolation in space-bounded settings
• A strategy for dynamic programs: start over and muddle through

This page was built for publication: Reachability is in DynFO

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