25.46/7.37 YES 25.74/7.44 proof of /export/starexec/sandbox2/benchmark/theBenchmark.xml 25.74/7.44 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 25.74/7.44 25.74/7.44 25.74/7.44 Termination w.r.t. Q of the given QTRS could be proven: 25.74/7.44 25.74/7.44 (0) QTRS 25.74/7.44 (1) DependencyPairsProof [EQUIVALENT, 11 ms] 25.74/7.44 (2) QDP 25.74/7.44 (3) DependencyGraphProof [EQUIVALENT, 0 ms] 25.74/7.44 (4) AND 25.74/7.44 (5) QDP 25.74/7.44 (6) UsableRulesProof [EQUIVALENT, 11 ms] 25.74/7.44 (7) QDP 25.74/7.44 (8) MRRProof [EQUIVALENT, 51 ms] 25.74/7.44 (9) QDP 25.74/7.44 (10) DependencyGraphProof [EQUIVALENT, 0 ms] 25.74/7.44 (11) QDP 25.74/7.44 (12) QDPOrderProof [EQUIVALENT, 1 ms] 25.74/7.44 (13) QDP 25.74/7.44 (14) DependencyGraphProof [EQUIVALENT, 0 ms] 25.74/7.44 (15) TRUE 25.74/7.44 (16) QDP 25.74/7.44 (17) UsableRulesProof [EQUIVALENT, 1 ms] 25.74/7.44 (18) QDP 25.74/7.44 (19) QDPOrderProof [EQUIVALENT, 64 ms] 25.74/7.44 (20) QDP 25.74/7.44 (21) PisEmptyProof [EQUIVALENT, 0 ms] 25.74/7.44 (22) YES 25.74/7.44 25.74/7.44 25.74/7.44 ---------------------------------------- 25.74/7.44 25.74/7.44 (0) 25.74/7.44 Obligation: 25.74/7.44 Q restricted rewrite system: 25.74/7.44 The TRS R consists of the following rules: 25.74/7.44 25.74/7.44 b(a(a(x1))) -> a(b(c(x1))) 25.74/7.44 c(a(x1)) -> a(c(x1)) 25.74/7.44 b(c(a(x1))) -> a(b(c(x1))) 25.74/7.44 c(b(x1)) -> d(x1) 25.74/7.44 a(d(x1)) -> d(a(x1)) 25.74/7.44 d(x1) -> b(a(x1)) 25.74/7.44 L(a(a(x1))) -> L(a(b(c(x1)))) 25.74/7.44 c(R(x1)) -> c(b(R(x1))) 25.74/7.44 25.74/7.44 Q is empty. 25.74/7.44 25.74/7.44 ---------------------------------------- 25.74/7.44 25.74/7.44 (1) DependencyPairsProof (EQUIVALENT) 25.74/7.44 Using Dependency Pairs [AG00,LPAR04] we result in the following initial DP problem. 25.74/7.44 ---------------------------------------- 25.74/7.44 25.74/7.44 (2) 25.74/7.44 Obligation: 25.74/7.44 Q DP problem: 25.74/7.44 The TRS P consists of the following rules: 25.74/7.44 25.74/7.44 B(a(a(x1))) -> A(b(c(x1))) 25.74/7.44 B(a(a(x1))) -> B(c(x1)) 25.74/7.44 B(a(a(x1))) -> C(x1) 25.74/7.44 C(a(x1)) -> A(c(x1)) 25.74/7.44 C(a(x1)) -> C(x1) 25.74/7.44 B(c(a(x1))) -> A(b(c(x1))) 25.74/7.44 B(c(a(x1))) -> B(c(x1)) 25.74/7.44 B(c(a(x1))) -> C(x1) 25.74/7.44 C(b(x1)) -> D(x1) 25.74/7.44 A(d(x1)) -> D(a(x1)) 25.74/7.44 A(d(x1)) -> A(x1) 25.74/7.44 D(x1) -> B(a(x1)) 25.74/7.44 D(x1) -> A(x1) 25.74/7.44 L^1(a(a(x1))) -> L^1(a(b(c(x1)))) 25.74/7.44 L^1(a(a(x1))) -> A(b(c(x1))) 25.74/7.44 L^1(a(a(x1))) -> B(c(x1)) 25.74/7.44 L^1(a(a(x1))) -> C(x1) 25.74/7.44 C(R(x1)) -> C(b(R(x1))) 25.74/7.44 C(R(x1)) -> B(R(x1)) 25.74/7.44 25.74/7.44 The TRS R consists of the following rules: 25.74/7.44 25.74/7.44 b(a(a(x1))) -> a(b(c(x1))) 25.74/7.45 c(a(x1)) -> a(c(x1)) 25.74/7.45 b(c(a(x1))) -> a(b(c(x1))) 25.74/7.45 c(b(x1)) -> d(x1) 25.74/7.45 a(d(x1)) -> d(a(x1)) 25.74/7.45 d(x1) -> b(a(x1)) 25.74/7.45 L(a(a(x1))) -> L(a(b(c(x1)))) 25.74/7.45 c(R(x1)) -> c(b(R(x1))) 25.74/7.45 25.74/7.45 Q is empty. 25.74/7.45 We have to consider all minimal (P,Q,R)-chains. 25.74/7.45 ---------------------------------------- 25.74/7.45 25.74/7.45 (3) DependencyGraphProof (EQUIVALENT) 25.74/7.45 The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 2 SCCs with 4 less nodes. 25.74/7.45 ---------------------------------------- 25.74/7.45 25.74/7.45 (4) 25.74/7.45 Complex Obligation (AND) 25.74/7.45 25.74/7.45 ---------------------------------------- 25.74/7.45 25.74/7.45 (5) 25.74/7.45 Obligation: 25.74/7.45 Q DP problem: 25.74/7.45 The TRS P consists of the following rules: 25.74/7.45 25.74/7.45 A(d(x1)) -> D(a(x1)) 25.74/7.45 D(x1) -> B(a(x1)) 25.74/7.45 B(a(a(x1))) -> A(b(c(x1))) 25.74/7.45 A(d(x1)) -> A(x1) 25.74/7.45 B(a(a(x1))) -> B(c(x1)) 25.74/7.45 B(a(a(x1))) -> C(x1) 25.74/7.45 C(a(x1)) -> A(c(x1)) 25.74/7.45 C(a(x1)) -> C(x1) 25.74/7.45 C(b(x1)) -> D(x1) 25.74/7.45 D(x1) -> A(x1) 25.74/7.45 C(R(x1)) -> C(b(R(x1))) 25.74/7.45 B(c(a(x1))) -> A(b(c(x1))) 25.74/7.45 B(c(a(x1))) -> B(c(x1)) 25.74/7.45 B(c(a(x1))) -> C(x1) 25.74/7.45 25.74/7.45 The TRS R consists of the following rules: 25.74/7.45 25.74/7.45 b(a(a(x1))) -> a(b(c(x1))) 25.74/7.45 c(a(x1)) -> a(c(x1)) 25.74/7.45 b(c(a(x1))) -> a(b(c(x1))) 25.74/7.45 c(b(x1)) -> d(x1) 25.74/7.45 a(d(x1)) -> d(a(x1)) 25.74/7.45 d(x1) -> b(a(x1)) 25.74/7.45 L(a(a(x1))) -> L(a(b(c(x1)))) 25.74/7.45 c(R(x1)) -> c(b(R(x1))) 25.74/7.45 25.74/7.45 Q is empty. 25.74/7.45 We have to consider all minimal (P,Q,R)-chains. 25.74/7.45 ---------------------------------------- 25.74/7.45 25.74/7.45 (6) UsableRulesProof (EQUIVALENT) 25.74/7.45 We can use the usable rules and reduction pair processor [LPAR04] with the Ce-compatible extension of the polynomial order that maps every function symbol to the sum of its arguments. Then, we can delete all non-usable rules [FROCOS05] from R. 25.74/7.45 ---------------------------------------- 25.74/7.45 25.74/7.45 (7) 25.74/7.45 Obligation: 25.74/7.45 Q DP problem: 25.74/7.45 The TRS P consists of the following rules: 25.74/7.45 25.74/7.45 A(d(x1)) -> D(a(x1)) 25.74/7.45 D(x1) -> B(a(x1)) 25.74/7.45 B(a(a(x1))) -> A(b(c(x1))) 25.74/7.45 A(d(x1)) -> A(x1) 25.74/7.45 B(a(a(x1))) -> B(c(x1)) 25.74/7.45 B(a(a(x1))) -> C(x1) 25.74/7.45 C(a(x1)) -> A(c(x1)) 25.74/7.45 C(a(x1)) -> C(x1) 25.74/7.45 C(b(x1)) -> D(x1) 25.74/7.45 D(x1) -> A(x1) 25.74/7.45 C(R(x1)) -> C(b(R(x1))) 25.74/7.45 B(c(a(x1))) -> A(b(c(x1))) 25.74/7.45 B(c(a(x1))) -> B(c(x1)) 25.74/7.45 B(c(a(x1))) -> C(x1) 25.74/7.45 25.74/7.45 The TRS R consists of the following rules: 25.74/7.45 25.74/7.45 c(a(x1)) -> a(c(x1)) 25.74/7.45 c(b(x1)) -> d(x1) 25.74/7.45 c(R(x1)) -> c(b(R(x1))) 25.74/7.45 a(d(x1)) -> d(a(x1)) 25.74/7.45 d(x1) -> b(a(x1)) 25.74/7.45 b(a(a(x1))) -> a(b(c(x1))) 25.74/7.45 b(c(a(x1))) -> a(b(c(x1))) 25.74/7.45 25.74/7.45 Q is empty. 25.74/7.45 We have to consider all minimal (P,Q,R)-chains. 25.74/7.45 ---------------------------------------- 25.74/7.45 25.74/7.45 (8) MRRProof (EQUIVALENT) 25.74/7.45 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. 25.74/7.45 25.74/7.45 Strictly oriented dependency pairs: 25.74/7.45 25.74/7.45 A(d(x1)) -> A(x1) 25.74/7.45 B(a(a(x1))) -> B(c(x1)) 25.74/7.45 B(a(a(x1))) -> C(x1) 25.74/7.45 C(a(x1)) -> A(c(x1)) 25.74/7.45 C(a(x1)) -> C(x1) 25.74/7.45 C(b(x1)) -> D(x1) 25.74/7.45 B(c(a(x1))) -> B(c(x1)) 25.74/7.45 B(c(a(x1))) -> C(x1) 25.74/7.45 25.74/7.45 25.74/7.45 Used ordering: Polynomial interpretation [POLO]: 25.74/7.45 25.74/7.45 POL(A(x_1)) = 1 + 2*x_1 25.74/7.45 POL(B(x_1)) = x_1 25.74/7.45 POL(C(x_1)) = 2 + 2*x_1 25.74/7.45 POL(D(x_1)) = 1 + 2*x_1 25.74/7.45 POL(R(x_1)) = 2*x_1 25.74/7.45 POL(a(x_1)) = 1 + 2*x_1 25.74/7.45 POL(b(x_1)) = x_1 25.74/7.45 POL(c(x_1)) = 1 + 2*x_1 25.74/7.45 POL(d(x_1)) = 1 + 2*x_1 25.74/7.45 25.74/7.45 25.74/7.45 ---------------------------------------- 25.74/7.45 25.74/7.45 (9) 25.74/7.45 Obligation: 25.74/7.45 Q DP problem: 25.74/7.45 The TRS P consists of the following rules: 25.74/7.45 25.74/7.45 A(d(x1)) -> D(a(x1)) 25.74/7.45 D(x1) -> B(a(x1)) 25.74/7.45 B(a(a(x1))) -> A(b(c(x1))) 25.74/7.45 D(x1) -> A(x1) 25.74/7.45 C(R(x1)) -> C(b(R(x1))) 25.74/7.45 B(c(a(x1))) -> A(b(c(x1))) 25.74/7.45 25.74/7.45 The TRS R consists of the following rules: 25.74/7.45 25.74/7.45 c(a(x1)) -> a(c(x1)) 25.74/7.45 c(b(x1)) -> d(x1) 25.74/7.45 c(R(x1)) -> c(b(R(x1))) 25.74/7.45 a(d(x1)) -> d(a(x1)) 25.74/7.45 d(x1) -> b(a(x1)) 25.74/7.45 b(a(a(x1))) -> a(b(c(x1))) 25.74/7.45 b(c(a(x1))) -> a(b(c(x1))) 25.74/7.45 25.74/7.45 Q is empty. 25.74/7.45 We have to consider all minimal (P,Q,R)-chains. 25.74/7.45 ---------------------------------------- 25.74/7.45 25.74/7.45 (10) DependencyGraphProof (EQUIVALENT) 25.74/7.45 The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 1 less node. 25.74/7.45 ---------------------------------------- 25.74/7.45 25.74/7.45 (11) 25.74/7.45 Obligation: 25.74/7.45 Q DP problem: 25.74/7.45 The TRS P consists of the following rules: 25.74/7.45 25.74/7.45 D(x1) -> B(a(x1)) 25.74/7.45 B(a(a(x1))) -> A(b(c(x1))) 25.74/7.45 A(d(x1)) -> D(a(x1)) 25.74/7.45 D(x1) -> A(x1) 25.74/7.45 B(c(a(x1))) -> A(b(c(x1))) 25.74/7.45 25.74/7.45 The TRS R consists of the following rules: 25.74/7.45 25.74/7.45 c(a(x1)) -> a(c(x1)) 25.74/7.45 c(b(x1)) -> d(x1) 25.74/7.45 c(R(x1)) -> c(b(R(x1))) 25.74/7.45 a(d(x1)) -> d(a(x1)) 25.74/7.45 d(x1) -> b(a(x1)) 25.74/7.45 b(a(a(x1))) -> a(b(c(x1))) 25.74/7.45 b(c(a(x1))) -> a(b(c(x1))) 25.74/7.45 25.74/7.45 Q is empty. 25.74/7.45 We have to consider all minimal (P,Q,R)-chains. 25.74/7.45 ---------------------------------------- 25.74/7.45 25.74/7.45 (12) QDPOrderProof (EQUIVALENT) 25.74/7.45 We use the reduction pair processor [LPAR04,JAR06]. 25.74/7.45 25.74/7.45 25.74/7.45 The following pairs can be oriented strictly and are deleted. 25.74/7.45 25.74/7.45 A(d(x1)) -> D(a(x1)) 25.74/7.45 The remaining pairs can at least be oriented weakly. 25.74/7.45 Used ordering: Polynomial interpretation [POLO]: 25.74/7.45 25.74/7.45 POL(A(x_1)) = x_1 25.74/7.45 POL(B(x_1)) = 0 25.74/7.45 POL(D(x_1)) = x_1 25.74/7.45 POL(R(x_1)) = 1 + x_1 25.74/7.45 POL(a(x_1)) = x_1 25.74/7.45 POL(b(x_1)) = 0 25.74/7.45 POL(c(x_1)) = 0 25.74/7.45 POL(d(x_1)) = 1 + x_1 25.74/7.45 25.74/7.45 The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: 25.74/7.45 25.74/7.45 d(x1) -> b(a(x1)) 25.74/7.45 b(a(a(x1))) -> a(b(c(x1))) 25.74/7.45 a(d(x1)) -> d(a(x1)) 25.74/7.45 b(c(a(x1))) -> a(b(c(x1))) 25.74/7.45 25.74/7.45 25.74/7.45 ---------------------------------------- 25.74/7.45 25.74/7.45 (13) 25.74/7.45 Obligation: 25.74/7.45 Q DP problem: 25.74/7.45 The TRS P consists of the following rules: 25.74/7.45 25.74/7.45 D(x1) -> B(a(x1)) 25.74/7.45 B(a(a(x1))) -> A(b(c(x1))) 25.74/7.45 D(x1) -> A(x1) 25.74/7.45 B(c(a(x1))) -> A(b(c(x1))) 25.74/7.45 25.74/7.45 The TRS R consists of the following rules: 25.74/7.45 25.74/7.45 c(a(x1)) -> a(c(x1)) 25.74/7.45 c(b(x1)) -> d(x1) 25.74/7.45 c(R(x1)) -> c(b(R(x1))) 25.74/7.45 a(d(x1)) -> d(a(x1)) 25.74/7.45 d(x1) -> b(a(x1)) 25.74/7.45 b(a(a(x1))) -> a(b(c(x1))) 25.74/7.45 b(c(a(x1))) -> a(b(c(x1))) 25.74/7.45 25.74/7.45 Q is empty. 25.74/7.45 We have to consider all minimal (P,Q,R)-chains. 25.74/7.45 ---------------------------------------- 25.74/7.45 25.74/7.45 (14) DependencyGraphProof (EQUIVALENT) 25.74/7.45 The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 0 SCCs with 4 less nodes. 25.74/7.45 ---------------------------------------- 25.74/7.45 25.74/7.45 (15) 25.74/7.45 TRUE 25.74/7.45 25.74/7.45 ---------------------------------------- 25.74/7.45 25.74/7.45 (16) 25.74/7.45 Obligation: 25.74/7.45 Q DP problem: 25.74/7.45 The TRS P consists of the following rules: 25.74/7.45 25.74/7.45 L^1(a(a(x1))) -> L^1(a(b(c(x1)))) 25.74/7.45 25.74/7.45 The TRS R consists of the following rules: 25.74/7.45 25.74/7.45 b(a(a(x1))) -> a(b(c(x1))) 25.74/7.45 c(a(x1)) -> a(c(x1)) 25.74/7.45 b(c(a(x1))) -> a(b(c(x1))) 25.74/7.45 c(b(x1)) -> d(x1) 25.74/7.45 a(d(x1)) -> d(a(x1)) 25.74/7.45 d(x1) -> b(a(x1)) 25.79/7.45 L(a(a(x1))) -> L(a(b(c(x1)))) 25.79/7.45 c(R(x1)) -> c(b(R(x1))) 25.79/7.45 25.79/7.45 Q is empty. 25.79/7.45 We have to consider all minimal (P,Q,R)-chains. 25.79/7.45 ---------------------------------------- 25.79/7.45 25.79/7.45 (17) UsableRulesProof (EQUIVALENT) 25.79/7.45 We can use the usable rules and reduction pair processor [LPAR04] with the Ce-compatible extension of the polynomial order that maps every function symbol to the sum of its arguments. Then, we can delete all non-usable rules [FROCOS05] from R. 25.79/7.45 ---------------------------------------- 25.79/7.45 25.79/7.45 (18) 25.79/7.45 Obligation: 25.79/7.45 Q DP problem: 25.79/7.45 The TRS P consists of the following rules: 25.79/7.45 25.79/7.45 L^1(a(a(x1))) -> L^1(a(b(c(x1)))) 25.79/7.45 25.79/7.45 The TRS R consists of the following rules: 25.79/7.45 25.79/7.45 c(a(x1)) -> a(c(x1)) 25.79/7.45 c(b(x1)) -> d(x1) 25.79/7.45 c(R(x1)) -> c(b(R(x1))) 25.79/7.45 a(d(x1)) -> d(a(x1)) 25.79/7.45 d(x1) -> b(a(x1)) 25.79/7.45 b(a(a(x1))) -> a(b(c(x1))) 25.79/7.45 b(c(a(x1))) -> a(b(c(x1))) 25.79/7.45 25.79/7.45 Q is empty. 25.79/7.45 We have to consider all minimal (P,Q,R)-chains. 25.79/7.45 ---------------------------------------- 25.79/7.45 25.79/7.45 (19) QDPOrderProof (EQUIVALENT) 25.79/7.45 We use the reduction pair processor [LPAR04,JAR06]. 25.79/7.45 25.79/7.45 25.79/7.45 The following pairs can be oriented strictly and are deleted. 25.79/7.45 25.79/7.45 L^1(a(a(x1))) -> L^1(a(b(c(x1)))) 25.79/7.45 The remaining pairs can at least be oriented weakly. 25.79/7.45 Used ordering: Polynomial Order [NEGPOLO,POLO] with Interpretation: 25.79/7.45 25.79/7.45 POL( L^1_1(x_1) ) = max{0, x_1 - 2} 25.79/7.45 POL( a_1(x_1) ) = x_1 + 2 25.79/7.45 POL( b_1(x_1) ) = max{0, x_1 - 2} 25.79/7.45 POL( c_1(x_1) ) = x_1 + 2 25.79/7.45 POL( d_1(x_1) ) = x_1 25.79/7.45 POL( R_1(x_1) ) = 0 25.79/7.45 25.79/7.45 The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: 25.79/7.45 25.79/7.45 c(a(x1)) -> a(c(x1)) 25.79/7.45 c(b(x1)) -> d(x1) 25.79/7.45 c(R(x1)) -> c(b(R(x1))) 25.79/7.45 d(x1) -> b(a(x1)) 25.79/7.45 b(a(a(x1))) -> a(b(c(x1))) 25.79/7.45 a(d(x1)) -> d(a(x1)) 25.79/7.45 b(c(a(x1))) -> a(b(c(x1))) 25.79/7.45 25.79/7.45 25.79/7.45 ---------------------------------------- 25.79/7.45 25.79/7.45 (20) 25.79/7.45 Obligation: 25.79/7.45 Q DP problem: 25.79/7.45 P is empty. 25.79/7.45 The TRS R consists of the following rules: 25.79/7.45 25.79/7.45 c(a(x1)) -> a(c(x1)) 25.79/7.45 c(b(x1)) -> d(x1) 25.79/7.45 c(R(x1)) -> c(b(R(x1))) 25.79/7.45 a(d(x1)) -> d(a(x1)) 25.79/7.45 d(x1) -> b(a(x1)) 25.79/7.45 b(a(a(x1))) -> a(b(c(x1))) 25.79/7.45 b(c(a(x1))) -> a(b(c(x1))) 25.79/7.45 25.79/7.45 Q is empty. 25.79/7.45 We have to consider all minimal (P,Q,R)-chains. 25.79/7.45 ---------------------------------------- 25.79/7.45 25.79/7.45 (21) PisEmptyProof (EQUIVALENT) 25.79/7.45 The TRS P is empty. Hence, there is no (P,Q,R) chain. 25.79/7.45 ---------------------------------------- 25.79/7.45 25.79/7.45 (22) 25.79/7.45 YES 26.00/7.54 EOF