Paper Info
Title
Periodicity and ultimate periodicity of DOL systems
Abstract
A unified presentation of periodicity and ultimate periodicity of D0L systems is given. Bounds are provided for the period and index of periodic systems, and simplified algorithms are obtained by using elementary morphisms. It was shown previously (Harju and Linna, 1986; Pansiot, 1986) that if ( A, h, w ) is a D0L system with h ( w )= wy , then it is decidable whether the ω -word h ω ( w ) is ultimately periodic, i.e., of the form xu ω . In this paper a decision procedure is given to decide if there are an index i and a period p such that h p ( h i ( w ))= h i ( w ) y and h ωp ( h i ( w )) is ultimately periodic. Given a morphism h:A ∗ → A ∗ , bounds are obtained for the period and index of ultimately periodic systems. It is also shown that the set {wϵA ∗ |h ωp (h i (w)} is ultimately periodic} is a constructable regular language.
Year
DOI
Venue
1991
10.1016/0304-3975(91)90169-3
Theor. Comput. Sci.
Keywords
DocType
Volume
DOL system,ultimate periodicity
Journal
82
Issue
ISSN
Citations 
1
Theoretical Computer Science
4
PageRank 
References 
Authors
0.88
3
1
Name
Order
Citations
PageRank
Barbara Lando140.88