Foundations · Lesson 3

Borders

Practice this topic →

Definition

Intuition: the same nonempty string appears at both the beginning and the end of the word.

A border must be nonempty (so $\epsilon$ never counts) and proper (strictly shorter than $w$, so the whole word never counts).

For 010010, the borders are 0 and 010 — each appears at both ends:

A non-example

For 001001, length $2$ is not a border: the prefix of length 2 is 00, but the suffix of length 2 is 01. The prefix and suffix differ:

Bordered and unbordered words

For example, aaaa is bordered (its borders are a, aa, aaa), while abcde is unbordered.

Why borders matter: packet markers

Imagine a stream of bits being sent from one computer to another. The stream is split into packets, and the receiver needs to know where each packet begins and ends. So we insert a marker, say the word 010, between every packet.

The trouble is that two occurrences of 010 can overlap. In the stream

010 | 10     =    01 | 010

the packet following the marker begins with 10, and the packet before the marker ends with 01. Both produce the same bit string 01010, so the receiver cannot tell where the packet boundary is: is it 010 | 10 or 01 | 010?

The shared symbol is a border of the marker. More generally, any overlap between two distinct occurrences of a marker is simultaneously a suffix of the first occurrence and a prefix of the next — exactly a border of the marker. An unbordered marker therefore can never overlap another occurrence of itself, which is why unbordered words are studied in digital communications. This same border information later lets pattern-matching algorithms reuse comparisons: after a partial match fails, a border tells us which part of the match is still useful.

Longest and shortest border

If a word has borders, the longest border is the border of greatest length, and the shortest border the border of least length.

For abababa, the borders are a, aba, and ababa:

• longest border: ababa
• shortest border: a

Note that ab is not a border: its suffix counterpart of length 2 is ba, not ab.

Practice

Identify all borders

Is it unbordered?

Longest and shortest border

Construct an unbordered word

Practice this topic →Every quiz from this lesson, at four difficulties.