鉴于：
- 仅包含从to字符的 char 字符串
S长度l'a''z'- 一组
ordered替换规则R（格式为X->Y），其中x,y是来自的单个字母'a' to 'z'（例如，'a' -> ' e'可能是有效规则，但'ce'->'abc'永远不会是有效规则）
当应用规则inr时，如果规则导致任何替换 in ，则所有与规则的字母相等的字母都将被替换为中的字母。RSSleft siderright siderrSrtriggered rule
流程图（算法）：
(1) 在 上交替应用all规则R（按照规则的顺序R）S。
(2) While (there exists any 'triggered rule' DURING (1) ): 重复 (1)
(3) 终止
问题是：有没有办法确定给定字符串 S 和集合 R，算法是否会终止（永远运行）
示例1：（手动执行）
S =
'abcdef'R ={ 'a'->'b' , 'b' -> 'c' }
（顺序隐含每条规则从左到右出现的顺序）
在 S 和 R 上运行算法：
(1.1): 'abcdef' --> 'bbcdef' --> 'cccdef'
(2.1): 重复 (1) 因为在 (1.1) 期间有 2 个替换
(1.2): 'cccdef'
(2.2): 继续 (3) 因为在 (1.1) 期间没有替换(1.2)
(3) : 终止算法
=> 算法以给定的 S 和 R 终止示例 2
：
S =
'abcdef'R ={ 'a'->'b' , 'b' -> 'a' }
（顺序隐含每条规则从左到右的出现顺序）
在 S 和 R 上运行算法：
(1.1): 'abcdef' --> 'bbcdef' --> 'abcdef'
(2.1): 重复 (1) 因为在 (1.1) 期间有 2 个替换
(1.2): 'abcdef--> 'bbcdef' --> 'abcdef'
(2.2): 重复 (1) 因为有在 (1.2) (1.3) 期间有 2 次替换
：......这将永远是 (1.1)....
步骤 (3) (terminate) 永远不会到达。
=> 算法不会以给定的 S 和 R 终止。
- 我对此进行了研究，发现“如果算法停止”这个问题没有有效的算法。
我想到的第一个想法是对
"find cycle"其中的字母，triggered rules但规则的数量可能太大，以至于这个想法不理想。第二个是为
"threshold"重复的时间提出一个，如果超过阈值，我们得出结论算法不会终止。可以随机选择，
"threshold"（只要它足够大） - 这种方法并不是很有吸引力。我在想，如果有任何东西
upper bound可以"threshold"确保我们总是得到正确的答案。我想出了threshold = 2626 是从“a”到“z”的字母数——但我无法证明它是真的（或不是）。（我希望它会类似于 Bellman-Ford 算法，它以固定的步数确定负循环，..）你呢？请帮我找到答案（这不是作业）
谢谢你的阅读。