<p>The problem is undecidable, already for very particular cases.</p>
<p>This is because in the case <span class="math-container">$\Sigma'=\Sigma$</span>, the problem is equivalent to deciding whethe
r a given rational subset of a monoid <span class="math-container">$M$</span> is recognizable. Here, <span class="math-container">$M$</span> is the monoid
<span class="math-container">$\Sigma^*/R$</span>, i.e. the monoid presented by the equations in <span class="math-container">$R$</span>. This is also called the &quot;
recognizability problem&quot; for <span class="math-container">$M$</span>.</p>
<p>Recognizability is decidable for some monoids (e.g. finitely generated commutative monoids), but in many cases, it is undecidable. As an example, if <span class="math-container">$\Sigma=\{a,b,c\}$</span> and <span class="math-container">$R$</span> allows us to commute <span class="math-container">$a$</span> with <span class="math-container">$b$</span> and <span class="math-container">$a$</span> with <span class="math-container">$c$</span> (i.e. <span class="math-container">$R$</span> contains the two rules <span class="math-container">$(ab,ba)$</span> and <span class="math-container">$(ac,ca)$</span>), then <span class="math-container">$M$</span> is the trace monoid whose commutation relation is a path on three nodes. As shown by Sakarovitch [1], it is undecidable whether a given rational subset of <span class="math-container">$M$</span> is recognizable. (In fact, Sakarovitch characterizes all trace monoids in which recognizability is decidable.)</p>
<p>[1] J. Sakarovitch, The 'last' decision problem for rational trace languages, LATIN'92,
<a href="https://doi.org/10.1007/BFb0023848" rel="nofollow noreferrer">https://doi.org/10.1007/BFb0023848</a></p>

CC BY-SA 4.0
2024-08-02T13:29:15.420Z
I’m confused. It seems to me that given a regular language $L\subseteq\{a,b,c\}^*$ (say, as a DFA $A$), it *is* decidable whether $L$ is closed under $\{(ab,ba),(ac,ca)\}$ (construct an NFA $A'$ that works as $A$, except that it may nondeterministically decide to exchange some $a$ with a later symbol, and test whether $A$ and $A'$ recognize the same language). What am I doing wrong?
Emil Jeřábek
CC BY-SA 4.0
2024-08-02T13:44:15.760Z
Also, I may be confused by the terminology (unfamiliar to me), but I do not understand how you got to the problem whether “a given rational subset of a monoid $M$ is recognizable”. The problem for $\Sigma=\Sigma'$ is, given a regular language $L$ and a Thue system $R$, decide if $L$ is closed under $R$. In terms of the monoid $M=\Sigma^*/R$, and going by the definitions in https://en.wikipedia.org/wiki/Recognizable_set this says, ”given a presentation of $M$ and a rational subset of $\Sigma^*$, decide if it is recognized by $M$”. So $M$ is the target rather than source of the homomorphism.
Emil Jeřábek
CC BY-SA 4.0
2024-08-02T13:58:42.950Z
Ah, you're right! My argument is flawed, thank you! But I think with a slight modification, one can still reduce the recognizability problem (in the case of $\Sigma$ being strictly smaller than $\Sigma'$---if they're the same, you're right, the problem is decidable). What's the right thing to do, edit my answer, or delete and post a new one?
Georg Zetzsche
CC BY-SA 4.0
2024-08-02T13:58:47.017Z
Come think of it, the algorithm in my first comment is perfectly general: it shows that the problem for $\Sigma=\Sigma'$ is decidable.
Emil Jeřábek
CC BY-SA 4.0
2024-08-02T14:00:42.457Z
It seems we posted comments at the same time. It is definitely preferable if you fix your existing answer rather than post a new one.
Emil Jeřábek
CC BY-SA 4.0
2024-08-02T12:31:36.010Z
2024-08-02T12:31:36.010Z
Georg Zetzsche
<p>Given a regular language <span class="math-container">$L \subseteq \Sigma^*$</span> and a finitely presented Thue system <span class="math-container">$R$</span> in a finitely extended alphabet <span class="math-container">$\Sigma' \supseteq \Sigma$</span>, can we decide whether there is a regular language <span class="math-container">$L' \subseteq \Sigma'^*$</span> that is closed under <span class="math-container">$R$</span>, and <span class="math-container">$L' \cap \Sigma^* = L$</span>? I tried to reduce the halting problem or the string rewriting problem to it, but did not come up with a method.</p>

