Some properties of \(C^ \infty\)-words with applications
type: Item
instance of: scholarly article
title: Some properties of \(C^ \infty\)-words with applications
zbMATH Open document ID: 0877.68095
author: C. L. Shen
author: Yunbao Huang
published in: Southeast Asian Bulletin of Mathematics
publication date: 1997-12-08T00:00:00Z
review text: The Kolakoski sequence is the sequence of 1's and 2's beginning with 1, such that the sequence of lengths of consecutive blocks of 1's and 2's is the initial sequence itself. This sequence begins with 122112122\dots [see \textit{W. Kolakoski}, Self generating runs, Problem 5304, Am. Math. Mon. 73, 681-682 (1966)]. Not much is known concerning this sequence [see \textit{F. M. Dekking}, Sémin. Théorie Nombres Bordeaux 1979-1980, Exposé, No. 9 (1980; Zbl 0438.10040), and Exposé 31 (1981; Zbl 0472.10054)]. Note two misprints in these references in the paper under review. Dekking proposed the notion of (finite) \(C^\infty\)-word: this is a word that can be differentiated an infinite number of times. The derivative of a word on \(\{1,2\}\) without any occurrence of 111 or 222 is the word whose \(j\)th symbol is the length of the \(j\)th run of 1's or 2's in this word (discarding the first and last run if their length is 1). For example \((122112)'=22\). Dekking noted that every finite subword of the Kolakoski sequence is \(C^\infty\). The authors study the minimal and maximal number of 2's in a \(C^\infty\) word of length \(n\) and obtain interesting estimations for these quantities. In particular, they give a partial answer to a question of J. Shallit.
Mathematics Subject Classification ID: 68R15
Mathematics Subject Classification ID: 11B99
zbMATH DE Number: 1022776
zbMATH Keywords: derivative of a word
zbMATH Keywords: \(C^ \infty\)-word
zbMATH Keywords: Kolakoski sequence
reviewed by: Jean-Paul Allouche
MaRDI profile type: Publication
Recommended article: Q4848914
Recommended article: A note on the complexity of \(C^{\infty }\)-words
Recommended article: On a conjecture of powers of \(C^{\infty}\)-words
Recommended article: Properties of infinite words : Recent results
Recommended article: Some combinatorial properties of infinite words and applications to semigroup theory
Recommended article: Q4374003
Recommended article: On the number of \(C^{\infty}\)-words of each length
Recommended article: On repeated factors in \(C^\infty\)-words
Recommended article: Q4364281
Recommended article: About the number of \(C^\infty \)-words of form \(\widetilde wxw \)
description: scientific article; zbMATH DE number 1022776