beta-adic

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

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

[git]

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

​3e2376d

Correct a bug of indentation.

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

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

[mercatp]

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.

[git]

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

​6779b7e

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

[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

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

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

[git]

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

​350054a

Correct differents bugs.

[git]

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

​cd28a73

Add a new file that I forgot to trac.

[git]

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

​718704d

Correct a bug in automata_tools.h

[git]

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

[git]

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

​ffc1ae2

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

[git]

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 !!!

[git]

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.

[git]

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

​c18febb

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

[git]

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

​2a6a48d

Add functions has_empty_langage() and equals_langages() to FastAutomaton.

[git]

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

​f256a4b

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

[git]

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.

[git]

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.

[git]

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

​d444962

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

[git]

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

​8d1a1cb

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

[git]

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

[git]

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

​968d02a

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

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

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

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

[git]

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

​8efcdea

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

[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

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

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

[git]

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

​e4c6241

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

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

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

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

[git]

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

​effde91

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

[git]

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

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

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

[git]

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

​7ae36cb

Correct some memory bugs.