The subword complexity of a class of infinite binary words

Details The subword complexity of a class of infinite binary words The subword complexity of a class of infinite binary words

2005-12-13

arxiv.org/abs/math/0512256v1

Mathematics

Combinatorics

29 pages, 2 figures

Scientific paper

Let $A_q$ be a $q$-letter alphabet and $w$ be a right infinite word on this alphabet. A subword of $w$ is a block of consecutive letters of $w$. The subword complexity function of $w$ assigns to each positive integer $n$ the number $f_w(n)$ of distinct subwords of length $n$ of $w$. The gap function of an infinite word over the binary alphabet $\{0,1 \}$ gives the distances between consecutive 1's in this word. In this paper we study infinite binary words whose gap function is injective or "almost injective". A method for computing the subword complexity of such words is given. A necessary and sufficient condition for a function to be the subword complexity function of a binary word whose gap function is strictly increasing is obtained.

Affiliated with

Also associated with

No associations

Rating

The subword complexity of a class of infinite binary words does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with The subword complexity of a class of infinite binary words, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and The subword complexity of a class of infinite binary words will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-36546