Provide an alphabet to the parent of any generated word

[sagetrac-tmonteil]

The current situation is not uniform, some word generators provide an alphabet to their parent, some other do not. Currently, the policy can be different even for close word generators:

sage: words.LowerMechanicalWord(1/sqrt(2)).parent()
Words
sage: words.CharacteristicSturmianWord(1/sqrt(2)).parent()
Words over Ordered Alphabet [0, 1]

There should be an overall policy (to be discussed in the community).

My point of view is that we should provide a default alphabet each time we know it a priori, so that accessing this info will take a constant time, otherwise the user will sometimes have to use a parsing function that will take a linear time.

Depends on #8920

CC: @seblabbe @sagetrac-abmasse @videlec @saliola

Component: combinatorics

Keywords: days45

Author: Travis Scrimshaw

Reviewer: Sébastien Labbé

Merged: sage-5.9.beta4

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

[seblabbe]

comment:1

I write a useless comment here so that this ticket be listed in the list of Open ticket I participated in.

[sagetrac-abmasse]

comment:2

I checked one by one all the generated words in Sage. They all have parent alphabets except two:

sage: words.CharacteristicSturmianWord(1/sqrt(2)).parent()
Words over Ordered Alphabet [0, 1]
sage: words.ChristoffelWord(4,7).parent()
Words over Ordered Alphabet [0, 1]
sage: words.CodingOfRotationWord(0.1234, 0.5678, alphabet='01').parent()
Words over Ordered Alphabet ['0', '1']
sage: words.FibonacciWord().parent()
Words over Ordered Alphabet [0, 1]
sage: words.FixedPointOfMorphism(WordMorphism('a->ab,b->a'), 'a').parent()
Words over Ordered Alphabet ['a', 'b']
sage: words.KolakoskiWord().parent()
Words over Ordered Alphabet [1, 2]
sage: words.LowerChristoffelWord(4,3).parent()
Words over Ordered Alphabet [0, 1]
sage: words.MinimalSmoothPrefix(20).parent()
Words over Ordered Alphabet [1, 2]
sage: words.PalindromicDefectWord(5, 'ab').parent()
Words over Ordered Alphabet ['a', 'b']
sage: words.RandomWord(15, 3, alphabet='abc').parent()
Words over Ordered Alphabet ['a', 'b', 'c']
sage: words.StandardEpisturmianWord(Words('ab')('ab')).parent()
Words over Ordered Alphabet ['a', 'b']
sage: words.ThueMorseWord().parent()
Words over Ordered Alphabet [0, 1]
sage: words.UpperChristoffelWord(2,3).parent()
Words over Ordered Alphabet [0, 1]
sage: phi = WordMorphism('a->abc,b->ca,c->bb')
sage: words.dual_fibonacci_tile(3).parent()
Word Paths on the square grid
sage: words.fibonacci_tile(3).parent()
Word Paths on the square grid
sage: words.s_adic([phi], 'a').parent()
Words over Ordered Alphabet ['a', 'b', 'c']

These ones should be corrected:

sage: words.LowerMechanicalWord(sqrt(2) - 1).parent()
Words
sage: words.UpperMechanicalWord(sqrt(2) - 1).parent()
Words

Is is the goal of this ticket? Just to correct those two generated words? If so, I can write a patch, but I want to make sure I understand correctly what it is about.

Alex

[tscrim]

Changed keywords from none to days45

[tscrim]

comment:3

Here's a patch which gives the two missing words an alphabet and I've also cleaned up some of the documentation in word_generators.py.

Best,

Travis

[tscrim]

Author: Travis Scrimshaw

[tscrim]

comment:4

Added the dependency.

[tscrim]

Dependencies: #8920

[seblabbe]

comment:5

Attachment: trac_10054-parent_gen_words-ts.patch.gz

All tests pass (failing test on the patchbot are unrelated). Doc builds fine. Positive review.

Thanks for the doc improvements.

Sébastien

[seblabbe]

Reviewer: Sébastien Labbé

[tscrim]

comment:6

Thank you for the review Sebastien.

[jdemeyer]

Merged: sage-5.9.beta4