13 votes
Accepted

Category-theoretic treatment of diffs, patches and merging?

As pointed by Martin, there is some work on the categorical representation of patches. Mimram and Di Giusto's "A Categorical Theory of Patches" being the most extensive categorical approach to edit-...
Victor Miraldo's user avatar
8 votes
Accepted

Find a string with minimal edit distance from a set of given strings

Your problem is called the Median string problem. Nicolas and Rivals proved that the Median String problem (under the Levenshtein distance) is NP-complete even for binary strings.
Mohammad Al-Turkistany's user avatar
8 votes

Category-theoretic treatment of diffs, patches and merging?

There is quite a bit of work in this direction. You could start by looking at [1, 2], but they don't exhaust the topic. S. Mimram, C. Di Giusto, A Categorical Theory of Patches. C. Angiuli, E. ...
Martin Berger's user avatar
6 votes
Accepted

Complexity of Homogenizing a String

This problem is NP-complete, by reduction from Minimum Hitting Set. In minimum hitting set, we are given a universe, $U$, and a set of sets $S$ such that $\forall s \in S, s \subset U$. The objective ...
isaacg's user avatar
  • 806
6 votes

Time complexity for a variant of edit distance

Computing this type of edit distance is NP-complete, which I will prove below by reducing from the NP-complete problem Vertex Cover (given a graph $G$ and a number $k$, determine whether there exists ...
Mikhail Rudoy's user avatar
5 votes
Accepted

L1 / Variational Distance between distributions

Using the relation between total variation and $L_1$/$\ell_1$ distance of the probability/distribution/mass functions, we have $$\begin{align} d_{\rm TV}(D_1, D_2) &= \frac{1}{2}\lVert D_1-D_2\...
Clement C.'s user avatar
  • 4,461
5 votes

Proof of Levenshtein distance

I looked into this last year while teaching. The other answers, including Prof. Erickson's excellent book, feel incomplete, because they handwave a step along the lines of "there is an optimal ...
usul's user avatar
  • 7,615
2 votes

Algorithm for computing unordered tree edit distance

A student of ours recently looked into a dynamic programming A* algorithm for computing the unordered tree edit distance (although we adapted it for the ordered tree edit distance). I was not directly ...
SX.'s user avatar
  • 21
2 votes

Complexity of Homogenizing a String

Look at the number of changes from one letter to the other in your string, which you could see as a measure for the string's inhomogenity. With every (useful) move of a subsequence you reduce this ...
Peter Leupold's user avatar
1 vote

Formal proof of correctness of Levenshtein distance

As pointed out in a comment above, the answer is yes, in Lean. See the paper and the code as linked into comments. I was rather hoping Agda or Idris... but perhaps the Lean formalization is actually ...
Jacques Carette's user avatar
1 vote

Relation between edit distances over different alphabets

Obviously, $L(2^b) \leq L(2)$. The Levenshtein distance is at most the length of the longest string, so $L(2^b) \leq \max(cn,cm) / b$ whereas $L(2) \leq \max(cn,cm)$. You cannot avoid $L(2^b)(S_1,...
Boson's user avatar
  • 560
1 vote

Proof of Levenshtein distance

I'll put my two cents here. First we claim that d[i+1,j+1] >= d[i,j] Here we don't care when s1[j+1] == s2[i+1], but we can use a simple contradiction to prove that in this case d[i+1,j+1]=d[i][j]...
tartaruga_casco_mole's user avatar

Only top scored, non community-wiki answers of a minimum length are eligible