Some combinatorial properties of infinite words and applications to semigroup theory (Q1917528): Difference between revisions

The main result, which generalizes a theorem of de Luca and Varrichio, is that a finitely generated semigroup \(S\) is finite if and only if \(S\) has the \(\omega\)-iteration property, which means that for each infinite sequence \(T\): \(s_1,s_2,\dots\) of elements of \(S\) there exists \(n\geq 1\), depending on \(T\), and \(i,j\in\{1,2,\dots,n\}\) such that \[ s_ns_{n-1}\dots s_2s_1=s_ns_{n-1}\dots s_{i+1}(s_i\dots s_j)^2s_{j-1}\dots s_2s_1. \] The proof makes use of bi-ideal sequences and Ramsey's Theorem. Earlier in the paper, theorems of Konig and of Shirshov are the inspiration for a new proof of the result of Restivo and Reutenauer that a finitely generated semigroup \(S\) is finite if and only if \(S\) is periodic and permutable. The proof is based on the notion of a word \(x\) being \(n\)-divided, meaning that \(x\) can be written as a product of \(n\) factors which is greater in the lexicographic ordering than all words \(x_\sigma\) formed by permuting these factors.