Opened 4 years ago
Last modified 18 months ago
#21295 needs_work enhancement
recognizable series (a base for kregular sequences)
Reported by:  dkrenn  Owned by:  

Priority:  major  Milestone:  sage8.0 
Component:  combinatorics  Keywords:  thursdaysbdx 
Cc:  Merged in:  
Authors:  Daniel Krenn  Reviewers:  Sébastien Labbé 
Report Upstream:  N/A  Work issues:  
Branch:  u/dkrenn/sequences/recognizable (Commits)  Commit:  5dbdcbb79a50371eda4a6fd65a7511e91e915469 
Dependencies:  Stopgaps: 
Description
Implement recognizable series, which are formal series, whose coefficients (each belongs to a word over an alphabet) satisfy a certain linear representation. (This linear representation is based on a monoid morphism into matrices.)
See also meta ticket #21202.
Change History (24)
comment:1 Changed 4 years ago by
 Branch set to u/dkrenn/sequences/recognizable
comment:2 Changed 4 years ago by
 Commit set to fd4f5414050ce650eeedca54580535aefeb008a1
comment:3 Changed 4 years ago by
 Status changed from new to needs_review
comment:4 Changed 4 years ago by
 Commit changed from fd4f5414050ce650eeedca54580535aefeb008a1 to 9e12383a4d19664c152c26248768c69dc1c893e8
comment:5 Changed 4 years ago by
 Commit changed from 9e12383a4d19664c152c26248768c69dc1c893e8 to 41874bafbd0fdd2faafbd499a0933f8ca502843e
Branch pushed to git repo; I updated commit sha1. New commits:
41874ba  fix a typo

comment:6 Changed 4 years ago by
 Status changed from needs_review to needs_work
comment:7 Changed 4 years ago by
 Commit changed from 41874bafbd0fdd2faafbd499a0933f8ca502843e to c7243a68f3be1898b6e478b429954587e2b493db
Branch pushed to git repo; I updated commit sha1. New commits:
c7243a6  Merge tag '7.4.beta1' into t/21295/sequences/recognizable

comment:8 Changed 4 years ago by
 Status changed from needs_work to needs_review
comment:9 Changed 4 years ago by
 Commit changed from c7243a68f3be1898b6e478b429954587e2b493db to 352751e2d5ff38ca5d5d819c01385035d11f2269
Branch pushed to git repo; I updated commit sha1. New commits:
352751e  Merge tag '7.4.beta2' into t/21295/sequences/recognizable

comment:10 followup: ↓ 16 Changed 4 years ago by
 Status changed from needs_review to needs_work
patchbot python3 plugin failure
comment:11 followup: ↓ 18 Changed 4 years ago by
 Dependencies set to #21200
comment:12 Changed 4 years ago by
 Branch changed from u/dkrenn/sequences/recognizable to u/cheuberg/sequences/recognizable
comment:13 Changed 4 years ago by
 Commit changed from 352751e2d5ff38ca5d5d819c01385035d11f2269 to a6b55613133efc2d002a8ae4b4f194621fd3717d
Branch pushed to git repo; I updated commit sha1. New commits:
a6b5561  Trac #21295: fix ReST error

comment:14 Changed 4 years ago by
 Commit changed from a6b55613133efc2d002a8ae4b4f194621fd3717d to c9c3408af4edead15b16886353258731d35092e0
Branch pushed to git repo; I updated commit sha1. New commits:
c9c3408  Trac #21295: fix typos

comment:15 Changed 4 years ago by
 Branch changed from u/cheuberg/sequences/recognizable to u/dkrenn/sequences/recognizable
comment:16 in reply to: ↑ 10 Changed 4 years ago by
 Commit changed from c9c3408af4edead15b16886353258731d35092e0 to 4a43407d37361ab2e24b965e13358ab408ef894a
comment:17 Changed 4 years ago by
 Commit changed from 4a43407d37361ab2e24b965e13358ab408ef894a to 4970cf5984fb88c379748c29fd3824981389468e
Branch pushed to git repo; I updated commit sha1. New commits:
4970cf5  Python3: absolute import

comment:18 in reply to: ↑ 11 Changed 4 years ago by
comment:19 Changed 4 years ago by
 Status changed from needs_work to needs_review
comment:20 Changed 3 years ago by
 Reviewers set to Sébastien Labbé
 Status changed from needs_review to needs_work
Some remarks.
 Document keyword
infinite
in the list of inputs ofRecognizableSeriesSpace??
.
 Add an example of use of keyword
category
in doc ofRecognizableSeriesSpace??
.
 When I do
sage: S = RecognizableSeriesSpace(ZZ, (0,1)) sage: S?
I would like to see examples of how to create an object in this space, but there is no.
 There is an error on the repr of s recognizable series:
sage: Rec = RecognizableSeriesSpace(ZZ, (0,1)) sage: S = Rec((M0,M1), (0,1), (1,1)) sage: S <repr(<sage.combinat.recognizable_series.RecognizableSeriesSpace_with_category.element_class at 0x7fd8f6d68640>) failed: TypeError: unsupported operand parent(s) for *: '<type 'tuple'>' and 'Full MatrixSpace of 2 by 2 dense matrices over Integer Ring'>
 "The indices of this family are the alphabet." > is the alphabet or > are elements of the alphabet
 There is a ReST indentation problem in the paragraph of "transpose" of
