Periodicity and ultimate periodicity of D0L systems (Q807022): Difference between revisions

The paper considers periodic and ultimately periodic DOL systems see e.g. \textit{T. Head} and \textit{B. Lando} [Periodic DOL languages, Theor. Comput. Sci. 46, 83-89 (1986; Zbl 0628.68058)], \textit{T. Harju} and \textit{M. Linna} [RAIRO, Inf. Theoret. 20, 47-54 (1986; Zbl 0608.68065)] and \textit{J. J. Pansiot} [RAIRO Inf. Theoret. 20, 43-46 (1986; Zbl 0617.68063)]. Bounds for the index and period of a periodic DOL system as well as for the index and period of an ultimately periodic DOL system are given. Using this, a decision procedure for ultimate periodicity with arbitrary index and period is presented. It is also shown that the set of words w such that the DOL system (A,h,w) is ultimately periodic is a constructable regular set.