LIPIcs.CSL.2023.20.pdf
- Filesize: 1.48 MB
- 20 pages
Document
A Normalized Edit Distance on Infinite Words
Authors
Dana Fisman 
,
Joshua Grogin ,
Gera Weiss
-
Part of:
Volume:
31st EACSL Annual Conference on Computer Science Logic (CSL 2023)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: Computer Science Logic (CSL) - License:
Creative Commons Attribution 4.0 International license
- Publication Date: 2023-02-01
File
Document Identifiers
Author Details
Cite As Get BibTex
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)
https://doi.org/10.4230/LIPIcs.CSL.2023.20
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.
Subject Classification
ACM Subject Classification
- Theory of computation → Formal languages and automata theory
- Theory of computation → Pattern matching
- Hardware → Robustness
Keywords
- Edit Distance
- Infinite Words
- Robustness
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
- Roderick Bloem, Krishnendu Chatterjee, Karin Greimel, Thomas A. Henzinger, Georg Hofferek, Barbara Jobstmann, Bettina Könighofer, and Robert Könighofer. Synthesizing robust systems. Acta Informatica, 51(3-4):193-220, 2014. URL: https://doi.org/10.1007/s00236-013-0191-5.
- Roderick Bloem, Krishnendu Chatterjee, Karin Greimel, Thomas A. Henzinger, and Barbara Jobstmann. Specification-centered robustness. In Industrial Embedded Systems (SIES), 2011 6th IEEE International Symposium on, SIES 2011. Vasteras, Sweden, June 15-17, 2011, pages 176-185, 2011. URL: https://doi.org/10.1109/SIES.2011.5953660.
-
Pavol Cerný, Thomas A. Henzinger, and Arjun Radhakrishna. Simulation distances. Theor. Comput. Sci., 413(1):21-35, 2012.
- Krishnendu Chatterjee, Laurent Doyen, and Thomas A. Henzinger. Quantitative languages. ACM Trans. Comput. Log., 11(4):23:1-23:38, 2010. URL: https://doi.org/10.1145/1805950.1805953.
-
Colin de la Higuera and Luisa Micó. A contextual normalised edit distance. In Proceedings of the 24th International Conference on Data Engineering Workshops, ICDE 2008, April 7-12, 2008, Cancún, Mexico, pages 354-361. IEEE Computer Society, 2008.
-
Emmanuel Filiot, Nicolas Mazzocchi, Jean-François Raskin, Sriram Sankaranarayanan, and Ashutosh Trivedi. Weighted transducers for robustness verification. In 31st International Conference on Concurrency Theory, CONCUR 2020, September 1-4, 2020, Vienna, Austria (Virtual Conference), pages 17:1-17:21, 2020.
- 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. To appear (meantime available on arxiv). URL: http://arxiv.org/abs/2201.06115.
- Erich Grädel, Wolfgang Thomas, and Thomas Wilke, editors. Automata, Logics, and Infinite Games: A Guide to Current Research [outcome of a Dagstuhl seminar, February 2001], volume 2500 of Lecture Notes in Computer Science. Springer, 2002. URL: https://doi.org/10.1007/3-540-36387-4.
- Joshua Grogin. A normalized edit distance on finite and infinite words, Master Thesis, Ben-Gurion University of the Negev, March 2022. URL: https://jgrogin.github.io/A_Normalized_Edit_Distance_on_Finite_and_Infinite_Words_thesis.pdf.
- H. J. Hoogeboom and G. Rozenberg. Infinitary languages: Basic theory and applications to concurrent systems, pages 266-342. Springer Berlin Heidelberg, Berlin, Heidelberg, 1986. URL: https://doi.org/10.1007/BFb0027043.
- Richard Johnsonbaugh. A Discrete Intermediate Value Theorem. https://www.maa.org/sites/default/files/0746834259610.di020780.02p0372v.pdf, 1998. The College Mathematical Journal.
- Richard M. Karp. A characterization of the minimum cycle mean in a digraph. Discret. Math., 23(3):309-311, 1978. URL: https://doi.org/10.1016/0012-365X(78)90011-0.
-
Vladimir Iosifovich Levenshtein. Binary codes capable of correcting deletions, insertions and reversals. Soviet Physics Doklady, 10(8):707-710, February 1966. Doklady Akademii Nauk SSSR, V163 No4 845-848 1965.
-
Yujian Li and Bi Liu. A normalized levenshtein distance metric. IEEE Trans. Pattern Anal. Mach. Intell., 29(6):1091-1095, 2007.
-
Andrés Marzal and Enrique Vidal. Computation of normalized edit distance and applications. IEEE Trans. Pattern Anal. Mach. Intell., 15(9):926-932, 1993.
- Daniel Neider, Alexander Weinert, and Martin Zimmermann. Robust, expressive, and quantitative linear temporal logics: Pick any two for free. In Proceedings Tenth International Symposium on Games, Automata, Logics, and Formal Verification, GandALF 2019, Bordeaux, France, 2-3rd September 2019, pages 1-16, 2019. URL: https://doi.org/10.4204/EPTCS.305.1.
- Paulo Tabuada and Daniel Neider. Robust linear temporal logic. In 25th EACSL Annual Conference on Computer Science Logic, CSL 2016, August 29 - September 1, 2016, Marseille, France, pages 10:1-10:21, 2016. URL: https://doi.org/10.4230/LIPIcs.CSL.2016.10.