Non-uniform automata over groups
type: Item
instance of: scholarly article
title: Non-uniform automata over groups
zbMATH Open document ID: 0727.68070
DOI: 10.1016/0890-5401(90)90007-5
author: David A. Mix Barrington
author: Howard Straubing
author: Denis Thérien
published in: Information and Computation
publication date: 1990-01-01T00:00:00Z
review text: Non-uniform deterministic finite automata (NUDFA's) over general finite monoids have recently been developed as a link between the theory of finite automata and low-lewel parallel complexity. The paper under review extends this theory to NUDFA's over solvable groups. The authors characterize the power of NUDFA's over nilpotent groups and prove some optimal lower bounds for NUDFA's over certain groups which are solvable but not nilpotent.
reviewed by: Michael Clausen
Mathematics Subject Classification ID: 68Q70
zbMATH DE Number: 4201645
zbMATH Keywords: Non-uniform deterministic finite automata
zbMATH Keywords: parallel complexity
zbMATH Keywords: solvable groups
MaRDI profile type: Publication
full work available at URL: 0890-5401(90)90007-5
OpenAlex ID: W1500453128
cites work: \(\Sigma_ 1^ 1\)-formulae on finite structures
cites work: Superlinear lower bounds for bounded-width branching programs
cites work: Bounded-width polynomial-size branching programs recognize exactly those languages in \(NC^ 1\)
cites work: Q3773353
cites work: Finite monoids and the fine structure of NC 1
cites work: The dot-depth hierarchy of star-free languages is infinite
cites work: Constant Depth Reducibility
cites work: Dot-depth of star-free events
cites work: A taxonomy of problems with fast parallel algorithms
cites work: Q4132170
cites work: Bounded-depth, polynomial-size circuits for symmetric functions
cites work: Parity, circuits, and the polynomial-time hierarchy
cites work: The NP-completeness column: An ongoing guide
cites work: Q5570933
cites work: Q3853827
cites work: Q3779765
cites work: Q3769981
cites work: Lower bounds on the size of bounded depth circuits over a complete basis with logical addition
cites work: Q4172915
cites work: On finite monoids having only trivial subgroups
cites work: Families of recognizable sets corresponding to certain varieties of finite monoids
cites work: Q3730029
cites work: Classification of finite monoids: the language approach
cites work: Q3689383
cites work: Q3256242
Recommended article: Q3773353
Recommended article: Q4206411
Recommended article: Group-Type Automata
Recommended article: Extended finite automata over groups
Recommended article: Q3681945
Recommended article: Q3695483
Recommended article: Representations of group automata
Recommended article: Representation of automata by groups
Recommended article: Finite automata over free groups
Recommended article: Q3692879
description: scientific article; zbMATH DE number 4201645