Is there a standard term for the relation on sequences where two sequences are related iff they have a finite Levenshtein distance, or for the equivalence classes it induces?
Finite Levenshtein distance?
1
$\begingroup$
combinatorics
general-topology
sequences-and-series
terminology
metric-spaces
-
0Are you referring to [this levenshtein distance?](http://en.wikipedia.org/wiki/Levenshtein_distance). Because I think if the sequences are infinite, that levenshtein distance would imply that they both diverge or converge to the same limit. – 2011-08-22
-
0@Peláez: Yes, that one -- are there others? – 2011-08-22
-
0The sequences I'm looking at will rarely have limits, so that aspect is not interesting to me. I'm more interested in seeing that, e.g., the primes are in the same class as the odd primes but in a different class than odd numbers. – 2011-08-22
-
0I’ve never encountered a term for it. I’d probably say that the sequences were *eventually equal modulo finite shifts*. – 2011-08-23
-
0@Peláez: Having finite Levenshtein distance is much stronger than having the same convergence behavior: sequences $\sigma$ and $\tau$ have finite Levenshtein distance iff there are $n,m\in\omega$ such that $\sigma(n+k)=\tau(m+k)$ for all $k\in\omega$. – 2011-08-23
-
0@Brian: Yeah, that was what I was thinking. Thanks :) – 2011-08-23
-
0@Charles: I am just used to see the levenshtein distance in an algorithmical context, so I thought there may be another one for infinite sequences. Anyway, I have seen some books that call this sequences "ultimately equal". – 2011-08-23
-
0@Peláez: I searched the term to see how it was used. Sohrab's Basic Real Analysis uses the "ultimately equal" to mean finite Hamming distance. Allouche & Shallit use it as a relation between a sequence and a scalar (Allouche uses it the same way in a paper). Higman ("Some countably free groups") uses it to mean a countable Hamming distance. Risley & Zamboni ("A generalization of Sturmian...") don't define it, but context suggests finite Levenshtein distance. Berstela 2006 uses it in the same sense as Allouche. Wada 1953 uses it in the same sense as Sohrab. So there's not much uniformity. – 2011-08-23