|
The complexity of the word-problem for finite matrix rings
Author(s):
Csaba
Szabó;
Vera
Vértesi
Journal:
Proc. Amer. Math. Soc.
132
(2004),
3689-3695.
MSC (2000):
Primary 68Q17, 03C13
Posted:
July 20, 2004
MathSciNet review:
2084092
Retrieve article in:
PDF
This article is available free of charge
Abstract |
References |
Similar articles |
Additional information
Abstract:
We analyze the so-called word-problem for  , the ring of  matrices over  . We prove that the term-equivalence problem for the semigroup (and so for the ring)  is coNP-complete.
References:
-
- 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:
10.1090/S0002-9939-04-07488-X
PII:
S 0002-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
Posted:
July 20, 2004
Communicated by:
Lance W. Small
Copyright of article:
Copyright
2004,
American Mathematical Society
|
