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 $\epsilon$ 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\mathrm{\dots }{w}_n$ with $w_j\in X$ for each $j\in \{1,\mathrm{\dots },n\}$ we have

$$\mathrm{pref}(w)=\{\epsilon ,w_1,w_1{w}_2,\mathrm{\dots },w_1{w}_2\mathrm{\dots }{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.

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