Recognizable Series#

Let \(A\) be an alphabet and \(K\) a semiring. Then a formal series \(S\) with coefficients in \(K\) and indices in the words \(A^*\) is called recognizable if it has a linear representation, i.e., there exists

a nonnegative integer \(n\)

and there exist

two vectors \(\mathit{left}\) and \(\mathit{right}\) of dimension \(n\) and
a morphism of monoids \(\mu\) from \(A^*\) to \(n\times n\) matrices over \(K\)

such that the coefficient corresponding to a word \(w\in A^*\) equals

\[\mathit{left} \, \mu(w) \, \mathit{right}.\]

Note

Whenever a minimization (minimized()) of a series needs to be computed, it is required that \(K\) is a field. In particular, minimization is called before checking if a series is nonzero.

Various#

Classes and Methods#

class sage.combinat.recognizable_series.PrefixClosedSet(words)#

Bases: object

A prefix-closed set.

Creation of this prefix-closed set is interactive iteratively.

INPUT:

words – a class of words (instance of Words)

EXAMPLES:

sage: from sage.combinat.recognizable_series import PrefixClosedSet
sage: P = PrefixClosedSet(Words([0, 1], infinite=False)); P
[word: ]

sage: P = PrefixClosedSet.create_by_alphabet([0, 1]); P
[word: ]

See iterate_possible_additions() for further examples.

add(w, check=True)#

Add a word to this prefix-closed set.

INPUT:

w – a word
check – boolean (default: True). If set, then it is verified whether all proper prefixes of w are already in this prefix-closed set.

OUTPUT:

Nothing, but a RuntimeError is raised if the check fails.

EXAMPLES:

sage: from sage.combinat.recognizable_series import PrefixClosedSet
sage: P = PrefixClosedSet.create_by_alphabet([0, 1])
sage: W = P.words
sage: P.add(W([0])); P
[word: , word: 0]
sage: P.add(W([0, 1])); P
[word: , word: 0, word: 01]
sage: P.add(W([1, 1]))
Traceback (most recent call last):
...
ValueError: cannot add as not all prefixes of 11 are included yet

classmethod create_by_alphabet(alphabet)#

A prefix-closed set

This is a convenience method for the creation of prefix-closed sets by specifying an alphabet.

INPUT:

alphabet – finite words over this alphabet will used

EXAMPLES:

sage: from sage.combinat.recognizable_series import PrefixClosedSet
sage: P = PrefixClosedSet.create_by_alphabet([0, 1]); P
[word: ]

iterate_possible_additions()#

Return an iterator over all elements including possible new elements.

OUTPUT:

An iterator

EXAMPLES:

sage: from sage.combinat.recognizable_series import PrefixClosedSet
sage: P = PrefixClosedSet.create_by_alphabet([0, 1]); P
[word: ]
sage: for n, p in enumerate(P.iterate_possible_additions()):
....:     print('{}?'.format(p))
....:     if n in (0, 2, 3, 5):
....:         P.add(p)
....:         print('...added')
0?
...added
1?
00?
...added
01?
...added
000?
001?
...added
010?
011?
0010?
0011?
sage: P.elements
[word: , word: 0, word: 00, word: 01, word: 001]

Calling the iterator once more, returns all elements:

sage: list(P.iterate_possible_additions())
[word: 0,
 word: 1,
 word: 00,
 word: 01,
 word: 000,
 word: 001,
 word: 010,
 word: 011,
 word: 0010,
 word: 0011]

The method iterate_possible_additions() is roughly equivalent to

sage: list(p + a
....:      for p in P.elements
....:      for a in P.words.iterate_by_length(1))
[word: 0,
 word: 1,
 word: 00,
 word: 01,
 word: 000,
 word: 001,
 word: 010,
 word: 011,
 word: 0010,
 word: 0011]

However, the above does not allow to add elements during iteration, whereas iterate_possible_additions() does.

prefix_set()#

Return the set of minimal (with respect to prefix ordering) elements of the complement of this prefix closed set.

