Extensional Uniformity for Boolean Circuits

DOI10.1007/978-3-540-87531-4_7MaRDI QIDQ3540171zbMATH OpenOpenAlexFDO

Authors

Publication date 20 November 2008

Published in Computer Science Logic (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-540-87531-4_7

zbMATH Keywords

Boolean circuitsuniformitydescriptive complexity

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Descriptive complexity and finite models (68Q19)

Recommendations

• Extensional Uniformity for Boolean Circuits
• Expressing uniformity via oracles
• On uniformity within \(NC^ 1\)
• The lower reaches of circuit uniformity
• Some results on uniform arithmetic circuit complexity

Cites work

• scientific article; zbMATH DE number 6003856 (Why is no real title available?)
• scientific article; zbMATH DE number 3426894 (Why is no real title available?)
• scientific article; zbMATH DE number 3660804 (Why is no real title available?)
• scientific article; zbMATH DE number 618821 (Why is no real title available?)
• scientific article; zbMATH DE number 3293666 (Why is no real title available?)
• An infinite hierarchy of intersections of context-free languages
• Arithmetic, first-order logic, and counting quantifiers
• Expressibility and Parallel Complexity
• First-order expressibility of languages with neutral letters or: The Crane Beach conjecture
• On Relating Time and Space to Size and Depth
• On uniform circuit complexity
• On uniformity within \(NC^ 1\)
• P-uniform circuit complexity
• Rudimentary Predicates and Relative Computation
• Some subclasses of context-free languages in \(NC^ 1\)
• Studies in abstract families of languages
• The descriptive complexity approach to LOGCFL
• Turing machines that take advice
• Visibly pushdown languages

Cited in

(1)

• Extensional Uniformity for Boolean Circuits

This page was built for publication: Extensional Uniformity for Boolean Circuits

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