Long words: The theory of concatenation and \(\omega\)-power (Q5941292): Difference between revisions

It is shown that for any set \(A,\) the algebra of ordinal words on the alphabet \(A\) equipped with the operations of concatenation and \(\omega\)-power is axiomatized by the equations \(x\cdot(y\cdot z)=(x\cdot y)\cdot z\), \((x\cdot y)^{\omega}=x\cdot(y\cdot x)^{\omega}\), \((x^{n})^{\omega}=x^{\omega}\), \(n\geqslant\)1. Indeed, the algebra freely generated by \(A\) in the variety determined by these equations is the algebra of tail-finite ordinal words of length \(<\omega^{\omega}\) on the alphabet \(A.\) It is further shown that this collection of identities cannot be replaced by any finite set. Last, a polynomial algorithm is given for recognizing when two terms denote the same tail-finite ordinal word.