Non-uniform automata over groups

DOI10.1016/0890-5401(90)90007-5zbMath0727.68070MaRDI QIDQ804303

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

zbMATH Keywords

parallel complexity; solvable groups; Non-uniform deterministic finite automata

Mathematics Subject Classification ID

68Q70: Algebraic theory of languages and automata

Related Items

MONOIDS AND COMPUTATIONS, \(NC^ 1\): The automata-theoretic viewpoint, An impossibility gap between width-4 and width-5 permutation branching programs, Regular languages in \(NC\), Formulas, regular languages and Boolean circuits, Extensions to Barrington's M-program model, On the computational power of depth-2 circuits with threshold and modulo gates, Functions with bounded symmetric communication complexity, programs over commutative monoids, and ACC, Spectral properties of threshold functions, 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, Upper and lower bounds for some depth-3 circuit classes, Finite semigroup varieties defined by programs, Programs over semigroups of dot-depth one, Languages defined with modular counting quantifiers, The complexity of solving equations over finite groups, Inapproximability results for equations over finite groups, Homomorphic public-key cryptosystems and encrypting Boolean circuits, Learning expressions and programs over monoids, Learning Read-Constant Polynomials of Constant Degree Modulo Composites, Typed Monoids – An Eilenberg-Like Theorem for Non Regular Languages, Depth Reduction for Circuits with a Single Layer of Modular Counting Gates, An Algebraic Perspective on Boolean Function Learning

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 ¹
• On finite monoids having only trivial subgroups
• The NP-completeness column: An ongoing guide