Abstract:
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.
Citation:
V. O. Yankovskiy, “Isometry groups of formal languages for generalized Levenshtein distances”, Mat. Zametki, 116:2 (2024), 306–315; Math. Notes, 116:2 (2024), 373–381