Dyn-FO: A parallel, dynamic complexity class
From MaRDI portal
Publication:1376403
DOI10.1006/JCSS.1997.1520zbMATH Open0889.68063OpenAlexW2041298014MaRDI QIDQ1376403FDOQ1376403
Authors: Sushant Patnaik, Neil Immerman 
Publication date: 11 June 1998
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Full work available at URL: https://semanticscholar.org/paper/00d3501889da08bed1214961dd4373fc69469a04
Recommendations
Cites Work
- \(\Sigma_ 1^ 1\)-formulae on finite structures
- Logic for improving integrity checking in relational data bases
- Incremental and decremental evaluation of transitive closure by first- order queries
- Parity, circuits, and the polynomial-time hierarchy
- Languages that Capture Complexity Classes
- Improved data structures for fully dynamic biconnectivity
- Data Structures for On-Line Updating of Minimum Spanning Trees, with Applications
- Bounded-width polynomial-size branching programs recognize exactly those languages in \(NC^ 1\)
- Number of quantifiers is better than number of tape cells
- Expressibility and Parallel Complexity
- Storing a sparse table
- Title not available (Why is that?)
- Complexity models for incremental computation
- Structure and complexity of relational queries
- The complexity of iterated multiplication
- Title not available (Why is that?)
- Integrity constraint checking in stratified databases
- Title not available (Why is that?)
- Dynamic sensitivity of a chemostat for a microbial reaction with substrate and product inhibition
- Systematic derivation of incremental programs
- Title not available (Why is that?)
Cited In (28)
- Answering UCQs under updates and in the presence of integrity constraints
- Dynamic kernels for hitting sets and set packing
- Dynamic conjunctive queries
- Dynamic complexity of expansion
- The dynamic complexity of transitive closure is in DynTC\(^{0}\).
- Title not available (Why is that?)
- Dynamic complexity of the Dyck reachability
- A strategy for dynamic programs: start over and muddle through
- Reachability and distances under multiple changes
- Local properties of query languages
- 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
- The dynamic complexity of formal languages
- Modular materialisation of Datalog programs
- Dynamic complexity theory revisited
- STACS 2005
- The dynamic complexity of acyclic hypergraph homomorphisms
- A strategy for dynamic programs: start over and muddle through
- Incremental recomputation in local languages.
- The dynamic complexity of formal languages
- Dynamic algorithms for the Dyck languages
- On the quantifier-free dynamic complexity of reachability
- Small dynamic complexity classes. An investigation into dynamic descriptive complexity
Uses Software
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)
