Non-uniform automata over groups
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.
Non-uniform deterministic finite automata
scientific article; zbMATH DE number 4201645
scientific article