Given a symbol set , a sequence over is an ordered collection of symbols of , .
We call the set of all the sequences over .
Given , we use the following notation:
- is the empty sequence.
- is the concatenation of and .
- is the length (number of symbols) of .
- is the -th symbols of .
- represents that is a subsequence of , ie, there exist sequences such that .
- is the equality of sequences, ie., and .
- is the number of times that the sequence appears in the sequence .