Complexity of the word problem for commutative semigroups of fixed dimension

DOI10.1007/BF00288776MaRDI QIDQ802020zbMATH OpenOpenAlexFDO

Authors 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

complete problemcomputational complexityword problem for commutative semigroups

Mathematics Subject Classification ID

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

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.

Recommendations

• Varieties of Commutative Semigroups
• Time-Complexity of the Word Problem for Semigroups and the Higman Embedding Theorem
• scientific article; zbMATH DE number 3920796
• Commutative grammars: The complexity of uniform word problems
• COMPLEXITY OF SEMIGROUP IDENTITY CHECKING

Cites work

• Counter machines and counter languages
• scientific article; zbMATH DE number 3664335 (Why is no real title available?)
• scientific article; zbMATH DE number 3564361 (Why is no real title available?)
• scientific article; zbMATH DE number 3582425 (Why is no real title available?)
• Rational sets in commutative monoids
• Some algorithmic problems for finitely defined commutative semigroups
• Symmetric space-bounded computation
• The complexity of the word problems for commutative semigroups and polynomial ideals

Cited in

(15)

• 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
• Optimal algorithms for the coverability, the subword, the containment, and the equivalence problems for commutative semigroups.
• Improved lower bounds for the complexity of finite semigroups
• scientific article; zbMATH DE number 4017191 (Why is no real title available?)
• scientific article; zbMATH DE number 6004843 (Why is no real title available?)
• scientific article; zbMATH DE number 3920796 (Why is no real title available?)
• Space functions and space complexity of the word problem in semigroups.
• Varieties of Commutative Semigroups
• scientific article; zbMATH DE number 1936760 (Why is no real title available?)
• COMPLEXITY OF SEMIGROUP IDENTITY CHECKING
• Polynomial time machines equipped with word problems over algebraic structures as their acceptance criteria
• The complexity of the coverability, the containment, and the equivalence problems for commutative semigroups
• Generic complexity of the word problem in some semigroups
• On complexity of the word problem in semigroups with homogeneous relations

This page was built for publication: Complexity of the word problem for commutative semigroups of fixed dimension

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q802020)