# Tag Info

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