Opened 6 years ago

Closed 12 months ago

#21295 closed enhancement (fixed)

recognizable series (a base for k-regular sequences)

Reported by: dkrenn Owned by:
Priority: major Milestone: sage-9.4
Component: combinatorics Keywords: thursdaysbdx
Cc: galipnik Merged in:
Authors: Daniel Krenn Reviewers: Sébastien Labbé, Clemens Heuberger
Report Upstream: N/A Work issues:
Branch: 42606e3 (Commits, GitHub, GitLab) Commit: 42606e37c2f4a301c3c597a2470a62ae5687022c
Dependencies: #30551 Stopgaps:

Status badges

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

comment:1 Changed 6 years ago by dkrenn

  • Branch set to u/dkrenn/sequences/recognizable

comment:2 Changed 6 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 6 years ago by dkrenn

  • Status changed from new to needs_review

comment:4 Changed 6 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 6 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 6 years ago by dkrenn

  • Status changed from needs_review to needs_work

comment:7 Changed 6 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 6 years ago by dkrenn

  • Status changed from needs_work to needs_review

comment:9 Changed 6 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 5 years ago by cheuberg

  • Status changed from needs_review to needs_work

patchbot python3 plugin failure

comment:11 follow-up: Changed 5 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 5 years ago by cheuberg

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

comment:13 Changed 5 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 5 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 5 years ago by dkrenn

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

comment:16 in reply to: ↑ 10 Changed 5 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 5 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 5 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 5 years ago by dkrenn

  • Status changed from needs_work to needs_review

comment:20 follow-up: Changed 5 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 5 years ago by slabbe

  • Keywords thursdaysbdx added

comment:22 Changed 5 years ago by chapoton

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

comment:23 Changed 4 years 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 3 years 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

comment:25 Changed 15 months ago by cheuberg

  • Branch changed from u/dkrenn/sequences/recognizable to u/cheuberg/sequences/recognizable
  • Commit changed from 5dbdcbb79a50371eda4a6fd65a7511e91e915469 to a194ee636bd1b9c8977cf06f6ef3f6fe0aedc7cd

New commits:

de83710Trac #21295: Fix typo
cc8cfcbTrac #21295: Fix ReST syntax
a194ee6Trac #21295: Fix indentation

comment:26 Changed 13 months ago by git

  • Commit changed from a194ee636bd1b9c8977cf06f6ef3f6fe0aedc7cd to 3b6f64407c5a76452f652a23878cd2f973b96098

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

99297d0Trac #21295: Fix typo in docstring
3b6f644Trac #21295: Fix ReST reference syntax

comment:27 follow-up: Changed 13 months ago by cheuberg

  • Milestone changed from sage-8.0 to sage-9.4
  • Reviewers changed from Sébastien Labbé to Sébastien Labbé, Clemens Heuberger

I now had a look at the code and a few comments:

  1. Please move reference BR2010 to src/doc/en/reference/references/index.rst as per the developer's guide https://doc.sagemath.org/html/en/developer/coding_basics.html#the-docstring-of-a-function-content
  1. The examples in the developer's guide do not have a closing punctuation for INPUT and OUTPUT items
  1. PrefixClosedSet.__init__: I suggest to clarify in the docstring that the parameters alphabet and words are mutually exclusive and to also throw an error if this is not the case (currently, the words parameter is silently discarded if alphabet is set).
  1. PrefixClosedSet.__init__: When first reading this, I was confused by the parameter words because I assumed that it actually contains words, and then the test shows a rather empty output. Therefore, I think it would be helpful if either the name of the parameter or the description clarifies that it is a class of words.
  1. PrefixClosedSet.populate_interactive: from the name, I would guess that this method will actually add something to the set, but it is a mere iterator. Only the example then turns towards adding elements. Would a method name like iterate_possible_additions be a better name?
  1. PrefixClosedSet.populate_interactive: from the description and the example, I thought it might only list new elements. However,
    sage: P = PrefixClosedSet(alphabet=[0, 1])
    sage: P.add(P.words([0]))
    sage: list(P.populate_interactive())
    [word: 0, word: 1, word: 00, word: 01]
    

