/export/starexec/sandbox/solver/bin/starexec_run_standard /export/starexec/sandbox/benchmark/theBenchmark.xml /export/starexec/sandbox/output/output_files -------------------------------------------------------------------------------- YES proof of /export/starexec/sandbox/benchmark/theBenchmark.xml # AProVE Commit ID: 794c25de1cacf0d048858bcd21c9a779e1221865 marcel 20200619 unpublished dirty Quasi decreasingness of the given CTRS could be proven: (0) CTRS (1) CTRSToQTRSProof [SOUND, 0 ms] (2) QTRS (3) QTRSRRRProof [EQUIVALENT, 60 ms] (4) QTRS (5) QTRSRRRProof [EQUIVALENT, 13 ms] (6) QTRS (7) QTRSRRRProof [EQUIVALENT, 21 ms] (8) QTRS (9) QTRSRRRProof [EQUIVALENT, 23 ms] (10) QTRS (11) DependencyPairsProof [EQUIVALENT, 0 ms] (12) QDP (13) DependencyGraphProof [EQUIVALENT, 0 ms] (14) AND (15) QDP (16) UsableRulesProof [EQUIVALENT, 0 ms] (17) QDP (18) QDPSizeChangeProof [EQUIVALENT, 0 ms] (19) YES (20) QDP (21) UsableRulesReductionPairsProof [EQUIVALENT, 0 ms] (22) QDP (23) MRRProof [EQUIVALENT, 0 ms] (24) QDP (25) DependencyGraphProof [EQUIVALENT, 0 ms] (26) TRUE ---------------------------------------- (0) Obligation: Conditional term rewrite system: The TRS R consists of the following rules: ssp'(xs, 0) -> nil sub(z, 0) -> z get(cons(y, ys)) -> tp2(y, ys) The conditional TRS C consists of the following conditional rules: ssp'(cons(y', ws), v) -> cons(y', ys') <= sub(v, y') -> w, ssp'(ws, w) -> ys' ssp'(cons(x', xs'), v) -> cons(y', ys') <= get(xs') -> tp2(y', zs), sub(v, y') -> w, ssp'(cons(x', zs), w) -> ys' sub(s(v), s(w)) -> z <= sub(v, w) -> z get(cons(x', xs')) -> tp2(y, cons(x', zs)) <= get(xs') -> tp2(y, zs) ---------------------------------------- (1) CTRSToQTRSProof (SOUND) The conditional rules have been transormed into unconditional rules according to [CTRS,AAECCNOC]. ---------------------------------------- (2) Obligation: Q restricted rewrite system: The TRS R consists of the following rules: ssp'(cons(y', ws), v) -> U1(sub(v, y'), y', ws) U1(w, y', ws) -> U2(ssp'(ws, w), y') U2(ys', y') -> cons(y', ys') ssp'(cons(x', xs'), v) -> U3(get(xs'), x', v) U3(tp2(y', zs), x', v) -> U4(sub(v, y'), x', y', zs) U4(w, x', y', zs) -> U5(ssp'(cons(x', zs), w), y') U5(ys', y') -> cons(y', ys') sub(s(v), s(w)) -> U6(sub(v, w)) U6(z) -> z get(cons(x', xs')) -> U7(get(xs'), x') U7(tp2(y, zs), x') -> tp2(y, cons(x', zs)) ssp'(xs, 0) -> nil sub(z, 0) -> z get(cons(y, ys)) -> tp2(y, ys) Q is empty. ---------------------------------------- (3) QTRSRRRProof (EQUIVALENT) Used ordering: Polynomial interpretation [POLO]: POL(0) = 0 POL(U1(x_1, x_2, x_3)) = x_1 + x_2 + 2*x_3 POL(U2(x_1, x_2)) = x_1 + x_2 POL(U3(x_1, x_2, x_3)) = 2*x_1 + 2*x_2 + x_3 POL(U4(x_1, x_2, x_3, x_4)) = x_1 + 2*x_2 + x_3 + 2*x_4 POL(U5(x_1, x_2)) = x_1 + x_2 POL(U6(x_1)) = 2*x_1 POL(U7(x_1, x_2)) = x_1 + x_2 POL(cons(x_1, x_2)) = x_1 + x_2 POL(get(x_1)) = x_1 POL(nil) = 0 POL(s(x_1)) = 1 + 2*x_1 POL(ssp'(x_1, x_2)) = 2*x_1 + x_2 POL(sub(x_1, x_2)) = x_1 + x_2 POL(tp2(x_1, x_2)) = x_1 + x_2 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: sub(s(v), s(w)) -> U6(sub(v, w)) ---------------------------------------- (4) Obligation: Q restricted rewrite system: The TRS R consists of the following rules: ssp'(cons(y', ws), v) -> U1(sub(v, y'), y', ws) U1(w, y', ws) -> U2(ssp'(ws, w), y') U2(ys', y') -> cons(y', ys') ssp'(cons(x', xs'), v) -> U3(get(xs'), x', v) U3(tp2(y', zs), x', v) -> U4(sub(v, y'), x', y', zs) U4(w, x', y', zs) -> U5(ssp'(cons(x', zs), w), y') U5(ys', y') -> cons(y', ys') U6(z) -> z get(cons(x', xs')) -> U7(get(xs'), x') U7(tp2(y, zs), x') -> tp2(y, cons(x', zs)) ssp'(xs, 0) -> nil sub(z, 0) -> z get(cons(y, ys)) -> tp2(y, ys) Q is empty. ---------------------------------------- (5) QTRSRRRProof (EQUIVALENT) Used ordering: Polynomial interpretation [POLO]: POL(0) = 2 POL(U1(x_1, x_2, x_3)) = x_1 + x_2 + 2*x_3 POL(U2(x_1, x_2)) = x_1 + x_2 POL(U3(x_1, x_2, x_3)) = 2*x_1 + 2*x_2 + x_3 POL(U4(x_1, x_2, x_3, x_4)) = x_1 + 2*x_2 + x_3 + 2*x_4 POL(U5(x_1, x_2)) = x_1 + x_2 POL(U6(x_1)) = x_1 POL(U7(x_1, x_2)) = x_1 + x_2 POL(cons(x_1, x_2)) = x_1 + x_2 POL(get(x_1)) = x_1 POL(nil) = 2 POL(ssp'(x_1, x_2)) = 2*x_1 + x_2 POL(sub(x_1, x_2)) = x_1 + x_2 POL(tp2(x_1, x_2)) = x_1 + x_2 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: sub(z, 0) -> z ---------------------------------------- (6) Obligation: Q restricted rewrite system: The TRS R consists of the following rules: ssp'(cons(y', ws), v) -> U1(sub(v, y'), y', ws) U1(w, y', ws) -> U2(ssp'(ws, w), y') U2(ys', y') -> cons(y', ys') ssp'(cons(x', xs'), v) -> U3(get(xs'), x', v) U3(tp2(y', zs), x', v) -> U4(sub(v, y'), x', y', zs) U4(w, x', y', zs) -> U5(ssp'(cons(x', zs), w), y') U5(ys', y') -> cons(y', ys') U6(z) -> z get(cons(x', xs')) -> U7(get(xs'), x') U7(tp2(y, zs), x') -> tp2(y, cons(x', zs)) ssp'(xs, 0) -> nil get(cons(y, ys)) -> tp2(y, ys) Q is empty. ---------------------------------------- (7) QTRSRRRProof (EQUIVALENT) Used ordering: Polynomial interpretation [POLO]: POL(0) = 2 POL(U1(x_1, x_2, x_3)) = x_1 + x_2 + 2*x_3 POL(U2(x_1, x_2)) = x_1 + x_2 POL(U3(x_1, x_2, x_3)) = 2*x_1 + 2*x_2 + x_3 POL(U4(x_1, x_2, x_3, x_4)) = x_1 + 2*x_2 + x_3 + 2*x_4 POL(U5(x_1, x_2)) = x_1 + x_2 POL(U6(x_1)) = 1 + x_1 POL(U7(x_1, x_2)) = x_1 + x_2 POL(cons(x_1, x_2)) = x_1 + x_2 POL(get(x_1)) = x_1 POL(nil) = 2 POL(ssp'(x_1, x_2)) = 2*x_1 + x_2 POL(sub(x_1, x_2)) = x_1 + x_2 POL(tp2(x_1, x_2)) = x_1 + x_2 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: U6(z) -> z ---------------------------------------- (8) Obligation: Q restricted rewrite system: The TRS R consists of the following rules: ssp'(cons(y', ws), v) -> U1(sub(v, y'), y', ws) U1(w, y', ws) -> U2(ssp'(ws, w), y') U2(ys', y') -> cons(y', ys') ssp'(cons(x', xs'), v) -> U3(get(xs'), x', v) U3(tp2(y', zs), x', v) -> U4(sub(v, y'), x', y', zs) U4(w, x', y', zs) -> U5(ssp'(cons(x', zs), w), y') U5(ys', y') -> cons(y', ys') get(cons(x', xs')) -> U7(get(xs'), x') U7(tp2(y, zs), x') -> tp2(y, cons(x', zs)) ssp'(xs, 0) -> nil get(cons(y, ys)) -> tp2(y, ys) Q is empty. ---------------------------------------- (9) QTRSRRRProof (EQUIVALENT) Used ordering: Polynomial interpretation [POLO]: POL(0) = 2 POL(U1(x_1, x_2, x_3)) = x_1 + x_2 + 2*x_3 POL(U2(x_1, x_2)) = x_1 + x_2 POL(U3(x_1, x_2, x_3)) = 2*x_1 + 2*x_2 + x_3 POL(U4(x_1, x_2, x_3, x_4)) = x_1 + 2*x_2 + x_3 + 2*x_4 POL(U5(x_1, x_2)) = x_1 + x_2 POL(U7(x_1, x_2)) = x_1 + x_2 POL(cons(x_1, x_2)) = x_1 + x_2 POL(get(x_1)) = x_1 POL(nil) = 0 POL(ssp'(x_1, x_2)) = 2*x_1 + x_2 POL(sub(x_1, x_2)) = x_1 + x_2 POL(tp2(x_1, x_2)) = x_1 + x_2 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: ssp'(xs, 0) -> nil ---------------------------------------- (10) Obligation: Q restricted rewrite system: The TRS R consists of the following rules: ssp'(cons(y', ws), v) -> U1(sub(v, y'), y', ws) U1(w, y', ws) -> U2(ssp'(ws, w), y') U2(ys', y') -> cons(y', ys') ssp'(cons(x', xs'), v) -> U3(get(xs'), x', v) U3(tp2(y', zs), x', v) -> U4(sub(v, y'), x', y', zs) U4(w, x', y', zs) -> U5(ssp'(cons(x', zs), w), y') U5(ys', y') -> cons(y', ys') get(cons(x', xs')) -> U7(get(xs'), x') U7(tp2(y, zs), x') -> tp2(y, cons(x', zs)) get(cons(y, ys)) -> tp2(y, ys) Q is empty. ---------------------------------------- (11) DependencyPairsProof (EQUIVALENT) Using Dependency Pairs [AG00,LPAR04] we result in the following initial DP problem. ---------------------------------------- (12) Obligation: Q DP problem: The TRS P consists of the following rules: SSP'(cons(y', ws), v) -> U1^1(sub(v, y'), y', ws) U1^1(w, y', ws) -> U2^1(ssp'(ws, w), y') U1^1(w, y', ws) -> SSP'(ws, w) SSP'(cons(x', xs'), v) -> U3^1(get(xs'), x', v) SSP'(cons(x', xs'), v) -> GET(xs') U3^1(tp2(y', zs), x', v) -> U4^1(sub(v, y'), x', y', zs) U4^1(w, x', y', zs) -> U5^1(ssp'(cons(x', zs), w), y') U4^1(w, x', y', zs) -> SSP'(cons(x', zs), w) GET(cons(x', xs')) -> U7^1(get(xs'), x') GET(cons(x', xs')) -> GET(xs') The TRS R consists of the following rules: ssp'(cons(y', ws), v) -> U1(sub(v, y'), y', ws) U1(w, y', ws) -> U2(ssp'(ws, w), y') U2(ys', y') -> cons(y', ys') ssp'(cons(x', xs'), v) -> U3(get(xs'), x', v) U3(tp2(y', zs), x', v) -> U4(sub(v, y'), x', y', zs) U4(w, x', y', zs) -> U5(ssp'(cons(x', zs), w), y') U5(ys', y') -> cons(y', ys') get(cons(x', xs')) -> U7(get(xs'), x') U7(tp2(y, zs), x') -> tp2(y, cons(x', zs)) get(cons(y, ys)) -> tp2(y, ys) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (13) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 2 SCCs with 4 less nodes. ---------------------------------------- (14) Complex Obligation (AND) ---------------------------------------- (15) Obligation: Q DP problem: The TRS P consists of the following rules: GET(cons(x', xs')) -> GET(xs') The TRS R consists of the following rules: ssp'(cons(y', ws), v) -> U1(sub(v, y'), y', ws) U1(w, y', ws) -> U2(ssp'(ws, w), y') U2(ys', y') -> cons(y', ys') ssp'(cons(x', xs'), v) -> U3(get(xs'), x', v) U3(tp2(y', zs), x', v) -> U4(sub(v, y'), x', y', zs) U4(w, x', y', zs) -> U5(ssp'(cons(x', zs), w), y') U5(ys', y') -> cons(y', ys') get(cons(x', xs')) -> U7(get(xs'), x') U7(tp2(y, zs), x') -> tp2(y, cons(x', zs)) get(cons(y, ys)) -> tp2(y, ys) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (16) UsableRulesProof (EQUIVALENT) 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. ---------------------------------------- (17) Obligation: Q DP problem: The TRS P consists of the following rules: GET(cons(x', xs')) -> GET(xs') R is empty. Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (18) QDPSizeChangeProof (EQUIVALENT) 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. From the DPs we obtained the following set of size-change graphs: *GET(cons(x', xs')) -> GET(xs') The graph contains the following edges 1 > 1 ---------------------------------------- (19) YES ---------------------------------------- (20) Obligation: Q DP problem: The TRS P consists of the following rules: U1^1(w, y', ws) -> SSP'(ws, w) SSP'(cons(y', ws), v) -> U1^1(sub(v, y'), y', ws) SSP'(cons(x', xs'), v) -> U3^1(get(xs'), x', v) U3^1(tp2(y', zs), x', v) -> U4^1(sub(v, y'), x', y', zs) U4^1(w, x', y', zs) -> SSP'(cons(x', zs), w) The TRS R consists of the following rules: ssp'(cons(y', ws), v) -> U1(sub(v, y'), y', ws) U1(w, y', ws) -> U2(ssp'(ws, w), y') U2(ys', y') -> cons(y', ys') ssp'(cons(x', xs'), v) -> U3(get(xs'), x', v) U3(tp2(y', zs), x', v) -> U4(sub(v, y'), x', y', zs) U4(w, x', y', zs) -> U5(ssp'(cons(x', zs), w), y') U5(ys', y') -> cons(y', ys') get(cons(x', xs')) -> U7(get(xs'), x') U7(tp2(y, zs), x') -> tp2(y, cons(x', zs)) get(cons(y, ys)) -> tp2(y, ys) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (21) UsableRulesReductionPairsProof (EQUIVALENT) 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. No dependency pairs are removed. The following rules are removed from R: ssp'(cons(y', ws), v) -> U1(sub(v, y'), y', ws) U1(w, y', ws) -> U2(ssp'(ws, w), y') U2(ys', y') -> cons(y', ys') ssp'(cons(x', xs'), v) -> U3(get(xs'), x', v) U3(tp2(y', zs), x', v) -> U4(sub(v, y'), x', y', zs) U4(w, x', y', zs) -> U5(ssp'(cons(x', zs), w), y') U5(ys', y') -> cons(y', ys') Used ordering: POLO with Polynomial interpretation [POLO]: POL(SSP'(x_1, x_2)) = x_1 + x_2 POL(U1^1(x_1, x_2, x_3)) = x_1 + x_2 + x_3 POL(U3^1(x_1, x_2, x_3)) = x_1 + 2*x_2 + x_3 POL(U4^1(x_1, x_2, x_3, x_4)) = x_1 + 2*x_2 + x_3 + x_4 POL(U7(x_1, x_2)) = x_1 + 2*x_2 POL(cons(x_1, x_2)) = 2*x_1 + x_2 POL(get(x_1)) = x_1 POL(sub(x_1, x_2)) = x_1 + x_2 POL(tp2(x_1, x_2)) = 2*x_1 + x_2 ---------------------------------------- (22) Obligation: Q DP problem: The TRS P consists of the following rules: U1^1(w, y', ws) -> SSP'(ws, w) SSP'(cons(y', ws), v) -> U1^1(sub(v, y'), y', ws) SSP'(cons(x', xs'), v) -> U3^1(get(xs'), x', v) U3^1(tp2(y', zs), x', v) -> U4^1(sub(v, y'), x', y', zs) U4^1(w, x', y', zs) -> SSP'(cons(x', zs), w) The TRS R consists of the following rules: get(cons(x', xs')) -> U7(get(xs'), x') get(cons(y, ys)) -> tp2(y, ys) U7(tp2(y, zs), x') -> tp2(y, cons(x', zs)) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (23) MRRProof (EQUIVALENT) 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. Strictly oriented dependency pairs: SSP'(cons(y', ws), v) -> U1^1(sub(v, y'), y', ws) U3^1(tp2(y', zs), x', v) -> U4^1(sub(v, y'), x', y', zs) U4^1(w, x', y', zs) -> SSP'(cons(x', zs), w) Strictly oriented rules of the TRS R: U7(tp2(y, zs), x') -> tp2(y, cons(x', zs)) Used ordering: Polynomial interpretation [POLO]: POL(SSP'(x_1, x_2)) = x_1 + x_2 POL(U1^1(x_1, x_2, x_3)) = x_1 + x_2 + 2*x_3 POL(U3^1(x_1, x_2, x_3)) = 1 + 2*x_1 + 2*x_2 + x_3 POL(U4^1(x_1, x_2, x_3, x_4)) = 2 + x_1 + 2*x_2 + x_3 + 2*x_4 POL(U7(x_1, x_2)) = 1 + 2*x_1 + 2*x_2 POL(cons(x_1, x_2)) = 1 + 2*x_1 + 2*x_2 POL(get(x_1)) = x_1 POL(sub(x_1, x_2)) = x_1 + x_2 POL(tp2(x_1, x_2)) = 1 + 2*x_1 + x_2 ---------------------------------------- (24) Obligation: Q DP problem: The TRS P consists of the following rules: U1^1(w, y', ws) -> SSP'(ws, w) SSP'(cons(x', xs'), v) -> U3^1(get(xs'), x', v) The TRS R consists of the following rules: get(cons(x', xs')) -> U7(get(xs'), x') get(cons(y, ys)) -> tp2(y, ys) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (25) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 0 SCCs with 2 less nodes. ---------------------------------------- (26) TRUE