# Tagged Questions

**11**

votes

**1**answer

145 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

**2**answers

995 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

**3**answers

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