Complexity of the word problem for commutative semigroups of fixed dimension (Q802020): Difference between revisions
From MaRDI portal
ReferenceBot (talk | contribs) Changed an Item |
Set OpenAlex properties. |
||
| Property / full work available at URL | |||
| Property / full work available at URL: https://doi.org/10.1007/bf00288776 / rank | |||
Normal rank | |||
| Property / OpenAlex ID | |||
| Property / OpenAlex ID: W2036954119 / rank | |||
Normal rank | |||
Latest revision as of 10:48, 30 July 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