CC BY-SA 4.0
2024-07-30T06:33:22.417Z
Thanks, I've updated my problem; I meant to consider Thue systems. The word problem asks whether $u$ can be transformed to $v$, but here I want to ask (decide) whether this problem is regular.
luke36
CC BY-SA 4.0
2024-07-30T18:19:53.157Z
So you might be able to reduce a word problem $(u,v)$ in a Thue system over the alphabet $\Sigma'\setminus\Sigma$ to your problem. Probably by taking $L=\{a\}$, and extending the rewriting relation by $(a, u)$ and $(v,b)$, or something like that
xavierm02
CC BY-SA 4.0
2024-07-30T18:38:28.407Z
If I take $L=\{a\}$, $R=\{(ba, a)\}$, then there is no such $X$ because it must be the case $ba \in L \cup X$, which is impossible. But we can take $L'=\{b^* a\}$
luke36
CC BY-SA 4.0
2024-07-30T19:10:23.033Z
Right. So the rephrasing doesn't work. That doesn't seem to impact the reduction idea though
xavierm02
CC BY-SA 4.0
2024-07-31T07:15:31.820Z
The problem is (always) that the congruence class of $a$, no matter it includes $v$ or not, appears to be complex (and not regular), if the word problem $(u, v)$ is undecidable.
luke36
CC BY-SA 4.0
2024-07-31T15:23:05.320Z
Here's another random guess: reduce the problem "Given a computable function $f:\mathbb{N} \to\{T,F\}$, does there exist $n$ such that $f(n)=T$?" instead. We can a priori turn such a function into a Thue system whose runs start from $a$, then computes successive values of $f$ untils it gets a $T$ output (i.e. $a \rightarrow_R^* \overline{0} \rightarrow_R^* f(0)\overline{1} \rightarrow_R^* f(0)f(1)\overline{2} \rightarrow_R^* f(0)f(1)...f(n)\overline{n}=F...FT\overline{n}$, where the overline represents some encoding from $\mathbb{N}$ into words) and then keeps adding $F$ on the left of the $T$
xavierm02
CC BY-SA 4.0
2024-07-31T15:23:24.443Z
, with the possibility of erasing the $\overline{n}$ at each of these intermediate steps. The intersection of the congruence class of $a$ with $\{T,F\}^*$ is $F^*T$ when $f$ is a positive instance, and $F^*$ when it is a negative one. We might be able to ensure that the congruence class of $a$ is regular for positive instances $f$ because the run until the first $T$ is finite, and the behavior of then adding $F$s is regular.
xavierm02
<fl.formal-languages><automata-theory><regular-language><undecidability><term-rewriting-systems>
Can we decide the existence of some regular language closed under a Thue system?
luke36
# Can we decide the existence of some regular language closed under a Thue system?

(Asked by: username_0 on 2024-07-28)

Given a regular language $L \subseteq \Sigma^\*$ and a finitely presented Thue system $R$ in a finitely extended alphabet $\Sigma' \supseteq \Sigma$, can we decide whether there is a regular language $L' \subseteq \Sigma'^\*$ that is closed under $R$, and $L' \cap \Sigma^\* = L$? I tried to reduce the halting problem or the string rewriting problem to it, but did not come up with a method.

