Non-uniform automata over groups
From MaRDI portal
Publication:804303
DOI10.1016/0890-5401(90)90007-5zbMATH Open0727.68070OpenAlexW1500453128MaRDI QIDQ804303FDOQ804303
Authors: David A. Mix Barrington, Howard Straubing, 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
Recommendations
- scientific article; zbMATH DE number 4033093
- Publication:4206411
- Group-Type Automata
- Extended finite automata over groups
- scientific article; zbMATH DE number 3903978
- scientific article; zbMATH DE number 3918681
- Representations of group automata
- Representation of automata by groups
- Finite automata over free groups
- scientific article; zbMATH DE number 3917722
Cites Work
- \(\Sigma_ 1^ 1\)-formulae on finite structures
- A taxonomy of problems with fast parallel algorithms
- Title not available (Why is that?)
- Lower bounds on the size of bounded depth circuits over a complete basis with logical addition
- Title not available (Why is that?)
- Parity, circuits, and the polynomial-time hierarchy
- Title not available (Why is that?)
- On finite monoids having only trivial subgroups
- Bounded-width polynomial-size branching programs recognize exactly those languages in \(NC^ 1\)
- Title not available (Why is that?)
- Families of recognizable sets corresponding to certain varieties of finite monoids
- Classification of finite monoids: the language approach
- Dot-depth of star-free events
- Title not available (Why is that?)
- Finite monoids and the fine structure of NC 1
- Title not available (Why is that?)
- Constant Depth Reducibility
- Title not available (Why is that?)
- The dot-depth hierarchy of star-free languages is infinite
- Title not available (Why is that?)
- The NP-completeness column: An ongoing guide
- Bounded-depth, polynomial-size circuits for symmetric functions
- Superlinear lower bounds for bounded-width branching programs
- Title not available (Why is that?)
- Title not available (Why is that?)
Cited In (42)
- Depth Reduction for Circuits with a Single Layer of Modular Counting Gates
- On the computational power of depth-2 circuits with threshold and modulo gates
- An Algebraic Perspective on Boolean Function Learning
- Homomorphic public-key cryptosystems and encrypting Boolean circuits
- Title not available (Why is that?)
- Circuit complexity before the dawn of the new millennium
- The power of programs over monoids in DA
- New size hierarchies for two way automata
- On the computational power of programs over \(\mathsf{BA}_2\) monoid
- \(NC^ 1\): The automata-theoretic viewpoint
- Typed monoids -- an Eilenberg-like theorem for non regular languages
- Title not available (Why is that?)
- A lower bound for depth-3 circuits with MOD \(m\) gates
- Learning read-constant polynomials of constant degree modulo composites
- Finite semigroup varieties defined by programs
- Spectral properties of threshold functions
- Representing Boolean functions as polynomials modulo composite numbers
- A note on a theorem of Barrington, Straubing and Thérien
- Learning expressions and programs over monoids
- Satisfiability in MultiValued Circuits
- Functions with bounded symmetric communication complexity, programs over commutative monoids, and ACC
- Nonuniform ACC circuit lower bounds
- Upper and lower bounds for some depth-3 circuit classes
- Extensions to Barrington's M-program model
- Ultrafilters on words for a fragment of logic
- Regular languages in \(NC\)
- Learning Read-Constant Polynomials of Constant Degree Modulo Composites
- A topological approach to non-uniform complexity
- The complexity of solving equations over finite groups
- Quantum Fourier transforms and the complexity of link invariants for quantum doubles of finite groups
- Programs over semigroups of dot-depth one
- An impossibility gap between width-4 and width-5 permutation branching programs
- Complexity of modular circuits
- Lower bounds for modular counting by circuits with modular gates
- MONOIDS AND COMPUTATIONS
- Title not available (Why is that?)
- Formulas, regular languages and Boolean circuits
- Circuits constructed with MOD\(_ q\) gates cannot compute ``and in sublinear size
- Inapproximability results for equations over finite groups
- Title not available (Why is that?)
- Complex polynomials and circuit lower bounds for modular counting
- Languages defined with modular counting quantifiers
This page was built for publication: Non-uniform automata over groups
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q804303)
