2 Search Results for "Zilles, Sandra"

Document
DOI: 10.4230/LIPIcs.CPM.2024.14
When Is the Normalized Edit Distance over Non-Uniform Weights a Metric?

Authors: Dana Fisman and Ilay Tzarfati

Published in: LIPIcs, Volume 296, 35th Annual Symposium on Combinatorial Pattern Matching (CPM 2024)

Abstract
The well known Normalized Edit Distance (ned) [Marzal and Vidal 1993] is known to disobey the triangle inequality on contrived weight functions, while in practice it often exhibits a triangular behavior. Let d be a weight function on basic edit operations, and let ned_{d} be the resulting normalized edit distance. The question what criteria should d satisfy for ned_{d} to be a metric is long standing. It was recently shown that when d is the uniform weight function (all operations cost 1 except for no-op which costs 0) then ned_{d} is a metric. The question regarding non-uniform weights remained open. In this paper we answer this question by providing a necessary and sufficient condition on d under which ned_{d} is a metric.
Cite as

Dana Fisman and Ilay Tzarfati. When Is the Normalized Edit Distance over Non-Uniform Weights a Metric?. In 35th Annual Symposium on Combinatorial Pattern Matching (CPM 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 296, pp. 14:1-14:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{fisman_et_al:LIPIcs.CPM.2024.14,
  author =	{Fisman, Dana and Tzarfati, Ilay},
  title =	{{When Is the Normalized Edit Distance over Non-Uniform Weights a Metric?}},
  booktitle =	{35th Annual Symposium on Combinatorial Pattern Matching (CPM 2024)},
  pages =	{14:1--14:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-326-3},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{296},
  editor =	{Inenaga, Shunsuke and Puglisi, Simon J.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2024.14},
  URN =		{urn:nbn:de:0030-drops-201247},
  doi =		{10.4230/LIPIcs.CPM.2024.14},
  annote =	{Keywords: Normalized Edit Distance, Non-uniform Weights, Triangle Inequality, Metric}
}
Document
DOI: 10.4230/LIPIcs.CSL.2022.21
Inferring Symbolic Automata

Authors: Dana Fisman, Hadar Frenkel, and Sandra Zilles

Published in: LIPIcs, Volume 216, 30th EACSL Annual Conference on Computer Science Logic (CSL 2022)

Abstract
We study the learnability of symbolic finite state automata, a model shown useful in many applications in software verification. The state-of-the-art literature on this topic follows the query learning paradigm, and so far all obtained results are positive. We provide a necessary condition for efficient learnability of SFAs in this paradigm, from which we obtain the first negative result. The main focus of our work lies in the learnability of SFAs under the paradigm of identification in the limit using polynomial time and data. We provide a necessary condition and a sufficient condition for efficient learnability of SFAs in this paradigm, from which we derive a positive and a negative result.
Cite as

Dana Fisman, Hadar Frenkel, and Sandra Zilles. Inferring Symbolic Automata. In 30th EACSL Annual Conference on Computer Science Logic (CSL 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 216, pp. 21:1-21:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{fisman_et_al:LIPIcs.CSL.2022.21,
  author =	{Fisman, Dana and Frenkel, Hadar and Zilles, Sandra},
  title =	{{Inferring Symbolic Automata}},
  booktitle =	{30th EACSL Annual Conference on Computer Science Logic (CSL 2022)},
  pages =	{21:1--21:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-218-1},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{216},
  editor =	{Manea, Florin and Simpson, Alex},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CSL.2022.21},
  URN =		{urn:nbn:de:0030-drops-157412},
  doi =		{10.4230/LIPIcs.CSL.2022.21},
  annote =	{Keywords: Symbolic Finite State Automata, Query Learning, Characteristic Sets}
}
  • Refine by Author
  • 2 Fisman, Dana
  • 1 Frenkel, Hadar
  • 1 Tzarfati, Ilay
  • 1 Zilles, Sandra

  • Refine by Classification

  • Refine by Keyword
  • 1 Characteristic Sets
  • 1 Metric
  • 1 Non-uniform Weights
  • 1 Normalized Edit Distance
  • 1 Query Learning
  • Show More...

  • Refine by Type
  • 2 document

  • Refine by Publication Year
  • 1 2022
  • 1 2024

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
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact