Complexity of the word problem for commutative semigroups of fixed dimension
type: Item
instance of: scholarly article
title: Complexity of the word problem for commutative semigroups of fixed dimension
zbMATH Open document ID: 0553.20034
DOI: 10.1007/BF00288776
author: Dung T. Huynh
published in: Acta Informatica
publication date: 1985-01-01T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 20M05
Mathematics Subject Classification ID: 20M35
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 20M14
zbMATH DE Number: 3880948
zbMATH Keywords: computational complexity
zbMATH Keywords: word problem for commutative semigroups
zbMATH Keywords: complete problem
MaRDI profile type: Publication
cites work: Q4152749
cites work: Some algorithmic problems for finitely defined commutative semigroups
cites work: Rational sets in commutative monoids
cites work: Counter machines and counter languages
cites work: Q3862379
cites work: Q4136592
cites work: Symmetric space-bounded computation
cites work: The complexity of the word problems for commutative semigroups and polynomial ideals
full work available at URL: https://doi.org/10.1007/bf00288776
OpenAlex ID: W2036954119
description: scientific article; zbMATH DE number 3880948