Extensional Uniformity for Boolean Circuits
From MaRDI portal
Publication:3540171
DOI10.1007/978-3-540-87531-4_7zbMath1157.68030MaRDI QIDQ3540171
No author found.
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
68Q45: Formal languages and automata
68Q15: Complexity classes (hierarchies, relations among complexity classes, etc.)
68Q19: Descriptive complexity and finite models
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Turing machines that take advice
- Some subclasses of context-free languages in \(NC^ 1\)
- On uniform circuit complexity
- First-order expressibility of languages with neutral letters or: The Crane Beach conjecture
- On uniformity within \(NC^ 1\)
- P-uniform circuit complexity
- Visibly pushdown languages
- On Relating Time and Space to Size and Depth
- Rudimentary Predicates and Relative Computation
- Expressibility and Parallel Complexity
- Arithmetic, first-order logic, and counting quantifiers
- Studies in abstract families of languages
- An infinite hierarchy of intersections of context-free languages
- The descriptive complexity approach to LOGCFL