Non-uniform automata over groups
From MaRDI portal
Publication:804303
DOI10.1016/0890-5401(90)90007-5zbMath0727.68070OpenAlexW1500453128MaRDI QIDQ804303
Howard Straubing, David A. Mix Barrington, Denis Thérien
Publication date: 1990
Published in: Information and Computation (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0890-5401(90)90007-5
Related Items
Inapproximability results for equations over finite groups, A lower bound for depth-3 circuits with MOD \(m\) gates, Complex polynomials and circuit lower bounds for modular counting, Representing Boolean functions as polynomials modulo composite numbers, Circuits constructed with MOD\(_ q\) gates cannot compute ``and in sublinear size, A note on a theorem of Barrington, Straubing and Thérien, Nonuniform ACC Circuit Lower Bounds, Satisfiability in MultiValued Circuits, Upper and lower bounds for some depth-3 circuit classes, Finite semigroup varieties defined by programs, Ultrafilters on words for a fragment of logic, Homomorphic public-key cryptosystems and encrypting Boolean circuits, On the computational power of programs over \(\mathsf{BA}_2\) monoid, Learning Read-Constant Polynomials of Constant Degree Modulo Composites, Regular languages in \(NC\), Formulas, regular languages and Boolean circuits, Typed Monoids – An Eilenberg-Like Theorem for Non Regular Languages, New size hierarchies for two way automata, \(NC^ 1\): The automata-theoretic viewpoint, Learning read-constant polynomials of constant degree modulo composites, MONOIDS AND COMPUTATIONS, Extensions to Barrington's M-program model, Quantum Fourier transforms and the complexity of link invariants for quantum doubles of finite groups, Learning expressions and programs over monoids, Unnamed Item, A topological approach to non-uniform complexity, Unnamed Item, On the computational power of depth-2 circuits with threshold and modulo gates, Depth Reduction for Circuits with a Single Layer of Modular Counting Gates, An Algebraic Perspective on Boolean Function Learning, Lower bounds for modular counting by circuits with modular gates, Programs over semigroups of dot-depth one, An impossibility gap between width-4 and width-5 permutation branching programs, The Power of Programs over Monoids in DA, Languages defined with modular counting quantifiers, The complexity of solving equations over finite groups, Functions with bounded symmetric communication complexity, programs over commutative monoids, and ACC, Spectral properties of threshold functions
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Families of recognizable sets corresponding to certain varieties of finite monoids
- \(\Sigma_ 1^ 1\)-formulae on finite structures
- Bounded-depth, polynomial-size circuits for symmetric functions
- Lower bounds on the size of bounded depth circuits over a complete basis with logical addition
- Bounded-width polynomial-size branching programs recognize exactly those languages in \(NC^ 1\)
- Classification of finite monoids: the language approach
- The dot-depth hierarchy of star-free languages is infinite
- Superlinear lower bounds for bounded-width branching programs
- Dot-depth of star-free events
- Parity, circuits, and the polynomial-time hierarchy
- Constant Depth Reducibility
- A taxonomy of problems with fast parallel algorithms
- Finite monoids and the fine structure of NC 1
- On finite monoids having only trivial subgroups
- The NP-completeness column: An ongoing guide
