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 mercatp)

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 mercatp

  • Branch set to u/mercatp/beta-adic

comment:2 Changed 6 years ago by git

  • Commit set to 91b1507bfa50a520f0d4601d1306a599a3b3008e

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

037b54dThis is a new branch that permits to have what I've done in ticket 15883 to work with sage 6.2
91b1507Idem.

comment:3 Changed 6 years ago by git

  • Commit changed from 91b1507bfa50a520f0d4601d1306a599a3b3008e to 3e2376d996de554a54dd06fe3b64a0df5886129c

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

3e2376dCorrect a bug of indentation.

comment:4 follow-up: Changed 6 years ago by 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 :(

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 vbraun_spam

  • Milestone changed from sage-6.3 to sage-6.4

comment:6 Changed 6 years ago by git

  • Commit changed from 3e2376d996de554a54dd06fe3b64a0df5886129c to 827d9524f01fc485a274afca6101422e13e6341b

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

b0a8eadAdd a better plotting of automata (new functions plot2 and plot3) using GraphViz.
d7d4455Add a better way to draw a beta-adic monoid (new function plot2) using extern C files.
06e20efAdd 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.
827d952Some 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 mercatp

  • 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 mercatp

  • Type changed from PLEASE CHANGE to enhancement

comment:9 Changed 6 years ago by git

  • Commit changed from 827d9524f01fc485a274afca6101422e13e6341b to 6779b7ea6f90450052f5ad602bc1c2062fe842f1

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

6779b7eCorrect a bug in getBetaAdic2 from sage.monoids.beta_adic_monoid.

comment:10 Changed 6 years ago by git

  • Commit changed from 6779b7ea6f90450052f5ad602bc1c2062fe842f1 to 23ba6f2f9e358a94cace7c962958e6e3fb3ff3b2

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

23ba6f2Permit to set the color of the background independently in plot3 from sage.monoids.beta_adic_monoid

comment:11 Changed 6 years ago by git

  • Commit changed from 23ba6f2f9e358a94cace7c962958e6e3fb3ff3b2 to 4d6e4bd7d9beab60c243a7be8f36c9cb279699b2

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

4d6e4bdAdd the function get_la() to BetaAdicMonoid and correct the doc of plot2 and plot3.

comment:12 Changed 6 years ago by git

  • Commit changed from 4d6e4bd7d9beab60c243a7be8f36c9cb279699b2 to eaf6401181420ae7c6ae45ec054dbe0a089d45b9

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

85f9158Add the extension sage.combinat.words.cautomata.
eaf6401Permit to use sage.combinat.words.cautomata.FastAutomaton to plot a BetaAdicMonoid.

comment:13 Changed 6 years ago by git

  • Commit changed from eaf6401181420ae7c6ae45ec054dbe0a089d45b9 to 350054af54b1028cc03f62c23b7bfa1bd4dddcd5

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

350054aCorrect differents bugs.

comment:14 Changed 6 years ago by git

  • Commit changed from 350054af54b1028cc03f62c23b7bfa1bd4dddcd5 to cd28a7317a3815e7ccc576d3cd1ddb11e81c6311

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

cd28a73Add a new file that I forgot to trac.

comment:15 Changed 6 years ago by git

  • Commit changed from cd28a7317a3815e7ccc576d3cd1ddb11e81c6311 to 718704d5d6f96624430212952a0f48358a5f51d9

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

718704dCorrect a bug in automata_tools.h

comment:16 Changed 6 years ago by git

  • Commit changed from 718704d5d6f96624430212952a0f48358a5f51d9 to 01f1f97c25ea9b6522efa27fd228b774d3d522af

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

01f1f97Add 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 git

  • Commit changed from 01f1f97c25ea9b6522efa27fd228b774d3d522af to ffc1ae2813f89dea4759bd42fbacbee5f0fdd4e1

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

ffc1ae2Add an efficient implementation of Hopcroft's algorithm to minimise a FastAutomaton.

comment:18 Changed 6 years ago by git

  • Commit changed from ffc1ae2813f89dea4759bd42fbacbee5f0fdd4e1 to 7e64c8a8fad6bf5c78ce5378a0b0ff5a2a2ad454

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

acb1f53Avoid tabulation that appears after upgrading from sage 6.2 to sage 6.3
afeab50Merge branch 'u/mercatp/beta-adic' of git://trac.sagemath.org/sage into beta-adic
d5cbb9eMerge branch 'u/mercatp/beta-adic' of git://trac.sagemath.org/sage into beta-adic
b53c93bMerge branch 'u/mercatp/beta-adic' of git://trac.sagemath.org/sage into beta-adic
5119e89Merge branch 'u/mercatp/beta-adic' of git://trac.sagemath.org/sage into beta-adic
39d8fc4Merge branch 'u/mercatp/beta-adic' of git://trac.sagemath.org/sage into beta-adic
4e45a85Merge branch 'u/mercatp/beta-adic' of git://trac.sagemath.org/sage into beta-adic
7e64c8aAdd a new C function to compute relations automaton for algebraic integers. DOESN'T WORK YET !!!

comment:19 Changed 6 years ago by git

  • Commit changed from 7e64c8a8fad6bf5c78ce5378a0b0ff5a2a2ad454 to 9ce37a941f5d47a6d7545e7710c57fef41c335ef

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

9ce37a9Corrects some bugs : now the previous computing of relations automaton using FastAutomaton works.

comment:20 Changed 6 years ago by git

  • Commit changed from 9ce37a941f5d47a6d7545e7710c57fef41c335ef to c18febb7b0763ab055b8c29bec87f1faa39d9974

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

c18febbAdd new functionalities using FastAutomaton : copy, intersection, ... and correct some bugs.

comment:21 Changed 6 years ago by tjolivet

  • Cc tjolivet added

comment:22 Changed 6 years ago by git

  • Commit changed from c18febb7b0763ab055b8c29bec87f1faa39d9974 to 2a6a48d00c99577f090ed3bfb7f884c9c7683809

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

2a6a48dAdd functions has_empty_langage() and equals_langages() to FastAutomaton.

comment:23 Changed 6 years ago by git

  • Commit changed from 2a6a48d00c99577f090ed3bfb7f884c9c7683809 to f256a4beb31200622be7ad9b7f36543a9a379185

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

f256a4bCorrect some little problems with BetaAdicMonoid.relations_automaton3() and others.

comment:24 Changed 6 years ago by git

  • Commit changed from f256a4beb31200622be7ad9b7f36543a9a379185 to 79686e5424206116fa1c4b4207d5133d1b3837cc

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

79686e5Add a function relations_automata2() to BetaAdicMonoid much more efficient than relations_automaton(), and using FastAutomaton.

comment:25 Changed 6 years ago by git

  • Commit changed from 79686e5424206116fa1c4b4207d5133d1b3837cc to 62b55671807b2e74e689fbcf9d280e9dbdb472e4

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

62b5567Add functions is_complete(), complete(), union() and shift() to FastAutomaton. Improve adherence() of BetaAdicMonoid.

comment:26 Changed 6 years ago by git

  • Commit changed from 62b55671807b2e74e689fbcf9d280e9dbdb472e4 to d4449629d0adc2c3a106d6fe6586243a3778c510

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

d444962Add a function move() to BetaAdicMonoid and correct some bugs.

comment:27 Changed 6 years ago by git

  • Commit changed from d4449629d0adc2c3a106d6fe6586243a3778c510 to 8d1a1cbf17de48b3b938ae2a3b0d6b09c904da61

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

8d1a1cbCorrect some little bugs in beta_adic_monoid (with adherence() and initInfoBetaAdic()).

comment:28 Changed 6 years ago by git

  • Commit changed from 8d1a1cbf17de48b3b938ae2a3b0d6b09c904da61 to 4c59b96b6b69286462cc079674e664361cc58759

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

4c59b96Improve the completion of FastAutomaton and add complementaryOP() and test of inclusion : included().

comment:29 Changed 6 years ago by git

  • Commit changed from 4c59b96b6b69286462cc079674e664361cc58759 to 968d02a20da72f146a99718f7dc8fb1c3a986140

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

968d02aAdd functions split(), shift1OP() and unshift1() to FastAutomaton and correct some bugs.

comment:30 Changed 6 years ago by git

  • Commit changed from 968d02a20da72f146a99718f7dc8fb1c3a986140 to 65ba2cedccac8d28ebfe4a588efd98493c91dad8

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

65ba2ceAdd 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 git

  • Commit changed from 65ba2cedccac8d28ebfe4a588efd98493c91dad8 to b590f0e4414e2c118b7974a98396fd9b2c5fdeb1

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

b590f0eCorrect the computing of the extended relation automaton of a beta-adic monoid.

comment:32 Changed 6 years ago by git

  • Commit changed from b590f0e4414e2c118b7974a98396fd9b2c5fdeb1 to ba302836b7699ba2bf92ab2a0004f1e4f67d14bd

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

ba30283Improve 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 git

  • Commit changed from ba302836b7699ba2bf92ab2a0004f1e4f67d14bd to 8efcdea31a4a223341e68145b2aa38adc641d383

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

8efcdeaMerge branch 'master' into t/16723/beta-adic

comment:34 Changed 6 years ago by git

  • Commit changed from 8efcdea31a4a223341e68145b2aa38adc641d383 to fda86b763cf787959ed28bb3966a74145357241e

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

fda86b7Add a function piece to FastAutomaton, add intersection2 and intersect to BetaAdicMonoid

comment:35 Changed 6 years ago by git

  • Commit changed from fda86b763cf787959ed28bb3966a74145357241e to 3af2ddf276557a73b802a7f59f9181cc997aee7c

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

3af2ddfAdd 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 git

  • Commit changed from 3af2ddf276557a73b802a7f59f9181cc997aee7c to b5a7107424f2658442942a71c8579d5928e84109

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

b5a7107Add __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 git

  • Commit changed from b5a7107424f2658442942a71c8579d5928e84109 to e4c62412a0cb6e1eec0f2e6114ba9d096bd37a0b

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

e4c6241Forget to add file src/sage/combinat/words/automataC.c

comment:38 Changed 5 years ago by git

  • Commit changed from e4c62412a0cb6e1eec0f2e6114ba9d096bd37a0b to ae245aaea19057dbe88294cb0c9d8b54905a978e

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

ae245aaAdd a tool to compute relations automata with translation and change a lot of little things.

comment:39 Changed 5 years ago by git

  • Commit changed from ae245aaea19057dbe88294cb0c9d8b54905a978e to 8c1bf8a4083d1dd2fe73ebfbe7de20a469d3b22c

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

8c1bf8aAdd a function move2() that compute the translate ( replace move() ), and correct some problems.

comment:40 Changed 5 years ago by git

  • Commit changed from 8c1bf8a4083d1dd2fe73ebfbe7de20a469d3b22c to a45bb655f48d152a750f0e4a30d445c5bea92593

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

a45bb65Add 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 git

  • Commit changed from a45bb655f48d152a750f0e4a30d445c5bea92593 to effde91e40efffb7486175c3f01ac89b06ba7293

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

effde91Add a function add_edge() to FastAutomaton and correct some bugs.

comment:42 Changed 5 years ago by git

  • Commit changed from effde91e40efffb7486175c3f01ac89b06ba7293 to ce640480dddc2395f52001f5a796b503a507014a

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

2a2c283Add functions shiftOP and unshift, and suppress shift.
ce64048Correct unshift.

comment:43 Changed 5 years ago by git

  • Commit changed from ce640480dddc2395f52001f5a796b503a507014a to 42b95c530f1b81530fd3b49af3696c1ef3aa13d3

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

42b95c5Add functions rec_word() and find_word() to FastAutomaton, and modify function is_empty().

comment:44 Changed 5 years ago by git

  • Commit changed from 42b95c530f1b81530fd3b49af3696c1ef3aa13d3 to 7ae36cb1a57564e390102549262a079a02bcd54a

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

7ae36cbCorrect some memory bugs.
Note: See TracTickets for help on using tickets.