We can talk of a set of models of the same signature, where signature refers to a set S = {f 1 , ..., f n , R 1 , ..., R n } of named functions and relations.
we consider models of strings of the signature {p, s, P σ∈Σ }, where p and s are the predecessor and successor functions, respectively, indicating the order of positions in the string, and for every σ ∈ Σ there is a unary relation P σ indicating the labels of each position.