Long words: The theory of concatenation and \(\omega\)-power (Q5941292): Difference between revisions
From MaRDI portal
Set profile property. |
ReferenceBot (talk | contribs) Changed an Item |
||
Property / cites work | |||
Property / cites work: Nonfinite axiomatizability of shuffle inequalities / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Free shuffle algebras in language varieties / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Finite automata, definable sets, and regular expressions over \(\omega^n\)- tapes / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4218143 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4222756 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3123633 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3253173 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4036596 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: AN ALGEBRAIC THEORY FOR REGULAR LANGUAGES OF FINITE AND INFINITE WORDS / rank | |||
Normal rank |
Latest revision as of 19:23, 3 June 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