What is known about $CFL \cap coCFL$? CFL is the class of context-free languages; co-CFL the languages whose complements are context-free.  So CFL $\neq$ co-CFL.

Are there any nice characterizations or other basic facts about CFL $\cap$ co-CFL?

Two easy examples of the kind of fact I have in mind (but one would like more precise information):


DCFL $\subseteq$ CFL $\cap$ co-CFL.
pCFL $\subseteq$ CFL $\cap$ co-CFL, where pCFL is the class of CFLs that are permutation-closed.  It's closed under complement by Parikh's theorem and the fact that semilinear sets are definable in Presburger arithmetic.


Another related question: given a CFL $L$, it's undecidable whether $L \in$ DCFL.  Is the same true for pCFL?
About the last question, the usual undecidability proof for universality could be adapted.

Recall that in this proof, one considers an instance $\langle \Sigma,\Delta,u,v\rangle$ of Post's correspondence problem, where $\Sigma$ and $\Delta$ are two disjoint alphabets, and $u$ and $v$ are two homomorphisms from $\Sigma^\ast$ to $\Delta^\ast$.  Then $$L_u=\{a_1\cdots a_n(u(a_1\cdots a_n))^R\mid n&gt;0\wedge\forall 0&lt;i\leq n.a_i\in\Sigma\}$$ and $$L_v=\{a_1\cdots a_n(v(a_1\cdots a_n))^R\mid n&gt;0\wedge\forall 0&lt;i\leq n.a_i\in\Sigma\}$$&mdash;where $w^R$ denotes the reversal of word $w$&mdash;are two DCFLs s.t. $L_u\cap L_v=\emptyset$ iff the original PCP instance was negative.  Letting $$L=\overline{L_u}\cup\overline{L_v}\;,$$one thus defines a CFL (since DCFLs are effectively closed under complement and CFLs under union), which is universal, i.e. equal to $(\Sigma\cup\Delta)^\ast$, iff the original PCP instance was negative.

Now, if $L$ is universal, i.e. if $L=(\Sigma\cup\Delta)^\ast$, then $L$ is closed under permutations.  Conversely, if $L$ is not universal, i.e. if $L_u\cap L_v\neq\emptyset$, there is at least one word $x$ of form $x=w(u(w))^R=w(v(w))^R$ for some $w$ in $\Sigma^+$.  Then $x$ does not belong to $L$, but it's easy to find a permutation of $x$ that belongs to $L$: for instance, permute the last letter of $w$ (which is in $\Sigma$) with the first of $(u(w))^R$ (which is in $\Delta$) to obtain a word in $\Sigma^\ast\Delta\Sigma\Delta^\ast\subseteq L$.

Hence $L$ is closed under permutation iff it is universal iff the original PCP instance was negative.