# Avoiding infinite rule recursion

Assume I want to apply rule $$R_1$$ from a rule set $$S$$ to an expression $$E$$ just if it is "half safe", i.e., if the next application of $$S$$ to $$R_1(E)$$ does not yield $$E$$ again. (This obviously doesn't help against larger cycles of evaluation, and also if a rule $$R_2\in S$$ exists that would "take $$E$$ to safety" but $$R_1$$ has precedence, I'm stuck either, but at least I'm only stuck and not in an infinite recursion.)

Surely this condition can be written succinctly so I can \; it after $$R_1$$? Or is there even a "try each rule unless one gets you out of the rut" approach (the problem, obviously, is that the length of the expression may temporarily get larger, but applying $$S$$ should always yield the shortest final $$E_F$$ - at least I can probably guarantee that if $$E_F$$ is shorter than $$E$$, the rule path to it is rather short either)?

(Application: Think of knot theory, where the unknot sometimes must get more tangled until it can be recognized as such - but probably not arbitrarily much.)

EDIT: (Very technical, you must know a bit of knot theory!) The rules are all Turaev rules on a braid with four strings ($$R$$ is overcrossing, $$S$$ undercrossing and $$H$$ Temperley-Lieb) so my generators are $$F[T,i], T=R,S,H;i=1,2,3$$, together with the assumption that all clasps, say $$F[S,2,S,2]$$ resolve to a linear combination of, say $$F[X,2], X=R,S,H,null$$. A typical word is e.g. $$F[H,1,R,3,S,2,H,3]$$. A typical evaluation rule is $$F[X,R,3,S,2,H,3,Y]=F[X,R,3,R,3,H,2,H,3,Y]$$ (got longer, but now the two $$R,3$$ simplify and the temp $$H,2$$ can be eliminated again, so the string loses one generator). The problem is e.g. Reidemeister 3, $$F[R,3,S,2,S,3]=F[S,2,S,3,R,2]$$ which may be applied in both directions but it's not trivial to decide beforehand if you should apply it and into which direction. Ultimately my goal is to prove the string can't get infinitely long - everything over $$n$$ generators must simplify. My estimate is about $$1000$$ different non-reducable words.

• Please provide greater detail, including Mathematica code you have tried and the difficulties you have encountered. Aug 5 '21 at 13:50
• If efficiency is not a great concern, you could build a stack of previous results until either an expression shows up a second time or some other criteria is met (max iterations). Aug 5 '21 at 14:52
• You can probably abuse FullSimplify with your replacement rules as TransformationFunctions and a custom ComplexityFunction. It can properly avoid infinite loops, and it handles the case where the expression will temporarily get more complex. Aug 5 '21 at 15:19
• To bbgodfrey: All is still experimental (especially swapping around rule precedences sometimes solves the problem altogether). To Michael E2: Considered that idea already, but I'm a bit to n00b for actually executing it. To Lukas Lang: Sounds worth trying. (The complexity is simply word length.) Aug 5 '21 at 18:05
• Here's the idea: stack = {first (* starting expression *)}; NestWhileList[First[stack = {(last = #) /. rules, stack}] &, First@stack, FreeQ[Rest@stack, #] &, 1, 1000]; last. After seeing the update, FullSimplify sounds better. Aug 5 '21 at 22:19