Repetitiveness of languages generated by morphisms

DOI10.1016/S0304-3975(99)00238-8MaRDI QIDQ1575438zbMATH OpenOpenAlexFDO

Authors Yuji Kobayashi, Friedrich Otto

Publication date 21 August 2000

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/s0304-3975(99)00238-8

zbMATH Keywords

D0L-languageQuasi-repetitive elementRepetitive morphism

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Review text

We study the repetition of subwords in languages generated by morphisms. Fundamental to our approach is the notion of quasi-repetitive elements. Using these elements we present a new characterization for repetitive morphisms, from which we derive a simple proof for the fact that a D0L-language is repetitive if and only if it is strongly repetitive [\textit{A. Ehrenfeucht} and \textit{G. Rozenberg}, Inf. Control 59, 13-35 (1983; Zbl 0549.68076)]. From this proof we obtain a structurally simple polynomial-time algorithm for deciding whether such a language is repetitive. From further results on quasi-repetitive elements we obtain as a consequence a complete characterization for all those morphisms on a two-letter alphabet that are repetitive, a result which is closely related to a result of \textit{P. Séébold} [Bull. EATCS 36, 137-151 (1988; Zbl 0678.68072)] on the D0L periodicity problem. Finally, we characterize those morphisms f on a two-letter alphabet, for which the language L(\(f\)) generated by \(f\) or the language SL(\(f\)) of subwords of L(\(f\)) are context-free or even regular.

Recommendations

• scientific article; zbMATH DE number 1361492
• scientific article; zbMATH DE number 1088280
• Repetition of subwords in DOL languages
• On k-repetition freeness of length uniform morphisms over a binary alphabet

Cites work

• Every iterated morphism yields a co-CFL
• scientific article; zbMATH DE number 4112045 (Why is no real title available?)
• scientific article; zbMATH DE number 3660804 (Why is no real title available?)
• scientific article; zbMATH DE number 107464 (Why is no real title available?)
• scientific article; zbMATH DE number 3569855 (Why is no real title available?)
• scientific article; zbMATH DE number 1737190 (Why is no real title available?)
• scientific article; zbMATH DE number 3311755 (Why is no real title available?)
• If a DOL language is k-power free then it is circular
• On the subword complexity of square-free DOL languages
• Periodic D0L languages
• Proof of Dejean's conjecture for alphabets with \(5, 6, 7, 8, 9, 10\) and \(11\) letters
• Repetition of subwords in DOL languages
• Simplifications of homomorphisms
• The equations h(w)=w^ n in binary alphabets

Cited in

(9)

• Some remarks about stabilizers
• Characterization of circular D0L-systems
• Repetition of subwords in DOL languages
• On Critical exponents in fixed points ofk-uniform binary morphisms
• scientific article; zbMATH DE number 1088280 (Why is no real title available?)
• scientific article; zbMATH DE number 1361492 (Why is no real title available?)
• An algorithm for enumerating all infinite repetitions in a D0L-system
• Automatic sequences of rank two
• On critical exponents in fixed points of non-erasing morphisms

This page was built for publication: Repetitiveness of languages generated by morphisms

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