). Let Σ be an alphabet. For two characters a, b ∈ Σ, we denote by a → b the elementary edit operation that substitutes a with b. Denoting by ε the null character (the empty string), we can define the elementary edit operations of insertion and deletion as ε → b and a → ε, respectively.