scientific article; zbMATH DE number 512861

MaRDI QIDQ4281558zbMATH OpenFDO

Authors Martin Beaudry, Pierre McKenzie, Pierre Péladeau

Publication date 7 April 1994

zbMATH Keywords

\(P\)-completecircuit evaluationcomplexity classgeneralization of word problemnonsolvable monoid

Mathematics Subject Classification ID

Semigroups in automata theory, linguistics, etc. (20M35) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Recommendations

• Finite Monoids: From Word to Circuit Evaluation
• Circuits and expressions with nonassociative gates
• Evaluating matrix circuits
• Circuits, matrices, and nonassociative computation
• CONSTANT-DEPTH PERIODIC CIRCUITS

Cited in

(11)

• The complexity of iterated multiplication
• Predicting nonlinear cellular automata quickly by decomposing them into linear ones
• Circuits and expressions with nonassociative gates
• Circuits, matrices, and nonassociative computation
• Evaluating matrix circuits
• scientific article; zbMATH DE number 3871197 (Why is no real title available?)
• Linear Circuits, Two-Variable Logic and Weakly Blocked Monoids
• scientific article; zbMATH DE number 3959282 (Why is no real title available?)
• Linear circuits, two-variable logic and weakly blocked monoids
• Circuit evaluation for finite semirings
• CONSTANT-DEPTH PERIODIC CIRCUITS

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 Q4281558)