Dyn-FO: A parallel, dynamic complexity class
From MaRDI portal
Publication:1376403
DOI10.1006/jcss.1997.1520zbMath0889.68063MaRDI QIDQ1376403
Neil Immerman, Sushant Patnaik
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
68Q15: Complexity classes (hierarchies, relations among complexity classes, etc.)
Related Items
The dynamic complexity of transitive closure is in DynTC\(^{0}\)., Incremental recomputation in local languages., Local properties of query languages
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- \(\Sigma_ 1^ 1\)-formulae on finite structures
- Bounded-width polynomial-size branching programs recognize exactly those languages in \(NC^ 1\)
- Logic for improving integrity checking in relational data bases
- Number of quantifiers is better than number of tape cells
- Complexity models for incremental computation
- Dynamic sensitivity of a chemostat for a microbial reaction with substrate and product inhibition
- The complexity of iterated multiplication
- Structure and complexity of relational queries
- Systematic derivation of incremental programs
- Incremental and decremental evaluation of transitive closure by first- order queries
- Improved data structures for fully dynamic biconnectivity
- Storing a sparse table
- Parity, circuits, and the polynomial-time hierarchy
- Data Structures for On-Line Updating of Minimum Spanning Trees, with Applications
- Languages that Capture Complexity Classes
- Integrity constraint checking in stratified databases
- Expressibility and Parallel Complexity
