scientific article; zbMATH DE number 4033093

MaRDI QIDQ3773353zbMATH OpenFDO

Authors David A. Barrington, Denis Thérien

Publication date 1987

zbMATH Keywords

complexity of algorithmsfinite automatonparallel computation

Mathematics Subject Classification ID

Semigroups in automata theory, linguistics, etc. (20M35) Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45) Algebraic theory of languages and automata (68Q70)

Recommendations

• Non-uniform automata over groups
• scientific article; zbMATH DE number 17309
• A characterisation of NL/poly via nondeterministic finite automata
• Bounded-width polynomial-size branching programs recognize exactly those languages in \(NC^ 1\)
• scientific article; zbMATH DE number 4041299

Cited in

(7)

• Programs over aperiodic monoids
• Coxeter groups and nonuniform complexity
• Uniform and nonuniform recognizability.
• A topological approach to non-uniform complexity
• scientific article; zbMATH DE number 5697432 (Why is no real title available?)
• scientific article; zbMATH DE number 4041299 (Why is no real title available?)
• Non-uniform automata over groups

This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3773353)