The word problem for free adequate semigroups

DOI10.1142/S0218196714500404zbMath1307.20046arXiv1311.7523OpenAlexW2962984570MaRDI QIDQ2934271

Mark Kambites, Alexandr Kazda

Publication date: 12 December 2014

Published in: International Journal of Algebra and Computation (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1311.7523

zbMATH Keywords

word problemconstraint satisfaction problempolynomial time algorithmsnormal form theoremscomplexity of computationfree adequate semigroups

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) General structure theory for semigroups (20M10) Free semigroups, generators and relations, word problems (20M05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items

Proper Ehresmann semigroups, The algebra of functions with antidomain and range

Cites Work

• Unnamed Item
• Left adequate and left Ehresmann monoids. II.
• Linear time algorithms for NP-hard problems restricted to partial k- trees
• Semigroups and ordered categories. I: The reduced case
• Inverse monoids: decidability and complexity of algebraic questions.
• On Retracts, Absolute Retracts, and Folds in Cographs
• Adequate Semigroups
• Retracts of trees and free left adequate semigroups
• LEFT ADEQUATE AND LEFT EHRESMANN MONOIDS
• Graph minors. II. Algorithmic aspects of tree-width
• FREE ADEQUATE SEMIGROUPS
• A characterization of adequate semigroups by forbidden subsemigroups