2 Search Results for "Grogin, Joshua"


Document
A Normalized Edit Distance on Infinite Words

Authors: Dana Fisman, Joshua Grogin, and Gera Weiss

Published in: LIPIcs, Volume 252, 31st EACSL Annual Conference on Computer Science Logic (CSL 2023)


Abstract
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.

Cite as

Dana Fisman, Joshua Grogin, and Gera Weiss. A Normalized Edit Distance on Infinite Words. In 31st EACSL Annual Conference on Computer Science Logic (CSL 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 252, pp. 20:1-20:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)


Copy BibTex To Clipboard

@InProceedings{fisman_et_al:LIPIcs.CSL.2023.20,
  author =	{Fisman, Dana and Grogin, Joshua and Weiss, Gera},
  title =	{{A Normalized Edit Distance on Infinite Words}},
  booktitle =	{31st EACSL Annual Conference on Computer Science Logic (CSL 2023)},
  pages =	{20:1--20:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-264-8},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{252},
  editor =	{Klin, Bartek and Pimentel, Elaine},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CSL.2023.20},
  URN =		{urn:nbn:de:0030-drops-174818},
  doi =		{10.4230/LIPIcs.CSL.2023.20},
  annote =	{Keywords: Edit Distance, Infinite Words, Robustness}
}
Document
The Normalized Edit Distance with Uniform Operation Costs Is a Metric

Authors: Dana Fisman, Joshua Grogin, Oded Margalit, and Gera Weiss

Published in: LIPIcs, Volume 223, 33rd Annual Symposium on Combinatorial Pattern Matching (CPM 2022)


Abstract
We prove that the normalized edit distance proposed in [Marzal and Vidal 1993] is a metric when the cost of all the edit operations are the same. This closes a long standing gap in the literature where several authors noted that this distance does not satisfy the triangle inequality in the general case, and that it was not known whether it is satisfied in the uniform case - where all the edit costs are equal. We compare this metric to two normalized metrics proposed as alternatives in the literature, when people thought that Marzal’s and Vidal’s distance is not a metric, and identify key properties that explain why the original distance, now known to also be a metric, is better for some applications. Our examination is from a point of view of formal verification, but the properties and their significance are stated in an application agnostic way.

Cite as

Dana Fisman, Joshua Grogin, Oded Margalit, and Gera Weiss. The Normalized Edit Distance with Uniform Operation Costs Is a Metric. In 33rd Annual Symposium on Combinatorial Pattern Matching (CPM 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 223, pp. 17:1-17:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)


Copy BibTex To Clipboard

@InProceedings{fisman_et_al:LIPIcs.CPM.2022.17,
  author =	{Fisman, Dana and Grogin, Joshua and Margalit, Oded and Weiss, Gera},
  title =	{{The Normalized Edit Distance with Uniform Operation Costs Is a Metric}},
  booktitle =	{33rd Annual Symposium on Combinatorial Pattern Matching (CPM 2022)},
  pages =	{17:1--17:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-234-1},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{223},
  editor =	{Bannai, Hideo and Holub, Jan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2022.17},
  URN =		{urn:nbn:de:0030-drops-161446},
  doi =		{10.4230/LIPIcs.CPM.2022.17},
  annote =	{Keywords: edit distance, normalized distance, triangle inequality, metric}
}
  • Refine by Author
  • 2 Fisman, Dana
  • 2 Grogin, Joshua
  • 2 Weiss, Gera
  • 1 Margalit, Oded

  • Refine by Classification
  • 2 Theory of computation → Pattern matching
  • 1 Hardware → Robustness
  • 1 Theory of computation → Formal languages and automata theory

  • Refine by Keyword
  • 1 Edit Distance
  • 1 Infinite Words
  • 1 Robustness
  • 1 edit distance
  • 1 metric
  • Show More...

  • Refine by Type
  • 2 document

  • Refine by Publication Year
  • 1 2022
  • 1 2023

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail