Behavior of various complexity functions
type: Item
instance of: scholarly article
title: Behavior of various complexity functions
zbMATH Open document ID: 1260.68312
author: Teturo Kamae
published in: Theoretical Computer Science
publication date: 2012-03-13T00:00:00Z
review text: 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)].
Mathematics Subject Classification ID: 68R15
Mathematics Subject Classification ID: 68Q45
Mathematics Subject Classification ID: 37B10
Mathematics Subject Classification ID: 37B40
zbMATH DE Number: 6014336
zbMATH Keywords: subword complexity
zbMATH Keywords: maximal pattern complexity
zbMATH Keywords: minimal pattern complexity
zbMATH Keywords: uniform complexity
reviewed by: Jeffrey Shallit
MaRDI profile type: Publication
full work available at URL: j.tcs.2011.11.012
OpenAlex ID: W1980974263
cites work: Three complexity functions
cites work: Substitutions in dynamics, arithmetics and combinatorics
cites work: Combinatorial lemmas and applications to dynamics
cites work: Sequence entropy and the maximal pattern complexity of infinite words
cites work: Maximal pattern complexity for discrete systems
cites work: Language structure of pattern Sturmian words
cites work: Maximal pattern complexity of two-dimensional words
cites work: Maximal pattern complexity of words over \(\ell\) letters
cites work: Uniform sets and complexity
cites work: Super-stationary set, subword problem and the complexity
cites work: On maximal pattern complexity of some automatic words
cites work: Uniform sets and super-stationary sets over general alphabets
cites work: Partitions by congruent sets and optimal positions
cites work: Maximal pattern complexity, dual system and pattern recognition
DOI: 10.1016/J.TCS.2011.11.012
Recommended article: Factor complexity
Recommended article: Three complexity functions
Recommended article: On the complexity of infinite sequences
Recommended article: On maximal pattern complexity of some automatic words
Recommended article: Modified complexity and *-Sturmian word
Recommended article: Drunken man infinite words complexity
Recommended article: Q4432080
Recommended article: Automata calculating the complexity of automatic sequences
Recommended article: Q4432079
Recommended article: Complexity of infinite sequences with zero entropy
description: scientific article; zbMATH DE number 6014336