The 2024 Developer Survey results are live! See the results

# Tag Info

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-...
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.

### 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. ...
• 11.5k

### 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 ...
• 2,873
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 ...
• 806

### 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 ...
• 7,738
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\...
• 4,481

### 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 ...
• 21

### 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 ...
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 ...
• 1,540
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]...

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