Some non finitely generated monoids of repetition-free endomorphisms.

DOI10.1016/S0020-0190(02)00354-XMaRDI QIDQ1853181zbMATH OpenOpenAlexFDO

Authors Yanyan Li

Publication date 21 January 2003

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/s0020-0190(02)00354-x

zbMATH Keywords

Combinatorics on wordsFormal languagesMorphismsPrimitive words

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Review text

We answer a question raised by Mitrana in Information Processing Letters 64 about primitive morphisms, that is, morphisms that preserve primitiveness of words. Given an alphabet \(A\) with \(\text{Card} (A)\geqslant2\), the monoid of primitive endomorphisms on \(A\) and the monoid of primitive uniform endomorphisms on \(A\) are not finitely generated. Moreover we show that it is also the case for the following monoids: the monoid of overlap-free (uniform) endomorphisms on \(A\) (when \(\text{Card} (A)\geqslant3)\), the monoid of \(k\)-power-free (uniform) endomorphisms on \(A\) (when \(\text{Card} (A)\geqslant2\) and \(k\geqslant3)\).

Recommendations

• The finiteness problem for monoids of morphisms.
• On the periodicity of morphisms on free monoids
• Periodic endomorphisms of a free monoid
• Monogenic endomorphisms of a free monoid
• Primitive morphisms

Cites work

• A test-set fork-power-free binary morphisms
• Avoidable patterns in strings of symbols
• Characterization of test-sets for overlap-free morphisms
• scientific article; zbMATH DE number 3723890 (Why is no real title available?)
• scientific article; zbMATH DE number 3995996 (Why is no real title available?)
• scientific article; zbMATH DE number 1413186 (Why is no real title available?)
• Overlap-free morphisms and finite test-sets
• Primitive morphisms
• Sharp characterizations of squarefree morphisms
• Some results on k-power-free morphisms
• Uniformly growing k-th power-free homomorphisms

Cited in

(8)

• Sequences generated by infinitely iterated morphisms
• Overlap-free morphisms and finite test-sets
• Existence of finite test-sets for k-power-freeness of uniform morphisms
• A characterization of free pairs of upper triangular free monoid morphisms
• scientific article; zbMATH DE number 1047906 (Why is no real title available?)
• The finiteness problem for monoids of morphisms.
• On stabilizers of infinite words
• There are \(k\)-uniform cubefree binary morphisms for all \(k \geq 0\)

This page was built for publication: Some non finitely generated monoids of repetition-free endomorphisms.

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1853181)