Opened 7 years ago
Last modified 5 years ago
#16723 new enhancement
beta-adic
Reported by: | mercatp | Owned by: | mercatp |
---|---|---|---|
Priority: | minor | Milestone: | sage-feature |
Component: | PLEASE CHANGE | Keywords: | |
Cc: | tjolivet | Merged in: | |
Authors: | Reviewers: | ||
Report Upstream: | N/A | Work issues: | |
Branch: | u/mercatp/beta-adic (Commits) | Commit: | 7ae36cb1a57564e390102549262a079a02bcd54a |
Dependencies: | Stopgaps: |
Description (last modified by )
This ticket gives a implementation of beta-adic monoids, as described in the article http://www.latp.univ-mrs.fr/~paul.mercat/Publis/Semi-groupes%20fortement%20automatiques.pdf It permit to compute the beta-adic monoid corresponding to a WordMorphism?, to draw limit sets of beta-adic monoid, to compute relations automaton and reduced words automaton (defined in the article). For that I re-implemented the Automata.
This ticket is too big to be included directly into sage : I forsee to cut it in small parts that I will try to include in sage when it will be completly implemented, documented and well tested.
Change History (44)
comment:1 Changed 6 years ago by
- Branch set to u/mercatp/beta-adic
comment:2 Changed 6 years ago by
- Commit set to 91b1507bfa50a520f0d4601d1306a599a3b3008e
comment:3 Changed 6 years ago by
- Commit changed from 91b1507bfa50a520f0d4601d1306a599a3b3008e to 3e2376d996de554a54dd06fe3b64a0df5886129c
Branch pushed to git repo; I updated commit sha1. New commits:
3e2376d | Correct a bug of indentation.
|
comment:4 follow-up: ↓ 7 Changed 6 years ago by
This is pretty cryptic until you start reading the code. Could you put a brief description of what you are implementing in the "Description" area of the ticket so new people coming to it know what beta-adics are and why they should be in Sage? Otherwise it means searching a bit more through the proposed branch than necessary :(
Also, I am having a hard time finding any reference to these objects other than in your own papers. But I do find other references to beta-adic which seem to mean something else (though with "adic" of course they are somehow related). I don't know what our policy is on that; Purple Sage used to exist for that context but I think it may be defunct. Don't take this as criticism, but rather request for clarification; these files are large enough that it would be helpful to know that others will be interested in using them; especially if the name may be fluid it would be unfortunate to lock ourselves in a name, though that may be unavoidable.
(I suppose this all applies to #15883 as well, though less so.)
comment:5 Changed 6 years ago by
- Milestone changed from sage-6.3 to sage-6.4
comment:6 Changed 6 years ago by
- Commit changed from 3e2376d996de554a54dd06fe3b64a0df5886129c to 827d9524f01fc485a274afca6101422e13e6341b
Branch pushed to git repo; I updated commit sha1. New commits:
b0a8ead | Add a better plotting of automata (new functions plot2 and plot3) using GraphViz.
|
d7d4455 | Add a better way to draw a beta-adic monoid (new function plot2) using extern C files.
|
06e20ef | Add a new function plot3 to BetaAdicMonoid that draw with colors (corresponds to the colors of the Rauzy fractal when it comes from a substitution). Add the size of the result drawing as argument of plot2.
|
827d952 | Some little improvements (add Cd argument in sage.monoids.beta_adic_monoid BetaAdicMonoid.relations, change the style of the arrows for plotting automaton using TikZ)
|
comment:7 in reply to: ↑ 4 Changed 6 years ago by
- Description modified (diff)
- Milestone changed from sage-6.4 to sage-feature
- Owner changed from (none) to mercatp
- Priority changed from major to minor
Replying to kcrisman:
This is pretty cryptic until you start reading the code. Could you put a brief description of what you are implementing in the "Description" area of the ticket so new people coming to it know what beta-adics are and why they should be in Sage? Otherwise it means searching a bit more through the proposed branch than necessary :(
Sorry to be cryptic. I've writted a description. I think that these tools can be useful for others people (mainly researcher on beta-expansion, rauzy fractals, quasi-cristals etc...)
Also, I am having a hard time finding any reference to these objects other than in your own papers. But I do find other references to beta-adic which seem to mean something else (though with "adic" of course they are somehow related).
There are several names for that : beta-adic, beta-expansions, non-standard numeration systems, etc... I don't know what is the better name for that, so I choosed the name I used (in french) in my article.
I don't know what our policy is on that; Purple Sage used to exist for that context but I think it may be defunct.
I did'nt know Purple Sage. If it was not defunct, you're right, it would be more appropriate. But the last version has the date oct-2010...
Don't take this as criticism, but rather request for clarification; these files are large enough that it would be helpful to know that others will be interested in using them; especially if the name may be fluid it would be unfortunate to lock ourselves in a name, though that may be unavoidable.
As I explain now in the description, I plan to cut this ticket into smaller ones that could be inclued in sage. I would like to improve Automaton first (because I need it), then add BetaAdicMonoid? (maybe I'll change the name if I find a better one) and then modify WordMorphism? to use BetaAdicMonoid?.
(I suppose this all applies to #15883 as well, though less so.)
The ticket #15883 is an old copy of this ticket that didn't worked with sage-6.2. I should combine the two tickets, but I don't know how to do it.
comment:8 Changed 6 years ago by
- Type changed from PLEASE CHANGE to enhancement
comment:9 Changed 6 years ago by
- Commit changed from 827d9524f01fc485a274afca6101422e13e6341b to 6779b7ea6f90450052f5ad602bc1c2062fe842f1
Branch pushed to git repo; I updated commit sha1. New commits:
6779b7e | Correct a bug in getBetaAdic2 from sage.monoids.beta_adic_monoid.
|
comment:10 Changed 6 years ago by
- Commit changed from 6779b7ea6f90450052f5ad602bc1c2062fe842f1 to 23ba6f2f9e358a94cace7c962958e6e3fb3ff3b2
Branch pushed to git repo; I updated commit sha1. New commits:
23ba6f2 | Permit to set the color of the background independently in plot3 from sage.monoids.beta_adic_monoid
|
comment:11 Changed 6 years ago by
- Commit changed from 23ba6f2f9e358a94cace7c962958e6e3fb3ff3b2 to 4d6e4bd7d9beab60c243a7be8f36c9cb279699b2
Branch pushed to git repo; I updated commit sha1. New commits:
4d6e4bd | Add the function get_la() to BetaAdicMonoid and correct the doc of plot2 and plot3.
|
comment:12 Changed 6 years ago by
- Commit changed from 4d6e4bd7d9beab60c243a7be8f36c9cb279699b2 to eaf6401181420ae7c6ae45ec054dbe0a089d45b9
comment:13 Changed 6 years ago by
- Commit changed from eaf6401181420ae7c6ae45ec054dbe0a089d45b9 to 350054af54b1028cc03f62c23b7bfa1bd4dddcd5
Branch pushed to git repo; I updated commit sha1. New commits:
350054a | Correct differents bugs.
|
comment:14 Changed 6 years ago by
- Commit changed from 350054af54b1028cc03f62c23b7bfa1bd4dddcd5 to cd28a7317a3815e7ccc576d3cd1ddb11e81c6311
Branch pushed to git repo; I updated commit sha1. New commits:
cd28a73 | Add a new file that I forgot to trac.
|
comment:15 Changed 6 years ago by
- Commit changed from cd28a7317a3815e7ccc576d3cd1ddb11e81c6311 to 718704d5d6f96624430212952a0f48358a5f51d9
Branch pushed to git repo; I updated commit sha1. New commits:
718704d | Correct a bug in automata_tools.h
|
comment:16 Changed 6 years ago by
- Commit changed from 718704d5d6f96624430212952a0f48358a5f51d9 to 01f1f97c25ea9b6522efa27fd228b774d3d522af
Branch pushed to git repo; I updated commit sha1. New commits:
01f1f97 | Add usefull function to FastAutomaton. Correct some bugs of doc. Correct a bug with wrong order of letters in plot2 and plot3 of BetaAdicMonoid (need more tests).
|
comment:17 Changed 6 years ago by
- Commit changed from 01f1f97c25ea9b6522efa27fd228b774d3d522af to ffc1ae2813f89dea4759bd42fbacbee5f0fdd4e1
Branch pushed to git repo; I updated commit sha1. New commits:
ffc1ae2 | Add an efficient implementation of Hopcroft's algorithm to minimise a FastAutomaton.
|
comment:18 Changed 6 years ago by
- Commit changed from ffc1ae2813f89dea4759bd42fbacbee5f0fdd4e1 to 7e64c8a8fad6bf5c78ce5378a0b0ff5a2a2ad454
Branch pushed to git repo; I updated commit sha1. New commits:
acb1f53 | Avoid tabulation that appears after upgrading from sage 6.2 to sage 6.3
|
afeab50 | Merge branch 'u/mercatp/beta-adic' of git://trac.sagemath.org/sage into beta-adic
|
d5cbb9e | Merge branch 'u/mercatp/beta-adic' of git://trac.sagemath.org/sage into beta-adic
|
b53c93b | Merge branch 'u/mercatp/beta-adic' of git://trac.sagemath.org/sage into beta-adic
|
5119e89 | Merge branch 'u/mercatp/beta-adic' of git://trac.sagemath.org/sage into beta-adic
|
39d8fc4 | Merge branch 'u/mercatp/beta-adic' of git://trac.sagemath.org/sage into beta-adic
|
4e45a85 | Merge branch 'u/mercatp/beta-adic' of git://trac.sagemath.org/sage into beta-adic
|
7e64c8a | Add a new C function to compute relations automaton for algebraic integers. DOESN'T WORK YET !!!
|
comment:19 Changed 6 years ago by
- Commit changed from 7e64c8a8fad6bf5c78ce5378a0b0ff5a2a2ad454 to 9ce37a941f5d47a6d7545e7710c57fef41c335ef
Branch pushed to git repo; I updated commit sha1. New commits:
9ce37a9 | Corrects some bugs : now the previous computing of relations automaton using FastAutomaton works.
|
comment:20 Changed 6 years ago by
- Commit changed from 9ce37a941f5d47a6d7545e7710c57fef41c335ef to c18febb7b0763ab055b8c29bec87f1faa39d9974
Branch pushed to git repo; I updated commit sha1. New commits:
c18febb | Add new functionalities using FastAutomaton : copy, intersection, ... and correct some bugs.
|
comment:21 Changed 6 years ago by
- Cc tjolivet added
comment:22 Changed 6 years ago by
- Commit changed from c18febb7b0763ab055b8c29bec87f1faa39d9974 to 2a6a48d00c99577f090ed3bfb7f884c9c7683809
Branch pushed to git repo; I updated commit sha1. New commits:
2a6a48d | Add functions has_empty_langage() and equals_langages() to FastAutomaton.
|
comment:23 Changed 6 years ago by
- Commit changed from 2a6a48d00c99577f090ed3bfb7f884c9c7683809 to f256a4beb31200622be7ad9b7f36543a9a379185
Branch pushed to git repo; I updated commit sha1. New commits:
f256a4b | Correct some little problems with BetaAdicMonoid.relations_automaton3() and others.
|
comment:24 Changed 6 years ago by
- Commit changed from f256a4beb31200622be7ad9b7f36543a9a379185 to 79686e5424206116fa1c4b4207d5133d1b3837cc
Branch pushed to git repo; I updated commit sha1. New commits:
79686e5 | Add a function relations_automata2() to BetaAdicMonoid much more efficient than relations_automaton(), and using FastAutomaton.
|
comment:25 Changed 6 years ago by
- Commit changed from 79686e5424206116fa1c4b4207d5133d1b3837cc to 62b55671807b2e74e689fbcf9d280e9dbdb472e4
Branch pushed to git repo; I updated commit sha1. New commits:
62b5567 | Add functions is_complete(), complete(), union() and shift() to FastAutomaton. Improve adherence() of BetaAdicMonoid.
|
comment:26 Changed 6 years ago by
- Commit changed from 62b55671807b2e74e689fbcf9d280e9dbdb472e4 to d4449629d0adc2c3a106d6fe6586243a3778c510
Branch pushed to git repo; I updated commit sha1. New commits:
d444962 | Add a function move() to BetaAdicMonoid and correct some bugs.
|
comment:27 Changed 6 years ago by
- Commit changed from d4449629d0adc2c3a106d6fe6586243a3778c510 to 8d1a1cbf17de48b3b938ae2a3b0d6b09c904da61
Branch pushed to git repo; I updated commit sha1. New commits:
8d1a1cb | Correct some little bugs in beta_adic_monoid (with adherence() and initInfoBetaAdic()).
|
comment:28 Changed 6 years ago by
- Commit changed from 8d1a1cbf17de48b3b938ae2a3b0d6b09c904da61 to 4c59b96b6b69286462cc079674e664361cc58759
Branch pushed to git repo; I updated commit sha1. New commits:
4c59b96 | Improve the completion of FastAutomaton and add complementaryOP() and test of inclusion : included().
|
comment:29 Changed 6 years ago by
- Commit changed from 4c59b96b6b69286462cc079674e664361cc58759 to 968d02a20da72f146a99718f7dc8fb1c3a986140
Branch pushed to git repo; I updated commit sha1. New commits:
968d02a | Add functions split(), shift1OP() and unshift1() to FastAutomaton and correct some bugs.
|
comment:30 Changed 6 years ago by
- Commit changed from 968d02a20da72f146a99718f7dc8fb1c3a986140 to 65ba2cedccac8d28ebfe4a588efd98493c91dad8
Branch pushed to git repo; I updated commit sha1. New commits:
65ba2ce | Add a structure NAutomaton that permits to represent non-deterministic automata, and add a transposition of deterministic automaton (that gives a non-deterministic one) and a function determinise to get back a deterministic automaton.
|
comment:31 Changed 6 years ago by
- Commit changed from 65ba2cedccac8d28ebfe4a588efd98493c91dad8 to b590f0e4414e2c118b7974a98396fd9b2c5fdeb1
Branch pushed to git repo; I updated commit sha1. New commits:
b590f0e | Correct the computing of the extended relation automaton of a beta-adic monoid.
|
comment:32 Changed 6 years ago by
- Commit changed from b590f0e4414e2c118b7974a98396fd9b2c5fdeb1 to ba302836b7699ba2bf92ab2a0004f1e4f67d14bd
Branch pushed to git repo; I updated commit sha1. New commits:
ba30283 | Improve function is_final() and convert function get_la() to use FastAutomaton and not Automaton. Load class FastAutomaton at start.
|
comment:33 Changed 6 years ago by
- Commit changed from ba302836b7699ba2bf92ab2a0004f1e4f67d14bd to 8efcdea31a4a223341e68145b2aa38adc641d383
Branch pushed to git repo; I updated commit sha1. New commits:
8efcdea | Merge branch 'master' into t/16723/beta-adic
|
comment:34 Changed 6 years ago by
- Commit changed from 8efcdea31a4a223341e68145b2aa38adc641d383 to fda86b763cf787959ed28bb3966a74145357241e
Branch pushed to git repo; I updated commit sha1. New commits:
fda86b7 | Add a function piece to FastAutomaton, add intersection2 and intersect to BetaAdicMonoid
|
comment:35 Changed 6 years ago by
- Commit changed from fda86b763cf787959ed28bb3966a74145357241e to 3af2ddf276557a73b802a7f59f9181cc997aee7c
Branch pushed to git repo; I updated commit sha1. New commits:
3af2ddf | Add a function is_all_connected() to BetaAdicMonoid that decides if all the tiles of the self-similar tiling are connected.
|
comment:36 Changed 6 years ago by
- Commit changed from 3af2ddf276557a73b802a7f59f9181cc997aee7c to b5a7107424f2658442942a71c8579d5928e84109
Branch pushed to git repo; I updated commit sha1. New commits:
b5a7107 | Add __hash__ and __cmp__ functions to FastAutomaton, correct the test of equality, improve is_all_connected of BetaAdicMonoid, replace spaces by tabs for indentation and correct some bugs.
|
comment:37 Changed 6 years ago by
- Commit changed from b5a7107424f2658442942a71c8579d5928e84109 to e4c62412a0cb6e1eec0f2e6114ba9d096bd37a0b
Branch pushed to git repo; I updated commit sha1. New commits:
e4c6241 | Forget to add file src/sage/combinat/words/automataC.c
|
comment:38 Changed 5 years ago by
- Commit changed from e4c62412a0cb6e1eec0f2e6114ba9d096bd37a0b to ae245aaea19057dbe88294cb0c9d8b54905a978e
Branch pushed to git repo; I updated commit sha1. New commits:
ae245aa | Add a tool to compute relations automata with translation and change a lot of little things.
|
comment:39 Changed 5 years ago by
- Commit changed from ae245aaea19057dbe88294cb0c9d8b54905a978e to 8c1bf8a4083d1dd2fe73ebfbe7de20a469d3b22c
Branch pushed to git repo; I updated commit sha1. New commits:
8c1bf8a | Add a function move2() that compute the translate ( replace move() ), and correct some problems.
|
comment:40 Changed 5 years ago by
- Commit changed from 8c1bf8a4083d1dd2fe73ebfbe7de20a469d3b22c to a45bb655f48d152a750f0e4a30d445c5bea92593
Branch pushed to git repo; I updated commit sha1. New commits:
a45bb65 | Add a function zero_complete() for FastAutomaton, a function shift for BetaAdicMonoid (not well tested) and correct some little things.
|
comment:41 Changed 5 years ago by
- Commit changed from a45bb655f48d152a750f0e4a30d445c5bea92593 to effde91e40efffb7486175c3f01ac89b06ba7293
Branch pushed to git repo; I updated commit sha1. New commits:
effde91 | Add a function add_edge() to FastAutomaton and correct some bugs.
|
comment:42 Changed 5 years ago by
- Commit changed from effde91e40efffb7486175c3f01ac89b06ba7293 to ce640480dddc2395f52001f5a796b503a507014a
comment:43 Changed 5 years ago by
- Commit changed from ce640480dddc2395f52001f5a796b503a507014a to 42b95c530f1b81530fd3b49af3696c1ef3aa13d3
Branch pushed to git repo; I updated commit sha1. New commits:
42b95c5 | Add functions rec_word() and find_word() to FastAutomaton, and modify function is_empty().
|
comment:44 Changed 5 years ago by
- Commit changed from 42b95c530f1b81530fd3b49af3696c1ef3aa13d3 to 7ae36cb1a57564e390102549262a079a02bcd54a
Branch pushed to git repo; I updated commit sha1. New commits:
7ae36cb | Correct some memory bugs.
|
Branch pushed to git repo; I updated commit sha1. New commits:
This is a new branch that permits to have what I've done in ticket 15883 to work with sage 6.2
Idem.