scientific article; zbMATH DE number 7471669

MaRDI QIDQ5028429zbMATH OpenFDO

Authors Nils Vortmeier, Thomas Zeume

Publication date 9 February 2022

Full work available at URL https://arxiv.org/abs/1910.06004, https://lmcs.episciences.org/8717

zbMATH Keywords

dynamic complexityarity hierarchyparity quantifier

Mathematics Subject Classification ID

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

Recommendations

• scientific article; zbMATH DE number 7650850
• scientific article; zbMATH DE number 7650849
• Parallel complexity of logical query programs
• On the power of parity queries in Boolean decision trees
• Automata, Languages and Programming
• On dynamic bit-probe complexity
• scientific article; zbMATH DE number 6292744
• On the parity complexity measures of Boolean functions
• The complexity of DNF of parities
• On the power of parity polynomial time

Cites work

• scientific article; zbMATH DE number 1343480 (Why is no real title available?)
• scientific article; zbMATH DE number 839556 (Why is no real title available?)
• Arity bounds in first-order incremental evaluation and definition of polynomial time database queries
• Dyn-FO: A parallel, dynamic complexity class
• Dynamic complexity under definable changes
• On ACC
• On the quantifier-free dynamic complexity of reachability
• On uniformity within \(NC^ 1\)
• Parity, circuits, and the polynomial-time hierarchy
• SEPARATING AUXILIARY ARITY HIERARCHY OF FIRST-ORDER INCREMENTAL EVALUATION SYSTEMS USING (3K+1)-ary INPUT RELATIONS
• The dynamic complexity of formal languages
• The dynamic complexity of transitive closure is in DynTC\(^{0}\).
• The dynamic descriptive complexity of k-clique
• \(\Sigma_ 1^ 1\)-formulae on finite structures

Cited in

(2)

• scientific article; zbMATH DE number 6292744 (Why is no real title available?)
• The dynamic complexity of acyclic hypergraph homomorphisms

This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5028429)