Hostname: page-component-74656f9884-rdgjk Total loading time: 0 Render date: 2026-11-09T00:36:33.170Z Has data issue: false hasContentIssue false
  • English
  • Français

Three complexity functions

Published online by Cambridge University Press:  23 November 2011

Sébastien Ferenczi  and
Pascal Hubert
Sébastien Ferenczi
Affiliation:
Institut de Mathématiques de Luminy, CNRS UMR 6206, Case 907, 163 av. de Luminy, 13288 Marseille Cedex 9, France. ferenczi@iml.univ-mrs.fr Fédération de Recherche des Unités de Mathématiques de Marseille, CNRS FR, 2291, France
Pascal Hubert
Affiliation:
Fédération de Recherche des Unités de Mathématiques de Marseille, CNRS FR, 2291, France Laboratoire d’Analyse, Topologie et Probabilités, CNRS UMR 6632, Case A, Faculté de Saint Jérôme, Avenue Escadrille Normandie-Niemen, 13397 Marseille Cedex 20, France; hubert@cmi.univ-mrs.fr

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

For an extensive range of infinite words, and the associated symbolic dynamical systems, we compute, together with the usual language complexity function counting the finite words, the minimal and maximal complexity functions we get by replacing finite words by finite patterns, or words with holes.

Keywords

Infinite wordssymbolic dynamical systemscomplexity

References

P. Alesssandri, Codages de rotations et basses complexités. Université Aix-Marseille II, Ph.D. thesis (1996).
Avila, A. and Forni, G., Weak mixing for interval exchange maps and translation flows, Ann. Math. (2) 165 (2007) 637 − 664. Google Scholar
Castiglione, G., Restivo, A. and Salemi, S., Patterns in words and languages. Discrete Appl. Math. 144 (2004) 237 − 246. Google Scholar
J. Chaika, Topological mixing for some residual sets of interval exchange transformations. Preprint (2011).
I.P. Cornfeld, S.V. Fomin and Y.G. Sinai, Ergodic theory. Translated from the Russian by A.B. Sosinski, Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences]. Springer-Verlag, New York 245 (1982) x+486.
Coven, E.M. and Hedlund, G.A., Sequences with minimal block growth. Math. Syst. Theory 7 (1973) 138–153. Google Scholar
Ferenczi, S., Complexity of sequences and dynamical systems. Combinatorics and number theory (Tiruchirappalli, 1996). Discrete Math. 206 (1999) 145–154. Google Scholar
Kamae, T., Uniform sets and complexity. Discrete Math. 309 (2009) 3738 − 3747. Google Scholar
T. Kamae, Behavior of various complexity functions. Preprint (2011).
Kamae, T. and Zamboni, L., Sequence entropy and the maximal pattern complexity of infinite words. Ergod. Theory Dyn. Syst. 22 (2002) 1191–1199. Google Scholar
Kamae, T. and Zamboni, L., Maximal pattern complexity for discrete systems. Ergod. Theory Dyn. Syst. 22 (2002) 1201–1214. Google Scholar
Kamae, T., Rao, H., Tan, B. and Xue, Y.-M., Super-stationary set, subword problem and the complexity. Discrete Math. 309 (2009) 4417–4427. Google Scholar
Keane, M.S., Non-ergodic interval exchange transformations. Israe"l J. Math. 26 (1977), 188–196. Google Scholar
D. Lind and B. Marcus, An introduction to symbolic dynamics and coding. Cambridge University Press, Cambridge (1995) xvi+495.
Morse, M. and Hedlund, G.A., Symbolic dynamics. Amer. J. Math. 60 (1938) 815–866. Google Scholar
Morse, M. and Hedlund, G.A., Symbolic dynamics II. Sturmian trajectories. Amer. J. Math. 62 (1940) 1 − 42. Google Scholar
N. Pytheas-Fogg, Substitutions in dynamics, arithmetics and combinatorics. Lect. Notes Math. 1794, edited by V. Berthé, S. Ferenczi, C. Mauduit and A. Siegel. Springer-Verlag, Berlin (2002).
Rote, G., Sequences with subword complexity 2n. J. Number Theory 46 (1994) 196–213. Google Scholar