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