Small overlap monoids: the word problem

Simple item page
dc.creatorKambites, Mark
dc.date2007-12-03
dc.date.accessioned2026-07-07T08:46:53Z
dc.date.available2026-07-07T08:46:53Z
dc.descriptionWe 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.
dc.description22 pages
dc.identifierhttps://arxiv.org/abs/0712.0250
dc.identifierhttp://arxiv.org/abs/0712.0250
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/143407
dc.subjectRings and Algebras
dc.subject20M05
dc.titleSmall overlap monoids: the word problem
dc.typetext

Files

Collections

arXiv