# Can we decide the existence of some regular language closed under a Thue system?

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.

New contributor
luke36 is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct.
• 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 Commented Jul 30 at 18:19
• 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\}$ Commented Jul 30 at 18:38
• 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. Commented Jul 31 at 7:15
• 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$ Commented Jul 31 at 15:23
• , 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. Commented Jul 31 at 15:23

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

• 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? Commented yesterday
• 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 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. Commented yesterday
• 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? Commented yesterday
• Come think of it, the algorithm in my first comment is perfectly general: it shows that the problem for $\Sigma=\Sigma'$ is decidable. Commented yesterday
• 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. Commented yesterday