A periodicity property of iterated morphisms

Juha Honkala

RAIRO - Theoretical Informatics and Applications (2007)

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

Abstract

top
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*.

How to cite

top

Honkala, 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
  1. A. Ehrenfeucht and G. Rozenberg, Elementary homomorphisms and a solution of the D0L sequence equivalence problem. Theoret. Comput. Sci.7 (1978) 169–183.  
  2. 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.  
  3. G.T. Herman and G. Rozenberg, Developmental Systems and Languages. North-Holland, Amsterdam (1975).  
  4. J. Honkala, The equivalence problem for DF0L languages and power series. J. Comput. Syst. Sci.65 (2002) 377–392.  
  5. G. Rozenberg and A. Salomaa, The Mathematical Theory of L Systems. Academic Press, New York (1980).  
  6. G. Rozenberg and A. Salomaa (Eds.), Handbook of Formal Languages. Vol. 1–3, Springer, Berlin (1997).  
  7. A. Salomaa, Jewels of Formal Language Theory. Computer Science Press, Rockville, Md. (1981).  

NotesEmbed ?

top

You must be logged in to post comments.

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

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.