I came across following problem:
Let $L_1$ and $L_2$ are two languages and both of them are accepted by DPDA. If $L=L_1-L_2$ is any language, then what is the smallest language family $L'$ belongs to?
I know DCFLs are not closed under set difference operation. Neither do CFL are closed. However CSLs are closed under set difference operation. So $L$ must be CSL. CSLs are also closed under complementations. Thus, $L'$ must be CSL. But when checked the solution, it gave $L'$ must be recursive. The reason given was:
If CFL $\cap$ CFL is accepted in time complexity $\leq O(2^n)$,then $L'$ will be CSL. If it is accepted in time complexity $>O(2^n)$, then it will be recursive.
However I dont really get what does this means. I have never used time complexity logic to decide which language family given language belongs to. Can someone explain? Also if that does means something, isnt it wrong to say CSLs are closed under intersection and complementation? Why we have to disregard CSL bound can call them recursive?