1
$\begingroup$

According to the article: every c.e.language over $\Sigma^*$can be formed by homomorphism from a Dyck language over $\Sigma^{'}$ intersection with a minimal linear language over $\Sigma^{'}$ to the Kleene closure $\Sigma^*$ over a alphabet.

Now we know, intersection between languages is parallel to series connection of the corresponding Turing Machines. Then what does homomorphism between languages mean to the correspoding Turing Machines?

Partially it seemingly means merge of computational paths,

Improve this question
$\endgroup$
1
  • $\begingroup$ Since CFL is in P, the finite intersection of them is also in P, So homomorphism leads to undecidability and NPC,NP-hard . $\endgroup$
    – XL _At_Here_There
    Commented Aug 23, 2017 at 1:14

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .