Behavior of various complexity functions (Q764361): Difference between revisions

In this paper the author continues his study of pattern complexity. Let \(\mathbf{w}\) be an infinite word indexed by \(\mathbb{N} = \{ 0,1,2,\dots \}\). In block complexity (aka ``subword complexity'' or sometimes just ``complexity''), we count the number of distinct factors of length \(n\) appearing in \(\mathbf{w}\). Maximal pattern complexity, by contrast, counts the maximal number of scattered (non-contiguous) subwords obtainable by fixing a set of offsets of cardinality \(n\), and ``sweeping it across'' \(\mathbf{w}\), counting the number of distinct words so obtained. Minimal pattern complexity is defined analogously. Here the author studies a generalization from infinite words to closed subsets \(\Omega\) of \(A^{\mathbb{N}}\), where \(A\) is a finite alphabet. (The original notions correspond to the case where \(\Omega\) is the orbit closure of an infinite word.) In particular he calls \(\Omega\) uniform if all three notions of complexity mentioned above coincide. A number of results are proved, including a characterization of block complexity, and inequalities for the case where \(\Omega\) is stationary and transitive. The paper suffers somewhat from language problems and could have benefited from editorial assistance. Reference [1] has now appeared: [\textit{S. Ferenczi} and \textit{P. Hubert}, RAIRO, Theor. Inform. Appl. 46, No. 1, 67--76 (2012; Zbl 1271.37012)].