CONSTANT-DEPTH PERIODIC CIRCUITS

DOI10.1142/S0218196791000043MaRDI QIDQ5750404zbMATH OpenOpenAlexFDO

Authors Howard Straubing

Publication date 1991

Published in International Journal of Algebra and Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1142/s0218196791000043

zbMATH Keywords

automataboolean circuitsconstant depth circuitsparallel complexitypolynomial-length programs over finite solvable groupssmall-depth circuitssuper-polynomial lower bounds

Mathematics Subject Classification ID

Semigroups in automata theory, linguistics, etc. (20M35) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45) Algebraic theory of languages and automata (68Q70)

Recommendations

• scientific article; zbMATH DE number 1379307
• scientific article; zbMATH DE number 512861
• Bounded-width polynomial-size branching programs recognize exactly those languages in \(NC^ 1\)
• scientific article; zbMATH DE number 17309
• Circuits on cylinders

Cited in

(16)

• Regular languages in \(NC\)
• Finite semigroup varieties defined by programs
• Programs over semigroups of dot-depth one
• A topological approach to non-uniform complexity
• Circuits on cylinders
• scientific article; zbMATH DE number 512861 (Why is no real title available?)
• scientific article; zbMATH DE number 1379307 (Why is no real title available?)
• scientific article; zbMATH DE number 7453183 (Why is no real title available?)
• CC-circuits and the expressive power of nilpotent algebras
• Lower bounds for modular counting by circuits with modular gates
• Circuit complexity and the expressive power of generalized first-order formulas
• Circuits on cylinders.
• Circuit complexity of regular languages
• The regular languages of first-order logic with one alternation
• \(NC^ 1\): The automata-theoretic viewpoint
• Ultrafilters on words for a fragment of logic

This page was built for publication: CONSTANT-DEPTH PERIODIC CIRCUITS

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