See also Proposition 2.3.1 of [BR2010a].

OUTPUT:

A list

EXAMPLES:

sage: from sage.combinat.recognizable_series import PrefixClosedSet
sage: P = PrefixClosedSet.create_by_alphabet([0, 1]); P
[word: ]
sage: for n, p in enumerate(P.iterate_possible_additions()):
....:     if n in (0, 1, 2, 4, 6):
....:         P.add(p)
sage: P
[word: , word: 0, word: 1, word: 00, word: 10, word: 000]
sage: P.prefix_set()
[word: 01, word: 11, word: 001, word: 100,
 word: 101, word: 0000, word: 0001]

class sage.combinat.recognizable_series.RecognizableSeries(parent, mu, left, right)#

Bases: ModuleElement

A recognizable series.

parent – an instance of RecognizableSeriesSpace
mu – a family of square matrices, all of which have the same dimension. The indices of this family are the elements of the alphabet. mu may be a list or tuple of the same cardinality as the alphabet as well. See also mu.
left – a vector. When evaluating a coefficient, this vector is multiplied from the left to the matrix obtained from mu applying on a word. See also left.
right – a vector. When evaluating a coefficient, this vector is multiplied from the right to the matrix obtained from mu applying on a word. See also right.

When created via the parent RecognizableSeriesSpace, then the following option is available.

EXAMPLES:

sage: Rec = RecognizableSeriesSpace(ZZ, [0, 1])
sage: S = Rec((Matrix([[3, 6], [0, 1]]), Matrix([[0, -6], [1, 5]])),
....:         vector([0, 1]), vector([1, 0])).transposed(); S
[1] + 3*[01] + [10] + 5*[11] + 9*[001] + 3*[010] + ...

We can access coefficients by

sage: W = Rec.indices()
sage: S[W([0, 0, 1])]
9

coefficient_of_word(w, multiply_left=True, multiply_right=True)#

Return the coefficient to word \(w\) of this series.

INPUT:

w – a word over the parent’s alphabet()
multiply_left – (default: True) a boolean. If False, then multiplication by left is skipped.
multiply_right – (default: True) a boolean. If False, then multiplication by right is skipped.

OUTPUT:

An element in the parent’s coefficient_ring()

EXAMPLES:

sage: Rec = RecognizableSeriesSpace(ZZ, [0, 1])
sage: W = Rec.indices()
sage: S = Rec((Matrix([[1, 0], [0, 1]]), Matrix([[0, -1], [1, 2]])),
....:          left=vector([0, 1]), right=vector([1, 0]))
sage: S[W(7.digits(2))]  # indirect doctest
3

dimension()#

Return the dimension of this recognizable series.

EXAMPLES:

sage: Rec = RecognizableSeriesSpace(ZZ, [0, 1])
sage: Rec((Matrix([[1, 0], [0, 1]]), Matrix([[1, 0], [0, 1]])),
....:     left=vector([0, 1]), right=vector([1, 0])).dimension()
2

hadamard_product(*args, **kwds)#

Return the Hadamard product of this recognizable series and the other recognizable series, i.e., multiply the two series coefficient-wise.

INPUT:

other – a RecognizableSeries with the same parent as this recognizable series
minimize – (default: None) a boolean or None. If True, then minimized() is called after the operation, if False, then not. If this argument is None, then the default specified by the parent’s minimize_results is used.

OUTPUT:

A RecognizableSeries

EXAMPLES:

sage: Seq2 = RegularSequenceRing(2, ZZ)

sage: E = Seq2((Matrix([[0, 1], [0, 1]]), Matrix([[0, 0], [0, 1]])),
....:          vector([1, 0]), vector([1, 1]))
sage: E
2-regular sequence 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, ...

sage: O = Seq2((Matrix([[0, 0], [0, 1]]), Matrix([[0, 1], [0, 1]])),
....:          vector([1, 0]), vector([0, 1]))
sage: O
2-regular sequence 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, ...

