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

Warning

As this code is experimental, warnings are thrown when a recognizable series space is created for the first time in a session (see sage.misc.superseded.experimental).

## Various#

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

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 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
[word: , word: 0]
sage: P.add(W([0, 1])); P
[word: , word: 0, word: 01]
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: ]

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):
0?
1?
00?
01?
000?
001?
010?
011?
0010?
0011?
sage: P.elements
[word: , word: 0, word: 00, word: 01, word: 001]

Calling the iterator once more, returns all elements:

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

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

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

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:

EXAMPLES:

sage: Seq2 = kRegularSequenceSpace(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
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:

ALGORITHM:

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

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: 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
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().

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:

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

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

Element#

alias of RecognizableSeries

alphabet()#

Return the alphabet of this recognizable series space.

OUTPUT:

A totally ordered set

EXAMPLES:

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

Return the coefficients of this recognizable series space.

OUTPUT:

A (semi-)ring

EXAMPLES:

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

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}
minimize_results#

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

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

OUTPUT:

EXAMPLES:

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

Return some elements of this recognizable series space.

See TestSuite for a typical use case.

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] + ...)
sage.combinat.recognizable_series.minimize_result(operation)#

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.