search

sagemath / sage

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

Meta ticket: k-regular sequences #21202

Open dkrenn opened 8 years ago

dkrenn commented 8 years ago

Implementation of k-regular sequences (https://en.wikipedia.org/wiki/K-regular_sequence).

Roadmap:

Depends on #21203 Depends on #21204 Depends on #21295 Depends on #21318 Depends on #21319 Depends on #21325 Depends on #21343 Depends on #22964 Depends on #27940 Depends on #31787 Depends on #32198 Depends on #32921

CC: @behackl @cheuberg @galipnik

Component: combinatorics

Author: Daniel Krenn, Gabriel F. Lipnik

Branch/Commit: u/dkrenn/k-regular-trunk @ f3564a3

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

dkrenn commented 8 years ago

Description changed:

--- 
+++ 
@@ -2,5 +2,5 @@

 ---
 **Roadmap:**
-- basic element and parent
-- guessing k-regular sequences from the first few values
+- #21203: basic element and parent
+- #21204: guessing k-regular sequences from the first few values
dkrenn commented 8 years ago

Dependencies: #21203, #21204

dkrenn commented 8 years ago

Description changed:

--- 
+++ 
@@ -3,4 +3,11 @@
 ---
 **Roadmap:**
 - #21203: basic element and parent
+- minimization algorithm
+- arithmetic
+  - enable coercions and functorial constructions
+  - scalar multiplication
+  - addition/subtraction
+  - shift, forward/backward differences
+  - partial summation
 - #21204: guessing k-regular sequences from the first few values
dkrenn commented 8 years ago

Description changed:

--- 
+++ 
@@ -4,10 +4,13 @@
 **Roadmap:**
 - #21203: basic element and parent
 - minimization algorithm
-- arithmetic
+- arithmetic:
   - enable coercions and functorial constructions
   - scalar multiplication
   - addition/subtraction
   - shift, forward/backward differences
   - partial summation
 - #21204: guessing k-regular sequences from the first few values
+- related tickets:
+  - #21205: bounds for the joint spectral radius
+
videlec commented 8 years ago
comment:6

Please, try to not add one more class for sequences. There are already

dkrenn commented 8 years ago
comment:7

Replying to @videlec:

Please, try to not add one more class for sequences.

None of the below does what k-regular sequence do, so how to accomplish working with k-regular sequences by not adding another class? ;)

To make it clear: A k-regular sequence is a very concrete object with rules how to manipulate them. I am not intending to add a kind of metaclass for sequences.

There are already

  • lazy lists in sage.misc.lazy_list

Are more like a data structure behind; do not fit into the parent/element scheme of SageMath.

  • words in sage.combinat.words

Of course, generalizing words sufficiently, then more or less every sequence is a word. k-regular sequences have values in ZZ or QQ or something else. Moreover, they have a kind of rich arithmetic structure, which has to be implemented.

  • C finite sequence in sage.rings.cfinite_sequence

This is probably closest to k-regular sequences, but in some sense, k-regular sequence are more general, in some sense, they are orthogonal to C-finite sequences. Thus this cannot be used very well.

  • paths of directed graphs in quivers.paths.pyx

Never seen before, but for sure something different.

Would be nice to unify them at some point.

I completely agree. Any ideas how to accomplish this? The category framework might help...

dkrenn commented 8 years ago

Changed dependencies from #21203, #21204 to #21203, #21204, #21295

dkrenn commented 8 years ago

Description changed:

--- 
+++ 
@@ -2,8 +2,9 @@

 ---
 **Roadmap:**
-- #21203: basic element and parent
-- minimization algorithm
+- basic:
+  - #21295: recognozable series and the minimization algorithm
+  - #21203: basic element and parent for k-regular sequences
 - arithmetic:
   - enable coercions and functorial constructions
   - scalar multiplication
dkrenn commented 8 years ago

Changed dependencies from #21203, #21204, #21295 to #21203, #21204, #21295, #21318, #21319

dkrenn commented 8 years ago

Description changed:

--- 
+++ 
@@ -7,10 +7,12 @@
   - #21203: basic element and parent for k-regular sequences
 - arithmetic:
   - enable coercions and functorial constructions
-  - scalar multiplication
-  - addition/subtraction
+  - #21318: scalar multiplication
+  - #21318: addition/subtraction
   - shift, forward/backward differences
   - partial summation
+  - #21318: subsequences
+  - #21318: hashing, equality testing
 - #21204: guessing k-regular sequences from the first few values
 - related tickets:
   - #21205: bounds for the joint spectral radius
dkrenn commented 8 years ago

Description changed:

--- 
+++ 
@@ -12,7 +12,7 @@
   - shift, forward/backward differences
   - partial summation
   - #21318: subsequences
