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#

See also

k-regular sequence, sage.rings.cfinite_sequence, sage.combinat.binary_recurrence_sequences.

AUTHORS:

  • Daniel Krenn (2016, 2021)

ACKNOWLEDGEMENT:

  • Daniel Krenn is supported by the Austrian Science Fund (FWF): P 24644-N26.

Classes and Methods#

class sage.combinat.recognizable_series.PrefixClosedSet(words)[source]#

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: ]

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

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

See iterate_possible_additions() for further examples.

add(w, check=True)[source]#

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

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

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: ]

>>> from sage.all import *
>>> from sage.combinat.recognizable_series import PrefixClosedSet
>>> P = PrefixClosedSet.create_by_alphabet([Integer(0), Integer(1)]); P
[word: ]
iterate_possible_additions()[source]#

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]

>>> from sage.all import *
>>> from sage.combinat.recognizable_series import PrefixClosedSet
>>> P = PrefixClosedSet.create_by_alphabet([Integer(0), Integer(1)]); P
[word: ]
>>> for n, p in enumerate(P.iterate_possible_additions()):
...     print('{}?'.format(p))
...     if n in (Integer(0), Integer(2), Integer(3), Integer(5)):
...         P.add(p)
...         print('...added')
0?
...added
1?
00?
...added
01?
...added
000?
001?
...added
010?
011?
0010?
0011?
>>> 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]

>>> from sage.all import *
>>> 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]

>>> from sage.all import *
>>> list(p + a
...      for p in P.elements
...      for a in P.words.iterate_by_length(Integer(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()[source]#

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]

>>> from sage.all import *
>>> from sage.combinat.recognizable_series import PrefixClosedSet
>>> P = PrefixClosedSet.create_by_alphabet([Integer(0), Integer(1)]); P
[word: ]
>>> for n, p in enumerate(P.iterate_possible_additions()):
...     if n in (Integer(0), Integer(1), Integer(2), Integer(4), Integer(6)):
...         P.add(p)
>>> P
[word: , word: 0, word: 1, word: 00, word: 10, word: 000]
>>> 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)[source]#

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] + ...

>>> from sage.all import *
>>> Rec = RecognizableSeriesSpace(ZZ, [Integer(0), Integer(1)])
>>> S = Rec((Matrix([[Integer(3), Integer(6)], [Integer(0), Integer(1)]]), Matrix([[Integer(0), -Integer(6)], [Integer(1), Integer(5)]])),
...         vector([Integer(0), Integer(1)]), vector([Integer(1), Integer(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

>>> from sage.all import *
>>> W = Rec.indices()
>>> S[W([Integer(0), Integer(0), Integer(1)])]
9

See also

recognizable series, RecognizableSeriesSpace.

coefficient_of_word(w, multiply_left=True, multiply_right=True)[source]#

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

>>> from sage.all import *
>>> Rec = RecognizableSeriesSpace(ZZ, [Integer(0), Integer(1)])
>>> W = Rec.indices()
>>> S = Rec((Matrix([[Integer(1), Integer(0)], [Integer(0), Integer(1)]]), Matrix([[Integer(0), -Integer(1)], [Integer(1), Integer(2)]])),
...          left=vector([Integer(0), Integer(1)]), right=vector([Integer(1), Integer(0)]))
>>> S[W(Integer(7).digits(Integer(2)))]  # indirect doctest
3
dimension()[source]#

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

>>> from sage.all import *
>>> Rec = RecognizableSeriesSpace(ZZ, [Integer(0), Integer(1)])
>>> Rec((Matrix([[Integer(1), Integer(0)], [Integer(0), Integer(1)]]), Matrix([[Integer(1), Integer(0)], [Integer(0), Integer(1)]])),
...     left=vector([Integer(0), Integer(1)]), right=vector([Integer(1), Integer(0)])).dimension()
2
hadamard_product(*args, **kwds)[source]#

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, ...

>>> from sage.all import *
>>> Seq2 = RegularSequenceRing(Integer(2), ZZ)

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

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

>>> C = Seq2((Matrix([[Integer(2), Integer(0)], [Integer(2), Integer(1)]]), Matrix([[Integer(0), Integer(1)], [-Integer(2), Integer(3)]])),
...          vector([Integer(1), Integer(0)]), vector([Integer(0), Integer(1)]))
>>> 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: []},
 ())

>>> from sage.all import *
>>> CE = C.hadamard_product(E)
>>> CE
2-regular sequence 0, 0, 2, 0, 4, 0, 6, 0, 8, 0, ...
>>> 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))

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

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

