The Combinatorics of String Alignments: Reconsidering the Problem*
Steffen Eger · Journal of Quantitative Linguistics · 2012
In recent work, Covington discusses the number of alignments of two strings. Thereby, Covington defines an alignment as “a way of pairing up elements of two strings, optionally skipping some but preserving the order”. This definition has drawbacks as it excludes many relevant situations. In this work, we specify the notion of an alignment so that many linguistically interesting situations are covered. To this end, we define an alignment in an abstract manner as a set of pairs and then define three properties on such sets. Secondly, we specify the numbers of possibilities of aligning two strings in each case.