Border (String)

Definition

Border (String)

A string $X$ is a border of a string $S$ if $X$ is both a prefix and a suffix of $S$.

Trivial

Definition

Trivial String Border

Given a string $S$, then $\epsilon$, the empty string, and $S$, the string itself, are called trivial string borders.

Link to original

Chain

Definition

Chain (Border, String)

Of two borders of the same string, the shorter is a border of the longer. For strings $X,Y,S$,

$$X\text{ and }Y\text{ are borders of }S,|X|<|Y|⟹X\text{ is a border of }Y.$$

Thus the borders of $S$ form a nested chain: ordering them by length also orders them by the border relation. Two borders of equal length are the same string, since both are the prefix of $S$ of that length.

Link to original

Transitivity

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.

Link to original

Examples

$S=\text{ababa}$

The borders are $\epsilon$, $\text{a}$, and $\text{aba}$.

$S=\text{abcab}$

The borders are $\epsilon$ and $\text{ab}$.

$S=\text{aaaa}$

The borders are $\epsilon$, $\text{a}$, $\text{aa}$, and $\text{aaa}$. The full string itself is not a border.