Computing the Edit-Distance of Formal Languages

ABSTRACT:
The edit-distance between two strings is the smallest number of operations required to transform one string into the other. The edit-distance is often used as a natural measure of string similarity. The problem of computing the edit-distance arises in many areas, such as, computational biology, text processing and speech recognition. In this tutorial, we study the edit-distance between two formal languages instead of two strings. Mainly, we focus on the decidability and computational complexity of the edit-distance between various types of formal languages.

BIOGRAPHY:
Sang-Ki Ko received his Ph.D. at Yonsei University in 2016 and is now a senior researcher at AI Research Center of Korea Electronics Technology Institute (KETI). His research field lies in the theory of computation and applications related to automata theory. He also worked on reachability problems for automata, matrices, and maps at University of Liverpool in 2016 as a postdoctoral researcher. Since he moved to KETI in August of 2017, he is now working on artificial intelligence problems and trying to find interesting connections between AI and formal language problems.