search

sagemath / sage

Main repository of SageMath
https://www.sagemath.org
Other
1.44k stars 481 forks source link

beta-adic #16723

Open c165f187-4f33-4a54-8b5c-49666d3fe91f opened 10 years ago

c165f187-4f33-4a54-8b5c-49666d3fe91f commented 10 years ago

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

c165f187-4f33-4a54-8b5c-49666d3fe91f commented 10 years ago

Branch: u/mercatp/beta-adic

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 10 years ago

Commit: 91b1507

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 10 years ago

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.
7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 10 years ago

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

3e2376dCorrect a bug of indentation.
7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 10 years ago

Changed commit from 91b1507 to 3e2376d

kcrisman commented 10 years ago
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.)

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 10 years ago

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)
7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 10 years ago

Changed commit from 3e2376d to 827d952

c165f187-4f33-4a54-8b5c-49666d3fe91f commented 10 years ago
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.

c165f187-4f33-4a54-8b5c-49666d3fe91f commented 10 years ago

Description changed:

--- 
+++ 
@@ -1 +1,4 @@
+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.
7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 10 years ago

Changed commit from 827d952 to 6779b7e

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 10 years ago

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

6779b7eCorrect a bug in getBetaAdic2 from sage.monoids.beta_adic_monoid.
7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 10 years ago

Changed commit from 6779b7e to 23ba6f2

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 10 years ago

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
7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 10 years ago

Changed commit from 23ba6f2 to 4d6e4bd

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 10 years ago

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.
7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 10 years ago

Changed commit from 4d6e4bd to eaf6401

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 10 years ago

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.
7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 10 years ago

Changed commit from eaf6401 to 350054a

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 10 years ago

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

350054aCorrect differents bugs.
7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 10 years ago

Changed commit from 350054a to cd28a73

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 10 years ago

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

cd28a73Add a new file that I forgot to trac.
7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 10 years ago

Changed commit from cd28a73 to 718704d

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 10 years ago

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

718704dCorrect a bug in automata_tools.h
7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 10 years ago

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).
7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 10 years ago

Changed commit from 718704d to 01f1f97

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 10 years ago

Changed commit from 01f1f97 to ffc1ae2

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 10 years ago

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

ffc1ae2Add an efficient implementation of Hopcroft's algorithm to minimise a FastAutomaton.
7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 10 years ago

Changed commit from ffc1ae2 to 7e64c8a

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 10 years ago

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 !!!
7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 10 years ago

Changed commit from 7e64c8a to 9ce37a9

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 10 years ago

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

9ce37a9Corrects some bugs : now the previous computing of relations automaton using FastAutomaton works.
7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 10 years ago

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

c18febbAdd new functionalities using FastAutomaton : copy, intersection, ... and correct some bugs.
7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 10 years ago

Changed commit from 9ce37a9 to c18febb

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 10 years ago

Changed commit from c18febb to 2a6a48d

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 10 years ago

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

2a6a48dAdd functions has_empty_langage() and equals_langages() to FastAutomaton.
7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 10 years ago

Changed commit from 2a6a48d to f256a4b

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 10 years ago

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

f256a4bCorrect some little problems with BetaAdicMonoid.relations_automaton3() and others.
7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 10 years ago

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.
7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 10 years ago

Changed commit from f256a4b to 79686e5

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 10 years ago

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.
7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 10 years ago

Changed commit from 79686e5 to 62b5567

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 10 years ago

Changed commit from 62b5567 to d444962

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 10 years ago

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

d444962Add a function move() to BetaAdicMonoid and correct some bugs.
7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 10 years ago

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

8d1a1cbCorrect some little bugs in beta_adic_monoid (with adherence() and initInfoBetaAdic()).
7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 10 years ago

Changed commit from d444962 to 8d1a1cb

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 10 years ago

Changed commit from 8d1a1cb to 4c59b96

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 10 years ago

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

4c59b96Improve the completion of FastAutomaton and add complementaryOP() and test of inclusion : included().
7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 9 years ago

Changed commit from 4c59b96 to 968d02a

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 9 years ago

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

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