13
votes
1answer
208 views

Is there an unambiguous CFL whose complement is not context-free?

I'm doing a little bit of research about context-free languages. A question that's popped up is whether or not there exists an unambiguous context-free language whose complement is not a context-free ...
8
votes
2answers
1k views

palindromic subsequences

I'd like any insight or references to the following two conjectures (see the glossary below for definitions): Conjecture 1: For any string $x$, there exists a longest common subsequence of $x$ and ...
7
votes
3answers
963 views

How to characterize a Self-avoiding path.

I cannot find any answer to that apparently simple problem : On a square lattice, a path is given by a sequence of relative moves in {"move forward", "turn right" and "turn left"}. Is there a rule ...