5
$\begingroup$

I know that RE is closed under union, intersection, and concatenation (but not complement). It is likewise easy to show that coRE is closed under union and intersection (but not complement). What about concatenation? I don't even know which way to conjecture...

$\endgroup$
5
  • 1
    $\begingroup$ What is the concatenation of two sets of integers? $\endgroup$ Jul 6, 2021 at 15:15
  • 2
    $\begingroup$ @BartoszBednarczyk: OP is talking about sets of finite words over an alphabet. But since you ask, the concatenation of 42 and 23 is 4223. $\endgroup$ Jul 6, 2021 at 16:15
  • 1
    $\begingroup$ Yes. Or, alternatively, one could set up a 1-to-1 correspondence between strings and integers (in any way you like), and that extends the concatenation operation from strings to integers. $\endgroup$
    – Aryeh
    Jul 6, 2021 at 16:37
  • $\begingroup$ But languages are neither integers nor strings, but sets thereof. Concatenation on sets of strings is, apparently, in this context defined by $L_0\cdot L_1=\{w_0\cdot w_1:w_0\in L_0,w_1\in L_1\}$. $\endgroup$ Jul 7, 2021 at 8:07
  • 2
    $\begingroup$ Yes, this is the standard definition given in every textbook. $\endgroup$
    – Aryeh
    Jul 7, 2021 at 8:54

1 Answer 1

8
$\begingroup$

Yes coRE is closed under concatenation:

Let $L_1, L_2$ be coRE, witnessed by Turing Machines $M_1,M_2$ whose domain is the complement of $L_1,L_2$ respectively.

We then build a Turing Machine $M$ whose domain is the complement of $L_1\cdot L_2$: on input $u$, $M$ will enumerate the finitely many ways to decompose $u$ into $u_1u_2$, and for each of them run $M_1$ on $u_1$ and $M_2$ on $u_2$ in parallel. If one of the machines halts, it means that the decomposition is not a witness that $u$ is in $L_1\cdot L_2$, and $M$ continues with the next decomposition. The machine $M$ will halt once all decompositions have been tried. Therefore, $M$ does not halt on $u$ if and only if $u\in L_1\cdot L_2$.

$\endgroup$
1
  • $\begingroup$ Very nice! Should've seen that myself... $\endgroup$
    – Aryeh
    Jul 6, 2021 at 23:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.