/export/starexec/sandbox2/solver/bin/starexec_run_standard /export/starexec/sandbox2/benchmark/theBenchmark.xml /export/starexec/sandbox2/output/output_files


--------------------------------------------------------------------------------


YES
proof of /export/starexec/sandbox2/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, 61 ms]
(4) QTRS
(5) QTRSRRRProof [EQUIVALENT, 14 ms]
(6) QTRS
(7) QTRSRRRProof [EQUIVALENT, 0 ms]
(8) QTRS
(9) QTRSRRRProof [EQUIVALENT, 2 ms]
(10) QTRS
(11) RisEmptyProof [EQUIVALENT, 0 ms]
(12) YES


----------------------------------------

(0)
Obligation:
Conditional term rewrite system:
The TRS R consists of the following rules:

   ssp(nil, 0) -> nil
   sub(z, 0) -> z

The conditional TRS C consists of the following conditional rules:

   ssp(cons(y, ys'), v) -> xs <= ssp(ys', v) -> xs
   ssp(cons(y, ys'), v) -> cons(y, xs') <= sub(v, y) -> w, ssp(ys', w) -> xs'
   sub(s(v), s(w)) -> z <= sub(v, w) -> z


----------------------------------------

(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, ys'), v) -> U1(ssp(ys', v))
   U1(xs) -> xs
   ssp(cons(y, ys'), v) -> U2(sub(v, y), y, ys')
   U2(w, y, ys') -> U3(ssp(ys', w), y)
   U3(xs', y) -> cons(y, xs')
   sub(s(v), s(w)) -> U4(sub(v, w))
   U4(z) -> z
   ssp(nil, 0) -> nil
   sub(z, 0) -> z

Q is empty.

----------------------------------------

(3) QTRSRRRProof (EQUIVALENT)
Used ordering:
Polynomial interpretation [POLO]:

   POL(0) = 2
   POL(U1(x_1)) = x_1
   POL(U2(x_1, x_2, x_3)) = x_1 + 2*x_2 + 2*x_3
   POL(U3(x_1, x_2)) = x_1 + 2*x_2
   POL(U4(x_1)) = 2*x_1
   POL(cons(x_1, x_2)) = 2*x_1 + x_2
   POL(nil) = 0
   POL(s(x_1)) = 2*x_1
   POL(ssp(x_1, x_2)) = 2*x_1 + x_2
   POL(sub(x_1, x_2)) = x_1 + 2*x_2
With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly:

   ssp(nil, 0) -> nil
   sub(z, 0) -> z




----------------------------------------

(4)
Obligation:
Q restricted rewrite system:
The TRS R consists of the following rules:

   ssp(cons(y, ys'), v) -> U1(ssp(ys', v))
   U1(xs) -> xs
   ssp(cons(y, ys'), v) -> U2(sub(v, y), y, ys')
   U2(w, y, ys') -> U3(ssp(ys', w), y)
   U3(xs', y) -> cons(y, xs')
   sub(s(v), s(w)) -> U4(sub(v, w))
   U4(z) -> z

Q is empty.

----------------------------------------

(5) QTRSRRRProof (EQUIVALENT)
Used ordering:
Polynomial interpretation [POLO]:

   POL(U1(x_1)) = 1 + x_1
   POL(U2(x_1, x_2, x_3)) = 2 + x_1 + x_2 + 2*x_3
   POL(U3(x_1, x_2)) = 2 + x_1 + x_2
   POL(U4(x_1)) = x_1
   POL(cons(x_1, x_2)) = 1 + x_1 + x_2
   POL(s(x_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
With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly:

   ssp(cons(y, ys'), v) -> U1(ssp(ys', v))
   U1(xs) -> xs
   U3(xs', y) -> cons(y, xs')




----------------------------------------

(6)
Obligation:
Q restricted rewrite system:
The TRS R consists of the following rules:

   ssp(cons(y, ys'), v) -> U2(sub(v, y), y, ys')
   U2(w, y, ys') -> U3(ssp(ys', w), y)
   sub(s(v), s(w)) -> U4(sub(v, w))
   U4(z) -> z

Q is empty.

----------------------------------------

(7) QTRSRRRProof (EQUIVALENT)
Used ordering:
Polynomial interpretation [POLO]:

   POL(U2(x_1, x_2, x_3)) = x_1 + 2*x_2 + 2*x_3
   POL(U3(x_1, x_2)) = x_1 + 2*x_2
   POL(U4(x_1)) = x_1
   POL(cons(x_1, x_2)) = 2 + 2*x_1 + 2*x_2
   POL(s(x_1)) = 2*x_1
   POL(ssp(x_1, x_2)) = 2*x_1 + x_2
   POL(sub(x_1, x_2)) = x_1 + 2*x_2
With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly:

   ssp(cons(y, ys'), v) -> U2(sub(v, y), y, ys')




----------------------------------------

(8)
Obligation:
Q restricted rewrite system:
The TRS R consists of the following rules:

   U2(w, y, ys') -> U3(ssp(ys', w), y)
   sub(s(v), s(w)) -> U4(sub(v, w))
   U4(z) -> z

Q is empty.

----------------------------------------

(9) QTRSRRRProof (EQUIVALENT)
Used ordering:
Knuth-Bendix order [KBO] with precedence:sub_2 > U4_1 > s_1 > ssp_2 > U2_3 > U3_2

and weight map:

   s_1=1
   U4_1=2
   U2_3=0
   U3_2=0
   ssp_2=0
   sub_2=0

The variable weight is 1With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly:

   U2(w, y, ys') -> U3(ssp(ys', w), y)
   sub(s(v), s(w)) -> U4(sub(v, w))
   U4(z) -> z




----------------------------------------

(10)
Obligation:
Q restricted rewrite system:
R is empty.
Q is empty.

----------------------------------------

(11) RisEmptyProof (EQUIVALENT)
The TRS R is empty. Hence, termination is trivially proven.
----------------------------------------

(12)
YES