Please clarify.

  1. PrefixClosedSet.prefix_set: For me, the description does not explain what the method does; it is only understandible in the context of BR2010, Proposition 2.3.1. Something like "the set of minimal (with respect to prefix ordering) elements of the complement of self"?
  1. RecognizableSeries.__init__: The docstring promises that the documentation of left and right will give more details. I do not think that this is the case. I appreciate providing a link, but suggest to adapt the wording.
  1. RecognizableSeries.__iter__: please document explicitly that the empty word is not included.
  1. RecognizableSeries.__bool__: what is the role of sage: S # not tested in the tests?
  1. RecognizableSeries.transposed: replace the map function by a list comprehension to avoid Python3 issues
  1. In the algorithm described in Chapter 2 of BR2010, K is assumed to be a field (it is not stated in the description of the algorithm, but before the crucial Proposition 2.2.1 as well as the crucial theorem 3.2. As far as I can see, this is not mentioned in the documentation or the code here (and __bool__ calls minimized).
  1. RecognizableSeries._minimized_left_: the tests demonstrate that the zero sequence has no consistent minimized representation: sometimes, it is a 1x1 representation with 0 entries; sometimes, a 0x0 representation.
  1. RecognizableSeries._minimized_left_: one could start with ML = matrix(0, self.left.degree()) and then use ML = ML.stack(vector(left)) and get rid of the local variable Left. No extra treatment for pcs.element(0) would be necessary (as long as PrefixClosedSet.populate_interactive includes the empty word, which I would consider to be more consistent).
  1. RecognizableSeries._minimized_left_: it seems that alpha(c) is called repeatedly for all entries of the row corresponding to p with p+a in C. So I suggest to either cache the value alpha(c) or to construct the matrix row by row (either as alpha(c) or as [ZZ(c==q) for q in P], depending on whether c in C).

comment:28 Changed 13 months ago by galipnik

  • Cc galipnik added

comment:29 Changed 13 months ago by dkrenn

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

comment:30 Changed 13 months ago by dkrenn

  • Commit changed from 3b6f64407c5a76452f652a23878cd2f973b96098 to d80854685db74279a749fc00795decb787403f09

Resolved conflict with current version (9.3.rc3)


New commits:

d808546Merge tag '9.3.rc3' into t/21295/sequences/recognizable

comment:31 Changed 13 months ago by git

  • Commit changed from d80854685db74279a749fc00795decb787403f09 to 2f17011b98dbd0870cf92d33e1f37028b824d363

Branch pushed to git repo; I updated commit sha1. Last 10 new commits:

160a68aTrac #21295 review issue 3: fix non-vector input
08e7555Trac #21295 review issue 4: fix wording "indices are"
794573bTrac #21295 review issue 6: remove transpose keyword
c200d07Trac #21295 review issue 9: remove some empty lines
c2cbe85Trac #21295 review issue 11: remove unneccessary "tuple"
e9e7de2Trac #21295 review issue 14: document equivalent code for iterate_possible_additions
eaa7af5Trac #21295 review issue 17: linear_representation
b8746abTrac #21295 review issue 12: fix inconsistency in __iter__
7d68373Trac #21295: avoid minimization in repr
2f17011Trac #21295 review issue 29: Document that minimize uses fraction field

comment:32 in reply to: ↑ 20 Changed 13 months ago by dkrenn

Replying to slabbe:

  1. Document keyword infinite in the list of inputs of RecognizableSeriesSpace??.

There is no keyword "infinite".

  1. Add an example of use of keyword category in doc of RecognizableSeriesSpace??.

Categories can be added as with any other SageMath-Parent.

  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.

Example added.

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

Fixed.

  1. "The indices of this family are the alphabet." -> is the alphabet or -> are elements of the alphabet

Changed.

  1. There is a ReST indentation problem in the paragraph of "transpose" of RecognizableSeries?

Fixed.

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)

Indeed, this seems to be more natural to me now as well. Removed.

  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

The input needs to be a word.

  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.

Transpose was removed (see above).

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

    def __init__(self, parent, mu, left, right):

Removed.

  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

Yes, this is desirable; I'll open a follow-up ticket for it. (See #31769)

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

Done.

  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.

The iter-method as inconsistent, as an "empty" sequence was handled differently than a finite sequence. So this been rewritten and is now quite easy. (As a side note: Raising StopIteration? in a generator expression will raise a RuntimeError?; I believe a simple return should do the trick in this case.)

  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?

