Non-uniform automata over groups (Q804303)

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.