I'm searching for the name and an efficient solution for the following problem: Assume I have a string s='abcdef' and a set of find/replace rules Pn
P1: ab -> xy
P2: xyc -> 123
P3: ef -> ab
Sequentially applying these rules to s I could arrive at the following strings:
1. xycdef
2. 123def
3. 123dab
4. 123dxy
My goal is to reach a "stable" state where all (most?) rules have been applied (here: 123dxy).
So my question is, is there a well defined approach for dealing with this type of problems? Are there general constraints on the rules to avoid infinite loops (eg, ab -> xy, xy -> ab). Is there a way to determine a bound for the maximum number of iterations?
Any pointers to relevant concepts/related work are appreciated.
I would translate this into a graph problem.
In your case, I would have a node named ab, another xy, xyc, etc.
Directed edges exist between node according to the rules.
Here: V={ab, xy, xyc, 123, ef}; E={(ab,xy), (xyz.123), (ef, ab)}
Basic check:
If at this stage you have loops in your graph, then you have a real problem.
Prefixes:
The case with ab -> xy and xyc -> 123 gives us an issue where two rules are not a problem unless the given string is built in a certain way. (abc becomes xyc). This could be checked with directed edges that are marked in a certain way. If they create a loop, then you will have an issue with certain strings, but not with others.
Hope this helped.