6.38/2.38 YES 6.71/2.43 proof of /export/starexec/sandbox/benchmark/theBenchmark.xml 6.71/2.43 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 6.71/2.43 6.71/2.43 6.71/2.43 Termination w.r.t. Q of the given QTRS could be proven: 6.71/2.43 6.71/2.43 (0) QTRS 6.71/2.43 (1) FlatCCProof [EQUIVALENT, 0 ms] 6.71/2.43 (2) QTRS 6.71/2.43 (3) RootLabelingProof [EQUIVALENT, 4 ms] 6.71/2.43 (4) QTRS 6.71/2.43 (5) QTRSRRRProof [EQUIVALENT, 91 ms] 6.71/2.43 (6) QTRS 6.71/2.43 (7) DependencyPairsProof [EQUIVALENT, 15 ms] 6.71/2.43 (8) QDP 6.71/2.43 (9) DependencyGraphProof [EQUIVALENT, 0 ms] 6.71/2.43 (10) TRUE 6.71/2.43 6.71/2.43 6.71/2.43 ---------------------------------------- 6.71/2.43 6.71/2.43 (0) 6.71/2.43 Obligation: 6.71/2.43 Q restricted rewrite system: 6.71/2.43 The TRS R consists of the following rules: 6.71/2.43 6.71/2.43 a(a(x1)) -> b(a(b(x1))) 6.71/2.43 a(a(a(x1))) -> a(b(a(b(a(x1))))) 6.71/2.43 a(b(a(x1))) -> b(b(a(b(b(x1))))) 6.71/2.43 a(a(a(a(x1)))) -> a(a(b(a(b(a(a(x1))))))) 6.71/2.43 a(a(b(a(x1)))) -> a(b(b(a(b(a(b(x1))))))) 6.71/2.43 a(b(a(a(x1)))) -> b(a(b(a(b(b(a(x1))))))) 6.71/2.43 a(b(b(a(x1)))) -> b(b(b(a(b(b(b(x1))))))) 6.71/2.43 a(a(a(a(a(x1))))) -> a(a(a(b(a(b(a(a(a(x1))))))))) 6.71/2.43 a(a(a(b(a(x1))))) -> a(a(b(b(a(b(a(a(b(x1))))))))) 6.71/2.43 a(a(b(a(a(x1))))) -> a(b(a(b(a(b(a(b(a(x1))))))))) 6.71/2.43 a(a(b(b(a(x1))))) -> a(b(b(b(a(b(a(b(b(x1))))))))) 6.71/2.43 a(b(a(a(a(x1))))) -> b(a(a(b(a(b(b(a(a(x1))))))))) 6.71/2.43 a(b(a(b(a(x1))))) -> b(a(b(b(a(b(b(a(b(x1))))))))) 6.71/2.43 a(b(b(a(a(x1))))) -> b(b(a(b(a(b(b(b(a(x1))))))))) 6.71/2.43 a(b(b(b(a(x1))))) -> b(b(b(b(a(b(b(b(b(x1))))))))) 6.71/2.43 6.71/2.43 Q is empty. 6.71/2.43 6.71/2.43 ---------------------------------------- 6.71/2.43 6.71/2.43 (1) FlatCCProof (EQUIVALENT) 6.71/2.43 We used flat context closure [ROOTLAB] 6.71/2.43 As Q is empty the flat context closure was sound AND complete. 6.71/2.43 6.71/2.43 ---------------------------------------- 6.71/2.43 6.71/2.43 (2) 6.71/2.43 Obligation: 6.71/2.43 Q restricted rewrite system: 6.71/2.43 The TRS R consists of the following rules: 6.71/2.43 6.71/2.43 a(a(a(x1))) -> a(b(a(b(a(x1))))) 6.71/2.43 a(a(a(a(x1)))) -> a(a(b(a(b(a(a(x1))))))) 6.71/2.43 a(a(b(a(x1)))) -> a(b(b(a(b(a(b(x1))))))) 6.71/2.43 a(a(a(a(a(x1))))) -> a(a(a(b(a(b(a(a(a(x1))))))))) 6.71/2.43 a(a(a(b(a(x1))))) -> a(a(b(b(a(b(a(a(b(x1))))))))) 6.71/2.43 a(a(b(a(a(x1))))) -> a(b(a(b(a(b(a(b(a(x1))))))))) 6.71/2.43 a(a(b(b(a(x1))))) -> a(b(b(b(a(b(a(b(b(x1))))))))) 6.71/2.43 a(a(a(x1))) -> a(b(a(b(x1)))) 6.71/2.43 b(a(a(x1))) -> b(b(a(b(x1)))) 6.71/2.43 a(a(b(a(x1)))) -> a(b(b(a(b(b(x1)))))) 6.71/2.44 b(a(b(a(x1)))) -> b(b(b(a(b(b(x1)))))) 6.71/2.44 a(a(b(a(a(x1))))) -> a(b(a(b(a(b(b(a(x1)))))))) 6.71/2.44 b(a(b(a(a(x1))))) -> b(b(a(b(a(b(b(a(x1)))))))) 6.71/2.44 a(a(b(b(a(x1))))) -> a(b(b(b(a(b(b(b(x1)))))))) 6.71/2.44 b(a(b(b(a(x1))))) -> b(b(b(b(a(b(b(b(x1)))))))) 6.71/2.44 a(a(b(a(a(a(x1)))))) -> a(b(a(a(b(a(b(b(a(a(x1)))))))))) 6.71/2.44 b(a(b(a(a(a(x1)))))) -> b(b(a(a(b(a(b(b(a(a(x1)))))))))) 6.71/2.44 a(a(b(a(b(a(x1)))))) -> a(b(a(b(b(a(b(b(a(b(x1)))))))))) 6.71/2.44 b(a(b(a(b(a(x1)))))) -> b(b(a(b(b(a(b(b(a(b(x1)))))))))) 6.71/2.44 a(a(b(b(a(a(x1)))))) -> a(b(b(a(b(a(b(b(b(a(x1)))))))))) 6.71/2.44 b(a(b(b(a(a(x1)))))) -> b(b(b(a(b(a(b(b(b(a(x1)))))))))) 6.71/2.44 a(a(b(b(b(a(x1)))))) -> a(b(b(b(b(a(b(b(b(b(x1)))))))))) 6.71/2.44 b(a(b(b(b(a(x1)))))) -> b(b(b(b(b(a(b(b(b(b(x1)))))))))) 6.71/2.44 6.71/2.44 Q is empty. 6.71/2.44 6.71/2.44 ---------------------------------------- 6.71/2.44 6.71/2.44 (3) RootLabelingProof (EQUIVALENT) 6.71/2.44 We used plain root labeling [ROOTLAB] with the following heuristic: 6.71/2.44 LabelAll: All function symbols get labeled 6.71/2.44 6.71/2.44 As Q is empty the root labeling was sound AND complete. 6.71/2.44 6.71/2.44 ---------------------------------------- 6.71/2.44 6.71/2.44 (4) 6.71/2.44 Obligation: 6.71/2.44 Q restricted rewrite system: 6.71/2.44 The TRS R consists of the following rules: 6.71/2.44 6.71/2.44 a_{a_1}(a_{a_1}(a_{a_1}(x1))) -> a_{b_1}(b_{a_1}(a_{b_1}(b_{a_1}(a_{a_1}(x1))))) 6.71/2.44 a_{a_1}(a_{a_1}(a_{b_1}(x1))) -> a_{b_1}(b_{a_1}(a_{b_1}(b_{a_1}(a_{b_1}(x1))))) 6.71/2.44 a_{a_1}(a_{a_1}(a_{a_1}(a_{a_1}(x1)))) -> a_{a_1}(a_{b_1}(b_{a_1}(a_{b_1}(b_{a_1}(a_{a_1}(a_{a_1}(x1))))))) 6.71/2.44 a_{a_1}(a_{a_1}(a_{a_1}(a_{b_1}(x1)))) -> a_{a_1}(a_{b_1}(b_{a_1}(a_{b_1}(b_{a_1}(a_{a_1}(a_{b_1}(x1))))))) 6.71/2.44 a_{a_1}(a_{b_1}(b_{a_1}(a_{a_1}(x1)))) -> a_{b_1}(b_{b_1}(b_{a_1}(a_{b_1}(b_{a_1}(a_{b_1}(b_{a_1}(x1))))))) 6.71/2.44 a_{a_1}(a_{b_1}(b_{a_1}(a_{b_1}(x1)))) -> a_{b_1}(b_{b_1}(b_{a_1}(a_{b_1}(b_{a_1}(a_{b_1}(b_{b_1}(x1))))))) 6.71/2.44 a_{a_1}(a_{a_1}(a_{a_1}(a_{a_1}(a_{a_1}(x1))))) -> a_{a_1}(a_{a_1}(a_{b_1}(b_{a_1}(a_{b_1}(b_{a_1}(a_{a_1}(a_{a_1}(a_{a_1}(x1))))))))) 6.71/2.44 a_{a_1}(a_{a_1}(a_{a_1}(a_{a_1}(a_{b_1}(x1))))) -> a_{a_1}(a_{a_1}(a_{b_1}(b_{a_1}(a_{b_1}(b_{a_1}(a_{a_1}(a_{a_1}(a_{b_1}(x1))))))))) 6.71/2.44 a_{a_1}(a_{a_1}(a_{b_1}(b_{a_1}(a_{a_1}(x1))))) -> a_{a_1}(a_{b_1}(b_{b_1}(b_{a_1}(a_{b_1}(b_{a_1}(a_{a_1}(a_{b_1}(b_{a_1}(x1))))))))) 6.71/2.44 a_{a_1}(a_{a_1}(a_{b_1}(b_{a_1}(a_{b_1}(x1))))) -> a_{a_1}(a_{b_1}(b_{b_1}(b_{a_1}(a_{b_1}(b_{a_1}(a_{a_1}(a_{b_1}(b_{b_1}(x1))))))))) 6.71/2.44 a_{a_1}(a_{b_1}(b_{a_1}(a_{a_1}(a_{a_1}(x1))))) -> a_{b_1}(b_{a_1}(a_{b_1}(b_{a_1}(a_{b_1}(b_{a_1}(a_{b_1}(b_{a_1}(a_{a_1}(x1))))))))) 6.71/2.44 a_{a_1}(a_{b_1}(b_{a_1}(a_{a_1}(a_{b_1}(x1))))) -> a_{b_1}(b_{a_1}(a_{b_1}(b_{a_1}(a_{b_1}(b_{a_1}(a_{b_1}(b_{a_1}(a_{b_1}(x1))))))))) 6.71/2.44 a_{a_1}(a_{b_1}(b_{b_1}(b_{a_1}(a_{a_1}(x1))))) -> a_{b_1}(b_{b_1}(b_{b_1}(b_{a_1}(a_{b_1}(b_{a_1}(a_{b_1}(b_{b_1}(b_{a_1}(x1))))))))) 6.71/2.44 a_{a_1}(a_{b_1}(b_{b_1}(b_{a_1}(a_{b_1}(x1))))) -> a_{b_1}(b_{b_1}(b_{b_1}(b_{a_1}(a_{b_1}(b_{a_1}(a_{b_1}(b_{b_1}(b_{b_1}(x1))))))))) 6.71/2.44 a_{a_1}(a_{a_1}(a_{a_1}(x1))) -> a_{b_1}(b_{a_1}(a_{b_1}(b_{a_1}(x1)))) 6.71/2.44 a_{a_1}(a_{a_1}(a_{b_1}(x1))) -> a_{b_1}(b_{a_1}(a_{b_1}(b_{b_1}(x1)))) 6.71/2.44 b_{a_1}(a_{a_1}(a_{a_1}(x1))) -> b_{b_1}(b_{a_1}(a_{b_1}(b_{a_1}(x1)))) 6.71/2.44 b_{a_1}(a_{a_1}(a_{b_1}(x1))) -> b_{b_1}(b_{a_1}(a_{b_1}(b_{b_1}(x1)))) 6.71/2.44 a_{a_1}(a_{b_1}(b_{a_1}(a_{a_1}(x1)))) -> a_{b_1}(b_{b_1}(b_{a_1}(a_{b_1}(b_{b_1}(b_{a_1}(x1)))))) 6.71/2.44 a_{a_1}(a_{b_1}(b_{a_1}(a_{b_1}(x1)))) -> a_{b_1}(b_{b_1}(b_{a_1}(a_{b_1}(b_{b_1}(b_{b_1}(x1)))))) 6.71/2.44 b_{a_1}(a_{b_1}(b_{a_1}(a_{a_1}(x1)))) -> b_{b_1}(b_{b_1}(b_{a_1}(a_{b_1}(b_{b_1}(b_{a_1}(x1)))))) 6.71/2.44 b_{a_1}(a_{b_1}(b_{a_1}(a_{b_1}(x1)))) -> b_{b_1}(b_{b_1}(b_{a_1}(a_{b_1}(b_{b_1}(b_{b_1}(x1)))))) 6.71/2.44 a_{a_1}(a_{b_1}(b_{a_1}(a_{a_1}(a_{a_1}(x1))))) -> a_{b_1}(b_{a_1}(a_{b_1}(b_{a_1}(a_{b_1}(b_{b_1}(b_{a_1}(a_{a_1}(x1)))))))) 6.71/2.44 a_{a_1}(a_{b_1}(b_{a_1}(a_{a_1}(a_{b_1}(x1))))) -> a_{b_1}(b_{a_1}(a_{b_1}(b_{a_1}(a_{b_1}(b_{b_1}(b_{a_1}(a_{b_1}(x1)))))))) 6.71/2.44 b_{a_1}(a_{b_1}(b_{a_1}(a_{a_1}(a_{a_1}(x1))))) -> b_{b_1}(b_{a_1}(a_{b_1}(b_{a_1}(a_{b_1}(b_{b_1}(b_{a_1}(a_{a_1}(x1)))))))) 6.71/2.44 b_{a_1}(a_{b_1}(b_{a_1}(a_{a_1}(a_{b_1}(x1))))) -> b_{b_1}(b_{a_1}(a_{b_1}(b_{a_1}(a_{b_1}(b_{b_1}(b_{a_1}(a_{b_1}(x1)))))))) 6.71/2.44 a_{a_1}(a_{b_1}(b_{b_1}(b_{a_1}(a_{a_1}(x1))))) -> a_{b_1}(b_{b_1}(b_{b_1}(b_{a_1}(a_{b_1}(b_{b_1}(b_{b_1}(b_{a_1}(x1)))))))) 6.71/2.44 a_{a_1}(a_{b_1}(b_{b_1}(b_{a_1}(a_{b_1}(x1))))) -> a_{b_1}(b_{b_1}(b_{b_1}(b_{a_1}(a_{b_1}(b_{b_1}(b_{b_1}(b_{b_1}(x1)))))))) 6.71/2.44 b_{a_1}(a_{b_1}(b_{b_1}(b_{a_1}(a_{a_1}(x1))))) -> b_{b_1}(b_{b_1}(b_{b_1}(b_{a_1}(a_{b_1}(b_{b_1}(b_{b_1}(b_{a_1}(x1)))))))) 6.71/2.44 b_{a_1}(a_{b_1}(b_{b_1}(b_{a_1}(a_{b_1}(x1))))) -> b_{b_1}(b_{b_1}(b_{b_1}(b_{a_1}(a_{b_1}(b_{b_1}(b_{b_1}(b_{b_1}(x1)))))))) 6.71/2.44 a_{a_1}(a_{b_1}(b_{a_1}(a_{a_1}(a_{a_1}(a_{a_1}(x1)))))) -> a_{b_1}(b_{a_1}(a_{a_1}(a_{b_1}(b_{a_1}(a_{b_1}(b_{b_1}(b_{a_1}(a_{a_1}(a_{a_1}(x1)))))))))) 6.71/2.44 a_{a_1}(a_{b_1}(b_{a_1}(a_{a_1}(a_{a_1}(a_{b_1}(x1)))))) -> a_{b_1}(b_{a_1}(a_{a_1}(a_{b_1}(b_{a_1}(a_{b_1}(b_{b_1}(b_{a_1}(a_{a_1}(a_{b_1}(x1)))))))))) 6.71/2.44 b_{a_1}(a_{b_1}(b_{a_1}(a_{a_1}(a_{a_1}(a_{a_1}(x1)))))) -> b_{b_1}(b_{a_1}(a_{a_1}(a_{b_1}(b_{a_1}(a_{b_1}(b_{b_1}(b_{a_1}(a_{a_1}(a_{a_1}(x1)))))))))) 6.71/2.44 b_{a_1}(a_{b_1}(b_{a_1}(a_{a_1}(a_{a_1}(a_{b_1}(x1)))))) -> b_{b_1}(b_{a_1}(a_{a_1}(a_{b_1}(b_{a_1}(a_{b_1}(b_{b_1}(b_{a_1}(a_{a_1}(a_{b_1}(x1)))))))))) 6.71/2.44 a_{a_1}(a_{b_1}(b_{a_1}(a_{b_1}(b_{a_1}(a_{a_1}(x1)))))) -> a_{b_1}(b_{a_1}(a_{b_1}(b_{b_1}(b_{a_1}(a_{b_1}(b_{b_1}(b_{a_1}(a_{b_1}(b_{a_1}(x1)))))))))) 6.71/2.44 a_{a_1}(a_{b_1}(b_{a_1}(a_{b_1}(b_{a_1}(a_{b_1}(x1)))))) -> a_{b_1}(b_{a_1}(a_{b_1}(b_{b_1}(b_{a_1}(a_{b_1}(b_{b_1}(b_{a_1}(a_{b_1}(b_{b_1}(x1)))))))))) 6.71/2.44 b_{a_1}(a_{b_1}(b_{a_1}(a_{b_1}(b_{a_1}(a_{a_1}(x1)))))) -> b_{b_1}(b_{a_1}(a_{b_1}(b_{b_1}(b_{a_1}(a_{b_1}(b_{b_1}(b_{a_1}(a_{b_1}(b_{a_1}(x1)))))))))) 6.71/2.44 b_{a_1}(a_{b_1}(b_{a_1}(a_{b_1}(b_{a_1}(a_{b_1}(x1)))))) -> b_{b_1}(b_{a_1}(a_{b_1}(b_{b_1}(b_{a_1}(a_{b_1}(b_{b_1}(b_{a_1}(a_{b_1}(b_{b_1}(x1)))))))))) 6.71/2.44 a_{a_1}(a_{b_1}(b_{b_1}(b_{a_1}(a_{a_1}(a_{a_1}(x1)))))) -> a_{b_1}(b_{b_1}(b_{a_1}(a_{b_1}(b_{a_1}(a_{b_1}(b_{b_1}(b_{b_1}(b_{a_1}(a_{a_1}(x1)))))))))) 6.71/2.44 a_{a_1}(a_{b_1}(b_{b_1}(b_{a_1}(a_{a_1}(a_{b_1}(x1)))))) -> a_{b_1}(b_{b_1}(b_{a_1}(a_{b_1}(b_{a_1}(a_{b_1}(b_{b_1}(b_{b_1}(b_{a_1}(a_{b_1}(x1)))))))))) 6.71/2.44 b_{a_1}(a_{b_1}(b_{b_1}(b_{a_1}(a_{a_1}(a_{a_1}(x1)))))) -> b_{b_1}(b_{b_1}(b_{a_1}(a_{b_1}(b_{a_1}(a_{b_1}(b_{b_1}(b_{b_1}(b_{a_1}(a_{a_1}(x1)))))))))) 6.71/2.44 b_{a_1}(a_{b_1}(b_{b_1}(b_{a_1}(a_{a_1}(a_{b_1}(x1)))))) -> b_{b_1}(b_{b_1}(b_{a_1}(a_{b_1}(b_{a_1}(a_{b_1}(b_{b_1}(b_{b_1}(b_{a_1}(a_{b_1}(x1)))))))))) 6.71/2.44 a_{a_1}(a_{b_1}(b_{b_1}(b_{b_1}(b_{a_1}(a_{a_1}(x1)))))) -> a_{b_1}(b_{b_1}(b_{b_1}(b_{b_1}(b_{a_1}(a_{b_1}(b_{b_1}(b_{b_1}(b_{b_1}(b_{a_1}(x1)))))))))) 6.71/2.44 a_{a_1}(a_{b_1}(b_{b_1}(b_{b_1}(b_{a_1}(a_{b_1}(x1)))))) -> a_{b_1}(b_{b_1}(b_{b_1}(b_{b_1}(b_{a_1}(a_{b_1}(b_{b_1}(b_{b_1}(b_{b_1}(b_{b_1}(x1)))))))))) 6.71/2.44 b_{a_1}(a_{b_1}(b_{b_1}(b_{b_1}(b_{a_1}(a_{a_1}(x1)))))) -> b_{b_1}(b_{b_1}(b_{b_1}(b_{b_1}(b_{a_1}(a_{b_1}(b_{b_1}(b_{b_1}(b_{b_1}(b_{a_1}(x1)))))))))) 6.71/2.44 b_{a_1}(a_{b_1}(b_{b_1}(b_{b_1}(b_{a_1}(a_{b_1}(x1)))))) -> b_{b_1}(b_{b_1}(b_{b_1}(b_{b_1}(b_{a_1}(a_{b_1}(b_{b_1}(b_{b_1}(b_{b_1}(b_{b_1}(x1)))))))))) 6.71/2.44 6.71/2.44 Q is empty. 6.71/2.44 6.71/2.44 ---------------------------------------- 6.71/2.44 6.71/2.44 (5) QTRSRRRProof (EQUIVALENT) 6.71/2.44 Used ordering: 6.71/2.44 Polynomial interpretation [POLO]: 6.71/2.44 6.71/2.44 POL(a_{a_1}(x_1)) = 1 + x_1 6.71/2.44 POL(a_{b_1}(x_1)) = x_1 6.71/2.44 POL(b_{a_1}(x_1)) = x_1 6.71/2.44 POL(b_{b_1}(x_1)) = x_1 6.71/2.44 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: 6.71/2.44 6.71/2.44 a_{a_1}(a_{a_1}(a_{a_1}(x1))) -> a_{b_1}(b_{a_1}(a_{b_1}(b_{a_1}(a_{a_1}(x1))))) 6.71/2.44 a_{a_1}(a_{a_1}(a_{b_1}(x1))) -> a_{b_1}(b_{a_1}(a_{b_1}(b_{a_1}(a_{b_1}(x1))))) 6.71/2.44 a_{a_1}(a_{a_1}(a_{a_1}(a_{a_1}(x1)))) -> a_{a_1}(a_{b_1}(b_{a_1}(a_{b_1}(b_{a_1}(a_{a_1}(a_{a_1}(x1))))))) 6.71/2.44 a_{a_1}(a_{a_1}(a_{a_1}(a_{b_1}(x1)))) -> a_{a_1}(a_{b_1}(b_{a_1}(a_{b_1}(b_{a_1}(a_{a_1}(a_{b_1}(x1))))))) 6.71/2.44 a_{a_1}(a_{b_1}(b_{a_1}(a_{a_1}(x1)))) -> a_{b_1}(b_{b_1}(b_{a_1}(a_{b_1}(b_{a_1}(a_{b_1}(b_{a_1}(x1))))))) 6.71/2.44 a_{a_1}(a_{b_1}(b_{a_1}(a_{b_1}(x1)))) -> a_{b_1}(b_{b_1}(b_{a_1}(a_{b_1}(b_{a_1}(a_{b_1}(b_{b_1}(x1))))))) 6.71/2.44 a_{a_1}(a_{a_1}(a_{b_1}(b_{a_1}(a_{a_1}(x1))))) -> a_{a_1}(a_{b_1}(b_{b_1}(b_{a_1}(a_{b_1}(b_{a_1}(a_{a_1}(a_{b_1}(b_{a_1}(x1))))))))) 6.71/2.44 a_{a_1}(a_{b_1}(b_{a_1}(a_{a_1}(a_{a_1}(x1))))) -> a_{b_1}(b_{a_1}(a_{b_1}(b_{a_1}(a_{b_1}(b_{a_1}(a_{b_1}(b_{a_1}(a_{a_1}(x1))))))))) 6.71/2.44 a_{a_1}(a_{b_1}(b_{a_1}(a_{a_1}(a_{b_1}(x1))))) -> a_{b_1}(b_{a_1}(a_{b_1}(b_{a_1}(a_{b_1}(b_{a_1}(a_{b_1}(b_{a_1}(a_{b_1}(x1))))))))) 6.71/2.44 a_{a_1}(a_{b_1}(b_{b_1}(b_{a_1}(a_{a_1}(x1))))) -> a_{b_1}(b_{b_1}(b_{b_1}(b_{a_1}(a_{b_1}(b_{a_1}(a_{b_1}(b_{b_1}(b_{a_1}(x1))))))))) 6.71/2.44 a_{a_1}(a_{b_1}(b_{b_1}(b_{a_1}(a_{b_1}(x1))))) -> a_{b_1}(b_{b_1}(b_{b_1}(b_{a_1}(a_{b_1}(b_{a_1}(a_{b_1}(b_{b_1}(b_{b_1}(x1))))))))) 6.71/2.44 a_{a_1}(a_{a_1}(a_{a_1}(x1))) -> a_{b_1}(b_{a_1}(a_{b_1}(b_{a_1}(x1)))) 6.71/2.44 a_{a_1}(a_{a_1}(a_{b_1}(x1))) -> a_{b_1}(b_{a_1}(a_{b_1}(b_{b_1}(x1)))) 6.71/2.44 b_{a_1}(a_{a_1}(a_{a_1}(x1))) -> b_{b_1}(b_{a_1}(a_{b_1}(b_{a_1}(x1)))) 6.71/2.44 b_{a_1}(a_{a_1}(a_{b_1}(x1))) -> b_{b_1}(b_{a_1}(a_{b_1}(b_{b_1}(x1)))) 6.71/2.44 a_{a_1}(a_{b_1}(b_{a_1}(a_{a_1}(x1)))) -> a_{b_1}(b_{b_1}(b_{a_1}(a_{b_1}(b_{b_1}(b_{a_1}(x1)))))) 6.71/2.44 a_{a_1}(a_{b_1}(b_{a_1}(a_{b_1}(x1)))) -> a_{b_1}(b_{b_1}(b_{a_1}(a_{b_1}(b_{b_1}(b_{b_1}(x1)))))) 6.71/2.44 b_{a_1}(a_{b_1}(b_{a_1}(a_{a_1}(x1)))) -> b_{b_1}(b_{b_1}(b_{a_1}(a_{b_1}(b_{b_1}(b_{a_1}(x1)))))) 6.71/2.44 a_{a_1}(a_{b_1}(b_{a_1}(a_{a_1}(a_{a_1}(x1))))) -> a_{b_1}(b_{a_1}(a_{b_1}(b_{a_1}(a_{b_1}(b_{b_1}(b_{a_1}(a_{a_1}(x1)))))))) 6.71/2.44 a_{a_1}(a_{b_1}(b_{a_1}(a_{a_1}(a_{b_1}(x1))))) -> a_{b_1}(b_{a_1}(a_{b_1}(b_{a_1}(a_{b_1}(b_{b_1}(b_{a_1}(a_{b_1}(x1)))))))) 6.71/2.44 b_{a_1}(a_{b_1}(b_{a_1}(a_{a_1}(a_{a_1}(x1))))) -> b_{b_1}(b_{a_1}(a_{b_1}(b_{a_1}(a_{b_1}(b_{b_1}(b_{a_1}(a_{a_1}(x1)))))))) 6.71/2.44 b_{a_1}(a_{b_1}(b_{a_1}(a_{a_1}(a_{b_1}(x1))))) -> b_{b_1}(b_{a_1}(a_{b_1}(b_{a_1}(a_{b_1}(b_{b_1}(b_{a_1}(a_{b_1}(x1)))))))) 6.71/2.44 a_{a_1}(a_{b_1}(b_{b_1}(b_{a_1}(a_{a_1}(x1))))) -> a_{b_1}(b_{b_1}(b_{b_1}(b_{a_1}(a_{b_1}(b_{b_1}(b_{b_1}(b_{a_1}(x1)))))))) 6.71/2.44 a_{a_1}(a_{b_1}(b_{b_1}(b_{a_1}(a_{b_1}(x1))))) -> a_{b_1}(b_{b_1}(b_{b_1}(b_{a_1}(a_{b_1}(b_{b_1}(b_{b_1}(b_{b_1}(x1)))))))) 6.71/2.44 b_{a_1}(a_{b_1}(b_{b_1}(b_{a_1}(a_{a_1}(x1))))) -> b_{b_1}(b_{b_1}(b_{b_1}(b_{a_1}(a_{b_1}(b_{b_1}(b_{b_1}(b_{a_1}(x1)))))))) 6.71/2.44 a_{a_1}(a_{b_1}(b_{a_1}(a_{a_1}(a_{a_1}(a_{a_1}(x1)))))) -> a_{b_1}(b_{a_1}(a_{a_1}(a_{b_1}(b_{a_1}(a_{b_1}(b_{b_1}(b_{a_1}(a_{a_1}(a_{a_1}(x1)))))))))) 6.71/2.44 a_{a_1}(a_{b_1}(b_{a_1}(a_{a_1}(a_{a_1}(a_{b_1}(x1)))))) -> a_{b_1}(b_{a_1}(a_{a_1}(a_{b_1}(b_{a_1}(a_{b_1}(b_{b_1}(b_{a_1}(a_{a_1}(a_{b_1}(x1)))))))))) 6.71/2.44 a_{a_1}(a_{b_1}(b_{a_1}(a_{b_1}(b_{a_1}(a_{a_1}(x1)))))) -> a_{b_1}(b_{a_1}(a_{b_1}(b_{b_1}(b_{a_1}(a_{b_1}(b_{b_1}(b_{a_1}(a_{b_1}(b_{a_1}(x1)))))))))) 6.71/2.44 a_{a_1}(a_{b_1}(b_{a_1}(a_{b_1}(b_{a_1}(a_{b_1}(x1)))))) -> a_{b_1}(b_{a_1}(a_{b_1}(b_{b_1}(b_{a_1}(a_{b_1}(b_{b_1}(b_{a_1}(a_{b_1}(b_{b_1}(x1)))))))))) 6.71/2.44 b_{a_1}(a_{b_1}(b_{a_1}(a_{b_1}(b_{a_1}(a_{a_1}(x1)))))) -> b_{b_1}(b_{a_1}(a_{b_1}(b_{b_1}(b_{a_1}(a_{b_1}(b_{b_1}(b_{a_1}(a_{b_1}(b_{a_1}(x1)))))))))) 6.71/2.44 a_{a_1}(a_{b_1}(b_{b_1}(b_{a_1}(a_{a_1}(a_{a_1}(x1)))))) -> a_{b_1}(b_{b_1}(b_{a_1}(a_{b_1}(b_{a_1}(a_{b_1}(b_{b_1}(b_{b_1}(b_{a_1}(a_{a_1}(x1)))))))))) 6.71/2.44 a_{a_1}(a_{b_1}(b_{b_1}(b_{a_1}(a_{a_1}(a_{b_1}(x1)))))) -> a_{b_1}(b_{b_1}(b_{a_1}(a_{b_1}(b_{a_1}(a_{b_1}(b_{b_1}(b_{b_1}(b_{a_1}(a_{b_1}(x1)))))))))) 6.71/2.44 b_{a_1}(a_{b_1}(b_{b_1}(b_{a_1}(a_{a_1}(a_{a_1}(x1)))))) -> b_{b_1}(b_{b_1}(b_{a_1}(a_{b_1}(b_{a_1}(a_{b_1}(b_{b_1}(b_{b_1}(b_{a_1}(a_{a_1}(x1)))))))))) 6.71/2.44 b_{a_1}(a_{b_1}(b_{b_1}(b_{a_1}(a_{a_1}(a_{b_1}(x1)))))) -> b_{b_1}(b_{b_1}(b_{a_1}(a_{b_1}(b_{a_1}(a_{b_1}(b_{b_1}(b_{b_1}(b_{a_1}(a_{b_1}(x1)))))))))) 6.71/2.44 a_{a_1}(a_{b_1}(b_{b_1}(b_{b_1}(b_{a_1}(a_{a_1}(x1)))))) -> a_{b_1}(b_{b_1}(b_{b_1}(b_{b_1}(b_{a_1}(a_{b_1}(b_{b_1}(b_{b_1}(b_{b_1}(b_{a_1}(x1)))))))))) 6.71/2.44 a_{a_1}(a_{b_1}(b_{b_1}(b_{b_1}(b_{a_1}(a_{b_1}(x1)))))) -> a_{b_1}(b_{b_1}(b_{b_1}(b_{b_1}(b_{a_1}(a_{b_1}(b_{b_1}(b_{b_1}(b_{b_1}(b_{b_1}(x1)))))))))) 6.71/2.44 b_{a_1}(a_{b_1}(b_{b_1}(b_{b_1}(b_{a_1}(a_{a_1}(x1)))))) -> b_{b_1}(b_{b_1}(b_{b_1}(b_{b_1}(b_{a_1}(a_{b_1}(b_{b_1}(b_{b_1}(b_{b_1}(b_{a_1}(x1)))))))))) 6.71/2.44 6.71/2.44 6.71/2.44 6.71/2.44 6.71/2.44 ---------------------------------------- 6.71/2.44 6.71/2.44 (6) 6.71/2.44 Obligation: 6.71/2.44 Q restricted rewrite system: 6.71/2.44 The TRS R consists of the following rules: 6.71/2.44 6.71/2.44 a_{a_1}(a_{a_1}(a_{a_1}(a_{a_1}(a_{a_1}(x1))))) -> a_{a_1}(a_{a_1}(a_{b_1}(b_{a_1}(a_{b_1}(b_{a_1}(a_{a_1}(a_{a_1}(a_{a_1}(x1))))))))) 6.71/2.44 a_{a_1}(a_{a_1}(a_{a_1}(a_{a_1}(a_{b_1}(x1))))) -> a_{a_1}(a_{a_1}(a_{b_1}(b_{a_1}(a_{b_1}(b_{a_1}(a_{a_1}(a_{a_1}(a_{b_1}(x1))))))))) 6.71/2.44 a_{a_1}(a_{a_1}(a_{b_1}(b_{a_1}(a_{b_1}(x1))))) -> a_{a_1}(a_{b_1}(b_{b_1}(b_{a_1}(a_{b_1}(b_{a_1}(a_{a_1}(a_{b_1}(b_{b_1}(x1))))))))) 6.71/2.44 b_{a_1}(a_{b_1}(b_{a_1}(a_{b_1}(x1)))) -> b_{b_1}(b_{b_1}(b_{a_1}(a_{b_1}(b_{b_1}(b_{b_1}(x1)))))) 6.71/2.44 b_{a_1}(a_{b_1}(b_{b_1}(b_{a_1}(a_{b_1}(x1))))) -> b_{b_1}(b_{b_1}(b_{b_1}(b_{a_1}(a_{b_1}(b_{b_1}(b_{b_1}(b_{b_1}(x1)))))))) 6.71/2.44 b_{a_1}(a_{b_1}(b_{a_1}(a_{a_1}(a_{a_1}(a_{a_1}(x1)))))) -> b_{b_1}(b_{a_1}(a_{a_1}(a_{b_1}(b_{a_1}(a_{b_1}(b_{b_1}(b_{a_1}(a_{a_1}(a_{a_1}(x1)))))))))) 6.71/2.44 b_{a_1}(a_{b_1}(b_{a_1}(a_{a_1}(a_{a_1}(a_{b_1}(x1)))))) -> b_{b_1}(b_{a_1}(a_{a_1}(a_{b_1}(b_{a_1}(a_{b_1}(b_{b_1}(b_{a_1}(a_{a_1}(a_{b_1}(x1)))))))))) 6.71/2.44 b_{a_1}(a_{b_1}(b_{a_1}(a_{b_1}(b_{a_1}(a_{b_1}(x1)))))) -> b_{b_1}(b_{a_1}(a_{b_1}(b_{b_1}(b_{a_1}(a_{b_1}(b_{b_1}(b_{a_1}(a_{b_1}(b_{b_1}(x1)))))))))) 6.71/2.44 b_{a_1}(a_{b_1}(b_{b_1}(b_{b_1}(b_{a_1}(a_{b_1}(x1)))))) -> b_{b_1}(b_{b_1}(b_{b_1}(b_{b_1}(b_{a_1}(a_{b_1}(b_{b_1}(b_{b_1}(b_{b_1}(b_{b_1}(x1)))))))))) 6.71/2.44 6.71/2.44 Q is empty. 6.71/2.44 6.71/2.44 ---------------------------------------- 6.71/2.44 6.71/2.44 (7) DependencyPairsProof (EQUIVALENT) 6.71/2.44 Using Dependency Pairs [AG00,LPAR04] we result in the following initial DP problem. 6.71/2.44 ---------------------------------------- 6.71/2.44 6.71/2.44 (8) 6.71/2.44 Obligation: 6.71/2.44 Q DP problem: 6.71/2.44 The TRS P consists of the following rules: 6.71/2.44 6.71/2.44 A_{A_1}(a_{a_1}(a_{a_1}(a_{a_1}(a_{a_1}(x1))))) -> A_{A_1}(a_{a_1}(a_{b_1}(b_{a_1}(a_{b_1}(b_{a_1}(a_{a_1}(a_{a_1}(a_{a_1}(x1))))))))) 6.71/2.44 A_{A_1}(a_{a_1}(a_{a_1}(a_{a_1}(a_{a_1}(x1))))) -> A_{A_1}(a_{b_1}(b_{a_1}(a_{b_1}(b_{a_1}(a_{a_1}(a_{a_1}(a_{a_1}(x1)))))))) 6.71/2.44 A_{A_1}(a_{a_1}(a_{a_1}(a_{a_1}(a_{a_1}(x1))))) -> B_{A_1}(a_{b_1}(b_{a_1}(a_{a_1}(a_{a_1}(a_{a_1}(x1)))))) 6.71/2.44 A_{A_1}(a_{a_1}(a_{a_1}(a_{a_1}(a_{a_1}(x1))))) -> B_{A_1}(a_{a_1}(a_{a_1}(a_{a_1}(x1)))) 6.71/2.44 A_{A_1}(a_{a_1}(a_{a_1}(a_{a_1}(a_{b_1}(x1))))) -> A_{A_1}(a_{a_1}(a_{b_1}(b_{a_1}(a_{b_1}(b_{a_1}(a_{a_1}(a_{a_1}(a_{b_1}(x1))))))))) 6.71/2.44 A_{A_1}(a_{a_1}(a_{a_1}(a_{a_1}(a_{b_1}(x1))))) -> A_{A_1}(a_{b_1}(b_{a_1}(a_{b_1}(b_{a_1}(a_{a_1}(a_{a_1}(a_{b_1}(x1)))))))) 6.71/2.44 A_{A_1}(a_{a_1}(a_{a_1}(a_{a_1}(a_{b_1}(x1))))) -> B_{A_1}(a_{b_1}(b_{a_1}(a_{a_1}(a_{a_1}(a_{b_1}(x1)))))) 6.71/2.44 A_{A_1}(a_{a_1}(a_{a_1}(a_{a_1}(a_{b_1}(x1))))) -> B_{A_1}(a_{a_1}(a_{a_1}(a_{b_1}(x1)))) 6.71/2.44 A_{A_1}(a_{a_1}(a_{b_1}(b_{a_1}(a_{b_1}(x1))))) -> A_{A_1}(a_{b_1}(b_{b_1}(b_{a_1}(a_{b_1}(b_{a_1}(a_{a_1}(a_{b_1}(b_{b_1}(x1))))))))) 6.71/2.44 A_{A_1}(a_{a_1}(a_{b_1}(b_{a_1}(a_{b_1}(x1))))) -> B_{A_1}(a_{b_1}(b_{a_1}(a_{a_1}(a_{b_1}(b_{b_1}(x1)))))) 6.71/2.44 A_{A_1}(a_{a_1}(a_{b_1}(b_{a_1}(a_{b_1}(x1))))) -> B_{A_1}(a_{a_1}(a_{b_1}(b_{b_1}(x1)))) 6.71/2.44 A_{A_1}(a_{a_1}(a_{b_1}(b_{a_1}(a_{b_1}(x1))))) -> A_{A_1}(a_{b_1}(b_{b_1}(x1))) 6.71/2.44 B_{A_1}(a_{b_1}(b_{a_1}(a_{b_1}(x1)))) -> B_{A_1}(a_{b_1}(b_{b_1}(b_{b_1}(x1)))) 6.71/2.44 B_{A_1}(a_{b_1}(b_{b_1}(b_{a_1}(a_{b_1}(x1))))) -> B_{A_1}(a_{b_1}(b_{b_1}(b_{b_1}(b_{b_1}(x1))))) 6.71/2.44 B_{A_1}(a_{b_1}(b_{a_1}(a_{a_1}(a_{a_1}(a_{a_1}(x1)))))) -> B_{A_1}(a_{a_1}(a_{b_1}(b_{a_1}(a_{b_1}(b_{b_1}(b_{a_1}(a_{a_1}(a_{a_1}(x1))))))))) 6.71/2.44 B_{A_1}(a_{b_1}(b_{a_1}(a_{a_1}(a_{a_1}(a_{a_1}(x1)))))) -> A_{A_1}(a_{b_1}(b_{a_1}(a_{b_1}(b_{b_1}(b_{a_1}(a_{a_1}(a_{a_1}(x1)))))))) 6.71/2.44 B_{A_1}(a_{b_1}(b_{a_1}(a_{a_1}(a_{a_1}(a_{a_1}(x1)))))) -> B_{A_1}(a_{b_1}(b_{b_1}(b_{a_1}(a_{a_1}(a_{a_1}(x1)))))) 6.71/2.44 B_{A_1}(a_{b_1}(b_{a_1}(a_{a_1}(a_{a_1}(a_{a_1}(x1)))))) -> B_{A_1}(a_{a_1}(a_{a_1}(x1))) 6.71/2.44 B_{A_1}(a_{b_1}(b_{a_1}(a_{a_1}(a_{a_1}(a_{b_1}(x1)))))) -> B_{A_1}(a_{a_1}(a_{b_1}(b_{a_1}(a_{b_1}(b_{b_1}(b_{a_1}(a_{a_1}(a_{b_1}(x1))))))))) 6.71/2.44 B_{A_1}(a_{b_1}(b_{a_1}(a_{a_1}(a_{a_1}(a_{b_1}(x1)))))) -> A_{A_1}(a_{b_1}(b_{a_1}(a_{b_1}(b_{b_1}(b_{a_1}(a_{a_1}(a_{b_1}(x1)))))))) 6.71/2.44 B_{A_1}(a_{b_1}(b_{a_1}(a_{a_1}(a_{a_1}(a_{b_1}(x1)))))) -> B_{A_1}(a_{b_1}(b_{b_1}(b_{a_1}(a_{a_1}(a_{b_1}(x1)))))) 6.71/2.44 B_{A_1}(a_{b_1}(b_{a_1}(a_{a_1}(a_{a_1}(a_{b_1}(x1)))))) -> B_{A_1}(a_{a_1}(a_{b_1}(x1))) 6.71/2.44 B_{A_1}(a_{b_1}(b_{a_1}(a_{b_1}(b_{a_1}(a_{b_1}(x1)))))) -> B_{A_1}(a_{b_1}(b_{b_1}(b_{a_1}(a_{b_1}(b_{b_1}(b_{a_1}(a_{b_1}(b_{b_1}(x1))))))))) 6.71/2.44 B_{A_1}(a_{b_1}(b_{a_1}(a_{b_1}(b_{a_1}(a_{b_1}(x1)))))) -> B_{A_1}(a_{b_1}(b_{b_1}(b_{a_1}(a_{b_1}(b_{b_1}(x1)))))) 6.71/2.44 B_{A_1}(a_{b_1}(b_{a_1}(a_{b_1}(b_{a_1}(a_{b_1}(x1)))))) -> B_{A_1}(a_{b_1}(b_{b_1}(x1))) 6.71/2.44 B_{A_1}(a_{b_1}(b_{b_1}(b_{b_1}(b_{a_1}(a_{b_1}(x1)))))) -> B_{A_1}(a_{b_1}(b_{b_1}(b_{b_1}(b_{b_1}(b_{b_1}(x1)))))) 6.71/2.44 6.71/2.44 The TRS R consists of the following rules: 6.71/2.44 6.71/2.44 a_{a_1}(a_{a_1}(a_{a_1}(a_{a_1}(a_{a_1}(x1))))) -> a_{a_1}(a_{a_1}(a_{b_1}(b_{a_1}(a_{b_1}(b_{a_1}(a_{a_1}(a_{a_1}(a_{a_1}(x1))))))))) 6.71/2.44 a_{a_1}(a_{a_1}(a_{a_1}(a_{a_1}(a_{b_1}(x1))))) -> a_{a_1}(a_{a_1}(a_{b_1}(b_{a_1}(a_{b_1}(b_{a_1}(a_{a_1}(a_{a_1}(a_{b_1}(x1))))))))) 6.71/2.44 a_{a_1}(a_{a_1}(a_{b_1}(b_{a_1}(a_{b_1}(x1))))) -> a_{a_1}(a_{b_1}(b_{b_1}(b_{a_1}(a_{b_1}(b_{a_1}(a_{a_1}(a_{b_1}(b_{b_1}(x1))))))))) 6.71/2.44 b_{a_1}(a_{b_1}(b_{a_1}(a_{b_1}(x1)))) -> b_{b_1}(b_{b_1}(b_{a_1}(a_{b_1}(b_{b_1}(b_{b_1}(x1)))))) 6.71/2.44 b_{a_1}(a_{b_1}(b_{b_1}(b_{a_1}(a_{b_1}(x1))))) -> b_{b_1}(b_{b_1}(b_{b_1}(b_{a_1}(a_{b_1}(b_{b_1}(b_{b_1}(b_{b_1}(x1)))))))) 6.71/2.44 b_{a_1}(a_{b_1}(b_{a_1}(a_{a_1}(a_{a_1}(a_{a_1}(x1)))))) -> b_{b_1}(b_{a_1}(a_{a_1}(a_{b_1}(b_{a_1}(a_{b_1}(b_{b_1}(b_{a_1}(a_{a_1}(a_{a_1}(x1)))))))))) 6.71/2.44 b_{a_1}(a_{b_1}(b_{a_1}(a_{a_1}(a_{a_1}(a_{b_1}(x1)))))) -> b_{b_1}(b_{a_1}(a_{a_1}(a_{b_1}(b_{a_1}(a_{b_1}(b_{b_1}(b_{a_1}(a_{a_1}(a_{b_1}(x1)))))))))) 6.71/2.44 b_{a_1}(a_{b_1}(b_{a_1}(a_{b_1}(b_{a_1}(a_{b_1}(x1)))))) -> b_{b_1}(b_{a_1}(a_{b_1}(b_{b_1}(b_{a_1}(a_{b_1}(b_{b_1}(b_{a_1}(a_{b_1}(b_{b_1}(x1)))))))))) 6.71/2.44 b_{a_1}(a_{b_1}(b_{b_1}(b_{b_1}(b_{a_1}(a_{b_1}(x1)))))) -> b_{b_1}(b_{b_1}(b_{b_1}(b_{b_1}(b_{a_1}(a_{b_1}(b_{b_1}(b_{b_1}(b_{b_1}(b_{b_1}(x1)))))))))) 6.71/2.44 6.71/2.44 Q is empty. 6.71/2.44 We have to consider all minimal (P,Q,R)-chains. 6.71/2.44 ---------------------------------------- 6.71/2.44 6.71/2.44 (9) DependencyGraphProof (EQUIVALENT) 6.71/2.44 The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 0 SCCs with 26 less nodes. 6.71/2.44 ---------------------------------------- 6.71/2.44 6.71/2.44 (10) 6.71/2.44 TRUE 6.71/2.48 EOF