Complexity of the word problem for commutative semigroups of fixed dimension

DOI10.1007/BF00288776zbMATH Open0553.20034OpenAlexW2036954119MaRDI QIDQ802020FDOQ802020

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

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

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)

Cites Work

• Title not available (Why is that?)
• Rational sets in commutative monoids
• Title not available (Why is that?)
• The complexity of the word problems for commutative semigroups and polynomial ideals
• Symmetric space-bounded computation
• Counter machines and counter languages
• Some algorithmic problems for finitely defined commutative semigroups
• Title not available (Why is that?)

Cited In (12)

• Improved lower bounds for the complexity of finite semigroups
• Space functions and space complexity of the word problem in semigroups.
• Some complexity bounds for problems concerning finite and 2-dimensional vector addition systems with states
• COMPLEXITY OF SEMIGROUP IDENTITY CHECKING
• Title not available (Why is that?)
• Optimal algorithms for the coverability, the subword, the containment, and the equivalence problems for commutative semigroups.
• An \(O(n^{1.5})\) algorithm to decide boundedness for conflict-free vector replacement systems
• Title not available (Why is that?)
• Title not available (Why is that?)
• Polynomial time machines equipped with word problems over algebraic structures as their acceptance criteria
• Title not available (Why is that?)
• The complexity of the coverability, 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)