Opened 7 years ago
Last modified 5 years ago
#16723 new enhancement
betaadic
Reported by:  mercatp  Owned by:  mercatp 

Priority:  minor  Milestone:  sagefeature 
Component:  PLEASE CHANGE  Keywords:  
Cc:  tjolivet  Merged in:  
Authors:  Reviewers:  
Report Upstream:  N/A  Work issues:  
Branch:  u/mercatp/betaadic (Commits)  Commit:  7ae36cb1a57564e390102549262a079a02bcd54a 
Dependencies:  Stopgaps: 
Description (last modified by )
This ticket gives a implementation of betaadic monoids, as described in the article http://www.latp.univmrs.fr/~paul.mercat/Publis/Semigroupes%20fortement%20automatiques.pdf It permit to compute the betaadic monoid corresponding to a WordMorphism?, to draw limit sets of betaadic monoid, to compute relations automaton and reduced words automaton (defined in the article). For that I reimplemented 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/betaadic
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 followup: ↓ 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 betaadics 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 betaadic 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 sage6.3 to sage6.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 betaadic 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 sage6.4 to sagefeature
 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 betaadics 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 betaexpansion, rauzy fractals, quasicristals 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 betaadic which seem to mean something else (though with "adic" of course they are somehow related).
There are several names for that : betaadic, betaexpansions, nonstandard 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 oct2010...
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 sage6.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/betaadic' of git://trac.sagemath.org/sage into betaadic

d5cbb9e  Merge branch 'u/mercatp/betaadic' of git://trac.sagemath.org/sage into betaadic

b53c93b  Merge branch 'u/mercatp/betaadic' of git://trac.sagemath.org/sage into betaadic

5119e89  Merge branch 'u/mercatp/betaadic' of git://trac.sagemath.org/sage into betaadic

39d8fc4  Merge branch 'u/mercatp/betaadic' of git://trac.sagemath.org/sage into betaadic

4e45a85  Merge branch 'u/mercatp/betaadic' of git://trac.sagemath.org/sage into betaadic

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 nondeterministic automata, and add a transposition of deterministic automaton (that gives a nondeterministic 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 betaadic 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/betaadic

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 selfsimilar 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.