Definitions

As variable length Markov models (VLMM) have been designed to learn text, that is sequence of letters, it is easier to understand if we keep the original terminology and map it to our problem. So in the next sections, we will use the following definitions.

An alphabet $\Sigma$ is a set of predefined distinct entities. In the case of sequence of letters, the entities would be letters. In the case of sequence of face, the entities would be the prototypes as defined in 4.3. We will refer to these entities as being letters to stick to the original definitions given by Ron et al. [51]. $\vert\Sigma\vert$ denotes the size of the alphabet.

A string is a sequence of letters and is denoted by $s=s_1s_2s_3\ldots s_n$ where $n$ is the length of the sequence. We denote by $e$ the empty string. $\Sigma^*$ is the set of all strings over $\Sigma$, $\Sigma^L$ is the set of all strings of length $L$ over $\Sigma$, and $\Sigma^{\leq L}$ is the set of all strings of length at most $L$ over $\Sigma$.

A prefix of a string $s$ of length $n$ is denoted by $prefix(s)=s_1s_2s_3\ldots s_{n-1}$. In the same manner, a suffix of a string $s$ of length $n$ is denoted by $suffix(s)=s_2s_3\ldots s_n$. The set of all suffixes of a string $s$ of length $n$ is $Suffix^*(s)=\{s_i\ldots s_n\vert 1\leq i\leq n\}\cup{e}$.

A string $p$ is a suffix extension of $s$ if and only if $s$ is a suffix of $p$, that is $s\in Suffix^*(p)$.