The word problem for free adequate semigroups.

DOI10.1142/S0218196714500404MaRDI QIDQ2934271zbMATH OpenOpenAlexFDO

Authors 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

constraint satisfaction problemword problemnormal form theoremscomplexity of computationpolynomial time algorithmsfree adequate semigroups

Mathematics Subject Classification ID

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

Abstract: We study the complexity of computation in finitely generated free left, right and two-sided adequate semigroups and monoids. We present polynomial time (quadratic in the RAM model of computation) algorithms to solve the word problem and compute normal forms in each of these, and hence also to test whether any given identity holds in the classes of left, right and/or two-sided adequate semigroups.

Recommendations

• Free adequate semigroups.
• scientific article; zbMATH DE number 3995984
• scientific article; zbMATH DE number 4073302
• Concrete algorithms for word problem and subsemigroup problem for semigroups which are disjoint unions of finitely many copies of the free monogenic semigroup
• On the word problem for free completely regular semigroups

Cites work

• A characterization of adequate semigroups by forbidden subsemigroups.
• Adequate Semigroups
• Free adequate semigroups.
• Graph minors. II. Algorithmic aspects of tree-width
• Introduction to algorithms
• Inverse monoids: decidability and complexity of algebraic questions.
• Left adequate and left Ehresmann monoids.
• Left adequate and left Ehresmann monoids. II.
• Linear time algorithms for NP-hard problems restricted to partial k- trees
• On retracts, absolute retracts, and folds in cographs
• Retracts of trees and free left adequate semigroups.
• Semigroups and ordered categories. I: The reduced case

Cited in

(12)

• Polynomial time multiplication and normal forms in free bands
• scientific article; zbMATH DE number 4073302 (Why is no real title available?)
• Proper Ehresmann semigroups
• Free completely regular semigroups. II: Word problem.
• scientific article; zbMATH DE number 2112143 (Why is no real title available?)
• Free adequate semigroups.
• NORMAL FORMS FOR FREE APERIODIC SEMIGROUPS
• Efficient testing of equivalence of words in a free idempotent semigroup
• scientific article; zbMATH DE number 459344 (Why is no real title available?)
• THE WORD PROBLEM FOR THE RELATIVELY FREE SEMIGROUP SATISFYING T^m=T^m+n WITH m≥3
• The algebra of functions with antidomain and range
• An explicit algorithm for normal forms in small overlap monoids

This page was built for publication: The word problem for free adequate semigroups.

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