17.31/5.33 YES 17.55/5.36 proof of /export/starexec/sandbox2/benchmark/theBenchmark.xml 17.55/5.36 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 17.55/5.36 17.55/5.36 17.55/5.36 Termination w.r.t. Q of the given QTRS could be proven: 17.55/5.36 17.55/5.36 (0) QTRS 17.55/5.36 (1) FlatCCProof [EQUIVALENT, 0 ms] 17.55/5.36 (2) QTRS 17.55/5.36 (3) RootLabelingProof [EQUIVALENT, 0 ms] 17.55/5.36 (4) QTRS 17.55/5.36 (5) QTRSRRRProof [EQUIVALENT, 40 ms] 17.55/5.36 (6) QTRS 17.55/5.36 (7) DependencyPairsProof [EQUIVALENT, 50 ms] 17.55/5.36 (8) QDP 17.55/5.36 (9) DependencyGraphProof [EQUIVALENT, 3 ms] 17.55/5.36 (10) QDP 17.55/5.36 (11) QDPOrderProof [EQUIVALENT, 107 ms] 17.55/5.36 (12) QDP 17.55/5.36 (13) DependencyGraphProof [EQUIVALENT, 0 ms] 17.55/5.36 (14) TRUE 17.55/5.36 17.55/5.36 17.55/5.36 ---------------------------------------- 17.55/5.36 17.55/5.36 (0) 17.55/5.36 Obligation: 17.55/5.36 Q restricted rewrite system: 17.55/5.36 The TRS R consists of the following rules: 17.55/5.36 17.55/5.36 a(x1) -> x1 17.55/5.36 a(a(x1)) -> a(b(x1)) 17.55/5.36 b(x1) -> x1 17.55/5.36 c(b(x1)) -> b(a(c(c(x1)))) 17.55/5.36 17.55/5.36 Q is empty. 17.55/5.36 17.55/5.36 ---------------------------------------- 17.55/5.36 17.55/5.36 (1) FlatCCProof (EQUIVALENT) 17.55/5.36 We used flat context closure [ROOTLAB] 17.55/5.36 As Q is empty the flat context closure was sound AND complete. 17.55/5.36 17.55/5.36 ---------------------------------------- 17.55/5.36 17.55/5.36 (2) 17.55/5.36 Obligation: 17.55/5.36 Q restricted rewrite system: 17.55/5.36 The TRS R consists of the following rules: 17.55/5.36 17.55/5.36 a(a(x1)) -> a(b(x1)) 17.55/5.36 a(a(x1)) -> a(x1) 17.55/5.36 b(a(x1)) -> b(x1) 17.55/5.36 c(a(x1)) -> c(x1) 17.55/5.36 a(b(x1)) -> a(x1) 17.55/5.36 b(b(x1)) -> b(x1) 17.55/5.36 c(b(x1)) -> c(x1) 17.55/5.36 a(c(b(x1))) -> a(b(a(c(c(x1))))) 17.55/5.36 b(c(b(x1))) -> b(b(a(c(c(x1))))) 17.55/5.36 c(c(b(x1))) -> c(b(a(c(c(x1))))) 17.55/5.36 17.55/5.36 Q is empty. 17.55/5.36 17.55/5.36 ---------------------------------------- 17.55/5.36 17.55/5.36 (3) RootLabelingProof (EQUIVALENT) 17.55/5.36 We used plain root labeling [ROOTLAB] with the following heuristic: 17.55/5.36 LabelAll: All function symbols get labeled 17.55/5.36 17.55/5.36 As Q is empty the root labeling was sound AND complete. 17.55/5.36 17.55/5.36 ---------------------------------------- 17.55/5.36 17.55/5.36 (4) 17.55/5.36 Obligation: 17.55/5.36 Q restricted rewrite system: 17.55/5.36 The TRS R consists of the following rules: 17.55/5.36 17.55/5.36 a_{a_1}(a_{a_1}(x1)) -> a_{b_1}(b_{a_1}(x1)) 17.55/5.36 a_{a_1}(a_{b_1}(x1)) -> a_{b_1}(b_{b_1}(x1)) 17.55/5.36 a_{a_1}(a_{c_1}(x1)) -> a_{b_1}(b_{c_1}(x1)) 17.55/5.36 a_{a_1}(a_{a_1}(x1)) -> a_{a_1}(x1) 17.55/5.36 a_{a_1}(a_{b_1}(x1)) -> a_{b_1}(x1) 17.55/5.36 a_{a_1}(a_{c_1}(x1)) -> a_{c_1}(x1) 17.55/5.36 b_{a_1}(a_{a_1}(x1)) -> b_{a_1}(x1) 17.55/5.36 b_{a_1}(a_{b_1}(x1)) -> b_{b_1}(x1) 17.55/5.36 b_{a_1}(a_{c_1}(x1)) -> b_{c_1}(x1) 17.55/5.36 c_{a_1}(a_{a_1}(x1)) -> c_{a_1}(x1) 17.55/5.36 c_{a_1}(a_{b_1}(x1)) -> c_{b_1}(x1) 17.55/5.36 c_{a_1}(a_{c_1}(x1)) -> c_{c_1}(x1) 17.55/5.36 a_{b_1}(b_{a_1}(x1)) -> a_{a_1}(x1) 17.55/5.36 a_{b_1}(b_{b_1}(x1)) -> a_{b_1}(x1) 17.55/5.36 a_{b_1}(b_{c_1}(x1)) -> a_{c_1}(x1) 17.55/5.36 b_{b_1}(b_{a_1}(x1)) -> b_{a_1}(x1) 17.55/5.36 b_{b_1}(b_{b_1}(x1)) -> b_{b_1}(x1) 17.55/5.36 b_{b_1}(b_{c_1}(x1)) -> b_{c_1}(x1) 17.55/5.36 c_{b_1}(b_{a_1}(x1)) -> c_{a_1}(x1) 17.55/5.36 c_{b_1}(b_{b_1}(x1)) -> c_{b_1}(x1) 17.55/5.36 c_{b_1}(b_{c_1}(x1)) -> c_{c_1}(x1) 17.55/5.36 a_{c_1}(c_{b_1}(b_{a_1}(x1))) -> a_{b_1}(b_{a_1}(a_{c_1}(c_{c_1}(c_{a_1}(x1))))) 17.55/5.36 a_{c_1}(c_{b_1}(b_{b_1}(x1))) -> a_{b_1}(b_{a_1}(a_{c_1}(c_{c_1}(c_{b_1}(x1))))) 17.55/5.36 a_{c_1}(c_{b_1}(b_{c_1}(x1))) -> a_{b_1}(b_{a_1}(a_{c_1}(c_{c_1}(c_{c_1}(x1))))) 17.55/5.36 b_{c_1}(c_{b_1}(b_{a_1}(x1))) -> b_{b_1}(b_{a_1}(a_{c_1}(c_{c_1}(c_{a_1}(x1))))) 17.55/5.36 b_{c_1}(c_{b_1}(b_{b_1}(x1))) -> b_{b_1}(b_{a_1}(a_{c_1}(c_{c_1}(c_{b_1}(x1))))) 17.55/5.36 b_{c_1}(c_{b_1}(b_{c_1}(x1))) -> b_{b_1}(b_{a_1}(a_{c_1}(c_{c_1}(c_{c_1}(x1))))) 17.55/5.36 c_{c_1}(c_{b_1}(b_{a_1}(x1))) -> c_{b_1}(b_{a_1}(a_{c_1}(c_{c_1}(c_{a_1}(x1))))) 17.55/5.36 c_{c_1}(c_{b_1}(b_{b_1}(x1))) -> c_{b_1}(b_{a_1}(a_{c_1}(c_{c_1}(c_{b_1}(x1))))) 17.55/5.36 c_{c_1}(c_{b_1}(b_{c_1}(x1))) -> c_{b_1}(b_{a_1}(a_{c_1}(c_{c_1}(c_{c_1}(x1))))) 17.55/5.36 17.55/5.36 Q is empty. 17.55/5.36 17.55/5.36 ---------------------------------------- 17.55/5.36 17.55/5.36 (5) QTRSRRRProof (EQUIVALENT) 17.55/5.36 Used ordering: 17.55/5.36 Polynomial interpretation [POLO]: 17.55/5.36 17.55/5.36 POL(a_{a_1}(x_1)) = 1 + x_1 17.55/5.36 POL(a_{b_1}(x_1)) = x_1 17.55/5.36 POL(a_{c_1}(x_1)) = x_1 17.55/5.36 POL(b_{a_1}(x_1)) = 1 + x_1 17.55/5.36 POL(b_{b_1}(x_1)) = 1 + x_1 17.55/5.36 POL(b_{c_1}(x_1)) = 1 + x_1 17.55/5.36 POL(c_{a_1}(x_1)) = x_1 17.55/5.36 POL(c_{b_1}(x_1)) = x_1 17.55/5.36 POL(c_{c_1}(x_1)) = x_1 17.55/5.36 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: 17.55/5.36 17.55/5.36 a_{a_1}(a_{a_1}(x1)) -> a_{b_1}(b_{a_1}(x1)) 17.55/5.36 a_{a_1}(a_{a_1}(x1)) -> a_{a_1}(x1) 17.55/5.36 a_{a_1}(a_{b_1}(x1)) -> a_{b_1}(x1) 17.55/5.36 a_{a_1}(a_{c_1}(x1)) -> a_{c_1}(x1) 17.55/5.36 b_{a_1}(a_{a_1}(x1)) -> b_{a_1}(x1) 17.55/5.36 c_{a_1}(a_{a_1}(x1)) -> c_{a_1}(x1) 17.55/5.36 a_{b_1}(b_{b_1}(x1)) -> a_{b_1}(x1) 17.55/5.36 a_{b_1}(b_{c_1}(x1)) -> a_{c_1}(x1) 17.55/5.36 b_{b_1}(b_{a_1}(x1)) -> b_{a_1}(x1) 17.55/5.36 b_{b_1}(b_{b_1}(x1)) -> b_{b_1}(x1) 17.55/5.36 b_{b_1}(b_{c_1}(x1)) -> b_{c_1}(x1) 17.55/5.36 c_{b_1}(b_{a_1}(x1)) -> c_{a_1}(x1) 17.55/5.36 c_{b_1}(b_{b_1}(x1)) -> c_{b_1}(x1) 17.55/5.36 c_{b_1}(b_{c_1}(x1)) -> c_{c_1}(x1) 17.55/5.36 17.55/5.36 17.55/5.36 17.55/5.36 17.55/5.36 ---------------------------------------- 17.55/5.36 17.55/5.36 (6) 17.55/5.36 Obligation: 17.55/5.36 Q restricted rewrite system: 17.55/5.36 The TRS R consists of the following rules: 17.55/5.36 17.55/5.36 a_{a_1}(a_{b_1}(x1)) -> a_{b_1}(b_{b_1}(x1)) 17.55/5.36 a_{a_1}(a_{c_1}(x1)) -> a_{b_1}(b_{c_1}(x1)) 17.55/5.36 b_{a_1}(a_{b_1}(x1)) -> b_{b_1}(x1) 17.55/5.36 b_{a_1}(a_{c_1}(x1)) -> b_{c_1}(x1) 17.55/5.36 c_{a_1}(a_{b_1}(x1)) -> c_{b_1}(x1) 17.55/5.36 c_{a_1}(a_{c_1}(x1)) -> c_{c_1}(x1) 17.55/5.36 a_{b_1}(b_{a_1}(x1)) -> a_{a_1}(x1) 17.55/5.36 a_{c_1}(c_{b_1}(b_{a_1}(x1))) -> a_{b_1}(b_{a_1}(a_{c_1}(c_{c_1}(c_{a_1}(x1))))) 17.55/5.36 a_{c_1}(c_{b_1}(b_{b_1}(x1))) -> a_{b_1}(b_{a_1}(a_{c_1}(c_{c_1}(c_{b_1}(x1))))) 17.55/5.36 a_{c_1}(c_{b_1}(b_{c_1}(x1))) -> a_{b_1}(b_{a_1}(a_{c_1}(c_{c_1}(c_{c_1}(x1))))) 17.55/5.36 b_{c_1}(c_{b_1}(b_{a_1}(x1))) -> b_{b_1}(b_{a_1}(a_{c_1}(c_{c_1}(c_{a_1}(x1))))) 17.55/5.36 b_{c_1}(c_{b_1}(b_{b_1}(x1))) -> b_{b_1}(b_{a_1}(a_{c_1}(c_{c_1}(c_{b_1}(x1))))) 17.55/5.36 b_{c_1}(c_{b_1}(b_{c_1}(x1))) -> b_{b_1}(b_{a_1}(a_{c_1}(c_{c_1}(c_{c_1}(x1))))) 17.55/5.36 c_{c_1}(c_{b_1}(b_{a_1}(x1))) -> c_{b_1}(b_{a_1}(a_{c_1}(c_{c_1}(c_{a_1}(x1))))) 17.55/5.36 c_{c_1}(c_{b_1}(b_{b_1}(x1))) -> c_{b_1}(b_{a_1}(a_{c_1}(c_{c_1}(c_{b_1}(x1))))) 17.55/5.36 c_{c_1}(c_{b_1}(b_{c_1}(x1))) -> c_{b_1}(b_{a_1}(a_{c_1}(c_{c_1}(c_{c_1}(x1))))) 17.55/5.36 17.55/5.36 Q is empty. 17.55/5.36 17.55/5.36 ---------------------------------------- 17.55/5.36 17.55/5.36 (7) DependencyPairsProof (EQUIVALENT) 17.55/5.36 Using Dependency Pairs [AG00,LPAR04] we result in the following initial DP problem. 17.55/5.36 ---------------------------------------- 17.55/5.36 17.55/5.36 (8) 17.55/5.36 Obligation: 17.55/5.36 Q DP problem: 17.55/5.36 The TRS P consists of the following rules: 17.55/5.36 17.55/5.36 A_{A_1}(a_{b_1}(x1)) -> A_{B_1}(b_{b_1}(x1)) 17.55/5.36 A_{A_1}(a_{c_1}(x1)) -> A_{B_1}(b_{c_1}(x1)) 17.55/5.36 A_{A_1}(a_{c_1}(x1)) -> B_{C_1}(x1) 17.55/5.36 B_{A_1}(a_{c_1}(x1)) -> B_{C_1}(x1) 17.55/5.36 C_{A_1}(a_{c_1}(x1)) -> C_{C_1}(x1) 17.55/5.36 A_{B_1}(b_{a_1}(x1)) -> A_{A_1}(x1) 17.55/5.36 A_{C_1}(c_{b_1}(b_{a_1}(x1))) -> A_{B_1}(b_{a_1}(a_{c_1}(c_{c_1}(c_{a_1}(x1))))) 17.55/5.36 A_{C_1}(c_{b_1}(b_{a_1}(x1))) -> B_{A_1}(a_{c_1}(c_{c_1}(c_{a_1}(x1)))) 17.55/5.36 A_{C_1}(c_{b_1}(b_{a_1}(x1))) -> A_{C_1}(c_{c_1}(c_{a_1}(x1))) 17.55/5.36 A_{C_1}(c_{b_1}(b_{a_1}(x1))) -> C_{C_1}(c_{a_1}(x1)) 17.55/5.36 A_{C_1}(c_{b_1}(b_{a_1}(x1))) -> C_{A_1}(x1) 17.55/5.36 A_{C_1}(c_{b_1}(b_{b_1}(x1))) -> A_{B_1}(b_{a_1}(a_{c_1}(c_{c_1}(c_{b_1}(x1))))) 17.55/5.36 A_{C_1}(c_{b_1}(b_{b_1}(x1))) -> B_{A_1}(a_{c_1}(c_{c_1}(c_{b_1}(x1)))) 17.55/5.36 A_{C_1}(c_{b_1}(b_{b_1}(x1))) -> A_{C_1}(c_{c_1}(c_{b_1}(x1))) 17.55/5.36 A_{C_1}(c_{b_1}(b_{b_1}(x1))) -> C_{C_1}(c_{b_1}(x1)) 17.55/5.36 A_{C_1}(c_{b_1}(b_{c_1}(x1))) -> A_{B_1}(b_{a_1}(a_{c_1}(c_{c_1}(c_{c_1}(x1))))) 17.55/5.36 A_{C_1}(c_{b_1}(b_{c_1}(x1))) -> B_{A_1}(a_{c_1}(c_{c_1}(c_{c_1}(x1)))) 17.55/5.36 A_{C_1}(c_{b_1}(b_{c_1}(x1))) -> A_{C_1}(c_{c_1}(c_{c_1}(x1))) 17.55/5.36 A_{C_1}(c_{b_1}(b_{c_1}(x1))) -> C_{C_1}(c_{c_1}(x1)) 17.55/5.36 A_{C_1}(c_{b_1}(b_{c_1}(x1))) -> C_{C_1}(x1) 17.55/5.36 B_{C_1}(c_{b_1}(b_{a_1}(x1))) -> B_{A_1}(a_{c_1}(c_{c_1}(c_{a_1}(x1)))) 17.55/5.36 B_{C_1}(c_{b_1}(b_{a_1}(x1))) -> A_{C_1}(c_{c_1}(c_{a_1}(x1))) 17.55/5.36 B_{C_1}(c_{b_1}(b_{a_1}(x1))) -> C_{C_1}(c_{a_1}(x1)) 17.55/5.36 B_{C_1}(c_{b_1}(b_{a_1}(x1))) -> C_{A_1}(x1) 17.55/5.36 B_{C_1}(c_{b_1}(b_{b_1}(x1))) -> B_{A_1}(a_{c_1}(c_{c_1}(c_{b_1}(x1)))) 17.55/5.36 B_{C_1}(c_{b_1}(b_{b_1}(x1))) -> A_{C_1}(c_{c_1}(c_{b_1}(x1))) 17.55/5.36 B_{C_1}(c_{b_1}(b_{b_1}(x1))) -> C_{C_1}(c_{b_1}(x1)) 17.55/5.36 B_{C_1}(c_{b_1}(b_{c_1}(x1))) -> B_{A_1}(a_{c_1}(c_{c_1}(c_{c_1}(x1)))) 17.55/5.36 B_{C_1}(c_{b_1}(b_{c_1}(x1))) -> A_{C_1}(c_{c_1}(c_{c_1}(x1))) 17.55/5.36 B_{C_1}(c_{b_1}(b_{c_1}(x1))) -> C_{C_1}(c_{c_1}(x1)) 17.55/5.36 B_{C_1}(c_{b_1}(b_{c_1}(x1))) -> C_{C_1}(x1) 17.55/5.36 C_{C_1}(c_{b_1}(b_{a_1}(x1))) -> B_{A_1}(a_{c_1}(c_{c_1}(c_{a_1}(x1)))) 17.55/5.36 C_{C_1}(c_{b_1}(b_{a_1}(x1))) -> A_{C_1}(c_{c_1}(c_{a_1}(x1))) 17.55/5.36 C_{C_1}(c_{b_1}(b_{a_1}(x1))) -> C_{C_1}(c_{a_1}(x1)) 17.55/5.36 C_{C_1}(c_{b_1}(b_{a_1}(x1))) -> C_{A_1}(x1) 17.55/5.36 C_{C_1}(c_{b_1}(b_{b_1}(x1))) -> B_{A_1}(a_{c_1}(c_{c_1}(c_{b_1}(x1)))) 17.55/5.36 C_{C_1}(c_{b_1}(b_{b_1}(x1))) -> A_{C_1}(c_{c_1}(c_{b_1}(x1))) 17.55/5.36 C_{C_1}(c_{b_1}(b_{b_1}(x1))) -> C_{C_1}(c_{b_1}(x1)) 17.55/5.36 C_{C_1}(c_{b_1}(b_{c_1}(x1))) -> B_{A_1}(a_{c_1}(c_{c_1}(c_{c_1}(x1)))) 17.55/5.36 C_{C_1}(c_{b_1}(b_{c_1}(x1))) -> A_{C_1}(c_{c_1}(c_{c_1}(x1))) 17.55/5.36 C_{C_1}(c_{b_1}(b_{c_1}(x1))) -> C_{C_1}(c_{c_1}(x1)) 17.55/5.36 C_{C_1}(c_{b_1}(b_{c_1}(x1))) -> C_{C_1}(x1) 17.55/5.36 17.55/5.36 The TRS R consists of the following rules: 17.55/5.36 17.55/5.36 a_{a_1}(a_{b_1}(x1)) -> a_{b_1}(b_{b_1}(x1)) 17.55/5.36 a_{a_1}(a_{c_1}(x1)) -> a_{b_1}(b_{c_1}(x1)) 17.55/5.36 b_{a_1}(a_{b_1}(x1)) -> b_{b_1}(x1) 17.55/5.36 b_{a_1}(a_{c_1}(x1)) -> b_{c_1}(x1) 17.55/5.36 c_{a_1}(a_{b_1}(x1)) -> c_{b_1}(x1) 17.55/5.36 c_{a_1}(a_{c_1}(x1)) -> c_{c_1}(x1) 17.55/5.36 a_{b_1}(b_{a_1}(x1)) -> a_{a_1}(x1) 17.55/5.36 a_{c_1}(c_{b_1}(b_{a_1}(x1))) -> a_{b_1}(b_{a_1}(a_{c_1}(c_{c_1}(c_{a_1}(x1))))) 17.55/5.36 a_{c_1}(c_{b_1}(b_{b_1}(x1))) -> a_{b_1}(b_{a_1}(a_{c_1}(c_{c_1}(c_{b_1}(x1))))) 17.55/5.36 a_{c_1}(c_{b_1}(b_{c_1}(x1))) -> a_{b_1}(b_{a_1}(a_{c_1}(c_{c_1}(c_{c_1}(x1))))) 17.55/5.36 b_{c_1}(c_{b_1}(b_{a_1}(x1))) -> b_{b_1}(b_{a_1}(a_{c_1}(c_{c_1}(c_{a_1}(x1))))) 17.55/5.36 b_{c_1}(c_{b_1}(b_{b_1}(x1))) -> b_{b_1}(b_{a_1}(a_{c_1}(c_{c_1}(c_{b_1}(x1))))) 17.55/5.36 b_{c_1}(c_{b_1}(b_{c_1}(x1))) -> b_{b_1}(b_{a_1}(a_{c_1}(c_{c_1}(c_{c_1}(x1))))) 17.55/5.36 c_{c_1}(c_{b_1}(b_{a_1}(x1))) -> c_{b_1}(b_{a_1}(a_{c_1}(c_{c_1}(c_{a_1}(x1))))) 17.55/5.36 c_{c_1}(c_{b_1}(b_{b_1}(x1))) -> c_{b_1}(b_{a_1}(a_{c_1}(c_{c_1}(c_{b_1}(x1))))) 17.55/5.36 c_{c_1}(c_{b_1}(b_{c_1}(x1))) -> c_{b_1}(b_{a_1}(a_{c_1}(c_{c_1}(c_{c_1}(x1))))) 17.55/5.36 17.55/5.36 Q is empty. 17.55/5.36 We have to consider all minimal (P,Q,R)-chains. 17.55/5.36 ---------------------------------------- 17.55/5.36 17.55/5.36 (9) DependencyGraphProof (EQUIVALENT) 17.55/5.36 The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 2 less nodes. 17.55/5.36 ---------------------------------------- 17.55/5.36 17.55/5.36 (10) 17.55/5.36 Obligation: 17.55/5.36 Q DP problem: 17.55/5.36 The TRS P consists of the following rules: 17.55/5.36 17.55/5.36 A_{A_1}(a_{c_1}(x1)) -> B_{C_1}(x1) 17.55/5.36 B_{C_1}(c_{b_1}(b_{a_1}(x1))) -> B_{A_1}(a_{c_1}(c_{c_1}(c_{a_1}(x1)))) 17.55/5.36 B_{A_1}(a_{c_1}(x1)) -> B_{C_1}(x1) 17.55/5.36 B_{C_1}(c_{b_1}(b_{a_1}(x1))) -> A_{C_1}(c_{c_1}(c_{a_1}(x1))) 17.55/5.36 A_{C_1}(c_{b_1}(b_{a_1}(x1))) -> A_{B_1}(b_{a_1}(a_{c_1}(c_{c_1}(c_{a_1}(x1))))) 17.55/5.36 A_{B_1}(b_{a_1}(x1)) -> A_{A_1}(x1) 17.55/5.36 A_{C_1}(c_{b_1}(b_{a_1}(x1))) -> B_{A_1}(a_{c_1}(c_{c_1}(c_{a_1}(x1)))) 17.55/5.36 A_{C_1}(c_{b_1}(b_{a_1}(x1))) -> A_{C_1}(c_{c_1}(c_{a_1}(x1))) 17.55/5.36 A_{C_1}(c_{b_1}(b_{a_1}(x1))) -> C_{C_1}(c_{a_1}(x1)) 17.55/5.36 C_{C_1}(c_{b_1}(b_{a_1}(x1))) -> B_{A_1}(a_{c_1}(c_{c_1}(c_{a_1}(x1)))) 17.55/5.36 C_{C_1}(c_{b_1}(b_{a_1}(x1))) -> A_{C_1}(c_{c_1}(c_{a_1}(x1))) 17.55/5.36 A_{C_1}(c_{b_1}(b_{a_1}(x1))) -> C_{A_1}(x1) 17.55/5.36 C_{A_1}(a_{c_1}(x1)) -> C_{C_1}(x1) 17.55/5.36 C_{C_1}(c_{b_1}(b_{a_1}(x1))) -> C_{C_1}(c_{a_1}(x1)) 17.55/5.36 C_{C_1}(c_{b_1}(b_{a_1}(x1))) -> C_{A_1}(x1) 17.55/5.36 C_{C_1}(c_{b_1}(b_{b_1}(x1))) -> B_{A_1}(a_{c_1}(c_{c_1}(c_{b_1}(x1)))) 17.55/5.36 C_{C_1}(c_{b_1}(b_{b_1}(x1))) -> A_{C_1}(c_{c_1}(c_{b_1}(x1))) 17.55/5.36 A_{C_1}(c_{b_1}(b_{b_1}(x1))) -> A_{B_1}(b_{a_1}(a_{c_1}(c_{c_1}(c_{b_1}(x1))))) 17.55/5.36 A_{C_1}(c_{b_1}(b_{b_1}(x1))) -> B_{A_1}(a_{c_1}(c_{c_1}(c_{b_1}(x1)))) 17.55/5.36 A_{C_1}(c_{b_1}(b_{b_1}(x1))) -> A_{C_1}(c_{c_1}(c_{b_1}(x1))) 17.55/5.36 A_{C_1}(c_{b_1}(b_{b_1}(x1))) -> C_{C_1}(c_{b_1}(x1)) 17.55/5.36 C_{C_1}(c_{b_1}(b_{b_1}(x1))) -> C_{C_1}(c_{b_1}(x1)) 17.55/5.36 C_{C_1}(c_{b_1}(b_{c_1}(x1))) -> B_{A_1}(a_{c_1}(c_{c_1}(c_{c_1}(x1)))) 17.55/5.36 C_{C_1}(c_{b_1}(b_{c_1}(x1))) -> A_{C_1}(c_{c_1}(c_{c_1}(x1))) 17.55/5.36 A_{C_1}(c_{b_1}(b_{c_1}(x1))) -> A_{B_1}(b_{a_1}(a_{c_1}(c_{c_1}(c_{c_1}(x1))))) 17.55/5.36 A_{C_1}(c_{b_1}(b_{c_1}(x1))) -> B_{A_1}(a_{c_1}(c_{c_1}(c_{c_1}(x1)))) 17.55/5.36 A_{C_1}(c_{b_1}(b_{c_1}(x1))) -> A_{C_1}(c_{c_1}(c_{c_1}(x1))) 17.55/5.36 A_{C_1}(c_{b_1}(b_{c_1}(x1))) -> C_{C_1}(c_{c_1}(x1)) 17.55/5.36 C_{C_1}(c_{b_1}(b_{c_1}(x1))) -> C_{C_1}(c_{c_1}(x1)) 17.55/5.36 C_{C_1}(c_{b_1}(b_{c_1}(x1))) -> C_{C_1}(x1) 17.55/5.36 A_{C_1}(c_{b_1}(b_{c_1}(x1))) -> C_{C_1}(x1) 17.55/5.36 B_{C_1}(c_{b_1}(b_{a_1}(x1))) -> C_{C_1}(c_{a_1}(x1)) 17.55/5.36 B_{C_1}(c_{b_1}(b_{a_1}(x1))) -> C_{A_1}(x1) 17.55/5.36 B_{C_1}(c_{b_1}(b_{b_1}(x1))) -> B_{A_1}(a_{c_1}(c_{c_1}(c_{b_1}(x1)))) 17.55/5.36 B_{C_1}(c_{b_1}(b_{b_1}(x1))) -> A_{C_1}(c_{c_1}(c_{b_1}(x1))) 17.55/5.36 B_{C_1}(c_{b_1}(b_{b_1}(x1))) -> C_{C_1}(c_{b_1}(x1)) 17.55/5.36 B_{C_1}(c_{b_1}(b_{c_1}(x1))) -> B_{A_1}(a_{c_1}(c_{c_1}(c_{c_1}(x1)))) 17.55/5.36 B_{C_1}(c_{b_1}(b_{c_1}(x1))) -> A_{C_1}(c_{c_1}(c_{c_1}(x1))) 17.55/5.36 B_{C_1}(c_{b_1}(b_{c_1}(x1))) -> C_{C_1}(c_{c_1}(x1)) 17.55/5.36 B_{C_1}(c_{b_1}(b_{c_1}(x1))) -> C_{C_1}(x1) 17.55/5.36 17.55/5.36 The TRS R consists of the following rules: 17.55/5.36 17.55/5.36 a_{a_1}(a_{b_1}(x1)) -> a_{b_1}(b_{b_1}(x1)) 17.55/5.36 a_{a_1}(a_{c_1}(x1)) -> a_{b_1}(b_{c_1}(x1)) 17.55/5.36 b_{a_1}(a_{b_1}(x1)) -> b_{b_1}(x1) 17.55/5.36 b_{a_1}(a_{c_1}(x1)) -> b_{c_1}(x1) 17.55/5.36 c_{a_1}(a_{b_1}(x1)) -> c_{b_1}(x1) 17.55/5.36 c_{a_1}(a_{c_1}(x1)) -> c_{c_1}(x1) 17.55/5.36 a_{b_1}(b_{a_1}(x1)) -> a_{a_1}(x1) 17.55/5.36 a_{c_1}(c_{b_1}(b_{a_1}(x1))) -> a_{b_1}(b_{a_1}(a_{c_1}(c_{c_1}(c_{a_1}(x1))))) 17.55/5.36 a_{c_1}(c_{b_1}(b_{b_1}(x1))) -> a_{b_1}(b_{a_1}(a_{c_1}(c_{c_1}(c_{b_1}(x1))))) 17.55/5.36 a_{c_1}(c_{b_1}(b_{c_1}(x1))) -> a_{b_1}(b_{a_1}(a_{c_1}(c_{c_1}(c_{c_1}(x1))))) 17.55/5.36 b_{c_1}(c_{b_1}(b_{a_1}(x1))) -> b_{b_1}(b_{a_1}(a_{c_1}(c_{c_1}(c_{a_1}(x1))))) 17.55/5.36 b_{c_1}(c_{b_1}(b_{b_1}(x1))) -> b_{b_1}(b_{a_1}(a_{c_1}(c_{c_1}(c_{b_1}(x1))))) 17.55/5.36 b_{c_1}(c_{b_1}(b_{c_1}(x1))) -> b_{b_1}(b_{a_1}(a_{c_1}(c_{c_1}(c_{c_1}(x1))))) 17.55/5.36 c_{c_1}(c_{b_1}(b_{a_1}(x1))) -> c_{b_1}(b_{a_1}(a_{c_1}(c_{c_1}(c_{a_1}(x1))))) 17.55/5.36 c_{c_1}(c_{b_1}(b_{b_1}(x1))) -> c_{b_1}(b_{a_1}(a_{c_1}(c_{c_1}(c_{b_1}(x1))))) 17.55/5.36 c_{c_1}(c_{b_1}(b_{c_1}(x1))) -> c_{b_1}(b_{a_1}(a_{c_1}(c_{c_1}(c_{c_1}(x1))))) 17.55/5.36 17.55/5.36 Q is empty. 17.55/5.36 We have to consider all minimal (P,Q,R)-chains. 17.55/5.36 ---------------------------------------- 17.55/5.36 17.55/5.36 (11) QDPOrderProof (EQUIVALENT) 17.55/5.36 We use the reduction pair processor [LPAR04,JAR06]. 17.55/5.36 17.55/5.36 17.55/5.36 The following pairs can be oriented strictly and are deleted. 17.55/5.36 17.55/5.36 A_{A_1}(a_{c_1}(x1)) -> B_{C_1}(x1) 17.55/5.36 B_{C_1}(c_{b_1}(b_{a_1}(x1))) -> B_{A_1}(a_{c_1}(c_{c_1}(c_{a_1}(x1)))) 17.55/5.36 B_{C_1}(c_{b_1}(b_{a_1}(x1))) -> A_{C_1}(c_{c_1}(c_{a_1}(x1))) 17.55/5.36 A_{C_1}(c_{b_1}(b_{a_1}(x1))) -> B_{A_1}(a_{c_1}(c_{c_1}(c_{a_1}(x1)))) 17.55/5.36 A_{C_1}(c_{b_1}(b_{a_1}(x1))) -> A_{C_1}(c_{c_1}(c_{a_1}(x1))) 17.55/5.36 A_{C_1}(c_{b_1}(b_{a_1}(x1))) -> C_{C_1}(c_{a_1}(x1)) 17.55/5.36 C_{C_1}(c_{b_1}(b_{a_1}(x1))) -> B_{A_1}(a_{c_1}(c_{c_1}(c_{a_1}(x1)))) 17.55/5.36 C_{C_1}(c_{b_1}(b_{a_1}(x1))) -> A_{C_1}(c_{c_1}(c_{a_1}(x1))) 17.55/5.36 A_{C_1}(c_{b_1}(b_{a_1}(x1))) -> C_{A_1}(x1) 17.55/5.36 C_{C_1}(c_{b_1}(b_{a_1}(x1))) -> C_{C_1}(c_{a_1}(x1)) 17.55/5.36 C_{C_1}(c_{b_1}(b_{a_1}(x1))) -> C_{A_1}(x1) 17.55/5.36 C_{C_1}(c_{b_1}(b_{b_1}(x1))) -> B_{A_1}(a_{c_1}(c_{c_1}(c_{b_1}(x1)))) 17.55/5.36 C_{C_1}(c_{b_1}(b_{b_1}(x1))) -> A_{C_1}(c_{c_1}(c_{b_1}(x1))) 17.55/5.36 A_{C_1}(c_{b_1}(b_{b_1}(x1))) -> B_{A_1}(a_{c_1}(c_{c_1}(c_{b_1}(x1)))) 17.55/5.36 A_{C_1}(c_{b_1}(b_{b_1}(x1))) -> A_{C_1}(c_{c_1}(c_{b_1}(x1))) 17.55/5.36 A_{C_1}(c_{b_1}(b_{b_1}(x1))) -> C_{C_1}(c_{b_1}(x1)) 17.55/5.36 C_{C_1}(c_{b_1}(b_{b_1}(x1))) -> C_{C_1}(c_{b_1}(x1)) 17.55/5.36 C_{C_1}(c_{b_1}(b_{c_1}(x1))) -> B_{A_1}(a_{c_1}(c_{c_1}(c_{c_1}(x1)))) 17.55/5.36 C_{C_1}(c_{b_1}(b_{c_1}(x1))) -> A_{C_1}(c_{c_1}(c_{c_1}(x1))) 17.55/5.36 A_{C_1}(c_{b_1}(b_{c_1}(x1))) -> B_{A_1}(a_{c_1}(c_{c_1}(c_{c_1}(x1)))) 17.55/5.36 A_{C_1}(c_{b_1}(b_{c_1}(x1))) -> A_{C_1}(c_{c_1}(c_{c_1}(x1))) 17.55/5.36 A_{C_1}(c_{b_1}(b_{c_1}(x1))) -> C_{C_1}(c_{c_1}(x1)) 17.55/5.36 C_{C_1}(c_{b_1}(b_{c_1}(x1))) -> C_{C_1}(c_{c_1}(x1)) 17.55/5.36 C_{C_1}(c_{b_1}(b_{c_1}(x1))) -> C_{C_1}(x1) 17.55/5.36 A_{C_1}(c_{b_1}(b_{c_1}(x1))) -> C_{C_1}(x1) 17.55/5.36 B_{C_1}(c_{b_1}(b_{a_1}(x1))) -> C_{C_1}(c_{a_1}(x1)) 17.55/5.36 B_{C_1}(c_{b_1}(b_{a_1}(x1))) -> C_{A_1}(x1) 17.55/5.36 B_{C_1}(c_{b_1}(b_{b_1}(x1))) -> B_{A_1}(a_{c_1}(c_{c_1}(c_{b_1}(x1)))) 17.55/5.36 B_{C_1}(c_{b_1}(b_{b_1}(x1))) -> A_{C_1}(c_{c_1}(c_{b_1}(x1))) 17.55/5.36 B_{C_1}(c_{b_1}(b_{b_1}(x1))) -> C_{C_1}(c_{b_1}(x1)) 17.55/5.36 B_{C_1}(c_{b_1}(b_{c_1}(x1))) -> B_{A_1}(a_{c_1}(c_{c_1}(c_{c_1}(x1)))) 17.55/5.36 B_{C_1}(c_{b_1}(b_{c_1}(x1))) -> A_{C_1}(c_{c_1}(c_{c_1}(x1))) 17.55/5.36 B_{C_1}(c_{b_1}(b_{c_1}(x1))) -> C_{C_1}(c_{c_1}(x1)) 17.55/5.36 B_{C_1}(c_{b_1}(b_{c_1}(x1))) -> C_{C_1}(x1) 17.55/5.36 The remaining pairs can at least be oriented weakly. 17.55/5.36 Used ordering: Polynomial interpretation [POLO]: 17.55/5.36 17.55/5.36 POL(A_{A_1}(x_1)) = 1 + x_1 17.55/5.36 POL(A_{B_1}(x_1)) = x_1 17.55/5.36 POL(A_{C_1}(x_1)) = x_1 17.55/5.36 POL(B_{A_1}(x_1)) = x_1 17.55/5.36 POL(B_{C_1}(x_1)) = x_1 17.55/5.36 POL(C_{A_1}(x_1)) = x_1 17.55/5.36 POL(C_{C_1}(x_1)) = x_1 17.55/5.36 POL(a_{a_1}(x_1)) = 1 + x_1 17.55/5.36 POL(a_{b_1}(x_1)) = x_1 17.55/5.36 POL(a_{c_1}(x_1)) = x_1 17.55/5.36 POL(b_{a_1}(x_1)) = 1 + x_1 17.55/5.36 POL(b_{b_1}(x_1)) = 1 + x_1 17.55/5.36 POL(b_{c_1}(x_1)) = 1 + x_1 17.55/5.36 POL(c_{a_1}(x_1)) = x_1 17.55/5.36 POL(c_{b_1}(x_1)) = x_1 17.55/5.36 POL(c_{c_1}(x_1)) = x_1 17.55/5.36 17.55/5.36 The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: 17.55/5.36 17.55/5.36 c_{a_1}(a_{b_1}(x1)) -> c_{b_1}(x1) 17.55/5.36 c_{a_1}(a_{c_1}(x1)) -> c_{c_1}(x1) 17.55/5.36 c_{c_1}(c_{b_1}(b_{a_1}(x1))) -> c_{b_1}(b_{a_1}(a_{c_1}(c_{c_1}(c_{a_1}(x1))))) 17.55/5.36 c_{c_1}(c_{b_1}(b_{b_1}(x1))) -> c_{b_1}(b_{a_1}(a_{c_1}(c_{c_1}(c_{b_1}(x1))))) 17.55/5.36 c_{c_1}(c_{b_1}(b_{c_1}(x1))) -> c_{b_1}(b_{a_1}(a_{c_1}(c_{c_1}(c_{c_1}(x1))))) 17.55/5.36 a_{c_1}(c_{b_1}(b_{a_1}(x1))) -> a_{b_1}(b_{a_1}(a_{c_1}(c_{c_1}(c_{a_1}(x1))))) 17.55/5.36 a_{c_1}(c_{b_1}(b_{b_1}(x1))) -> a_{b_1}(b_{a_1}(a_{c_1}(c_{c_1}(c_{b_1}(x1))))) 17.55/5.36 a_{c_1}(c_{b_1}(b_{c_1}(x1))) -> a_{b_1}(b_{a_1}(a_{c_1}(c_{c_1}(c_{c_1}(x1))))) 17.55/5.36 b_{a_1}(a_{b_1}(x1)) -> b_{b_1}(x1) 17.55/5.36 b_{a_1}(a_{c_1}(x1)) -> b_{c_1}(x1) 17.55/5.36 a_{a_1}(a_{c_1}(x1)) -> a_{b_1}(b_{c_1}(x1)) 17.55/5.36 a_{b_1}(b_{a_1}(x1)) -> a_{a_1}(x1) 17.55/5.36 b_{c_1}(c_{b_1}(b_{a_1}(x1))) -> b_{b_1}(b_{a_1}(a_{c_1}(c_{c_1}(c_{a_1}(x1))))) 17.55/5.36 b_{c_1}(c_{b_1}(b_{b_1}(x1))) -> b_{b_1}(b_{a_1}(a_{c_1}(c_{c_1}(c_{b_1}(x1))))) 17.55/5.36 b_{c_1}(c_{b_1}(b_{c_1}(x1))) -> b_{b_1}(b_{a_1}(a_{c_1}(c_{c_1}(c_{c_1}(x1))))) 17.55/5.36 a_{a_1}(a_{b_1}(x1)) -> a_{b_1}(b_{b_1}(x1)) 17.55/5.36 17.55/5.36 17.55/5.36 ---------------------------------------- 17.55/5.36 17.55/5.36 (12) 17.55/5.36 Obligation: 17.55/5.36 Q DP problem: 17.55/5.36 The TRS P consists of the following rules: 17.55/5.36 17.55/5.36 B_{A_1}(a_{c_1}(x1)) -> B_{C_1}(x1) 17.55/5.36 A_{C_1}(c_{b_1}(b_{a_1}(x1))) -> A_{B_1}(b_{a_1}(a_{c_1}(c_{c_1}(c_{a_1}(x1))))) 17.55/5.36 A_{B_1}(b_{a_1}(x1)) -> A_{A_1}(x1) 17.55/5.36 C_{A_1}(a_{c_1}(x1)) -> C_{C_1}(x1) 17.55/5.36 A_{C_1}(c_{b_1}(b_{b_1}(x1))) -> A_{B_1}(b_{a_1}(a_{c_1}(c_{c_1}(c_{b_1}(x1))))) 17.55/5.36 A_{C_1}(c_{b_1}(b_{c_1}(x1))) -> A_{B_1}(b_{a_1}(a_{c_1}(c_{c_1}(c_{c_1}(x1))))) 17.55/5.36 17.55/5.36 The TRS R consists of the following rules: 17.55/5.36 17.55/5.36 a_{a_1}(a_{b_1}(x1)) -> a_{b_1}(b_{b_1}(x1)) 17.55/5.36 a_{a_1}(a_{c_1}(x1)) -> a_{b_1}(b_{c_1}(x1)) 17.55/5.36 b_{a_1}(a_{b_1}(x1)) -> b_{b_1}(x1) 17.55/5.36 b_{a_1}(a_{c_1}(x1)) -> b_{c_1}(x1) 17.55/5.36 c_{a_1}(a_{b_1}(x1)) -> c_{b_1}(x1) 17.55/5.36 c_{a_1}(a_{c_1}(x1)) -> c_{c_1}(x1) 17.55/5.36 a_{b_1}(b_{a_1}(x1)) -> a_{a_1}(x1) 17.55/5.36 a_{c_1}(c_{b_1}(b_{a_1}(x1))) -> a_{b_1}(b_{a_1}(a_{c_1}(c_{c_1}(c_{a_1}(x1))))) 17.55/5.36 a_{c_1}(c_{b_1}(b_{b_1}(x1))) -> a_{b_1}(b_{a_1}(a_{c_1}(c_{c_1}(c_{b_1}(x1))))) 17.55/5.36 a_{c_1}(c_{b_1}(b_{c_1}(x1))) -> a_{b_1}(b_{a_1}(a_{c_1}(c_{c_1}(c_{c_1}(x1))))) 17.55/5.36 b_{c_1}(c_{b_1}(b_{a_1}(x1))) -> b_{b_1}(b_{a_1}(a_{c_1}(c_{c_1}(c_{a_1}(x1))))) 17.55/5.36 b_{c_1}(c_{b_1}(b_{b_1}(x1))) -> b_{b_1}(b_{a_1}(a_{c_1}(c_{c_1}(c_{b_1}(x1))))) 17.55/5.36 b_{c_1}(c_{b_1}(b_{c_1}(x1))) -> b_{b_1}(b_{a_1}(a_{c_1}(c_{c_1}(c_{c_1}(x1))))) 17.55/5.36 c_{c_1}(c_{b_1}(b_{a_1}(x1))) -> c_{b_1}(b_{a_1}(a_{c_1}(c_{c_1}(c_{a_1}(x1))))) 17.55/5.36 c_{c_1}(c_{b_1}(b_{b_1}(x1))) -> c_{b_1}(b_{a_1}(a_{c_1}(c_{c_1}(c_{b_1}(x1))))) 17.55/5.36 c_{c_1}(c_{b_1}(b_{c_1}(x1))) -> c_{b_1}(b_{a_1}(a_{c_1}(c_{c_1}(c_{c_1}(x1))))) 17.55/5.36 17.55/5.36 Q is empty. 17.55/5.36 We have to consider all minimal (P,Q,R)-chains. 17.55/5.36 ---------------------------------------- 17.55/5.36 17.55/5.36 (13) DependencyGraphProof (EQUIVALENT) 17.55/5.36 The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 0 SCCs with 6 less nodes. 17.55/5.36 ---------------------------------------- 17.55/5.36 17.55/5.36 (14) 17.55/5.36 TRUE 17.79/5.48 EOF