New method transducers.Recursion #17221

cheuberg · 2014-10-25T15:09:07Z

A new transducer generator for sequences given by recursions a(q^K n + r) = a(q^k n + s_r) + t_r for some 0<k<K.

Depends on #17752

CC: @sagetrac-skropf @dkrenn

Component: finite state machines

Keywords: recursion, sd66

Author: Clemens Heuberger

Branch: 2cd08fb

Reviewer: Daniel Krenn, Sara Kropf

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

The text was updated successfully, but these errors were encountered:

cheuberg · 2015-01-24T05:55:50Z

comment:2

Needs to be rewritten to avoid using the recursion where the sequence is not defined.

sagetrac-git · 2015-02-07T14:37:02Z

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

`8a880be`	`Trac #17221: Add reference`
`570cac5`	`Trac #17221: Also deal with negative s. Well-posedness is now strictly enforced.`
`6785007`	`Trac #17221: Add doctest for paperfolding sequence`
`b86e14f`	`Merge branch 'fsm/recursion/paperfolding-sequence' into fsm/generator-recursion`
`57bad3c`	`Trac #17221: Replace one more occurrence of "2" by "base"`
`e9bc72f`	`Trac #17221: Fix lifting of rules to higher exponents`
`38b5341`	`Trac #17221: Adapt doctests of paperfolding sequence to new output`
`1ab837d`	`Trac #17221: Add reference and additional doctest for paperfolding sequence`

sagetrac-git · 2015-02-07T14:37:02Z

Changed commit from 44a2455 to 1ab837d

sagetrac-git · 2015-02-09T10:56:28Z

Changed commit from 1ab837d to 0ea253d

sagetrac-git · 2015-02-09T10:56:28Z

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

`12f7062`	`Trac #17752: Move reference [HKW2014] to a global "References" block`
`5dc81de`	`Trac #17752: Update reference [HKP2014]`
`ec9264a`	`Merge branch 'fsm/references' into fsm/generator-recursion`
`0ea253d`	`Trac #17221: Move reference [HKP2015] to a global "References" block`

cheuberg · 2015-02-09T10:57:51Z

comment:6

Merged #17752 and adapted [HKP2015].

cheuberg · 2015-02-09T10:57:51Z

Dependencies: #17752

dkrenn · 2015-02-09T13:52:52Z

comment:7

Review of 1ab837d. Here are a couple of things that could be improved:

coercions mentioned w.r.t. output rings are conversions
maybe: range(base.abs()) --> srange(base.abs()) (in code and docstring)
I'm not sure if it is good to mention "Python int" at all (in docstring), since usually they shouldn't appear (maybe adapt your code (where necessary) to avoid Python-int output (if any appears; not checked by me))
T(expansion) ==f(n) is confusing, e.g. in the first example (binary sum of digits) you would have here [1,1,1] = T([1,1,1]) = f(7) = 3.
example binary sum of digits: Maybe (for a deeper understanding) it helps, if one could see the output of the transducer on a concrete example. Maybe also write one sentence why binary sum of digits gives the Identity-transducer and how one can see the sum of digits somewhere.
still example binary sum of digits: there is a lot about output_rings...is this needed in the first example already? Maybe make that a second example or at least separate it from the first example, so that it is clear, this is not needed to understand in the introductory example.
example nonadjacent form: it would be good to include concrete examples here as well, so that one sees a NAF and its weight. Also: at the moment digits -1 are not considered, but in the wiki-article they are mentioned at the top; this could lead to some confusion.

Apart from those things: code looks good, doc builds, tests pass. I did not check the math of the ticket, only the examples (these seem to be correct). I would be happy if someone else could help with this part.

I've also made a couple of small changes (PEP8; docstrings) which I'll upload soon.

dkrenn · 2015-02-09T13:52:52Z

Reviewer: Daniel Krenn

dkrenn · 2015-02-09T13:56:19Z

Changed branch from u/cheuberg/fsm/generator-recursion to u/dkrenn/fsm/generator-recursion

dkrenn · 2015-02-09T13:57:30Z

comment:9

Added a small reviewer patch.

New commits:

`5bfa80b`	`two fullstops at end of lines added`
`81bb95b`	`Merge branch 'u/cheuberg/fsm/generator-recursion' of trac.sagemath.org:sage into t/17221/fsm/generator-recursion`
`5c811af`	`Merge branch 'u/cheuberg/fsm/generator-recursion' of trac.sagemath.org:sage into t/17221/fsm/generator-recursion`
`bbd1b7e`	`reviewer-patch: PEP8, minor rewritings in docstrings`
`53bbb91`	`Merge branch 't/17221/fsm/generator-recursion-review' into t/17221/fsm/generator-recursion`

dkrenn · 2015-02-09T13:57:30Z

Changed commit from 0ea253d to 53bbb91

cheuberg · 2015-02-10T16:07:22Z

comment:11

Cross-reviewed your reviewer patch, is fine, thank you.

cheuberg · 2015-02-11T19:00:47Z