>>> from sage.all import *
>>> Rec = RecognizableSeriesSpace(ZZ, [Integer(0), Integer(1)])
>>> Rec((Matrix([[Integer(1), Integer(0)], [Integer(0), Integer(1)]]), Matrix([[Integer(1), Integer(0)], [Integer(0), Integer(1)]])),
...     left=vector([Integer(0), Integer(1)]), right=vector([Integer(1), Integer(0)])).is_trivial_zero()
False
>>> Rec((Matrix([[Integer(1), Integer(0)], [Integer(0), Integer(1)]]), Matrix([[Integer(1), Integer(0)], [Integer(0), Integer(1)]])),
...     left=vector([Integer(0), Integer(0)]), right=vector([Integer(1), Integer(0)])).is_trivial_zero()
True
>>> Rec((Matrix([[Integer(1), Integer(0)], [Integer(0), Integer(1)]]), Matrix([[Integer(1), Integer(0)], [Integer(0), Integer(1)]])),
...     left=vector([Integer(0), Integer(1)]), right=vector([Integer(0), Integer(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

>>> from sage.all import *
>>> Rec((Matrix([[Integer(0), Integer(0)], [Integer(0), Integer(0)]]), Matrix([[Integer(0), Integer(0)], [Integer(0), Integer(0)]])),
...     left=vector([Integer(0), Integer(1)]), right=vector([Integer(1), Integer(0)])).is_trivial_zero()
True
>>> Rec((Matrix([[Integer(0), Integer(0)], [Integer(0), Integer(0)]]), Matrix([[Integer(0), Integer(0)], [Integer(0), Integer(0)]])),
...     left=vector([Integer(1), Integer(1)]), right=vector([Integer(1), Integer(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()[source]#

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))

>>> from sage.all import *
>>> Rec = RecognizableSeriesSpace(ZZ, [Integer(0), Integer(1)])
>>> Rec((Matrix([[Integer(3), Integer(6)], [Integer(0), Integer(1)]]), Matrix([[Integer(0), -Integer(6)], [Integer(1), Integer(5)]])),
...     vector([Integer(0), Integer(1)]), vector([Integer(1), Integer(0)])
...    ).transposed().linear_representation()
((1, 0),
 Finite family {0: [3 0]
                   [6 1],
                1: [ 0  1]
                   [-6  5]},
 (0, 1))
minimized()[source]#

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

>>> from sage.all import *
>>> from itertools import islice
>>> Rec = RecognizableSeriesSpace(ZZ, [Integer(0), Integer(1)])

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

>>> S = Rec((Matrix([[Integer(2), Integer(0)], [Integer(1), Integer(1)]]), Matrix([[Integer(2), Integer(0)], [Integer(2), Integer(1)]])),
...         vector([Integer(1), Integer(0)]), vector([Integer(1), Integer(1)]))
>>> S
[] + 2*[0] + 2*[1] + 4*[00] + 4*[01] + 4*[10] + 4*[11]
   + 8*[000] + 8*[001] + 8*[010] + ...
>>> M = S.minimized()
>>> M.mu[Integer(0)], M.mu[Integer(1)], M.left, M.right
([2], [2], (1), (1))
>>> all(c == d and v == w
...     for (c, v), (d, w) in islice(zip(iter(S), iter(M)), Integer(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()[source]#

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)
)

>>> from sage.all import *
>>> Rec = RecognizableSeriesSpace(ZZ, [Integer(0), Integer(1)])
>>> S = Rec((Matrix([[Integer(3), Integer(6)], [Integer(0), Integer(1)]]), Matrix([[Integer(0), -Integer(6)], [Integer(1), Integer(5)]])),
...         vector([Integer(0), Integer(1)]), vector([Integer(1), Integer(0)])).transposed()
>>> S
[1] + 3*[01] + [10] + 5*[11] + 9*[001] + 3*[010]
    + 15*[011] + [100] + 11*[101] + 5*[110] + ...
>>> S.mu[Integer(0)], S.mu[Integer(1)], S.left, S.right
(
[3 0]  [ 0  1]
[6 1], [-6  5], (1, 0), (0, 1)
)
>>> T = S.transposed()
>>> T
[1] + [01] + 3*[10] + 5*[11] + [001] + 3*[010]
    + 5*[011] + 9*[100] + 11*[101] + 15*[110] + ...
>>> T.mu[Integer(0)], T.mu[Integer(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)[source]#

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] + ...

>>> from sage.all import *
>>> Rec = RecognizableSeriesSpace(ZZ, [Integer(0), Integer(1)])
>>> Rec
Space of recognizable series on {0, 1} with coefficients in Integer Ring
>>> Rec((Matrix([[Integer(1), Integer(0)], [Integer(0), Integer(1)]]), Matrix([[Integer(1), Integer(1)], [Integer(0), Integer(1)]])),
...     vector([Integer(1), Integer(0)]), vector([Integer(0), Integer(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

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

See also

recognizable series, RecognizableSeries.

Element[source]#

alias of RecognizableSeries

alphabet()[source]#

Return the alphabet of this recognizable series space.

OUTPUT:

A totally ordered set

EXAMPLES:

sage: RecognizableSeriesSpace(ZZ, [0, 1]).alphabet()
{0, 1}

>>> from sage.all import *
>>> RecognizableSeriesSpace(ZZ, [Integer(0), Integer(1)]).alphabet()
{0, 1}
coefficient_ring()[source]#

Return the coefficients of this recognizable series space.

OUTPUT:

A (semi-)ring

EXAMPLES:

sage: RecognizableSeriesSpace(ZZ, [0, 1]).coefficient_ring()
Integer Ring

>>> from sage.all import *
>>> RecognizableSeriesSpace(ZZ, [Integer(0), Integer(1)]).coefficient_ring()
Integer Ring
indices()[source]#

Return the indices of the recognizable series.

OUTPUT:

The set of finite words over the alphabet

EXAMPLES:

sage: RecognizableSeriesSpace(ZZ, [0, 1]).indices()
Finite words over {0, 1}

>>> from sage.all import *
>>> RecognizableSeriesSpace(ZZ, [Integer(0), Integer(1)]).indices()
Finite words over {0, 1}
property minimize_results#

A boolean indicating whether RecognizableSeries.minimized() is automatically called after performing operations.

one()[source]#

Return the one element of this RecognizableSeriesSpace, i.e. the embedding of the one of the coefficient ring into this RecognizableSeriesSpace.

EXAMPLES:

sage: Rec = RecognizableSeriesSpace(ZZ, [0, 1])
sage: O = Rec.one(); O
[] + ...
sage: O.linear_representation()
((1), Finite family {0: [0], 1: [0]}, (1))

>>> from sage.all import *
>>> Rec = RecognizableSeriesSpace(ZZ, [Integer(0), Integer(1)])
>>> O = Rec.one(); O
[] + ...
>>> O.linear_representation()
((1), Finite family {0: [0], 1: [0]}, (1))
one_hadamard()[source]#

Return the identity with respect to the hadamard_product(), i.e. the coefficient-wise multiplication.

OUTPUT:

A RecognizableSeries

EXAMPLES:

sage: Rec = RecognizableSeriesSpace(ZZ, [0, 1])
sage: Rec.one_hadamard()
[] + [0] + [1] + [00] + [01] + [10]
   + [11] + [000] + [001] + [010] + ...

>>> from sage.all import *
>>> Rec = RecognizableSeriesSpace(ZZ, [Integer(0), Integer(1)])
>>> Rec.one_hadamard()
[] + [0] + [1] + [00] + [01] + [10]
   + [11] + [000] + [001] + [010] + ...
some_elements(**kwds)[source]#

Return some elements of this recognizable series space.

See TestSuite for a typical use case.

INPUT:

  • kwds are passed on to the element constructor

OUTPUT:

An iterator

EXAMPLES:

sage: tuple(RecognizableSeriesSpace(ZZ, [0, 1]).some_elements())
([1] + [01] + [10] + 2*[11] + [001] + [010]
     + 2*[011] + [100] + 2*[101] + 2*[110] + ...,
 [] + [1] + [11] + [111] + [1111] + [11111] + [111111] + ...,
 [] + [0] + [1] + [00] + [10] + [11]
    + [000] - 1*[001] + [100] + [110] + ...,
 2*[] - 1*[1] + 2*[10] - 1*[101]
      + 2*[1010] - 1*[10101] + 2*[101010] + ...,
 [] + [1] + 6*[00] + [11] - 39*[000] + 5*[001] + 6*[100] + [111]
    + 288*[0000] - 33*[0001] + ...,
 -5*[] + ...,
 ...
 210*[] + ...,
 2210*[] - 170*[0] + 170*[1] + ...)

>>> from sage.all import *
>>> tuple(RecognizableSeriesSpace(ZZ, [Integer(0), Integer(1)]).some_elements())
([1] + [01] + [10] + 2*[11] + [001] + [010]
     + 2*[011] + [100] + 2*[101] + 2*[110] + ...,
 [] + [1] + [11] + [111] + [1111] + [11111] + [111111] + ...,
 [] + [0] + [1] + [00] + [10] + [11]
    + [000] - 1*[001] + [100] + [110] + ...,
 2*[] - 1*[1] + 2*[10] - 1*[101]
      + 2*[1010] - 1*[10101] + 2*[101010] + ...,
 [] + [1] + 6*[00] + [11] - 39*[000] + 5*[001] + 6*[100] + [111]
    + 288*[0000] - 33*[0001] + ...,
 -5*[] + ...,
 ...
 210*[] + ...,
 2210*[] - 170*[0] + 170*[1] + ...)
sage.combinat.recognizable_series.minimize_result(operation)[source]#

A decorator for operations that enables control of automatic minimization on the result.

INPUT:

  • operation – a method

OUTPUT:

A method with the following additional argument:

  • 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.

Note

If the result of operation is self, then minimization is not applied unless minimize=True is explicitly set, in particular, independent of the parent’s minimize_results.