Finiteness and iteration conditions for semigroups (Q1177143): Difference between revisions

The article investigates iteration conditions of regular and finitely generated semigroups. Let \(S\) be a semigroup and \(m\) and \(n\) two integers such that \(m>0\) and \(n\geq 0\). We say that \(S\) verifies the iteration property \(C(n,m)\) if the following condition is verified: For any sequence \(s_ 1,s_ 2,\dots,s_ m\) of \(m\) elements of \(S\) there exists \(i,j\) such that \(1\leq i\leq j\leq m\) and \(s_ 1\dots s_ m=s_ 1\dots s_{i-1}(s_ i\dots s_ j)^ n s_{j+1}\dots s_ m\). The main result is that if a finitely generated semigroup \(S\) satisfies \(C(2,m)\) or \(C(3,m)\) for a suitable \(m>0\) then \(S\) is finite. This result gives a partial answer to a question raised in \textit{A. Ehrenfeucht}, \textit{R. Parikh} and \textit{G. Rozenberg} [SIAM J. Comput. 10, 536-541 (1981; Zbl 0461.68081)]. The result has an important application in the theory of automata and regular languages. It is also associated with solutions of the Burnside problem for semigroups (and groups [\textit{G. Lallement}, Semigroups and combinatorial applications. Wiley, New York (1979; Zbl 0421.20025)].