Repetitiveness of languages generated by morphisms (Q1575438): Difference between revisions

From MaRDI portal
RedirectionBot (talk | contribs)
Removed claims
Set OpenAlex properties.
 
(3 intermediate revisions by 3 users not shown)
Property / author
 
Property / author: Yuji Kobayashi / rank
 
Normal rank
Property / author
 
Property / author: Friedrich Otto / rank
 
Normal rank
Property / MaRDI profile type
 
Property / MaRDI profile type: MaRDI publication profile / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q3859267 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Every iterated morphism yields a co-CFL / rank
 
Normal rank
Property / cites work
 
Property / cites work: Simplifications of homomorphisms / rank
 
Normal rank
Property / cites work
 
Property / cites work: On the subword complexity of square-free DOL languages / rank
 
Normal rank
Property / cites work
 
Property / cites work: Repetition of subwords in DOL languages / rank
 
Normal rank
Property / cites work
 
Property / cites work: The equations \(h(w)=w^ n\) in binary alphabets / rank
 
Normal rank
Property / cites work
 
Property / cites work: Periodic D0L languages / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q5592246 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q4529547 / rank
 
Normal rank
Property / cites work
 
Property / cites work: If a DOL language is k-power free then it is circular / rank
 
Normal rank
Property / cites work
 
Property / cites work: Proof of Dejean's conjecture for alphabets with \(5, 6, 7, 8, 9, 10\) and \(11\) letters / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q4140407 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q4023070 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q3835038 / rank
 
Normal rank
Property / full work available at URL
 
Property / full work available at URL: https://doi.org/10.1016/s0304-3975(99)00238-8 / rank
 
Normal rank
Property / OpenAlex ID
 
Property / OpenAlex ID: W2083357883 / rank
 
Normal rank

Latest revision as of 09:05, 30 July 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
    0 references
    0 references

    Identifiers