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

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)

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

• 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?)
• Counter machines and counter languages
• 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

(14)

• Generic complexity of the word problem in some semigroups
• scientific article; zbMATH DE number 3920796 (Why is no real title available?)
• Some complexity bounds for problems concerning finite and 2-dimensional vector addition systems with states
• On complexity of the word problem in semigroups with homogeneous relations
• Space functions and space complexity of the word problem in semigroups.
• The complexity of the coverability, the containment, and the equivalence problems for commutative semigroups
• Polynomial time machines equipped with word problems over algebraic structures as their acceptance criteria
• COMPLEXITY OF SEMIGROUP IDENTITY CHECKING
• scientific article; zbMATH DE number 1936760 (Why is no real title available?)
• An \(O(n^{1.5})\) algorithm to decide boundedness for conflict-free vector replacement systems
• scientific article; zbMATH DE number 4017191 (Why is no real title available?)
• Improved lower bounds for the complexity of finite semigroups
• scientific article; zbMATH DE number 6004843 (Why is no real title available?)
• Optimal algorithms for the coverability, the subword, the containment, and the equivalence problems for commutative semigroups.

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)