Repetitiveness of languages generated by morphisms (Q1575438)

From MaRDI portal
Revision as of 03:59, 5 March 2024 by Import240304020342 (talk | contribs) (Set profile property.)
scientific article
Language Label Description Also known as
English
Repetitiveness of languages generated by morphisms
scientific article

    Statements

    Repetitiveness of languages generated by morphisms (English)
    0 references
    21 August 2000
    0 references
    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.
    0 references
    D0L-language
    0 references
    Repetitive morphism
    0 references
    Quasi-repetitive element
    0 references
    0 references
    0 references

    Identifiers