@MISC{Dershowitz_semigroupssatisfying, author = {Nachum Dershowitz}, title = {Semigroups Satisfying x m+n = x n}, year = {} }

Share

OpenURL

Abstract

We summarize recent results on semigroups satisfying the identity x m+n = x n , for n # 0andm # 1, and some rewrite techniques that havecontributed to their investigation. 1 Introduction Ninetyyears ago, Burnside #1902# posed the question whether every group satisfying the identity x m =1,andhaving a #nite number of generators, is #nite. In 1969, Brzozowski #see the list of open questions in #Brzozowski, 1980## conjectured that the congruence classes on words generated by x n+1 = x n , are all regular sets. Recently, McCammond #1991# extended this conjecture to all semigroups satisfying x m+n = x n and investigated the decidability of their word problems. These conjectures have been the topic of recent research, whichwe summarize here. Consider the set A # of #nite words over some #nite alphabet A containing at least two letters, and suppose weidentify certain repetitious words. #The case jAj = 1 is patently uninteresting.# Speci#cally,aword of the form ux m+n ...