31.69/8.98 YES 33.19/9.36 proof of /export/starexec/sandbox/benchmark/theBenchmark.xml 33.19/9.36 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 33.19/9.36 33.19/9.36 33.19/9.36 Termination w.r.t. Q of the given QTRS could be proven: 33.19/9.36 33.19/9.36 (0) QTRS 33.19/9.36 (1) QTRSRRRProof [EQUIVALENT, 52 ms] 33.19/9.36 (2) QTRS 33.19/9.36 (3) QTRSRRRProof [EQUIVALENT, 2 ms] 33.19/9.36 (4) QTRS 33.19/9.36 (5) QTRSRRRProof [EQUIVALENT, 2 ms] 33.19/9.36 (6) QTRS 33.19/9.36 (7) DependencyPairsProof [EQUIVALENT, 21 ms] 33.19/9.36 (8) QDP 33.19/9.36 (9) QDPOrderProof [EQUIVALENT, 139 ms] 33.19/9.36 (10) QDP 33.19/9.36 (11) DependencyGraphProof [EQUIVALENT, 0 ms] 33.19/9.36 (12) AND 33.19/9.36 (13) QDP 33.19/9.36 (14) QDPOrderProof [EQUIVALENT, 0 ms] 33.19/9.36 (15) QDP 33.19/9.36 (16) DependencyGraphProof [EQUIVALENT, 0 ms] 33.19/9.36 (17) TRUE 33.19/9.36 (18) QDP 33.19/9.36 (19) MRRProof [EQUIVALENT, 0 ms] 33.19/9.36 (20) QDP 33.19/9.36 (21) DependencyGraphProof [EQUIVALENT, 0 ms] 33.19/9.36 (22) TRUE 33.19/9.36 33.19/9.36 33.19/9.36 ---------------------------------------- 33.19/9.36 33.19/9.36 (0) 33.19/9.36 Obligation: 33.19/9.36 Q restricted rewrite system: 33.19/9.36 The TRS R consists of the following rules: 33.19/9.36 33.19/9.36 a(b(c(x1))) -> c(b(a(x1))) 33.19/9.36 C(B(A(x1))) -> A(B(C(x1))) 33.19/9.36 b(a(C(x1))) -> C(a(b(x1))) 33.19/9.36 c(A(B(x1))) -> B(A(c(x1))) 33.19/9.36 A(c(b(x1))) -> b(c(A(x1))) 33.19/9.36 B(C(a(x1))) -> a(C(B(x1))) 33.19/9.36 a(A(x1)) -> x1 33.19/9.36 A(a(x1)) -> x1 33.19/9.36 b(B(x1)) -> x1 33.19/9.36 B(b(x1)) -> x1 33.19/9.36 c(C(x1)) -> x1 33.19/9.36 C(c(x1)) -> x1 33.19/9.36 33.19/9.36 Q is empty. 33.19/9.36 33.19/9.36 ---------------------------------------- 33.19/9.36 33.19/9.36 (1) QTRSRRRProof (EQUIVALENT) 33.19/9.36 Used ordering: 33.19/9.36 Polynomial interpretation [POLO]: 33.19/9.36 33.19/9.36 POL(A(x_1)) = 1 + x_1 33.19/9.36 POL(B(x_1)) = x_1 33.19/9.36 POL(C(x_1)) = x_1 33.19/9.36 POL(a(x_1)) = x_1 33.19/9.36 POL(b(x_1)) = x_1 33.19/9.36 POL(c(x_1)) = x_1 33.19/9.36 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: 33.19/9.36 33.19/9.36 a(A(x1)) -> x1 33.19/9.36 A(a(x1)) -> x1 33.19/9.36 33.19/9.36 33.19/9.36 33.19/9.36 33.19/9.36 ---------------------------------------- 33.19/9.36 33.19/9.36 (2) 33.19/9.36 Obligation: 33.19/9.36 Q restricted rewrite system: 33.19/9.36 The TRS R consists of the following rules: 33.19/9.36 33.19/9.36 a(b(c(x1))) -> c(b(a(x1))) 33.19/9.36 C(B(A(x1))) -> A(B(C(x1))) 33.19/9.36 b(a(C(x1))) -> C(a(b(x1))) 33.19/9.36 c(A(B(x1))) -> B(A(c(x1))) 33.19/9.36 A(c(b(x1))) -> b(c(A(x1))) 33.19/9.36 B(C(a(x1))) -> a(C(B(x1))) 33.19/9.36 b(B(x1)) -> x1 33.19/9.36 B(b(x1)) -> x1 33.19/9.36 c(C(x1)) -> x1 33.19/9.36 C(c(x1)) -> x1 33.19/9.36 33.19/9.36 Q is empty. 33.19/9.36 33.19/9.36 ---------------------------------------- 33.19/9.36 33.19/9.36 (3) QTRSRRRProof (EQUIVALENT) 33.19/9.36 Used ordering: 33.19/9.36 Polynomial interpretation [POLO]: 33.19/9.36 33.19/9.36 POL(A(x_1)) = x_1 33.19/9.36 POL(B(x_1)) = 1 + x_1 33.19/9.36 POL(C(x_1)) = x_1 33.19/9.36 POL(a(x_1)) = x_1 33.19/9.36 POL(b(x_1)) = x_1 33.19/9.36 POL(c(x_1)) = x_1 33.19/9.36 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: 33.19/9.36 33.19/9.36 b(B(x1)) -> x1 33.19/9.36 B(b(x1)) -> x1 33.19/9.36 33.19/9.36 33.19/9.36 33.19/9.36 33.19/9.36 ---------------------------------------- 33.19/9.36 33.19/9.36 (4) 33.19/9.36 Obligation: 33.19/9.36 Q restricted rewrite system: 33.19/9.36 The TRS R consists of the following rules: 33.19/9.36 33.19/9.36 a(b(c(x1))) -> c(b(a(x1))) 33.19/9.36 C(B(A(x1))) -> A(B(C(x1))) 33.19/9.36 b(a(C(x1))) -> C(a(b(x1))) 33.19/9.36 c(A(B(x1))) -> B(A(c(x1))) 33.19/9.36 A(c(b(x1))) -> b(c(A(x1))) 33.19/9.36 B(C(a(x1))) -> a(C(B(x1))) 33.19/9.36 c(C(x1)) -> x1 33.19/9.36 C(c(x1)) -> x1 33.19/9.36 33.19/9.36 Q is empty. 33.19/9.36 33.19/9.36 ---------------------------------------- 33.19/9.36 33.19/9.36 (5) QTRSRRRProof (EQUIVALENT) 33.19/9.36 Used ordering: 33.19/9.36 Polynomial interpretation [POLO]: 33.19/9.36 33.19/9.36 POL(A(x_1)) = x_1 33.19/9.36 POL(B(x_1)) = x_1 33.19/9.36 POL(C(x_1)) = 1 + x_1 33.19/9.36 POL(a(x_1)) = x_1 33.19/9.36 POL(b(x_1)) = x_1 33.19/9.36 POL(c(x_1)) = x_1 33.19/9.36 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: 33.19/9.36 33.19/9.36 c(C(x1)) -> x1 33.19/9.36 C(c(x1)) -> x1 33.19/9.36 33.19/9.36 33.19/9.36 33.19/9.36 33.19/9.36 ---------------------------------------- 33.19/9.36 33.19/9.36 (6) 33.19/9.36 Obligation: 33.19/9.36 Q restricted rewrite system: 33.19/9.36 The TRS R consists of the following rules: 33.19/9.36 33.19/9.36 a(b(c(x1))) -> c(b(a(x1))) 33.19/9.36 C(B(A(x1))) -> A(B(C(x1))) 33.19/9.36 b(a(C(x1))) -> C(a(b(x1))) 33.19/9.36 c(A(B(x1))) -> B(A(c(x1))) 33.19/9.36 A(c(b(x1))) -> b(c(A(x1))) 33.19/9.36 B(C(a(x1))) -> a(C(B(x1))) 33.19/9.36 33.19/9.36 Q is empty. 33.19/9.36 33.19/9.36 ---------------------------------------- 33.19/9.36 33.19/9.36 (7) DependencyPairsProof (EQUIVALENT) 33.19/9.36 Using Dependency Pairs [AG00,LPAR04] we result in the following initial DP problem. 33.19/9.36 ---------------------------------------- 33.19/9.36 33.19/9.36 (8) 33.19/9.36 Obligation: 33.19/9.36 Q DP problem: 33.19/9.36 The TRS P consists of the following rules: 33.19/9.36 33.19/9.36 A^1(b(c(x1))) -> C^1(b(a(x1))) 33.19/9.36 A^1(b(c(x1))) -> B^1(a(x1)) 33.19/9.36 A^1(b(c(x1))) -> A^1(x1) 33.19/9.36 C^2(B(A(x1))) -> A^2(B(C(x1))) 33.19/9.36 C^2(B(A(x1))) -> B^2(C(x1)) 33.19/9.36 C^2(B(A(x1))) -> C^2(x1) 33.19/9.36 B^1(a(C(x1))) -> C^2(a(b(x1))) 33.19/9.36 B^1(a(C(x1))) -> A^1(b(x1)) 33.19/9.36 B^1(a(C(x1))) -> B^1(x1) 33.19/9.36 C^1(A(B(x1))) -> B^2(A(c(x1))) 33.19/9.36 C^1(A(B(x1))) -> A^2(c(x1)) 33.19/9.36 C^1(A(B(x1))) -> C^1(x1) 33.19/9.36 A^2(c(b(x1))) -> B^1(c(A(x1))) 33.19/9.36 A^2(c(b(x1))) -> C^1(A(x1)) 33.19/9.36 A^2(c(b(x1))) -> A^2(x1) 33.19/9.36 B^2(C(a(x1))) -> A^1(C(B(x1))) 33.19/9.36 B^2(C(a(x1))) -> C^2(B(x1)) 33.19/9.36 B^2(C(a(x1))) -> B^2(x1) 33.19/9.36 33.19/9.36 The TRS R consists of the following rules: 33.19/9.36 33.19/9.36 a(b(c(x1))) -> c(b(a(x1))) 33.19/9.36 C(B(A(x1))) -> A(B(C(x1))) 33.19/9.36 b(a(C(x1))) -> C(a(b(x1))) 33.19/9.36 c(A(B(x1))) -> B(A(c(x1))) 33.19/9.36 A(c(b(x1))) -> b(c(A(x1))) 33.19/9.36 B(C(a(x1))) -> a(C(B(x1))) 33.19/9.36 33.19/9.36 Q is empty. 33.19/9.36 We have to consider all minimal (P,Q,R)-chains. 33.19/9.36 ---------------------------------------- 33.19/9.36 33.19/9.36 (9) QDPOrderProof (EQUIVALENT) 33.19/9.36 We use the reduction pair processor [LPAR04,JAR06]. 33.19/9.36 33.19/9.36 33.19/9.36 The following pairs can be oriented strictly and are deleted. 33.19/9.36 33.19/9.36 A^1(b(c(x1))) -> B^1(a(x1)) 33.19/9.36 A^1(b(c(x1))) -> A^1(x1) 33.19/9.36 C^2(B(A(x1))) -> B^2(C(x1)) 33.19/9.36 C^2(B(A(x1))) -> C^2(x1) 33.19/9.36 B^1(a(C(x1))) -> A^1(b(x1)) 33.19/9.36 B^1(a(C(x1))) -> B^1(x1) 33.19/9.36 C^1(A(B(x1))) -> A^2(c(x1)) 33.19/9.36 C^1(A(B(x1))) -> C^1(x1) 33.19/9.36 A^2(c(b(x1))) -> C^1(A(x1)) 33.19/9.36 A^2(c(b(x1))) -> A^2(x1) 33.19/9.36 B^2(C(a(x1))) -> C^2(B(x1)) 33.19/9.36 B^2(C(a(x1))) -> B^2(x1) 33.19/9.36 The remaining pairs can at least be oriented weakly. 33.19/9.36 Used ordering: Polynomial Order [NEGPOLO,POLO] with Interpretation: 33.19/9.36 33.19/9.36 POL( A^2_1(x_1) ) = 2x_1 33.19/9.36 POL( B^1_1(x_1) ) = 2x_1 33.19/9.36 POL( C^2_1(x_1) ) = 2x_1 33.19/9.36 POL( A_1(x_1) ) = 2x_1 + 2 33.19/9.36 POL( A^1_1(x_1) ) = 2x_1 + 2 33.19/9.36 POL( B^2_1(x_1) ) = 2x_1 + 2 33.19/9.36 POL( C^1_1(x_1) ) = 2x_1 + 2 33.19/9.36 POL( C_1(x_1) ) = 2x_1 + 2 33.19/9.36 POL( b_1(x_1) ) = 2x_1 + 2 33.19/9.36 POL( c_1(x_1) ) = 2x_1 33.19/9.36 POL( B_1(x_1) ) = 2x_1 33.19/9.36 POL( a_1(x_1) ) = 2x_1 33.19/9.36 33.19/9.36 The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: 33.19/9.36 33.19/9.36 c(A(B(x1))) -> B(A(c(x1))) 33.19/9.36 B(C(a(x1))) -> a(C(B(x1))) 33.19/9.36 a(b(c(x1))) -> c(b(a(x1))) 33.19/9.36 A(c(b(x1))) -> b(c(A(x1))) 33.19/9.36 b(a(C(x1))) -> C(a(b(x1))) 33.19/9.36 C(B(A(x1))) -> A(B(C(x1))) 33.19/9.36 33.19/9.36 33.19/9.36 ---------------------------------------- 33.19/9.36 33.19/9.36 (10) 33.19/9.36 Obligation: 33.19/9.36 Q DP problem: 33.19/9.36 The TRS P consists of the following rules: 33.19/9.36 33.19/9.36 A^1(b(c(x1))) -> C^1(b(a(x1))) 33.19/9.36 C^2(B(A(x1))) -> A^2(B(C(x1))) 33.19/9.36 B^1(a(C(x1))) -> C^2(a(b(x1))) 33.19/9.36 C^1(A(B(x1))) -> B^2(A(c(x1))) 33.19/9.36 A^2(c(b(x1))) -> B^1(c(A(x1))) 33.19/9.36 B^2(C(a(x1))) -> A^1(C(B(x1))) 33.19/9.36 33.19/9.36 The TRS R consists of the following rules: 33.19/9.36 33.19/9.36 a(b(c(x1))) -> c(b(a(x1))) 33.19/9.36 C(B(A(x1))) -> A(B(C(x1))) 33.19/9.36 b(a(C(x1))) -> C(a(b(x1))) 33.19/9.36 c(A(B(x1))) -> B(A(c(x1))) 33.19/9.36 A(c(b(x1))) -> b(c(A(x1))) 33.19/9.36 B(C(a(x1))) -> a(C(B(x1))) 33.19/9.36 33.19/9.36 Q is empty. 33.19/9.36 We have to consider all minimal (P,Q,R)-chains. 33.19/9.36 ---------------------------------------- 33.19/9.36 33.19/9.36 (11) DependencyGraphProof (EQUIVALENT) 33.19/9.36 The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 2 SCCs. 33.19/9.36 ---------------------------------------- 33.19/9.36 33.19/9.36 (12) 33.19/9.36 Complex Obligation (AND) 33.19/9.36 33.19/9.36 ---------------------------------------- 33.19/9.36 33.19/9.36 (13) 33.19/9.36 Obligation: 33.19/9.36 Q DP problem: 33.19/9.36 The TRS P consists of the following rules: 33.19/9.36 33.19/9.36 A^2(c(b(x1))) -> B^1(c(A(x1))) 33.19/9.36 B^1(a(C(x1))) -> C^2(a(b(x1))) 33.19/9.36 C^2(B(A(x1))) -> A^2(B(C(x1))) 33.19/9.36 33.19/9.36 The TRS R consists of the following rules: 33.19/9.36 33.19/9.36 a(b(c(x1))) -> c(b(a(x1))) 33.19/9.36 C(B(A(x1))) -> A(B(C(x1))) 33.19/9.36 b(a(C(x1))) -> C(a(b(x1))) 33.19/9.36 c(A(B(x1))) -> B(A(c(x1))) 33.19/9.36 A(c(b(x1))) -> b(c(A(x1))) 33.19/9.36 B(C(a(x1))) -> a(C(B(x1))) 33.19/9.36 33.19/9.36 Q is empty. 33.19/9.36 We have to consider all minimal (P,Q,R)-chains. 33.19/9.36 ---------------------------------------- 33.19/9.36 33.19/9.36 (14) QDPOrderProof (EQUIVALENT) 33.19/9.36 We use the reduction pair processor [LPAR04,JAR06]. 33.19/9.36 33.19/9.36 33.19/9.36 The following pairs can be oriented strictly and are deleted. 33.19/9.36 33.19/9.36 B^1(a(C(x1))) -> C^2(a(b(x1))) 33.19/9.36 The remaining pairs can at least be oriented weakly. 33.19/9.36 Used ordering: Polynomial interpretation [POLO]: 33.19/9.36 33.19/9.36 POL(A(x_1)) = 1 33.19/9.36 POL(A^2(x_1)) = 1 33.19/9.36 POL(B(x_1)) = 1 33.19/9.36 POL(B^1(x_1)) = 1 33.19/9.36 POL(C(x_1)) = x_1 33.19/9.36 POL(C^2(x_1)) = x_1 33.19/9.36 POL(a(x_1)) = 0 33.19/9.36 POL(b(x_1)) = 0 33.19/9.36 POL(c(x_1)) = x_1 33.19/9.36 33.19/9.36 The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: 33.19/9.36 33.19/9.36 A(c(b(x1))) -> b(c(A(x1))) 33.19/9.36 b(a(C(x1))) -> C(a(b(x1))) 33.19/9.36 C(B(A(x1))) -> A(B(C(x1))) 33.19/9.36 c(A(B(x1))) -> B(A(c(x1))) 33.19/9.36 B(C(a(x1))) -> a(C(B(x1))) 33.19/9.36 a(b(c(x1))) -> c(b(a(x1))) 33.19/9.36 33.19/9.36 33.19/9.36 ---------------------------------------- 33.19/9.36 33.19/9.36 (15) 33.19/9.36 Obligation: 33.19/9.36 Q DP problem: 33.19/9.36 The TRS P consists of the following rules: 33.19/9.36 33.19/9.36 A^2(c(b(x1))) -> B^1(c(A(x1))) 33.19/9.36 C^2(B(A(x1))) -> A^2(B(C(x1))) 33.19/9.36 33.19/9.36 The TRS R consists of the following rules: 33.19/9.36 33.19/9.36 a(b(c(x1))) -> c(b(a(x1))) 33.19/9.36 C(B(A(x1))) -> A(B(C(x1))) 33.19/9.36 b(a(C(x1))) -> C(a(b(x1))) 33.19/9.36 c(A(B(x1))) -> B(A(c(x1))) 33.19/9.36 A(c(b(x1))) -> b(c(A(x1))) 33.19/9.36 B(C(a(x1))) -> a(C(B(x1))) 33.19/9.36 33.19/9.36 Q is empty. 33.19/9.36 We have to consider all minimal (P,Q,R)-chains. 33.19/9.36 ---------------------------------------- 33.19/9.36 33.19/9.36 (16) DependencyGraphProof (EQUIVALENT) 33.19/9.36 The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 0 SCCs with 2 less nodes. 33.19/9.36 ---------------------------------------- 33.19/9.36 33.19/9.36 (17) 33.19/9.36 TRUE 33.19/9.36 33.19/9.36 ---------------------------------------- 33.19/9.36 33.19/9.36 (18) 33.19/9.36 Obligation: 33.19/9.36 Q DP problem: 33.19/9.36 The TRS P consists of the following rules: 33.19/9.36 33.19/9.36 C^1(A(B(x1))) -> B^2(A(c(x1))) 33.19/9.36 B^2(C(a(x1))) -> A^1(C(B(x1))) 33.19/9.36 A^1(b(c(x1))) -> C^1(b(a(x1))) 33.19/9.36 33.19/9.36 The TRS R consists of the following rules: 33.19/9.36 33.19/9.36 a(b(c(x1))) -> c(b(a(x1))) 33.19/9.36 C(B(A(x1))) -> A(B(C(x1))) 33.19/9.36 b(a(C(x1))) -> C(a(b(x1))) 33.19/9.36 c(A(B(x1))) -> B(A(c(x1))) 33.19/9.36 A(c(b(x1))) -> b(c(A(x1))) 33.19/9.36 B(C(a(x1))) -> a(C(B(x1))) 33.19/9.36 33.19/9.36 Q is empty. 33.19/9.36 We have to consider all minimal (P,Q,R)-chains. 33.19/9.36 ---------------------------------------- 33.19/9.36 33.19/9.36 (19) MRRProof (EQUIVALENT) 33.19/9.36 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. 33.19/9.36 33.19/9.36 Strictly oriented dependency pairs: 33.19/9.36 33.19/9.36 B^2(C(a(x1))) -> A^1(C(B(x1))) 33.19/9.36 33.19/9.36 Strictly oriented rules of the TRS R: 33.19/9.36 33.19/9.36 A(c(b(x1))) -> b(c(A(x1))) 33.19/9.36 B(C(a(x1))) -> a(C(B(x1))) 33.19/9.36 33.19/9.36 Used ordering: Polynomial interpretation [POLO]: 33.19/9.36 33.19/9.36 POL(A(x_1)) = 2*x_1 33.19/9.36 POL(A^1(x_1)) = 3 + 2*x_1 33.19/9.36 POL(B(x_1)) = 2*x_1 33.19/9.36 POL(B^2(x_1)) = 2 + 2*x_1 33.19/9.36 POL(C(x_1)) = x_1 33.19/9.36 POL(C^1(x_1)) = 2 + x_1 33.19/9.36 POL(a(x_1)) = 1 + 2*x_1 33.19/9.36 POL(b(x_1)) = 1 + 2*x_1 33.19/9.36 POL(c(x_1)) = x_1 33.19/9.36 33.19/9.36 33.19/9.36 ---------------------------------------- 33.19/9.36 33.19/9.36 (20) 33.19/9.36 Obligation: 33.19/9.36 Q DP problem: 33.19/9.36 The TRS P consists of the following rules: 33.19/9.36 33.19/9.36 C^1(A(B(x1))) -> B^2(A(c(x1))) 33.19/9.36 A^1(b(c(x1))) -> C^1(b(a(x1))) 33.19/9.36 33.19/9.36 The TRS R consists of the following rules: 33.19/9.36 33.19/9.36 a(b(c(x1))) -> c(b(a(x1))) 33.19/9.36 C(B(A(x1))) -> A(B(C(x1))) 33.19/9.36 b(a(C(x1))) -> C(a(b(x1))) 33.19/9.36 c(A(B(x1))) -> B(A(c(x1))) 33.19/9.36 33.19/9.36 Q is empty. 33.19/9.36 We have to consider all minimal (P,Q,R)-chains. 33.19/9.36 ---------------------------------------- 33.19/9.36 33.19/9.36 (21) DependencyGraphProof (EQUIVALENT) 33.19/9.36 The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 0 SCCs with 2 less nodes. 33.19/9.36 ---------------------------------------- 33.19/9.36 33.19/9.36 (22) 33.19/9.36 TRUE 33.64/9.57 EOF