Languages under substitutions and balanced words

Alex Heinis[1]

  • [1] Rode Kruislaan 1403 D 1111 XD Diemen, Pays-Bas

Journal de Théorie des Nombres de Bordeaux (2004)

  • Volume: 16, Issue: 1, page 151-172
  • ISSN: 1246-7405

Abstract

top
This paper consists of three parts. In the first part we prove a general theorem on the image of a language under a substitution, in the second we apply this to the special case when is the language of balanced words and in the third part we deal with recurrent Z-words of minimal block growth.

How to cite

top

Heinis, Alex. "Languages under substitutions and balanced words." Journal de Théorie des Nombres de Bordeaux 16.1 (2004): 151-172. <http://eudml.org/doc/249243>.

@article{Heinis2004,
abstract = {This paper consists of three parts. In the first part we prove a general theorem on the image of a language $K$ under a substitution, in the second we apply this to the special case when $K$ is the language of balanced words and in the third part we deal with recurrent Z-words of minimal block growth.},
affiliation = {Rode Kruislaan 1403 D 1111 XD Diemen, Pays-Bas},
author = {Heinis, Alex},
journal = {Journal de Théorie des Nombres de Bordeaux},
keywords = {substitutions; subword complexity; balanced word},
language = {eng},
number = {1},
pages = {151-172},
publisher = {Université Bordeaux 1},
title = {Languages under substitutions and balanced words},
url = {http://eudml.org/doc/249243},
volume = {16},
year = {2004},
}

TY - JOUR
AU - Heinis, Alex
TI - Languages under substitutions and balanced words
JO - Journal de Théorie des Nombres de Bordeaux
PY - 2004
PB - Université Bordeaux 1
VL - 16
IS - 1
SP - 151
EP - 172
AB - This paper consists of three parts. In the first part we prove a general theorem on the image of a language $K$ under a substitution, in the second we apply this to the special case when $K$ is the language of balanced words and in the third part we deal with recurrent Z-words of minimal block growth.
LA - eng
KW - substitutions; subword complexity; balanced word
UR - http://eudml.org/doc/249243
ER -

References

top
  1. J. Berstel, M. Pocchiola, A geometric proof of the enumeration formula for Sturmian words. Internat. J. Algebra Comput. 3 (1993), 394–355. Zbl0802.68099MR1240390
  2. J. Cassaigne, Complexité et facteurs spéciaux. Bull. Belg. Math. Soc. 4 (1997), 67–88. Zbl0921.68065MR1440670
  3. E.M. Coven, G.A. Hedlund, Sequences With Minimal Block Growth. Math. Systems Th. 7 (1971), 138–153. Zbl0256.54028MR322838
  4. N.J. Fine, H.S. Wilf, Uniqueness theorems for periodic functions. Proc. Amer. Math. Soc. 16 (1965), 109–114. Zbl0131.30203MR174934
  5. A. Heinis, Arithmetics and combinatorics of words of low complexity. Doctor’s Thesis Rijksuniversiteit Leiden (2001). Available on http://www.math.leidenuniv.nl/~tijdeman Zbl1136.68302
  6. M. Lothaire, Mots. Hermès Paris 1990. Zbl0862.05001MR1252659
  7. A. de Luca, F. Mignosi, Some combinatorial properties of Sturmian words. Theoret. Comp. Sci. 136 (1994), 361–385. Zbl0874.68245MR1311214
  8. F. Mignosi, On the number of factors of Sturmian words. Theoret. Comp. Sci. 82 (1991), 71–84. Zbl0728.68093MR1112109
  9. F. Mignosi, P. Séébold, Morphismes sturmiens et règles de Rauzy. J. Th. Nombres Bordeaux 5 (1993), 211–233. Zbl0797.11029MR1265903
  10. M. Morse, G.A. Hedlund, Symbolic dynamics II: Sturmian trajectories. Amer. J. Math. 62 (1940), 1–42. Zbl0022.34003MR745
  11. R. Tijdeman, Intertwinings of periodic sequences. Indag. Math. 9 (1998), 113–122. Zbl0918.11012MR1618219

NotesEmbed ?

top

You must be logged in to post comments.