A Normalized Edit Distance on Infinite Words
Dana Fisman, Joshua Grogin, Margalit, Oded, Gera Weiss · arXiv (Cornell University) · 2022
We introduce ω^ ̅-NED, an edit distance between infinite words, that is a natural extension of NED, the normalized edit distance between finite words. We show it is a metric on (equivalence classes of) infinite words. We provide a polynomial time algorithm to compute the distance between two ultimately periodic words, and a polynomial time algorithm to compute the distance between two regular ω-languages given by non-deterministic Büchi automata.