Changed branch from u/dkrenn/fsm/generator-recursion to u/cheuberg/fsm/generator-recursion

cheuberg · 2015-02-11T19:00:47Z

Last 10 new commits:

`85efb10`	`Trac #17221: Interpret "+" as addition of output words.`
`4d160d7`	`Trac #17221: move parsing of equation to a different method`
`aeaebf1`	`Trac #17221: replace "coercion" by "conversion" where appropriate`
`969160c`	`Trac #17221: range(base.abs()) --> srange(base.abs())`
`f891643`	`Trac #17221: remove "Python int" from docstring`
`83f1c03`	`Trac #17221: Replace example on binary sum of digits by weight of ternary expansion`
`aa37aaf`	Trac #17221: Move examples on ``output_rings`` to the end
`9594dca`	`Trac #17221: More explanations on the NAF, concrete examples`
`446f8f4`	`Trac #17221: Allow alternative input format (rules)`
`25e02eb`	`Trac #17221: Allow negative residues r in recursion rules.`

cheuberg · 2015-02-11T19:00:47Z

Changed commit from 53bbb91 to 25e02eb

cheuberg · 2015-02-11T19:04:44Z

comment:13

Replying to @dkrenn:

Review of 1ab837d. Here are a couple of things that could be improved:

coercions mentioned w.r.t. output rings are conversions

done: aeaebf1

maybe: range(base.abs()) --> srange(base.abs()) (in code and docstring)

done: 969160c

I'm not sure if it is good to mention "Python int" at all (in docstring), since usually they shouldn't appear (maybe adapt your code (where necessary) to avoid Python-int output (if any appears; not checked by me))

done: f891643

In fact, as a by-product of 85efb10, Python int cannot occur any more.

T(expansion) ==f(n) is confusing, e.g. in the first example (binary sum of digits) you would have here [1,1,1] = T([1,1,1]) = f(7) = 3.

This lead to a new concept for the whole method: it is more general to interpret + as addition of words than to interpret it in a ring. So this has been changed in 85efb10. I somehow reworded this sentence you mention here, please check whether it is clearer now.

example binary sum of digits: Maybe (for a deeper understanding) it helps, if one could see the output of the transducer on a concrete example. Maybe also write one sentence why binary sum of digits gives the Identity-transducer and how one can see the sum of digits somewhere.

I replaced the example by the weight of the ternary expansion; here it should be clearer. Concrete example and more explanations added (83f1c03).

still example binary sum of digits: there is a lot about output_rings...is this needed in the first example already? Maybe make that a second example or at least separate it from the first example, so that it is clear, this is not needed to understand in the introductory example.

Done: aa37aaf

example nonadjacent form: it would be good to include concrete examples here as well, so that one sees a NAF and its weight. Also: at the moment digits -1 are not considered, but in the wiki-article they are mentioned at the top; this could lead to some confusion.

Done: 9594dca

cheuberg · 2015-02-11T19:05:01Z

comment:14

Apart from that, I made three more changes:

4d160d7 Trac New method transducers.Recursion #17221: move parsing of equation to a different method

transducers.Recursions had two major parts: parsing the symbolic
equations and actual construction of the transducer. These first part
has now been refactored into a new method.
446f8f4 Trac New method transducers.Recursion #17221: Allow alternative input format (rules)

Allow to enter the recursions in the form of rules as they are stored
internally. In that case, no symbolic function and no variable are needed,
so the order of the parameters has been changed.
25e02eb Trac New method transducers.Recursion #17221: Allow negative residues r in recursion rules.

dkrenn · 2015-04-01T18:52:02Z

Changed branch from u/cheuberg/fsm/generator-recursion to u/dkrenn/fsm/generator-recursion

dkrenn · 2015-04-01T18:54:17Z

Changed keywords from recursion to recursion, sd66

dkrenn · 2015-04-01T18:54:17Z

Changed commit from 25e02eb to 2cd08fb

dkrenn · 2015-04-01T18:54:17Z

comment:17

Looks good. Tests pass. Docstrings good. Positive!

New commits:

`2cd08fb`	`Trac #17221: minor changes in docstring (reviewer patch)`

sagetrac-skropf · 2015-04-13T11:20:18Z

Changed branch from u/dkrenn/fsm/generator-recursion to u/skropf/fsm/generator-recursion

sagetrac-git · 2015-04-13T11:22:22Z

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

`2e62790`	`Trac #17221: Minor changes in the documentation`

sagetrac-git · 2015-04-13T11:22:22Z

Changed commit from 2cd08fb to 2e62790

sagetrac-skropf · 2015-04-13T11:23:38Z

comment:21

For me, it is also ok. Positive review.

cheuberg · 2015-04-13T16:27:45Z

Changed reviewer from Daniel Krenn to Daniel Krenn, Sara Kropf

cheuberg · 2015-04-13T16:27:45Z

comment:22

For the record: The doctest removed in 2e62790 was a duplicate. This explains its removal.

vbraun · 2015-04-14T19:44:07Z

Changed branch from u/skropf/fsm/generator-recursion to 2e62790

