A Normalized Edit Distance on Infinite Words

Autor:	Fisman, Dana, Grogin, Joshua, Weiss, Gera
Jazyk:	angličtina
Rok vydání:	2023
Předmět:	Edit Distance Hardware → Robustness Theory of computation → Formal languages and automata theory Theory of computation → Pattern matching Robustness Infinite Words
DOI:	10.4230/lipics.csl.2023.20
Popis:	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. LIPIcs, Vol. 252, 31st EACSL Annual Conference on Computer Science Logic (CSL 2023), pages 20:1-20:20
Databáze:	OpenAIRE
Externí odkaz:	https://explore.openaire.eu/search/publication?articleId=doi_________::b9bae9b6ef7c336a64cbbafe4485d506 Zobrazit plný text záznamu