Extensional Uniformity for Boolean Circuits

DOI10.1007/978-3-540-87531-4_7zbMATH Open1157.68030OpenAlexW1966288006MaRDI QIDQ3540171FDOQ3540171

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

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

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)

Cites Work

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

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)