Skip to main content
Computer Science

Timeline for Is the language of pairs of words of equal length whose hamming distance is 2 or greater context-free?

Current License: CC BY-SA 3.0

56 events
when toggle format what by license comment
Jun 25, 2013 at 1:26 history wiki removed Shog9
Jun 20, 2013 at 13:29 comment added Vor @babou: if you want take a look at my answer (mutual proof shoot-down :-)
Jun 18, 2013 at 0:27 history edited babou CC BY-SA 3.0
added 25 characters in body
Jun 17, 2013 at 12:54 history edited babou CC BY-SA 3.0
added 335 characters in body
Jun 17, 2013 at 12:33 comment added babou @Vor Thinking about it, I am pretty sure it is the anchoring that failed. There is a simple grammar for your language that will allow the $y$ only on the second $1$. Hence the anchoring must be wrong. The problem is that I get only one marked symbol in $xz$. It can be in $x$ but I have no bound on the length of $x$. I think a version of the lemma also has a marked symbol in $y$, but again without a bound on the size of $y$. Hence, I am pumping on the wrong side. If this explains it, it would leave the lemma extension OK. But it must exist somewhere.
Jun 17, 2013 at 12:14 comment added babou @Vor Actually, your Language $L'$ is even deterministic. And I do not see off hand why the proof should not apply. Indeed, I use only strings in $L'$. So your example is very appropriate. But off-hand I do not see where I erred. My first bet is that I lost something in the achoring of the substrings on marked symbols because of the erasure. But I am really not sure. The other point that bothered me is that such an extension to Ogden's lemma should be known if correct. But I found no trace. I have no one to exchange ideas with right now, and my books are in boxes. It does not help.
Jun 17, 2013 at 10:05 comment added Vor @babou: I'm trying to understand the proof; $L' = \{ w \mid w = uv = 10^i10^j, |u|=|v|, d(u,v)\geq 2 \}$ is context free (guess the middle, check that the two halves have the same length, accept if w begins with a 1, contains exactly another 1 and the second half begins with a zero). Why can't your proof be applied to $L'$?
Jun 17, 2013 at 6:26 history edited babou CC BY-SA 3.0
added 56 characters in body
Jun 16, 2013 at 17:26 history edited babou CC BY-SA 3.0
added 4 characters in body
Jun 16, 2013 at 13:56 history edited babou CC BY-SA 3.0
deleted 12 characters in body
Jun 16, 2013 at 12:56 history edited babou CC BY-SA 3.0
added 10 characters in body
Jun 16, 2013 at 12:43 history edited babou CC BY-SA 3.0
added 46 characters in body
Jun 16, 2013 at 12:35 history edited babou CC BY-SA 3.0
added 46 characters in body
Jun 16, 2013 at 12:30 history edited babou CC BY-SA 3.0
added 46 characters in body
Jun 16, 2013 at 12:24 history edited babou CC BY-SA 3.0
added 46 characters in body
Jun 16, 2013 at 12:06 history edited babou CC BY-SA 3.0
added 61 characters in body
Jun 16, 2013 at 10:59 history edited babou CC BY-SA 3.0
added 61 characters in body
Jun 16, 2013 at 9:36 history edited babou CC BY-SA 3.0
deleted 32 characters in body
Jun 16, 2013 at 9:12 history edited babou CC BY-SA 3.0
added 69 characters in body
Jun 16, 2013 at 8:56 history edited babou CC BY-SA 3.0
added 128 characters in body
Jun 16, 2013 at 8:01 history edited babou CC BY-SA 3.0
deleted 8 characters in body
Jun 16, 2013 at 7:55 history edited babou CC BY-SA 3.0
deleted 8 characters in body
Jun 16, 2013 at 7:49 history undeleted babou
Jun 16, 2013 at 7:49 history edited babou CC BY-SA 3.0
added 233 characters in body
Jun 16, 2013 at 7:31 history edited babou CC BY-SA 3.0
added 1588 characters in body
Jun 13, 2013 at 16:33 history edited babou CC BY-SA 3.0
added 118 characters in body
Jun 13, 2013 at 12:26 history edited babou CC BY-SA 3.0
deleted 272 characters in body
Jun 12, 2013 at 21:14 history edited babou CC BY-SA 3.0
deleted 1509 characters in body
Jun 12, 2013 at 14:28 history edited babou CC BY-SA 3.0
added 1974 characters in body
Jun 12, 2013 at 10:52 history edited babou CC BY-SA 3.0
still incorrect
Jun 12, 2013 at 10:49 history deleted babou
Jun 12, 2013 at 10:15 history edited babou CC BY-SA 3.0
typo on the third proof (hopefully the right one)
Jun 12, 2013 at 10:07 history undeleted babou
Jun 12, 2013 at 10:06 history edited babou CC BY-SA 3.0
deleted 60 characters in body
Jun 12, 2013 at 9:37 history edited babou CC BY-SA 3.0
deleted 1780 characters in body
Jun 12, 2013 at 9:25 history edited babou CC BY-SA 3.0
deleted 1780 characters in body
Jun 11, 2013 at 19:50 history deleted babou
Jun 11, 2013 at 19:48 comment added babou I guess i'm getting old ... and I am doing administrative work at the same time.
Jun 11, 2013 at 19:00 history edited babou CC BY-SA 3.0
added 1 characters in body
Jun 11, 2013 at 18:55 history edited babou CC BY-SA 3.0
added 1 characters in body
Jun 11, 2013 at 18:10 history edited babou CC BY-SA 3.0
edited body
Jun 11, 2013 at 18:06 comment added sdcvvc While $L$ might be the image of $M$, $M$ is not the inverse image of $L$, and I doubt this can easily be fixed. Also I would remove the clearly wrong part, the mistake is elementary and it's doubtful it will help.
Jun 11, 2013 at 17:58 comment added babou @HendrikJan Did I goof again ? (BTW, thanks for making it a discussion)
Jun 11, 2013 at 17:39 history edited babou CC BY-SA 3.0
more precision
Jun 11, 2013 at 17:32 history edited babou CC BY-SA 3.0
more precision
Jun 11, 2013 at 17:17 history edited babou CC BY-SA 3.0
typo
Jun 11, 2013 at 17:07 history edited babou CC BY-SA 3.0
changed wrong answer into hopefully a correct one
Jun 11, 2013 at 17:01 history edited babou CC BY-SA 3.0
added 714 characters in body
Jun 11, 2013 at 14:16 history edited babou CC BY-SA 3.0
deleted 155 characters in body
Jun 11, 2013 at 14:04 comment added babou Should I leave this wrong answer ? It is somehow helping, I think, as it make the problem suspiciously similar to ${a^ib^jc^ka^ib^jc^k}$. The problem is that rules of the site are not intended to encourage wrong results for discussion ( I mean I do not enjoy downvotes more than anyone else).
Jun 11, 2013 at 14:00 comment added Hendrik Jan I recognized the argument (because I could not make it work when I tried myself).
Jun 11, 2013 at 13:57 history edited babou CC BY-SA 3.0
wrong answer
Jun 11, 2013 at 13:50 history edited babou CC BY-SA 3.0
added 52 characters in body
Jun 11, 2013 at 13:45 comment added babou you are correct ... I goofed ... now I know what was nagging me at the back of my head.
Jun 11, 2013 at 13:36 comment added Hendrik Jan Note however that the pass over the second half reads the stack in reverse. That seems to mean that the two positions are in the same position in both halves, but in reverse?
Jun 11, 2013 at 13:24 history answered babou CC BY-SA 3.0
toggle format