Finite Monoids: From Word to Circuit Evaluation

DOI10.1137/S0097539793249530MaRDI QIDQ4337437zbMATH OpenFDO

Authors Martin Beaudry, Pierre McKenzie, Pierre Péladeau, Denis Thérien

Publication date 3 August 1997

Published in SIAM Journal on Computing (Search for Journal in Brave)

zbMATH Keywords

circuit evaluation

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Semigroups in automata theory, linguistics, etc. (20M35)

Recommendations

• scientific article; zbMATH DE number 3871197
• MONOIDS AND COMPUTATIONS
• Arithmetic Circuits, Monomial Algebras and Finite Automata
• Enumerating words in finitely presented monoids
• Publication:3026992
• Circuit evaluation for finite semirings
• scientific article; zbMATH DE number 988809
• scientific article; zbMATH DE number 6719345
• Computations over finite monoids and their test complexity
• Analysis approach to finite monoids

Cited in

(24)

• Evaluating matrix circuits
• Linear Circuits, Two-Variable Logic and Weakly Blocked Monoids
• Compression techniques in group theory
• Linear circuits, two-variable logic and weakly blocked monoids
• Integer circuit evaluation is PSPACE-complete
• A PTIME-complete matching problem for SLP-compressed words
• Parallel identity testing for skew circuits with big powers and applications
• Leaf languages and string compression
• The complexity of iterated multiplication
• Circuits, matrices, and nonassociative computation
• scientific article; zbMATH DE number 1419259 (Why is no real title available?)
• Compressed decision problems in hyperbolic groups
• Polynomial time machines equipped with word problems over algebraic structures as their acceptance criteria
• The power word problem in graph products
• Circuit evaluation for finite semirings
• The complexity of compressed membership problems for finite automata
• Parallel identity testing for skew circuits with big powers and applications
• Better complexity bounds for cost register automata
• Evaluation of circuits over nilpotent and polycyclic groups
• Better complexity bounds for cost register automata
• scientific article; zbMATH DE number 7559146 (Why is no real title available?)
• scientific article; zbMATH DE number 7561687 (Why is no real title available?)
• scientific article; zbMATH DE number 7561757 (Why is no real title available?)
• Space Complexity of Reachability Testing in Labelled Graphs

This page was built for publication: Finite Monoids: From Word to Circuit Evaluation

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