Simple Search

Query:

Enter a query and click »Search«...

Format:

Display: entries per page entries

Zbl 1216.68204
Cassaigne, Julien; Nicolas, François
Factor complexity. (English)
[A] Berthé, Valérie (ed.) et al., Combinatorics, automata, and number theory. Cambridge: Cambridge University Press. Encyclopedia of Mathematics and its Applications 135, 163-217 (2010). ISBN 978-0-521-51597-9/hbk

Introduction: Given an infinite word, we can study the language of its finite factors. Intuitively, we expect that `simple' words (because they are generated by simple devices, or have some regularity property) will also have a `simple' language of factors. One way to quantify this is to just count factors of each length. In doing so, we associate a function with the infinite word considered: its factor complexity function. This function was introduced in 1938 by {\it G. A. Hedlund} and {\it M. Morse} [Am. J. Math. 60, 815--866 (1938; Zbl 0019.33502)] under the name block growth as a tool to study symbolic dynamical systems. The name subword complexity was given in 1975 by Andrzej Ehrenfeucht, Kwok Pun Lee and Grzegorz Rozenberg. Here we use, factor complexity for consistence with the use of factor. Factor complexity should not be confused with other notions of complexity, like algorithmic complexity or Kolmogorov complexity. We shall not use them here, and by `complexity' we always mean `factor complexity'.

MSC 2000:: *68R15 Combinatorics on words
11B83 Special sequences of integers and polynomials

Keywords: infinite words; language of finite factors; factor complexity function

Citations: Zbl 0019.33502

Comment on this Item PDF MathML XML ASCII DVI PS BibTeX Online Ordering

	Scientific prize winners of the ICM 2010
	Overhang
	Lie groups, physics and geometry. An introduction for physicists, engineers and chemists.

Simple Search

Zentralblatt MATH Berlin [Germany]