0
$\begingroup$

Given two context-sensitive languages, $L_1$ and $L_2$ is the problem of "whether $L_1 \cap L_2$ also belongs to CSL" decidable?

I have the same question for the case when $L_1$ and $L_2$ belongs to Recursive/Recursively enumerable language. I think, they are decidable because they are closed under intersection operation as can be seen here. But I haven't found any text mentioning this explicitly so I can't be sure.

$\endgroup$
  • $\begingroup$ All three classes you mention are closed under intersection, so the problems are trivially decidable (i.e. by the algorithm: "return YES"). Are you perhaps searching for proof of closure under intersection? $\endgroup$ – potestasity Jan 18 '18 at 12:08
  • $\begingroup$ I was looking for confirmation that closure under a property implies decidability for that property. I guess that is trivial then. @potestasity $\endgroup$ – momo Jan 18 '18 at 16:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.