Arithmetic is done on follow-up tickets. (See meta ticket #21202)

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

See issue below. Now this method is called iterate_possible_additions. Indeed it is roughly equivalent to the above, but iterate_possible_additions also works correctly, when elements are extended in-between.

Documented now.

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

Equality testing is not straight forward as it might be that two equal sequences have different minimal representations. One can build the difference and then minimize to see if it is the zero sequence. This will also be done on a follow-up ticket, once arithmethic is ready.

  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.

The interesting stuff begins with regular sequences which is done on the successor ticket of this ticket. A ref will be added then.

  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.

Added.

comment:33 in reply to: ↑ 27 Changed 13 months ago by dkrenn

Replying to cheuberg:

  1. Please move reference BR2010 to src/doc/en/reference/references/index.rst as per the developer's guide https://doc.sagemath.org/html/en/developer/coding_basics.html#the-docstring-of-a-function-content

Done.

  1. The examples in the developer's guide do not have a closing punctuation for INPUT and OUTPUT items

Done.

  1. PrefixClosedSet.__init__: I suggest to clarify in the docstring that the parameters alphabet and words are mutually exclusive and to also throw an error if this is not the case (currently, the words parameter is silently discarded if alphabet is set).

init rewritten.

  1. PrefixClosedSet.__init__: When first reading this, I was confused by the parameter words because I assumed that it actually contains words, and then the test shows a rather empty output. Therefore, I think it would be helpful if either the name of the parameter or the description clarifies that it is a class of words.

init rewritten.

  1. PrefixClosedSet.populate_interactive: from the name, I would guess that this method will actually add something to the set, but it is a mere iterator. Only the example then turns towards adding elements. Would a method name like iterate_possible_additions be a better name?

Renamed.

  1. PrefixClosedSet.populate_interactive: from the description and the example, I thought it might only list new elements. However,
    sage: P = PrefixClosedSet(alphabet=[0, 1])
    sage: P.add(P.words([0]))
    sage: list(P.populate_interactive())
    [word: 0, word: 1, word: 00, word: 01]
    

Please clarify.

Clarified and example added.

  1. PrefixClosedSet.prefix_set: For me, the description does not explain what the method does; it is only understandible in the context of BR2010, Proposition 2.3.1. Something like "the set of minimal (with respect to prefix ordering) elements of the complement of self"?

Description rewritten and reference added.

  1. RecognizableSeries.__init__: The docstring promises that the documentation of left and right will give more details. I do not think that this is the case. I appreciate providing a link, but suggest to adapt the wording.

Wording adapted.

  1. RecognizableSeries.__iter__: please document explicitly that the empty word is not included.

This is included; example added.

  1. RecognizableSeries.__bool__: what is the role of sage: S # not tested in the tests?

No idea anymore; I've removed it.

  1. RecognizableSeries.transposed: replace the map function by a list comprehension to avoid Python3 issues

This map is actually the map method of sage.sets.family.AbstractFamily?, so I don't think it should be replaced.

  1. In the algorithm described in Chapter 2 of BR2010, K is assumed to be a field (it is not stated in the description of the algorithm, but before the crucial Proposition 2.2.1 as well as the crucial theorem 3.2. As far as I can see, this is not mentioned in the documentation or the code here (and __bool__ calls minimized).

Yes, indeed. Minimization uses solve_left, this is a place, where it is hidden (did not find any others right now.) Now documented.

See also follow-up ticket #31770

  1. RecognizableSeries._minimized_left_: the tests demonstrate that the zero sequence has no consistent minimized representation: sometimes, it is a 1x1 representation with 0 entries; sometimes, a 0x0 representation.

I believe, this is not true. The 1x1 representation is not the zero sequence; it has a nonzero constant coefficient. This is (I hope; for sure so in the examples) also the reason why the minimization algorithm is returning this.

  1. RecognizableSeries._minimized_left_: one could start with ML = matrix(0, self.left.degree()) and then use ML = ML.stack(vector(left)) and get rid of the local variable Left. No extra treatment for pcs.element(0) would be necessary (as long as PrefixClosedSet.populate_interactive includes the empty word, which I would consider to be more consistent).

I believe that populate_interactive should not include the empty word. It is renamed now to iterate_possible_additions which makes its purpose more obvious. The empty word is not something you want to add. (I agree, however, that with your above idea, including the empty word would be worth it; maybe renaming the method once more.)

  1. RecognizableSeries._minimized_left_: it seems that alpha(c) is called repeatedly for all entries of the row corresponding to p with p+a in C. So I suggest to either cache the value alpha(c) or to construct the matrix row by row (either as alpha(c) or as [ZZ(c==q) for q in P], depending on whether c in C).

Rewritten to row by row constuction; this seem much more readable now.

comment:34 Changed 13 months ago by dkrenn

  • Status changed from needs_work to needs_review

comment:35 Changed 13 months ago by cheuberg

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

comment:36 Changed 13 months ago by git

  • Commit changed from 2f17011b98dbd0870cf92d33e1f37028b824d363 to 2b91fd873a627b9c1bb824032419a43b01da9f9d

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

2b91fd8Trac #21295: fix typo "alphabeth"

comment:37 follow-up: Changed 13 months ago by cheuberg

  • Status changed from needs_review to needs_work

Thank you for your changes and comments. I added a reviewer commit.

I still have three comments:

  1. I would also appreciate having an example in a very visible spot on how to access a coefficient. I think that unless someone guesses the __getitem__ method, they might have some hard time, in particular in view of the fact that the documentation of __getitem__ is not visible in the reference manual.
  1. In the module description, K is supposed to be a semiring. I fear that something bad might happen if that semiring is not a domain; "coefficients are automatically coerced to their fraction field." might then be inappropriate. As minimized is called by __bool__, the explanation added in minimized might not be enough.
  1. RecognizableSeries._repr_.all_coefficients: I think that the variable name number_of_nonzeros is misleading: it seems to count the number of zeros since the last zero. So I think that number_of_zeros would be more appropriate.

comment:38 Changed 13 months ago by cheuberg

For the record: the findings by the linters do not concern the files changed in this ticket.

comment:39 Changed 13 months ago by dkrenn

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

comment:40 Changed 13 months ago by git

  • Commit changed from 2b91fd873a627b9c1bb824032419a43b01da9f9d to 13ad4a1ef8368b6438c9c2ce1033113833eb8f8d

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

89f656bTrac #21295 review issue 33: rename to number_of_zeros (as it should be)
2ddb686Trac #21295 review issue 7: document accessing coefficients
13ad4a1Trac #21295 review issue 29: notice minimize vs field

comment:41 in reply to: ↑ 37 Changed 13 months ago by dkrenn

Replying to cheuberg:

  1. I would also appreciate having an example in a very visible spot on how to access a coefficient. I think that unless someone guesses the __getitem__ method, they might have some hard time, in particular in view of the fact that the documentation of __getitem__ is not visible in the reference manual.

Added.

  1. In the module description, K is supposed to be a semiring. I fear that something bad might happen if that semiring is not a domain; "coefficients are automatically coerced to their fraction field." might then be inappropriate. As minimized is called by __bool__, the explanation added in minimized might not be enough.

Note added.

  1. RecognizableSeries._repr_.all_coefficients: I think that the variable name number_of_nonzeros is misleading: it seems to count the number of zeros since the last zero. So I think that number_of_zeros would be more appropriate.

Indeed; renamed.


New commits:

cbd187fTrac #21295: rename to coefficient_ring
89f656bTrac #21295 review issue 33: rename to number_of_zeros (as it should be)
2ddb686Trac #21295 review issue 7: document accessing coefficients
13ad4a1Trac #21295 review issue 29: notice minimize vs field

comment:42 Changed 13 months ago by dkrenn

Last 10 new commits:

e9e7de2Trac #21295 review issue 14: document equivalent code for iterate_possible_additions
eaa7af5Trac #21295 review issue 17: linear_representation
b8746abTrac #21295 review issue 12: fix inconsistency in __iter__
7d68373Trac #21295: avoid minimization in repr
2f17011Trac #21295 review issue 29: Document that minimize uses fraction field
2b91fd8Trac #21295: fix typo "alphabeth"
cbd187fTrac #21295: rename to coefficient_ring
89f656bTrac #21295 review issue 33: rename to number_of_zeros (as it should be)
2ddb686Trac #21295 review issue 7: document accessing coefficients
13ad4a1Trac #21295 review issue 29: notice minimize vs field

comment:43 Changed 13 months ago by dkrenn

  • Status changed from needs_work to needs_review

comment:44 Changed 13 months ago by cheuberg

Thank you for your changes and comments. I have no further comments, feel free to set to positive once the patchbot is happy.

comment:45 Changed 12 months ago by cheuberg

  • Status changed from needs_review to positive_review

comment:46 Changed 12 months ago by git

  • Commit changed from 13ad4a1ef8368b6438c9c2ce1033113833eb8f8d to 42606e37c2f4a301c3c597a2470a62ae5687022c
  • Status changed from positive_review to needs_review

Branch pushed to git repo; I updated commit sha1 and set ticket back to needs_review. New commits:

42606e3Merge tag '9.3' into t/21295/sequences/recognizable

comment:47 Changed 12 months ago by dkrenn

  • Status changed from needs_review to positive_review

comment:48 Changed 12 months ago by cheuberg

  • Dependencies set to #30551

I add dependency #30551 (Drop python 3.6 support): this ticket introduces occurrences of islice with an sage integer as an argument; this does not work with python 3.6.

An alternative would be to explicitly convert to an integer, but as #30551 is positively reviewed, this does not seem to be necessary.

comment:49 Changed 12 months ago by vbraun

  • Branch changed from u/dkrenn/sequences/recognizable to 42606e37c2f4a301c3c597a2470a62ae5687022c
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.