-  - #21318: hashing, equality testing
+  - #21319: hashing, equality testing
 - #21204: guessing k-regular sequences from the first few values
 - related tickets:
   - #21205: bounds for the joint spectral radius
dkrenn commented 8 years ago

Changed dependencies from #21203, #21204, #21295, #21318, #21319 to #21203, #21204, #21295, #21318, #21319, #21325

dkrenn commented 8 years ago

Description changed:

--- 
+++ 
@@ -9,10 +9,10 @@
   - enable coercions and functorial constructions
   - #21318: scalar multiplication
   - #21318: addition/subtraction
-  - shift, forward/backward differences
+  - #21319: hashing, equality testing
+  - #21325: subsequences, shift
+  - #21325: forward/backward differences
   - partial summation
-  - #21318: subsequences
-  - #21319: hashing, equality testing
 - #21204: guessing k-regular sequences from the first few values
 - related tickets:
   - #21205: bounds for the joint spectral radius
dkrenn commented 8 years ago

Description changed:

--- 
+++ 
@@ -11,8 +11,7 @@
   - #21318: addition/subtraction
   - #21319: hashing, equality testing
   - #21325: subsequences, shift
-  - #21325: forward/backward differences
-  - partial summation
+  - #21325: forward/backward differences, partial summation
 - #21204: guessing k-regular sequences from the first few values
 - related tickets:
   - #21205: bounds for the joint spectral radius
dkrenn commented 8 years ago

Branch: u/dkrenn/k-regular-trunk

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

Commit: cfeca16

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

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

73ad7bdMerge branch 'u/dkrenn/sequences/k-regular' into u/dkrenn/sequences/k-regular-guess
c349170fix code and doctests to adapt with upstream recognizable series
15e4008Merge branch 'u/dkrenn/sequences/k-regular' into u/dkrenn/sequences/k-regular-guess
eaf8df2Merge branch 'u/dkrenn/sequences/k-regular' into u/dkrenn/sequences/k-regular-guess
355d24dsimplify code by using features of recognizable series better (and adapting to removing None-sense)
348fcffsolve transpositioning problem
2e99c5canother example
a68e20dMerge branch 't/21203/sequences/k-regular' into t/21204/sequences/k-regular-guess
816fcfdMerge branch 't/21325/sequences/k-regular-subseq' into t/21204/sequences/k-regular-guess
cfeca16Merge branch 't/21204/sequences/k-regular-guess' into t/21202/k-regular-trunk
dkrenn commented 8 years ago

Description changed:

--- 
+++ 
@@ -9,7 +9,7 @@
   - enable coercions and functorial constructions
   - #21318: scalar multiplication
   - #21318: addition/subtraction
-  - #21319: hashing, equality testing
+  - #21319: hashing, equality testing, TestSuite
   - #21325: subsequences, shift
   - #21325: forward/backward differences, partial summation
 - #21204: guessing k-regular sequences from the first few values
7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 8 years ago

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

a8e6334MatrixSpace.some_elements
520aaf1FreeModule_generic.some_elements
5afda8eMerge branch 'u/dkrenn/matrices-some-elements' into t/21319/sequences/rec-hash
1e5754ban_element and some_elements
becce48pickling support
a4ccbecTestSuite
c2f9c62Merge branch 't/21325/sequences/k-regular-subseq' into t/21319/sequences/rec-hash
80861bcMerge branch 't/21319/sequences/rec-hash' into t/21202/k-regular-trunk
7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 8 years ago

Changed commit from cfeca16 to 80861bc

dkrenn commented 8 years ago

Description changed:

--- 
+++ 
@@ -3,7 +3,7 @@
 ---
 **Roadmap:**
 - basic:
-  - #21295: recognozable series and the minimization algorithm
+  - #21295: recognizable series and the minimization algorithm
   - #21203: basic element and parent for k-regular sequences
 - arithmetic:
   - enable coercions and functorial constructions
7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 8 years ago

Changed commit from 80861bc to 1863001

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

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

65da1e7Merge branch 'u/dkrenn/sequences/k-regular' into u/dkrenn/sequences/k-regular-guess
3e955e1guessing partial sums
0d5fbedMerge ../7.2 into t/21204/sequences/k-regular-guess
9818d94Merge branch 't/21319/sequences/rec-hash' into t/21204/sequences/k-regular-guess
90e4ed5doctests
899e56efinish .guess (docstrings etc)
1863001Merge branch 't/21204/sequences/k-regular-guess' into t/21202/k-regular-trunk
dkrenn commented 8 years ago

Changed dependencies from #21203, #21204, #21295, #21318, #21319, #21325 to #21203, #21204, #21295, #21318, #21319, #21325, #21343

dkrenn commented 8 years ago

Description changed:

--- 
+++ 
@@ -13,6 +13,8 @@
   - #21325: subsequences, shift
   - #21325: forward/backward differences, partial summation
 - #21204: guessing k-regular sequences from the first few values
