17

Just to get things going, rather than trying to close out this problem: there is an obvious nondeterministic algorithm using logarithmically many bits of space (search for a single path through the dynamic programming matrix) so by Savitch's theorem there is a deterministic algorithm with space $O(\log^2 n)$. Its time must be of the form $n^{O(\log n)}$, ...


13

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-scripts as used by the UNIX diff. In their sense, you have what you want. The objects are finite sequences of words over an alphabet $L$, seen as a mapping $A : [...


8

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. Morehouse, D. R. Licata, R. Harper, Homotopical Patch Theory.


8

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.


6

Elaborating Paul's suggestion for a $O(n \log n)$-time algorithm: Input: Let $u \in [m]^k$ and $v \in [m]^n$ with $k \leq n$, where $U=[m]=\{1,2,\cdots,m\}$. Define polynomials $$p(x,y) = \sum_{i \in [n]} x^i y^{v_i} \qquad \text{and} \qquad q(x,y) = \sum_{j \in [k]} x^{k-j} y^{m-u_j}.$$ Compute the polynomial $$r(x,y) = p(x,y) q(x,y).$$ Then $$r(x,y) = \...


6

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 is to find $H \subset U$ of smallest size such that $\forall s \in S, \exists h \in H$ such that $h \in s$. The reduction is as follows: The string is as ...


5

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\rVert_1 = \frac{1}{2}\lVert \beta D_2 +(1-\beta)D_3 - D_2\rVert_1\\ &= \frac{1-\beta}{2}\lVert D_3 - D_2\rVert_1 = (1-\beta)d_{\rm TV}(D_2, D_3). \end{align}$$


4

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 a set of vertices $C$ with $|C|\le k$ such that each edge in $G$ has at least one vertex in $C$, aka a vertex cover of size at most $k$). Helpful subproblem ...


3

Actually, the Damerau–Levenshtein distance is a metric. (See, for example, §11.1 of Encyclopedia of Distances, by Deza & Deza, Springer, 2009.) That is, it does obey the triangle inequality. This can be seen quite easily if you view every possible string as a node, with the edit operations and transpositions between them as edges. The Damerau–Levenshtein ...


3

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 edit sequence that proceeds left-to-right" or "we start by lining up the two words in columns vertically...." (Even if that feels obvious, can you ...


3

Hint: Express the binary vectors as a polynomial with coefficients in {-1,0,1} and obtain the hamming distance of u with all length k contiguous subsequences of v through a polynomial multiplication. Use Fourier transforms to improve the complexity to what you need.


2

Look up the concept of anticodes. Some bounds exist. Also if you have a linear $t-$error correcting code over $GF(q)$ with length $n$ and covering radius $r$ and use homogeneity under translations by adding vectors $n-d=n-2t-1$ would seem to be your answer but I haven't checked carefully. Cohen and Litsyn have a book on covering codes. A Simple ...


2

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 involved into this project, but as far as I know, this algorithm explores a search tree that represents all possible edit distances and stops exploring ...


2

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 number by one if the subsequence you move is preceded and followed by two distinct letters. Otherwise you reduce the inhomogenity by two. So for a string with k ...


1

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


1

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,S_2) = L(2)(S_1,S_2)$ when $L(2)(S_1,S_2) \leq \max(cn,cm) / b$: consider for instance $b = c = 2$, $S_1 = 0^{2n}$ and $S_2 = (01)^{p} (00)^{n-p}$. When $L(2)(...


1

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]. Now we consider when s1[j+1] != s2[i+1]. If we want to make d[i+1,j+1] < d[i,j], by intuition, we have to make either s1[i+1] or s[j+1] match something. ...


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