Mathematics – Combinatorics
Scientific paper
2005-12-13
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.
No associations
LandOfFree
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.
Profile ID: LFWR-SCP-O-36546