Dyn-FO: A parallel, dynamic complexity class
From MaRDI portal
Recommendations
Cites work
- scientific article; zbMATH DE number 432805 (Why is no real title available?)
- scientific article; zbMATH DE number 4106276 (Why is no real title available?)
- scientific article; zbMATH DE number 1256641 (Why is no real title available?)
- scientific article; zbMATH DE number 512871 (Why is no real title available?)
- Bounded-width polynomial-size branching programs recognize exactly those languages in \(NC^ 1\)
- Complexity models for incremental computation
- Data Structures for On-Line Updating of Minimum Spanning Trees, with Applications
- Dynamic sensitivity of a chemostat for a microbial reaction with substrate and product inhibition
- Expressibility and Parallel Complexity
- Improved data structures for fully dynamic biconnectivity
- Incremental and decremental evaluation of transitive closure by first- order queries
- Integrity constraint checking in stratified databases
- Languages that Capture Complexity Classes
- Logic for improving integrity checking in relational data bases
- Number of quantifiers is better than number of tape cells
- Parity, circuits, and the polynomial-time hierarchy
- Storing a sparse table
- Structure and complexity of relational queries
- Systematic derivation of incremental programs
- The complexity of iterated multiplication
- \(\Sigma_ 1^ 1\)-formulae on finite structures
Cited in
(28)- Dynamic kernels for hitting sets and set packing
- Answering UCQs under updates and in the presence of integrity constraints
- Dynamic conjunctive queries
- Dynamic complexity of expansion
- The dynamic complexity of transitive closure is in DynTC\(^{0}\).
- Dynamic complexity of the Dyck reachability
- scientific article; zbMATH DE number 7471669 (Why is no real title available?)
- Local properties of query languages
- A strategy for dynamic programs: start over and muddle through
- Reachability and distances under multiple changes
- Work-sensitive dynamic complexity of formal languages
- Reachability is in DynFO
- The dynamic descriptive complexity of k-clique
- Reachability is in DynFO
- Maintenance of datalog materialisations revisited
- Dynamic databases with optimal in order time complexity
- Dynamic complexity of planar 3-connected graph isomorphism
- Modular materialisation of Datalog programs
- The dynamic complexity of formal languages
- Dynamic complexity theory revisited
- STACS 2005
- The dynamic complexity of acyclic hypergraph homomorphisms
- Incremental recomputation in local languages.
- A strategy for dynamic programs: start over and muddle through
- The dynamic complexity of formal languages
- Dynamic algorithms for the Dyck languages
- Small dynamic complexity classes. An investigation into dynamic descriptive complexity
- On the quantifier-free dynamic complexity of reachability
This page was built for publication: Dyn-FO: A parallel, dynamic complexity class
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1376403)
