get k-regular sequence from certain recurrence relations

[galipnik]

Code for constructing the linear representation of k-regular sequences given by certain recurrence relations.

See also Meta ticket #21202.

Depends on #21295
Depends on #21203

CC: @dkrenn

Component: combinatorics

Author: Gabriel F. Lipnik, Daniel Krenn

Branch/Commit: 488123c

Reviewer: Clemens Heuberger, Daniel Krenn

Issue created by migration from https://trac.sagemath.org/ticket/27940

[embray]

comment:2

As the Sage-8.8 release milestone is pending, we should delete the sage-8.8 milestone for tickets that are not actively being worked on or that still require significant work to move forward. If you feel that this ticket should be included in the next Sage release at the soonest please set its milestone to the next release milestone (sage-8.9).

[sagetrac-git]

Changed commit from 3b7c866 to d367496

[sagetrac-git]

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

9e0f817	Merge tag '8.8' into u/galipnik/k-regular-recursions
0b03904	ccMerge tag '8.9' into u/galipnik/k-regular-recursions
d367496	n0 as input for _parse_recursions_

[sagetrac-git]

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

c2c47e0	implement correction for n0
7d47dbe	add examples

[sagetrac-git]

Changed commit from d367496 to 7d47dbe

[sagetrac-git]

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

c2d9903

add another example

[sagetrac-git]

Changed commit from 7d47dbe to c2d9903

[sagetrac-git]

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

98c24d1

start_values --> initial_values

[sagetrac-git]

Changed commit from c2d9903 to 98c24d1

[sagetrac-git]

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

060ca25

add doc-strings

[sagetrac-git]

Changed commit from 98c24d1 to 060ca25

[sagetrac-git]

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

eb44f15	start to implement correction for initial values
6aff6b4	Merge branch 'u/galipnik/k-regular-recursions' of git://trac.sagemath.org/sage into u/galipnik/k-regular-recursions

[sagetrac-git]

Changed commit from 060ca25 to 6aff6b4

[sagetrac-git]

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

b411bda	fix bug from merge
5a7d293	add n1 to recursion_rules
b0f0e1b	some fixes for n1 and dim

[sagetrac-git]

Changed commit from 6aff6b4 to b0f0e1b

[sagetrac-git]

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

9ced30c	adapt tests
0bdf2e1	adapt definition of l and u
a29d29b	add _get_ind_
b36adac	fix constructions

[sagetrac-git]

Changed commit from b0f0e1b to b36adac

[sagetrac-git]

Changed commit from b36adac to d0fe273

[sagetrac-git]

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

d0fe273

adapt construction of W and J

[sagetrac-git]

Changed commit from d0fe273 to 2edf0cf

[sagetrac-git]

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

49850eb	adapt docstring
78e21ac	more changes in docstrings
2edf0cf	refactor

[sagetrac-git]

Changed commit from 2edf0cf to 9b454f9

[sagetrac-git]

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

9b454f9

some more changes in the docstring...

[sagetrac-git]

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

46fc3e5	fix link to :meth:minimized
1e43197	some more updates

[sagetrac-git]

Changed commit from 9b454f9 to 1e43197

[sagetrac-git]

Changed commit from 288995e to 86c5df7

[dkrenn]

Changed author from Gabriel F. Lipnik to Gabriel F. Lipnik, Daniel Krenn

[dkrenn]

comment:59

As discussed, I've slightly refactored the code to have the parser and all helper methods in a separate class. I suggest to review the changes above commit-wise.

[dkrenn]

Changed reviewer from Clemens Heuberger to Clemens Heuberger, Daniel Krenn

[cheuberg]

comment:60

I reviewed the refactored code, fine for me except for one suggestion:

67. RecurrenceParser.__call__: I suggest to keep the signature of the output consistent with the signature of the input of k-regular sequences, i.e., (mu, left, right). Otherwise, I think that the lines

    left, mu, right = RP(*args, **kwds)
    return self(mu, left, right)

    in kRegularSequenceSpace.from_recurrence are surprising.

[sagetrac-git]

Changed commit from 86c5df7 to 6db5f58

[sagetrac-git]

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

6db5f58

Trac #27940 review 67: change signature of output of RecurrenceParser.__call__

[dkrenn]

comment:62

Replying to @cheuberg:

I reviewed the refactored code, fine for me except for one suggestion:

67. RecurrenceParser.__call__: I suggest to keep the signature of the output consistent with the signature of the input of k-regular sequences, i.e., (mu, left, right). Otherwise, I think that the lines

    left, mu, right = RP(*args, **kwds)
    return self(mu, left, right)

    in kRegularSequenceSpace.from_recurrence are surprising.

Changed. (Note that RecognizableSeries.linear_representation uses left, mu, right; if this should be changed as well (on a follow-up ticket to the whole k-regular stuff #21202), then now would be a good time as it is not yet merged in a stable release, only in a beta. Any thoughts?)

[cheuberg]

comment:63

Yes, in the last iteration of the other ticket (#21238), I was also thinking about the inconsistency between the input of k-regular sequences and the output of linear_representation.

It seems that the order left, mu, right for linear_representation has not been invented within this series of tickets, but is defined in that way at least somewhere in the literature (e.g. Berstel and Reutenauer p. 10). So in my opinion if we aim for consistency, then the signature of element creation in regular sequences should be changed. And, as you say, if it is done, then it should be done very soon.

[cheuberg]

comment:64

As discussed earlier off-site: linear_representation should stick to the ordering in the literature (left, matrices, right); construction of recognizable series should stick to the current implementatoin (matrices, left, right): if we ever decide to make left and right optional, this ordering is required.

This means that we do not change anything here; we just wait for the patchbot.

[cheuberg]

comment:65

@galipnik: could you please also have a look on dkrenn's changes?

[galipnik]

comment:66

Replying to @cheuberg:

@galipnik: could you please also have a look on dkrenn's changes?

Done, the changes are fine for me. Thank you!

[galipnik]

Changed branch from u/dkrenn/k-regular-recurions-rebased to u/galipnik/k-regular-recurions-rebased

[galipnik]

Changed commit from 6db5f58 to 288995e

[sagetrac-git]

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

6ff29ba	Trac #27940: fix doctests (use RecurrenceParser)
22cb3f0	Trac #27940: remove underscores from helper methods
293905a	Trac #27940: remove "_from_recurrence" from method names
75fe130	Trac #27940: remove "get_" from method names
952d724	Trac #27940: consistently use coefficient_ring
fbf3a81	Trac #27940: adapt/complete docstrings
16de2ab	Trac #27940: unify input parameters
86c5df7	Trac #27940: fix indention (due to renamings)
6db5f58	Trac #27940 review 67: change signature of output of RecurrenceParser.__call__
488123c	Trac #27940: remove redundant line

[sagetrac-git]

Changed commit from 288995e to 488123c

[galipnik]

comment:69

Sorry for the late change, but I incidentally found a redundant line of code and removed it in the last commit 488123c. I've restarted the patchbot.

[cheuberg]

comment:70

488123c is fine. Patchbot is happy. Time to set it to positive.

[vbraun]

Changed branch from u/galipnik/k-regular-recurions-rebased to 488123c