cheuberg · 2015-04-17T04:20:18Z

Changed branch from 2e62790 to 2cd08fb

cheuberg · 2015-04-17T04:20:18Z

comment:24

Replying to @sagetrac-git:

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

`2e62790`	`Trac #17221: Minor changes in the documentation`

This last commit has not been merged, see the discussion at sage-devel. Follow-up ticket is #18206.

cheuberg · 2015-04-17T04:20:18Z

Changed commit from 2e62790 to none

cheuberg added this to the sage-6.4 milestone Oct 25, 2014

cheuberg added c: finite state machines labels Oct 25, 2014

cheuberg added s: needs work and removed s: needs review labels Jan 24, 2015

This comment has been minimized.

Sign in to view

cheuberg added s: needs review and removed s: needs work labels Feb 7, 2015

cheuberg modified the milestones: sage-6.4, sage-6.5 Feb 7, 2015

dkrenn added s: needs work and removed s: needs review labels Feb 9, 2015

cheuberg added s: needs review and removed s: needs work labels Feb 11, 2015

dkrenn added s: positive review and removed s: needs review labels Apr 1, 2015

sagetrac-skropf mannequin added s: needs review and removed s: positive review labels Apr 13, 2015

sagetrac-skropf mannequin added s: positive review and removed s: needs review labels Apr 13, 2015

vbraun removed the s: positive review label Apr 14, 2015

vbraun closed this as completed Apr 14, 2015

This was referenced Dec 8, 2015

Fourier coefficients of the fluctuation of the output sum of a transducer #17222

Open

Plot fluctuations of the output sum of a transducer #17263

Open

sagetrac-skropf mannequin mentioned this issue Apr 15, 2015

transducers.Recursion: Improvement of the documentation #18206

Closed

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

New method transducers.Recursion #17221

New method transducers.Recursion #17221

cheuberg commented Oct 25, 2014

cheuberg commented Jan 24, 2015

sagetrac-git mannequin commented Feb 7, 2015

sagetrac-git mannequin commented Feb 7, 2015

This comment has been minimized.

sagetrac-git mannequin commented Feb 9, 2015

sagetrac-git mannequin commented Feb 9, 2015

cheuberg commented Feb 9, 2015

cheuberg commented Feb 9, 2015

dkrenn commented Feb 9, 2015

dkrenn commented Feb 9, 2015

dkrenn commented Feb 9, 2015

dkrenn commented Feb 9, 2015

dkrenn commented Feb 9, 2015

cheuberg commented Feb 10, 2015

cheuberg commented Feb 11, 2015

cheuberg commented Feb 11, 2015

cheuberg commented Feb 11, 2015

cheuberg commented Feb 11, 2015

cheuberg commented Feb 11, 2015

dkrenn commented Apr 1, 2015

dkrenn commented Apr 1, 2015

dkrenn commented Apr 1, 2015

dkrenn commented Apr 1, 2015

sagetrac-skropf mannequin commented Apr 13, 2015

sagetrac-git mannequin commented Apr 13, 2015

sagetrac-git mannequin commented Apr 13, 2015

sagetrac-skropf mannequin commented Apr 13, 2015

cheuberg commented Apr 13, 2015

cheuberg commented Apr 13, 2015

vbraun commented Apr 14, 2015

cheuberg commented Apr 17, 2015

cheuberg commented Apr 17, 2015

cheuberg commented Apr 17, 2015

New method transducers.Recursion #17221

New method transducers.Recursion #17221

Comments

cheuberg commented Oct 25, 2014

cheuberg commented Jan 24, 2015

sagetrac-git mannequin commented Feb 7, 2015

sagetrac-git mannequin commented Feb 7, 2015

This comment has been minimized.

sagetrac-git mannequin commented Feb 9, 2015

sagetrac-git mannequin commented Feb 9, 2015

cheuberg commented Feb 9, 2015

cheuberg commented Feb 9, 2015

dkrenn commented Feb 9, 2015

dkrenn commented Feb 9, 2015

dkrenn commented Feb 9, 2015

dkrenn commented Feb 9, 2015

dkrenn commented Feb 9, 2015

cheuberg commented Feb 10, 2015

cheuberg commented Feb 11, 2015

cheuberg commented Feb 11, 2015

cheuberg commented Feb 11, 2015

cheuberg commented Feb 11, 2015

cheuberg commented Feb 11, 2015

dkrenn commented Apr 1, 2015

dkrenn commented Apr 1, 2015

dkrenn commented Apr 1, 2015

dkrenn commented Apr 1, 2015

sagetrac-skropf mannequin commented Apr 13, 2015

sagetrac-git mannequin commented Apr 13, 2015

sagetrac-git mannequin commented Apr 13, 2015

sagetrac-skropf mannequin commented Apr 13, 2015

cheuberg commented Apr 13, 2015

cheuberg commented Apr 13, 2015

vbraun commented Apr 14, 2015

cheuberg commented Apr 17, 2015

cheuberg commented Apr 17, 2015

cheuberg commented Apr 17, 2015