Transitivity (Border, String)

Definition

Transitivity (Border, String)

A border of a border is a border of the original string. For strings $X,Y,S$,

$$\underset{Y\text{ begins and ends with }X}{\underbrace{X\text{ is a border of }Y}}\wedge \underset{S\text{ begins and ends with }Y}{\underbrace{Y\text{ is a border of }S}}⟹X\text{ is a border of }S.$$

This is transitivity of the border relation. The diagram shows one arrangement; the two occurrences of $Y$ in $S$ need not be disjoint.

Why the Ends Are Preserved

Start with $Y$, which begins and ends with $X$. Now suppose a string $S$ begins and ends with $Y$.

Both ends of $S$ contain $X$

The prefix of the prefix and the suffix of the suffix remain at the ends of $S$.

Proof

• At the beginning: $S$ begins with $Y$, and $Y$ begins with $X$. Therefore $S$ begins with $X$.
• At the end: $S$ ends with $Y$, and $Y$ ends with $X$. Therefore $S$ ends with $X$.

Thus $X$ is both a prefix and a suffix of $S$, so it is a border of $S$.

Taking $S=YY$ works, as does $S=YUY$ for any intervening string $U$. But the theorem does not require either construction: the initial and final occurrences of $Y$ may overlap.

Examples

Overlapping occurrences, not a doubled string

Let $X=\mathrm{a}$, $Y=\mathrm{aba}$, and $S=\mathrm{ababa}$.

• $Y$ begins and ends with $X=\mathrm{a}$.
• $S$ begins and ends with $Y=\mathrm{aba}$; these occurrences share the middle character.
• Therefore $S$ begins and ends with $X=\mathrm{a}$.

Here $S\ne YY$: transitivity concerns the ends, not concatenating two copies.