2123.sagews

Here is a very basic code to see what tangent words are, and their relation with balanced words (Sturmian factors).

def sturmian_desubstitute_as_possible(self):
    r"""
    Sturmian desubstitutes the word self as much as possible.

    The word self must be definied on a two-letter alphabet. It can be
    Sturmian desubstituted if one letter appears isolated. The
    Sturmian desubstitution consist in removing the shortest run to
    any run of the non-isolated letter. The Sturmian desubstitution is
    done as much as possible. A word is a factor of a Sturmian word
    if, and only if, the result is the empty word.
    """
    # print self
    W = self.parent()
    if (W.size_of_alphabet() != 2):
        raise TypeError, 'Your word must be defined on a binary alphabet'
    alphabet = W.alphabet()
    if self.is_empty():
        return self
    is_prefix = True
    current_run_length = 0
    prefix_length = 0
    prefix_letter = self[0]
    is_isolated = {alphabet[0]:True,alphabet[1]:True}
    minimal_run = {alphabet[0]:Infinity,alphabet[1]:Infinity}
    maximal_run = {alphabet[0]:0,alphabet[1]:0}
    runs = {alphabet[0]:[],alphabet[1]:[]}
    for i in self:
        if is_prefix:
            if i == prefix_letter:
                prefix_length += 1
                if prefix_length > 1:
                    is_isolated[i] = False
            else:
                is_prefix = False
                current_run_length = 1
                previous_letter = i
        else:
            if i == previous_letter:
                current_run_length += 1
                if current_run_length > 1:
                    is_isolated[i] = False
            else:
                runs[previous_letter].append(current_run_length)
                minimal_run[previous_letter] = min(minimal_run[previous_letter],current_run_length)
                maximal_run[previous_letter] = max(maximal_run[previous_letter],current_run_length)
                current_run_length = 1
                previous_letter = i
    # print runs
    # at his point, previous_letter is the suffix letter and current_run_length is the suffix length
    if not (is_isolated[alphabet[0]] or is_isolated[alphabet[1]]):
        return self
    elif is_isolated[alphabet[0]] and is_isolated[alphabet[1]]:
        return W()
    else:
        if is_isolated[alphabet[0]]:
            l_isolated = alphabet[0] #the isolated letter
            l_running = alphabet[1] #the running letter (non-isolated)
        else:
            l_isolated = alphabet[1]
            l_running = alphabet[0]
        w_isolated = W(l_isolated,datatype='letter') #the word associated to the isolated letter
        w_running = W(l_running,datatype='letter') #the word associated to the running letter
        min_run = minimal_run[l_running]
        if (prefix_letter == l_isolated) or (prefix_length <= min_run):
            desubstitued_word = W()
        else:
            desubstitued_word = w_running ** (prefix_length - min_run)
        for i in runs[l_running]:
            desubstitued_word = desubstitued_word + w_isolated + w_running ** (i - min_run)
        if (current_run_length > 0):
            desubstitued_word = desubstitued_word + w_isolated
            if (previous_letter == l_running) and (current_run_length > min_run):
                desubstitued_word = desubstitued_word + w_running ** (current_run_length - min_run)
        return sturmian_desubstitute_as_possible(desubstitued_word)

Some examples

u = Word('10111101101110111',alphabet='01') ; u
v = sturmian_desubstitute_as_possible(u) ; v

word: 01100101

sturmian_desubstitute_as_possible(Word('azaazaaazaaazaazaaaz', alphabet='az'))

word:

def is_sturmian_factor(self):
    r"""
    Tells whether self is a factor of a Sturmian word.

    Equivalently, tells whether self is balanced. The advantage over
    the is_balanced() method is that this one runs in linear time
    whereas is_balanced() runs in quadratic time. The word self must
    be definied on a two-letter alphabet.
    """
    return sturmian_desubstitute_as_possible(self).is_empty()

An example

w = Word('0111011011011101101',alphabet='01')
is_sturmian_factor(w)

True

Fit with existing classes.

print is_sturmian_factor(words.LowerMechanicalWord(random(),alphabet='01')[:100])
print is_sturmian_factor(words.CharacteristicSturmianWord(random())[:100])

True True

Famous words

is_sturmian_factor(words.FibonacciWord()[:100])

True

is_sturmian_factor(words.ThueMorseWord()[:1000])

False

# The Kolakoski word will be soon realeased in sage
#is_sturmian_factor(words.KolakoskiWord()[:1000])

def is_tangent(self):
    r"""
    Tells whether self is a tangent word.

    A binary word is said to be tangent if it can appear in the
    cutting sequences of a smooth curve to arbitrary small scale.
    This class of words strictly contains the class of 1-balanced
    words, and is strictly contained in the class of 2-balanced words.

    This method runs in linear time.
    """
    if (self.parent().size_of_alphabet() != 2):
        raise TypeError, 'Your word must be defined on a binary alphabet '
    [a,b] = self.parent().alphabet()
    mini = 0
    maxi = 0
    height = 0
    for i in sturmian_desubstitute_as_possible(self):
        if i == a:
            height = height + 1
            maxi = max(maxi , height)
        if i == b:
            height = height - 1
            mini = min(mini , height)
    return (maxi - mini <= 2)

An example

w = Word('01110110110111011101',alphabet='01')
is_tangent(w)

True

Some tangent words may not be balanced

print Word('aabb',alphabet='ab').is_balanced()
print is_tangent(Word('aabb',alphabet='ab'))

False True

Some 2-balanced words may not be tangent

print is_tangent(Word('aaabb',alphabet='ab'))
print Word('aaabb',alphabet='ab').is_balanced(2)

False True

Famous examples

is_tangent(words.FibonacciWord()[:100])

True

is_tangent(words.ThueMorseWord()[:1000])

True

# The Kolakoski word will be soon realeased in sage
#is_tangent(words.KolakoskiWord()[:1000])