<p>Yes coRE is closed under concatenation:</p>
<p>Let <span class="math-container">$L_1, L_2$</span> be coRE, witnessed by Turing Machines <span class="math-container">$M_1,M_2$</span> whose domain is the complement of <span class="math-container">$L_1,L_2$</span> respectively.</p>
<p>We then build a Turing Machine <span class="math-container">$M$</span> whose domain is the complement of <span class="math-container">$L_1\cdot L_2$</span>: on input <span class="math-container">$u$</span>, <span class="math-container">$M$</span> will enumerate the finitely many ways to decompose <span class="math-container">$u$</span> into <span class="math-container">$u_1u_2$</span>, and for each of them run <span class="math-container">$M_1$</span> on <span class="math-container">$u_1$</span> and <span class="math-container">$M_2$</span> on <span class="math-container">$u_2$</span> in parallel. If one of the machines halts, it means that the decomposition is not a witness that <span class="math-container">$u$</span> is in <span class="math-container">$L_1\cdot  L_2$</span>, and <span class="math-container">$M$</span> continues with the next decomposition. The machine <span class="math-container">$M$</span> will halt once all decompositions have been tried. Therefore, <span class="math-container">$M$</span> does not halt on <span class="math-container">$u$</span> if and only if <span class="math-container">$u\in L_1\cdot L_2$</span>.</p>

CC BY-SA 4.0
2021-07-06T23:34:56.953Z
Very nice! Should've seen that myself...
Aryeh
CC BY-SA 4.0
2021-07-06T15:35:52.230Z
2021-07-06T15:35:52.230Z
Denis
<p>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...</p>

CC BY-SA 4.0
2021-07-06T15:15:10.763Z
What is the concatenation of two sets of integers?
Bartosz Bednarczyk
CC BY-SA 4.0
2021-07-06T16:15:02.563Z
@BartoszBednarczyk: OP is talking about sets of finite words over an alphabet. But since you ask, the concatenation of 42 and 23 is 4223.
Andrej Bauer
CC BY-SA 4.0
2021-07-06T16:37:44.560Z
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.
Aryeh
CC BY-SA 4.0
2021-07-07T08:07:44.917Z
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\}$.
Emil Jeřábek
CC BY-SA 4.0
2021-07-07T08:54:01.907Z
Yes, this is the standard definition given in every textbook.
Aryeh
<computability><turing-machines>
Is coRE closed under concatenation?
Aryeh
# Is coRE closed under concatenation?

(Asked by: username_0 on 2021-07-06)

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...

**Tags:** computability, turing-machines
> **Comments:**
> **username_1**: What is the concatenation of two sets of integers?  
> **username_2**: @BartoszBednarczyk: OP is talking about sets of finite words over an alphabet. But since you ask, the concatenation of 42 and 23 is 4223.  
> **username_0**: 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.  
> **username_3**: 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\}$.  
> **username_0**: Yes, this is the standard definition given in every textbook.  

---

## 1 answers

### Answer by username_4 on 2021-07-06. Score: 8 | Accepted answer

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$.

> **Comments:**
> **username_0**: Very nice! Should've seen that myself...  

---