sage: C = Seq2((Matrix([[2, 0], [2, 1]]), Matrix([[0, 1], [-2, 3]])),
....:          vector([1, 0]), vector([0, 1]))
sage: C
2-regular sequence 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, ...

sage: CE = C.hadamard_product(E)
sage: CE
2-regular sequence 0, 0, 2, 0, 4, 0, 6, 0, 8, 0, ...
sage: CE.linear_representation()
((1, 0, 0),
 Finite family {0: [0 1 0]
                   [0 2 0]
                   [0 2 1],
                1: [ 0  0  0]
                   [ 0  0  1]
                   [ 0 -2  3]},
 (0, 0, 2))

sage: Z = E.hadamard_product(O)
sage: Z
2-regular sequence 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, ...
sage: Z.linear_representation()
((),
 Finite family {0: [],
                1: []},
 ())

is_trivial_zero()#

Return whether this recognizable series is trivially equal to zero (without any minimization).

EXAMPLES:

sage: Rec = RecognizableSeriesSpace(ZZ, [0, 1])
sage: Rec((Matrix([[1, 0], [0, 1]]), Matrix([[1, 0], [0, 1]])),
....:     left=vector([0, 1]), right=vector([1, 0])).is_trivial_zero()
False
sage: Rec((Matrix([[1, 0], [0, 1]]), Matrix([[1, 0], [0, 1]])),
....:     left=vector([0, 0]), right=vector([1, 0])).is_trivial_zero()
True
sage: Rec((Matrix([[1, 0], [0, 1]]), Matrix([[1, 0], [0, 1]])),
....:     left=vector([0, 1]), right=vector([0, 0])).is_trivial_zero()
True

The following two differ in the coefficient of the empty word:

sage: Rec((Matrix([[0, 0], [0, 0]]), Matrix([[0, 0], [0, 0]])),
....:     left=vector([0, 1]), right=vector([1, 0])).is_trivial_zero()
True
sage: Rec((Matrix([[0, 0], [0, 0]]), Matrix([[0, 0], [0, 0]])),
....:     left=vector([1, 1]), right=vector([1, 1])).is_trivial_zero()
False

property left#: When evaluating a coefficient, this vector is multiplied from the left to the matrix obtained from mu applied on a word.

linear_representation()#

Return the linear representation of this series.

OUTPUT:

A triple (left, mu, right) containing the vectors left and right, and the family of matrices mu.

EXAMPLES:

sage: Rec = RecognizableSeriesSpace(ZZ, [0, 1])
sage: Rec((Matrix([[3, 6], [0, 1]]), Matrix([[0, -6], [1, 5]])),
....:     vector([0, 1]), vector([1, 0])
....:    ).transposed().linear_representation()
((1, 0),
 Finite family {0: [3 0]
                   [6 1],
                1: [ 0  1]
                   [-6  5]},
 (0, 1))

minimized()#

Return a recognizable series equivalent to this series, but with a minimized linear representation.

The coefficients of the involved matrices need be in a field. If this is not the case, then the coefficients are automatically coerced to their fraction field.

OUTPUT:

A RecognizableSeries

ALGORITHM:

This method implements the minimization algorithm presented in Chapter 2 of [BR2010a].

Note

Due to the algorithm, the left vector of the result is always \((1, 0, \ldots, 0)\), i.e., the first vector of the standard basis.

EXAMPLES:

sage: from itertools import islice
sage: Rec = RecognizableSeriesSpace(ZZ, [0, 1])

sage: S = Rec((Matrix([[3, 6], [0, 1]]), Matrix([[0, -6], [1, 5]])),
....:         vector([0, 1]), vector([1, 0])).transposed()
sage: S
[1] + 3*[01] + [10] + 5*[11] + 9*[001] + 3*[010]
    + 15*[011] + [100] + 11*[101] + 5*[110] + ...
sage: M = S.minimized()
sage: M.mu[0], M.mu[1], M.left, M.right
(
[3 0]  [ 0  1]
[6 1], [-6  5], (1, 0), (0, 1)
)
sage: M.left == vector([1, 0])
True
sage: all(c == d and v == w
....:     for (c, v), (d, w) in islice(zip(iter(S), iter(M)), 20))
True

