On the size distribution of the fixed-length Levenshtein balls with radius one

Wang, Geyang1,2; Wang, Qi3,4

2024-04-01

10.1007/s10623-024-01382-1

DESIGNS CODES AND CRYPTOGRAPHY   影响因子和分区

0925-1022

1573-7586

The fixed-length Levenshtein (FLL) distance between two words x,y is an element of Zmn\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\varvec{x}, \varvec{y}\in \mathbb {Z}_m<^>n$$\end{document} is the smallest integer t such that x\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\varvec{x}$$\end{document} can be transformed to y\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\varvec{y}$$\end{document} by t insertions and t deletions. The size of a ball in the FLL metric is a fundamental yet challenging problem. Very recently, Bar-Lev, Etzion, and Yaakobi explicitly determined the minimum, maximum and average sizes of the FLL balls with radius one, respectively. In this paper, based on these results, we further prove that the size of the FLL balls with radius one is highly concentrated around its mean by Azuma's inequality.

Levenshtein ball Fixed-length Levenshtein distance Azuma's inequality

SCI ; EI

英语

通讯

Computer Science ; Mathematics

Computer Science, Theory & Methods ; Mathematics, Applied

WOS:001197351100001

SPRINGER

20241515851636

Combinatorial Mathematics, Includes Graph Theory, Set Theory:921.4

COMPUTER SCIENCE

Web of Science

1.Univ Maryland, Dept Elect & Comp Engn, College Pk, MD 20742 USA
2.Univ Maryland, Inst Syst Res, College Pk, MD 20742 USA
3.Southern Univ Sci & Technol, Dept Comp Sci & Engn, Shenzhen 518055, Guangdong, Peoples R China
4.Southern Univ Sci & Technol, Natl Ctr Appl Math Shenzhen, Shenzhen 518055, Guangdong, Peoples R China

Wang, Geyang,Wang, Qi. On the size distribution of the fixed-length Levenshtein balls with radius one[J]. DESIGNS CODES AND CRYPTOGRAPHY,2024,92:2253-2265.

Wang, Geyang,&Wang, Qi.(2024).On the size distribution of the fixed-length Levenshtein balls with radius one.DESIGNS CODES AND CRYPTOGRAPHY,92,2253-2265.

Wang, Geyang,et al."On the size distribution of the fixed-length Levenshtein balls with radius one".DESIGNS CODES AND CRYPTOGRAPHY 92(2024):2253-2265.