August 13th, 2012

beartato phd

(no subject)

Here's a cute puzzle:

Define a edit distance function d(x,y) between strings x and y to be the minimum number of steps to get from x to y allowing only insertions and deletions of characters at the beginning of the string. For example, d("foo", "baroo") is 4: there's four hops in the sequence "foo", "oo", "roo", "aroo", "baroo".

Does there exist a bijection
 f : string + string -> string

and a number n such that
d(f(inl(x)), x) < n
d(f(inr(x)), x) < n

? That is, can you embed string + string into string with bounded prefix-edit-distance?
Finding such a function that's merely an injection is trivial. Just prefix with one character in one branch, another character in the other branch.
fun f s = case s of inl(x) => "!" ^ x | inr(x) => "#" ^ x

But how can you make it a bijection?

Collapse )

Variation 1: is it possible to write such a bijection (still prefix-edit-distance-bounded) that doesn't have to inspect an unbounded amount of the input string? I don't actually know off the top of my head, and I suspect not, since it sounds like a strong sort of continuity requirement, and I'm not sure that string is so "topologically" isomorphic to string + string.

Variation 2: is it possible to write such a bijection (still prefix-edit-distance-bounded) with only one "escape" character? That is, the edit-distance function only permits insertions or deletions of a single character, rather than the two characters "!" and "#" that are used above? I also suspect not.