41.38/11.51 YES 43.72/12.10 proof of /export/starexec/sandbox/benchmark/theBenchmark.xml 43.72/12.10 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 43.72/12.10 43.72/12.10 43.72/12.10 Termination w.r.t. Q of the given QTRS could be proven: 43.72/12.10 43.72/12.10 (0) QTRS 43.72/12.10 (1) QTRSRRRProof [EQUIVALENT, 106 ms] 43.72/12.10 (2) QTRS 43.72/12.10 (3) Overlay + Local Confluence [EQUIVALENT, 26 ms] 43.72/12.10 (4) QTRS 43.72/12.10 (5) DependencyPairsProof [EQUIVALENT, 83 ms] 43.72/12.10 (6) QDP 43.72/12.10 (7) MRRProof [EQUIVALENT, 683 ms] 43.72/12.10 (8) QDP 43.72/12.10 (9) PisEmptyProof [EQUIVALENT, 0 ms] 43.72/12.10 (10) YES 43.72/12.10 43.72/12.10 43.72/12.10 ---------------------------------------- 43.72/12.10 43.72/12.10 (0) 43.72/12.10 Obligation: 43.72/12.10 Q restricted rewrite system: 43.72/12.10 The TRS R consists of the following rules: 43.72/12.10 43.72/12.10 a(a(b(b(x1)))) -> C(C(x1)) 43.72/12.10 b(b(c(c(x1)))) -> A(A(x1)) 43.72/12.10 c(c(a(a(x1)))) -> B(B(x1)) 43.72/12.10 A(A(C(C(x1)))) -> b(b(x1)) 43.72/12.10 C(C(B(B(x1)))) -> a(a(x1)) 43.72/12.10 B(B(A(A(x1)))) -> c(c(x1)) 43.72/12.10 a(a(a(a(a(a(a(a(a(a(x1)))))))))) -> A(A(A(A(A(A(x1)))))) 43.72/12.10 A(A(A(A(A(A(A(A(x1)))))))) -> a(a(a(a(a(a(a(a(x1)))))))) 43.72/12.10 b(b(b(b(b(b(b(b(b(b(x1)))))))))) -> B(B(B(B(B(B(x1)))))) 43.72/12.10 B(B(B(B(B(B(B(B(x1)))))))) -> b(b(b(b(b(b(b(b(x1)))))))) 43.72/12.10 c(c(c(c(c(c(c(c(c(c(x1)))))))))) -> C(C(C(C(C(C(x1)))))) 43.72/12.10 C(C(C(C(C(C(C(C(x1)))))))) -> c(c(c(c(c(c(c(c(x1)))))))) 43.72/12.10 B(B(a(a(a(a(a(a(a(a(x1)))))))))) -> c(c(A(A(A(A(A(A(x1)))))))) 43.72/12.10 A(A(A(A(A(A(b(b(x1)))))))) -> a(a(a(a(a(a(a(a(C(C(x1)))))))))) 43.72/12.10 C(C(b(b(b(b(b(b(b(b(x1)))))))))) -> a(a(B(B(B(B(B(B(x1)))))))) 43.72/12.10 B(B(B(B(B(B(c(c(x1)))))))) -> b(b(b(b(b(b(b(b(A(A(x1)))))))))) 43.72/12.10 A(A(c(c(c(c(c(c(c(c(x1)))))))))) -> b(b(C(C(C(C(C(C(x1)))))))) 43.72/12.10 C(C(C(C(C(C(a(a(x1)))))))) -> c(c(c(c(c(c(c(c(B(B(x1)))))))))) 43.72/12.10 a(a(A(A(x1)))) -> x1 43.72/12.10 A(A(a(a(x1)))) -> x1 43.72/12.10 b(b(B(B(x1)))) -> x1 43.72/12.10 B(B(b(b(x1)))) -> x1 43.72/12.10 c(c(C(C(x1)))) -> x1 43.72/12.10 C(C(c(c(x1)))) -> x1 43.72/12.10 43.72/12.10 Q is empty. 43.72/12.10 43.72/12.10 ---------------------------------------- 43.72/12.10 43.72/12.10 (1) QTRSRRRProof (EQUIVALENT) 43.72/12.10 Used ordering: 43.72/12.10 Polynomial interpretation [POLO]: 43.72/12.10 43.72/12.10 POL(A(x_1)) = 3 + x_1 43.72/12.10 POL(B(x_1)) = 3 + x_1 43.72/12.10 POL(C(x_1)) = 3 + x_1 43.72/12.10 POL(a(x_1)) = 2 + x_1 43.72/12.10 POL(b(x_1)) = 2 + x_1 43.72/12.10 POL(c(x_1)) = 2 + x_1 43.72/12.10 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: 43.72/12.10 43.72/12.10 a(a(b(b(x1)))) -> C(C(x1)) 43.72/12.10 b(b(c(c(x1)))) -> A(A(x1)) 43.72/12.10 c(c(a(a(x1)))) -> B(B(x1)) 43.72/12.10 A(A(C(C(x1)))) -> b(b(x1)) 43.72/12.10 C(C(B(B(x1)))) -> a(a(x1)) 43.72/12.10 B(B(A(A(x1)))) -> c(c(x1)) 43.72/12.10 a(a(a(a(a(a(a(a(a(a(x1)))))))))) -> A(A(A(A(A(A(x1)))))) 43.72/12.10 A(A(A(A(A(A(A(A(x1)))))))) -> a(a(a(a(a(a(a(a(x1)))))))) 43.72/12.10 b(b(b(b(b(b(b(b(b(b(x1)))))))))) -> B(B(B(B(B(B(x1)))))) 43.72/12.10 B(B(B(B(B(B(B(B(x1)))))))) -> b(b(b(b(b(b(b(b(x1)))))))) 43.72/12.10 c(c(c(c(c(c(c(c(c(c(x1)))))))))) -> C(C(C(C(C(C(x1)))))) 43.72/12.10 C(C(C(C(C(C(C(C(x1)))))))) -> c(c(c(c(c(c(c(c(x1)))))))) 43.72/12.10 a(a(A(A(x1)))) -> x1 43.72/12.10 A(A(a(a(x1)))) -> x1 43.72/12.10 b(b(B(B(x1)))) -> x1 43.72/12.10 B(B(b(b(x1)))) -> x1 43.72/12.10 c(c(C(C(x1)))) -> x1 43.72/12.10 C(C(c(c(x1)))) -> x1 43.72/12.10 43.72/12.10 43.72/12.10 43.72/12.10 43.72/12.10 ---------------------------------------- 43.72/12.10 43.72/12.10 (2) 43.72/12.10 Obligation: 43.72/12.10 Q restricted rewrite system: 43.72/12.10 The TRS R consists of the following rules: 43.72/12.10 43.72/12.10 B(B(a(a(a(a(a(a(a(a(x1)))))))))) -> c(c(A(A(A(A(A(A(x1)))))))) 43.72/12.10 A(A(A(A(A(A(b(b(x1)))))))) -> a(a(a(a(a(a(a(a(C(C(x1)))))))))) 43.72/12.10 C(C(b(b(b(b(b(b(b(b(x1)))))))))) -> a(a(B(B(B(B(B(B(x1)))))))) 43.72/12.10 B(B(B(B(B(B(c(c(x1)))))))) -> b(b(b(b(b(b(b(b(A(A(x1)))))))))) 43.72/12.10 A(A(c(c(c(c(c(c(c(c(x1)))))))))) -> b(b(C(C(C(C(C(C(x1)))))))) 43.72/12.10 C(C(C(C(C(C(a(a(x1)))))))) -> c(c(c(c(c(c(c(c(B(B(x1)))))))))) 43.72/12.10 43.72/12.10 Q is empty. 43.72/12.10 43.72/12.10 ---------------------------------------- 43.72/12.10 43.72/12.10 (3) Overlay + Local Confluence (EQUIVALENT) 43.72/12.10 The TRS is overlay and locally confluent. By [NOC] we can switch to innermost. 43.72/12.10 ---------------------------------------- 43.72/12.10 43.72/12.10 (4) 43.72/12.10 Obligation: 43.72/12.10 Q restricted rewrite system: 43.72/12.10 The TRS R consists of the following rules: 43.72/12.10 43.72/12.10 B(B(a(a(a(a(a(a(a(a(x1)))))))))) -> c(c(A(A(A(A(A(A(x1)))))))) 43.72/12.10 A(A(A(A(A(A(b(b(x1)))))))) -> a(a(a(a(a(a(a(a(C(C(x1)))))))))) 43.72/12.10 C(C(b(b(b(b(b(b(b(b(x1)))))))))) -> a(a(B(B(B(B(B(B(x1)))))))) 43.72/12.10 B(B(B(B(B(B(c(c(x1)))))))) -> b(b(b(b(b(b(b(b(A(A(x1)))))))))) 43.72/12.10 A(A(c(c(c(c(c(c(c(c(x1)))))))))) -> b(b(C(C(C(C(C(C(x1)))))))) 43.72/12.10 C(C(C(C(C(C(a(a(x1)))))))) -> c(c(c(c(c(c(c(c(B(B(x1)))))))))) 43.72/12.10 43.72/12.10 The set Q consists of the following terms: 43.72/12.10 43.72/12.10 B(B(a(a(a(a(a(a(a(a(x0)))))))))) 43.72/12.10 A(A(A(A(A(A(b(b(x0)))))))) 43.72/12.10 C(C(b(b(b(b(b(b(b(b(x0)))))))))) 43.72/12.10 B(B(B(B(B(B(c(c(x0)))))))) 43.72/12.10 A(A(c(c(c(c(c(c(c(c(x0)))))))))) 43.72/12.10 C(C(C(C(C(C(a(a(x0)))))))) 43.72/12.10 43.72/12.10 43.72/12.10 ---------------------------------------- 43.72/12.10 43.72/12.10 (5) DependencyPairsProof (EQUIVALENT) 43.72/12.10 Using Dependency Pairs [AG00,LPAR04] we result in the following initial DP problem. 43.72/12.10 ---------------------------------------- 43.72/12.10 43.72/12.10 (6) 43.72/12.10 Obligation: 43.72/12.10 Q DP problem: 43.72/12.10 The TRS P consists of the following rules: 43.72/12.10 43.72/12.10 B^1(B(a(a(a(a(a(a(a(a(x1)))))))))) -> A^1(A(A(A(A(A(x1)))))) 43.72/12.10 B^1(B(a(a(a(a(a(a(a(a(x1)))))))))) -> A^1(A(A(A(A(x1))))) 43.72/12.10 B^1(B(a(a(a(a(a(a(a(a(x1)))))))))) -> A^1(A(A(A(x1)))) 43.72/12.10 B^1(B(a(a(a(a(a(a(a(a(x1)))))))))) -> A^1(A(A(x1))) 43.72/12.10 B^1(B(a(a(a(a(a(a(a(a(x1)))))))))) -> A^1(A(x1)) 43.72/12.10 B^1(B(a(a(a(a(a(a(a(a(x1)))))))))) -> A^1(x1) 43.72/12.10 A^1(A(A(A(A(A(b(b(x1)))))))) -> C^1(C(x1)) 43.72/12.10 A^1(A(A(A(A(A(b(b(x1)))))))) -> C^1(x1) 43.72/12.10 C^1(C(b(b(b(b(b(b(b(b(x1)))))))))) -> B^1(B(B(B(B(B(x1)))))) 43.72/12.10 C^1(C(b(b(b(b(b(b(b(b(x1)))))))))) -> B^1(B(B(B(B(x1))))) 43.72/12.10 C^1(C(b(b(b(b(b(b(b(b(x1)))))))))) -> B^1(B(B(B(x1)))) 43.72/12.10 C^1(C(b(b(b(b(b(b(b(b(x1)))))))))) -> B^1(B(B(x1))) 43.72/12.10 C^1(C(b(b(b(b(b(b(b(b(x1)))))))))) -> B^1(B(x1)) 43.72/12.10 C^1(C(b(b(b(b(b(b(b(b(x1)))))))))) -> B^1(x1) 43.72/12.10 B^1(B(B(B(B(B(c(c(x1)))))))) -> A^1(A(x1)) 43.72/12.10 B^1(B(B(B(B(B(c(c(x1)))))))) -> A^1(x1) 43.72/12.10 A^1(A(c(c(c(c(c(c(c(c(x1)))))))))) -> C^1(C(C(C(C(C(x1)))))) 43.72/12.10 A^1(A(c(c(c(c(c(c(c(c(x1)))))))))) -> C^1(C(C(C(C(x1))))) 43.72/12.10 A^1(A(c(c(c(c(c(c(c(c(x1)))))))))) -> C^1(C(C(C(x1)))) 43.72/12.10 A^1(A(c(c(c(c(c(c(c(c(x1)))))))))) -> C^1(C(C(x1))) 43.72/12.10 A^1(A(c(c(c(c(c(c(c(c(x1)))))))))) -> C^1(C(x1)) 43.72/12.10 A^1(A(c(c(c(c(c(c(c(c(x1)))))))))) -> C^1(x1) 43.72/12.10 C^1(C(C(C(C(C(a(a(x1)))))))) -> B^1(B(x1)) 43.72/12.10 C^1(C(C(C(C(C(a(a(x1)))))))) -> B^1(x1) 43.72/12.10 43.72/12.10 The TRS R consists of the following rules: 43.72/12.10 43.72/12.10 B(B(a(a(a(a(a(a(a(a(x1)))))))))) -> c(c(A(A(A(A(A(A(x1)))))))) 43.72/12.10 A(A(A(A(A(A(b(b(x1)))))))) -> a(a(a(a(a(a(a(a(C(C(x1)))))))))) 43.72/12.10 C(C(b(b(b(b(b(b(b(b(x1)))))))))) -> a(a(B(B(B(B(B(B(x1)))))))) 43.72/12.10 B(B(B(B(B(B(c(c(x1)))))))) -> b(b(b(b(b(b(b(b(A(A(x1)))))))))) 43.72/12.10 A(A(c(c(c(c(c(c(c(c(x1)))))))))) -> b(b(C(C(C(C(C(C(x1)))))))) 43.72/12.10 C(C(C(C(C(C(a(a(x1)))))))) -> c(c(c(c(c(c(c(c(B(B(x1)))))))))) 43.72/12.10 43.72/12.10 The set Q consists of the following terms: 43.72/12.10 43.72/12.10 B(B(a(a(a(a(a(a(a(a(x0)))))))))) 43.72/12.10 A(A(A(A(A(A(b(b(x0)))))))) 43.72/12.10 C(C(b(b(b(b(b(b(b(b(x0)))))))))) 43.72/12.10 B(B(B(B(B(B(c(c(x0)))))))) 43.72/12.10 A(A(c(c(c(c(c(c(c(c(x0)))))))))) 43.72/12.10 C(C(C(C(C(C(a(a(x0)))))))) 43.72/12.10 43.72/12.10 We have to consider all minimal (P,Q,R)-chains. 43.72/12.10 ---------------------------------------- 43.72/12.10 43.72/12.10 (7) MRRProof (EQUIVALENT) 43.72/12.10 By using the rule removal processor [LPAR04] with the following ordering, at least one Dependency Pair or term rewrite system rule of this QDP problem can be strictly oriented. 43.72/12.10 43.72/12.10 Strictly oriented dependency pairs: 43.72/12.10 43.72/12.10 B^1(B(a(a(a(a(a(a(a(a(x1)))))))))) -> A^1(A(A(A(A(A(x1)))))) 43.72/12.10 B^1(B(a(a(a(a(a(a(a(a(x1)))))))))) -> A^1(A(A(A(A(x1))))) 43.72/12.10 B^1(B(a(a(a(a(a(a(a(a(x1)))))))))) -> A^1(A(A(A(x1)))) 43.72/12.10 B^1(B(a(a(a(a(a(a(a(a(x1)))))))))) -> A^1(A(A(x1))) 43.72/12.10 B^1(B(a(a(a(a(a(a(a(a(x1)))))))))) -> A^1(A(x1)) 43.72/12.10 B^1(B(a(a(a(a(a(a(a(a(x1)))))))))) -> A^1(x1) 43.72/12.10 A^1(A(A(A(A(A(b(b(x1)))))))) -> C^1(C(x1)) 43.72/12.10 A^1(A(A(A(A(A(b(b(x1)))))))) -> C^1(x1) 43.72/12.10 C^1(C(b(b(b(b(b(b(b(b(x1)))))))))) -> B^1(B(B(B(B(B(x1)))))) 43.72/12.10 C^1(C(b(b(b(b(b(b(b(b(x1)))))))))) -> B^1(B(B(B(B(x1))))) 43.72/12.10 C^1(C(b(b(b(b(b(b(b(b(x1)))))))))) -> B^1(B(B(B(x1)))) 43.72/12.10 C^1(C(b(b(b(b(b(b(b(b(x1)))))))))) -> B^1(B(B(x1))) 43.72/12.10 C^1(C(b(b(b(b(b(b(b(b(x1)))))))))) -> B^1(B(x1)) 43.72/12.10 C^1(C(b(b(b(b(b(b(b(b(x1)))))))))) -> B^1(x1) 43.72/12.10 B^1(B(B(B(B(B(c(c(x1)))))))) -> A^1(A(x1)) 43.72/12.10 B^1(B(B(B(B(B(c(c(x1)))))))) -> A^1(x1) 43.72/12.10 A^1(A(c(c(c(c(c(c(c(c(x1)))))))))) -> C^1(C(C(C(C(C(x1)))))) 43.72/12.10 A^1(A(c(c(c(c(c(c(c(c(x1)))))))))) -> C^1(C(C(C(C(x1))))) 43.72/12.10 A^1(A(c(c(c(c(c(c(c(c(x1)))))))))) -> C^1(C(C(C(x1)))) 43.72/12.10 A^1(A(c(c(c(c(c(c(c(c(x1)))))))))) -> C^1(C(C(x1))) 43.72/12.10 A^1(A(c(c(c(c(c(c(c(c(x1)))))))))) -> C^1(C(x1)) 43.72/12.10 A^1(A(c(c(c(c(c(c(c(c(x1)))))))))) -> C^1(x1) 43.72/12.10 C^1(C(C(C(C(C(a(a(x1)))))))) -> B^1(B(x1)) 43.72/12.10 C^1(C(C(C(C(C(a(a(x1)))))))) -> B^1(x1) 43.72/12.10 43.72/12.10 43.72/12.10 Used ordering: Polynomial interpretation [POLO]: 43.72/12.10 43.72/12.10 POL(A(x_1)) = 3 + x_1 43.72/12.10 POL(A^1(x_1)) = 2 + 2*x_1 43.72/12.10 POL(B(x_1)) = 3 + x_1 43.72/12.10 POL(B^1(x_1)) = 2 + 2*x_1 43.72/12.10 POL(C(x_1)) = 3 + x_1 43.72/12.10 POL(C^1(x_1)) = 2 + 2*x_1 43.72/12.10 POL(a(x_1)) = 2 + x_1 43.72/12.10 POL(b(x_1)) = 2 + x_1 43.72/12.10 POL(c(x_1)) = 2 + x_1 43.72/12.10 43.72/12.10 43.72/12.10 ---------------------------------------- 43.72/12.10 43.72/12.10 (8) 43.72/12.10 Obligation: 43.72/12.10 Q DP problem: 43.72/12.10 P is empty. 43.72/12.10 The TRS R consists of the following rules: 43.72/12.10 43.72/12.10 B(B(a(a(a(a(a(a(a(a(x1)))))))))) -> c(c(A(A(A(A(A(A(x1)))))))) 43.72/12.10 A(A(A(A(A(A(b(b(x1)))))))) -> a(a(a(a(a(a(a(a(C(C(x1)))))))))) 43.72/12.10 C(C(b(b(b(b(b(b(b(b(x1)))))))))) -> a(a(B(B(B(B(B(B(x1)))))))) 43.72/12.10 B(B(B(B(B(B(c(c(x1)))))))) -> b(b(b(b(b(b(b(b(A(A(x1)))))))))) 43.72/12.10 A(A(c(c(c(c(c(c(c(c(x1)))))))))) -> b(b(C(C(C(C(C(C(x1)))))))) 43.72/12.10 C(C(C(C(C(C(a(a(x1)))))))) -> c(c(c(c(c(c(c(c(B(B(x1)))))))))) 43.72/12.10 43.72/12.10 The set Q consists of the following terms: 43.72/12.10 43.72/12.10 B(B(a(a(a(a(a(a(a(a(x0)))))))))) 43.72/12.10 A(A(A(A(A(A(b(b(x0)))))))) 43.72/12.10 C(C(b(b(b(b(b(b(b(b(x0)))))))))) 43.72/12.10 B(B(B(B(B(B(c(c(x0)))))))) 43.72/12.10 A(A(c(c(c(c(c(c(c(c(x0)))))))))) 43.72/12.10 C(C(C(C(C(C(a(a(x0)))))))) 43.72/12.10 43.72/12.10 We have to consider all minimal (P,Q,R)-chains. 43.72/12.10 ---------------------------------------- 43.72/12.10 43.72/12.10 (9) PisEmptyProof (EQUIVALENT) 43.72/12.10 The TRS P is empty. Hence, there is no (P,Q,R) chain. 43.72/12.10 ---------------------------------------- 43.72/12.10 43.72/12.10 (10) 43.72/12.10 YES 43.72/12.18 EOF