Opened 11 years ago

Last modified 8 years ago

#12225 new enhancement

Finite and lazy factorial languages

Reported by: vdelecroix Owned by: vdelecroix
Priority: major Milestone: sage-6.4
Component: combinatorics Keywords: word, factorial language, symbolic dynamics
Cc: sstarosta, slabbe, tmonteil Merged in:
Authors: Vincent Delecroix Reviewers:
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: #12224 Stopgaps:

Status badges

Description (last modified by vdelecroix)

1) Implement a data structure (similar to a tree with label on edges) for finite factorial language which extends the actual SuffixTrie? and SuffixTree? in sage/combinat/words/suffix_tree.py (a "RauzyCastle?").

2.a) Use it in a static version for the implementation of finite factorial language

2.b) Use it in a dynamical version for the implementation of some lazy languages (square free, cube free, overlap free, finite defect, ...)

see also: #12224, #12227

Change History (9)

comment:1 Changed 11 years ago by vdelecroix

  • Dependencies set to #12224
  • Description modified (diff)
  • Owner changed from Vincent Delecroix to vdelecroix
  • Summary changed from Finite and some lazy factorial language to Finite and lazy factorial languages

comment:2 follow-ups: Changed 11 years ago by slabbe

Nice ticket!

Related to this, I want to add that I want to remove the class and the file nfactor_enumerable_word from Sage. Currently, only Finite Word class inherits from it. So it would be easy to fix by just moving the methods to the Finite Word class. I am sorry for having introduced this class into Sage : it was an error. This job must be done inside of the appropriate Language class... I still haven't created the ticket for it, but I definitively will.

Sébastien

comment:3 in reply to: ↑ 2 ; follow-up: Changed 11 years ago by vdelecroix

Hi Sebastien,

Nice ticket!

Thanks! It now needs work!

Related to this, I want to add that I want to remove the class and the file nfactor_enumerable_word from Sage. Currently, only Finite Word class inherits from it. So it would be easy to fix by just moving the methods to the Finite Word class. I am sorry for having introduced this class into Sage : it was an error. This job must be done inside of the appropriate Language class... I still haven't created the ticket for it, but I definitively will.

I have some patch almost ready for it. It is just an update of suffix_trie into a prefix_suffix_trie. The data structure I used is perhaps not optimal (many dictionnaries that points toward other dictionnaries). It would be very nice to have a low-level implementation as the one used in Graph as well as a sparse and a dense version (certainly another ticket).

Before submitting a patch, I want to fix #12224 (Use Parent/Element? and GradedEnumeratedSets? for Language).

I have a questions for you : do we remove suffix_trie and use this new class instead ? (I made some timings and it seems that mine is twice slower, which is not so good or not so bad) Anyway, if yes, it is for another ticket.

comment:4 in reply to: ↑ 3 Changed 11 years ago by slabbe

Nice ticket!

Thanks! It now needs work!

Indeed...

I have some patch almost ready for it. It is just an update of suffix_trie into a prefix_suffix_trie. The data structure I used is perhaps not optimal (many dictionnaries that points toward other dictionnaries). It would be very nice to have a low-level implementation as the one used in Graph as well as a sparse and a dense version (certainly another ticket).

I once rewrote the code of suffix_tree and was able to improve timing (something like 40%) just by choosing better data structures (dict instead of list or vice versa). My patches does not apply anymore because of conflicts but it is here : http://sage.math.washington.edu/home/slabbe/patches/ (starts with suffix_something). I did not push it any further, because I wanted instead to rewrite suffix tree code in cython, which we did for the suffix tree. But this construction is quadratic in the length of the (finite) word, and I want it to be linear. So, my next step was to implement the suffix_trie in cython, but I never did...

Before submitting a patch, I want to fix #12224 (Use Parent/Element? and GradedEnumeratedSets? for Language).

I have a questions for you : do we remove suffix_trie and use this new class instead ? (I made some timings and it seems that mine is twice slower, which is not so good or not so bad) Anyway, if yes, it is for another ticket.

Well, I would say not to delete it first. Just add a new implementation beside it. And, for some time, one could choose the algorithm or implementation. Later, we could delete the initial implementation.

sage: w.factors(algorithm="first slow python implementation")
sage: w.factors(algorithm="cython implementation")

Sébastien

comment:5 in reply to: ↑ 2 Changed 11 years ago by slabbe

Related to this, I want to add that I want to remove the class and the file nfactor_enumerable_word from Sage.

This is now : #12380

comment:6 Changed 9 years ago by jdemeyer

  • Milestone changed from sage-5.11 to sage-5.12

comment:7 Changed 9 years ago by vbraun_spam

  • Milestone changed from sage-6.1 to sage-6.2

comment:8 Changed 8 years ago by vbraun_spam

  • Milestone changed from sage-6.2 to sage-6.3

comment:9 Changed 8 years ago by vbraun_spam

  • Milestone changed from sage-6.3 to sage-6.4
Note: See TracTickets for help on using tickets.