Penn Arts & Sciences Logo

Probability and Combinatorics

Tuesday, October 15, 2002 - 4:30pm

Irina Gheorghiciuc

Penn

Location

University of Pennsylvania

DRL 4N30

The subword complexity function of an infinite word w on a finite alphabet A assigns to each positive integer the number of distinct subwords of length n of w. For every infinite binary word w on the alphabet {0,1} which contains an infinite number of 1's, we introduce a function which measures the distances between consecutive 1's in this word, called the gap function. We obtain formulas for the subword complexity of infinite binary words whose gap function is one-to-one or non-decreasing. We also give a necessary and sufficient condition for a function f : N => N to be a subword complexity function of an infinite word whose gap function is strictly increasing. The result is generalized to infinite words whose gap function is one-to-one.