}, and let S ⊆ N 2 \{(0, 0)} be a set defining the valid match-up operations between x characters and y characters.
when (s, t) ∈ S, then this means we allow matches of subsequences of x of length s and subsequences of y of length t. 1 It is convenient to define a monotone many-tomany alignment of x and y as a 2×k (for k ≥ 1 arbitrary) nonnegative integer matrix A x,y ∈ N 2×k satisfying A x,y 1 k = x y , i.e., the two rows of A x,y sum up to the lengths of the respective strings, 2 and where each column of A x,y lies in S. For any such alignment, we let (x 1 , .