## You are here

Homeprefix set

## Primary tabs

# prefix set

Let $X$ be a set, and $w\in X^{*}$ be a word, i.e. an element of the free monoid on $X$. A word $v\in X^{*}$ is called *prefix* of $w$ when a second word $z\in X^{*}$ exists such that $x=vz$. A *proper prefix* of a word u is a prefix v of u not equal to u (sometimes v is required to be non-empty).

Note that the empty word $\varepsilon$ and $w$ are prefix of $w$, and a proper prefix of $w$ if $w$ is non-empty.

The *prefix set* of $w$ is the set $\mathrm{pref}(w)$ of prefixes of $w$, i.e. if $w=w_{1}w_{2}...w_{n}$ with $w_{j}\in X$ for each $j\in\{1,...,n\}$ we have

$\mathrm{pref}(w)=\{\varepsilon,\ w_{1},\ w_{1}w_{2},\ ...,\ w_{1}w_{2}...w_{{n% -1}},\ w\}.$ |

Some closely related concepts are:

1. A set of words is

*prefix closed*if for every word in the set, any of its prefix is also in the set.2. The

*prefix closure*of a set S is the smallest prefix closed set containing S, or, equivalently, the union of the prefix sets of words in S.3. A set S is

*prefix free*if for any word in S, no proper prefixes of the word are in S.

## Mathematics Subject Classification

20M05*no label found*

- Forums
- Planetary Bugs
- HS/Secondary
- University/Tertiary
- Graduate/Advanced
- Industry/Practice
- Research Topics
- LaTeX help
- Math Comptetitions
- Math History
- Math Humor
- PlanetMath Comments
- PlanetMath System Updates and News
- PlanetMath help
- PlanetMath.ORG
- Strategic Communications Development
- The Math Pub
- Testing messages (ignore)

- Other useful stuff
- Corrections