CONSTANT-DEPTH PERIODIC CIRCUITS

DOI10.1142/S0218196791000043zbMath0718.68045OpenAlexW1982818703MaRDI QIDQ5750404

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

automatasuper-polynomial lower boundsparallel complexitysmall-depth circuitsconstant depth circuitsboolean circuitspolynomial-length programs over finite solvable groups

Mathematics Subject Classification ID

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

Related Items (9)

Finite semigroup varieties defined by programs ⋮ Ultrafilters on words for a fragment of logic ⋮ Regular languages in \(NC\) ⋮ \(NC^ 1\): The automata-theoretic viewpoint ⋮ Circuit complexity of regular languages ⋮ A topological approach to non-uniform complexity ⋮ Circuit complexity and the expressive power of generalized first-order formulas ⋮ Lower bounds for modular counting by circuits with modular gates ⋮ Programs over semigroups of dot-depth one

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