Affiliations: [a] Department of Computer Science, University of Salerno, Italy | [b] Department of Mathematics and Computer Science, University of Palermo, Italy | [c] Department of Mathematics and Computer Science, University of Catania, Italy
Abstract: Isometric words are those words whose occurrence as a factor in a transformation of a word u in a word v can be avoided, while preserving the minimal length of the transformation. Such minimal length refers to a distance between u and v. In the literature, isometric words have been considered with respect to the Hamming distance and the Lee distance; the former especially for binary words, while the latter for k-ary words, with k⩾2. Ham- and Lee- isometric words have been characterized in terms of their overlaps with errors. In this paper, we give algorithms to decide whether a word f, of length n, is Ham- or Lee-isometric and provide evidence of the possible non-isometricity by returning a pair of words of minimal length whose transformation cannot avoid the factor f. Such a pair of words is called a pair of witnesses and the minimal length of the witnesses is called the index of f. The algorithms run in O(n) time with a preprocessing of O(n) time and space to construct a data structure that allows answering LCA queries on the suffix tree of f in constant time. The correctness of the algorithms lies on some theoretical results on the index and the witnesses of a word that are here presented. The investigation on the index is completed by the characterization of words with minimum/maximum index. All the results are shown referring to both Hamming and Lee distance.
Keywords: Isometric words, words avoiding factors, index of a word, overlap, Hamming and Lee distances, k-ary n-cube
DOI: 10.3233/COM-230441
Journal: Computability, vol. 13, no. 3-4, pp. 199-222, 2024
