Skip to main content
added 278 characters in body
Source Link
Tim Campion
  • 63.9k
  • 13
  • 143
  • 384

If every string appears in $f$ consecutively, then every string appears consecutively in $f \sigma$.

(So yes in answer to the title question, no in answer to the question as phrased in the question body :)

(Thanks to Alessandro Della Corte for corrections in the comments below!)

To see this, suppose that every string appears consecutively in $f$. Let $S$ be a string of even length. Since $S 0 S$ appears consecutively in $f$, it follows that $S$ appears consecutively in $f$ starting from an even position. (We could equally have used $S1S$.)

Since every string $S$ of even length appears consecutively in $f$ starting from even position, it's also the case that $S \circ \sigma$ appears consecutively in $f$ starting from an even position. So every string $S$ of even length appears consecutively in $f \circ \sigma$ (starting from even position). As every string is a consecutive substring of a string of even length, it follows that every string appears consecutively in $f \circ \sigma$.

If every string appears in $f$ consecutively, then every string appears consecutively in $f \sigma$.

(So yes in answer to the title question, no in answer to the question as phrased in the question body :)

To see this, suppose that every string appears consecutively in $f$. Let $S$ be a string. Since $S 0 S$ appears consecutively in $f$, it follows that $S$ appears consecutively in $f$ starting from an even position. (We could equally have used $S1S$.)

Since every string $S$ appears consecutively in $f$ starting from even position, it's also the case that $S \circ \sigma$ appears consecutively in $f$ starting from an even position. So $S$ appears consecutively in $f \circ \sigma$ (starting from even position).

If every string appears in $f$ consecutively, then every string appears consecutively in $f \sigma$.

(So yes in answer to the title question, no in answer to the question as phrased in the question body :)

(Thanks to Alessandro Della Corte for corrections in the comments below!)

To see this, suppose that every string appears consecutively in $f$. Let $S$ be a string of even length. Since $S 0 S$ appears consecutively in $f$, it follows that $S$ appears consecutively in $f$ starting from an even position. (We could equally have used $S1S$.)

Since every string $S$ of even length appears consecutively in $f$ starting from even position, it's also the case that $S \circ \sigma$ appears consecutively in $f$ starting from an even position. So every string $S$ of even length appears consecutively in $f \circ \sigma$ (starting from even position). As every string is a consecutive substring of a string of even length, it follows that every string appears consecutively in $f \circ \sigma$.

edited body
Source Link
Tim Campion
  • 63.9k
  • 13
  • 143
  • 384

If every string appears in $f$ consecutively, then every string appears consecutively in $f \sigma$.

(So yes in answer to the title question, no in answer to the question as phrased in the question body :)

To see this, suppose that every string appears consecutively in $f$. Let $S$ be a string. Since $S 0 S$ appears consecutively in $f$, it follows that $S$ appears consecutively in $f$ starting from an even position. (We could equally have used $S1S$.)

Since every string appears consecutively $S$ appears consecutively in $f$ starting from even position, it's also the case that $S \sigma$$S \circ \sigma$ appears consecutively in $f$ starting from an even position. So $S$ appears consecutively in $f \sigma$$f \circ \sigma$ (starting from even position).

If every string appears in $f$ consecutively, then every string appears consecutively in $f \sigma$.

(So yes in answer to the title question, no in answer to the question as phrased in the question body :)

To see this, suppose that every string appears consecutively in $f$. Let $S$ be a string. Since $S 0 S$ appears consecutively in $f$, it follows that $S$ appears consecutively in $f$ starting from an even position. (We could equally have used $S1S$.)

Since every string appears consecutively $S$ in $f$ starting from even position, it's also the case that $S \sigma$ appears consecutively in $f$ starting from an even position. So $S$ appears consecutively in $f \sigma$ (starting from even position).

If every string appears in $f$ consecutively, then every string appears consecutively in $f \sigma$.

(So yes in answer to the title question, no in answer to the question as phrased in the question body :)

To see this, suppose that every string appears consecutively in $f$. Let $S$ be a string. Since $S 0 S$ appears consecutively in $f$, it follows that $S$ appears consecutively in $f$ starting from an even position. (We could equally have used $S1S$.)

Since every string $S$ appears consecutively in $f$ starting from even position, it's also the case that $S \circ \sigma$ appears consecutively in $f$ starting from an even position. So $S$ appears consecutively in $f \circ \sigma$ (starting from even position).

Source Link
Tim Campion
  • 63.9k
  • 13
  • 143
  • 384

If every string appears in $f$ consecutively, then every string appears consecutively in $f \sigma$.

(So yes in answer to the title question, no in answer to the question as phrased in the question body :)

To see this, suppose that every string appears consecutively in $f$. Let $S$ be a string. Since $S 0 S$ appears consecutively in $f$, it follows that $S$ appears consecutively in $f$ starting from an even position. (We could equally have used $S1S$.)

Since every string appears consecutively $S$ in $f$ starting from even position, it's also the case that $S \sigma$ appears consecutively in $f$ starting from an even position. So $S$ appears consecutively in $f \sigma$ (starting from even position).