Spearman Permutation Distances and Shannon's Distinguishability

• Autorzy: Bortolussi L. , Dinu L.P. , Sgarro A.
• Języki publikacji: EN

Abstrakty

EN

Spearman distance is a permutation distance which might be used for codes in permutations beside Kendall distance. However, Spearman distance gives rise to a geometry of strings, which is rather unruly from the point of view of error correction and error detection. Special care has to be taken to discriminate between the two notions of codeword distance and codeword distinguishability. This stresses the importance of rejuvenating the latter notion, extending it from Shannon's zero-error information theory to the more general setting of metric string distances.

Słowa kluczowe

EN

Shannon theory; codeword distinguishability; Spearman footrule distance; rank distance

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2012
• Tom: Vol. 118, nr 3
• Strony: 245--252
• Opis fizyczny: Bibliogr. 12 poz., tab.

Twórcy

autor

Bortolussi L.

autor

Dinu L.P.

autor

Sgarro A.

• University of Bucharest, Faculty of Mathematics and Computer Science, Academiei 14, 010014, Bucharest, Romania,

Bibliografia

• [1] Al. Barg, A. Mazumdar. Codes in Permutations and Error Correction for Rank Modulation. IEEE Trans. Inform. Th., 56 (7) 3158-3165,2010.
• [2] L. Bortolussi, A. Sgarro. Possibilistic Coding: Error Detection vs. Error Correction, in Combining Soft Computing and Statistical Methods in Data Analysis, ed. by Ch. Borgelt et alt., Advances in Intelligent and Soft Computing 77, Springer Vcrlag, 41-48,2010.
• [3] A. Condon, R.M. Corn, and A. Marathe. On Combinatorial DNA Word Design. Journal of Computational Biology, 8(3), 201-220, November 2001.
• [4] Fr.J. Damerau. A Technique for Computer Detection and Correction of Spelling Errors. Communications of the ACM, 7 (3) 171-176,1964
• [5] E. Deza, M.M. Deza. Dictionary of Distances. Elsevier, Amsterdam, 2006
• [61 P. Diaconis, R.L. Graham, Spearman Footrule as a Measure of Disarray, Journal of Royal Statistical Society. Series B Methodological, 39(2), 262-268,1977
• [7] L.P. Dinu, A. Sgarro. A Low-Complexity Distance for DNA Strings. Fundamenta Informaticae, 73(3), 361-372,2006
• [8] J. Kórner, A. Orlitsky. Zero-error information theory. IEEE Trans. Inform. T/i., 44 (6) 2207-2229,1998.
• [9] J van Lint. Introduction to Coding Theory. Springer Verlag, Berlin, 1999.
• [10] Cl. E. Shannon. The Zero-Error Capacity of a Noisy Channel. IRE Trans. Inform. Th., 2, 8-19, 1956.
• [11] A. Sgarro. Possibilistic Information Theory, a Coding-Theoretic Approach. Fuzzy Sets and Systems, 132-1, 11-32,2002.
• [12] P. Walley, Peter (1991). Statistical Reasoning with Imprecise Probabilities. Chapman and Hall, London, 1991.