**Tags:** fl.formal-languages, automata-theory, regular-language, undecidability, term-rewriting-systems
> **Comments:**
> **username_0**: Thanks, I've updated my problem; I meant to consider Thue systems. The word problem asks whether $u$ can be transformed to $v$, but here I want to ask (decide) whether this problem is regular.  
> **username_1**: So you might be able to reduce a word problem $(u,v)$ in a Thue system over the alphabet $\Sigma'\setminus\Sigma$ to your problem. Probably by taking $L=\{a\}$, and extending the rewriting relation by $(a, u)$ and $(v,b)$, or something like that  
> **username_0**: If I take $L=\{a\}$, $R=\{(ba, a)\}$, then there is no such $X$ because it must be the case $ba \in L \cup X$, which is impossible. But we can take $L'=\{b^* a\}$  
> **username_1**: Right. So the rephrasing doesn't work. That doesn't seem to impact the reduction idea though  
> **username_0**: The problem is (always) that the congruence class of $a$, no matter it includes $v$ or not, appears to be complex (and not regular), if the word problem $(u, v)$ is undecidable.  
> **username_1**: Here's another random guess: reduce the problem "Given a computable function $f:\mathbb{N} \to\{T,F\}$, does there exist $n$ such that $f(n)=T$?" instead. We can a priori turn such a function into a Thue system whose runs start from $a$, then computes successive values of $f$ untils it gets a $T$ output (i.e. $a \rightarrow_R^* \overline{0} \rightarrow_R^* f(0)\overline{1} \rightarrow_R^* f(0)f(1)\overline{2} \rightarrow_R^* f(0)f(1)...f(n)\overline{n}=F...FT\overline{n}$, where the overline represents some encoding from $\mathbb{N}$ into words) and then keeps adding $F$ on the left of the $T$  
> **username_1**: , with the possibility of erasing the $\overline{n}$ at each of these intermediate steps. The intersection of the congruence class of $a$ with $\{T,F\}^*$ is $F^*T$ when $f$ is a positive instance, and $F^*$ when it is a negative one. We might be able to ensure that the congruence class of $a$ is regular for positive instances $f$ because the run until the first $T$ is finite, and the behavior of then adding $F$s is regular.  

---

## 1 answers

### Answer by username_2 on 2024-08-02. Score: -1

The problem is undecidable, already for very particular cases.

This is because in the case $\Sigma'=\Sigma$, the problem is equivalent to deciding whethe
r a given rational subset of a monoid $M$ is recognizable. Here, $M$ is the monoid
$\Sigma^\*/R$, i.e. the monoid presented by the equations in $R$. This is also called the "
recognizability problem" for $M$.

Recognizability is decidable for some monoids (e.g. finitely generated commutative monoids), but in many cases, it is undecidable. As an example, if $\Sigma=\{a,b,c\}$ and $R$ allows us to commute $a$ with $b$ and $a$ with $c$ (i.e. $R$ contains the two rules $(ab,ba)$ and $(ac,ca)$), then $M$ is the trace monoid whose commutation relation is a path on three nodes. As shown by Sakarovitch [1], it is undecidable whether a given rational subset of $M$ is recognizable. (In fact, Sakarovitch characterizes all trace monoids in which recognizability is decidable.)

[1] J. Sakarovitch, The 'last' decision problem for rational trace languages, LATIN'92,
<https://doi.org/10.1007/BFb0023848>

> **Comments:**
> **username_3**: I’m confused. It seems to me that given a regular language $L\subseteq\{a,b,c\}^*$ (say, as a DFA $A$), it *is* decidable whether $L$ is closed under $\{(ab,ba),(ac,ca)\}$ (construct an NFA $A'$ that works as $A$, except that it may nondeterministically decide to exchange some $a$ with a later symbol, and test whether $A$ and $A'$ recognize the same language). What am I doing wrong?  
> **username_3**: Also, I may be confused by the terminology (unfamiliar to me), but I do not understand how you got to the problem whether “a given rational subset of a monoid $M$ is recognizable”. The problem for $\Sigma=\Sigma'$ is, given a regular language $L$ and a Thue system $R$, decide if $L$ is closed under $R$. In terms of the monoid $M=\Sigma^*/R$, and going by the definitions in https://en.wikipedia.org/wiki/Recognizable_set this says, ”given a presentation of $M$ and a rational subset of $\Sigma^*$, decide if it is recognized by $M$”. So $M$ is the target rather than source of the homomorphism.  
> **username_2**: Ah, you're right! My argument is flawed, thank you! But I think with a slight modification, one can still reduce the recognizability problem (in the case of $\Sigma$ being strictly smaller than $\Sigma'$---if they're the same, you're right, the problem is decidable). What's the right thing to do, edit my answer, or delete and post a new one?  
> **username_3**: Come think of it, the algorithm in my first comment is perfectly general: it shows that the problem for $\Sigma=\Sigma'$ is decidable.  
> **username_3**: It seems we posted comments at the same time. It is definitely preferable if you fix your existing answer rather than post a new one.  

---

