Circuit complexity and the expressive power of generalized first-order formulas

DOI10.1007/3-540-55719-9_60zbMath1425.03016OpenAlexW1504809082MaRDI QIDQ5204302

Howard Straubing

Publication date: 4 December 2019

Published in: Automata, Languages and Programming (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/3-540-55719-9_60

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Automata and formal grammars in connection with logical questions (03D05) Complexity of computation (including implicit computational complexity) (03D15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Products of languages with counter
• \(\Sigma_ 1^ 1\)-formulae on finite structures
• Bounded-width polynomial-size branching programs recognize exactly those languages in \(NC^ 1\)
• On uniformity within \(NC^ 1\)
• Weak Second‐Order Arithmetic and Finite Automata
• Parity, circuits, and the polynomial-time hierarchy
• Languages that Capture Complexity Classes
• Finite monoids and the fine structure of NC ¹
• CONSTANT-DEPTH PERIODIC CIRCUITS