Periodic D0L languages

DOI10.1016/0304-3975(86)90023-XMaRDI QIDQ1093376zbMATH OpenFDO

Authors Tom Head, Barbara Lando

Publication date 1986

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

Full work available at URL https://doi.org/10.1016/0304-3975(86)90023-X

zbMATH Keywords

D0L-systemsformal languagefree semigroupsperiodicity of words

Mathematics Subject Classification ID

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

Review text

The following problem in combinatorial semigroup theory and in formal language theory is proved to be decidable. Given a morphism \(h:A^*\to A^*\) and a word \(w\in A^*\) over the alphabet A, is the sequence w, h(w), \(h^ 2(w)\),... eventually periodic, that is, does there exist integers i, p and \(e>0\) such that \(h^{i+p}(w)=(h^ i(w))^ e\)?

Recommendations

• On the periodicity of morphisms on free monoids
• scientific article; zbMATH DE number 3872709
• A new proof for the decidability of D0L ultimate periodicity
• Periodicity of morphic words
• Decidability of periodicity for infinite words

Cites work

• Code properties and homomorphisms of DOL systems
• Decidability of periodicity for infinite words
• Finite DOL languages and codes
• scientific article; zbMATH DE number 3890761 (Why is no real title available?)
• scientific article; zbMATH DE number 3811868 (Why is no real title available?)
• scientific article; zbMATH DE number 3940748 (Why is no real title available?)
• scientific article; zbMATH DE number 3767067 (Why is no real title available?)
• scientific article; zbMATH DE number 3569855 (Why is no real title available?)
• On the periodicity of morphisms on free monoids

Cited in

(13)

• Bounded D0L languages
• Repetitiveness of languages generated by morphisms
• Circular languages
• A new proof for the decidability of D0L ultimate periodicity
• scientific article; zbMATH DE number 3872709 (Why is no real title available?)
• On the periodicity of morphisms on free monoids
• scientific article; zbMATH DE number 177835 (Why is no real title available?)
• On periodically iterated morphisms
• ON THE BURNSIDE SEMIGROUPS xⁿ = x^n+m
• Regularity of sets of initial strings of periodic D0L-systems
• Periodicity and ultimate periodicity of D0L systems
• Periodic and Sturmian languages
• The set of strings mapped into a submonoid by iterates of a morphism

This page was built for publication: Periodic D0L languages

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