I found my copy of "Free Lie Algebras" by
Christophe Reutenauer and it is clearer in that
reference that you are correct that the empty
word is not considered Lyndon.
-Mike
On Dec 30, 2007, at 6:48 PM, Xavier Molinero wrote:
> Hi Mike,
>
> =46rom the beginning, the empty word has not been considered in
> cycles/necklaces and Lyndown words (aperiodic necklaces).
> The attached file shows such definitions with the corresponding =20
> formulas
> (Formulas.pdf) from
> http://www.theory.csc.uvic.ca/~cos/inf/neck/NecklaceInfo.html
>
> Thus, the empty "Cycle"/"Necklace"/"Lyndown word" do not exist and
>
> dom::count([])
>
> should be 0.
>
> Best,
> Xavier
>
> Nicolas M. Thiery escribi=F3:
>
>> Hi Mike,
>>
>>
>>> It looks like I changed something on my lyndonWords file which is
>>> why it was broken.
>>> I reverted the file and it worked fine afterwards.
>>>
>>
>> Ok.
>>
>>
>>> I am going to commit some changes but I have some questions
>>> about Lyndon words and the implementation in MuPAD.
>>> 1) is the empty word Lyndon?
>>> if so, then shouldn't
>>> combinat::lyndonWords::fromEvaluation::count([])
>>> be 1?
>>> http://www.research.att.com/~njas/sequences/A000031
>>> The formula fails to be useful, but one must assume
>>> a convention and I have implemented dom::isA([]) is TRUE
>>> but this contradicts dom::count([])
>>>
>>
>> Honestly, I don't remember the rationale (if any) for this
>> choice. This question has popped up in the past (and also for
>> necklaces), with no serious answer. See for example:
>>
>> http://sourceforge.net/mailarchive/message.php?=20
>> msg_id=3D20040714080801.GB5629%40eole.rouba.net
>>
>>>> Nicolas:
>>>> Does anybody care about the default value for the minimal length of
>>>> cycles? Right now, the default is zero, which is coherent with >
>>>> Multiset/Powerset/Sequence. On the other hand it seems that taking
>>>> a > minimal length of 1 for Cycles is more standard in the
>>>> community, > and is a little bit more coherent when looking at the
>>>> generating > series.
>>>>
>>
>> Anyone suggestions? Conrado? Xavier?
>>
>> So: please make your investigation, take the right choice (as you =
say,
>> this is mostly conventional, but being compatible with generating
>> series is a good sign), and fix the code in lyndonWords and necklaces
>> accordingly. I assume this should not break much other things.
>>
>>
>>> 2) should lyndonWords be a sub-domain of words?
>>> Why have a whole domain of lyndonWords for 3 functions (i.e. isA, =20=
>>> count, list)?
>>>
>>
>> Well, there may be more functions in the future. Anyway, we do not =
yet
>> have a good systematic policy for the hierarchy structure of our
>> combinatorial domains. This has been discussed (see e.g. the wiki,
>> Specifications -> Tableaux). Further ideas are welcome. In the mean
>> time it's not worth moving things around, and a flat structure is not
>> so bad anyway.
>>
>>
>>> 3) Why is everything in the lyndonWords (apart from the =20
>>> ::fromEvaluation
>>> or ::fromContent part) not implemented?
>>>
>>
>> No one needed it I guess.
>>
>>
>>> I would think that
>>> combinat::lyndonWords::count([1,2,3],4);
>>> is easier to calculate than the same functions for ::fromEvaluation.
>>> Isn't the formula:
>>> a(n) =3D (1/n)*Sum_{ d divides n } phi(d)*k^(n/d) ?
>>>
>>
>> I don't remember by heart, but yes, this should be something like
>> this. Note that the formula in fromEvaluation is nothing but a
>> multivariate refinement of this.
>>
>> Similarly, I expect it to be easier to generate lyndon words and
>> necklaces by alphabet (but since we have a Constant Amortized Time
>> algorithm for those by evaluation, we can also just reuse it).
>>
>> Best,
>> Nicolas
>>
>
> <Formulas.pdf>=
|