Re: [sage-combinat-devel] Fwd: [sage-devel] GSOC 2010 proposal
Hi Mike, Hi Carlos, I just answer few words about Automata. We talked with Jean Berstel about it during Sage days 20 and he said that there was a lot of software available around the world for dealing with them. The most general and most active is vaucanson (maintained by Jacques Sakarovitch) which at the same time a software for dealing with Automaton and a latex library. Everything is GPL, written in C++ and available here http://www.infres.enst.fr/~jsaka/PROJ-VAUC/proj-vauc-eng.html We also talked with Sébastien Labbé and Alexandre Blondin-Massé about a class for general languages (which contains regular language). Julien Cassaigne during his two talks gave good ideas for data structure and algorithms for factorial languages arising from substitution... too much work to do in this direction in Sage. Regards Vincent -- You received this message because you are subscribed to the Google Groups "sage-combinat-devel" group. To post to this group, send email to sage-combinat-de...@googlegroups.com. To unsubscribe from this group, send email to sage-combinat-devel+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/sage-combinat-devel?hl=en.
Re: [sage-combinat-devel] Re: Lie Methods and Related Combinatorics
Hi Nicolas, On Tue, Mar 9, 2010 at 5:11 AM, Nicolas M. Thiery wrote: > To summarize, and as was previously vaguely discussed on > http://groups.google.com/group/sage-combinat-devel/msg/18c3926662cf5033, > we would love to aim progressively at: > >sage: sage? # quickref and short index for Sage >sage: sage.tutorial?# A short Sage tutorial + Minh's index > of thematic tutorials > >sage: sage.groups # quickref and short index about group > theory >sage: sage.groups.primer? >sage: sage.groups.tutorial? # The main group theory tutorial + > links to other group theory tutorials > >sage: sage.combinat.crystals? # quickref and short index about > crystals Overall, the above is an excellent proposal for centralizing source code and documentation (reference manual, tutorials, primers). I can imagine that I would want to do sage: sage.groups.tutorial? to get a tutorial on how to use the group theory module. Also, to do sage: sage.groups.primer? to get a primer on the group theory module. That is, inline documentation available from the command line and through the notebook interface. In case this hasn't come up before, I want to now focus on how all these tutorials and primers are to be organized in the HTML version of the standard documentation [1]. Are they to be found in the Reference Manual [2]? Or within a thematic new category such as "Sage HOWTOs" as proposed at #8470 [3]? Since you mentioned the phrase "thematic tutorials" above, I have an urge to borrow (no, steal :-) the phrase and instead rename "Sage HOWTOs" to "Thematic Tutorials". I really like that phrase of yours. > By the way, Jason: can you remind me what's the difference between > 'primer' and 'tutorial'? * primer --- a mini tutorial that should get you started, up and running in a few minutes. * tutorial --- requires about half an hour (or more) to work through. [1] http://www.sagemath.org/doc/ [2] http://www.sagemath.org/doc/reference/ [3] http://trac.sagemath.org/sage_trac/ticket/8470 -- Regards Minh Van Nguyen -- You received this message because you are subscribed to the Google Groups "sage-combinat-devel" group. To post to this group, send email to sage-combinat-de...@googlegroups.com. To unsubscribe from this group, send email to sage-combinat-devel+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/sage-combinat-devel?hl=en.
[sage-combinat-devel] Fwd: [sage-devel] GSOC 2010 proposal
-- Forwarded message -- From: Carlos Eduardo Lopez Camey Date: Mon, Mar 8, 2010 at 11:56 AM Subject: [sage-devel] GSOC 2010 proposal To: sage-de...@googlegroups.com Hello, i read you were applying for GSOC this year. I've gone through the ideas page and found some i could enjoy working on like the Internationalization of the notebook and the notebook itself. Beside those.. do you think it's a good idea to propose Finite Automata support? I'm coursing Languages Design this semester (until June) and doing a Lexical analyzer and parser generator (like lexx & a) as a project written in Scala. I don't know if it's a good idea to propose to write the classes from scratch, or to use a library (like NetworkX with Graph support), recommendations? If I were to write it from scratch, my idea is to write at least Non-deterministic and deterministic Finite Atomata classes: I've seen #4854 from a message on this list and It also occurs to me that they could be built from a Graph. Subset subconstruction algorithm (NFA -> DFA) Direct conversion from regular expressions to DFA Direct conversion from regular expressions to NFA (with different algorithms, which i don't know if it's appropiate: Thompson, Glushkov and I'd like to implement this one as well: http://portal.acm.org/citation.cfm?id=986537.986588) State-minimizing algorithm for DFAs I'm interested in LaTeX support as well, so I could think of embedding Automatas drawn with TikZ/PGF, that of course, as a plus. That is what I got on the top of my head, I'd appreciate if you can tell me what do you think. Regards, Carlos López -- To post to this group, send an email to sage-de...@googlegroups.com To unsubscribe from this group, send an email to sage-devel+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/sage-devel URL: http://www.sagemath.org -- You received this message because you are subscribed to the Google Groups "sage-combinat-devel" group. To post to this group, send email to sage-combinat-de...@googlegroups.com. To unsubscribe from this group, send email to sage-combinat-devel+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/sage-combinat-devel?hl=en.
Re: [sage-combinat-devel] Re: Lie Methods and Related Combinatorics
Dear Dan, Jason, Minh, Sage devs, Please find below a discussion on the appropriate location for tutorials. On Fri, Mar 05, 2010 at 07:12:29AM -0800, bump wrote: > > One question is where should we put those tutorials. During sage days 20, we > > had lost of newcommers to Sage so we started to write several tutorials. We > > Are those tutorials available somewhere now? With the Sage-Combinat patches applied, see: doc/en/talks/sage-combinat-demo.rst doc/en/talks/demo-iterator.py doc/en/demo-NDPF.rst Note that it is very much work in progress. > > discussed a little about where those tutorial should ends into > > sage. One of the main point was that putting them outside sage > > sources make then unaccessible from the command line and ? > > Of course the documentation in the source files is essential. But > although there is adequate documentation in the source files for > someone who knows it is there and wants to dig, you don't get any > sense of how to use the program from the reference manual. > > I think that for Lie group computations, Sage now has adequate tools > for all the typical problems. (If there are gaps, let us fill them.) > But people don't seem to know this. So I wanted to write a > tutorial. A tutorial has a different function from the documentation > in the source files and should be complementary. Yes, yes, yes! We are all for it. Your work on the Lie tutorial is a great addition to Sage's documentation. And +1 also for a good and well advertised index of those tutorials like Minh is preparing. Florent's point (and mine) though is that we would rather have those tutorials live *within* the Sage sources, rather than in separate directories / documents. The rationale is that this makes them directly accessible through the online/introspection help, which is a highly desirable feature. Try, e.g.: sage: sage.categories? sage: sage.categories.primer? sage: sage.combinat? sage: sage.combinat.root_system? In particular, the above mentioned tutorials should probably be accessible from: sage: sage.combinat.tutorial? sage: sage.combinat.tutorial_iterators? This will be particularly powerful once the notebook inline help will include a link to the corresponding live documentation (see http://groups.google.com/group/sage-devel/msg/670d3392c3b6743f; I need to create a ticket for this). Another nice feature is that this keeps physically close all the material on a given theme. Hence, someone browsing trough the combinat sources will stumble on the combinatorics tutorial. Also, running: sage -t sage/combinat does check the combinatorics tutorial. To summarize, and as was previously vaguely discussed on http://groups.google.com/group/sage-combinat-devel/msg/18c3926662cf5033, we would love to aim progressively at: sage: sage? # quickref and short index for Sage sage: sage.tutorial?# A short Sage tutorial + Minh's index of thematic tutorials sage: sage.groups # quickref and short index about group theory sage: sage.groups.primer? sage: sage.groups.tutorial? # The main group theory tutorial + links to other group theory tutorials sage: sage.combinat.crystals? # quickref and short index about crystals By the way, Jason: can you remind me what's the difference between 'primer' and 'tutorial'? I remember one was meant to be doable in a couple minutes, and the other in, say, half an hour, but can't recall which is which. That being said, it might be a bit tricky to find a natural spot for cross-themes tutorials like Dan's. Should it be accessible through: sage: sage.tutorial_lie? Best regards, Nicolas -- Nicolas M. Thiéry "Isil" http://Nicolas.Thiery.name/ -- You received this message because you are subscribed to the Google Groups "sage-combinat-devel" group. To post to this group, send email to sage-combinat-de...@googlegroups.com. To unsubscribe from this group, send email to sage-combinat-devel+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/sage-combinat-devel?hl=en.
Re: [sage-combinat-devel] WordMorphismExtension, vocabulary ang global namespace
Hi, >> {{{ >> sage: e = WordMorphismExtensionDual('a->ab,b->ac,c->a') >> sage: e >> E*(WordMorphism: a->ab, b->ac, c->a) >> sage: f1 = Face((0,0,0),1) # the face 1 or a at (0,0,0) >> sage: f2 = Face((0,0,0),2) # the face 2 or b at (0,0,0) >> sage: f3 = Face((0,0,0),3) # the face 3 or c at (0,0,0) >> sage: e(f1) # the image of f1 >> Patch([((0, 1, -1), 2), ((1, 0, -1), 1), ((0, 0, 0), 3)]) >> sage: e(f2) # the image of f2 >> Patch([((0, 0, 0), 1)]) >> sage: e(f3) # the image of f3 >> Patch([((0, 0, 0), 2)]) >> }}} Instead of adding WordMorphismExtensionDual to the namespace, I prefer the following : sage: m = WordMorphism('a->ab,b->ac,c->a') sage: e = e.extension_dual() sage: e Extension dual of WordMorphism: a->ab, b->ac, c->a >> And one can iterates and this is the way we obtain our beautiful >> pictures (is there a standard for the option iterations ?) >> {{{ >> sage: e(f1,iterations=5) >> Patch([((1, -3, 4), 1), ((0, -1, 2), 3), ((1, -1, 1), 1), ((-1, -1, >> 4), 2), ((0, -1, 2), 1), ((1, -3, 3), 3), ((-1, -1, 4), 3), ((1, -2, >> 2), 2), ((1, -1, 0), 1), ((2, -2, 0), 1), ((1, -3, 3), 1), ((0, -2, >> 4), 2), ((0, -3, 5), 3), ((2, -2, 1), 1), ((-1, 0, 2), 2), ((0, 0, 1), >> 2), ((0, -1, 2), 2), ((0, -2, 4), 3), ((2, -3, 1), 1), ((1, -2, 3), >> 1), ((1, -1, 1), 2), ((0, 0, 0), 2), ((1, -2, 2), 3), ((0, -1, 3), 2), >> ((1, -2, 2), 1), ((2, -3, 2), 1), ((-1, -2, 5), 3), ((0, -1, 3), 1), >> ((1, -1, 0), 2), ((-1, 0, 3), 2), ((0, -2, 4), 1)]) >> }}} Right now, with word morphism, one can do either of the following sage: m = WordMorphism('a->ab,b->ac,c->a') sage: (m^5)('a') word: abacabaabacababacabaabac sage: m('a', 5) word: abacabaabacababacabaabac You obtain the fixed point using : sage: m('a', oo) word: abacabaabacababacabaabacabacabaabacababa... Hence, you could follow the same idea : sage: (e^5)(f1) A patch ... sage: e(f1, 5) A patch ... sage: e(f1, oo) The limit fractal! Does the name of "patch" is really used by Arnoux, Ito? Or is it Franco who used that name? Instead of patch, I would use another name that evoques a little bit more the idea of a finite domain of a discrete plane. So why not, "finite domain of a discrete plane" which says what it is!? > Thanks! So, somehow, e is a function from the set of patches to > itself, right? I have no clue on the subject, so this might be > completely silly, but what about: > > {{{ > sage: Patches = e.codomain() # or e.domain()? > }}} > > ``patches`` would be a parent modeling the collection of all > patches. And then, one could do things like: > > {{{ > sage: f1 = Patches.face((0,0,0),1) # builds a face > sage: p = Patches( ( ((0,0,0),1), ((0,0,0),2) ) ) # builds a patch from an > iterable of face-data > }}} +1 : I agree with the ideas of Nicolas After speaking with Timo (now in Montpellier), I think the extension (before taking the dual) of word morphism corresponds to something I use quite often for example to construct a Christoffel Tile : sage: P = WordPaths('abAB') sage: P Word Paths on the square grid sage: P.letters_to_steps() {'a': (1, 0), 'A': (-1, 0), 'B': (0, -1), 'b': (0, 1)} sage: L = WordMorphism('a->aBab,b->ab,A->AbAB,B->AB', codomain=P) sage: bar = WordMorphism('a->A,b->B,A->a,B->b', codomain=P) sage: w = P(words.ChristoffelWord(5,8, alphabet='ab')) sage: L(w*bar(w)).plot(endarrow=False) Maybe it can be usefull ... Sébastien -- You received this message because you are subscribed to the Google Groups "sage-combinat-devel" group. To post to this group, send email to sage-combinat-de...@googlegroups.com. To unsubscribe from this group, send email to sage-combinat-devel+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/sage-combinat-devel?hl=en.
[sage-combinat-devel] Re: One test fails when applying trac_8276-MatrixSpace_one-fh.patch
Never mind this post, this is probably due to the fact that some of the patches of #8276 are not available on sage-combinat. Sorry about having doubts, Florent ! Alex ablondin a écrit : > Hello everyone and in particular Florent ! > While testing all sage for a patch of Sébastien that modifies a lot of > files, I noticed that one test didn't pass, which seemed unrelated to > Sébastien's modifications. If I'm not mistaken, that would be > trac_8276-MatrixSpace_one-fh.patch. Since it seems also unrelated to > any matrix (so that it seems to be a side effect), I prefered to warn > you. Here's what I got. > > sage -t "local/lib/python2.6/site-packages/sagenb-0.7.5-py2.6.egg/ > sagenb/misc/sageinspect.py" > ** > File "/Users/alexandre/Applications/sage/local/lib/python2.6/site- > packages/sagenb-0.7.5-py2.6.egg/sagenb/misc/sageinspect.py", line 562: > sage: sage_getsourcelines(matrix, True)[1] > Expected: > 33 > Got: > 34 > ** > 1 items had failures: >1 of 5 in __main__.example_10 > > Thank you ! > Alexandre -- You received this message because you are subscribed to the Google Groups "sage-combinat-devel" group. To post to this group, send email to sage-combinat-de...@googlegroups.com. To unsubscribe from this group, send email to sage-combinat-devel+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/sage-combinat-devel?hl=en.
Re: [sage-combinat-devel] WordMorphismExtension, vocabulary ang global namespace
On Mon, Mar 08, 2010 at 11:29:16AM +0100, Vincent Delecroix wrote: > > > > Can you give here some typical use cases for those? > > > > Here it is (in fact the dual morphism operates more on patches than on > faces because the image of a face is a patch and not a face) > > {{{ > sage: e = WordMorphismExtensionDual('a->ab,b->ac,c->a') > sage: e > E*(WordMorphism: a->ab, b->ac, c->a) > sage: f1 = Face((0,0,0),1) # the face 1 or a at (0,0,0) > sage: f2 = Face((0,0,0),2) # the face 2 or b at (0,0,0) > sage: f3 = Face((0,0,0),3) # the face 3 or c at (0,0,0) > sage: e(f1) # the image of f1 > Patch([((0, 1, -1), 2), ((1, 0, -1), 1), ((0, 0, 0), 3)]) > sage: e(f2) # the image of f2 > Patch([((0, 0, 0), 1)]) > sage: e(f3) # the image of f3 > Patch([((0, 0, 0), 2)]) > }}} > > And one can iterates and this is the way we obtain our beautiful > pictures (is there a standard for the option iterations ?) > {{{ > sage: e(f1,iterations=5) > Patch([((1, -3, 4), 1), ((0, -1, 2), 3), ((1, -1, 1), 1), ((-1, -1, > 4), 2), ((0, -1, 2), 1), ((1, -3, 3), 3), ((-1, -1, 4), 3), ((1, -2, > 2), 2), ((1, -1, 0), 1), ((2, -2, 0), 1), ((1, -3, 3), 1), ((0, -2, > 4), 2), ((0, -3, 5), 3), ((2, -2, 1), 1), ((-1, 0, 2), 2), ((0, 0, 1), > 2), ((0, -1, 2), 2), ((0, -2, 4), 3), ((2, -3, 1), 1), ((1, -2, 3), > 1), ((1, -1, 1), 2), ((0, 0, 0), 2), ((1, -2, 2), 3), ((0, -1, 3), 2), > ((1, -2, 2), 1), ((2, -3, 2), 1), ((-1, -2, 5), 3), ((0, -1, 3), 1), > ((1, -1, 0), 2), ((-1, 0, 3), 2), ((0, -2, 4), 1)]) > }}} Thanks! So, somehow, e is a function from the set of patches to itself, right? I have no clue on the subject, so this might be completely silly, but what about: {{{ sage: Patches = e.codomain() # or e.domain()? }}} ``patches`` would be a parent modeling the collection of all patches. And then, one could do things like: {{{ sage: f1 = Patches.face((0,0,0),1) # builds a face sage: p = Patches( ( ((0,0,0),1), ((0,0,0),2) ) ) # builds a patch from an iterable of face-data }}} Cheers, Nicolas -- Nicolas M. Thiéry "Isil" http://Nicolas.Thiery.name/ -- You received this message because you are subscribed to the Google Groups "sage-combinat-devel" group. To post to this group, send email to sage-combinat-de...@googlegroups.com. To unsubscribe from this group, send email to sage-combinat-devel+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/sage-combinat-devel?hl=en.
Re: [sage-combinat-devel] schensted insertion
Dear Dan, Paul-Olivier, Pedro, On Sat, Mar 06, 2010 at 06:32:11PM -0500, Paul-Olivier Dehaye wrote: > On Sat, Mar 6, 2010 at 3:07 PM, Pedro Sanchez wrote: > > On Sat, Mar 6, 2010 at 11:08 AM, bump wrote: > >> > >> Tableau method contains two methods, bump and schensted_insert. > >> > >> I think these are equivalent. That is, I was unable to find case where > >> T.bump(i) and T.schensted_insert(i) produced different output. > >> > >> Am I missing something? > >> > >> Dan > > > > T.schensted_insert() allows for both left or right insertion (that is, row > > bumping or column bumping) > > > > T.schensted_insert() is a wrapper as its code shows: > > > > if left: > > return self._left_schensted_insert(i) > > else: > > return self._right_schensted_insert(i) > > > > > > On the other hand "bump" only codes row-bumping (right insertion) so "bump" > > is less useful. > > > > I compared > > T.bump() code with T._right_schensted_insert() > > and yes, it seems both do the same, although in different ways > > consider also the code in > sage: Permutation([6,2,3,1,7,5,4]).robinson_schensted() > which performs insertions (and more). Mike Hansen added it, it bisects > per row, and is thus be much faster for large partitions. > > in any case there should really be a function called T.bump()! Thanks for spotting this duplication! Please someone fix it by implement a single low-level method concentrating all the algorithmic: T._right_schensted_insert_word(iterable) using whichever implementation is best (bisection I guess), and have all the others (T.bump, T.schensted_insert, T.insert_word, P.robinson_schensted) call it. The same should be done for column insertion (but the bisection trick might not be applicable). Technical question: is it faster to insert a bunch of letters at once? Algorithmically, it is not; but this is the main use case, and the overhead of repeatedly calling the schensted insertion function on each letter, one by one may, or may not, be relevant. In the above, I assumed the answer was yes. If not, it is best to stick with T._right_schensted_insert(letter) as low-level method, with all the other methods calling it. The user interface could take some polishing at that occasion; for example, some of those methods could be deprecated, and maybe the names improved for more consistency. I am absolutely no expert on that, so please see for the best. For the record, here is the corresponding doc in MuPAD-Combinat: http://mupad-combinat.sourceforge.net/doc/en/combinat/tableaux.html Thanks much in advance! Cheers, Nicolas -- Nicolas M. Thiéry "Isil" http://Nicolas.Thiery.name/ -- You received this message because you are subscribed to the Google Groups "sage-combinat-devel" group. To post to this group, send email to sage-combinat-de...@googlegroups.com. To unsubscribe from this group, send email to sage-combinat-devel+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/sage-combinat-devel?hl=en.
Re: [sage-combinat-devel] WordMorphismExtension, vocabulary ang global namespace
> > Can you give here some typical use cases for those? > Here it is (in fact the dual morphism operates more on patches than on faces because the image of a face is a patch and not a face) {{{ sage: e = WordMorphismExtensionDual('a->ab,b->ac,c->a') sage: e E*(WordMorphism: a->ab, b->ac, c->a) sage: f1 = Face((0,0,0),1) # the face 1 or a at (0,0,0) sage: f2 = Face((0,0,0),2) # the face 2 or b at (0,0,0) sage: f3 = Face((0,0,0),3) # the face 3 or c at (0,0,0) sage: e(f1) # the image of f1 Patch([((0, 1, -1), 2), ((1, 0, -1), 1), ((0, 0, 0), 3)]) sage: e(f2) # the image of f2 Patch([((0, 0, 0), 1)]) sage: e(f3) # the image of f3 Patch([((0, 0, 0), 2)]) }}} And one can iterates and this is the way we obtain our beautiful pictures (is there a standard for the option iterations ?) {{{ sage: e(f1,iterations=5) Patch([((1, -3, 4), 1), ((0, -1, 2), 3), ((1, -1, 1), 1), ((-1, -1, 4), 2), ((0, -1, 2), 1), ((1, -3, 3), 3), ((-1, -1, 4), 3), ((1, -2, 2), 2), ((1, -1, 0), 1), ((2, -2, 0), 1), ((1, -3, 3), 1), ((0, -2, 4), 2), ((0, -3, 5), 3), ((2, -2, 1), 1), ((-1, 0, 2), 2), ((0, 0, 1), 2), ((0, -1, 2), 2), ((0, -2, 4), 3), ((2, -3, 1), 1), ((1, -2, 3), 1), ((1, -1, 1), 2), ((0, 0, 0), 2), ((1, -2, 2), 3), ((0, -1, 3), 2), ((1, -2, 2), 1), ((2, -3, 2), 1), ((-1, -2, 5), 3), ((0, -1, 3), 1), ((1, -1, 0), 2), ((-1, 0, 3), 2), ((0, -2, 4), 1)]) }}} Cheers, Vincent -- You received this message because you are subscribed to the Google Groups "sage-combinat-devel" group. To post to this group, send email to sage-combinat-de...@googlegroups.com. To unsubscribe from this group, send email to sage-combinat-devel+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/sage-combinat-devel?hl=en.
Re: [sage-combinat-devel] WordMorphismExtension, vocabulary ang global namespace
On Sun, Mar 07, 2010 at 01:23:22PM +0100, Vincent Delecroix wrote: > With Stepan and Timo we start this week to work on > WordMorphismExtensions starting from the code of Franco (thank you > Franco). The code is in sage-combinat and works almost well. There is > also an opened ticket #8431 relating this feature. Cool! > There are important problems > * we put in the global namespace object such as Face and Patch. This > operation is quite bad because the names are generic and our work is > specialized. A Face is just an 'colored vector' : an element of the > cartesian product (Z^d x {1,...,d}) where d is the size of the > (ordered) alphabet. A Patch is a collection a faces. A > WordMorphismExtensionDual operates on Face (and on Patch by > extension). Do you have a solution between user friendly and > consistance (ColoredVector and ColoredVectorSet are consistant but not > user friendly) ? I think about calling the constructor inside the > extension morphism (e.face(...)) but this solution does not convince > me. Can you give here some typical use cases for those? Cheers, Nicolas -- Nicolas M. Thiéry "Isil" http://Nicolas.Thiery.name/ -- You received this message because you are subscribed to the Google Groups "sage-combinat-devel" group. To post to this group, send email to sage-combinat-de...@googlegroups.com. To unsubscribe from this group, send email to sage-combinat-devel+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/sage-combinat-devel?hl=en.