The word problem for free adequate semigroups.

DOI10.1142/S0218196714500404zbMATH Open1307.20046arXiv1311.7523OpenAlexW2962984570MaRDI QIDQ2934271FDOQ2934271

Authors: Mark Kambites, Alexandr Kazda 

Publication date: 12 December 2014

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

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.

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

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

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)

Cites Work

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

Cited In (11)

• Title not available (Why is that?)
• Proper Ehresmann semigroups
• Title not available (Why is that?)
• Free completely regular semigroups. II: Word problem.
• Free adequate semigroups.
• NORMAL FORMS FOR FREE APERIODIC SEMIGROUPS
• Efficient testing of equivalence of words in a free idempotent semigroup
• Title not available (Why is that?)
• 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)