We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
Parallel identity testing for skew circuits with big powers and applications.
- Authors
König, Daniel; Lohrey, Markus
- Abstract
Powerful skew arithmetic circuits are introduced. These are skew arithmetic circuits with variables, where input gates can be labeled with powers x n for binary encoded numbers n. It is shown that polynomial identity testing for powerful skew arithmetic circuits belongs to c o R N C 2 , which generalizes a corresponding result for (standard) skew circuits. Two applications of this result are presented: (i) Equivalence of higher-dimensional straight-line programs can be tested in c o R N C 2 ; this result is even new in the one-dimensional case, where the straight-line programs produce words. (ii) The compressed word problem (or circuit evaluation problem) for certain wreath products of finitely generated abelian groups belongs to c o R N C 2 . Using the Magnus embedding, it follows that the compressed word problem for a free metabelian group belongs to c o R N C 2 .
- Subjects
BINARY number system; PI-algebras; ARITHMETIC; EMBEDDINGS (Mathematics); FREE metabelian groups
- Publication
International Journal of Algebra & Computation, 2018, Vol 28, Issue 6, p979
- ISSN
0218-1967
- Publication type
Article
- DOI
10.1142/S0218196718500431