Repetitiveness of languages generated by morphisms (Q1575438): Difference between revisions
From MaRDI portal
Added link to MaRDI item. |
Removed claims |
||
Property / author | |||
Property / author: Yuji Kobayashi / rank | |||
Property / author | |||
Property / author: Friedrich Otto / rank | |||
Revision as of 17:15, 12 February 2024
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