Timeline for So many types of subwords! How are they called?
Current License: CC BY-SA 4.0
16 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Aug 29, 2022 at 20:31 | comment | added | Salvo Tringali | At the end of the day, I think I won't get away with anything better than what has already emerged from the previous comments. If someone is willing to post a summary of the information collected so far, I'll be happy to accept it as an answer. | |
| Aug 29, 2022 at 19:07 | comment | added | Vladimir Dotsenko | P.S. You might also find useful that in studying a similar story for permutations rather than words, there is its own terminology: type 1 is referred to as "consecutive pattern", while type 2 is simply "pattern". | |
| Aug 29, 2022 at 18:28 | history | edited | Salvo Tringali | CC BY-SA 4.0 |
added further details to motivate the def of the shuffling preorder
|
| Aug 29, 2022 at 15:52 | comment | added | Benjamin Steinberg | French mathematicians often use subword for scattered subword and non-French mathematicians often use subword for factor | |
| Aug 29, 2022 at 15:22 | comment | added | Benjamin Steinberg | The standard terminology in combinatorics on words is factor for 1, scattered subword for 2. I don't know a term for 3. Abelian subword usually means the letters appear consecutively but in a different order I believe | |
| Aug 29, 2022 at 14:19 | comment | added | Salvo Tringali | @VilleSalo I very much like this idea of "anagrams". One could maybe talk of subanagrams in case of subwords of type 3. | |
| Aug 29, 2022 at 11:16 | history | edited | Salvo Tringali | CC BY-SA 4.0 |
addressed a question by Vladimir Dotsenko in the comments to the OP
|
| Aug 29, 2022 at 11:08 | history | edited | Salvo Tringali | CC BY-SA 4.0 |
addressed a question by Vladimir Dotsenko in the comments to the OP
|
| Aug 29, 2022 at 9:13 | comment | added | Ville Salo | Subword / scattered subword seems like a good enough pair. As for 3, combinatorics on word-ists sometimes throw around the word "abelian" when you take take a standard notion but also take anagrams (I don't know why they don't speak of "anagrams" given how much they talk about "palindromes"). So "abelian scattered subword" sounds relatively unambiguous to me. (And also horrible, sorry I'm not very helpful.) | |
| Aug 29, 2022 at 9:01 | comment | added | Salvo Tringali | @VilleSalo To me, "factor" makes a lot of sense for subwords of type 1, so one may want to talk of "factor subwords" in that case: A lot of people out there simply use the term "subword" (without any qualifier) for subwords of type 1 (as was also pointed out by Vladimir Dotsenko in his comment). But I really need to distinguish the three types in some situations that naturally occur in my research area. | |
| Aug 29, 2022 at 8:56 | comment | added | Salvo Tringali | @VladimirDotsenko Of course, a word is a (finite) sequence in $X$ and hence it makes sense to call a subword of type 2 a subsequence. But this is sort of mixing two different pts of view (after all, I'm referring to a word as a word and not as a sequence). As for situations where subwords of type 3 appear in a meaningful way, it's probably better if I edit the OP and address your question therein (but later, I'm a bit busy now). | |
| Aug 29, 2022 at 8:44 | comment | added | Ville Salo | I now notice the actual question. As far as I know, "factor" (when speaking of the factor of a word) can only mean 1 as far as I know. And as far as I know, "scattered subword" and "subsequence" can only mean 2. I think they are all "well-established", but I don't have statistics to back that up. I can't think of an unambiguous standard name for 3. | |
| Aug 29, 2022 at 8:27 | comment | added | Ville Salo | Lothaire's Combinatorics on words uses "factor" for 1 (Chapter 5) and "subword" for 2 (Chapter 6). It may or may not be an exception, but be careful out there. | |
| Aug 29, 2022 at 5:27 | comment | added | Vladimir Dotsenko | Does the situation 3 really appear in a meaningful way? Whenever I saw situations where 1 needed to be distinguished from 2, I recall 1 being described as a subword while 2 referred to as a subsequence. | |
| Aug 29, 2022 at 4:28 | history | edited | Salvo Tringali | CC BY-SA 4.0 |
edited tags
|
| Aug 29, 2022 at 4:23 | history | asked | Salvo Tringali | CC BY-SA 4.0 |