RO EN
About Applications of Distances on Monoids of Strings
Authors: Mitrofan Choban, Ivan Budanaev
Keywords: String pattern matching, parallel decomposition, semiparallel decomposition, free monoid, invariant distance, quasimetric, Levenshtein distance, Hamming distance, proper similarity.
– 0.16 Mb
Keywords: String pattern matching, parallel decomposition, semiparallel decomposition, free monoid, invariant distance, quasimetric, Levenshtein distance, Hamming distance, proper similarity.
Abstract
In this article we show that there are invariant distances on the monoid $L(A)$ of all strings closely related to Levenshtein's distance. We will use a distinct definition of the distance on $L(A)$, based on the Markov -â Graev method, proposed by him for free groups. As result we will show that for any quasimetric $d$ on alphabet $A$ in union with the empty string there exists a maximal invariant extension $d^*$ on the free monoid $L(A)$. This new approach allows the introduction of parallel and semiparallel decompositions of two strings. In virtue of \mbox{Theorem \ref{theorem1}}, they offer various applications of distances on monoids of strings in solving problems from distinct scientific fields. The discussion covers topics in fuzzy strings, string pattern search, DNA sequence matching etc.Mitrofan Choban
Professor, Doctor of Science,
Academician of the Academy of Science of Moldova
Tiraspol State University, Republic of Moldova
str. Iablochkin 5, Chisinau, Moldova
Phone: +373 22 754906
E-mail:
Ivan Budanaev
Doctoral School of Mathematics and Information Science
Institute of Mathematics and Computer Sciences of ASM
Tiraspol State University, Republic of Moldova
str. Academiei, 3/2, MD-2028, Chisinau, Moldova
Phone:+373 60926999
E-mail:
Professor, Doctor of Science,
Academician of the Academy of Science of Moldova
Tiraspol State University, Republic of Moldova
str. Iablochkin 5, Chisinau, Moldova
Phone: +373 22 754906
E-mail:
Ivan Budanaev
Doctoral School of Mathematics and Information Science
Institute of Mathematics and Computer Sciences of ASM
Tiraspol State University, Republic of Moldova
str. Academiei, 3/2, MD-2028, Chisinau, Moldova
Phone:+373 60926999
E-mail:
This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License
Fulltext
– 0.16 Mb
Contents
- Propositional inquisitive logic: a survey
- "The absence of the difference from a pot is potness" - Axiomatic Proofs of Theorems Concerning Negative Properties in Navya-Nyāya
- About Applications of Distances on Monoids of Strings
- Insertion Modeling and Its Applications
- Proving Properties of Programs on Hierarchical Nominative Data
- Natural Language Processing versus Logic. Pros and cons on the dispute whether logic is useful in the computational interpretation of language
- Executable choreographies applied in OPERANDO