+- other:
+  - #21343: deal with mu[0]*right != right in k-regular sequences
 - related tickets:
   - #21205: bounds for the joint spectral radius
7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 8 years ago

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

5444e7bactivate logging
edd773fsome doctests
ddb8f8cremove zero()
6470f09correct creation of element in transposed
f66840dmethods for dealing with healthyness
ecd22e8use logging more correctly
b2b167bequip element constructor with a warning
92a33feadd some doctests related to health
7a6340fMerge branch 't/21204/sequences/k-regular-guess' into u/dkrenn/k-regular-warning
6b7ac91Merge branch 't/21343/k-regular-warning' into t/21202/k-regular-trunk
7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 8 years ago

Changed commit from 1863001 to 6b7ac91

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

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

c0ade99Merge branch 't/21203/sequences/k-regular' into t/21318/sequences/rec-basic-arith
35807dfMerge branch 't/21318/sequences/rec-basic-arith' into t/21319/sequences/rec-hash
a2fe6f3Merge branch 't/21318/sequences/rec-basic-arith' into t/21325/sequences/k-regular-subseq
e4cec17minor correction in doc
3a4e849Merge branch 't/21318/sequences/rec-basic-arith' into t/21325/sequences/k-regular-subseq
c8a86dbMerge branch 't/21325/sequences/k-regular-subseq' into t/21319/sequences/rec-hash
0dae02bMerge branch 't/21319/sequences/rec-hash' into t/21204/sequences/k-regular-guess
5b7b85aMerge branch 't/21204/sequences/k-regular-guess' into t/21343/k-regular-warning
7bbe778Merge branch 't/21343/k-regular-warning' into t/21202/k-regular-trunk
983f86eMerge branch 'u/dkrenn/k-regular-trunk' of trac.sagemath.org:sage into t/21202/k-regular-trunk
7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 8 years ago

Changed commit from 6b7ac91 to 983f86e

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

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

92d9248Merge tag '7.4.beta3' into t/21202/k-regular-trunk
7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 8 years ago

Changed commit from 983f86e to 92d9248

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

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

13b536ePython3: absolut import
5919c4dMerge branch 't/21203/sequences/k-regular' into t/21318/sequences/rec-basic-arith
9086b64Merge branch 't/21318/sequences/rec-basic-arith' into t/21325/sequences/k-regular-subseq
fc6c3f5Python3: xrange
714276cMerge branch 't/21325/sequences/k-regular-subseq' into t/21319/sequences/rec-hash
457aefdPython3: fix iteritems
fcb53a3fix doctest output of TestSuite (new tests were added)
bde8e67Merge branch 't/21319/sequences/rec-hash' into t/21204/sequences/k-regular-guess
e25b8d2Merge branch 't/21204/sequences/k-regular-guess' into t/21343/k-regular-warning
a8482caMerge branch 't/21343/k-regular-warning' into t/21202/k-regular-trunk
7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 7 years ago

Changed commit from 92d9248 to a8482ca

dkrenn commented 7 years ago
comment:25

This is now on 7.5.

Dependency chain: #21295 #21203 #21318 #21325 #21319 #21204 #21343.

dkrenn commented 7 years ago

Description changed:

--- 
+++ 
@@ -12,6 +12,7 @@
   - #21319: hashing, equality testing, TestSuite
   - #21325: subsequences, shift
   - #21325: forward/backward differences, partial summation
+  - conversion of automatic sequences to formal series via Christol's theorem and vice versa
 - #21204: guessing k-regular sequences from the first few values
 - other:
   - #21343: deal with mu[0]*right != right in k-regular sequences
galipnik commented 7 years ago

Description changed:

--- 
+++ 
@@ -14,6 +14,7 @@
   - #21325: forward/backward differences, partial summation
   - conversion of automatic sequences to formal series via Christol's theorem and vice versa
 - #21204: guessing k-regular sequences from the first few values
+- #22964: boundedness
 - other:
   - #21343: deal with mu[0]*right != right in k-regular sequences
 - related tickets:
7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 6 years ago

Changed commit from a8482ca to 148ec6a

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

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

c2bf1b8Merge tag '8.1' into u/dkrenn/sequences/recognizable
fef79b2Merge branch 'u/dkrenn/sequences/recognizable' into u/dkrenn/sequences/k-regular
8eda76eMerge branch 'u/dkrenn/sequences/k-regular' into u/dkrenn/sequences/rec-basic-arith
0c83557Merge branch 'u/dkrenn/sequences/rec-basic-arith' into u/dkrenn/sequences/k-regular-subseq
e30a7fbMerge branch 'u/dkrenn/sequences/k-regular-subseq' into u/dkrenn/sequences/rec-hash
622c3f6Merge branch 'u/dkrenn/sequences/rec-hash' into u/dkrenn/sequences/k-regular-guess
148ec6aMerge branch 'u/dkrenn/sequences/k-regular-guess' into u/dkrenn/k-regular-trunk
dkrenn commented 6 years ago

