4.15/1.75 YES 4.15/1.76 proof of /export/starexec/sandbox/benchmark/theBenchmark.xml 4.15/1.76 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 4.15/1.76 4.15/1.76 4.15/1.76 Quasi decreasingness of the given CTRS could be proven: 4.15/1.76 4.15/1.76 (0) CTRS 4.15/1.76 (1) CTRSToQTRSProof [SOUND, 0 ms] 4.15/1.76 (2) QTRS 4.15/1.76 (3) QTRSRRRProof [EQUIVALENT, 57 ms] 4.15/1.76 (4) QTRS 4.15/1.76 (5) QTRSRRRProof [EQUIVALENT, 19 ms] 4.15/1.76 (6) QTRS 4.15/1.76 (7) QTRSRRRProof [EQUIVALENT, 0 ms] 4.15/1.76 (8) QTRS 4.15/1.76 (9) QTRSRRRProof [EQUIVALENT, 0 ms] 4.15/1.76 (10) QTRS 4.15/1.76 (11) RisEmptyProof [EQUIVALENT, 3 ms] 4.15/1.76 (12) YES 4.15/1.76 4.15/1.76 4.15/1.76 ---------------------------------------- 4.15/1.76 4.15/1.76 (0) 4.15/1.76 Obligation: 4.15/1.76 Conditional term rewrite system: 4.15/1.76 The TRS R consists of the following rules: 4.15/1.76 4.15/1.76 ssp(nil, 0) -> nil 4.15/1.76 sub(z, 0) -> z 4.15/1.76 4.15/1.76 The conditional TRS C consists of the following conditional rules: 4.15/1.76 4.15/1.76 ssp(cons(y, ys'), v) -> xs <= ssp(ys', v) -> xs 4.15/1.76 ssp(cons(y, ys'), v) -> cons(y, xs') <= sub(v, y) -> w, ssp(ys', w) -> xs' 4.15/1.76 sub(s(v), s(w)) -> z <= sub(v, w) -> z 4.15/1.76 4.15/1.76 4.15/1.76 ---------------------------------------- 4.15/1.76 4.15/1.76 (1) CTRSToQTRSProof (SOUND) 4.15/1.76 The conditional rules have been transormed into unconditional rules according to [CTRS,AAECCNOC]. 4.15/1.76 ---------------------------------------- 4.15/1.76 4.15/1.76 (2) 4.15/1.76 Obligation: 4.15/1.76 Q restricted rewrite system: 4.15/1.76 The TRS R consists of the following rules: 4.15/1.76 4.15/1.76 ssp(cons(y, ys'), v) -> U1(ssp(ys', v)) 4.15/1.76 U1(xs) -> xs 4.15/1.76 ssp(cons(y, ys'), v) -> U2(sub(v, y), y, ys') 4.15/1.76 U2(w, y, ys') -> U3(ssp(ys', w), y) 4.15/1.76 U3(xs', y) -> cons(y, xs') 4.15/1.76 sub(s(v), s(w)) -> U4(sub(v, w)) 4.15/1.76 U4(z) -> z 4.15/1.76 ssp(nil, 0) -> nil 4.15/1.76 sub(z, 0) -> z 4.15/1.76 4.15/1.76 Q is empty. 4.15/1.76 4.15/1.76 ---------------------------------------- 4.15/1.76 4.15/1.76 (3) QTRSRRRProof (EQUIVALENT) 4.15/1.76 Used ordering: 4.15/1.76 Polynomial interpretation [POLO]: 4.15/1.76 4.15/1.76 POL(0) = 2 4.15/1.76 POL(U1(x_1)) = x_1 4.15/1.76 POL(U2(x_1, x_2, x_3)) = x_1 + 2*x_2 + 2*x_3 4.15/1.76 POL(U3(x_1, x_2)) = x_1 + 2*x_2 4.15/1.76 POL(U4(x_1)) = 2*x_1 4.15/1.76 POL(cons(x_1, x_2)) = 2*x_1 + x_2 4.15/1.76 POL(nil) = 0 4.15/1.76 POL(s(x_1)) = 2*x_1 4.15/1.76 POL(ssp(x_1, x_2)) = 2*x_1 + x_2 4.15/1.76 POL(sub(x_1, x_2)) = x_1 + 2*x_2 4.15/1.76 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: 4.15/1.76 4.15/1.76 ssp(nil, 0) -> nil 4.15/1.76 sub(z, 0) -> z 4.15/1.76 4.15/1.76 4.15/1.76 4.15/1.76 4.15/1.76 ---------------------------------------- 4.15/1.76 4.15/1.76 (4) 4.15/1.76 Obligation: 4.15/1.76 Q restricted rewrite system: 4.15/1.76 The TRS R consists of the following rules: 4.15/1.76 4.15/1.76 ssp(cons(y, ys'), v) -> U1(ssp(ys', v)) 4.15/1.76 U1(xs) -> xs 4.15/1.76 ssp(cons(y, ys'), v) -> U2(sub(v, y), y, ys') 4.15/1.76 U2(w, y, ys') -> U3(ssp(ys', w), y) 4.15/1.76 U3(xs', y) -> cons(y, xs') 4.15/1.76 sub(s(v), s(w)) -> U4(sub(v, w)) 4.15/1.76 U4(z) -> z 4.15/1.76 4.15/1.76 Q is empty. 4.15/1.76 4.15/1.76 ---------------------------------------- 4.15/1.76 4.15/1.76 (5) QTRSRRRProof (EQUIVALENT) 4.15/1.76 Used ordering: 4.15/1.76 Polynomial interpretation [POLO]: 4.15/1.76 4.15/1.76 POL(U1(x_1)) = 1 + x_1 4.15/1.76 POL(U2(x_1, x_2, x_3)) = 2 + x_1 + x_2 + 2*x_3 4.15/1.76 POL(U3(x_1, x_2)) = 2 + x_1 + x_2 4.15/1.76 POL(U4(x_1)) = x_1 4.15/1.76 POL(cons(x_1, x_2)) = 1 + x_1 + x_2 4.15/1.76 POL(s(x_1)) = 2*x_1 4.15/1.76 POL(ssp(x_1, x_2)) = 2*x_1 + x_2 4.15/1.76 POL(sub(x_1, x_2)) = x_1 + x_2 4.15/1.76 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: 4.15/1.76 4.15/1.76 ssp(cons(y, ys'), v) -> U1(ssp(ys', v)) 4.15/1.76 U1(xs) -> xs 4.15/1.76 U3(xs', y) -> cons(y, xs') 4.15/1.76 4.15/1.76 4.15/1.76 4.15/1.76 4.15/1.76 ---------------------------------------- 4.15/1.76 4.15/1.76 (6) 4.15/1.76 Obligation: 4.15/1.76 Q restricted rewrite system: 4.15/1.76 The TRS R consists of the following rules: 4.15/1.76 4.15/1.76 ssp(cons(y, ys'), v) -> U2(sub(v, y), y, ys') 4.15/1.76 U2(w, y, ys') -> U3(ssp(ys', w), y) 4.15/1.76 sub(s(v), s(w)) -> U4(sub(v, w)) 4.15/1.76 U4(z) -> z 4.15/1.76 4.15/1.76 Q is empty. 4.15/1.76 4.15/1.76 ---------------------------------------- 4.15/1.76 4.15/1.76 (7) QTRSRRRProof (EQUIVALENT) 4.15/1.76 Used ordering: 4.15/1.76 Polynomial interpretation [POLO]: 4.15/1.76 4.15/1.76 POL(U2(x_1, x_2, x_3)) = x_1 + 2*x_2 + 2*x_3 4.15/1.76 POL(U3(x_1, x_2)) = x_1 + 2*x_2 4.15/1.76 POL(U4(x_1)) = x_1 4.15/1.76 POL(cons(x_1, x_2)) = 2 + 2*x_1 + 2*x_2 4.15/1.76 POL(s(x_1)) = 2*x_1 4.15/1.76 POL(ssp(x_1, x_2)) = 2*x_1 + x_2 4.15/1.76 POL(sub(x_1, x_2)) = x_1 + 2*x_2 4.15/1.76 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: 4.15/1.76 4.15/1.76 ssp(cons(y, ys'), v) -> U2(sub(v, y), y, ys') 4.15/1.76 4.15/1.76 4.15/1.76 4.15/1.76 4.15/1.76 ---------------------------------------- 4.15/1.76 4.15/1.76 (8) 4.15/1.76 Obligation: 4.15/1.76 Q restricted rewrite system: 4.15/1.76 The TRS R consists of the following rules: 4.15/1.76 4.15/1.76 U2(w, y, ys') -> U3(ssp(ys', w), y) 4.15/1.76 sub(s(v), s(w)) -> U4(sub(v, w)) 4.15/1.76 U4(z) -> z 4.15/1.76 4.15/1.76 Q is empty. 4.15/1.76 4.15/1.76 ---------------------------------------- 4.15/1.76 4.15/1.76 (9) QTRSRRRProof (EQUIVALENT) 4.15/1.76 Used ordering: 4.15/1.76 Quasi precedence: 4.15/1.76 U2_3 > [U3_2, ssp_2, U4_1] 4.15/1.76 s_1 > sub_2 > [U3_2, ssp_2, U4_1] 4.15/1.76 4.15/1.76 4.15/1.76 Status: 4.15/1.76 U2_3: [2,3,1] 4.15/1.76 U3_2: [1,2] 4.15/1.76 ssp_2: [2,1] 4.15/1.76 sub_2: [1,2] 4.15/1.76 s_1: multiset status 4.15/1.76 U4_1: multiset status 4.15/1.76 4.15/1.76 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: 4.15/1.76 4.15/1.76 U2(w, y, ys') -> U3(ssp(ys', w), y) 4.15/1.76 sub(s(v), s(w)) -> U4(sub(v, w)) 4.15/1.76 U4(z) -> z 4.15/1.76 4.15/1.76 4.15/1.76 4.15/1.76 4.15/1.76 ---------------------------------------- 4.15/1.76 4.15/1.76 (10) 4.15/1.76 Obligation: 4.15/1.76 Q restricted rewrite system: 4.15/1.76 R is empty. 4.15/1.76 Q is empty. 4.15/1.76 4.15/1.76 ---------------------------------------- 4.15/1.76 4.15/1.76 (11) RisEmptyProof (EQUIVALENT) 4.15/1.76 The TRS R is empty. Hence, termination is trivially proven. 4.15/1.76 ---------------------------------------- 4.15/1.76 4.15/1.76 (12) 4.15/1.76 YES 4.15/1.78 EOF