Finite Monoids: From Word to Circuit Evaluation
From MaRDI portal
Publication:4337437
DOI10.1137/S0097539793249530zbMath0868.68057MaRDI QIDQ4337437
Pierre McKenzie, Denis Thérien, Pierre Péladeau, Martin Beaudry
Publication date: 3 August 1997
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Analysis of algorithms and problem complexity (68Q25) Semigroups in automata theory, linguistics, etc. (20M35) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Related Items
A PTIME-complete matching problem for SLP-compressed words, Evaluating Matrix Circuits, Parallel Identity Testing for Skew Circuits with Big Powers and Applications, Evaluation of circuits over nilpotent and polycyclic groups, Better complexity bounds for cost register automata, The complexity of compressed membership problems for finite automata, Space Complexity of Reachability Testing in Labelled Graphs, Leaf languages and string compression, Unnamed Item, Unnamed Item, Unnamed Item, Integer circuit evaluation is PSPACE-complete, Parallel identity testing for skew circuits with big powers and applications, Better complexity bounds for cost register automata, Compression techniques in group theory
