search

sagemath / sage

Main repository of SageMath. Now open for Issues and Pull Requests.
https://www.sagemath.org
Other
1.21k stars 421 forks source link

factors of morphic words #32835

Open videlec opened 2 years ago

videlec commented 2 years ago

Using the prefix-suffix decompositions one can compute the set of factors of a primitive morphic word in close to optimal time. Only checking redundancy of the factors is a subtle task. An efficient way to store the associated language would be to use something similar to the sage.combinat.words.suffix_trees.SuffixTree.

Note : this is already partly availaible in sage.combinat.words.morphism.WordMorphism.language.

CC: @sagetrac-jlepsova @seblabbe

Component: combinatorics

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

videlec commented 2 years ago

Description changed:

--- 
+++ 
@@ -1 +1,3 @@
 Using the prefix-suffix decompositions one can compute the set of factors of a primitive morphic word in close to optimal time. Only checking redundancy of the factors is a subtle task. An efficient way to store the associated language would be to use something similar to the `sage.combinat.words.suffix_trees.SuffixTree`.
+
+Note : this is already partly availaible in `sage.combinat.words.morphism.WordMorphism.language`.