beta-adic

[sagetrac-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.

CC: @sagetrac-tjolivet

Component: PLEASE CHANGE

Branch/Commit: u/mercatp/beta-adic @ 7ae36cb

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

[sagetrac-mercatp]

Branch: u/mercatp/beta-adic

[sagetrac-git]

Commit: 91b1507

[sagetrac-git]

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

037b54d	This is a new branch that permits to have what I've done in ticket 15883 to work with sage 6.2
91b1507	Idem.

[sagetrac-git]

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

3e2376d

Correct a bug of indentation.

[sagetrac-git]

Changed commit from 91b1507 to 3e2376d

[kcrisman]

comment:4

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

[sagetrac-git]

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)

[sagetrac-git]

Changed commit from 3e2376d to 827d952

[sagetrac-mercatp]

comment:7

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.

[sagetrac-git]

Changed commit from 827d952 to 6779b7e

[sagetrac-git]

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

6779b7e

Correct a bug in getBetaAdic2 from sage.monoids.beta_adic_monoid.

[sagetrac-git]

Changed commit from 6779b7e to 23ba6f2

[sagetrac-git]

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

[sagetrac-git]

Changed commit from 23ba6f2 to 4d6e4bd

[sagetrac-git]

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.

[sagetrac-git]

Changed commit from 4d6e4bd to eaf6401

[sagetrac-git]

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

85f9158	Add the extension sage.combinat.words.cautomata.
eaf6401	Permit to use sage.combinat.words.cautomata.FastAutomaton to plot a BetaAdicMonoid.

[sagetrac-git]

Changed commit from eaf6401 to 350054a

[sagetrac-git]

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

350054a

Correct differents bugs.

[sagetrac-git]

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.

[sagetrac-git]

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.

[sagetrac-git]

Changed commit from 65ba2ce to b590f0e

[sagetrac-git]

Changed commit from b590f0e to ba30283

[sagetrac-git]

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.

[sagetrac-git]

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

8efcdea

Merge branch 'master' into t/16723/beta-adic

[sagetrac-git]

Changed commit from ba30283 to 8efcdea

[sagetrac-git]

Changed commit from 8efcdea to fda86b7

[sagetrac-git]

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

fda86b7

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

[sagetrac-git]

Changed commit from fda86b7 to 3af2ddf

[sagetrac-git]

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.

[sagetrac-git]

Changed commit from 3af2ddf to b5a7107

[sagetrac-git]

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.

[sagetrac-git]

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

e4c6241

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

[sagetrac-git]

Changed commit from b5a7107 to e4c6241

[sagetrac-git]

Changed commit from e4c6241 to ae245aa

[sagetrac-git]

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.

[sagetrac-git]

Changed commit from ae245aa to 8c1bf8a

[sagetrac-git]

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.

[sagetrac-git]

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.

[sagetrac-git]

Changed commit from 8c1bf8a to a45bb65

[sagetrac-git]

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

effde91

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

[sagetrac-git]

Changed commit from a45bb65 to effde91

[sagetrac-git]

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

2a2c283	Add functions shiftOP and unshift, and suppress shift.
ce64048	Correct unshift.

[sagetrac-git]

Changed commit from effde91 to ce64048

[sagetrac-git]

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().

[sagetrac-git]

Changed commit from ce64048 to 42b95c5

[sagetrac-git]

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

7ae36cb

Correct some memory bugs.

[sagetrac-git]

Changed commit from 42b95c5 to 7ae36cb