Complexity of the word problem for commutative semigroups of fixed dimension

DOI10.1007/BF00288776zbMath0553.20034OpenAlexW2036954119MaRDI QIDQ802020

Dung T. Huynh

Publication date: 1985

Published in: Acta Informatica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf00288776

zbMATH Keywords

computational complexitycomplete problemword problem for commutative semigroups

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Commutative semigroups (20M14) Free semigroups, generators and relations, word problems (20M05) Semigroups in automata theory, linguistics, etc. (20M35)

Related Items

Some complexity bounds for problems concerning finite and 2-dimensional vector addition systems with states ⋮ An \(O(n^{1.5})\) algorithm to decide boundedness for conflict-free vector replacement systems

Cites Work

• Symmetric space-bounded computation
• The complexity of the word problems for commutative semigroups and polynomial ideals
• Rational sets in commutative monoids
• Some algorithmic problems for finitely defined commutative semigroups
• Counter machines and counter languages
• Unnamed Item
• Unnamed Item
• Unnamed Item