5.15/2.16 YES 5.15/2.17 proof of /export/starexec/sandbox/benchmark/theBenchmark.xml 5.15/2.17 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 5.15/2.17 5.15/2.17 5.15/2.17 Quasi decreasingness of the given CTRS could be proven: 5.15/2.17 5.15/2.17 (0) CTRS 5.15/2.17 (1) CTRSToQTRSProof [SOUND, 0 ms] 5.15/2.17 (2) QTRS 5.15/2.17 (3) QTRSRRRProof [EQUIVALENT, 64 ms] 5.15/2.17 (4) QTRS 5.15/2.17 (5) QTRSRRRProof [EQUIVALENT, 0 ms] 5.15/2.17 (6) QTRS 5.15/2.17 (7) QTRSRRRProof [EQUIVALENT, 17 ms] 5.15/2.17 (8) QTRS 5.15/2.17 (9) QTRSRRRProof [EQUIVALENT, 19 ms] 5.15/2.17 (10) QTRS 5.15/2.17 (11) DependencyPairsProof [EQUIVALENT, 0 ms] 5.15/2.17 (12) QDP 5.15/2.17 (13) DependencyGraphProof [EQUIVALENT, 0 ms] 5.15/2.17 (14) AND 5.15/2.17 (15) QDP 5.15/2.17 (16) UsableRulesProof [EQUIVALENT, 0 ms] 5.15/2.17 (17) QDP 5.15/2.17 (18) QDPSizeChangeProof [EQUIVALENT, 0 ms] 5.15/2.17 (19) YES 5.15/2.17 (20) QDP 5.15/2.17 (21) UsableRulesReductionPairsProof [EQUIVALENT, 14 ms] 5.15/2.17 (22) QDP 5.15/2.17 (23) MRRProof [EQUIVALENT, 0 ms] 5.15/2.17 (24) QDP 5.15/2.17 (25) DependencyGraphProof [EQUIVALENT, 0 ms] 5.15/2.17 (26) TRUE 5.15/2.17 5.15/2.17 5.15/2.17 ---------------------------------------- 5.15/2.17 5.15/2.17 (0) 5.15/2.17 Obligation: 5.15/2.17 Conditional term rewrite system: 5.15/2.17 The TRS R consists of the following rules: 5.15/2.17 5.15/2.17 ssp'(xs, 0) -> nil 5.15/2.17 sub(z, 0) -> z 5.15/2.17 get(cons(y, ys)) -> tp2(y, ys) 5.15/2.17 5.15/2.17 The conditional TRS C consists of the following conditional rules: 5.15/2.17 5.15/2.17 ssp'(cons(y', ws), v) -> cons(y', ys') <= sub(v, y') -> w, ssp'(ws, w) -> ys' 5.15/2.17 ssp'(cons(x', xs'), v) -> cons(y', ys') <= get(xs') -> tp2(y', zs), sub(v, y') -> w, ssp'(cons(x', zs), w) -> ys' 5.15/2.17 sub(s(v), s(w)) -> z <= sub(v, w) -> z 5.15/2.17 get(cons(x', xs')) -> tp2(y, cons(x', zs)) <= get(xs') -> tp2(y, zs) 5.15/2.17 5.15/2.17 5.15/2.17 ---------------------------------------- 5.15/2.17 5.15/2.17 (1) CTRSToQTRSProof (SOUND) 5.15/2.17 The conditional rules have been transormed into unconditional rules according to [CTRS,AAECCNOC]. 5.15/2.17 ---------------------------------------- 5.15/2.17 5.15/2.17 (2) 5.15/2.17 Obligation: 5.15/2.17 Q restricted rewrite system: 5.15/2.17 The TRS R consists of the following rules: 5.15/2.17 5.15/2.17 ssp'(cons(y', ws), v) -> U1(sub(v, y'), y', ws) 5.15/2.17 U1(w, y', ws) -> U2(ssp'(ws, w), y') 5.15/2.17 U2(ys', y') -> cons(y', ys') 5.15/2.17 ssp'(cons(x', xs'), v) -> U3(get(xs'), x', v) 5.15/2.17 U3(tp2(y', zs), x', v) -> U4(sub(v, y'), x', y', zs) 5.15/2.17 U4(w, x', y', zs) -> U5(ssp'(cons(x', zs), w), y') 5.15/2.17 U5(ys', y') -> cons(y', ys') 5.15/2.17 sub(s(v), s(w)) -> U6(sub(v, w)) 5.15/2.17 U6(z) -> z 5.15/2.17 get(cons(x', xs')) -> U7(get(xs'), x') 5.15/2.17 U7(tp2(y, zs), x') -> tp2(y, cons(x', zs)) 5.15/2.17 ssp'(xs, 0) -> nil 5.15/2.17 sub(z, 0) -> z 5.15/2.17 get(cons(y, ys)) -> tp2(y, ys) 5.15/2.17 5.15/2.17 Q is empty. 5.15/2.17 5.15/2.17 ---------------------------------------- 5.15/2.17 5.15/2.17 (3) QTRSRRRProof (EQUIVALENT) 5.15/2.17 Used ordering: 5.15/2.17 Polynomial interpretation [POLO]: 5.15/2.17 5.15/2.17 POL(0) = 0 5.15/2.17 POL(U1(x_1, x_2, x_3)) = x_1 + x_2 + 2*x_3 5.15/2.17 POL(U2(x_1, x_2)) = x_1 + x_2 5.15/2.17 POL(U3(x_1, x_2, x_3)) = 2*x_1 + 2*x_2 + x_3 5.15/2.17 POL(U4(x_1, x_2, x_3, x_4)) = x_1 + 2*x_2 + x_3 + 2*x_4 5.15/2.17 POL(U5(x_1, x_2)) = x_1 + x_2 5.15/2.17 POL(U6(x_1)) = 2*x_1 5.15/2.17 POL(U7(x_1, x_2)) = x_1 + x_2 5.15/2.17 POL(cons(x_1, x_2)) = x_1 + x_2 5.15/2.17 POL(get(x_1)) = x_1 5.15/2.17 POL(nil) = 0 5.15/2.17 POL(s(x_1)) = 1 + 2*x_1 5.15/2.17 POL(ssp'(x_1, x_2)) = 2*x_1 + x_2 5.15/2.17 POL(sub(x_1, x_2)) = x_1 + x_2 5.15/2.17 POL(tp2(x_1, x_2)) = x_1 + x_2 5.15/2.17 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: 5.15/2.17 5.15/2.17 sub(s(v), s(w)) -> U6(sub(v, w)) 5.15/2.17 5.15/2.17 5.15/2.17 5.15/2.17 5.15/2.17 ---------------------------------------- 5.15/2.17 5.15/2.17 (4) 5.15/2.17 Obligation: 5.15/2.17 Q restricted rewrite system: 5.15/2.17 The TRS R consists of the following rules: 5.15/2.17 5.15/2.17 ssp'(cons(y', ws), v) -> U1(sub(v, y'), y', ws) 5.15/2.17 U1(w, y', ws) -> U2(ssp'(ws, w), y') 5.15/2.17 U2(ys', y') -> cons(y', ys') 5.15/2.17 ssp'(cons(x', xs'), v) -> U3(get(xs'), x', v) 5.15/2.17 U3(tp2(y', zs), x', v) -> U4(sub(v, y'), x', y', zs) 5.15/2.17 U4(w, x', y', zs) -> U5(ssp'(cons(x', zs), w), y') 5.15/2.17 U5(ys', y') -> cons(y', ys') 5.15/2.17 U6(z) -> z 5.15/2.17 get(cons(x', xs')) -> U7(get(xs'), x') 5.15/2.17 U7(tp2(y, zs), x') -> tp2(y, cons(x', zs)) 5.15/2.17 ssp'(xs, 0) -> nil 5.15/2.17 sub(z, 0) -> z 5.15/2.17 get(cons(y, ys)) -> tp2(y, ys) 5.15/2.17 5.15/2.17 Q is empty. 5.15/2.17 5.15/2.17 ---------------------------------------- 5.15/2.17 5.15/2.17 (5) QTRSRRRProof (EQUIVALENT) 5.15/2.17 Used ordering: 5.15/2.17 Polynomial interpretation [POLO]: 5.15/2.17 5.15/2.17 POL(0) = 2 5.15/2.17 POL(U1(x_1, x_2, x_3)) = x_1 + x_2 + 2*x_3 5.15/2.17 POL(U2(x_1, x_2)) = x_1 + x_2 5.15/2.17 POL(U3(x_1, x_2, x_3)) = 2*x_1 + 2*x_2 + x_3 5.15/2.17 POL(U4(x_1, x_2, x_3, x_4)) = x_1 + 2*x_2 + x_3 + 2*x_4 5.15/2.17 POL(U5(x_1, x_2)) = x_1 + x_2 5.15/2.17 POL(U6(x_1)) = x_1 5.15/2.17 POL(U7(x_1, x_2)) = x_1 + x_2 5.15/2.17 POL(cons(x_1, x_2)) = x_1 + x_2 5.15/2.17 POL(get(x_1)) = x_1 5.15/2.17 POL(nil) = 2 5.15/2.17 POL(ssp'(x_1, x_2)) = 2*x_1 + x_2 5.15/2.17 POL(sub(x_1, x_2)) = x_1 + x_2 5.15/2.17 POL(tp2(x_1, x_2)) = x_1 + x_2 5.15/2.17 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: 5.15/2.17 5.15/2.17 sub(z, 0) -> z 5.15/2.17 5.15/2.17 5.15/2.17 5.15/2.17 5.15/2.17 ---------------------------------------- 5.15/2.17 5.15/2.17 (6) 5.15/2.17 Obligation: 5.15/2.17 Q restricted rewrite system: 5.15/2.17 The TRS R consists of the following rules: 5.15/2.17 5.15/2.17 ssp'(cons(y', ws), v) -> U1(sub(v, y'), y', ws) 5.15/2.17 U1(w, y', ws) -> U2(ssp'(ws, w), y') 5.15/2.17 U2(ys', y') -> cons(y', ys') 5.15/2.17 ssp'(cons(x', xs'), v) -> U3(get(xs'), x', v) 5.15/2.17 U3(tp2(y', zs), x', v) -> U4(sub(v, y'), x', y', zs) 5.15/2.17 U4(w, x', y', zs) -> U5(ssp'(cons(x', zs), w), y') 5.15/2.17 U5(ys', y') -> cons(y', ys') 5.15/2.17 U6(z) -> z 5.15/2.17 get(cons(x', xs')) -> U7(get(xs'), x') 5.15/2.17 U7(tp2(y, zs), x') -> tp2(y, cons(x', zs)) 5.15/2.17 ssp'(xs, 0) -> nil 5.15/2.17 get(cons(y, ys)) -> tp2(y, ys) 5.15/2.17 5.15/2.17 Q is empty. 5.15/2.17 5.15/2.17 ---------------------------------------- 5.15/2.17 5.15/2.17 (7) QTRSRRRProof (EQUIVALENT) 5.15/2.17 Used ordering: 5.15/2.17 Polynomial interpretation [POLO]: 5.15/2.17 5.15/2.17 POL(0) = 2 5.15/2.17 POL(U1(x_1, x_2, x_3)) = x_1 + x_2 + 2*x_3 5.15/2.17 POL(U2(x_1, x_2)) = x_1 + x_2 5.15/2.17 POL(U3(x_1, x_2, x_3)) = 2*x_1 + 2*x_2 + x_3 5.15/2.17 POL(U4(x_1, x_2, x_3, x_4)) = x_1 + 2*x_2 + x_3 + 2*x_4 5.15/2.17 POL(U5(x_1, x_2)) = x_1 + x_2 5.15/2.17 POL(U6(x_1)) = 1 + x_1 5.15/2.17 POL(U7(x_1, x_2)) = x_1 + x_2 5.15/2.17 POL(cons(x_1, x_2)) = x_1 + x_2 5.15/2.17 POL(get(x_1)) = x_1 5.15/2.17 POL(nil) = 2 5.15/2.17 POL(ssp'(x_1, x_2)) = 2*x_1 + x_2 5.15/2.17 POL(sub(x_1, x_2)) = x_1 + x_2 5.15/2.17 POL(tp2(x_1, x_2)) = x_1 + x_2 5.15/2.17 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: 5.15/2.17 5.15/2.17 U6(z) -> z 5.15/2.17 5.15/2.17 5.15/2.17 5.15/2.17 5.15/2.17 ---------------------------------------- 5.15/2.17 5.15/2.17 (8) 5.15/2.17 Obligation: 5.15/2.17 Q restricted rewrite system: 5.15/2.17 The TRS R consists of the following rules: 5.15/2.17 5.15/2.17 ssp'(cons(y', ws), v) -> U1(sub(v, y'), y', ws) 5.15/2.17 U1(w, y', ws) -> U2(ssp'(ws, w), y') 5.15/2.17 U2(ys', y') -> cons(y', ys') 5.15/2.17 ssp'(cons(x', xs'), v) -> U3(get(xs'), x', v) 5.15/2.17 U3(tp2(y', zs), x', v) -> U4(sub(v, y'), x', y', zs) 5.15/2.17 U4(w, x', y', zs) -> U5(ssp'(cons(x', zs), w), y') 5.15/2.17 U5(ys', y') -> cons(y', ys') 5.15/2.17 get(cons(x', xs')) -> U7(get(xs'), x') 5.15/2.17 U7(tp2(y, zs), x') -> tp2(y, cons(x', zs)) 5.15/2.17 ssp'(xs, 0) -> nil 5.15/2.17 get(cons(y, ys)) -> tp2(y, ys) 5.15/2.17 5.15/2.17 Q is empty. 5.15/2.17 5.15/2.17 ---------------------------------------- 5.15/2.17 5.15/2.17 (9) QTRSRRRProof (EQUIVALENT) 5.15/2.17 Used ordering: 5.15/2.17 Polynomial interpretation [POLO]: 5.15/2.17 5.15/2.17 POL(0) = 2 5.15/2.17 POL(U1(x_1, x_2, x_3)) = x_1 + x_2 + 2*x_3 5.15/2.17 POL(U2(x_1, x_2)) = x_1 + x_2 5.15/2.17 POL(U3(x_1, x_2, x_3)) = 2*x_1 + 2*x_2 + x_3 5.15/2.17 POL(U4(x_1, x_2, x_3, x_4)) = x_1 + 2*x_2 + x_3 + 2*x_4 5.15/2.17 POL(U5(x_1, x_2)) = x_1 + x_2 5.15/2.17 POL(U7(x_1, x_2)) = x_1 + x_2 5.15/2.17 POL(cons(x_1, x_2)) = x_1 + x_2 5.15/2.17 POL(get(x_1)) = x_1 5.15/2.17 POL(nil) = 0 5.15/2.17 POL(ssp'(x_1, x_2)) = 2*x_1 + x_2 5.15/2.17 POL(sub(x_1, x_2)) = x_1 + x_2 5.15/2.17 POL(tp2(x_1, x_2)) = x_1 + x_2 5.15/2.17 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: 5.15/2.18 5.15/2.18 ssp'(xs, 0) -> nil 5.15/2.18 5.15/2.18 5.15/2.18 5.15/2.18 5.15/2.18 ---------------------------------------- 5.15/2.18 5.15/2.18 (10) 5.15/2.18 Obligation: 5.15/2.18 Q restricted rewrite system: 5.15/2.18 The TRS R consists of the following rules: 5.15/2.18 5.15/2.18 ssp'(cons(y', ws), v) -> U1(sub(v, y'), y', ws) 5.15/2.18 U1(w, y', ws) -> U2(ssp'(ws, w), y') 5.15/2.18 U2(ys', y') -> cons(y', ys') 5.15/2.18 ssp'(cons(x', xs'), v) -> U3(get(xs'), x', v) 5.15/2.18 U3(tp2(y', zs), x', v) -> U4(sub(v, y'), x', y', zs) 5.15/2.18 U4(w, x', y', zs) -> U5(ssp'(cons(x', zs), w), y') 5.15/2.18 U5(ys', y') -> cons(y', ys') 5.15/2.18 get(cons(x', xs')) -> U7(get(xs'), x') 5.15/2.18 U7(tp2(y, zs), x') -> tp2(y, cons(x', zs)) 5.15/2.18 get(cons(y, ys)) -> tp2(y, ys) 5.15/2.18 5.15/2.18 Q is empty. 5.15/2.18 5.15/2.18 ---------------------------------------- 5.15/2.18 5.15/2.18 (11) DependencyPairsProof (EQUIVALENT) 5.15/2.18 Using Dependency Pairs [AG00,LPAR04] we result in the following initial DP problem. 5.15/2.18 ---------------------------------------- 5.15/2.18 5.15/2.18 (12) 5.15/2.18 Obligation: 5.15/2.18 Q DP problem: 5.15/2.18 The TRS P consists of the following rules: 5.15/2.18 5.15/2.18 SSP'(cons(y', ws), v) -> U1^1(sub(v, y'), y', ws) 5.15/2.18 U1^1(w, y', ws) -> U2^1(ssp'(ws, w), y') 5.15/2.18 U1^1(w, y', ws) -> SSP'(ws, w) 5.15/2.18 SSP'(cons(x', xs'), v) -> U3^1(get(xs'), x', v) 5.15/2.18 SSP'(cons(x', xs'), v) -> GET(xs') 5.15/2.18 U3^1(tp2(y', zs), x', v) -> U4^1(sub(v, y'), x', y', zs) 5.15/2.18 U4^1(w, x', y', zs) -> U5^1(ssp'(cons(x', zs), w), y') 5.15/2.18 U4^1(w, x', y', zs) -> SSP'(cons(x', zs), w) 5.15/2.18 GET(cons(x', xs')) -> U7^1(get(xs'), x') 5.15/2.18 GET(cons(x', xs')) -> GET(xs') 5.15/2.18 5.15/2.18 The TRS R consists of the following rules: 5.15/2.18 5.15/2.18 ssp'(cons(y', ws), v) -> U1(sub(v, y'), y', ws) 5.15/2.18 U1(w, y', ws) -> U2(ssp'(ws, w), y') 5.15/2.18 U2(ys', y') -> cons(y', ys') 5.15/2.18 ssp'(cons(x', xs'), v) -> U3(get(xs'), x', v) 5.15/2.18 U3(tp2(y', zs), x', v) -> U4(sub(v, y'), x', y', zs) 5.15/2.18 U4(w, x', y', zs) -> U5(ssp'(cons(x', zs), w), y') 5.15/2.18 U5(ys', y') -> cons(y', ys') 5.15/2.18 get(cons(x', xs')) -> U7(get(xs'), x') 5.15/2.18 U7(tp2(y, zs), x') -> tp2(y, cons(x', zs)) 5.15/2.18 get(cons(y, ys)) -> tp2(y, ys) 5.15/2.18 5.15/2.18 Q is empty. 5.15/2.18 We have to consider all minimal (P,Q,R)-chains. 5.15/2.18 ---------------------------------------- 5.15/2.18 5.15/2.18 (13) DependencyGraphProof (EQUIVALENT) 5.15/2.18 The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 2 SCCs with 4 less nodes. 5.15/2.18 ---------------------------------------- 5.15/2.18 5.15/2.18 (14) 5.15/2.18 Complex Obligation (AND) 5.15/2.18 5.15/2.18 ---------------------------------------- 5.15/2.18 5.15/2.18 (15) 5.15/2.18 Obligation: 5.15/2.18 Q DP problem: 5.15/2.18 The TRS P consists of the following rules: 5.15/2.18 5.15/2.18 GET(cons(x', xs')) -> GET(xs') 5.15/2.18 5.15/2.18 The TRS R consists of the following rules: 5.15/2.18 5.15/2.18 ssp'(cons(y', ws), v) -> U1(sub(v, y'), y', ws) 5.15/2.18 U1(w, y', ws) -> U2(ssp'(ws, w), y') 5.15/2.18 U2(ys', y') -> cons(y', ys') 5.15/2.18 ssp'(cons(x', xs'), v) -> U3(get(xs'), x', v) 5.15/2.18 U3(tp2(y', zs), x', v) -> U4(sub(v, y'), x', y', zs) 5.15/2.18 U4(w, x', y', zs) -> U5(ssp'(cons(x', zs), w), y') 5.15/2.18 U5(ys', y') -> cons(y', ys') 5.15/2.18 get(cons(x', xs')) -> U7(get(xs'), x') 5.15/2.18 U7(tp2(y, zs), x') -> tp2(y, cons(x', zs)) 5.15/2.18 get(cons(y, ys)) -> tp2(y, ys) 5.15/2.18 5.15/2.18 Q is empty. 5.15/2.18 We have to consider all minimal (P,Q,R)-chains. 5.15/2.18 ---------------------------------------- 5.15/2.18 5.15/2.18 (16) UsableRulesProof (EQUIVALENT) 5.15/2.18 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. 5.15/2.18 ---------------------------------------- 5.15/2.18 5.15/2.18 (17) 5.15/2.18 Obligation: 5.15/2.18 Q DP problem: 5.15/2.18 The TRS P consists of the following rules: 5.15/2.18 5.15/2.18 GET(cons(x', xs')) -> GET(xs') 5.15/2.18 5.15/2.18 R is empty. 5.15/2.18 Q is empty. 5.15/2.18 We have to consider all minimal (P,Q,R)-chains. 5.15/2.18 ---------------------------------------- 5.15/2.18 5.15/2.18 (18) QDPSizeChangeProof (EQUIVALENT) 5.15/2.18 By using the subterm criterion [SUBTERM_CRITERION] together with the size-change analysis [AAECC05] we have proven that there are no infinite chains for this DP problem. 5.15/2.18 5.15/2.18 From the DPs we obtained the following set of size-change graphs: 5.15/2.18 *GET(cons(x', xs')) -> GET(xs') 5.15/2.18 The graph contains the following edges 1 > 1 5.15/2.18 5.15/2.18 5.15/2.18 ---------------------------------------- 5.15/2.18 5.15/2.18 (19) 5.15/2.18 YES 5.15/2.18 5.15/2.18 ---------------------------------------- 5.15/2.18 5.15/2.18 (20) 5.15/2.18 Obligation: 5.15/2.18 Q DP problem: 5.15/2.18 The TRS P consists of the following rules: 5.15/2.18 5.15/2.18 U1^1(w, y', ws) -> SSP'(ws, w) 5.15/2.18 SSP'(cons(y', ws), v) -> U1^1(sub(v, y'), y', ws) 5.15/2.18 SSP'(cons(x', xs'), v) -> U3^1(get(xs'), x', v) 5.15/2.18 U3^1(tp2(y', zs), x', v) -> U4^1(sub(v, y'), x', y', zs) 5.15/2.18 U4^1(w, x', y', zs) -> SSP'(cons(x', zs), w) 5.15/2.18 5.15/2.18 The TRS R consists of the following rules: 5.15/2.18 5.15/2.18 ssp'(cons(y', ws), v) -> U1(sub(v, y'), y', ws) 5.15/2.18 U1(w, y', ws) -> U2(ssp'(ws, w), y') 5.15/2.18 U2(ys', y') -> cons(y', ys') 5.15/2.18 ssp'(cons(x', xs'), v) -> U3(get(xs'), x', v) 5.15/2.18 U3(tp2(y', zs), x', v) -> U4(sub(v, y'), x', y', zs) 5.15/2.18 U4(w, x', y', zs) -> U5(ssp'(cons(x', zs), w), y') 5.15/2.18 U5(ys', y') -> cons(y', ys') 5.15/2.18 get(cons(x', xs')) -> U7(get(xs'), x') 5.15/2.18 U7(tp2(y, zs), x') -> tp2(y, cons(x', zs)) 5.15/2.18 get(cons(y, ys)) -> tp2(y, ys) 5.15/2.18 5.15/2.18 Q is empty. 5.15/2.18 We have to consider all minimal (P,Q,R)-chains. 5.15/2.18 ---------------------------------------- 5.15/2.18 5.15/2.18 (21) UsableRulesReductionPairsProof (EQUIVALENT) 5.15/2.18 By using the usable rules with reduction pair processor [LPAR04] with a polynomial ordering [POLO], all dependency pairs and the corresponding usable rules [FROCOS05] can be oriented non-strictly. All non-usable rules are removed, and those dependency pairs and usable rules that have been oriented strictly or contain non-usable symbols in their left-hand side are removed as well. 5.15/2.18 5.15/2.18 No dependency pairs are removed. 5.15/2.18 5.15/2.18 The following rules are removed from R: 5.15/2.18 5.15/2.18 ssp'(cons(y', ws), v) -> U1(sub(v, y'), y', ws) 5.15/2.18 U1(w, y', ws) -> U2(ssp'(ws, w), y') 5.15/2.18 U2(ys', y') -> cons(y', ys') 5.15/2.18 ssp'(cons(x', xs'), v) -> U3(get(xs'), x', v) 5.15/2.18 U3(tp2(y', zs), x', v) -> U4(sub(v, y'), x', y', zs) 5.15/2.18 U4(w, x', y', zs) -> U5(ssp'(cons(x', zs), w), y') 5.15/2.18 U5(ys', y') -> cons(y', ys') 5.15/2.18 Used ordering: POLO with Polynomial interpretation [POLO]: 5.15/2.18 5.15/2.18 POL(SSP'(x_1, x_2)) = x_1 + x_2 5.15/2.18 POL(U1^1(x_1, x_2, x_3)) = x_1 + x_2 + x_3 5.15/2.18 POL(U3^1(x_1, x_2, x_3)) = x_1 + 2*x_2 + x_3 5.15/2.18 POL(U4^1(x_1, x_2, x_3, x_4)) = x_1 + 2*x_2 + x_3 + x_4 5.15/2.18 POL(U7(x_1, x_2)) = x_1 + 2*x_2 5.15/2.18 POL(cons(x_1, x_2)) = 2*x_1 + x_2 5.15/2.18 POL(get(x_1)) = x_1 5.15/2.18 POL(sub(x_1, x_2)) = x_1 + x_2 5.15/2.18 POL(tp2(x_1, x_2)) = 2*x_1 + x_2 5.15/2.18 5.15/2.18 5.15/2.18 ---------------------------------------- 5.15/2.18 5.15/2.18 (22) 5.15/2.18 Obligation: 5.15/2.18 Q DP problem: 5.15/2.18 The TRS P consists of the following rules: 5.15/2.18 5.15/2.18 U1^1(w, y', ws) -> SSP'(ws, w) 5.15/2.18 SSP'(cons(y', ws), v) -> U1^1(sub(v, y'), y', ws) 5.15/2.18 SSP'(cons(x', xs'), v) -> U3^1(get(xs'), x', v) 5.15/2.18 U3^1(tp2(y', zs), x', v) -> U4^1(sub(v, y'), x', y', zs) 5.15/2.18 U4^1(w, x', y', zs) -> SSP'(cons(x', zs), w) 5.15/2.18 5.15/2.18 The TRS R consists of the following rules: 5.15/2.18 5.15/2.18 get(cons(x', xs')) -> U7(get(xs'), x') 5.15/2.18 get(cons(y, ys)) -> tp2(y, ys) 5.15/2.18 U7(tp2(y, zs), x') -> tp2(y, cons(x', zs)) 5.15/2.18 5.15/2.18 Q is empty. 5.15/2.18 We have to consider all minimal (P,Q,R)-chains. 5.15/2.18 ---------------------------------------- 5.15/2.18 5.15/2.18 (23) MRRProof (EQUIVALENT) 5.15/2.18 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. 5.15/2.18 5.15/2.18 Strictly oriented dependency pairs: 5.15/2.18 5.15/2.18 SSP'(cons(y', ws), v) -> U1^1(sub(v, y'), y', ws) 5.15/2.18 U3^1(tp2(y', zs), x', v) -> U4^1(sub(v, y'), x', y', zs) 5.15/2.18 U4^1(w, x', y', zs) -> SSP'(cons(x', zs), w) 5.15/2.18 5.15/2.18 Strictly oriented rules of the TRS R: 5.15/2.18 5.15/2.18 U7(tp2(y, zs), x') -> tp2(y, cons(x', zs)) 5.15/2.18 5.15/2.18 Used ordering: Polynomial interpretation [POLO]: 5.15/2.18 5.15/2.18 POL(SSP'(x_1, x_2)) = x_1 + x_2 5.15/2.18 POL(U1^1(x_1, x_2, x_3)) = x_1 + x_2 + 2*x_3 5.15/2.18 POL(U3^1(x_1, x_2, x_3)) = 1 + 2*x_1 + 2*x_2 + x_3 5.15/2.18 POL(U4^1(x_1, x_2, x_3, x_4)) = 2 + x_1 + 2*x_2 + x_3 + 2*x_4 5.15/2.18 POL(U7(x_1, x_2)) = 1 + 2*x_1 + 2*x_2 5.15/2.18 POL(cons(x_1, x_2)) = 1 + 2*x_1 + 2*x_2 5.15/2.18 POL(get(x_1)) = x_1 5.15/2.18 POL(sub(x_1, x_2)) = x_1 + x_2 5.15/2.18 POL(tp2(x_1, x_2)) = 1 + 2*x_1 + x_2 5.15/2.18 5.15/2.18 5.15/2.18 ---------------------------------------- 5.15/2.18 5.15/2.18 (24) 5.15/2.18 Obligation: 5.15/2.18 Q DP problem: 5.15/2.18 The TRS P consists of the following rules: 5.15/2.18 5.15/2.18 U1^1(w, y', ws) -> SSP'(ws, w) 5.15/2.18 SSP'(cons(x', xs'), v) -> U3^1(get(xs'), x', v) 5.15/2.18 5.15/2.18 The TRS R consists of the following rules: 5.15/2.18 5.15/2.18 get(cons(x', xs')) -> U7(get(xs'), x') 5.15/2.18 get(cons(y, ys)) -> tp2(y, ys) 5.15/2.18 5.15/2.18 Q is empty. 5.15/2.18 We have to consider all minimal (P,Q,R)-chains. 5.15/2.18 ---------------------------------------- 5.15/2.18 5.15/2.18 (25) DependencyGraphProof (EQUIVALENT) 5.15/2.18 The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 0 SCCs with 2 less nodes. 5.15/2.18 ---------------------------------------- 5.15/2.18 5.15/2.18 (26) 5.15/2.18 TRUE 5.41/2.21 EOF