Timeline for Testing whether letters can be scheduled to achieve a word in a regular language
Current License: CC BY-SA 3.0
6 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Mar 5, 2018 at 16:23 | vote | accept | Antoine Amarilli 'a3nm' | ||
| Mar 5, 2018 at 16:23 | comment | added | Antoine Amarilli 'a3nm' | I guess in your second message you meant "with the old interval $(l', r')$" rather than "$(l, r)$"? But OK, I see it: when you add the crossing vertex, the only bad case would be an interval $I$ that overlap with a new interval without overlapping with the corresponding interval. This cannot happen for supersets of $(l, r)$ or of $(l', r')$: if they overlap with a new interval then they overlapped with the old one. Likewise for subsets of $(l, r)$ or $(l', r')$ for the reason that you explain. So I agree that this proof looks correct to me. Thanks again! | |
| Mar 5, 2018 at 0:12 | comment | added | Mikhail Rudoy | (continued) interval. In this case, you aren't actually creating a new crossing, just turning an old crossing with the old interval $(l,r)$ into a new crossing with the interval $(i+\text{something}, r)$ | |
| Mar 5, 2018 at 0:08 | comment | added | Mikhail Rudoy | If $l <l' <r < r'$, then you can insert the new indices for the new crossover vertex immediately to the right of $l'$. This causes the new indices ($i\pm$ a bit) to be in exactly those intervals that used to contain $l'$. It should be easy to see that adding a crossover vertex can add a new crossing with some other interval only if the new indices fall in the other interval. If $l' < l'' < r'' < r'$ then the new indices do not fall into the interval $(l'', r'')$. If $l < l'' < r'' < r$ then the new indices might fall into the interval $(l'', r'')$, but only if $l'$ already fell into that | |
| Mar 4, 2018 at 19:20 | comment | added | Antoine Amarilli 'a3nm' | Thanks a lot for this elaborate proof, and with a very simple language! I think it is correct, the only thing I'm not sure about is the claim that "adding the crossover vertex can't cause any additional edges to become crossed". Couldn't it be the case that the interval $(l, r)$ included some other interval $(l'', r'')$ with $l \leq l'' \leq r'' \leq r$, and now one of $(l, i-1)$ and $(i+2, r)$ crosses it? It seems like the process still has to converge because the intervals get smaller, but that's not completely clear either because of the insertion of crossover vertices. How should I see it? | |
| Mar 3, 2018 at 22:18 | history | answered | Mikhail Rudoy | CC BY-SA 3.0 |