[alxmng]

Hmm maybe I misunderstand. All the rules must be applied to fixpoint or elimination, for every input right? And the larger the program (rule set) the worse the performance since more rules must be evaluated at each “tick” of the program, unless you play tricks with ordering rules.

[Jtsummers]

Yes, that's often the objective. If they're properly written they will terminate, but not all sets of rules may terminate. It's possible for rules to cause divergence or cycles.

  A -> A B (1)

  A -> B   (2)
  B -> A

(1) never terminates, always adding a new B on application but not removing the A. (2) doesn't grow, but never terminates since each term is replaced with the other.