Opened 3 years ago

Last modified 8 months ago

#21295 needs_work enhancement

recognizable series (a base for k-regular sequences)

Reported by: dkrenn Owned by:
Priority: major Milestone: sage-8.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 3 years ago by dkrenn

  • Branch set to u/dkrenn/sequences/recognizable

comment:2 Changed 3 years ago by git

  • Commit set to fd4f5414050ce650eeedca54580535aefeb008a1

Branch pushed to git repo; I updated commit sha1. New commits:

fd4f541move "transpose" in docstring to correct place

comment:3 Changed 3 years ago by dkrenn

  • Status changed from new to needs_review

comment:4 Changed 3 years ago by git

  • Commit changed from fd4f5414050ce650eeedca54580535aefeb008a1 to 9e12383a4d19664c152c26248768c69dc1c893e8

Branch pushed to git repo; I updated commit sha1. New commits:

863d57aremove None-sense to simplify code
aec95ceextend element constructor
9e12383add experimental warning

comment:5 Changed 3 years ago by git

  • Commit changed from 9e12383a4d19664c152c26248768c69dc1c893e8 to 41874bafbd0fdd2faafbd499a0933f8ca502843e

Branch pushed to git repo; I updated commit sha1. New commits:

41874bafix a typo

comment:6 Changed 3 years ago by dkrenn

  • Status changed from needs_review to needs_work

comment:7 Changed 3 years ago by git

  • Commit changed from 41874bafbd0fdd2faafbd499a0933f8ca502843e to c7243a68f3be1898b6e478b429954587e2b493db

Branch pushed to git repo; I updated commit sha1. New commits:

c7243a6Merge tag '7.4.beta1' into t/21295/sequences/recognizable

comment:8 Changed 3 years ago by dkrenn

  • Status changed from needs_work to needs_review

comment:9 Changed 3 years ago by git

  • Commit changed from c7243a68f3be1898b6e478b429954587e2b493db to 352751e2d5ff38ca5d5d819c01385035d11f2269

Branch pushed to git repo; I updated commit sha1. New commits:

352751eMerge tag '7.4.beta2' into t/21295/sequences/recognizable

comment:10 follow-up: Changed 3 years ago by cheuberg

  • Status changed from needs_review to needs_work

patchbot python3 plugin failure

comment:11 follow-up: Changed 3 years ago by cheuberg

  • Dependencies set to #21200

6 of the 9 commits of #21200 are in this branch here, so #21200 should probably a dependency.

comment:12 Changed 3 years ago by cheuberg

  • Branch changed from u/dkrenn/sequences/recognizable to u/cheuberg/sequences/recognizable

comment:13 Changed 3 years ago by git

  • Commit changed from 352751e2d5ff38ca5d5d819c01385035d11f2269 to a6b55613133efc2d002a8ae4b4f194621fd3717d

Branch pushed to git repo; I updated commit sha1. New commits:

a6b5561Trac #21295: fix ReST error

comment:14 Changed 3 years ago by git

  • Commit changed from a6b55613133efc2d002a8ae4b4f194621fd3717d to c9c3408af4edead15b16886353258731d35092e0

Branch pushed to git repo; I updated commit sha1. New commits:

c9c3408Trac #21295: fix typos

comment:15 Changed 3 years ago by dkrenn

  • Branch changed from u/cheuberg/sequences/recognizable to u/dkrenn/sequences/recognizable

comment:16 in reply to: ↑ 10 Changed 3 years ago by dkrenn

  • Commit changed from c9c3408af4edead15b16886353258731d35092e0 to 4a43407d37361ab2e24b965e13358ab408ef894a

Replying to cheuberg:

patchbot python3 plugin failure

Fixed. Merged in 7.5


New commits:

4fe1a56Merge tag '7.5' into t/21295/sequences/recognizable
5848353Python3: __nonzero__
4a43407Python3: izip

comment:17 Changed 3 years ago by git

  • Commit changed from 4a43407d37361ab2e24b965e13358ab408ef894a to 4970cf5984fb88c379748c29fd3824981389468e

Branch pushed to git repo; I updated commit sha1. New commits:

4970cf5Python3: absolute import

comment:18 in reply to: ↑ 11 Changed 3 years ago by dkrenn

Replying to cheuberg:

6 of the 9 commits of #21200 are in this branch here, so #21200 should probably a dependency.

Yes, indeed. Thank you

comment:19 Changed 3 years ago by dkrenn

  • Status changed from needs_work to needs_review

comment:20 Changed 3 years ago by slabbe

  • Reviewers set to Sébastien Labbé
  • Status changed from needs_review to needs_work

Some remarks.

  1. Document keyword infinite in the list of inputs of RecognizableSeriesSpace??.
  1. Add an example of use of keyword category in doc of RecognizableSeriesSpace??.
  1. 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.

  1. 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'>
  1. "The indices of this family are the alphabet." -> is the alphabet or -> are elements of the alphabet
  1. 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)
  1. 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
  1. 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.

  1. I would remove this space, no?
class RecognizableSeries(Element):

    def __init__(self, parent, mu, left, right):
  1. 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_())
  1. 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 a raise StopIteration.

  1. 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?

  1. 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))
  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() ?

  1. 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.
  1. I would add a method linear_representation which would return the 3-tuple (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 slabbe

  • Keywords thursdaysbdx added

comment:22 Changed 3 years ago by chapoton

  • Dependencies #21200 deleted
  • Milestone changed from sage-7.4 to sage-8.0

comment:23 Changed 20 months ago by git

  • Commit changed from 4970cf5984fb88c379748c29fd3824981389468e to c2bf1b852d6865b0f76b9b8f66118c180af54c91

Branch pushed to git repo; I updated commit sha1. New commits:

c2bf1b8Merge tag '8.1' into u/dkrenn/sequences/recognizable

comment:24 Changed 8 months ago by git

  • Commit changed from c2bf1b852d6865b0f76b9b8f66118c180af54c91 to 5dbdcbb79a50371eda4a6fd65a7511e91e915469

Branch pushed to git repo; I updated commit sha1. New commits:

5dbdcbbMerge tag '8.7' into u/dkrenn/sequences/recognizable
Note: See TracTickets for help on using tickets.