TY - GEN

T1 - Computing the edit-distance between a regular language and a context-free language

AU - Han, Yo Sub

AU - Ko, Sang Ki

AU - Salomaa, Kai

PY - 2012

Y1 - 2012

N2 - The edit-distance between two strings is the smallest number of operations required to transform one string into the other. The edit-distance problem for two languages is to find a pair of strings, each of which is from different language, with the minimum edit-distance. We consider the edit-distance problem for a regular language and a context-free language and present an efficient algorithm that finds an optimal alignment of two strings, each of which is from different language. Moreover, we design a faster algorithm for the edit-distance problem that only finds the minimum number of operations of the optimal alignment.

AB - The edit-distance between two strings is the smallest number of operations required to transform one string into the other. The edit-distance problem for two languages is to find a pair of strings, each of which is from different language, with the minimum edit-distance. We consider the edit-distance problem for a regular language and a context-free language and present an efficient algorithm that finds an optimal alignment of two strings, each of which is from different language. Moreover, we design a faster algorithm for the edit-distance problem that only finds the minimum number of operations of the optimal alignment.

KW - Context-free language

KW - Edit-distance

KW - Levenshtein distance

KW - Regular language

UR - http://www.scopus.com/inward/record.url?scp=84865039678&partnerID=8YFLogxK

U2 - 10.1007/978-3-642-31653-1_9

DO - 10.1007/978-3-642-31653-1_9

M3 - Conference contribution

AN - SCOPUS:84865039678

SN - 9783642316524

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 85

EP - 96

BT - Developments in Language Theory - 16th International Conference, DLT 2012, Proceedings

T2 - 16th International Conference on Developments in Language Theory, DLT 2012

Y2 - 14 August 2012 through 17 August 2012

ER -