Timeline for "Nyldon words": understanding a class of words factorizing the free monoid increasingly
Current License: CC BY-SA 4.0
26 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jan 31, 2019 at 20:33 | history | edited | darij grinberg | CC BY-SA 4.0 |
deleted 17 characters in body
|
| Jan 31, 2019 at 18:20 | vote | accept | darij grinberg | ||
| Jan 31, 2019 at 18:13 | answer | added | Manon Stipulanti | timeline score: 9 | |
| Nov 29, 2014 at 15:12 | answer | added | Wolfgang | timeline score: 0 | |
| Nov 21, 2014 at 21:49 | answer | added | user38477 | timeline score: 6 | |
| Nov 21, 2014 at 13:38 | comment | added | Ilya Bogdanov | @Wolfgang: But a Nyldon word may start with a square, as 1011010 does. Perhaps, we should excludr not all squares? | |
| Nov 21, 2014 at 13:27 | comment | added | Wolfgang | It is well known that for a given necklace, its Lyndon representative is the alphabetically smallest of all the cyclic shifts. Is it possible that, if there is a Nyldon representative for a given necklace (still iffy), it is the biggest one in alphabetical order, but excluding all the shifts starting with a square? e.g. 2120221>2022121, excluding 2212120 and 2121202. | |
| Nov 21, 2014 at 8:02 | comment | added | Ilya Bogdanov | I do not see that Nyldon words are pattern avoiding. E.g., $101101010\dots10$ is a Nyldon word. | |
| Nov 21, 2014 at 4:22 | comment | added | darij grinberg | @GjergjiZaimi: This is an interesting idea, but I have no experience with Hall sets so far (besides knowing that they somehow generalize Lyndon words, or rather a lift of them to the free magma), and the definition is daunting. Do you see a way to machinally check the existence of a Hall set lifting a given subset of $\mathfrak A^\ast$ (in given degrees)? | |
| Nov 20, 2014 at 20:40 | comment | added | The Masked Avenger | @David, my hopes for an alternate characterization as simple as the three part one for Lyndon words may be dampened, but what I propose is a computation that may lead to understanding or a sample testbed to try alternate definitions. Since I used * for word reversal as well as for reversing the alphabet ordering, the actual condition may be more complicated, e.g. one of u* > v or u> v* or v>* u must hold. Of course, you have the testbed, and I do not challenge your contention that there is no apparent and nice characterization appearing yet. | |
| Nov 20, 2014 at 20:23 | comment | added | David Hill | @TheMaskedAvenger This is definitely not what is going on. The modifications you are proposing would yield Lyndon words for the associated ordering. Nyldon words behave very differently. For example, the Nyldon words $101$ and $1011$ defy this kind of description. | |
| Nov 20, 2014 at 7:25 | comment | added | Gjergji Zaimi | Can these words be realized as Hall words for a specific ordering of words? (Maybe the dual ordering to lexicographic.) This would imply your conjectures if it was the case... encyclopediaofmath.org/index.php/Hall_word | |
| Nov 20, 2014 at 6:52 | history | edited | darij grinberg | CC BY-SA 3.0 |
added 272 characters in body
|
| Nov 20, 2014 at 2:46 | comment | added | darij grinberg | I have verified Conjecture 1 on a 3-letter alphabet for length up to $11$, and Conjecture 2 for length up to $9$. | |
| Nov 19, 2014 at 4:47 | comment | added | The Masked Avenger | Try computations on a three letter alphabet. I am hoping it will lead to a quick resolution. In particular, I hope you might get a three part equivalent charcacterization of Nyldon words, where a condition might be u* >* v*, where * means reversed word or reversed total order on the alphabet. | |
| Nov 18, 2014 at 22:12 | comment | added | David Hill | @darijgrinberg: sorry, no. I was not saying that. I was just pointing out that things that seem to happen in a 2 letter alphabet are unlikely to be true for bigger alphabets. For example, certain palindromes are Nyldon, but cycling the first letter to the end will not make them Lyndon Honestly, these Nyldon words are baffling. | |
| Nov 18, 2014 at 22:03 | comment | added | darij grinberg | @DavidHill: Are you implying that Per's statement is true on a 2-letter alphabet? This would be very interestign! | |
| Nov 18, 2014 at 21:51 | comment | added | David Hill | @PerAlexandersson, I don't think this coincidence in a 2 letter alphabet generalizes. The thing about Lyndon words is that they are filled with patterns. For example, every Lyndon work looks like $w=w_1^kw_1'i$, where $w_1$ is Lyndon, $w_1'$ is a (possibly empty) left factor of $w_1$ and $i$ is a letter such that $w_1'i>w_1$ (this was proved by Leclerc). In contrast, Nyldon words seem to be pattern avoiding. | |
| Nov 18, 2014 at 21:27 | comment | added | Per Alexandersson | Looks like in many (but not all) cases, $a_1a_2\dots a_n$ is a Nyldon word, then $a_2\dots a_n a_1$ is a Lyndon word. But this is not entirely true... But maybe a bijection can start from this? | |
| Nov 18, 2014 at 21:18 | comment | added | Ilya Bogdanov | Thanks! Now it's much easier to falsify the conjectures;) | |
| Nov 18, 2014 at 19:37 | history | edited | darij grinberg | CC BY-SA 3.0 |
added 447 characters in body
|
| Nov 18, 2014 at 19:32 | comment | added | darij grinberg | @PerAlexandersson: This would follow from either of the two conjectures. | |
| Nov 18, 2014 at 13:11 | comment | added | Ilya Bogdanov | Darij, wouldn't it be better to put into `Exp. data' the corresponding sets of Lyndon words? Just for comparison... | |
| Nov 18, 2014 at 9:14 | comment | added | Per Alexandersson | Are the sets of Lyndon words and Nyldon words of length $n$ of same cardinality? Maybe there is a simple bijective proof of these conjectures. | |
| Nov 18, 2014 at 8:24 | history | edited | darij grinberg | CC BY-SA 3.0 |
added 538 characters in body
|
| Nov 18, 2014 at 8:15 | history | asked | darij grinberg | CC BY-SA 3.0 |