Small overlap monoids I: The word problem

JOURNAL OF ALGEBRA

卷:321

Article

Kambites, Mark

关键词: Monoid;    Semigroup;    Word problem;    Finite presentation;    Small overlap;    Small cancellation;   

DOI  :  10.1016/j.jalgebra.2008.09.038

来源: Elsevier

【 摘 要 】

We develop a combinatorial approach to the study of semigroups and monoids with finite presentations satisfying small overlap conditions. In contrast to existing geometric methods, our approach facilitates a sequential left-right analysis of words which lends itself to the development of practical. efficient computational algorithms. In particular, we obtain a highly practical linear time solution to the word problem for monoids and semigroups with finite presentations satisfying the condition C(4). and a polynomial time Solution to the uniform word problem for presentations satisfying the same condition. (c) 2008 Elsevier Inc. All rights reserved.

【 授权许可】

Free