Long words: The theory of concatenation and \(\omega\)-power (Q5941292): Difference between revisions
From MaRDI portal
Created a new Item |
Added link to MaRDI item. |
||
links / mardi / name | links / mardi / name | ||
Revision as of 01:49, 30 January 2024
scientific article; zbMATH DE number 1635457
Language | Label | Description | Also known as |
---|---|---|---|
English | Long words: The theory of concatenation and \(\omega\)-power |
scientific article; zbMATH DE number 1635457 |
Statements
Long words: The theory of concatenation and \(\omega\)-power (English)
0 references
20 August 2001
0 references
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.
0 references
Series product
0 references
-power
0 references
Axiomatization
0 references
Choueka automata
0 references