33.52/9.51 YES 33.95/9.58 proof of /export/starexec/sandbox2/benchmark/theBenchmark.xml 33.95/9.58 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 33.95/9.58 33.95/9.58 33.95/9.58 Termination w.r.t. Q of the given QTRS could be proven: 33.95/9.58 33.95/9.58 (0) QTRS 33.95/9.58 (1) FlatCCProof [EQUIVALENT, 0 ms] 33.95/9.58 (2) QTRS 33.95/9.58 (3) RootLabelingProof [EQUIVALENT, 0 ms] 33.95/9.58 (4) QTRS 33.95/9.58 (5) DependencyPairsProof [EQUIVALENT, 114 ms] 33.95/9.58 (6) QDP 33.95/9.58 (7) QDPOrderProof [EQUIVALENT, 391 ms] 33.95/9.58 (8) QDP 33.95/9.58 (9) DependencyGraphProof [EQUIVALENT, 0 ms] 33.95/9.58 (10) AND 33.95/9.58 (11) QDP 33.95/9.58 (12) QDPOrderProof [EQUIVALENT, 80 ms] 33.95/9.58 (13) QDP 33.95/9.58 (14) DependencyGraphProof [EQUIVALENT, 0 ms] 33.95/9.58 (15) TRUE 33.95/9.58 (16) QDP 33.95/9.58 (17) QDPOrderProof [EQUIVALENT, 42 ms] 33.95/9.58 (18) QDP 33.95/9.58 (19) PisEmptyProof [EQUIVALENT, 0 ms] 33.95/9.58 (20) YES 33.95/9.58 33.95/9.58 33.95/9.58 ---------------------------------------- 33.95/9.58 33.95/9.58 (0) 33.95/9.58 Obligation: 33.95/9.58 Q restricted rewrite system: 33.95/9.58 The TRS R consists of the following rules: 33.95/9.58 33.95/9.58 b(b(b(x1))) -> a(x1) 33.95/9.58 a(a(x1)) -> a(b(a(x1))) 33.95/9.58 b(c(x1)) -> c(a(a(x1))) 33.95/9.58 a(c(x1)) -> c(b(b(x1))) 33.95/9.58 a(a(a(x1))) -> b(a(a(x1))) 33.95/9.58 33.95/9.58 Q is empty. 33.95/9.58 33.95/9.58 ---------------------------------------- 33.95/9.58 33.95/9.58 (1) FlatCCProof (EQUIVALENT) 33.95/9.58 We used flat context closure [ROOTLAB] 33.95/9.58 As Q is empty the flat context closure was sound AND complete. 33.95/9.58 33.95/9.58 ---------------------------------------- 33.95/9.58 33.95/9.58 (2) 33.95/9.58 Obligation: 33.95/9.58 Q restricted rewrite system: 33.95/9.58 The TRS R consists of the following rules: 33.95/9.58 33.95/9.58 a(a(x1)) -> a(b(a(x1))) 33.95/9.58 b(b(b(b(x1)))) -> b(a(x1)) 33.95/9.58 a(b(b(b(x1)))) -> a(a(x1)) 33.95/9.58 c(b(b(b(x1)))) -> c(a(x1)) 33.95/9.58 b(b(c(x1))) -> b(c(a(a(x1)))) 33.95/9.58 a(b(c(x1))) -> a(c(a(a(x1)))) 33.95/9.58 c(b(c(x1))) -> c(c(a(a(x1)))) 33.95/9.58 b(a(c(x1))) -> b(c(b(b(x1)))) 33.95/9.58 a(a(c(x1))) -> a(c(b(b(x1)))) 33.95/9.58 c(a(c(x1))) -> c(c(b(b(x1)))) 33.95/9.58 b(a(a(a(x1)))) -> b(b(a(a(x1)))) 33.95/9.58 a(a(a(a(x1)))) -> a(b(a(a(x1)))) 33.95/9.58 c(a(a(a(x1)))) -> c(b(a(a(x1)))) 33.95/9.58 33.95/9.58 Q is empty. 33.95/9.58 33.95/9.58 ---------------------------------------- 33.95/9.58 33.95/9.58 (3) RootLabelingProof (EQUIVALENT) 33.95/9.58 We used plain root labeling [ROOTLAB] with the following heuristic: 33.95/9.58 LabelAll: All function symbols get labeled 33.95/9.58 33.95/9.58 As Q is empty the root labeling was sound AND complete. 33.95/9.58 33.95/9.58 ---------------------------------------- 33.95/9.58 33.95/9.58 (4) 33.95/9.58 Obligation: 33.95/9.58 Q restricted rewrite system: 33.95/9.58 The TRS R consists of the following rules: 33.95/9.58 33.95/9.58 a_{a_1}(a_{a_1}(x1)) -> a_{b_1}(b_{a_1}(a_{a_1}(x1))) 33.95/9.58 a_{a_1}(a_{b_1}(x1)) -> a_{b_1}(b_{a_1}(a_{b_1}(x1))) 33.95/9.58 a_{a_1}(a_{c_1}(x1)) -> a_{b_1}(b_{a_1}(a_{c_1}(x1))) 33.95/9.58 b_{b_1}(b_{b_1}(b_{b_1}(b_{a_1}(x1)))) -> b_{a_1}(a_{a_1}(x1)) 33.95/9.58 b_{b_1}(b_{b_1}(b_{b_1}(b_{b_1}(x1)))) -> b_{a_1}(a_{b_1}(x1)) 33.95/9.58 b_{b_1}(b_{b_1}(b_{b_1}(b_{c_1}(x1)))) -> b_{a_1}(a_{c_1}(x1)) 33.95/9.58 a_{b_1}(b_{b_1}(b_{b_1}(b_{a_1}(x1)))) -> a_{a_1}(a_{a_1}(x1)) 33.95/9.58 a_{b_1}(b_{b_1}(b_{b_1}(b_{b_1}(x1)))) -> a_{a_1}(a_{b_1}(x1)) 33.95/9.58 a_{b_1}(b_{b_1}(b_{b_1}(b_{c_1}(x1)))) -> a_{a_1}(a_{c_1}(x1)) 33.95/9.58 c_{b_1}(b_{b_1}(b_{b_1}(b_{a_1}(x1)))) -> c_{a_1}(a_{a_1}(x1)) 33.95/9.58 c_{b_1}(b_{b_1}(b_{b_1}(b_{b_1}(x1)))) -> c_{a_1}(a_{b_1}(x1)) 33.95/9.58 c_{b_1}(b_{b_1}(b_{b_1}(b_{c_1}(x1)))) -> c_{a_1}(a_{c_1}(x1)) 33.95/9.58 b_{b_1}(b_{c_1}(c_{a_1}(x1))) -> b_{c_1}(c_{a_1}(a_{a_1}(a_{a_1}(x1)))) 33.95/9.58 b_{b_1}(b_{c_1}(c_{b_1}(x1))) -> b_{c_1}(c_{a_1}(a_{a_1}(a_{b_1}(x1)))) 33.95/9.58 b_{b_1}(b_{c_1}(c_{c_1}(x1))) -> b_{c_1}(c_{a_1}(a_{a_1}(a_{c_1}(x1)))) 33.95/9.58 a_{b_1}(b_{c_1}(c_{a_1}(x1))) -> a_{c_1}(c_{a_1}(a_{a_1}(a_{a_1}(x1)))) 33.95/9.58 a_{b_1}(b_{c_1}(c_{b_1}(x1))) -> a_{c_1}(c_{a_1}(a_{a_1}(a_{b_1}(x1)))) 33.95/9.58 a_{b_1}(b_{c_1}(c_{c_1}(x1))) -> a_{c_1}(c_{a_1}(a_{a_1}(a_{c_1}(x1)))) 33.95/9.58 c_{b_1}(b_{c_1}(c_{a_1}(x1))) -> c_{c_1}(c_{a_1}(a_{a_1}(a_{a_1}(x1)))) 33.95/9.58 c_{b_1}(b_{c_1}(c_{b_1}(x1))) -> c_{c_1}(c_{a_1}(a_{a_1}(a_{b_1}(x1)))) 33.95/9.58 c_{b_1}(b_{c_1}(c_{c_1}(x1))) -> c_{c_1}(c_{a_1}(a_{a_1}(a_{c_1}(x1)))) 33.95/9.58 b_{a_1}(a_{c_1}(c_{a_1}(x1))) -> b_{c_1}(c_{b_1}(b_{b_1}(b_{a_1}(x1)))) 33.95/9.58 b_{a_1}(a_{c_1}(c_{b_1}(x1))) -> b_{c_1}(c_{b_1}(b_{b_1}(b_{b_1}(x1)))) 33.95/9.58 b_{a_1}(a_{c_1}(c_{c_1}(x1))) -> b_{c_1}(c_{b_1}(b_{b_1}(b_{c_1}(x1)))) 33.95/9.58 a_{a_1}(a_{c_1}(c_{a_1}(x1))) -> a_{c_1}(c_{b_1}(b_{b_1}(b_{a_1}(x1)))) 33.95/9.58 a_{a_1}(a_{c_1}(c_{b_1}(x1))) -> a_{c_1}(c_{b_1}(b_{b_1}(b_{b_1}(x1)))) 33.95/9.58 a_{a_1}(a_{c_1}(c_{c_1}(x1))) -> a_{c_1}(c_{b_1}(b_{b_1}(b_{c_1}(x1)))) 33.95/9.58 c_{a_1}(a_{c_1}(c_{a_1}(x1))) -> c_{c_1}(c_{b_1}(b_{b_1}(b_{a_1}(x1)))) 33.95/9.58 c_{a_1}(a_{c_1}(c_{b_1}(x1))) -> c_{c_1}(c_{b_1}(b_{b_1}(b_{b_1}(x1)))) 33.95/9.58 c_{a_1}(a_{c_1}(c_{c_1}(x1))) -> c_{c_1}(c_{b_1}(b_{b_1}(b_{c_1}(x1)))) 33.95/9.58 b_{a_1}(a_{a_1}(a_{a_1}(a_{a_1}(x1)))) -> b_{b_1}(b_{a_1}(a_{a_1}(a_{a_1}(x1)))) 33.95/9.58 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}(x1)))) 33.95/9.58 b_{a_1}(a_{a_1}(a_{a_1}(a_{c_1}(x1)))) -> b_{b_1}(b_{a_1}(a_{a_1}(a_{c_1}(x1)))) 33.95/9.58 a_{a_1}(a_{a_1}(a_{a_1}(a_{a_1}(x1)))) -> a_{b_1}(b_{a_1}(a_{a_1}(a_{a_1}(x1)))) 33.95/9.58 a_{a_1}(a_{a_1}(a_{a_1}(a_{b_1}(x1)))) -> a_{b_1}(b_{a_1}(a_{a_1}(a_{b_1}(x1)))) 33.95/9.58 a_{a_1}(a_{a_1}(a_{a_1}(a_{c_1}(x1)))) -> a_{b_1}(b_{a_1}(a_{a_1}(a_{c_1}(x1)))) 33.95/9.58 c_{a_1}(a_{a_1}(a_{a_1}(a_{a_1}(x1)))) -> c_{b_1}(b_{a_1}(a_{a_1}(a_{a_1}(x1)))) 33.95/9.58 c_{a_1}(a_{a_1}(a_{a_1}(a_{b_1}(x1)))) -> c_{b_1}(b_{a_1}(a_{a_1}(a_{b_1}(x1)))) 33.95/9.58 c_{a_1}(a_{a_1}(a_{a_1}(a_{c_1}(x1)))) -> c_{b_1}(b_{a_1}(a_{a_1}(a_{c_1}(x1)))) 33.95/9.58 33.95/9.58 Q is empty. 33.95/9.58 33.95/9.58 ---------------------------------------- 33.95/9.58 33.95/9.58 (5) DependencyPairsProof (EQUIVALENT) 33.95/9.58 Using Dependency Pairs [AG00,LPAR04] we result in the following initial DP problem. 33.95/9.58 ---------------------------------------- 33.95/9.58 33.95/9.58 (6) 33.95/9.58 Obligation: 33.95/9.58 Q DP problem: 33.95/9.58 The TRS P consists of the following rules: 33.95/9.58 33.95/9.58 A_{A_1}(a_{a_1}(x1)) -> A_{B_1}(b_{a_1}(a_{a_1}(x1))) 33.95/9.58 A_{A_1}(a_{a_1}(x1)) -> B_{A_1}(a_{a_1}(x1)) 33.95/9.58 A_{A_1}(a_{b_1}(x1)) -> A_{B_1}(b_{a_1}(a_{b_1}(x1))) 33.95/9.58 A_{A_1}(a_{b_1}(x1)) -> B_{A_1}(a_{b_1}(x1)) 33.95/9.58 A_{A_1}(a_{c_1}(x1)) -> A_{B_1}(b_{a_1}(a_{c_1}(x1))) 33.95/9.58 A_{A_1}(a_{c_1}(x1)) -> B_{A_1}(a_{c_1}(x1)) 33.95/9.58 B_{B_1}(b_{b_1}(b_{b_1}(b_{a_1}(x1)))) -> B_{A_1}(a_{a_1}(x1)) 33.95/9.58 B_{B_1}(b_{b_1}(b_{b_1}(b_{a_1}(x1)))) -> A_{A_1}(x1) 33.95/9.58 B_{B_1}(b_{b_1}(b_{b_1}(b_{b_1}(x1)))) -> B_{A_1}(a_{b_1}(x1)) 33.95/9.58 B_{B_1}(b_{b_1}(b_{b_1}(b_{b_1}(x1)))) -> A_{B_1}(x1) 33.95/9.58 B_{B_1}(b_{b_1}(b_{b_1}(b_{c_1}(x1)))) -> B_{A_1}(a_{c_1}(x1)) 33.95/9.58 A_{B_1}(b_{b_1}(b_{b_1}(b_{a_1}(x1)))) -> A_{A_1}(a_{a_1}(x1)) 33.95/9.58 A_{B_1}(b_{b_1}(b_{b_1}(b_{a_1}(x1)))) -> A_{A_1}(x1) 33.95/9.58 A_{B_1}(b_{b_1}(b_{b_1}(b_{b_1}(x1)))) -> A_{A_1}(a_{b_1}(x1)) 33.95/9.58 A_{B_1}(b_{b_1}(b_{b_1}(b_{b_1}(x1)))) -> A_{B_1}(x1) 33.95/9.58 A_{B_1}(b_{b_1}(b_{b_1}(b_{c_1}(x1)))) -> A_{A_1}(a_{c_1}(x1)) 33.95/9.58 C_{B_1}(b_{b_1}(b_{b_1}(b_{a_1}(x1)))) -> C_{A_1}(a_{a_1}(x1)) 33.95/9.58 C_{B_1}(b_{b_1}(b_{b_1}(b_{a_1}(x1)))) -> A_{A_1}(x1) 33.95/9.58 C_{B_1}(b_{b_1}(b_{b_1}(b_{b_1}(x1)))) -> C_{A_1}(a_{b_1}(x1)) 33.95/9.58 C_{B_1}(b_{b_1}(b_{b_1}(b_{b_1}(x1)))) -> A_{B_1}(x1) 33.95/9.58 C_{B_1}(b_{b_1}(b_{b_1}(b_{c_1}(x1)))) -> C_{A_1}(a_{c_1}(x1)) 33.95/9.58 B_{B_1}(b_{c_1}(c_{a_1}(x1))) -> C_{A_1}(a_{a_1}(a_{a_1}(x1))) 33.95/9.58 B_{B_1}(b_{c_1}(c_{a_1}(x1))) -> A_{A_1}(a_{a_1}(x1)) 33.95/9.58 B_{B_1}(b_{c_1}(c_{a_1}(x1))) -> A_{A_1}(x1) 33.95/9.58 B_{B_1}(b_{c_1}(c_{b_1}(x1))) -> C_{A_1}(a_{a_1}(a_{b_1}(x1))) 33.95/9.58 B_{B_1}(b_{c_1}(c_{b_1}(x1))) -> A_{A_1}(a_{b_1}(x1)) 33.95/9.58 B_{B_1}(b_{c_1}(c_{b_1}(x1))) -> A_{B_1}(x1) 33.95/9.58 B_{B_1}(b_{c_1}(c_{c_1}(x1))) -> C_{A_1}(a_{a_1}(a_{c_1}(x1))) 33.95/9.58 B_{B_1}(b_{c_1}(c_{c_1}(x1))) -> A_{A_1}(a_{c_1}(x1)) 33.95/9.58 A_{B_1}(b_{c_1}(c_{a_1}(x1))) -> C_{A_1}(a_{a_1}(a_{a_1}(x1))) 33.95/9.58 A_{B_1}(b_{c_1}(c_{a_1}(x1))) -> A_{A_1}(a_{a_1}(x1)) 33.95/9.58 A_{B_1}(b_{c_1}(c_{a_1}(x1))) -> A_{A_1}(x1) 33.95/9.58 A_{B_1}(b_{c_1}(c_{b_1}(x1))) -> C_{A_1}(a_{a_1}(a_{b_1}(x1))) 33.95/9.58 A_{B_1}(b_{c_1}(c_{b_1}(x1))) -> A_{A_1}(a_{b_1}(x1)) 33.95/9.58 A_{B_1}(b_{c_1}(c_{b_1}(x1))) -> A_{B_1}(x1) 33.95/9.58 A_{B_1}(b_{c_1}(c_{c_1}(x1))) -> C_{A_1}(a_{a_1}(a_{c_1}(x1))) 33.95/9.58 A_{B_1}(b_{c_1}(c_{c_1}(x1))) -> A_{A_1}(a_{c_1}(x1)) 33.95/9.58 C_{B_1}(b_{c_1}(c_{a_1}(x1))) -> C_{A_1}(a_{a_1}(a_{a_1}(x1))) 33.95/9.58 C_{B_1}(b_{c_1}(c_{a_1}(x1))) -> A_{A_1}(a_{a_1}(x1)) 33.95/9.58 C_{B_1}(b_{c_1}(c_{a_1}(x1))) -> A_{A_1}(x1) 33.95/9.58 C_{B_1}(b_{c_1}(c_{b_1}(x1))) -> C_{A_1}(a_{a_1}(a_{b_1}(x1))) 33.95/9.58 C_{B_1}(b_{c_1}(c_{b_1}(x1))) -> A_{A_1}(a_{b_1}(x1)) 33.95/9.58 C_{B_1}(b_{c_1}(c_{b_1}(x1))) -> A_{B_1}(x1) 33.95/9.58 C_{B_1}(b_{c_1}(c_{c_1}(x1))) -> C_{A_1}(a_{a_1}(a_{c_1}(x1))) 33.95/9.58 C_{B_1}(b_{c_1}(c_{c_1}(x1))) -> A_{A_1}(a_{c_1}(x1)) 33.95/9.58 B_{A_1}(a_{c_1}(c_{a_1}(x1))) -> C_{B_1}(b_{b_1}(b_{a_1}(x1))) 33.95/9.58 B_{A_1}(a_{c_1}(c_{a_1}(x1))) -> B_{B_1}(b_{a_1}(x1)) 33.95/9.58 B_{A_1}(a_{c_1}(c_{a_1}(x1))) -> B_{A_1}(x1) 33.95/9.58 B_{A_1}(a_{c_1}(c_{b_1}(x1))) -> C_{B_1}(b_{b_1}(b_{b_1}(x1))) 33.95/9.58 B_{A_1}(a_{c_1}(c_{b_1}(x1))) -> B_{B_1}(b_{b_1}(x1)) 33.95/9.58 B_{A_1}(a_{c_1}(c_{b_1}(x1))) -> B_{B_1}(x1) 33.95/9.58 B_{A_1}(a_{c_1}(c_{c_1}(x1))) -> C_{B_1}(b_{b_1}(b_{c_1}(x1))) 33.95/9.58 B_{A_1}(a_{c_1}(c_{c_1}(x1))) -> B_{B_1}(b_{c_1}(x1)) 33.95/9.58 A_{A_1}(a_{c_1}(c_{a_1}(x1))) -> C_{B_1}(b_{b_1}(b_{a_1}(x1))) 33.95/9.58 A_{A_1}(a_{c_1}(c_{a_1}(x1))) -> B_{B_1}(b_{a_1}(x1)) 33.95/9.58 A_{A_1}(a_{c_1}(c_{a_1}(x1))) -> B_{A_1}(x1) 33.95/9.58 A_{A_1}(a_{c_1}(c_{b_1}(x1))) -> C_{B_1}(b_{b_1}(b_{b_1}(x1))) 33.95/9.58 A_{A_1}(a_{c_1}(c_{b_1}(x1))) -> B_{B_1}(b_{b_1}(x1)) 33.95/9.58 A_{A_1}(a_{c_1}(c_{b_1}(x1))) -> B_{B_1}(x1) 33.95/9.58 A_{A_1}(a_{c_1}(c_{c_1}(x1))) -> C_{B_1}(b_{b_1}(b_{c_1}(x1))) 33.95/9.58 A_{A_1}(a_{c_1}(c_{c_1}(x1))) -> B_{B_1}(b_{c_1}(x1)) 33.95/9.58 C_{A_1}(a_{c_1}(c_{a_1}(x1))) -> C_{B_1}(b_{b_1}(b_{a_1}(x1))) 33.95/9.58 C_{A_1}(a_{c_1}(c_{a_1}(x1))) -> B_{B_1}(b_{a_1}(x1)) 33.95/9.58 C_{A_1}(a_{c_1}(c_{a_1}(x1))) -> B_{A_1}(x1) 33.95/9.58 C_{A_1}(a_{c_1}(c_{b_1}(x1))) -> C_{B_1}(b_{b_1}(b_{b_1}(x1))) 33.95/9.58 C_{A_1}(a_{c_1}(c_{b_1}(x1))) -> B_{B_1}(b_{b_1}(x1)) 33.95/9.58 C_{A_1}(a_{c_1}(c_{b_1}(x1))) -> B_{B_1}(x1) 33.95/9.58 C_{A_1}(a_{c_1}(c_{c_1}(x1))) -> C_{B_1}(b_{b_1}(b_{c_1}(x1))) 33.95/9.58 C_{A_1}(a_{c_1}(c_{c_1}(x1))) -> B_{B_1}(b_{c_1}(x1)) 33.95/9.58 B_{A_1}(a_{a_1}(a_{a_1}(a_{a_1}(x1)))) -> B_{B_1}(b_{a_1}(a_{a_1}(a_{a_1}(x1)))) 33.95/9.58 B_{A_1}(a_{a_1}(a_{a_1}(a_{a_1}(x1)))) -> B_{A_1}(a_{a_1}(a_{a_1}(x1))) 33.95/9.58 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}(x1)))) 33.95/9.58 B_{A_1}(a_{a_1}(a_{a_1}(a_{b_1}(x1)))) -> B_{A_1}(a_{a_1}(a_{b_1}(x1))) 33.95/9.58 B_{A_1}(a_{a_1}(a_{a_1}(a_{c_1}(x1)))) -> B_{B_1}(b_{a_1}(a_{a_1}(a_{c_1}(x1)))) 33.95/9.58 B_{A_1}(a_{a_1}(a_{a_1}(a_{c_1}(x1)))) -> B_{A_1}(a_{a_1}(a_{c_1}(x1))) 33.95/9.58 A_{A_1}(a_{a_1}(a_{a_1}(a_{a_1}(x1)))) -> A_{B_1}(b_{a_1}(a_{a_1}(a_{a_1}(x1)))) 33.95/9.58 A_{A_1}(a_{a_1}(a_{a_1}(a_{a_1}(x1)))) -> B_{A_1}(a_{a_1}(a_{a_1}(x1))) 33.95/9.58 A_{A_1}(a_{a_1}(a_{a_1}(a_{b_1}(x1)))) -> A_{B_1}(b_{a_1}(a_{a_1}(a_{b_1}(x1)))) 33.95/9.58 A_{A_1}(a_{a_1}(a_{a_1}(a_{b_1}(x1)))) -> B_{A_1}(a_{a_1}(a_{b_1}(x1))) 33.95/9.58 A_{A_1}(a_{a_1}(a_{a_1}(a_{c_1}(x1)))) -> A_{B_1}(b_{a_1}(a_{a_1}(a_{c_1}(x1)))) 33.95/9.58 A_{A_1}(a_{a_1}(a_{a_1}(a_{c_1}(x1)))) -> B_{A_1}(a_{a_1}(a_{c_1}(x1))) 33.95/9.58 C_{A_1}(a_{a_1}(a_{a_1}(a_{a_1}(x1)))) -> C_{B_1}(b_{a_1}(a_{a_1}(a_{a_1}(x1)))) 33.95/9.58 C_{A_1}(a_{a_1}(a_{a_1}(a_{a_1}(x1)))) -> B_{A_1}(a_{a_1}(a_{a_1}(x1))) 33.95/9.58 C_{A_1}(a_{a_1}(a_{a_1}(a_{b_1}(x1)))) -> C_{B_1}(b_{a_1}(a_{a_1}(a_{b_1}(x1)))) 33.95/9.58 C_{A_1}(a_{a_1}(a_{a_1}(a_{b_1}(x1)))) -> B_{A_1}(a_{a_1}(a_{b_1}(x1))) 33.95/9.58 C_{A_1}(a_{a_1}(a_{a_1}(a_{c_1}(x1)))) -> C_{B_1}(b_{a_1}(a_{a_1}(a_{c_1}(x1)))) 33.95/9.58 C_{A_1}(a_{a_1}(a_{a_1}(a_{c_1}(x1)))) -> B_{A_1}(a_{a_1}(a_{c_1}(x1))) 33.95/9.58 33.95/9.58 The TRS R consists of the following rules: 33.95/9.58 33.95/9.58 a_{a_1}(a_{a_1}(x1)) -> a_{b_1}(b_{a_1}(a_{a_1}(x1))) 33.95/9.58 a_{a_1}(a_{b_1}(x1)) -> a_{b_1}(b_{a_1}(a_{b_1}(x1))) 33.95/9.58 a_{a_1}(a_{c_1}(x1)) -> a_{b_1}(b_{a_1}(a_{c_1}(x1))) 33.95/9.58 b_{b_1}(b_{b_1}(b_{b_1}(b_{a_1}(x1)))) -> b_{a_1}(a_{a_1}(x1)) 33.95/9.58 b_{b_1}(b_{b_1}(b_{b_1}(b_{b_1}(x1)))) -> b_{a_1}(a_{b_1}(x1)) 33.95/9.58 b_{b_1}(b_{b_1}(b_{b_1}(b_{c_1}(x1)))) -> b_{a_1}(a_{c_1}(x1)) 33.95/9.58 a_{b_1}(b_{b_1}(b_{b_1}(b_{a_1}(x1)))) -> a_{a_1}(a_{a_1}(x1)) 33.95/9.58 a_{b_1}(b_{b_1}(b_{b_1}(b_{b_1}(x1)))) -> a_{a_1}(a_{b_1}(x1)) 33.95/9.58 a_{b_1}(b_{b_1}(b_{b_1}(b_{c_1}(x1)))) -> a_{a_1}(a_{c_1}(x1)) 33.95/9.58 c_{b_1}(b_{b_1}(b_{b_1}(b_{a_1}(x1)))) -> c_{a_1}(a_{a_1}(x1)) 33.95/9.58 c_{b_1}(b_{b_1}(b_{b_1}(b_{b_1}(x1)))) -> c_{a_1}(a_{b_1}(x1)) 33.95/9.58 c_{b_1}(b_{b_1}(b_{b_1}(b_{c_1}(x1)))) -> c_{a_1}(a_{c_1}(x1)) 33.95/9.58 b_{b_1}(b_{c_1}(c_{a_1}(x1))) -> b_{c_1}(c_{a_1}(a_{a_1}(a_{a_1}(x1)))) 33.95/9.58 b_{b_1}(b_{c_1}(c_{b_1}(x1))) -> b_{c_1}(c_{a_1}(a_{a_1}(a_{b_1}(x1)))) 33.95/9.58 b_{b_1}(b_{c_1}(c_{c_1}(x1))) -> b_{c_1}(c_{a_1}(a_{a_1}(a_{c_1}(x1)))) 33.95/9.58 a_{b_1}(b_{c_1}(c_{a_1}(x1))) -> a_{c_1}(c_{a_1}(a_{a_1}(a_{a_1}(x1)))) 33.95/9.58 a_{b_1}(b_{c_1}(c_{b_1}(x1))) -> a_{c_1}(c_{a_1}(a_{a_1}(a_{b_1}(x1)))) 33.95/9.58 a_{b_1}(b_{c_1}(c_{c_1}(x1))) -> a_{c_1}(c_{a_1}(a_{a_1}(a_{c_1}(x1)))) 33.95/9.58 c_{b_1}(b_{c_1}(c_{a_1}(x1))) -> c_{c_1}(c_{a_1}(a_{a_1}(a_{a_1}(x1)))) 33.95/9.58 c_{b_1}(b_{c_1}(c_{b_1}(x1))) -> c_{c_1}(c_{a_1}(a_{a_1}(a_{b_1}(x1)))) 33.95/9.58 c_{b_1}(b_{c_1}(c_{c_1}(x1))) -> c_{c_1}(c_{a_1}(a_{a_1}(a_{c_1}(x1)))) 33.95/9.58 b_{a_1}(a_{c_1}(c_{a_1}(x1))) -> b_{c_1}(c_{b_1}(b_{b_1}(b_{a_1}(x1)))) 33.95/9.58 b_{a_1}(a_{c_1}(c_{b_1}(x1))) -> b_{c_1}(c_{b_1}(b_{b_1}(b_{b_1}(x1)))) 33.95/9.58 b_{a_1}(a_{c_1}(c_{c_1}(x1))) -> b_{c_1}(c_{b_1}(b_{b_1}(b_{c_1}(x1)))) 33.95/9.58 a_{a_1}(a_{c_1}(c_{a_1}(x1))) -> a_{c_1}(c_{b_1}(b_{b_1}(b_{a_1}(x1)))) 33.95/9.58 a_{a_1}(a_{c_1}(c_{b_1}(x1))) -> a_{c_1}(c_{b_1}(b_{b_1}(b_{b_1}(x1)))) 33.95/9.58 a_{a_1}(a_{c_1}(c_{c_1}(x1))) -> a_{c_1}(c_{b_1}(b_{b_1}(b_{c_1}(x1)))) 33.95/9.58 c_{a_1}(a_{c_1}(c_{a_1}(x1))) -> c_{c_1}(c_{b_1}(b_{b_1}(b_{a_1}(x1)))) 33.95/9.58 c_{a_1}(a_{c_1}(c_{b_1}(x1))) -> c_{c_1}(c_{b_1}(b_{b_1}(b_{b_1}(x1)))) 33.95/9.58 c_{a_1}(a_{c_1}(c_{c_1}(x1))) -> c_{c_1}(c_{b_1}(b_{b_1}(b_{c_1}(x1)))) 33.95/9.58 b_{a_1}(a_{a_1}(a_{a_1}(a_{a_1}(x1)))) -> b_{b_1}(b_{a_1}(a_{a_1}(a_{a_1}(x1)))) 33.95/9.58 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}(x1)))) 33.95/9.58 b_{a_1}(a_{a_1}(a_{a_1}(a_{c_1}(x1)))) -> b_{b_1}(b_{a_1}(a_{a_1}(a_{c_1}(x1)))) 33.95/9.58 a_{a_1}(a_{a_1}(a_{a_1}(a_{a_1}(x1)))) -> a_{b_1}(b_{a_1}(a_{a_1}(a_{a_1}(x1)))) 33.95/9.58 a_{a_1}(a_{a_1}(a_{a_1}(a_{b_1}(x1)))) -> a_{b_1}(b_{a_1}(a_{a_1}(a_{b_1}(x1)))) 33.95/9.58 a_{a_1}(a_{a_1}(a_{a_1}(a_{c_1}(x1)))) -> a_{b_1}(b_{a_1}(a_{a_1}(a_{c_1}(x1)))) 33.95/9.58 c_{a_1}(a_{a_1}(a_{a_1}(a_{a_1}(x1)))) -> c_{b_1}(b_{a_1}(a_{a_1}(a_{a_1}(x1)))) 33.95/9.58 c_{a_1}(a_{a_1}(a_{a_1}(a_{b_1}(x1)))) -> c_{b_1}(b_{a_1}(a_{a_1}(a_{b_1}(x1)))) 33.95/9.58 c_{a_1}(a_{a_1}(a_{a_1}(a_{c_1}(x1)))) -> c_{b_1}(b_{a_1}(a_{a_1}(a_{c_1}(x1)))) 33.95/9.58 33.95/9.58 Q is empty. 33.95/9.58 We have to consider all minimal (P,Q,R)-chains. 33.95/9.58 ---------------------------------------- 33.95/9.58 33.95/9.58 (7) QDPOrderProof (EQUIVALENT) 33.95/9.58 We use the reduction pair processor [LPAR04,JAR06]. 33.95/9.58 33.95/9.58 33.95/9.58 The following pairs can be oriented strictly and are deleted. 33.95/9.58 33.95/9.58 B_{B_1}(b_{c_1}(c_{a_1}(x1))) -> C_{A_1}(a_{a_1}(a_{a_1}(x1))) 33.95/9.58 B_{B_1}(b_{c_1}(c_{a_1}(x1))) -> A_{A_1}(a_{a_1}(x1)) 33.95/9.58 B_{B_1}(b_{c_1}(c_{a_1}(x1))) -> A_{A_1}(x1) 33.95/9.58 B_{B_1}(b_{c_1}(c_{b_1}(x1))) -> C_{A_1}(a_{a_1}(a_{b_1}(x1))) 33.95/9.58 B_{B_1}(b_{c_1}(c_{b_1}(x1))) -> A_{A_1}(a_{b_1}(x1)) 33.95/9.58 B_{B_1}(b_{c_1}(c_{b_1}(x1))) -> A_{B_1}(x1) 33.95/9.58 B_{B_1}(b_{c_1}(c_{c_1}(x1))) -> C_{A_1}(a_{a_1}(a_{c_1}(x1))) 33.95/9.58 B_{B_1}(b_{c_1}(c_{c_1}(x1))) -> A_{A_1}(a_{c_1}(x1)) 33.95/9.58 A_{B_1}(b_{c_1}(c_{a_1}(x1))) -> C_{A_1}(a_{a_1}(a_{a_1}(x1))) 33.95/9.58 A_{B_1}(b_{c_1}(c_{a_1}(x1))) -> A_{A_1}(a_{a_1}(x1)) 33.95/9.58 A_{B_1}(b_{c_1}(c_{a_1}(x1))) -> A_{A_1}(x1) 33.95/9.58 A_{B_1}(b_{c_1}(c_{b_1}(x1))) -> C_{A_1}(a_{a_1}(a_{b_1}(x1))) 33.95/9.58 A_{B_1}(b_{c_1}(c_{b_1}(x1))) -> A_{A_1}(a_{b_1}(x1)) 33.95/9.58 A_{B_1}(b_{c_1}(c_{b_1}(x1))) -> A_{B_1}(x1) 33.95/9.58 A_{B_1}(b_{c_1}(c_{c_1}(x1))) -> C_{A_1}(a_{a_1}(a_{c_1}(x1))) 33.95/9.58 A_{B_1}(b_{c_1}(c_{c_1}(x1))) -> A_{A_1}(a_{c_1}(x1)) 33.95/9.58 C_{B_1}(b_{c_1}(c_{a_1}(x1))) -> C_{A_1}(a_{a_1}(a_{a_1}(x1))) 33.95/9.58 C_{B_1}(b_{c_1}(c_{a_1}(x1))) -> A_{A_1}(a_{a_1}(x1)) 33.95/9.58 C_{B_1}(b_{c_1}(c_{a_1}(x1))) -> A_{A_1}(x1) 33.95/9.58 C_{B_1}(b_{c_1}(c_{b_1}(x1))) -> C_{A_1}(a_{a_1}(a_{b_1}(x1))) 33.95/9.58 C_{B_1}(b_{c_1}(c_{b_1}(x1))) -> A_{A_1}(a_{b_1}(x1)) 33.95/9.58 C_{B_1}(b_{c_1}(c_{b_1}(x1))) -> A_{B_1}(x1) 33.95/9.58 C_{B_1}(b_{c_1}(c_{c_1}(x1))) -> C_{A_1}(a_{a_1}(a_{c_1}(x1))) 33.95/9.58 C_{B_1}(b_{c_1}(c_{c_1}(x1))) -> A_{A_1}(a_{c_1}(x1)) 33.95/9.58 B_{A_1}(a_{c_1}(c_{a_1}(x1))) -> C_{B_1}(b_{b_1}(b_{a_1}(x1))) 33.95/9.58 B_{A_1}(a_{c_1}(c_{a_1}(x1))) -> B_{B_1}(b_{a_1}(x1)) 33.95/9.58 B_{A_1}(a_{c_1}(c_{a_1}(x1))) -> B_{A_1}(x1) 33.95/9.58 B_{A_1}(a_{c_1}(c_{b_1}(x1))) -> C_{B_1}(b_{b_1}(b_{b_1}(x1))) 33.95/9.58 B_{A_1}(a_{c_1}(c_{b_1}(x1))) -> B_{B_1}(b_{b_1}(x1)) 33.95/9.58 B_{A_1}(a_{c_1}(c_{b_1}(x1))) -> B_{B_1}(x1) 33.95/9.58 B_{A_1}(a_{c_1}(c_{c_1}(x1))) -> C_{B_1}(b_{b_1}(b_{c_1}(x1))) 33.95/9.58 B_{A_1}(a_{c_1}(c_{c_1}(x1))) -> B_{B_1}(b_{c_1}(x1)) 33.95/9.58 A_{A_1}(a_{c_1}(c_{a_1}(x1))) -> C_{B_1}(b_{b_1}(b_{a_1}(x1))) 33.95/9.58 A_{A_1}(a_{c_1}(c_{a_1}(x1))) -> B_{B_1}(b_{a_1}(x1)) 33.95/9.58 A_{A_1}(a_{c_1}(c_{a_1}(x1))) -> B_{A_1}(x1) 33.95/9.58 A_{A_1}(a_{c_1}(c_{b_1}(x1))) -> C_{B_1}(b_{b_1}(b_{b_1}(x1))) 33.95/9.58 A_{A_1}(a_{c_1}(c_{b_1}(x1))) -> B_{B_1}(b_{b_1}(x1)) 33.95/9.58 A_{A_1}(a_{c_1}(c_{b_1}(x1))) -> B_{B_1}(x1) 33.95/9.58 A_{A_1}(a_{c_1}(c_{c_1}(x1))) -> C_{B_1}(b_{b_1}(b_{c_1}(x1))) 33.95/9.58 A_{A_1}(a_{c_1}(c_{c_1}(x1))) -> B_{B_1}(b_{c_1}(x1)) 33.95/9.58 C_{A_1}(a_{c_1}(c_{a_1}(x1))) -> C_{B_1}(b_{b_1}(b_{a_1}(x1))) 33.95/9.58 C_{A_1}(a_{c_1}(c_{a_1}(x1))) -> B_{B_1}(b_{a_1}(x1)) 33.95/9.59 C_{A_1}(a_{c_1}(c_{a_1}(x1))) -> B_{A_1}(x1) 33.95/9.59 C_{A_1}(a_{c_1}(c_{b_1}(x1))) -> C_{B_1}(b_{b_1}(b_{b_1}(x1))) 33.95/9.59 C_{A_1}(a_{c_1}(c_{b_1}(x1))) -> B_{B_1}(b_{b_1}(x1)) 33.95/9.59 C_{A_1}(a_{c_1}(c_{b_1}(x1))) -> B_{B_1}(x1) 33.95/9.59 C_{A_1}(a_{c_1}(c_{c_1}(x1))) -> C_{B_1}(b_{b_1}(b_{c_1}(x1))) 33.95/9.59 C_{A_1}(a_{c_1}(c_{c_1}(x1))) -> B_{B_1}(b_{c_1}(x1)) 33.95/9.59 The remaining pairs can at least be oriented weakly. 33.95/9.59 Used ordering: Polynomial interpretation [POLO]: 33.95/9.59 33.95/9.59 POL(A_{A_1}(x_1)) = x_1 33.95/9.59 POL(A_{B_1}(x_1)) = x_1 33.95/9.59 POL(B_{A_1}(x_1)) = x_1 33.95/9.59 POL(B_{B_1}(x_1)) = x_1 33.95/9.59 POL(C_{A_1}(x_1)) = x_1 33.95/9.59 POL(C_{B_1}(x_1)) = x_1 33.95/9.59 POL(a_{a_1}(x_1)) = x_1 33.95/9.59 POL(a_{b_1}(x_1)) = x_1 33.95/9.59 POL(a_{c_1}(x_1)) = x_1 33.95/9.59 POL(b_{a_1}(x_1)) = x_1 33.95/9.59 POL(b_{b_1}(x_1)) = x_1 33.95/9.59 POL(b_{c_1}(x_1)) = x_1 33.95/9.59 POL(c_{a_1}(x_1)) = 1 + x_1 33.95/9.59 POL(c_{b_1}(x_1)) = 1 + x_1 33.95/9.59 POL(c_{c_1}(x_1)) = 1 + x_1 33.95/9.59 33.95/9.59 The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: 33.95/9.59 33.95/9.59 a_{b_1}(b_{b_1}(b_{b_1}(b_{a_1}(x1)))) -> a_{a_1}(a_{a_1}(x1)) 33.95/9.59 a_{a_1}(a_{a_1}(x1)) -> a_{b_1}(b_{a_1}(a_{a_1}(x1))) 33.95/9.59 a_{b_1}(b_{b_1}(b_{b_1}(b_{b_1}(x1)))) -> a_{a_1}(a_{b_1}(x1)) 33.95/9.59 a_{a_1}(a_{b_1}(x1)) -> a_{b_1}(b_{a_1}(a_{b_1}(x1))) 33.95/9.59 a_{b_1}(b_{b_1}(b_{b_1}(b_{c_1}(x1)))) -> a_{a_1}(a_{c_1}(x1)) 33.95/9.59 a_{a_1}(a_{c_1}(x1)) -> a_{b_1}(b_{a_1}(a_{c_1}(x1))) 33.95/9.59 a_{a_1}(a_{a_1}(a_{a_1}(a_{a_1}(x1)))) -> a_{b_1}(b_{a_1}(a_{a_1}(a_{a_1}(x1)))) 33.95/9.59 a_{a_1}(a_{a_1}(a_{a_1}(a_{b_1}(x1)))) -> a_{b_1}(b_{a_1}(a_{a_1}(a_{b_1}(x1)))) 33.95/9.59 a_{a_1}(a_{a_1}(a_{a_1}(a_{c_1}(x1)))) -> a_{b_1}(b_{a_1}(a_{a_1}(a_{c_1}(x1)))) 33.95/9.59 a_{a_1}(a_{c_1}(c_{a_1}(x1))) -> a_{c_1}(c_{b_1}(b_{b_1}(b_{a_1}(x1)))) 33.95/9.59 a_{a_1}(a_{c_1}(c_{b_1}(x1))) -> a_{c_1}(c_{b_1}(b_{b_1}(b_{b_1}(x1)))) 33.95/9.59 a_{a_1}(a_{c_1}(c_{c_1}(x1))) -> a_{c_1}(c_{b_1}(b_{b_1}(b_{c_1}(x1)))) 33.95/9.59 b_{a_1}(a_{c_1}(c_{a_1}(x1))) -> b_{c_1}(c_{b_1}(b_{b_1}(b_{a_1}(x1)))) 33.95/9.59 b_{a_1}(a_{c_1}(c_{b_1}(x1))) -> b_{c_1}(c_{b_1}(b_{b_1}(b_{b_1}(x1)))) 33.95/9.59 b_{a_1}(a_{c_1}(c_{c_1}(x1))) -> b_{c_1}(c_{b_1}(b_{b_1}(b_{c_1}(x1)))) 33.95/9.59 b_{a_1}(a_{a_1}(a_{a_1}(a_{a_1}(x1)))) -> b_{b_1}(b_{a_1}(a_{a_1}(a_{a_1}(x1)))) 33.95/9.59 b_{b_1}(b_{b_1}(b_{b_1}(b_{a_1}(x1)))) -> b_{a_1}(a_{a_1}(x1)) 33.95/9.59 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}(x1)))) 33.95/9.59 b_{b_1}(b_{b_1}(b_{b_1}(b_{b_1}(x1)))) -> b_{a_1}(a_{b_1}(x1)) 33.95/9.59 b_{a_1}(a_{a_1}(a_{a_1}(a_{c_1}(x1)))) -> b_{b_1}(b_{a_1}(a_{a_1}(a_{c_1}(x1)))) 33.95/9.59 a_{b_1}(b_{c_1}(c_{a_1}(x1))) -> a_{c_1}(c_{a_1}(a_{a_1}(a_{a_1}(x1)))) 33.95/9.59 a_{b_1}(b_{c_1}(c_{b_1}(x1))) -> a_{c_1}(c_{a_1}(a_{a_1}(a_{b_1}(x1)))) 33.95/9.59 a_{b_1}(b_{c_1}(c_{c_1}(x1))) -> a_{c_1}(c_{a_1}(a_{a_1}(a_{c_1}(x1)))) 33.95/9.59 b_{b_1}(b_{b_1}(b_{b_1}(b_{c_1}(x1)))) -> b_{a_1}(a_{c_1}(x1)) 33.95/9.59 b_{b_1}(b_{c_1}(c_{a_1}(x1))) -> b_{c_1}(c_{a_1}(a_{a_1}(a_{a_1}(x1)))) 33.95/9.59 b_{b_1}(b_{c_1}(c_{b_1}(x1))) -> b_{c_1}(c_{a_1}(a_{a_1}(a_{b_1}(x1)))) 33.95/9.59 b_{b_1}(b_{c_1}(c_{c_1}(x1))) -> b_{c_1}(c_{a_1}(a_{a_1}(a_{c_1}(x1)))) 33.95/9.59 c_{b_1}(b_{b_1}(b_{b_1}(b_{c_1}(x1)))) -> c_{a_1}(a_{c_1}(x1)) 33.95/9.59 c_{b_1}(b_{c_1}(c_{a_1}(x1))) -> c_{c_1}(c_{a_1}(a_{a_1}(a_{a_1}(x1)))) 33.95/9.59 c_{b_1}(b_{c_1}(c_{b_1}(x1))) -> c_{c_1}(c_{a_1}(a_{a_1}(a_{b_1}(x1)))) 33.95/9.59 c_{b_1}(b_{c_1}(c_{c_1}(x1))) -> c_{c_1}(c_{a_1}(a_{a_1}(a_{c_1}(x1)))) 33.95/9.59 c_{a_1}(a_{a_1}(a_{a_1}(a_{a_1}(x1)))) -> c_{b_1}(b_{a_1}(a_{a_1}(a_{a_1}(x1)))) 33.95/9.59 c_{b_1}(b_{b_1}(b_{b_1}(b_{a_1}(x1)))) -> c_{a_1}(a_{a_1}(x1)) 33.95/9.59 c_{a_1}(a_{a_1}(a_{a_1}(a_{b_1}(x1)))) -> c_{b_1}(b_{a_1}(a_{a_1}(a_{b_1}(x1)))) 33.95/9.59 c_{b_1}(b_{b_1}(b_{b_1}(b_{b_1}(x1)))) -> c_{a_1}(a_{b_1}(x1)) 33.95/9.59 c_{a_1}(a_{a_1}(a_{a_1}(a_{c_1}(x1)))) -> c_{b_1}(b_{a_1}(a_{a_1}(a_{c_1}(x1)))) 33.95/9.59 c_{a_1}(a_{c_1}(c_{a_1}(x1))) -> c_{c_1}(c_{b_1}(b_{b_1}(b_{a_1}(x1)))) 33.95/9.59 c_{a_1}(a_{c_1}(c_{b_1}(x1))) -> c_{c_1}(c_{b_1}(b_{b_1}(b_{b_1}(x1)))) 33.95/9.59 c_{a_1}(a_{c_1}(c_{c_1}(x1))) -> c_{c_1}(c_{b_1}(b_{b_1}(b_{c_1}(x1)))) 33.95/9.59 33.95/9.59 33.95/9.59 ---------------------------------------- 33.95/9.59 33.95/9.59 (8) 33.95/9.59 Obligation: 33.95/9.59 Q DP problem: 33.95/9.59 The TRS P consists of the following rules: 33.95/9.59 33.95/9.59 A_{A_1}(a_{a_1}(x1)) -> A_{B_1}(b_{a_1}(a_{a_1}(x1))) 33.95/9.59 A_{A_1}(a_{a_1}(x1)) -> B_{A_1}(a_{a_1}(x1)) 33.95/9.59 A_{A_1}(a_{b_1}(x1)) -> A_{B_1}(b_{a_1}(a_{b_1}(x1))) 33.95/9.59 A_{A_1}(a_{b_1}(x1)) -> B_{A_1}(a_{b_1}(x1)) 33.95/9.59 A_{A_1}(a_{c_1}(x1)) -> A_{B_1}(b_{a_1}(a_{c_1}(x1))) 33.95/9.59 A_{A_1}(a_{c_1}(x1)) -> B_{A_1}(a_{c_1}(x1)) 33.95/9.59 B_{B_1}(b_{b_1}(b_{b_1}(b_{a_1}(x1)))) -> B_{A_1}(a_{a_1}(x1)) 33.95/9.59 B_{B_1}(b_{b_1}(b_{b_1}(b_{a_1}(x1)))) -> A_{A_1}(x1) 33.95/9.59 B_{B_1}(b_{b_1}(b_{b_1}(b_{b_1}(x1)))) -> B_{A_1}(a_{b_1}(x1)) 33.95/9.59 B_{B_1}(b_{b_1}(b_{b_1}(b_{b_1}(x1)))) -> A_{B_1}(x1) 33.95/9.59 B_{B_1}(b_{b_1}(b_{b_1}(b_{c_1}(x1)))) -> B_{A_1}(a_{c_1}(x1)) 33.95/9.59 A_{B_1}(b_{b_1}(b_{b_1}(b_{a_1}(x1)))) -> A_{A_1}(a_{a_1}(x1)) 33.95/9.59 A_{B_1}(b_{b_1}(b_{b_1}(b_{a_1}(x1)))) -> A_{A_1}(x1) 33.95/9.59 A_{B_1}(b_{b_1}(b_{b_1}(b_{b_1}(x1)))) -> A_{A_1}(a_{b_1}(x1)) 33.95/9.59 A_{B_1}(b_{b_1}(b_{b_1}(b_{b_1}(x1)))) -> A_{B_1}(x1) 33.95/9.59 A_{B_1}(b_{b_1}(b_{b_1}(b_{c_1}(x1)))) -> A_{A_1}(a_{c_1}(x1)) 33.95/9.59 C_{B_1}(b_{b_1}(b_{b_1}(b_{a_1}(x1)))) -> C_{A_1}(a_{a_1}(x1)) 33.95/9.59 C_{B_1}(b_{b_1}(b_{b_1}(b_{a_1}(x1)))) -> A_{A_1}(x1) 33.95/9.59 C_{B_1}(b_{b_1}(b_{b_1}(b_{b_1}(x1)))) -> C_{A_1}(a_{b_1}(x1)) 33.95/9.59 C_{B_1}(b_{b_1}(b_{b_1}(b_{b_1}(x1)))) -> A_{B_1}(x1) 33.95/9.59 C_{B_1}(b_{b_1}(b_{b_1}(b_{c_1}(x1)))) -> C_{A_1}(a_{c_1}(x1)) 33.95/9.59 B_{A_1}(a_{a_1}(a_{a_1}(a_{a_1}(x1)))) -> B_{B_1}(b_{a_1}(a_{a_1}(a_{a_1}(x1)))) 33.95/9.59 B_{A_1}(a_{a_1}(a_{a_1}(a_{a_1}(x1)))) -> B_{A_1}(a_{a_1}(a_{a_1}(x1))) 33.95/9.59 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}(x1)))) 33.95/9.59 B_{A_1}(a_{a_1}(a_{a_1}(a_{b_1}(x1)))) -> B_{A_1}(a_{a_1}(a_{b_1}(x1))) 33.95/9.59 B_{A_1}(a_{a_1}(a_{a_1}(a_{c_1}(x1)))) -> B_{B_1}(b_{a_1}(a_{a_1}(a_{c_1}(x1)))) 33.95/9.59 B_{A_1}(a_{a_1}(a_{a_1}(a_{c_1}(x1)))) -> B_{A_1}(a_{a_1}(a_{c_1}(x1))) 33.95/9.59 A_{A_1}(a_{a_1}(a_{a_1}(a_{a_1}(x1)))) -> A_{B_1}(b_{a_1}(a_{a_1}(a_{a_1}(x1)))) 33.95/9.59 A_{A_1}(a_{a_1}(a_{a_1}(a_{a_1}(x1)))) -> B_{A_1}(a_{a_1}(a_{a_1}(x1))) 33.95/9.59 A_{A_1}(a_{a_1}(a_{a_1}(a_{b_1}(x1)))) -> A_{B_1}(b_{a_1}(a_{a_1}(a_{b_1}(x1)))) 33.95/9.59 A_{A_1}(a_{a_1}(a_{a_1}(a_{b_1}(x1)))) -> B_{A_1}(a_{a_1}(a_{b_1}(x1))) 33.95/9.59 A_{A_1}(a_{a_1}(a_{a_1}(a_{c_1}(x1)))) -> A_{B_1}(b_{a_1}(a_{a_1}(a_{c_1}(x1)))) 33.95/9.59 A_{A_1}(a_{a_1}(a_{a_1}(a_{c_1}(x1)))) -> B_{A_1}(a_{a_1}(a_{c_1}(x1))) 33.95/9.59 C_{A_1}(a_{a_1}(a_{a_1}(a_{a_1}(x1)))) -> C_{B_1}(b_{a_1}(a_{a_1}(a_{a_1}(x1)))) 33.95/9.59 C_{A_1}(a_{a_1}(a_{a_1}(a_{a_1}(x1)))) -> B_{A_1}(a_{a_1}(a_{a_1}(x1))) 33.95/9.59 C_{A_1}(a_{a_1}(a_{a_1}(a_{b_1}(x1)))) -> C_{B_1}(b_{a_1}(a_{a_1}(a_{b_1}(x1)))) 33.95/9.59 C_{A_1}(a_{a_1}(a_{a_1}(a_{b_1}(x1)))) -> B_{A_1}(a_{a_1}(a_{b_1}(x1))) 33.95/9.59 C_{A_1}(a_{a_1}(a_{a_1}(a_{c_1}(x1)))) -> C_{B_1}(b_{a_1}(a_{a_1}(a_{c_1}(x1)))) 33.95/9.59 C_{A_1}(a_{a_1}(a_{a_1}(a_{c_1}(x1)))) -> B_{A_1}(a_{a_1}(a_{c_1}(x1))) 33.95/9.59 33.95/9.59 The TRS R consists of the following rules: 33.95/9.59 33.95/9.59 a_{a_1}(a_{a_1}(x1)) -> a_{b_1}(b_{a_1}(a_{a_1}(x1))) 33.95/9.59 a_{a_1}(a_{b_1}(x1)) -> a_{b_1}(b_{a_1}(a_{b_1}(x1))) 33.95/9.59 a_{a_1}(a_{c_1}(x1)) -> a_{b_1}(b_{a_1}(a_{c_1}(x1))) 33.95/9.59 b_{b_1}(b_{b_1}(b_{b_1}(b_{a_1}(x1)))) -> b_{a_1}(a_{a_1}(x1)) 33.95/9.59 b_{b_1}(b_{b_1}(b_{b_1}(b_{b_1}(x1)))) -> b_{a_1}(a_{b_1}(x1)) 33.95/9.59 b_{b_1}(b_{b_1}(b_{b_1}(b_{c_1}(x1)))) -> b_{a_1}(a_{c_1}(x1)) 33.95/9.59 a_{b_1}(b_{b_1}(b_{b_1}(b_{a_1}(x1)))) -> a_{a_1}(a_{a_1}(x1)) 33.95/9.59 a_{b_1}(b_{b_1}(b_{b_1}(b_{b_1}(x1)))) -> a_{a_1}(a_{b_1}(x1)) 33.95/9.59 a_{b_1}(b_{b_1}(b_{b_1}(b_{c_1}(x1)))) -> a_{a_1}(a_{c_1}(x1)) 33.95/9.59 c_{b_1}(b_{b_1}(b_{b_1}(b_{a_1}(x1)))) -> c_{a_1}(a_{a_1}(x1)) 33.95/9.59 c_{b_1}(b_{b_1}(b_{b_1}(b_{b_1}(x1)))) -> c_{a_1}(a_{b_1}(x1)) 33.95/9.59 c_{b_1}(b_{b_1}(b_{b_1}(b_{c_1}(x1)))) -> c_{a_1}(a_{c_1}(x1)) 33.95/9.59 b_{b_1}(b_{c_1}(c_{a_1}(x1))) -> b_{c_1}(c_{a_1}(a_{a_1}(a_{a_1}(x1)))) 33.95/9.59 b_{b_1}(b_{c_1}(c_{b_1}(x1))) -> b_{c_1}(c_{a_1}(a_{a_1}(a_{b_1}(x1)))) 33.95/9.59 b_{b_1}(b_{c_1}(c_{c_1}(x1))) -> b_{c_1}(c_{a_1}(a_{a_1}(a_{c_1}(x1)))) 33.95/9.59 a_{b_1}(b_{c_1}(c_{a_1}(x1))) -> a_{c_1}(c_{a_1}(a_{a_1}(a_{a_1}(x1)))) 33.95/9.59 a_{b_1}(b_{c_1}(c_{b_1}(x1))) -> a_{c_1}(c_{a_1}(a_{a_1}(a_{b_1}(x1)))) 33.95/9.59 a_{b_1}(b_{c_1}(c_{c_1}(x1))) -> a_{c_1}(c_{a_1}(a_{a_1}(a_{c_1}(x1)))) 33.95/9.59 c_{b_1}(b_{c_1}(c_{a_1}(x1))) -> c_{c_1}(c_{a_1}(a_{a_1}(a_{a_1}(x1)))) 33.95/9.59 c_{b_1}(b_{c_1}(c_{b_1}(x1))) -> c_{c_1}(c_{a_1}(a_{a_1}(a_{b_1}(x1)))) 33.95/9.59 c_{b_1}(b_{c_1}(c_{c_1}(x1))) -> c_{c_1}(c_{a_1}(a_{a_1}(a_{c_1}(x1)))) 33.95/9.59 b_{a_1}(a_{c_1}(c_{a_1}(x1))) -> b_{c_1}(c_{b_1}(b_{b_1}(b_{a_1}(x1)))) 33.95/9.59 b_{a_1}(a_{c_1}(c_{b_1}(x1))) -> b_{c_1}(c_{b_1}(b_{b_1}(b_{b_1}(x1)))) 33.95/9.59 b_{a_1}(a_{c_1}(c_{c_1}(x1))) -> b_{c_1}(c_{b_1}(b_{b_1}(b_{c_1}(x1)))) 33.95/9.59 a_{a_1}(a_{c_1}(c_{a_1}(x1))) -> a_{c_1}(c_{b_1}(b_{b_1}(b_{a_1}(x1)))) 33.95/9.59 a_{a_1}(a_{c_1}(c_{b_1}(x1))) -> a_{c_1}(c_{b_1}(b_{b_1}(b_{b_1}(x1)))) 33.95/9.59 a_{a_1}(a_{c_1}(c_{c_1}(x1))) -> a_{c_1}(c_{b_1}(b_{b_1}(b_{c_1}(x1)))) 33.95/9.59 c_{a_1}(a_{c_1}(c_{a_1}(x1))) -> c_{c_1}(c_{b_1}(b_{b_1}(b_{a_1}(x1)))) 33.95/9.59 c_{a_1}(a_{c_1}(c_{b_1}(x1))) -> c_{c_1}(c_{b_1}(b_{b_1}(b_{b_1}(x1)))) 33.95/9.59 c_{a_1}(a_{c_1}(c_{c_1}(x1))) -> c_{c_1}(c_{b_1}(b_{b_1}(b_{c_1}(x1)))) 33.95/9.59 b_{a_1}(a_{a_1}(a_{a_1}(a_{a_1}(x1)))) -> b_{b_1}(b_{a_1}(a_{a_1}(a_{a_1}(x1)))) 33.95/9.59 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}(x1)))) 33.95/9.59 b_{a_1}(a_{a_1}(a_{a_1}(a_{c_1}(x1)))) -> b_{b_1}(b_{a_1}(a_{a_1}(a_{c_1}(x1)))) 33.95/9.59 a_{a_1}(a_{a_1}(a_{a_1}(a_{a_1}(x1)))) -> a_{b_1}(b_{a_1}(a_{a_1}(a_{a_1}(x1)))) 33.95/9.59 a_{a_1}(a_{a_1}(a_{a_1}(a_{b_1}(x1)))) -> a_{b_1}(b_{a_1}(a_{a_1}(a_{b_1}(x1)))) 33.95/9.59 a_{a_1}(a_{a_1}(a_{a_1}(a_{c_1}(x1)))) -> a_{b_1}(b_{a_1}(a_{a_1}(a_{c_1}(x1)))) 33.95/9.59 c_{a_1}(a_{a_1}(a_{a_1}(a_{a_1}(x1)))) -> c_{b_1}(b_{a_1}(a_{a_1}(a_{a_1}(x1)))) 33.95/9.59 c_{a_1}(a_{a_1}(a_{a_1}(a_{b_1}(x1)))) -> c_{b_1}(b_{a_1}(a_{a_1}(a_{b_1}(x1)))) 33.95/9.59 c_{a_1}(a_{a_1}(a_{a_1}(a_{c_1}(x1)))) -> c_{b_1}(b_{a_1}(a_{a_1}(a_{c_1}(x1)))) 33.95/9.59 33.95/9.59 Q is empty. 33.95/9.59 We have to consider all minimal (P,Q,R)-chains. 33.95/9.59 ---------------------------------------- 33.95/9.59 33.95/9.59 (9) DependencyGraphProof (EQUIVALENT) 33.95/9.59 The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 2 SCCs with 8 less nodes. 33.95/9.59 ---------------------------------------- 33.95/9.59 33.95/9.59 (10) 33.95/9.59 Complex Obligation (AND) 33.95/9.59 33.95/9.59 ---------------------------------------- 33.95/9.59 33.95/9.59 (11) 33.95/9.59 Obligation: 33.95/9.59 Q DP problem: 33.95/9.59 The TRS P consists of the following rules: 33.95/9.59 33.95/9.59 A_{B_1}(b_{b_1}(b_{b_1}(b_{a_1}(x1)))) -> A_{A_1}(a_{a_1}(x1)) 33.95/9.59 A_{A_1}(a_{a_1}(x1)) -> A_{B_1}(b_{a_1}(a_{a_1}(x1))) 33.95/9.59 A_{B_1}(b_{b_1}(b_{b_1}(b_{a_1}(x1)))) -> A_{A_1}(x1) 33.95/9.59 A_{A_1}(a_{a_1}(x1)) -> B_{A_1}(a_{a_1}(x1)) 33.95/9.60 B_{A_1}(a_{a_1}(a_{a_1}(a_{a_1}(x1)))) -> B_{B_1}(b_{a_1}(a_{a_1}(a_{a_1}(x1)))) 33.95/9.60 B_{B_1}(b_{b_1}(b_{b_1}(b_{a_1}(x1)))) -> B_{A_1}(a_{a_1}(x1)) 33.95/9.60 B_{A_1}(a_{a_1}(a_{a_1}(a_{a_1}(x1)))) -> B_{A_1}(a_{a_1}(a_{a_1}(x1))) 33.95/9.60 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}(x1)))) 33.95/9.60 B_{B_1}(b_{b_1}(b_{b_1}(b_{a_1}(x1)))) -> A_{A_1}(x1) 33.95/9.60 A_{A_1}(a_{b_1}(x1)) -> A_{B_1}(b_{a_1}(a_{b_1}(x1))) 33.95/9.60 A_{B_1}(b_{b_1}(b_{b_1}(b_{b_1}(x1)))) -> A_{A_1}(a_{b_1}(x1)) 33.95/9.60 A_{A_1}(a_{b_1}(x1)) -> B_{A_1}(a_{b_1}(x1)) 33.95/9.60 B_{A_1}(a_{a_1}(a_{a_1}(a_{b_1}(x1)))) -> B_{A_1}(a_{a_1}(a_{b_1}(x1))) 33.95/9.60 B_{A_1}(a_{a_1}(a_{a_1}(a_{c_1}(x1)))) -> B_{B_1}(b_{a_1}(a_{a_1}(a_{c_1}(x1)))) 33.95/9.60 B_{B_1}(b_{b_1}(b_{b_1}(b_{b_1}(x1)))) -> B_{A_1}(a_{b_1}(x1)) 33.95/9.60 B_{A_1}(a_{a_1}(a_{a_1}(a_{c_1}(x1)))) -> B_{A_1}(a_{a_1}(a_{c_1}(x1))) 33.95/9.60 B_{B_1}(b_{b_1}(b_{b_1}(b_{b_1}(x1)))) -> A_{B_1}(x1) 33.95/9.60 A_{B_1}(b_{b_1}(b_{b_1}(b_{b_1}(x1)))) -> A_{B_1}(x1) 33.95/9.60 A_{B_1}(b_{b_1}(b_{b_1}(b_{c_1}(x1)))) -> A_{A_1}(a_{c_1}(x1)) 33.95/9.60 A_{A_1}(a_{c_1}(x1)) -> A_{B_1}(b_{a_1}(a_{c_1}(x1))) 33.95/9.60 A_{A_1}(a_{a_1}(a_{a_1}(a_{a_1}(x1)))) -> A_{B_1}(b_{a_1}(a_{a_1}(a_{a_1}(x1)))) 33.95/9.60 A_{A_1}(a_{a_1}(a_{a_1}(a_{a_1}(x1)))) -> B_{A_1}(a_{a_1}(a_{a_1}(x1))) 33.95/9.60 A_{A_1}(a_{a_1}(a_{a_1}(a_{b_1}(x1)))) -> A_{B_1}(b_{a_1}(a_{a_1}(a_{b_1}(x1)))) 33.95/9.60 A_{A_1}(a_{a_1}(a_{a_1}(a_{b_1}(x1)))) -> B_{A_1}(a_{a_1}(a_{b_1}(x1))) 33.95/9.60 A_{A_1}(a_{a_1}(a_{a_1}(a_{c_1}(x1)))) -> A_{B_1}(b_{a_1}(a_{a_1}(a_{c_1}(x1)))) 33.95/9.60 A_{A_1}(a_{a_1}(a_{a_1}(a_{c_1}(x1)))) -> B_{A_1}(a_{a_1}(a_{c_1}(x1))) 33.95/9.60 33.95/9.60 The TRS R consists of the following rules: 33.95/9.60 33.95/9.60 a_{a_1}(a_{a_1}(x1)) -> a_{b_1}(b_{a_1}(a_{a_1}(x1))) 33.95/9.60 a_{a_1}(a_{b_1}(x1)) -> a_{b_1}(b_{a_1}(a_{b_1}(x1))) 33.95/9.60 a_{a_1}(a_{c_1}(x1)) -> a_{b_1}(b_{a_1}(a_{c_1}(x1))) 33.95/9.60 b_{b_1}(b_{b_1}(b_{b_1}(b_{a_1}(x1)))) -> b_{a_1}(a_{a_1}(x1)) 33.95/9.60 b_{b_1}(b_{b_1}(b_{b_1}(b_{b_1}(x1)))) -> b_{a_1}(a_{b_1}(x1)) 33.95/9.60 b_{b_1}(b_{b_1}(b_{b_1}(b_{c_1}(x1)))) -> b_{a_1}(a_{c_1}(x1)) 33.95/9.60 a_{b_1}(b_{b_1}(b_{b_1}(b_{a_1}(x1)))) -> a_{a_1}(a_{a_1}(x1)) 33.95/9.60 a_{b_1}(b_{b_1}(b_{b_1}(b_{b_1}(x1)))) -> a_{a_1}(a_{b_1}(x1)) 33.95/9.60 a_{b_1}(b_{b_1}(b_{b_1}(b_{c_1}(x1)))) -> a_{a_1}(a_{c_1}(x1)) 33.95/9.60 c_{b_1}(b_{b_1}(b_{b_1}(b_{a_1}(x1)))) -> c_{a_1}(a_{a_1}(x1)) 33.95/9.60 c_{b_1}(b_{b_1}(b_{b_1}(b_{b_1}(x1)))) -> c_{a_1}(a_{b_1}(x1)) 33.95/9.60 c_{b_1}(b_{b_1}(b_{b_1}(b_{c_1}(x1)))) -> c_{a_1}(a_{c_1}(x1)) 33.95/9.60 b_{b_1}(b_{c_1}(c_{a_1}(x1))) -> b_{c_1}(c_{a_1}(a_{a_1}(a_{a_1}(x1)))) 33.95/9.60 b_{b_1}(b_{c_1}(c_{b_1}(x1))) -> b_{c_1}(c_{a_1}(a_{a_1}(a_{b_1}(x1)))) 33.95/9.60 b_{b_1}(b_{c_1}(c_{c_1}(x1))) -> b_{c_1}(c_{a_1}(a_{a_1}(a_{c_1}(x1)))) 33.95/9.60 a_{b_1}(b_{c_1}(c_{a_1}(x1))) -> a_{c_1}(c_{a_1}(a_{a_1}(a_{a_1}(x1)))) 33.95/9.60 a_{b_1}(b_{c_1}(c_{b_1}(x1))) -> a_{c_1}(c_{a_1}(a_{a_1}(a_{b_1}(x1)))) 33.95/9.60 a_{b_1}(b_{c_1}(c_{c_1}(x1))) -> a_{c_1}(c_{a_1}(a_{a_1}(a_{c_1}(x1)))) 33.95/9.60 c_{b_1}(b_{c_1}(c_{a_1}(x1))) -> c_{c_1}(c_{a_1}(a_{a_1}(a_{a_1}(x1)))) 33.95/9.60 c_{b_1}(b_{c_1}(c_{b_1}(x1))) -> c_{c_1}(c_{a_1}(a_{a_1}(a_{b_1}(x1)))) 33.95/9.60 c_{b_1}(b_{c_1}(c_{c_1}(x1))) -> c_{c_1}(c_{a_1}(a_{a_1}(a_{c_1}(x1)))) 33.95/9.60 b_{a_1}(a_{c_1}(c_{a_1}(x1))) -> b_{c_1}(c_{b_1}(b_{b_1}(b_{a_1}(x1)))) 33.95/9.60 b_{a_1}(a_{c_1}(c_{b_1}(x1))) -> b_{c_1}(c_{b_1}(b_{b_1}(b_{b_1}(x1)))) 33.95/9.60 b_{a_1}(a_{c_1}(c_{c_1}(x1))) -> b_{c_1}(c_{b_1}(b_{b_1}(b_{c_1}(x1)))) 33.95/9.60 a_{a_1}(a_{c_1}(c_{a_1}(x1))) -> a_{c_1}(c_{b_1}(b_{b_1}(b_{a_1}(x1)))) 33.95/9.60 a_{a_1}(a_{c_1}(c_{b_1}(x1))) -> a_{c_1}(c_{b_1}(b_{b_1}(b_{b_1}(x1)))) 33.95/9.60 a_{a_1}(a_{c_1}(c_{c_1}(x1))) -> a_{c_1}(c_{b_1}(b_{b_1}(b_{c_1}(x1)))) 33.95/9.60 c_{a_1}(a_{c_1}(c_{a_1}(x1))) -> c_{c_1}(c_{b_1}(b_{b_1}(b_{a_1}(x1)))) 33.95/9.60 c_{a_1}(a_{c_1}(c_{b_1}(x1))) -> c_{c_1}(c_{b_1}(b_{b_1}(b_{b_1}(x1)))) 33.95/9.60 c_{a_1}(a_{c_1}(c_{c_1}(x1))) -> c_{c_1}(c_{b_1}(b_{b_1}(b_{c_1}(x1)))) 33.95/9.60 b_{a_1}(a_{a_1}(a_{a_1}(a_{a_1}(x1)))) -> b_{b_1}(b_{a_1}(a_{a_1}(a_{a_1}(x1)))) 33.95/9.60 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}(x1)))) 33.95/9.60 b_{a_1}(a_{a_1}(a_{a_1}(a_{c_1}(x1)))) -> b_{b_1}(b_{a_1}(a_{a_1}(a_{c_1}(x1)))) 33.95/9.60 a_{a_1}(a_{a_1}(a_{a_1}(a_{a_1}(x1)))) -> a_{b_1}(b_{a_1}(a_{a_1}(a_{a_1}(x1)))) 33.95/9.60 a_{a_1}(a_{a_1}(a_{a_1}(a_{b_1}(x1)))) -> a_{b_1}(b_{a_1}(a_{a_1}(a_{b_1}(x1)))) 33.95/9.60 a_{a_1}(a_{a_1}(a_{a_1}(a_{c_1}(x1)))) -> a_{b_1}(b_{a_1}(a_{a_1}(a_{c_1}(x1)))) 33.95/9.60 c_{a_1}(a_{a_1}(a_{a_1}(a_{a_1}(x1)))) -> c_{b_1}(b_{a_1}(a_{a_1}(a_{a_1}(x1)))) 33.95/9.60 c_{a_1}(a_{a_1}(a_{a_1}(a_{b_1}(x1)))) -> c_{b_1}(b_{a_1}(a_{a_1}(a_{b_1}(x1)))) 33.95/9.60 c_{a_1}(a_{a_1}(a_{a_1}(a_{c_1}(x1)))) -> c_{b_1}(b_{a_1}(a_{a_1}(a_{c_1}(x1)))) 33.95/9.60 33.95/9.60 Q is empty. 33.95/9.60 We have to consider all minimal (P,Q,R)-chains. 33.95/9.60 ---------------------------------------- 33.95/9.60 33.95/9.60 (12) QDPOrderProof (EQUIVALENT) 33.95/9.60 We use the reduction pair processor [LPAR04,JAR06]. 33.95/9.60 33.95/9.60 33.95/9.60 The following pairs can be oriented strictly and are deleted. 33.95/9.60 33.95/9.60 A_{B_1}(b_{b_1}(b_{b_1}(b_{a_1}(x1)))) -> A_{A_1}(a_{a_1}(x1)) 33.95/9.60 A_{B_1}(b_{b_1}(b_{b_1}(b_{a_1}(x1)))) -> A_{A_1}(x1) 33.95/9.60 B_{B_1}(b_{b_1}(b_{b_1}(b_{a_1}(x1)))) -> B_{A_1}(a_{a_1}(x1)) 33.95/9.60 B_{A_1}(a_{a_1}(a_{a_1}(a_{a_1}(x1)))) -> B_{A_1}(a_{a_1}(a_{a_1}(x1))) 33.95/9.60 B_{B_1}(b_{b_1}(b_{b_1}(b_{a_1}(x1)))) -> A_{A_1}(x1) 33.95/9.60 A_{B_1}(b_{b_1}(b_{b_1}(b_{b_1}(x1)))) -> A_{A_1}(a_{b_1}(x1)) 33.95/9.60 B_{A_1}(a_{a_1}(a_{a_1}(a_{b_1}(x1)))) -> B_{A_1}(a_{a_1}(a_{b_1}(x1))) 33.95/9.60 B_{B_1}(b_{b_1}(b_{b_1}(b_{b_1}(x1)))) -> B_{A_1}(a_{b_1}(x1)) 33.95/9.60 B_{A_1}(a_{a_1}(a_{a_1}(a_{c_1}(x1)))) -> B_{A_1}(a_{a_1}(a_{c_1}(x1))) 33.95/9.60 B_{B_1}(b_{b_1}(b_{b_1}(b_{b_1}(x1)))) -> A_{B_1}(x1) 33.95/9.60 A_{B_1}(b_{b_1}(b_{b_1}(b_{b_1}(x1)))) -> A_{B_1}(x1) 33.95/9.60 A_{B_1}(b_{b_1}(b_{b_1}(b_{c_1}(x1)))) -> A_{A_1}(a_{c_1}(x1)) 33.95/9.60 A_{A_1}(a_{a_1}(a_{a_1}(a_{a_1}(x1)))) -> A_{B_1}(b_{a_1}(a_{a_1}(a_{a_1}(x1)))) 33.95/9.60 A_{A_1}(a_{a_1}(a_{a_1}(a_{a_1}(x1)))) -> B_{A_1}(a_{a_1}(a_{a_1}(x1))) 33.95/9.60 A_{A_1}(a_{a_1}(a_{a_1}(a_{b_1}(x1)))) -> A_{B_1}(b_{a_1}(a_{a_1}(a_{b_1}(x1)))) 33.95/9.60 A_{A_1}(a_{a_1}(a_{a_1}(a_{b_1}(x1)))) -> B_{A_1}(a_{a_1}(a_{b_1}(x1))) 33.95/9.60 A_{A_1}(a_{a_1}(a_{a_1}(a_{c_1}(x1)))) -> A_{B_1}(b_{a_1}(a_{a_1}(a_{c_1}(x1)))) 33.95/9.60 A_{A_1}(a_{a_1}(a_{a_1}(a_{c_1}(x1)))) -> B_{A_1}(a_{a_1}(a_{c_1}(x1))) 33.95/9.60 The remaining pairs can at least be oriented weakly. 33.95/9.60 Used ordering: Polynomial interpretation [POLO]: 33.95/9.60 33.95/9.60 POL(A_{A_1}(x_1)) = x_1 33.95/9.60 POL(A_{B_1}(x_1)) = x_1 33.95/9.61 POL(B_{A_1}(x_1)) = x_1 33.95/9.61 POL(B_{B_1}(x_1)) = 1 + x_1 33.95/9.61 POL(a_{a_1}(x_1)) = 1 + x_1 33.95/9.61 POL(a_{b_1}(x_1)) = 1 + x_1 33.95/9.61 POL(a_{c_1}(x_1)) = 0 33.95/9.61 POL(b_{a_1}(x_1)) = x_1 33.95/9.61 POL(b_{b_1}(x_1)) = 1 + x_1 33.95/9.61 POL(b_{c_1}(x_1)) = 0 33.95/9.61 POL(c_{a_1}(x_1)) = 1 + x_1 33.95/9.61 POL(c_{b_1}(x_1)) = x_1 33.95/9.61 POL(c_{c_1}(x_1)) = 0 33.95/9.61 33.95/9.61 The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: 33.95/9.61 33.95/9.61 a_{b_1}(b_{b_1}(b_{b_1}(b_{a_1}(x1)))) -> a_{a_1}(a_{a_1}(x1)) 33.95/9.61 a_{a_1}(a_{a_1}(x1)) -> a_{b_1}(b_{a_1}(a_{a_1}(x1))) 33.95/9.61 a_{b_1}(b_{b_1}(b_{b_1}(b_{b_1}(x1)))) -> a_{a_1}(a_{b_1}(x1)) 33.95/9.61 a_{a_1}(a_{b_1}(x1)) -> a_{b_1}(b_{a_1}(a_{b_1}(x1))) 33.95/9.61 a_{b_1}(b_{b_1}(b_{b_1}(b_{c_1}(x1)))) -> a_{a_1}(a_{c_1}(x1)) 33.95/9.61 a_{a_1}(a_{c_1}(x1)) -> a_{b_1}(b_{a_1}(a_{c_1}(x1))) 33.95/9.61 a_{a_1}(a_{a_1}(a_{a_1}(a_{a_1}(x1)))) -> a_{b_1}(b_{a_1}(a_{a_1}(a_{a_1}(x1)))) 33.95/9.61 a_{a_1}(a_{a_1}(a_{a_1}(a_{b_1}(x1)))) -> a_{b_1}(b_{a_1}(a_{a_1}(a_{b_1}(x1)))) 33.95/9.61 a_{a_1}(a_{a_1}(a_{a_1}(a_{c_1}(x1)))) -> a_{b_1}(b_{a_1}(a_{a_1}(a_{c_1}(x1)))) 33.95/9.61 a_{a_1}(a_{c_1}(c_{a_1}(x1))) -> a_{c_1}(c_{b_1}(b_{b_1}(b_{a_1}(x1)))) 33.95/9.61 a_{a_1}(a_{c_1}(c_{b_1}(x1))) -> a_{c_1}(c_{b_1}(b_{b_1}(b_{b_1}(x1)))) 33.95/9.61 a_{a_1}(a_{c_1}(c_{c_1}(x1))) -> a_{c_1}(c_{b_1}(b_{b_1}(b_{c_1}(x1)))) 33.95/9.61 b_{a_1}(a_{c_1}(c_{a_1}(x1))) -> b_{c_1}(c_{b_1}(b_{b_1}(b_{a_1}(x1)))) 33.95/9.61 b_{a_1}(a_{c_1}(c_{b_1}(x1))) -> b_{c_1}(c_{b_1}(b_{b_1}(b_{b_1}(x1)))) 33.95/9.61 b_{a_1}(a_{c_1}(c_{c_1}(x1))) -> b_{c_1}(c_{b_1}(b_{b_1}(b_{c_1}(x1)))) 33.95/9.61 b_{a_1}(a_{a_1}(a_{a_1}(a_{a_1}(x1)))) -> b_{b_1}(b_{a_1}(a_{a_1}(a_{a_1}(x1)))) 33.95/9.61 b_{b_1}(b_{b_1}(b_{b_1}(b_{a_1}(x1)))) -> b_{a_1}(a_{a_1}(x1)) 33.95/9.61 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}(x1)))) 33.95/9.61 b_{b_1}(b_{b_1}(b_{b_1}(b_{b_1}(x1)))) -> b_{a_1}(a_{b_1}(x1)) 33.95/9.61 b_{a_1}(a_{a_1}(a_{a_1}(a_{c_1}(x1)))) -> b_{b_1}(b_{a_1}(a_{a_1}(a_{c_1}(x1)))) 33.95/9.61 a_{b_1}(b_{c_1}(c_{a_1}(x1))) -> a_{c_1}(c_{a_1}(a_{a_1}(a_{a_1}(x1)))) 33.95/9.61 a_{b_1}(b_{c_1}(c_{b_1}(x1))) -> a_{c_1}(c_{a_1}(a_{a_1}(a_{b_1}(x1)))) 33.95/9.61 a_{b_1}(b_{c_1}(c_{c_1}(x1))) -> a_{c_1}(c_{a_1}(a_{a_1}(a_{c_1}(x1)))) 33.95/9.61 b_{b_1}(b_{b_1}(b_{b_1}(b_{c_1}(x1)))) -> b_{a_1}(a_{c_1}(x1)) 33.95/9.61 b_{b_1}(b_{c_1}(c_{a_1}(x1))) -> b_{c_1}(c_{a_1}(a_{a_1}(a_{a_1}(x1)))) 33.95/9.61 b_{b_1}(b_{c_1}(c_{b_1}(x1))) -> b_{c_1}(c_{a_1}(a_{a_1}(a_{b_1}(x1)))) 33.95/9.61 b_{b_1}(b_{c_1}(c_{c_1}(x1))) -> b_{c_1}(c_{a_1}(a_{a_1}(a_{c_1}(x1)))) 33.95/9.61 33.95/9.61 33.95/9.61 ---------------------------------------- 33.95/9.61 33.95/9.61 (13) 33.95/9.61 Obligation: 33.95/9.61 Q DP problem: 33.95/9.61 The TRS P consists of the following rules: 33.95/9.61 33.95/9.61 A_{A_1}(a_{a_1}(x1)) -> A_{B_1}(b_{a_1}(a_{a_1}(x1))) 33.95/9.61 A_{A_1}(a_{a_1}(x1)) -> B_{A_1}(a_{a_1}(x1)) 33.95/9.61 B_{A_1}(a_{a_1}(a_{a_1}(a_{a_1}(x1)))) -> B_{B_1}(b_{a_1}(a_{a_1}(a_{a_1}(x1)))) 33.95/9.61 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}(x1)))) 33.95/9.61 A_{A_1}(a_{b_1}(x1)) -> A_{B_1}(b_{a_1}(a_{b_1}(x1))) 33.95/9.61 A_{A_1}(a_{b_1}(x1)) -> B_{A_1}(a_{b_1}(x1)) 33.95/9.61 B_{A_1}(a_{a_1}(a_{a_1}(a_{c_1}(x1)))) -> B_{B_1}(b_{a_1}(a_{a_1}(a_{c_1}(x1)))) 33.95/9.61 A_{A_1}(a_{c_1}(x1)) -> A_{B_1}(b_{a_1}(a_{c_1}(x1))) 33.95/9.61 33.95/9.61 The TRS R consists of the following rules: 33.95/9.61 33.95/9.61 a_{a_1}(a_{a_1}(x1)) -> a_{b_1}(b_{a_1}(a_{a_1}(x1))) 33.95/9.61 a_{a_1}(a_{b_1}(x1)) -> a_{b_1}(b_{a_1}(a_{b_1}(x1))) 33.95/9.61 a_{a_1}(a_{c_1}(x1)) -> a_{b_1}(b_{a_1}(a_{c_1}(x1))) 33.95/9.61 b_{b_1}(b_{b_1}(b_{b_1}(b_{a_1}(x1)))) -> b_{a_1}(a_{a_1}(x1)) 33.95/9.61 b_{b_1}(b_{b_1}(b_{b_1}(b_{b_1}(x1)))) -> b_{a_1}(a_{b_1}(x1)) 33.95/9.61 b_{b_1}(b_{b_1}(b_{b_1}(b_{c_1}(x1)))) -> b_{a_1}(a_{c_1}(x1)) 33.95/9.61 a_{b_1}(b_{b_1}(b_{b_1}(b_{a_1}(x1)))) -> a_{a_1}(a_{a_1}(x1)) 33.95/9.61 a_{b_1}(b_{b_1}(b_{b_1}(b_{b_1}(x1)))) -> a_{a_1}(a_{b_1}(x1)) 33.95/9.61 a_{b_1}(b_{b_1}(b_{b_1}(b_{c_1}(x1)))) -> a_{a_1}(a_{c_1}(x1)) 33.95/9.61 c_{b_1}(b_{b_1}(b_{b_1}(b_{a_1}(x1)))) -> c_{a_1}(a_{a_1}(x1)) 33.95/9.61 c_{b_1}(b_{b_1}(b_{b_1}(b_{b_1}(x1)))) -> c_{a_1}(a_{b_1}(x1)) 33.95/9.61 c_{b_1}(b_{b_1}(b_{b_1}(b_{c_1}(x1)))) -> c_{a_1}(a_{c_1}(x1)) 33.95/9.61 b_{b_1}(b_{c_1}(c_{a_1}(x1))) -> b_{c_1}(c_{a_1}(a_{a_1}(a_{a_1}(x1)))) 33.95/9.61 b_{b_1}(b_{c_1}(c_{b_1}(x1))) -> b_{c_1}(c_{a_1}(a_{a_1}(a_{b_1}(x1)))) 33.95/9.61 b_{b_1}(b_{c_1}(c_{c_1}(x1))) -> b_{c_1}(c_{a_1}(a_{a_1}(a_{c_1}(x1)))) 33.95/9.61 a_{b_1}(b_{c_1}(c_{a_1}(x1))) -> a_{c_1}(c_{a_1}(a_{a_1}(a_{a_1}(x1)))) 33.95/9.61 a_{b_1}(b_{c_1}(c_{b_1}(x1))) -> a_{c_1}(c_{a_1}(a_{a_1}(a_{b_1}(x1)))) 33.95/9.61 a_{b_1}(b_{c_1}(c_{c_1}(x1))) -> a_{c_1}(c_{a_1}(a_{a_1}(a_{c_1}(x1)))) 33.95/9.61 c_{b_1}(b_{c_1}(c_{a_1}(x1))) -> c_{c_1}(c_{a_1}(a_{a_1}(a_{a_1}(x1)))) 33.95/9.61 c_{b_1}(b_{c_1}(c_{b_1}(x1))) -> c_{c_1}(c_{a_1}(a_{a_1}(a_{b_1}(x1)))) 33.95/9.61 c_{b_1}(b_{c_1}(c_{c_1}(x1))) -> c_{c_1}(c_{a_1}(a_{a_1}(a_{c_1}(x1)))) 33.95/9.61 b_{a_1}(a_{c_1}(c_{a_1}(x1))) -> b_{c_1}(c_{b_1}(b_{b_1}(b_{a_1}(x1)))) 33.95/9.61 b_{a_1}(a_{c_1}(c_{b_1}(x1))) -> b_{c_1}(c_{b_1}(b_{b_1}(b_{b_1}(x1)))) 33.95/9.61 b_{a_1}(a_{c_1}(c_{c_1}(x1))) -> b_{c_1}(c_{b_1}(b_{b_1}(b_{c_1}(x1)))) 33.95/9.61 a_{a_1}(a_{c_1}(c_{a_1}(x1))) -> a_{c_1}(c_{b_1}(b_{b_1}(b_{a_1}(x1)))) 33.95/9.61 a_{a_1}(a_{c_1}(c_{b_1}(x1))) -> a_{c_1}(c_{b_1}(b_{b_1}(b_{b_1}(x1)))) 33.95/9.61 a_{a_1}(a_{c_1}(c_{c_1}(x1))) -> a_{c_1}(c_{b_1}(b_{b_1}(b_{c_1}(x1)))) 33.95/9.61 c_{a_1}(a_{c_1}(c_{a_1}(x1))) -> c_{c_1}(c_{b_1}(b_{b_1}(b_{a_1}(x1)))) 33.95/9.61 c_{a_1}(a_{c_1}(c_{b_1}(x1))) -> c_{c_1}(c_{b_1}(b_{b_1}(b_{b_1}(x1)))) 33.95/9.61 c_{a_1}(a_{c_1}(c_{c_1}(x1))) -> c_{c_1}(c_{b_1}(b_{b_1}(b_{c_1}(x1)))) 33.95/9.61 b_{a_1}(a_{a_1}(a_{a_1}(a_{a_1}(x1)))) -> b_{b_1}(b_{a_1}(a_{a_1}(a_{a_1}(x1)))) 33.95/9.61 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}(x1)))) 33.95/9.61 b_{a_1}(a_{a_1}(a_{a_1}(a_{c_1}(x1)))) -> b_{b_1}(b_{a_1}(a_{a_1}(a_{c_1}(x1)))) 33.95/9.61 a_{a_1}(a_{a_1}(a_{a_1}(a_{a_1}(x1)))) -> a_{b_1}(b_{a_1}(a_{a_1}(a_{a_1}(x1)))) 33.95/9.61 a_{a_1}(a_{a_1}(a_{a_1}(a_{b_1}(x1)))) -> a_{b_1}(b_{a_1}(a_{a_1}(a_{b_1}(x1)))) 33.95/9.61 a_{a_1}(a_{a_1}(a_{a_1}(a_{c_1}(x1)))) -> a_{b_1}(b_{a_1}(a_{a_1}(a_{c_1}(x1)))) 33.95/9.61 c_{a_1}(a_{a_1}(a_{a_1}(a_{a_1}(x1)))) -> c_{b_1}(b_{a_1}(a_{a_1}(a_{a_1}(x1)))) 33.95/9.61 c_{a_1}(a_{a_1}(a_{a_1}(a_{b_1}(x1)))) -> c_{b_1}(b_{a_1}(a_{a_1}(a_{b_1}(x1)))) 33.95/9.61 c_{a_1}(a_{a_1}(a_{a_1}(a_{c_1}(x1)))) -> c_{b_1}(b_{a_1}(a_{a_1}(a_{c_1}(x1)))) 33.95/9.61 33.95/9.61 Q is empty. 33.95/9.61 We have to consider all minimal (P,Q,R)-chains. 33.95/9.61 ---------------------------------------- 33.95/9.61 33.95/9.61 (14) DependencyGraphProof (EQUIVALENT) 33.95/9.61 The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 0 SCCs with 8 less nodes. 33.95/9.61 ---------------------------------------- 33.95/9.61 33.95/9.61 (15) 33.95/9.61 TRUE 33.95/9.61 33.95/9.61 ---------------------------------------- 33.95/9.61 33.95/9.61 (16) 33.95/9.61 Obligation: 33.95/9.61 Q DP problem: 33.95/9.61 The TRS P consists of the following rules: 33.95/9.61 33.95/9.61 C_{B_1}(b_{b_1}(b_{b_1}(b_{a_1}(x1)))) -> C_{A_1}(a_{a_1}(x1)) 33.95/9.61 C_{A_1}(a_{a_1}(a_{a_1}(a_{a_1}(x1)))) -> C_{B_1}(b_{a_1}(a_{a_1}(a_{a_1}(x1)))) 33.95/9.61 C_{B_1}(b_{b_1}(b_{b_1}(b_{b_1}(x1)))) -> C_{A_1}(a_{b_1}(x1)) 33.95/9.61 C_{A_1}(a_{a_1}(a_{a_1}(a_{b_1}(x1)))) -> C_{B_1}(b_{a_1}(a_{a_1}(a_{b_1}(x1)))) 33.95/9.61 C_{A_1}(a_{a_1}(a_{a_1}(a_{c_1}(x1)))) -> C_{B_1}(b_{a_1}(a_{a_1}(a_{c_1}(x1)))) 33.95/9.61 33.95/9.61 The TRS R consists of the following rules: 33.95/9.61 33.95/9.61 a_{a_1}(a_{a_1}(x1)) -> a_{b_1}(b_{a_1}(a_{a_1}(x1))) 33.95/9.61 a_{a_1}(a_{b_1}(x1)) -> a_{b_1}(b_{a_1}(a_{b_1}(x1))) 33.95/9.61 a_{a_1}(a_{c_1}(x1)) -> a_{b_1}(b_{a_1}(a_{c_1}(x1))) 33.95/9.61 b_{b_1}(b_{b_1}(b_{b_1}(b_{a_1}(x1)))) -> b_{a_1}(a_{a_1}(x1)) 33.95/9.61 b_{b_1}(b_{b_1}(b_{b_1}(b_{b_1}(x1)))) -> b_{a_1}(a_{b_1}(x1)) 33.95/9.61 b_{b_1}(b_{b_1}(b_{b_1}(b_{c_1}(x1)))) -> b_{a_1}(a_{c_1}(x1)) 33.95/9.61 a_{b_1}(b_{b_1}(b_{b_1}(b_{a_1}(x1)))) -> a_{a_1}(a_{a_1}(x1)) 33.95/9.61 a_{b_1}(b_{b_1}(b_{b_1}(b_{b_1}(x1)))) -> a_{a_1}(a_{b_1}(x1)) 33.95/9.61 a_{b_1}(b_{b_1}(b_{b_1}(b_{c_1}(x1)))) -> a_{a_1}(a_{c_1}(x1)) 33.95/9.61 c_{b_1}(b_{b_1}(b_{b_1}(b_{a_1}(x1)))) -> c_{a_1}(a_{a_1}(x1)) 33.95/9.61 c_{b_1}(b_{b_1}(b_{b_1}(b_{b_1}(x1)))) -> c_{a_1}(a_{b_1}(x1)) 33.95/9.61 c_{b_1}(b_{b_1}(b_{b_1}(b_{c_1}(x1)))) -> c_{a_1}(a_{c_1}(x1)) 33.95/9.61 b_{b_1}(b_{c_1}(c_{a_1}(x1))) -> b_{c_1}(c_{a_1}(a_{a_1}(a_{a_1}(x1)))) 33.95/9.61 b_{b_1}(b_{c_1}(c_{b_1}(x1))) -> b_{c_1}(c_{a_1}(a_{a_1}(a_{b_1}(x1)))) 33.95/9.61 b_{b_1}(b_{c_1}(c_{c_1}(x1))) -> b_{c_1}(c_{a_1}(a_{a_1}(a_{c_1}(x1)))) 33.95/9.61 a_{b_1}(b_{c_1}(c_{a_1}(x1))) -> a_{c_1}(c_{a_1}(a_{a_1}(a_{a_1}(x1)))) 33.95/9.61 a_{b_1}(b_{c_1}(c_{b_1}(x1))) -> a_{c_1}(c_{a_1}(a_{a_1}(a_{b_1}(x1)))) 33.95/9.61 a_{b_1}(b_{c_1}(c_{c_1}(x1))) -> a_{c_1}(c_{a_1}(a_{a_1}(a_{c_1}(x1)))) 33.95/9.61 c_{b_1}(b_{c_1}(c_{a_1}(x1))) -> c_{c_1}(c_{a_1}(a_{a_1}(a_{a_1}(x1)))) 33.95/9.61 c_{b_1}(b_{c_1}(c_{b_1}(x1))) -> c_{c_1}(c_{a_1}(a_{a_1}(a_{b_1}(x1)))) 33.95/9.61 c_{b_1}(b_{c_1}(c_{c_1}(x1))) -> c_{c_1}(c_{a_1}(a_{a_1}(a_{c_1}(x1)))) 33.95/9.61 b_{a_1}(a_{c_1}(c_{a_1}(x1))) -> b_{c_1}(c_{b_1}(b_{b_1}(b_{a_1}(x1)))) 33.95/9.61 b_{a_1}(a_{c_1}(c_{b_1}(x1))) -> b_{c_1}(c_{b_1}(b_{b_1}(b_{b_1}(x1)))) 33.95/9.61 b_{a_1}(a_{c_1}(c_{c_1}(x1))) -> b_{c_1}(c_{b_1}(b_{b_1}(b_{c_1}(x1)))) 33.95/9.61 a_{a_1}(a_{c_1}(c_{a_1}(x1))) -> a_{c_1}(c_{b_1}(b_{b_1}(b_{a_1}(x1)))) 33.95/9.61 a_{a_1}(a_{c_1}(c_{b_1}(x1))) -> a_{c_1}(c_{b_1}(b_{b_1}(b_{b_1}(x1)))) 33.95/9.61 a_{a_1}(a_{c_1}(c_{c_1}(x1))) -> a_{c_1}(c_{b_1}(b_{b_1}(b_{c_1}(x1)))) 33.95/9.61 c_{a_1}(a_{c_1}(c_{a_1}(x1))) -> c_{c_1}(c_{b_1}(b_{b_1}(b_{a_1}(x1)))) 33.95/9.61 c_{a_1}(a_{c_1}(c_{b_1}(x1))) -> c_{c_1}(c_{b_1}(b_{b_1}(b_{b_1}(x1)))) 33.95/9.61 c_{a_1}(a_{c_1}(c_{c_1}(x1))) -> c_{c_1}(c_{b_1}(b_{b_1}(b_{c_1}(x1)))) 33.95/9.61 b_{a_1}(a_{a_1}(a_{a_1}(a_{a_1}(x1)))) -> b_{b_1}(b_{a_1}(a_{a_1}(a_{a_1}(x1)))) 33.95/9.61 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}(x1)))) 33.95/9.61 b_{a_1}(a_{a_1}(a_{a_1}(a_{c_1}(x1)))) -> b_{b_1}(b_{a_1}(a_{a_1}(a_{c_1}(x1)))) 33.95/9.61 a_{a_1}(a_{a_1}(a_{a_1}(a_{a_1}(x1)))) -> a_{b_1}(b_{a_1}(a_{a_1}(a_{a_1}(x1)))) 33.95/9.61 a_{a_1}(a_{a_1}(a_{a_1}(a_{b_1}(x1)))) -> a_{b_1}(b_{a_1}(a_{a_1}(a_{b_1}(x1)))) 33.95/9.61 a_{a_1}(a_{a_1}(a_{a_1}(a_{c_1}(x1)))) -> a_{b_1}(b_{a_1}(a_{a_1}(a_{c_1}(x1)))) 33.95/9.61 c_{a_1}(a_{a_1}(a_{a_1}(a_{a_1}(x1)))) -> c_{b_1}(b_{a_1}(a_{a_1}(a_{a_1}(x1)))) 33.95/9.61 c_{a_1}(a_{a_1}(a_{a_1}(a_{b_1}(x1)))) -> c_{b_1}(b_{a_1}(a_{a_1}(a_{b_1}(x1)))) 33.95/9.61 c_{a_1}(a_{a_1}(a_{a_1}(a_{c_1}(x1)))) -> c_{b_1}(b_{a_1}(a_{a_1}(a_{c_1}(x1)))) 33.95/9.61 33.95/9.61 Q is empty. 33.95/9.61 We have to consider all minimal (P,Q,R)-chains. 33.95/9.61 ---------------------------------------- 33.95/9.61 33.95/9.61 (17) QDPOrderProof (EQUIVALENT) 33.95/9.61 We use the reduction pair processor [LPAR04,JAR06]. 33.95/9.61 33.95/9.61 33.95/9.61 The following pairs can be oriented strictly and are deleted. 33.95/9.61 33.95/9.61 C_{B_1}(b_{b_1}(b_{b_1}(b_{a_1}(x1)))) -> C_{A_1}(a_{a_1}(x1)) 33.95/9.61 C_{A_1}(a_{a_1}(a_{a_1}(a_{a_1}(x1)))) -> C_{B_1}(b_{a_1}(a_{a_1}(a_{a_1}(x1)))) 33.95/9.61 C_{B_1}(b_{b_1}(b_{b_1}(b_{b_1}(x1)))) -> C_{A_1}(a_{b_1}(x1)) 33.95/9.61 C_{A_1}(a_{a_1}(a_{a_1}(a_{b_1}(x1)))) -> C_{B_1}(b_{a_1}(a_{a_1}(a_{b_1}(x1)))) 33.95/9.61 C_{A_1}(a_{a_1}(a_{a_1}(a_{c_1}(x1)))) -> C_{B_1}(b_{a_1}(a_{a_1}(a_{c_1}(x1)))) 33.95/9.61 The remaining pairs can at least be oriented weakly. 33.95/9.61 Used ordering: Polynomial interpretation [POLO]: 33.95/9.61 33.95/9.61 POL(C_{A_1}(x_1)) = 1 + x_1 33.95/9.61 POL(C_{B_1}(x_1)) = x_1 33.95/9.61 POL(a_{a_1}(x_1)) = 1 + x_1 33.95/9.61 POL(a_{b_1}(x_1)) = x_1 33.95/9.61 POL(a_{c_1}(x_1)) = 0 33.95/9.61 POL(b_{a_1}(x_1)) = 1 + x_1 33.95/9.61 POL(b_{b_1}(x_1)) = 1 + x_1 33.95/9.61 POL(b_{c_1}(x_1)) = 0 33.95/9.61 POL(c_{a_1}(x_1)) = 0 33.95/9.61 POL(c_{b_1}(x_1)) = 0 33.95/9.61 POL(c_{c_1}(x_1)) = 0 33.95/9.61 33.95/9.61 The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: 33.95/9.61 33.95/9.61 a_{b_1}(b_{b_1}(b_{b_1}(b_{a_1}(x1)))) -> a_{a_1}(a_{a_1}(x1)) 33.95/9.61 a_{a_1}(a_{a_1}(x1)) -> a_{b_1}(b_{a_1}(a_{a_1}(x1))) 33.95/9.61 a_{b_1}(b_{b_1}(b_{b_1}(b_{b_1}(x1)))) -> a_{a_1}(a_{b_1}(x1)) 33.95/9.61 a_{a_1}(a_{b_1}(x1)) -> a_{b_1}(b_{a_1}(a_{b_1}(x1))) 33.95/9.61 a_{b_1}(b_{b_1}(b_{b_1}(b_{c_1}(x1)))) -> a_{a_1}(a_{c_1}(x1)) 33.95/9.61 a_{a_1}(a_{c_1}(x1)) -> a_{b_1}(b_{a_1}(a_{c_1}(x1))) 33.95/9.61 a_{a_1}(a_{a_1}(a_{a_1}(a_{a_1}(x1)))) -> a_{b_1}(b_{a_1}(a_{a_1}(a_{a_1}(x1)))) 33.95/9.61 a_{a_1}(a_{a_1}(a_{a_1}(a_{b_1}(x1)))) -> a_{b_1}(b_{a_1}(a_{a_1}(a_{b_1}(x1)))) 33.95/9.61 a_{a_1}(a_{a_1}(a_{a_1}(a_{c_1}(x1)))) -> a_{b_1}(b_{a_1}(a_{a_1}(a_{c_1}(x1)))) 33.95/9.61 a_{a_1}(a_{c_1}(c_{a_1}(x1))) -> a_{c_1}(c_{b_1}(b_{b_1}(b_{a_1}(x1)))) 33.95/9.61 a_{a_1}(a_{c_1}(c_{b_1}(x1))) -> a_{c_1}(c_{b_1}(b_{b_1}(b_{b_1}(x1)))) 33.95/9.61 a_{a_1}(a_{c_1}(c_{c_1}(x1))) -> a_{c_1}(c_{b_1}(b_{b_1}(b_{c_1}(x1)))) 33.95/9.61 b_{a_1}(a_{c_1}(c_{a_1}(x1))) -> b_{c_1}(c_{b_1}(b_{b_1}(b_{a_1}(x1)))) 33.95/9.61 b_{a_1}(a_{c_1}(c_{b_1}(x1))) -> b_{c_1}(c_{b_1}(b_{b_1}(b_{b_1}(x1)))) 33.95/9.61 b_{a_1}(a_{c_1}(c_{c_1}(x1))) -> b_{c_1}(c_{b_1}(b_{b_1}(b_{c_1}(x1)))) 33.95/9.61 b_{a_1}(a_{a_1}(a_{a_1}(a_{a_1}(x1)))) -> b_{b_1}(b_{a_1}(a_{a_1}(a_{a_1}(x1)))) 33.95/9.61 b_{b_1}(b_{b_1}(b_{b_1}(b_{a_1}(x1)))) -> b_{a_1}(a_{a_1}(x1)) 33.95/9.61 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}(x1)))) 33.95/9.61 b_{b_1}(b_{b_1}(b_{b_1}(b_{b_1}(x1)))) -> b_{a_1}(a_{b_1}(x1)) 33.95/9.61 b_{a_1}(a_{a_1}(a_{a_1}(a_{c_1}(x1)))) -> b_{b_1}(b_{a_1}(a_{a_1}(a_{c_1}(x1)))) 33.95/9.61 a_{b_1}(b_{c_1}(c_{a_1}(x1))) -> a_{c_1}(c_{a_1}(a_{a_1}(a_{a_1}(x1)))) 33.95/9.61 a_{b_1}(b_{c_1}(c_{b_1}(x1))) -> a_{c_1}(c_{a_1}(a_{a_1}(a_{b_1}(x1)))) 33.95/9.61 a_{b_1}(b_{c_1}(c_{c_1}(x1))) -> a_{c_1}(c_{a_1}(a_{a_1}(a_{c_1}(x1)))) 33.95/9.61 b_{b_1}(b_{b_1}(b_{b_1}(b_{c_1}(x1)))) -> b_{a_1}(a_{c_1}(x1)) 33.95/9.61 b_{b_1}(b_{c_1}(c_{a_1}(x1))) -> b_{c_1}(c_{a_1}(a_{a_1}(a_{a_1}(x1)))) 33.95/9.61 b_{b_1}(b_{c_1}(c_{b_1}(x1))) -> b_{c_1}(c_{a_1}(a_{a_1}(a_{b_1}(x1)))) 33.95/9.61 b_{b_1}(b_{c_1}(c_{c_1}(x1))) -> b_{c_1}(c_{a_1}(a_{a_1}(a_{c_1}(x1)))) 33.95/9.61 33.95/9.61 33.95/9.61 ---------------------------------------- 33.95/9.61 33.95/9.61 (18) 33.95/9.61 Obligation: 33.95/9.61 Q DP problem: 33.95/9.61 P is empty. 33.95/9.61 The TRS R consists of the following rules: 33.95/9.61 33.95/9.61 a_{a_1}(a_{a_1}(x1)) -> a_{b_1}(b_{a_1}(a_{a_1}(x1))) 33.95/9.61 a_{a_1}(a_{b_1}(x1)) -> a_{b_1}(b_{a_1}(a_{b_1}(x1))) 33.95/9.61 a_{a_1}(a_{c_1}(x1)) -> a_{b_1}(b_{a_1}(a_{c_1}(x1))) 33.95/9.61 b_{b_1}(b_{b_1}(b_{b_1}(b_{a_1}(x1)))) -> b_{a_1}(a_{a_1}(x1)) 33.95/9.61 b_{b_1}(b_{b_1}(b_{b_1}(b_{b_1}(x1)))) -> b_{a_1}(a_{b_1}(x1)) 33.95/9.61 b_{b_1}(b_{b_1}(b_{b_1}(b_{c_1}(x1)))) -> b_{a_1}(a_{c_1}(x1)) 33.95/9.61 a_{b_1}(b_{b_1}(b_{b_1}(b_{a_1}(x1)))) -> a_{a_1}(a_{a_1}(x1)) 33.95/9.61 a_{b_1}(b_{b_1}(b_{b_1}(b_{b_1}(x1)))) -> a_{a_1}(a_{b_1}(x1)) 33.95/9.61 a_{b_1}(b_{b_1}(b_{b_1}(b_{c_1}(x1)))) -> a_{a_1}(a_{c_1}(x1)) 33.95/9.61 c_{b_1}(b_{b_1}(b_{b_1}(b_{a_1}(x1)))) -> c_{a_1}(a_{a_1}(x1)) 33.95/9.61 c_{b_1}(b_{b_1}(b_{b_1}(b_{b_1}(x1)))) -> c_{a_1}(a_{b_1}(x1)) 33.95/9.61 c_{b_1}(b_{b_1}(b_{b_1}(b_{c_1}(x1)))) -> c_{a_1}(a_{c_1}(x1)) 33.95/9.61 b_{b_1}(b_{c_1}(c_{a_1}(x1))) -> b_{c_1}(c_{a_1}(a_{a_1}(a_{a_1}(x1)))) 33.95/9.61 b_{b_1}(b_{c_1}(c_{b_1}(x1))) -> b_{c_1}(c_{a_1}(a_{a_1}(a_{b_1}(x1)))) 33.95/9.61 b_{b_1}(b_{c_1}(c_{c_1}(x1))) -> b_{c_1}(c_{a_1}(a_{a_1}(a_{c_1}(x1)))) 33.95/9.61 a_{b_1}(b_{c_1}(c_{a_1}(x1))) -> a_{c_1}(c_{a_1}(a_{a_1}(a_{a_1}(x1)))) 33.95/9.61 a_{b_1}(b_{c_1}(c_{b_1}(x1))) -> a_{c_1}(c_{a_1}(a_{a_1}(a_{b_1}(x1)))) 33.95/9.61 a_{b_1}(b_{c_1}(c_{c_1}(x1))) -> a_{c_1}(c_{a_1}(a_{a_1}(a_{c_1}(x1)))) 33.95/9.61 c_{b_1}(b_{c_1}(c_{a_1}(x1))) -> c_{c_1}(c_{a_1}(a_{a_1}(a_{a_1}(x1)))) 33.95/9.61 c_{b_1}(b_{c_1}(c_{b_1}(x1))) -> c_{c_1}(c_{a_1}(a_{a_1}(a_{b_1}(x1)))) 33.95/9.61 c_{b_1}(b_{c_1}(c_{c_1}(x1))) -> c_{c_1}(c_{a_1}(a_{a_1}(a_{c_1}(x1)))) 33.95/9.61 b_{a_1}(a_{c_1}(c_{a_1}(x1))) -> b_{c_1}(c_{b_1}(b_{b_1}(b_{a_1}(x1)))) 33.95/9.61 b_{a_1}(a_{c_1}(c_{b_1}(x1))) -> b_{c_1}(c_{b_1}(b_{b_1}(b_{b_1}(x1)))) 33.95/9.61 b_{a_1}(a_{c_1}(c_{c_1}(x1))) -> b_{c_1}(c_{b_1}(b_{b_1}(b_{c_1}(x1)))) 33.95/9.61 a_{a_1}(a_{c_1}(c_{a_1}(x1))) -> a_{c_1}(c_{b_1}(b_{b_1}(b_{a_1}(x1)))) 33.95/9.61 a_{a_1}(a_{c_1}(c_{b_1}(x1))) -> a_{c_1}(c_{b_1}(b_{b_1}(b_{b_1}(x1)))) 33.95/9.61 a_{a_1}(a_{c_1}(c_{c_1}(x1))) -> a_{c_1}(c_{b_1}(b_{b_1}(b_{c_1}(x1)))) 33.95/9.61 c_{a_1}(a_{c_1}(c_{a_1}(x1))) -> c_{c_1}(c_{b_1}(b_{b_1}(b_{a_1}(x1)))) 33.95/9.61 c_{a_1}(a_{c_1}(c_{b_1}(x1))) -> c_{c_1}(c_{b_1}(b_{b_1}(b_{b_1}(x1)))) 33.95/9.61 c_{a_1}(a_{c_1}(c_{c_1}(x1))) -> c_{c_1}(c_{b_1}(b_{b_1}(b_{c_1}(x1)))) 33.95/9.61 b_{a_1}(a_{a_1}(a_{a_1}(a_{a_1}(x1)))) -> b_{b_1}(b_{a_1}(a_{a_1}(a_{a_1}(x1)))) 33.95/9.61 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}(x1)))) 33.95/9.61 b_{a_1}(a_{a_1}(a_{a_1}(a_{c_1}(x1)))) -> b_{b_1}(b_{a_1}(a_{a_1}(a_{c_1}(x1)))) 33.95/9.61 a_{a_1}(a_{a_1}(a_{a_1}(a_{a_1}(x1)))) -> a_{b_1}(b_{a_1}(a_{a_1}(a_{a_1}(x1)))) 33.95/9.61 a_{a_1}(a_{a_1}(a_{a_1}(a_{b_1}(x1)))) -> a_{b_1}(b_{a_1}(a_{a_1}(a_{b_1}(x1)))) 33.95/9.61 a_{a_1}(a_{a_1}(a_{a_1}(a_{c_1}(x1)))) -> a_{b_1}(b_{a_1}(a_{a_1}(a_{c_1}(x1)))) 33.95/9.61 c_{a_1}(a_{a_1}(a_{a_1}(a_{a_1}(x1)))) -> c_{b_1}(b_{a_1}(a_{a_1}(a_{a_1}(x1)))) 33.95/9.61 c_{a_1}(a_{a_1}(a_{a_1}(a_{b_1}(x1)))) -> c_{b_1}(b_{a_1}(a_{a_1}(a_{b_1}(x1)))) 33.95/9.61 c_{a_1}(a_{a_1}(a_{a_1}(a_{c_1}(x1)))) -> c_{b_1}(b_{a_1}(a_{a_1}(a_{c_1}(x1)))) 33.95/9.61 33.95/9.61 Q is empty. 33.95/9.61 We have to consider all minimal (P,Q,R)-chains. 33.95/9.61 ---------------------------------------- 33.95/9.61 33.95/9.61 (19) PisEmptyProof (EQUIVALENT) 33.95/9.61 The TRS P is empty. Hence, there is no (P,Q,R) chain. 33.95/9.61 ---------------------------------------- 33.95/9.61 33.95/9.61 (20) 33.95/9.61 YES 34.25/9.71 EOF