×

Periodicity and ultimate periodicity of D0L systems. (English) Zbl 0729.68038

The paper considers periodic and ultimately periodic DOL systems see e.g. T. Head and B. Lando [Periodic DOL languages, Theor. Comput. Sci. 46, 83-89 (1986; Zbl 0628.68058)], T. Harju and M. Linna [RAIRO, Inf. Theoret. 20, 47-54 (1986; Zbl 0608.68065)] and 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.
Reviewer: M.Linna (Naasa)

MSC:

68Q42 Grammars and rewriting systems
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Ehrenfeucht, A.; Rozenberg, G., Simplifications of homomorphisms, Inform. and Control, 38, 298-309 (1978) · Zbl 0387.68062
[2] Harju, T.; Linna, M., On the periodicity of morphisms on free monoids, Theoret. Inform. Appl., 20, 47-54 (1986) · Zbl 0608.68065
[3] Head, T., Expanded subalphabets in the theories of languages and semigroups, Internat. J. Comput. Math., 12, 113-123 (1982) · Zbl 0496.68050
[4] Head, T.; Lando, B., Fixed and stationary \(ω\)-words and \(ω\)-languages, (Rozenberg, G.; Salomaa, A., The Book of L (1986), Springer: Springer New York) · Zbl 0586.68063
[5] Head, T.; Lando, B., Periodic D0L languages, Theoret. Comput. Sci., 46, 83-89 (1986) · Zbl 0628.68058
[6] Head, T.; Lando, B., Regularity of sets of initial strings of periodic D0L systems, Theoret. Comput. Sci., 48, 101-108 (1986) · Zbl 0626.68055
[7] Head, T.; Lando, B., Bounded D0L languages, Theoret. Comput. Sci., 51, 255-264 (1987) · Zbl 0636.68097
[8] Head, T.; Lando, B., Eigenwords and periodic behaviors, Proc. Workshop on Sequences (June, 1988), to appear
[9] Pansiot, J. J., Decidability of periodicity for infinite words, Theoret. Inform. Appl., 20, 43-46 (1986) · Zbl 0617.68063
[10] Rozenberg, G.; Salomaa, A., The Mathematical Theory of L Systems (1980), Academic Press: Academic Press New York · Zbl 0365.68072
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.