Periodic D0L languages
type: Item
instance of: scholarly article
title: Periodic D0L languages
zbMATH Open document ID: 0628.68058
DOI: 10.1016/0304-3975(86)90023-X
author: Tom Head
author: Barbara Lando
published in: Theoretical Computer Science
publication date: 1986-01-01T00:00:00Z
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\)?
Mathematics Subject Classification ID: 68Q45
Mathematics Subject Classification ID: 20M05
Mathematics Subject Classification ID: 20M35
Mathematics Subject Classification ID: 68Q42
zbMATH DE Number: 4022656
zbMATH Keywords: free semigroups
zbMATH Keywords: D0L-systems
zbMATH Keywords: periodicity of words
zbMATH Keywords: formal language
reviewed by: Tero Harju
MaRDI profile type: Publication
cites work: On the periodicity of morphisms on free monoids
cites work: Q3711767
cites work: Q3347325
cites work: Finite DOL languages and codes
cites work: Code properties and homomorphisms of DOL systems
cites work: Q3659988
cites work: Decidability of periodicity for infinite words
cites work: Q4140407
cites work: Q3948608
description: scientific article; zbMATH DE number 4022656