YES Problem: a(a(x1)) -> b(a(b(x1))) a(a(a(x1))) -> a(b(a(b(a(x1))))) a(b(a(x1))) -> b(b(a(b(b(x1))))) a(a(a(a(x1)))) -> a(a(b(a(b(a(a(x1))))))) a(a(b(a(x1)))) -> a(b(b(a(b(a(b(x1))))))) a(b(a(a(x1)))) -> b(a(b(a(b(b(a(x1))))))) a(b(b(a(x1)))) -> b(b(b(a(b(b(b(x1))))))) a(a(a(a(a(x1))))) -> a(a(a(b(a(b(a(a(a(x1))))))))) a(a(a(b(a(x1))))) -> a(a(b(b(a(b(a(a(b(x1))))))))) a(a(b(a(a(x1))))) -> a(b(a(b(a(b(a(b(a(x1))))))))) a(a(b(b(a(x1))))) -> a(b(b(b(a(b(a(b(b(x1))))))))) a(b(a(a(a(x1))))) -> b(a(a(b(a(b(b(a(a(x1))))))))) a(b(a(b(a(x1))))) -> b(a(b(b(a(b(b(a(b(x1))))))))) a(b(b(a(a(x1))))) -> b(b(a(b(a(b(b(b(a(x1))))))))) a(b(b(b(a(x1))))) -> b(b(b(b(a(b(b(b(b(x1))))))))) Proof: Matrix Interpretation Processor: dim=3 interpretation: [1 0 0] [b](x0) = [0 0 0]x0 [0 0 0] , [1 0 1] [0] [a](x0) = [0 0 0]x0 + [1] [0 1 0] [0] orientation: [1 1 1] [0] [1 0 0] a(a(x1)) = [0 0 0]x1 + [1] >= [0 0 0]x1 = b(a(b(x1))) [0 0 0] [1] [0 0 0] [1 1 1] [1] [1 0 1] [0] a(a(a(x1))) = [0 0 0]x1 + [1] >= [0 0 0]x1 + [1] = a(b(a(b(a(x1))))) [0 0 0] [1] [0 0 0] [0] [1 0 1] [0] [1 0 0] a(b(a(x1))) = [0 0 0]x1 + [1] >= [0 0 0]x1 = b(b(a(b(b(x1))))) [0 0 0] [0] [0 0 0] [1 1 1] [2] [1 1 1] [0] a(a(a(a(x1)))) = [0 0 0]x1 + [1] >= [0 0 0]x1 + [1] = a(a(b(a(b(a(a(x1))))))) [0 0 0] [1] [0 0 0] [1] [1 0 1] [0] [1 0 0] [0] a(a(b(a(x1)))) = [0 0 0]x1 + [1] >= [0 0 0]x1 + [1] = a(b(b(a(b(a(b(x1))))))) [0 0 0] [1] [0 0 0] [0] [1 1 1] [0] [1 0 1] a(b(a(a(x1)))) = [0 0 0]x1 + [1] >= [0 0 0]x1 = b(a(b(a(b(b(a(x1))))))) [0 0 0] [0] [0 0 0] [1 0 1] [0] [1 0 0] a(b(b(a(x1)))) = [0 0 0]x1 + [1] >= [0 0 0]x1 = b(b(b(a(b(b(b(x1))))))) [0 0 0] [0] [0 0 0] [1 1 1] [3] [1 1 1] [2] a(a(a(a(a(x1))))) = [0 0 0]x1 + [1] >= [0 0 0]x1 + [1] = a(a(a(b(a(b(a(a(a(x1))))))))) [0 0 0] [1] [0 0 0] [1] [1 0 1] [1] [1 0 0] [0] a(a(a(b(a(x1))))) = [0 0 0]x1 + [1] >= [0 0 0]x1 + [1] = a(a(b(b(a(b(a(a(b(x1))))))))) [0 0 0] [1] [0 0 0] [1] [1 1 1] [0] [1 0 1] [0] a(a(b(a(a(x1))))) = [0 0 0]x1 + [1] >= [0 0 0]x1 + [1] = a(b(a(b(a(b(a(b(a(x1))))))))) [0 0 0] [1] [0 0 0] [0] [1 0 1] [0] [1 0 0] [0] a(a(b(b(a(x1))))) = [0 0 0]x1 + [1] >= [0 0 0]x1 + [1] = a(b(b(b(a(b(a(b(b(x1))))))))) [0 0 0] [1] [0 0 0] [0] [1 1 1] [1] [1 1 1] a(b(a(a(a(x1))))) = [0 0 0]x1 + [1] >= [0 0 0]x1 = b(a(a(b(a(b(b(a(a(x1))))))))) [0 0 0] [0] [0 0 0] [1 0 1] [0] [1 0 0] a(b(a(b(a(x1))))) = [0 0 0]x1 + [1] >= [0 0 0]x1 = b(a(b(b(a(b(b(a(b(x1))))))))) [0 0 0] [0] [0 0 0] [1 1 1] [0] [1 0 1] a(b(b(a(a(x1))))) = [0 0 0]x1 + [1] >= [0 0 0]x1 = b(b(a(b(a(b(b(b(a(x1))))))))) [0 0 0] [0] [0 0 0] [1 0 1] [0] [1 0 0] a(b(b(b(a(x1))))) = [0 0 0]x1 + [1] >= [0 0 0]x1 = b(b(b(b(a(b(b(b(b(x1))))))))) [0 0 0] [0] [0 0 0] problem: a(a(x1)) -> b(a(b(x1))) a(b(a(x1))) -> b(b(a(b(b(x1))))) a(a(b(a(x1)))) -> a(b(b(a(b(a(b(x1))))))) a(b(a(a(x1)))) -> b(a(b(a(b(b(a(x1))))))) a(b(b(a(x1)))) -> b(b(b(a(b(b(b(x1))))))) a(a(b(a(a(x1))))) -> a(b(a(b(a(b(a(b(a(x1))))))))) a(a(b(b(a(x1))))) -> a(b(b(b(a(b(a(b(b(x1))))))))) a(b(a(b(a(x1))))) -> b(a(b(b(a(b(b(a(b(x1))))))))) a(b(b(a(a(x1))))) -> b(b(a(b(a(b(b(b(a(x1))))))))) a(b(b(b(a(x1))))) -> b(b(b(b(a(b(b(b(b(x1))))))))) String Reversal Processor: a(a(x1)) -> b(a(b(x1))) a(b(a(x1))) -> b(b(a(b(b(x1))))) a(b(a(a(x1)))) -> b(a(b(a(b(b(a(x1))))))) a(a(b(a(x1)))) -> a(b(b(a(b(a(b(x1))))))) a(b(b(a(x1)))) -> b(b(b(a(b(b(b(x1))))))) a(a(b(a(a(x1))))) -> a(b(a(b(a(b(a(b(a(x1))))))))) a(b(b(a(a(x1))))) -> b(b(a(b(a(b(b(b(a(x1))))))))) a(b(a(b(a(x1))))) -> b(a(b(b(a(b(b(a(b(x1))))))))) a(a(b(b(a(x1))))) -> a(b(b(b(a(b(a(b(b(x1))))))))) a(b(b(b(a(x1))))) -> b(b(b(b(a(b(b(b(b(x1))))))))) Matrix Interpretation Processor: dim=2 interpretation: [1 0] [b](x0) = [0 0]x0, [1 2] [0] [a](x0) = [0 0]x0 + [1] orientation: [1 2] [2] [1 0] a(a(x1)) = [0 0]x1 + [1] >= [0 0]x1 = b(a(b(x1))) [1 2] [0] [1 0] a(b(a(x1))) = [0 0]x1 + [1] >= [0 0]x1 = b(b(a(b(b(x1))))) [1 2] [2] [1 2] a(b(a(a(x1)))) = [0 0]x1 + [1] >= [0 0]x1 = b(a(b(a(b(b(a(x1))))))) [1 2] [2] [1 0] [0] a(a(b(a(x1)))) = [0 0]x1 + [1] >= [0 0]x1 + [1] = a(b(b(a(b(a(b(x1))))))) [1 2] [0] [1 0] a(b(b(a(x1)))) = [0 0]x1 + [1] >= [0 0]x1 = b(b(b(a(b(b(b(x1))))))) [1 2] [4] [1 2] [0] a(a(b(a(a(x1))))) = [0 0]x1 + [1] >= [0 0]x1 + [1] = a(b(a(b(a(b(a(b(a(x1))))))))) [1 2] [2] [1 2] a(b(b(a(a(x1))))) = [0 0]x1 + [1] >= [0 0]x1 = b(b(a(b(a(b(b(b(a(x1))))))))) [1 2] [0] [1 0] a(b(a(b(a(x1))))) = [0 0]x1 + [1] >= [0 0]x1 = b(a(b(b(a(b(b(a(b(x1))))))))) [1 2] [2] [1 0] [0] a(a(b(b(a(x1))))) = [0 0]x1 + [1] >= [0 0]x1 + [1] = a(b(b(b(a(b(a(b(b(x1))))))))) [1 2] [0] [1 0] a(b(b(b(a(x1))))) = [0 0]x1 + [1] >= [0 0]x1 = b(b(b(b(a(b(b(b(b(x1))))))))) problem: a(b(a(x1))) -> b(b(a(b(b(x1))))) a(b(b(a(x1)))) -> b(b(b(a(b(b(b(x1))))))) a(b(a(b(a(x1))))) -> b(a(b(b(a(b(b(a(b(x1))))))))) a(b(b(b(a(x1))))) -> b(b(b(b(a(b(b(b(b(x1))))))))) Bounds Processor: bound: 2 enrichment: match automaton: final states: {3} transitions: b2(121) -> 122* b2(78) -> 79* b2(111) -> 112* b2(72) -> 73* b2(123) -> 124* b2(90) -> 91* b2(120) -> 121* b2(59) -> 60* b2(74) -> 75* b2(91) -> 92* b2(92) -> 93* b2(108) -> 109* b2(55) -> 56* b2(73) -> 74* b2(106) -> 107* b2(122) -> 123* b2(96) -> 97* b2(76) -> 77* b2(125) -> 126* b2(56) -> 57* b2(110) -> 111* b2(60) -> 61* b2(54) -> 55* b2(138) -> 139* b2(58) -> 59* b2(95) -> 96* b2(77) -> 78* b2(94) -> 95* b2(109) -> 110* a0(3) -> 3* a2(107) -> 108* a2(57) -> 58* a2(75) -> 76* a2(93) -> 94* a2(124) -> 125* b0(3) -> 3* a1(35) -> 36* a1(26) -> 27* a1(12) -> 13* a1(32) -> 33* a1(29) -> 30* a1(17) -> 18* b1(10) -> 11* b1(50) -> 51* b1(70) -> 71* b1(18) -> 19* b1(30) -> 31* b1(134) -> 135* b1(14) -> 15* b1(34) -> 35* b1(27) -> 28* b1(28) -> 29* b1(13) -> 14* b1(36) -> 37* b1(16) -> 17* b1(11) -> 12* b1(31) -> 32* 19 -> 13* 17 -> 34* 35 -> 70* 126 -> 94* 112 -> 27,30,13 12 -> 120,16 93 -> 106* 11 -> 18,3,26 79 -> 30* 26 -> 72* 135 -> 10* 139 -> 107* 71 -> 17* 37 -> 18* 57 -> 138* 3 -> 10* 15 -> 13,27,3 97 -> 27* 51 -> 11* 29 -> 134,54 32 -> 90,50 61 -> 33,14 33 -> 14* problem: Qed