Words having an algorithm that enumerates the factor of length n which includes finite words and some family of infinite words. This file gathers methods (e.g. rauzy_graph) that depends only on the existence of such an algorithm.
AUTHORS:
EXAMPLES:
Enumeration of factors:
sage: w = Word([4,5,6])^7
sage: it = w.factor_iterator(4)
sage: it.next()
word: 6456
sage: it.next()
word: 5645
sage: it.next()
word: 4564
sage: it.next()
Traceback (most recent call last):
...
StopIteration
The set of factors:
sage: sorted(w.factor_set(3))
[word: 456, word: 564, word: 645]
sage: sorted(w.factor_set(4))
[word: 4564, word: 5645, word: 6456]
sage: w.factor_set().cardinality()
61
Rauzy graphs:
sage: f = words.FibonacciWord()[:30]
sage: f.rauzy_graph(4)
Looped digraph on 5 vertices
sage: f.reduced_rauzy_graph(4)
Looped multi-digraph on 2 vertices
Left-special and bispecial factors:
sage: f.number_of_left_special_factors(7)
1
sage: f.bispecial_factors()
[word: , word: 0, word: 010, word: 010010, word: 01001010010]
Bases: sage.combinat.words.abstract_word.Word_class
Returns the bispecial factors (of length n).
A factor of a word
is bispecial if it is right special
and left special.
INPUT:
OUTPUT:
A list of words.
Warning
This may not halt for infinite words having an infinite number of such factors. Use the iterator version of this function instead.
EXAMPLES:
sage: w = words.FibonacciWord()[:30]
sage: w.bispecial_factors()
[word: , word: 0, word: 010, word: 010010, word: 01001010010]
sage: w = words.ThueMorseWord()[:30]
sage: for i in range(10): print i, sorted(w.bispecial_factors(i))
0 [word: ]
1 [word: 0, word: 1]
2 [word: 01, word: 10]
3 [word: 010, word: 101]
4 [word: 0110, word: 1001]
5 []
6 [word: 011001, word: 100110]
7 []
8 [word: 10010110]
9 []
Returns an iterator over the bispecial factors (of length n).
A factor of a word
is bispecial if it is right special
and left special.
INPUT:
EXAMPLES:
sage: w = words.ThueMorseWord()[:30]
sage: for i in range(10):
... for u in sorted(w.bispecial_factors_iterator(i)):
... print i,u
0
1 0
1 1
2 01
2 10
3 010
3 101
4 0110
4 1001
6 011001
6 100110
8 10010110
sage: key = lambda u : (len(u), u)
sage: for u in sorted(w.bispecial_factors_iterator(), key=key): u
word:
word: 0
word: 1
word: 01
word: 10
word: 010
word: 101
word: 0110
word: 1001
word: 011001
word: 100110
word: 10010110
Returns an iterator over the factor of lenght .
INPUT:
OUTPUT:
If n is an integer, returns an iterator over all distinct factors of length n. If n is None, returns an iterator generating all distinct factors.
EXAMPLES:
sage: w = Word(range(10))
sage: sorted(w.factor_iterator(7))
[word: 0123456, word: 1234567, word: 2345678, word: 3456789]
Returns the set of factors (of length n) of self.
INPUT:
OUTPUT:
If n is an integer, returns the set of all distinct factors of length n. If n is None, returns the set of all distinct factors.
EXAMPLES:
sage: w = Word('121')
sage: s = w.factor_set()
sage: sorted(s)
[word: , word: 1, word: 12, word: 121, word: 2, word: 21]
sage: w = Word('1213121')
sage: for i in range(w.length()): sorted(w.factor_set(i))
[word: ]
[word: 1, word: 2, word: 3]
[word: 12, word: 13, word: 21, word: 31]
[word: 121, word: 131, word: 213, word: 312]
[word: 1213, word: 1312, word: 2131, word: 3121]
[word: 12131, word: 13121, word: 21312]
[word: 121312, word: 213121]
sage: w = Word([1,2,1,2,3])
sage: s = w.factor_set()
sage: sorted(s)
[word: , word: 1, word: 12, word: 121, word: 1212, word: 12123, word: 123, word: 2, word: 21, word: 212, word: 2123, word: 23, word: 3]
TESTS:
sage: w = Word("xx")
sage: s = w.factor_set()
sage: sorted(s)
[word: , word: x, word: xx]
sage: Set(Word().factor_set())
{word: }
Returns the left special factors (of length n).
A factor of a word
is left special if there are
two distinct letters
and
such that
and
are factors of
.
INPUT:
OUTPUT:
A list of words.
Warning
This may not halt for infinite words having an infinite number of such factors. Use the iterator version of this function instead.
EXAMPLES:
sage: alpha, beta, x = 0.54, 0.294, 0.1415
sage: w = words.CodingOfRotationWord(alpha, beta, x)[:40]
sage: for i in range(5): print i, sorted(w.right_special_factors(i))
0 [word: ]
1 [word: 0]
2 [word: 00, word: 10]
3 [word: 000, word: 010]
4 [word: 0000, word: 1010]
Returns an iterator over the left special factors (of length n).
A factor of a word
is left special if there are
two distinct letters
and
such that
and
are factors of
.
INPUT:
EXAMPLES:
sage: alpha, beta, x = 0.54, 0.294, 0.1415
sage: w = words.CodingOfRotationWord(alpha, beta, x)[:40]
sage: sorted(w.left_special_factors_iterator(3))
[word: 000, word: 010]
sage: sorted(w.left_special_factors_iterator(4))
[word: 0000, word: 0101]
sage: sorted(w.left_special_factors_iterator(5))
[word: 00000, word: 01010]
Return the number of distinct factors of self.
INPUT:
OUTPUT:
integer
EXAMPLES:
sage: w = Word(range(10))
sage: w.number_of_factors(6)
5
Returns the number of left special factors of length n.
A factor of a word
is left special if there are
two distinct letters
and
such that
and
are factors of
.
INPUT:
OUTPUT:
Non negative integer
EXAMPLES:
sage: w = words.FibonacciWord()[:100]
sage: [w.number_of_left_special_factors(i) for i in range(10)]
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
sage: w = words.ThueMorseWord()[:100]
sage: [w.number_of_left_special_factors(i) for i in range(10)]
[1, 2, 2, 4, 2, 4, 4, 2, 2, 4]
Returns the number of right special factors of length n.
A factor of a word
is right special if there are
two distinct letters
and
such that
and
are factors of
.
INPUT:
OUTPUT:
Non negative integer
EXAMPLES:
sage: w = words.FibonacciWord()[:100]
sage: [w.number_of_right_special_factors(i) for i in range(10)]
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
sage: w = words.ThueMorseWord()[:100]
sage: [w.number_of_right_special_factors(i) for i in range(10)]
[1, 2, 2, 4, 2, 4, 4, 2, 2, 4]
Returns the Rauzy graph of the factors of length n of self.
The vertices are the factors of length and there is an edge from
to
if
is a factor of length
for some letters
and
.
INPUT:
EXAMPLES:
sage: w = Word(range(10)); w
word: 0123456789
sage: g = w.rauzy_graph(3); g
Looped digraph on 8 vertices
sage: WordOptions(identifier='')
sage: g.vertices()
[012, 123, 234, 345, 456, 567, 678, 789]
sage: g.edges()
[(012, 123, 3),
(123, 234, 4),
(234, 345, 5),
(345, 456, 6),
(456, 567, 7),
(567, 678, 8),
(678, 789, 9)]
sage: WordOptions(identifier='word: ')
sage: f = words.FibonacciWord()[:100]
sage: f.rauzy_graph(8)
Looped digraph on 9 vertices
sage: w = Word('1111111')
sage: g = w.rauzy_graph(3)
sage: g.edges()
[(word: 111, word: 111, word: 1)]
sage: w = Word('111')
sage: for i in range(5) : w.rauzy_graph(i)
Looped multi-digraph on 1 vertex
Looped digraph on 1 vertex
Looped digraph on 1 vertex
Looped digraph on 1 vertex
Looped digraph on 0 vertices
Multi-edges are allowed for the empty word:
sage: W = Words('abcde')
sage: w = W('abc')
sage: w.rauzy_graph(0)
Looped multi-digraph on 1 vertex
sage: _.edges()
[(word: , word: , word: a),
(word: , word: , word: b),
(word: , word: , word: c)]
Returns the reduced Rauzy graph of order of self.
INPUT:
OUTPUT:
Looped multi-digraph
DEFINITION:
For infinite periodic words (resp. for finite words of type ), the reduced Rauzy graph of order
(resp. for
smaller or equal to
) is the directed graph whose
unique vertex is the prefix
of length
of self and which has
an only edge which is a loop on
labelled by
where
is the unique return word to
.
In other cases, it is the directed graph defined as followed. Let
be the Rauzy graph of order
of self. The vertices are the
vertices of
that are either special or not prolongable to the
right or to the left. For each couple (
,
) of such vertices
and each directed path in
from
to
that contains no
other vertices that are special, there is an edge from
to
in the reduced Rauzy graph of order
whose label is the label of
the path in
.
Note
In the case of infinite recurrent non periodic words, this definition correspond to the following one that can be found in [1] and [2] where a simple path is a path that begins with a special factor, ends with a special factor and contains no other vertices that are special:
The reduced Rauzy graph of factors of length is obtained
from
by replacing each simple path
with an edge
whose label is the
concatenation of the labels of the edges of
.
EXAMPLES:
sage: w = Word(range(10)); w
word: 0123456789
sage: g = w.reduced_rauzy_graph(3); g
Looped multi-digraph on 2 vertices
sage: g.vertices()
[word: 012, word: 789]
sage: g.edges()
[(word: 012, word: 789, word: 3456789)]
For the Fibonacci word:
sage: f = words.FibonacciWord()[:100]
sage: g = f.reduced_rauzy_graph(8);g
Looped multi-digraph on 2 vertices
sage: g.vertices()
[word: 01001010, word: 01010010]
sage: g.edges()
[(word: 01001010, word: 01010010, word: 010), (word: 01010010, word: 01001010, word: 01010), (word: 01010010, word: 01001010, word: 10)]
For periodic words:
sage: from itertools import cycle
sage: w = Word(cycle('abcd'))[:100]
sage: g = w.reduced_rauzy_graph(3)
sage: g.edges()
[(word: abc, word: abc, word: dabc)]
sage: w = Word('111')
sage: for i in range(5) : w.reduced_rauzy_graph(i)
Looped digraph on 1 vertex
Looped digraph on 1 vertex
Looped digraph on 1 vertex
Looped multi-digraph on 1 vertex
Looped multi-digraph on 0 vertices
For ultimately periodic words:
sage: sigma = WordMorphism('a->abcd,b->cd,c->cd,d->cd')
sage: w = sigma.fixed_point('a')[:100]; w
word: abcdcdcdcdcdcdcdcdcdcdcdcdcdcdcdcdcdcdcd...
sage: g = w.reduced_rauzy_graph(5)
sage: g.vertices()
[word: abcdc, word: cdcdc]
sage: g.edges()
[(word: abcdc, word: cdcdc, word: dc), (word: cdcdc, word: cdcdc, word: dc)]
AUTHOR:
Julien Leroy (March 2010): initial version
REFERENCES:
Returns the right special factors (of length n).
A factor of a word
is right special if there are
two distinct letters
and
such that
and
are factors of
.
INPUT:
OUTPUT:
A list of words.
Warning
This may not halt for infinite words having an infinite number of such factors. Use the iterator version of this function instead.
EXAMPLES:
sage: w = words.ThueMorseWord()[:30]
sage: for i in range(5): print i, sorted(w.right_special_factors(i))
0 [word: ]
1 [word: 0, word: 1]
2 [word: 01, word: 10]
3 [word: 001, word: 010, word: 101, word: 110]
4 [word: 0110, word: 1001]
Returns an iterator over the right special factors (of length n).
A factor of a word
is right special if there are
two distinct letters
and
such that
and
are factors of
.
INPUT:
EXAMPLES:
sage: alpha, beta, x = 0.61, 0.54, 0.3
sage: w = words.CodingOfRotationWord(alpha, beta, x)[:40]
sage: sorted(w.right_special_factors_iterator(3))
[word: 010, word: 101]
sage: sorted(w.right_special_factors_iterator(4))
[word: 0101, word: 1010]
sage: sorted(w.right_special_factors_iterator(5))
[word: 00101, word: 11010]
Return the topological entropy for the factors of length n.
The topological entropy of a sequence is defined as the
exponential growth rate of the complexity of
as the length
increases:
where
denotes the cardinality of the alphabet and
is
the complexity function, i.e. the number of factors of length
in the sequence
[1].
INPUT:
OUTPUT:
real number (a symbolic expression)
EXAMPLES:
sage: W = Words([0, 1])
sage: w = W([0, 1, 0, 0, 0, 1, 1, 0, 0, 1, 0, 1])
sage: t = w.topological_entropy(3); t
1/3*log(7)/log(2)
sage: n(t)
0.935784974019201
sage: w = words.ThueMorseWord()[:100]
sage: topo = w.topological_entropy
sage: for i in range(0, 41, 5): print i, n(topo(i), digits=5)
0 1.0000
5 0.71699
10 0.48074
15 0.36396
20 0.28774
25 0.23628
30 0.20075
35 0.17270
40 0.14827
If no alphabet is specified, an error is raised:
sage: w = Word(range(20))
sage: w.topological_entropy(3)
Traceback (most recent call last):
...
TypeError: The word must be defined over a finite alphabet
The following is ok:
sage: W = Words(range(20))
sage: w = W(range(20))
sage: w.topological_entropy(3)
1/3*log(18)/log(20)
REFERENCES:
[1] N. Pytheas Fogg, Substitutions in Dynamics, Arithmetics, and Combinatorics, Lecture Notes in Mathematics 1794, Springer Verlag. V. Berthe, S. Ferenczi, C. Mauduit and A. Siegel, Eds. (2002).