Hostname: page-component-cd9895bd7-gxg78 Total loading time: 0 Render date: 2024-12-27T19:56:20.722Z Has data issue: false hasContentIssue false
  • English
  • Français

Asymptotic behaviour of bi-infinite words

Published online by Cambridge University Press:  15 March 2004

Wit Foryś
Wit Foryś*
Affiliation:
Jagiellonian University, Institute of Computer Science, Nawojki 11, 30-072 Kraków, Poland; [email protected].
Get access

Abstract

We present a description of asymptotic behaviour of languages of bi-infinite words obtained by iterating morphisms defined on free monoids.

Keywords

Bi-infinite wordsmorphismsiterationboundary set.
Type
Research Article
Information
RAIRO - Theoretical Informatics and Applications , Volume 38 , Issue 1 , January 2004 , pp. 27 - 48
Copyright
© EDP Sciences, 2004

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Ehrenfeucht, A. and Rozenberg, G., Simplifications of homomorphism. Inform. Control 38 (1978) 298–309. CrossRef
Foryś, W. and Head, T., The poset of retracts of a free monoid. Int. J. Comput. Math. 37 (1990) 45–48. CrossRef
Harju, T. and Linna, M., On the periodicity of morphism on free monoid. RAIRO: Theoret. Informatics Appl. 20 (1986) 47–54.
Head, T., Expanded subalphabets in the theories of languages and semigroups. Int. J. Comput. Math. 12 (1982) 113–123. CrossRef
T. Head and V. Lando, Fixed and stationary ω-wors and ω-languages. The book of L, Springer-Verlag, Berlin (1986) 147–155.
M. Lothaire, Combinatorics on words. Addison-Wesley (1983).
J. Matyja, Sets of primitive words given by fixed points of mappings. Int. J. Comput. Math. (to appear).
P. Narbel, Limits and boundaries of words and tiling substitutions. LITP, TH93.12 (1993).
Narbel, P., The boundary of iterated morphisms on free semi-groups. Int. J. Algebra Comput. 6 (1996) 229–260. CrossRef
Shallit, J. and Wang, M., On two-sided infinite fixed points of morphisms. Lect. Notes Comput. Sci. 1684 (1999) 488–499. CrossRef