Opened 11 years ago

Closed 8 years ago

#10054 closed defect (fixed)

Provide an alphabet to the parent of any generated word

Reported by: tmonteil Owned by: sage-combinat
Priority: major Milestone: sage-5.9
Component: combinatorics Keywords: days45
Cc: slabbe, abmasse, vdelecroix, saliola Merged in: sage-5.9.beta4
Authors: Travis Scrimshaw Reviewers: Sébastien Labbé
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: #8920 Stopgaps:

Status badges

Description

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.

Attachments (1)

trac_10054-parent_gen_words-ts.patch (27.2 KB) - added by tscrim 8 years ago.

Download all attachments as: .zip

Change History (8)

comment:1 Changed 11 years ago by slabbe

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

comment:2 Changed 10 years ago by abmasse

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

comment:3 Changed 8 years ago by tscrim

  • Authors set to Travis Scrimshaw
  • Keywords days45 added
  • Status changed from new to needs_review

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

comment:4 Changed 8 years ago by tscrim

  • Dependencies set to #8920

Added the dependency.

Changed 8 years ago by tscrim

comment:5 Changed 8 years ago by slabbe

  • Reviewers set to Sébastien Labbé
  • Status changed from needs_review to positive_review

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

Thanks for the doc improvements.

Sébastien

Last edited 8 years ago by slabbe (previous) (diff)

comment:6 Changed 8 years ago by tscrim

Thank you for the review Sebastien.

comment:7 Changed 8 years ago by jdemeyer

  • Merged in set to sage-5.9.beta4
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.