Some properties of C^ -words with applications

MaRDI QIDQ1357249zbMATH OpenFDO

Authors C. L. Shen, Yunbao Huang

Publication date 8 December 1997

Published in Southeast Asian Bulletin of Mathematics (Search for Journal in Brave)

zbMATH Keywords

\(C^ \infty\)-word derivative of a word Kolakoski sequence

Mathematics Subject Classification ID

Sequences and sets (11B99) Combinatorics on words (68R15)

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.

Recommendations

Cited in

(10)

This page was built for publication: Some properties of \(C^ \infty\)-words with applications

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1357249)