search

sagemath / sage

Main repository of SageMath
https://www.sagemath.org
Other
1.44k stars 481 forks source link

New method transducers.Recursion #17221

Closed cheuberg closed 9 years ago

cheuberg commented 10 years ago

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

cheuberg commented 9 years ago
comment:2

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

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 9 years ago

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

8a880beTrac #17221: Add reference
570cac5Trac #17221: Also deal with negative s. Well-posedness is now strictly enforced.
6785007Trac #17221: Add doctest for paperfolding sequence
b86e14fMerge branch 'fsm/recursion/paperfolding-sequence' into fsm/generator-recursion
57bad3cTrac #17221: Replace one more occurrence of "2" by "base"
e9bc72fTrac #17221: Fix lifting of rules to higher exponents
38b5341Trac #17221: Adapt doctests of paperfolding sequence to new output
1ab837dTrac #17221: Add reference and additional doctest for paperfolding sequence
7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 9 years ago

Changed commit from 44a2455 to 1ab837d

cheuberg commented 9 years ago

Description changed:

--- 
+++ 
@@ -1 +1,2 @@
-A new transducer generator for sequences given by a certain type of recursions.
+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`.
+
7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 9 years ago

Changed commit from 1ab837d to 0ea253d

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 9 years ago

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

12f7062Trac #17752: Move reference [HKW2014] to a global "References" block
5dc81deTrac #17752: Update reference [HKP2014]
ec9264aMerge branch 'fsm/references' into fsm/generator-recursion
0ea253dTrac #17221: Move reference [HKP2015] to a global "References" block
cheuberg commented 9 years ago
comment:6

Merged #17752 and adapted [HKP2015].

cheuberg commented 9 years ago

Dependencies: #17752

dkrenn commented 9 years ago
comment:7

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

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 commented 9 years ago

Reviewer: Daniel Krenn

dkrenn commented 9 years ago

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

dkrenn commented 9 years ago
comment:9

Added a small reviewer patch.

New commits:

5bfa80btwo fullstops at end of lines added
81bb95bMerge branch 'u/cheuberg/fsm/generator-recursion' of trac.sagemath.org:sage into t/17221/fsm/generator-recursion
5c811afMerge branch 'u/cheuberg/fsm/generator-recursion' of trac.sagemath.org:sage into t/17221/fsm/generator-recursion
bbd1b7ereviewer-patch: PEP8, minor rewritings in docstrings
53bbb91Merge branch 't/17221/fsm/generator-recursion-review' into t/17221/fsm/generator-recursion
dkrenn commented 9 years ago

Changed commit from 0ea253d to 53bbb91

cheuberg commented 9 years ago
comment:11

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

cheuberg commented 9 years ago

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

cheuberg commented 9 years ago

Last 10 new commits:

85efb10Trac #17221: Interpret "+" as addition of output words.
4d160d7Trac #17221: move parsing of equation to a different method
aeaebf1Trac #17221: replace "coercion" by "conversion" where appropriate
969160cTrac #17221: range(base.abs()) --> srange(base.abs())
f891643Trac #17221: remove "Python int" from docstring
83f1c03Trac #17221: Replace example on binary sum of digits by weight of ternary expansion
aa37aafTrac #17221: Move examples on ``output_rings`` to the end
9594dcaTrac #17221: More explanations on the NAF, concrete examples
446f8f4Trac #17221: Allow alternative input format (rules)
25e02ebTrac #17221: Allow negative residues r in recursion rules.
cheuberg commented 9 years ago

Changed commit from 53bbb91 to 25e02eb

cheuberg commented 9 years ago
comment:13

Replying to @dkrenn:

Review of 1ab837dc5f069e044af903439caa8807b9739102. 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 commented 9 years ago
comment:14

Apart from that, I made three more changes:

dkrenn commented 9 years ago

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

dkrenn commented 9 years ago

Changed keywords from recursion to recursion, sd66

dkrenn commented 9 years ago

Changed commit from 25e02eb to 2cd08fb

dkrenn commented 9 years ago
comment:17

Looks good. Tests pass. Docstrings good. Positive!

New commits:

2cd08fbTrac #17221: minor changes in docstring (reviewer patch)
c50b3d32-6cb1-4b90-a060-6a332e54ef6a commented 9 years ago

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

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 9 years ago

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

2e62790Trac #17221: Minor changes in the documentation
7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 9 years ago

Changed commit from 2cd08fb to 2e62790

c50b3d32-6cb1-4b90-a060-6a332e54ef6a commented 9 years ago
comment:21

For me, it is also ok. Positive review.

cheuberg commented 9 years ago

Changed reviewer from Daniel Krenn to Daniel Krenn, Sara Kropf

cheuberg commented 9 years ago
comment:22

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

vbraun commented 9 years ago

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

cheuberg commented 9 years ago

Changed branch from 2e62790 to 2cd08fb

cheuberg commented 9 years ago
comment:24

Replying to @sagetrac-git:

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

2e62790Trac #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 commented 9 years ago

Changed commit from 2e62790 to none