CONSTANT-DEPTH PERIODIC CIRCUITS
From MaRDI portal
Publication:5750404
DOI10.1142/S0218196791000043zbMath0718.68045OpenAlexW1982818703MaRDI QIDQ5750404
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
automatasuper-polynomial lower boundsparallel complexitysmall-depth circuitsconstant depth circuitsboolean circuitspolynomial-length programs over finite solvable groups
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
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
