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

Yo Sub Han; Sang Ki Ko; Kai Salomaa

doi:10.1007/978-3-642-31653-1_9

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

Yo Sub Han, Sang Ki Ko, Kai Salomaa

Department of Artificial Intelligence

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

8 Scopus citations

Abstract

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.

Original language	English
Title of host publication	Developments in Language Theory - 16th International Conference, DLT 2012, Proceedings
Pages	85-96
Number of pages	12
DOIs	https://doi.org/10.1007/978-3-642-31653-1_9
State	Published - 2012
Event	16th International Conference on Developments in Language Theory, DLT 2012 - Taipei, Taiwan, Province of China Duration: 14 Aug 2012 → 17 Aug 2012

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	7410 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	16th International Conference on Developments in Language Theory, DLT 2012
Country/Territory	Taiwan, Province of China
City	Taipei
Period	14/08/12 → 17/08/12

Keywords

Context-free language
Edit-distance
Levenshtein distance
Regular language

Access to Document

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

Cite this

Han, Y. S., Ko, S. K., & Salomaa, K. (2012). Computing the edit-distance between a regular language and a context-free language. In Developments in Language Theory - 16th International Conference, DLT 2012, Proceedings (pp. 85-96). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 7410 LNCS). https://doi.org/10.1007/978-3-642-31653-1_9

@inproceedings{6f9f2dad6bb140309cb0f3185be4ccc0,

title = "Computing the edit-distance between a regular language and a context-free language",

abstract = "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.",

keywords = "Context-free language, Edit-distance, Levenshtein distance, Regular language",

author = "Han, {Yo Sub} and Ko, {Sang Ki} and Kai Salomaa",

year = "2012",

doi = "10.1007/978-3-642-31653-1_9",

language = "English",

isbn = "9783642316524",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

pages = "85--96",

booktitle = "Developments in Language Theory - 16th International Conference, DLT 2012, Proceedings",

note = "16th International Conference on Developments in Language Theory, DLT 2012 ; Conference date: 14-08-2012 Through 17-08-2012",

}

Han, YS, Ko, SK & Salomaa, K 2012, Computing the edit-distance between a regular language and a context-free language. in Developments in Language Theory - 16th International Conference, DLT 2012, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 7410 LNCS, pp. 85-96, 16th International Conference on Developments in Language Theory, DLT 2012, Taipei, Taiwan, Province of China, 14/08/12. https://doi.org/10.1007/978-3-642-31653-1_9

Computing the edit-distance between a regular language and a context-free language. / Han, Yo Sub; Ko, Sang Ki; Salomaa, Kai.
Developments in Language Theory - 16th International Conference, DLT 2012, Proceedings. 2012. p. 85-96 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 7410 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

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 -

Han YS, Ko SK, Salomaa K. Computing the edit-distance between a regular language and a context-free language. In Developments in Language Theory - 16th International Conference, DLT 2012, Proceedings. 2012. p. 85-96. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-642-31653-1_9

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

Abstract

Publication series

Conference

Keywords

Access to Document

Other files and links

Fingerprint

Cite this