# A periodicity property of iterated morphisms

RAIRO - Theoretical Informatics and Applications (2007)

- Volume: 41, Issue: 2, page 215-223
- ISSN: 0988-3754

## Access Full Article

top## Abstract

top## How to cite

topHonkala, Juha. "A periodicity property of iterated morphisms." RAIRO - Theoretical Informatics and Applications 41.2 (2007): 215-223. <http://eudml.org/doc/250038>.

@article{Honkala2007,

abstract = {Suppose ƒ : X* → X* is a morphism and u,v ∈ X*. For every nonnegative integer n, let zn be the longest common
prefix of ƒn(u) and ƒn(v), and let un,vn ∈ X* be words such
that ƒn(u) = znun and ƒn(v) = znvn. We prove that there is a positive
integer q such that for any positive integer p, the prefixes of un
(resp. vn) of length p form an ultimately periodic sequence having period
q. Further, there is a value of q which works for all words u,v ∈ X*.},

author = {Honkala, Juha},

journal = {RAIRO - Theoretical Informatics and Applications},

keywords = {Iterated morphism; periodicity},

language = {eng},

month = {7},

number = {2},

pages = {215-223},

publisher = {EDP Sciences},

title = {A periodicity property of iterated morphisms},

url = {http://eudml.org/doc/250038},

volume = {41},

year = {2007},

}

TY - JOUR

AU - Honkala, Juha

TI - A periodicity property of iterated morphisms

JO - RAIRO - Theoretical Informatics and Applications

DA - 2007/7//

PB - EDP Sciences

VL - 41

IS - 2

SP - 215

EP - 223

AB - Suppose ƒ : X* → X* is a morphism and u,v ∈ X*. For every nonnegative integer n, let zn be the longest common
prefix of ƒn(u) and ƒn(v), and let un,vn ∈ X* be words such
that ƒn(u) = znun and ƒn(v) = znvn. We prove that there is a positive
integer q such that for any positive integer p, the prefixes of un
(resp. vn) of length p form an ultimately periodic sequence having period
q. Further, there is a value of q which works for all words u,v ∈ X*.

LA - eng

KW - Iterated morphism; periodicity

UR - http://eudml.org/doc/250038

ER -

## References

top- A. Ehrenfeucht and G. Rozenberg, Elementary homomorphisms and a solution of the D0L sequence equivalence problem. Theoret. Comput. Sci.7 (1978) 169–183. Zbl0407.68085
- A. Ehrenfeucht, K.P. Lee and G. Rozenberg, Subword complexities of various classes of deterministic developmental languages without interactions. Theoret. Comput. Sci.1 (1975) 59–75. Zbl0316.68043
- G.T. Herman and G. Rozenberg, Developmental Systems and Languages. North-Holland, Amsterdam (1975). Zbl0306.68045
- J. Honkala, The equivalence problem for DF0L languages and power series. J. Comput. Syst. Sci.65 (2002) 377–392. Zbl1059.68062
- G. Rozenberg and A. Salomaa, The Mathematical Theory of L Systems. Academic Press, New York (1980). Zbl0508.68031
- G. Rozenberg and A. Salomaa (Eds.), Handbook of Formal Languages. Vol. 1–3, Springer, Berlin (1997). Zbl0866.68057
- A. Salomaa, Jewels of Formal Language Theory. Computer Science Press, Rockville, Md. (1981). Zbl0487.68063

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.