Rewriting system is a set of rules in the form of $A \leftrightarrow B$. If we apply that rule to a string $w$ we replace any substring $A$ in $w$ with a substring $B$ and vice versa.

Given a starting string $AAABB$ can we derive $BAAB$ in the system with the following rules:

  • $A \leftrightarrow BA$
  • $BABA \leftrightarrow AABB$
  • $AAA \leftrightarrow AB$
  • $BA \leftrightarrow AB$

Is there a general algorithm for that?

  • $\begingroup$ I would appreciate if you could add more tags to this question, or change the rule set to make it look cooler. $\endgroup$
    – Daniil
    Mar 16 '12 at 5:07
  • 1
    $\begingroup$ @J.D. I think, in general, this rewriting problem can't be solved, because you can model Turing machine with such a rewriting system and derivation problem == halting problem in TM $\endgroup$
    – Daniil
    Mar 16 '12 at 5:57
  • $\begingroup$ @J.D. ah, that makes sense, I should read more into it, thanks! $\endgroup$
    – Daniil
    Mar 16 '12 at 6:58
  • $\begingroup$ @Daniil and future readers: The undecidable problem used is the Post correspondence problem. $\endgroup$
    – jmad
    Mar 17 '12 at 3:00
  • $\begingroup$ This is essentially Markov's idea of algorithm. $\endgroup$
    – vonbrand
    Mar 20 '13 at 19:47

Notice that the parity of the number of $A$s does not change. Since one string contains an odd number $A$ and the other even, they are not reachable.

I believe in general (for an arbitrary set of rules, not your specific example), this is likely to be an undecidable problem. If the transforms are one way(i.e rules of the form $A \to BA$) it is so , for eg see: Tag System.

  • 1
    $\begingroup$ Yeah, IIRC, it's undecidable because you can model a TM with a specific set of rewriting rules. $\endgroup$
    – Daniil
    Mar 16 '12 at 5:59

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.