On an Alternative Sequence Comparison Statistic of Steele
Discrete Mathematics and Theoretical Computer Science, cilt.22, sa.1, 2020 (SCI-Expanded, Scopus)
- Yayın Türü: Makale / Tam Makale
- Cilt numarası: 22 Sayı: 1
- Basım Tarihi: 2020
- Doi Numarası: 10.23638/dmtcs-22-1-18
- Dergi Adı: Discrete Mathematics and Theoretical Computer Science
- Derginin Tarandığı İndeksler: Science Citation Index Expanded (SCI-EXPANDED), Scopus, Academic Search Premier, Applied Science & Technology Source, Compendex, Computer & Applied Sciences, INSPEC, MathSciNet, zbMATH, Directory of Open Access Journals
- Anahtar Kelimeler: central limit theorem, longest common subsequences, random words, similarity measures
- Açık Arşiv Koleksiyonu: AVESİS Açık Erişim Koleksiyonu
- Boğaziçi Üniversitesi Adresli: Evet
Özet
The purpose of this paper is to study a statistic that is used to compare the similarity between two strings, which is first introduced by Michael Steele in 1982. It was proposed as an alternative to the length of the longest common subsequences, for which the variance problem is still open. Our results include moment asymptotics and distributional asymptotics for Steele’s statistic and a variation of it in random words.