sage: S = Rec((Matrix([[2, 0], [1, 1]]), Matrix([[2, 0], [2, 1]])),
....:         vector([1, 0]), vector([1, 1]))
sage: S
[] + 2*[0] + 2*[1] + 4*[00] + 4*[01] + 4*[10] + 4*[11]
   + 8*[000] + 8*[001] + 8*[010] + ...
sage: M = S.minimized()
sage: M.mu[0], M.mu[1], M.left, M.right
([2], [2], (1), (1))
sage: all(c == d and v == w
....:     for (c, v), (d, w) in islice(zip(iter(S), iter(M)), 20))
True

property mu#: When evaluating a coefficient, this is applied on each letter of a word; the result is a matrix. This extends mu to words over the parent’s alphabet().

property right#: When evaluating a coefficient, this vector is multiplied from the right to the matrix obtained from mu applied on a word.

transposed()#

Return the transposed series.

OUTPUT:

A RecognizableSeries

Each of the matrices in mu is transposed. Additionally the vectors left and right are switched.

EXAMPLES:

sage: Rec = RecognizableSeriesSpace(ZZ, [0, 1])
sage: S = Rec((Matrix([[3, 6], [0, 1]]), Matrix([[0, -6], [1, 5]])),
....:         vector([0, 1]), vector([1, 0])).transposed()
sage: S
[1] + 3*[01] + [10] + 5*[11] + 9*[001] + 3*[010]
    + 15*[011] + [100] + 11*[101] + 5*[110] + ...
sage: S.mu[0], S.mu[1], S.left, S.right
(
[3 0]  [ 0  1]
[6 1], [-6  5], (1, 0), (0, 1)
)
sage: T = S.transposed()
sage: T
[1] + [01] + 3*[10] + 5*[11] + [001] + 3*[010]
    + 5*[011] + 9*[100] + 11*[101] + 15*[110] + ...
sage: T.mu[0], T.mu[1], T.left, T.right
(
[3 6]  [ 0 -6]
[0 1], [ 1  5], (0, 1), (1, 0)
)

class sage.combinat.recognizable_series.RecognizableSeriesSpace(coefficient_ring, indices, category, minimize_results)#

Bases: UniqueRepresentation, Parent

The space of recognizable series on the given alphabet and with the given coefficients.

INPUT:

coefficient_ring – a (semi-)ring
alphabet – a tuple, list or TotallyOrderedFiniteSet. If specified, then the indices are the finite words over this alphabet. alphabet and indices cannot be specified at the same time.
indices – a SageMath-parent of finite words over an alphabet. alphabet and indices cannot be specified at the same time.
category – (default: None) the category of this space

EXAMPLES:

We create a recognizable series that counts the number of ones in each word:

sage: Rec = RecognizableSeriesSpace(ZZ, [0, 1])
sage: Rec
Space of recognizable series on {0, 1} with coefficients in Integer Ring
sage: Rec((Matrix([[1, 0], [0, 1]]), Matrix([[1, 1], [0, 1]])),
....:     vector([1, 0]), vector([0, 1]))
[1] + [01] + [10] + 2*[11] + [001] + [010] + 2*[011] + [100] + 2*[101] + 2*[110] + ...

All of the following examples create the same space:

sage: Rec1 = RecognizableSeriesSpace(ZZ, [0, 1])
sage: Rec1
Space of recognizable series on {0, 1} with coefficients in Integer Ring
sage: Rec2 = RecognizableSeriesSpace(coefficient_ring=ZZ, alphabet=[0, 1])
sage: Rec2
Space of recognizable series on {0, 1} with coefficients in Integer Ring
sage: Rec3 = RecognizableSeriesSpace(ZZ, indices=Words([0, 1], infinite=False))
sage: Rec3
Space of recognizable series on {0, 1} with coefficients in Integer Ring