Geodesic
Isometry groups of formal languages for generalized Levenshtein distances
Matematičeskie zametki, Tome 116 (2024) no. 2, pp. 306-315.

Voir la notice de l'article provenant de la source Math-Net.Ru

The paper gives a partial answer to the question of which groups can be represented as isometry groups of formal languages for generalized Levenshtein distances. Namely, it is proved that, for any language, the absolute value of the difference between the length of any of its words and the length of the image of this word under an isometry with respect to an arbitrary generalized Levenshtein distance is bounded above by a constant that depends only on the language, provided that the distance satisfies the condition that the weight of the substitution operation is less than the doubled weight of the deletion operation. It follows, in particular, that the isometry groups of formal languages for such distances always embed into the group $\Pi_{n=l}^\infty S_{n}$. A number of examples showing that this estimate is unimprovable in a certain sense are also constructed.
Keywords: formal language, generalized Levenshtein distance. 
@article{MZM_2024_116_2_a10,
     author = {V. O. Yankovskiy},
     title = {Isometry groups of formal languages for generalized {Levenshtein} distances},
     journal = {Matemati\v{c}eskie zametki},
     pages = {306--315},
     publisher = {mathdoc},
     volume = {116},
     number = {2},
     year = {2024},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/MZM_2024_116_2_a10/}
}
TY  - JOUR
AU  - V. O. Yankovskiy
TI  - Isometry groups of formal languages for generalized Levenshtein distances
JO  - Matematičeskie zametki
PY  - 2024
SP  - 306
EP  - 315
VL  - 116
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/MZM_2024_116_2_a10/
LA  - ru
ID  - MZM_2024_116_2_a10
ER  - 
%0 Journal Article
%A V. O. Yankovskiy
%T Isometry groups of formal languages for generalized Levenshtein distances
%J Matematičeskie zametki
%D 2024
%P 306-315
%V 116
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/MZM_2024_116_2_a10/
%G ru
%F MZM_2024_116_2_a10
V. O. Yankovskiy. Isometry groups of formal languages for generalized Levenshtein distances. Matematičeskie zametki, Tome 116 (2024) no. 2, pp. 306-315. http://geodesic.mathdoc.fr/item/MZM_2024_116_2_a10/

[1] V. I. Levenshtein, “Dvoichnye kody s ispravleniem vypadenii, vstavok i zameschenii simvolov”, Dokl. AN SSSR, 163:4 (1965), 845–848 | MR | Zbl

[2] R. Wagner, M. Fisher, “The string-to-string correction problem”, J. Assoc. Comput. Mach., 21 (1974), 168–178 | DOI | MR

[3] A. A. Markov, “O preobrazovaniyakh, ne rasprostranyayuschikh iskazheniya”, Izbrannye trudy, v. 2, M., 1956, 70–94 | MR

[4] W. C. Huffman, “Codes and groups”, Handbook of Coding Theory, v. 2, North-Holland, Amsterdam, 1998, 1345–1440 | MR

[5] R. Bienert, B. Klopsch, “Automorphism groups of cyclic codes”, J. Algebraic Combin., 31:1 (2010), 33–52 | DOI | MR

[6] P. E. Ruth, M. E. Ladser, Levenshtein graphs: resolvability, automorphisms and determining sets, arXiv: abs/2107.06951

[7] G. Higman, “Ordering by divisibility in abstract algebras”, Proc. London Math. Soc. (3), 2 (1952), 326–336 | DOI | MR

[8] R. Frucht, “Graphs of degree three with a given abstract group”, Canad. J. Math., 1 (1949), 365–378 | DOI | MR