Dyn-FO: A parallel, dynamic complexity class

DOI10.1006/jcss.1997.1520zbMath0889.68063OpenAlexW2041298014MaRDI 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

zbMATH Keywords

computational complexity

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items

Reachability is in DynFO ⋮ Dynamic algorithms for the Dyck languages ⋮ Unnamed Item ⋮ Modular materialisation of Datalog programs ⋮ The dynamic descriptive complexity of \(k\)-clique ⋮ The dynamic complexity of acyclic hypergraph homomorphisms ⋮ The dynamic complexity of transitive closure is in DynTC\(^{0}\). ⋮ Incremental recomputation in local languages. ⋮ Unnamed Item ⋮ Dynamic Complexity of the Dyck Reachability ⋮ Unnamed Item ⋮ Work-sensitive dynamic complexity of formal languages ⋮ On the quantifier-free dynamic complexity of reachability ⋮ Unnamed Item ⋮ Maintenance of datalog materialisations revisited ⋮ Local properties of query languages ⋮ Dynamic kernels for hitting sets and set packing ⋮ Dynamic complexity of expansion

Uses Software

• REACH

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