# Is this string substitution problem decidable?

Take as input a finite set of string pairs. Each pair represents a substitution. Replace exactly one instance of the left with the right. A substitution can only be performed on x if the left is a substring of x. For example $$01\rightarrow 10$$ means replace one 01 with 10, and can only be applied if 01 is in the string. The algorithm should decide if for the given set there exists a string such that applying a non - zero number of the substitutions yields the initial string.

I am wondering if this is a decidable task. It seems like it should be possible to establish an upper bound on the length of the string and number of substitutions, but I haven't been able to. And from the other end I tried to build a test based on invariants, since invariants can be used to show a lot of sets can't loop. For example

$$\{011\rightarrow 101, 101\rightarrow 110\}$$

Can never produce a loop. We can show this since each rule decreases the average position of 1s in the string when used. Thus it can never produce a string with the same average position as the start thus it can never produce the start.

But there are some cases that I can't think of a clever invariant. For example

$$\{1001\rightarrow 0110\}$$

Which clearly can't form a loop, but I can't think of a property which it always increases.

Is this problem decidable?

• Are you familiar with unrestricted grammars? Jun 2 at 8:16
• @YuvalFilmus I have worked with unrestricted grammars some before but had not made the connection. It would probably be a good idea too rephrase thirds question and have a look. Jun 2 at 8:20
• In fact this is very easy to answer once rephrased. Jun 2 at 8:23
• Can you now answer your own question? Jun 2 at 9:39
• @YuvalFilmus I can. It might be a little while (2 days) before I would write it though. You did the important insight so if you want the reputation feel free to answer. Jun 2 at 9:48