Finite Monoids: From Word to Circuit Evaluation
From MaRDI portal
Publication:4337437
DOI10.1137/S0097539793249530zbMATH Open0868.68057MaRDI QIDQ4337437FDOQ4337437
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)
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
Analysis of algorithms and problem complexity (68Q25) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Semigroups in automata theory, linguistics, etc. (20M35)
Cited In (23)
- Linear circuits, two-variable logic and weakly blocked monoids
- Better complexity bounds for cost register automata
- Better complexity bounds for cost register automata
- Leaf languages and string compression
- Evaluating Matrix Circuits
- Evaluation of circuits over nilpotent and polycyclic groups
- The power word problem in graph products
- Space Complexity of Reachability Testing in Labelled Graphs
- Compressed decision problems in hyperbolic groups
- The complexity of compressed membership problems for finite automata
- Parallel Identity Testing for Skew Circuits with Big Powers and Applications
- Compression techniques in group theory
- Title not available (Why is that?)
- A PTIME-complete matching problem for SLP-compressed words
- Parallel identity testing for skew circuits with big powers and applications
- Linear Circuits, Two-Variable Logic and Weakly Blocked Monoids
- Integer circuit evaluation is PSPACE-complete
- The complexity of iterated multiplication
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Polynomial time machines equipped with word problems over algebraic structures as their acceptance criteria
- Circuits, matrices, and nonassociative computation
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)
