We have the following task:

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?

  • $\begingroup$ Are you familiar with unrestricted grammars? $\endgroup$ Jun 2 at 8:16
  • $\begingroup$ @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. $\endgroup$ Jun 2 at 8:20
  • $\begingroup$ In fact this is very easy to answer once rephrased. $\endgroup$ Jun 2 at 8:23
  • $\begingroup$ Can you now answer your own question? $\endgroup$ Jun 2 at 9:39
  • $\begingroup$ @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. $\endgroup$ Jun 2 at 9:48

Your problem is essentially the same as the question of whether a given string can be generated from a given initial string using a given unrestricted grammar (simple reverse all productions). The latter question is known to be undecidable, since you can simulate the running of a Turing machine using an unrestricted grammar.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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