Remote Access Proceedings of the American Mathematical Society
Green Open Access

Proceedings of the American Mathematical Society

ISSN 1088-6826(online) ISSN 0002-9939(print)

 
 

 

The complexity of the word-problem for finite matrix rings


Authors: Csaba Szabó and Vera Vértesi
Journal: Proc. Amer. Math. Soc. 132 (2004), 3689-3695
MSC (2000): Primary 68Q17, 03C13
DOI: https://doi.org/10.1090/S0002-9939-04-07488-X
Published electronically: July 20, 2004
MathSciNet review: 2084092
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: We analyze the so-called word-problem for $M_2(Z_2)$, the ring of $2\times 2$ matrices over $Z_2$. We prove that the term-equivalence problem for the semigroup (and so for the ring) $M_2(Z_2)$ is coNP-complete.


References [Enhancements On Off] (What's this?)

  • 1. D. M. Barrington, P. McKenzie, C. Moore, P. Tesson, and D. Thérien, Equation satisfiability and program satisfiability for finite monoids, Math. Found. Comp. Sci. (2000, Bratislava), 127-181. MR 1844742 (2002f:68053)
  • 2. S. Burris and J. Lawrence, The equivalence problem for finite rings, Journal of Symbolic Computation 15 (1993), 67-71. MR 1210448 (94c:16030)
  • 3. H. Hunt and R. Stearns, The complexity for equivalence for commutative rings, Journal of Symbolic Computation 10 (1990), 411-436. MR 1087713 (92g:68062)
  • 4. A. Kisieliewicz, personal communication, 2002.
  • 5. J. Lawrence and R. Willard, The complexity of solving polynomial equations over finite rings, manuscript, 1997.
  • 6. V. Yu. Popov and M. V. Volkov, Complexity of checking identities and quasi-identities in finite semigroups, Journal of Symblic logic (to appear).
  • 7. S. Seif and Cs. Szabó, The computational complexity of checking identites in simple semigroups and matrix semigroups over finite fields, Semigroup Forum (to appear 2002).

Similar Articles

Retrieve articles in Proceedings of the American Mathematical Society with MSC (2000): 68Q17, 03C13

Retrieve articles in all journals with MSC (2000): 68Q17, 03C13


Additional Information

Csaba Szabó
Affiliation: Department of Algebra and Number Theory, Eötvös Loránd University, 1117 Budapest, Pázmány Péter sétány 1/c, Hungary
Email: csaba@cs.elte.hu

Vera Vértesi
Affiliation: Department of Algebra and Number Theory, Eötvös Loránd University, 1117 Budapest, Pázmány Péter sétány 1/c, Hungary
Email: wera13@cs.elte.hu

DOI: https://doi.org/10.1090/S0002-9939-04-07488-X
Keywords: 0-simple semigroup, term, complexity
Received by editor(s): September 5, 2002
Received by editor(s) in revised form: July 24, 2003
Published electronically: July 20, 2004
Communicated by: Lance W. Small
Article copyright: © Copyright 2004 American Mathematical Society

American Mathematical Society