RecognizableSeries?
6.
When created via the parent :class:`RecognizableSeriesSpace`, then the following option is available.
Then why should it be mentionned there? Is this option really necessary? I prefer
sage: S = Rec(inputs).transposed()
to
sage: S = Rec(inputs, transpose=False)
 How to access to the coefficient of some word? This should be documented soon, like in the top level module or in the constructors of series.
sage: S = Rec((M0,M1), vector((0,1)), vector((1,1))) sage: S [] + [0] + 3*[1] + [00] + 3*[01] + 3*[10] + 5*[11] + [000] + 3*[001] + 3*[010] + ... sage: S([0,0,1]) Traceback (most recent call last) ... TypeError: 'RecognizableSeriesSpace_with_category.element_class' object is not callable
 The documentation of the class
RecognizableSeriesSpace
does not contains any details relative to what_element_constructor_
is doing.
def _element_constructor_(self, data, left=None, right=None, transpose=False): r""" Return a recognizable series. See :class:`RecognizableSeriesSpace` for details.
I would rather document left
, right
and transpose
here.
Again, I do not know whether transpose
is really necessary here. Unless there
is an argument, I would just delete it.
 I would remove this space, no?
class RecognizableSeries(Element): def __init__(self, parent, mu, left, right):
 In the book of Berstel and Reutenauer, the notation of the coefficient of a word w in a series S is (S,w). In Python, this gives a tuple which is not what we want. I agree that using
__getitem__
is the way to go.
sage: M0 = matrix(2,[1,2,3,4]) sage: M1 = matrix(2,[2,1,3,7]) sage: Rec = RecognizableSeriesSpace(ZZ, (0,1)) sage: S = Rec((M0,M1), vector((0,1)), vector((1,1))) sage: F = S.parent().indices() sage: S[F((0,0,1))] 103
Would it be possible and desirable that the following also works?
sage: M0 = matrix(2,[1,2,3,4]) sage: M1 = matrix(2,[2,1,3,7]) sage: Rec = RecognizableSeriesSpace(ZZ, (0,1)) sage: S = Rec((M0,M1), vector((0,1)), vector((1,1))) sage: S[(0,0,1)] 103
11.
 return prod(tuple(self.mu[a] for a in w), z=self._mu_of_empty_word_()) + return prod((self.mu[a] for a in w), z=self._mu_of_empty_word_())
 This calls
self[w]
twice which is not good:
return iter((w, self[w]) for w in self.parent().indices() if self[w] != 0)
You may want to do a for loop with yields statements and replace
return iter([])
by araise StopIteration
.
 While reading chapter on Recognizable series of Berstel and Reutenauer, one
sees that
is_proper
,S+S
,S^+
,S^*
,S+1
,2*S
,hadamard_product
,a^1*S
,S.dimension()
are not implemented. Are these intended to be coded? Why not in this ticket?
 I do not understand what this means:
def populate_interactive(self): r""" Return an iterator over possible new elements.
Is the code equivalent to the following?
return (p + a for p in self.elements for a in self.words.iterate_by_length(1))
 What should
__eq__
return?
sage: M0 = matrix(2,[1,2,3,4]) sage: M1 = matrix(2,[2,1,3,7]) sage: Rec = RecognizableSeriesSpace(ZZ, (0,1)) sage: S = Rec((M0,M1), vector((0,1)), vector((1,1))) sage: S == S.minimized() False
Should it be self.minimized() == other.minimized()
?
 There should be an example in the top level module doc showing a nice aspect of what this module do. The most important code for now seems to be (1) Creation of a recognizable series and (2) the minimization of a recognizable series.
 I would add a method
linear_representation
which would return the 3tuple(left, mu, right)
. From Berstel and Reutenauer: "the triple (λ, μ, γ) is called a linear representation of S", because print does not says much.
This review was done during https://wiki.sagemath.org/thursdays_bordeaux
comment:21 Changed 3 years ago by
 Keywords thursdaysbdx added
comment:22 Changed 3 years ago by
 Dependencies #21200 deleted
 Milestone changed from sage7.4 to sage8.0
comment:23 Changed 2 years ago by
 Commit changed from 4970cf5984fb88c379748c29fd3824981389468e to c2bf1b852d6865b0f76b9b8f66118c180af54c91
Branch pushed to git repo; I updated commit sha1. New commits:
c2bf1b8  Merge tag '8.1' into u/dkrenn/sequences/recognizable

comment:24 Changed 18 months ago by
 Commit changed from c2bf1b852d6865b0f76b9b8f66118c180af54c91 to 5dbdcbb79a50371eda4a6fd65a7511e91e915469
Branch pushed to git repo; I updated commit sha1. New commits:
5dbdcbb  Merge tag '8.7' into u/dkrenn/sequences/recognizable

Branch pushed to git repo; I updated commit sha1. New commits:
move "transpose" in docstring to correct place