On the periodicity of morphisms on free monoids

DOI10.1051/ita/1986200100471zbMath0608.68065OpenAlexW34101780MaRDI QIDQ3747748

Matti Linna, Tero J.Harju

Publication date: 1986

Published in: RAIRO - Theoretical Informatics and Applications (Search for Journal in Brave)

Full work available at URL: https://eudml.org/doc/92245

zbMATH Keywords

D0L systemsprimitive wordsfinitely generated free monoidD0L periodicity problemperiodic \(\omega \)-words

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Free semigroups, generators and relations, word problems (20M05) Semigroups in automata theory, linguistics, etc. (20M35) Grammars and rewriting systems (68Q42)

Related Items (27)

Automatic sequences of rank two ⋮ Periodic D0L languages ⋮ Bounded D0L languages ⋮ Prefixes of infinite words and ambiguous context-free languages ⋮ On the subword equivalence problem for morphic words ⋮ Asymptotic behaviour of bi-infinite words ⋮ Presentations of Schützenberger groups of minimal subshifts. ⋮ Properties of infinite words : Recent results ⋮ Iterative devices generating infinite words ⋮ On the factors of automatic words ⋮ Decidable problems in substitution shifts ⋮ The set of strings mapped into a submonoid by iterates of a morphism ⋮ Periodicity Problem of Substitutions over Ternary Alphabets ⋮ If a DOL language is k-power free then it is circular ⋮ An algorithm for enumerating all infinite repetitions in a D0L-system ⋮ Relations on words ⋮ Cancellation and periodicity properties of iterated morphisms ⋮ Regularity of sets of initial strings of periodic D0L-systems ⋮ Iterative algebras. ⋮ Periodicity of morphic words ⋮ Coding of substitution dynamical systems as shifts of finite type ⋮ On the simplification of infinite morphic words ⋮ A DECISION PROBLEM FOR ULTIMATELY PERIODIC SETS IN NONSTANDARD NUMERATION SYSTEMS ⋮ DECIDABILITY OF UNIFORM RECURRENCE OF MORPHIC SEQUENCES ⋮ On D0L power series ⋮ On D0L systems with immigration ⋮ Periodicity and ultimate periodicity of D0L systems

Cites Work

• The equations \(h(w)=w^ n\) in binary alphabets
• The ultimate equivalence problem for DOL systems
• The decidability of the dol prefix problem
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: On the periodicity of morphisms on free monoids