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
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#
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)#
Bases:
object
A prefix-closed set.
Creation of this prefix-closed set is interactive iteratively.
INPUT:
words
– a class of words (instance ofWords
)
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 wordcheck
– boolean (default:True
). If set, then it is verified whether all proper prefixes ofw
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 thisalphabet
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 tosage: 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:
sage.structure.element.ModuleElement
A recognizable series.
parent
– an instance ofRecognizableSeriesSpace
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 alsomu
.left
– a vector. When evaluating a coefficient, this vector is multiplied from the left to the matrix obtained frommu
applying on a word. See alsoleft
.right
– a vector. When evaluating a coefficient, this vector is multiplied from the right to the matrix obtained frommu
applying on a word. See alsoright
.
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
See also
- 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’salphabet()
multiply_left
– (default:True
) a boolean. IfFalse
, then multiplication byleft
is skipped.multiply_right
– (default:True
) a boolean. IfFalse
, then multiplication byright
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
– aRecognizableSeries
with the same parent as this recognizable seriesminimize
– (default:None
) a boolean orNone
. IfTrue
, thenminimized()
is called after the operation, ifFalse
, then not. If this argument isNone
, then the default specified by the parent’sminimize_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 vectorsleft
andright
, and the family of matricesmu
.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].
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
- 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’salphabet()
.
- 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 vectorsleft
andright
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:
sage.structure.unique_representation.UniqueRepresentation
,sage.structure.parent.Parent
The space of recognizable series on the given alphabet and with the given coefficients.
INPUT:
coefficient_ring
– a (semi-)ringalphabet
– a tuple, list orTotallyOrderedFiniteSet
. If specified, then theindices
are the finite words over thisalphabet
.alphabet
andindices
cannot be specified at the same time.indices
– a SageMath-parent of finite words over an alphabet.alphabet
andindices
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
See also
- 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.
- one_hadamard()#
Return the identity with respect to the
hadamard_product()
, i.e. the coefficient-wise multiplication.OUTPUT:
EXAMPLES:
sage: Rec = RecognizableSeriesSpace(ZZ, [0, 1]) sage: Rec.one_hadamard() [] + [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 orNone
. IfTrue
, thenminimized()
is called after the operation, ifFalse
, then not. If this argument isNone
, then the default specified by the parent’sminimize_results
is used.