TY - JOUR
T1 - Improving calculations of the number of distinct alignments of two strings
AU - Rødseth, Øystein J.
AU - Sellers, James A.
PY - 2006/12/1
Y1 - 2006/12/1
N2 - In a recent work, Covington discusses the enumeration of two different sets of alignments of two strings of symbols using elementary combinatorial techniques. He defines two functions a(m, n) and A(m, n) to count the number of two-string alignments in his "small" and "middle" sets of alignments (respectively). He provides a recurrence for each of these functions which allows for the calculation of values of a(m,n) and A(m,n). In this note, we obtain generating functions for each of these functions. With the generating functions in hand, we provide improvements on Covington's recurrences, making the calculation of a(m, n) and A(m, n) much more efficient.
AB - In a recent work, Covington discusses the enumeration of two different sets of alignments of two strings of symbols using elementary combinatorial techniques. He defines two functions a(m, n) and A(m, n) to count the number of two-string alignments in his "small" and "middle" sets of alignments (respectively). He provides a recurrence for each of these functions which allows for the calculation of values of a(m,n) and A(m,n). In this note, we obtain generating functions for each of these functions. With the generating functions in hand, we provide improvements on Covington's recurrences, making the calculation of a(m, n) and A(m, n) much more efficient.
UR - http://www.scopus.com/inward/record.url?scp=43249154408&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=43249154408&partnerID=8YFLogxK
U2 - 10.1080/09296170500500777
DO - 10.1080/09296170500500777
M3 - Article
AN - SCOPUS:43249154408
VL - 13
SP - 45
EP - 55
JO - Journal of Quantitative Linguistics
JF - Journal of Quantitative Linguistics
SN - 0929-6174
IS - 1
ER -