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 . (y . z) = (x . y) .z, (x . y)(omega) = x . (y . x)(omega), (x(n))omega = x(omega), n greater than or equal to1. 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. (C) 2001 Elsevier Science B.V. All rights reserved. [References: 10]
展开▼
