# 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. 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. 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. 3.

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

 Title prefix set Canonical name PrefixSet Date of creation 2013-03-22 16:11:56 Last modified on 2013-03-22 16:11:56 Owner Mazzu (14365) Last modified by Mazzu (14365) Numerical id 6 Author Mazzu (14365) Entry type Definition Classification msc 20M05 Defines prefix Defines prefix set Defines proper prefix Defines prefix closed Defines prefix closure Defines prefix free