scientific article; zbMATH DE number 7471669

MaRDI QIDQ5028429

Thomas Zeume, Nils Vortmeier

Publication date: 9 February 2022

Full work available at URL: https://arxiv.org/abs/1910.06004

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

zbMATH Keywords

dynamic complexityarity hierarchyparity quantifier

Mathematics Subject Classification ID

Logic in computer science (03B70) Computer science (68-XX)

Related Items (1)

The dynamic complexity of acyclic hypergraph homomorphisms

Cites Work

• Unnamed Item
• Unnamed Item
• \(\Sigma_ 1^ 1\)-formulae on finite structures
• Arity bounds in first-order incremental evaluation and definition of polynomial time database queries
• On ACC
• Dyn-FO: A parallel, dynamic complexity class
• The dynamic complexity of transitive closure is in DynTC\(^{0}\).
• The dynamic descriptive complexity of \(k\)-clique
• On the quantifier-free dynamic complexity of reachability
• On uniformity within \(NC^ 1\)
• The dynamic complexity of formal languages
• Parity, circuits, and the polynomial-time hierarchy
• SEPARATING AUXILIARY ARITY HIERARCHY OF FIRST-ORDER INCREMENTAL EVALUATION SYSTEMS USING (3K+1)-ary INPUT RELATIONS
• Dynamic Complexity under Definable Changes

This page was built for publication: