prefix set

Let X be a set, and wX* be a word, i.e. an element of the free monoid on X. A word vX* is called prefix of w when a second word zX* 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 wordPlanetmathPlanetmath ε 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 pref(w) of prefixes of w, i.e. if w=w1w2wn with wjX for each j{1,,n} we have


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