Complexity of the word problem for commutative semigroups of fixed dimension (Q802020): Difference between revisions
From MaRDI portal
Added link to MaRDI item. |
Set profile property. |
||
| Property / MaRDI profile type | |||
| Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Revision as of 01:16, 5 March 2024
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Complexity of the word problem for commutative semigroups of fixed dimension |
scientific article |
Statements
Complexity of the word problem for commutative semigroups of fixed dimension (English)
0 references
1985
0 references
We investigate the computational complexity of the word problem for commutative semigroups of fixed dimension. It is shown that for commutative semigroups of dimension k, \(k\geq 6\), the word problem is complete for symmetric linear space, providing another complete problem for this symmetric complexity class. We also show that in the case of one generator, the word problem is solvable in polynomial time.
0 references
computational complexity
0 references
word problem for commutative semigroups
0 references
complete problem
0 references