Description changed:

--- 
+++ 
@@ -9,10 +9,10 @@
   - enable coercions and functorial constructions
   - #21318: scalar multiplication
   - #21318: addition/subtraction
-  - #21319: hashing, equality testing, TestSuite
   - #21325: subsequences, shift
   - #21325: forward/backward differences, partial summation
   - conversion of automatic sequences to formal series via Christol's theorem and vice versa
+  - #21319: hashing, equality testing, TestSuite
 - #21204: guessing k-regular sequences from the first few values
 - #22964: boundedness
 - other:
dkrenn commented 6 years ago
comment:30

This is now on 8.1.

Dependency chain: #21295 #21203 #21318 #21325 #21319 #21204 #21343.

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

Changed commit from 148ec6a to c71d605

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

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

dde1700Merge branch 'u/dkrenn/sequences/k-regular-guess' into u/dkrenn/k-regular-warning
c71d605Merge branch 'u/dkrenn/k-regular-warning' into u/dkrenn/k-regular-trunk
7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 5 years ago

Changed commit from c71d605 to d622b78

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

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

5dbdcbbMerge tag '8.7' into u/dkrenn/sequences/recognizable
d17def8Merge branch 'u/dkrenn/sequences/recognizable' into u/dkrenn/sequences/k-regular
2b998baMerge branch 'u/dkrenn/sequences/k-regular' into u/dkrenn/sequences/rec-basic-arith
1f8c2a1Merge branch 'u/dkrenn/sequences/rec-basic-arith' into u/dkrenn/sequences/k-regular-subseq
a87520eMerge branch 'u/dkrenn/sequences/k-regular-subseq' into u/dkrenn/sequences/rec-hash
4e7f615Merge branch 'u/dkrenn/sequences/rec-hash' into u/dkrenn/sequences/k-regular-guess
3b0f9d0Merge branch 'u/dkrenn/sequences/k-regular-guess' into u/dkrenn/k-regular-warning
d622b78Merge branch 'u/dkrenn/k-regular-warning' into u/dkrenn/k-regular-trunk
dkrenn commented 5 years ago
comment:33

This is now on 8.7.

Dependency chain: #21295 #21203 #21318 #21325 #21319 #21204 #21343 #22964.

galipnik commented 5 years ago

Description changed:

--- 
+++ 
@@ -14,6 +14,7 @@
   - conversion of automatic sequences to formal series via Christol's theorem and vice versa
   - #21319: hashing, equality testing, TestSuite
 - #21204: guessing k-regular sequences from the first few values
+- #27940: getting k-regular sequences from given recursions
 - #22964: boundedness
 - other:
   - #21343: deal with mu[0]*right != right in k-regular sequences
galipnik commented 3 years ago

Description changed:

--- 
+++ 
@@ -14,7 +14,7 @@
   - conversion of automatic sequences to formal series via Christol's theorem and vice versa
   - #21319: hashing, equality testing, TestSuite
 - #21204: guessing k-regular sequences from the first few values
-- #27940: getting k-regular sequences from given recursions
+- #27940: getting k-regular sequences from given recurrence relations
 - #22964: boundedness
 - other:
   - #21343: deal with mu[0]*right != right in k-regular sequences
galipnik commented 3 years ago

Description changed:

--- 
+++ 
@@ -14,7 +14,9 @@
   - conversion of automatic sequences to formal series via Christol's theorem and vice versa
   - #21319: hashing, equality testing, TestSuite
 - #21204: guessing k-regular sequences from the first few values
-- #27940: getting k-regular sequences from given recurrence relations
+- getting k-regular sequences from given recurrence relations
+  - #27940: basic methods
+  - #31787: get sequences with different input parameters
 - #22964: boundedness
 - other:
   - #21343: deal with mu[0]*right != right in k-regular sequences
7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 3 years ago

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

ad29c70Trac #22964: fix text between examples
6322a79Trac #22964: intends also in other file
05f7b24Trac #22964: fix test
f7c4a41Trac #22964: specify description of multiplicities in test cases
e9a5580Trac #22964: remove weird desription
6da9317Trac #22964: change test case
75d8245Merge branch 'u/dkrenn/k-regular-warning' into u/galipnik/k-regular-bounded
b44bdadMerge branch 't/21343/k-regular-warning' into t/22964/k-regular-bounded
a585f01Trac #22964: fixup degenerated sequences
478b8b1Merge branch 't/22964/k-regular-bounded' into t/21202/k-regular-trunk
7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 3 years ago

Changed commit from d622b78 to 478b8b1