Characterization of Isometric Words based on Swap and Mismatch Distance

التفاصيل البيبلوغرافية
العنوان: Characterization of Isometric Words based on Swap and Mismatch Distance
المؤلفون: Anselmo, M., Castiglione, G., Flores, M., Giammarresi, D., Madonia, M., Mantaci, S.
سنة النشر: 2024
المجموعة: Computer Science
مصطلحات موضوعية: Computer Science - Formal Languages and Automata Theory
الوصف: In this paper we consider an edit distance with swap and mismatch operations, called tilde-distance, and introduce the corresponding definition of tilde-isometric word. Isometric words are classically defined with respect to Hamming distance and combine the notion of edit distance with the property that a word does not appear as factor in other words. A word f is said tilde-isometric if, for any pair of f-free words u and v, there exists a transformation from u to v via the related edit operations such that all the intermediate words are also f -free. This new setting is here studied giving a full characterization of the tilde-isometric words in terms of overlaps with errors.
نوع الوثيقة: Working Paper
URL الوصول: http://arxiv.org/abs/2404.13577
رقم الأكسشن: edsarx.2404.13577
قاعدة البيانات: arXiv