/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: c69e44bd14796315568835c1ffa2502984884775 mhark 20210624 unpublished


Termination of the given CSR could be proven:

(0) CSR
(1) CSRInnermostProof [EQUIVALENT, 0 ms]
(2) CSR
(3) CSDependencyPairsProof [EQUIVALENT, 0 ms]
(4) QCSDP
(5) QCSDependencyGraphProof [EQUIVALENT, 0 ms]
(6) AND
    (7) QCSDP
        (8) QCSDPSubtermProof [EQUIVALENT, 1 ms]
        (9) QCSDP
        (10) PIsEmptyProof [EQUIVALENT, 0 ms]
        (11) YES
    (12) QCSDP
        (13) QCSDPSubtermProof [EQUIVALENT, 0 ms]
        (14) QCSDP
        (15) PIsEmptyProof [EQUIVALENT, 0 ms]
        (16) YES
    (17) QCSDP
        (18) QCSDPSubtermProof [EQUIVALENT, 0 ms]
        (19) QCSDP
        (20) PIsEmptyProof [EQUIVALENT, 0 ms]
        (21) YES
    (22) QCSDP
        (23) QCSDPSubtermProof [EQUIVALENT, 0 ms]
        (24) QCSDP
        (25) PIsEmptyProof [EQUIVALENT, 0 ms]
        (26) YES


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

(0)
Obligation:
Context-sensitive rewrite system:
The TRS R consists of the following rules:

   from(X) -> cons(X, from(s(X)))
   2ndspos(0, Z) -> rnil
   2ndspos(s(N), cons(X, cons(Y, Z))) -> rcons(posrecip(Y), 2ndsneg(N, Z))
   2ndsneg(0, Z) -> rnil
   2ndsneg(s(N), cons(X, cons(Y, Z))) -> rcons(negrecip(Y), 2ndspos(N, Z))
   pi(X) -> 2ndspos(X, from(0))
   plus(0, Y) -> Y
   plus(s(X), Y) -> s(plus(X, Y))
   times(0, Y) -> 0
   times(s(X), Y) -> plus(Y, times(X, Y))
   square(X) -> times(X, X)

The replacement map contains the following entries:

from: {1}
cons: {1}
s: {1}
2ndspos: {1, 2}
0: empty set
rnil: empty set
rcons: {1, 2}
posrecip: {1}
2ndsneg: {1, 2}
negrecip: {1}
pi: {1}
plus: {1, 2}
times: {1, 2}
square: {1}

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

(1) CSRInnermostProof (EQUIVALENT)
The CSR is orthogonal. By [CS_Inn] we can switch to innermost.
----------------------------------------

(2)
Obligation:
Context-sensitive rewrite system:
The TRS R consists of the following rules:

   from(X) -> cons(X, from(s(X)))
   2ndspos(0, Z) -> rnil
   2ndspos(s(N), cons(X, cons(Y, Z))) -> rcons(posrecip(Y), 2ndsneg(N, Z))
   2ndsneg(0, Z) -> rnil
   2ndsneg(s(N), cons(X, cons(Y, Z))) -> rcons(negrecip(Y), 2ndspos(N, Z))
   pi(X) -> 2ndspos(X, from(0))
   plus(0, Y) -> Y
   plus(s(X), Y) -> s(plus(X, Y))
   times(0, Y) -> 0
   times(s(X), Y) -> plus(Y, times(X, Y))
   square(X) -> times(X, X)

The replacement map contains the following entries:

from: {1}
cons: {1}
s: {1}
2ndspos: {1, 2}
0: empty set
rnil: empty set
rcons: {1, 2}
posrecip: {1}
2ndsneg: {1, 2}
negrecip: {1}
pi: {1}
plus: {1, 2}
times: {1, 2}
square: {1}


Innermost Strategy.

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

(3) CSDependencyPairsProof (EQUIVALENT)
Using Improved CS-DPs [LPAR08] we result in the following initial Q-CSDP problem.
----------------------------------------

(4)
Obligation:
Q-restricted context-sensitive dependency pair problem:
The symbols in {from_1, s_1, 2ndspos_2, rcons_2, posrecip_1, 2ndsneg_2, negrecip_1, pi_1, plus_2, times_2, square_1, 2NDSNEG_2, 2NDSPOS_2, PI_1, FROM_1, PLUS_2, TIMES_2, SQUARE_1} are replacing on all positions.
For all symbols f in {cons_2} we have mu(f) = {1}.
The symbols in {U_1} are not replacing on any position.

The ordinary context-sensitive dependency pairs DP_o are:
   2NDSPOS(s(N), cons(X, cons(Y, Z))) -> 2NDSNEG(N, Z)
   2NDSNEG(s(N), cons(X, cons(Y, Z))) -> 2NDSPOS(N, Z)
   PI(X) -> 2NDSPOS(X, from(0))
   PI(X) -> FROM(0)
   PLUS(s(X), Y) -> PLUS(X, Y)
   TIMES(s(X), Y) -> PLUS(Y, times(X, Y))
   TIMES(s(X), Y) -> TIMES(X, Y)
   SQUARE(X) -> TIMES(X, X)

The collapsing dependency pairs are DP_c:
   2NDSPOS(s(N), cons(X, cons(Y, Z))) -> Y
   2NDSPOS(s(N), cons(X, cons(Y, Z))) -> Z
   2NDSNEG(s(N), cons(X, cons(Y, Z))) -> Y
   2NDSNEG(s(N), cons(X, cons(Y, Z))) -> Z


The hidden terms of R are:

   from(s(x0))

Every hiding context is built from:
   aprove.DPFramework.CSDPProblem.QCSDPProblem$1@4961242e
   aprove.DPFramework.CSDPProblem.QCSDPProblem$1@41139c7b

Hence, the new unhiding pairs DP_u are :
   2NDSPOS(s(N), cons(X, cons(Y, Z))) -> U(Y)
   2NDSPOS(s(N), cons(X, cons(Y, Z))) -> U(Z)
   2NDSNEG(s(N), cons(X, cons(Y, Z))) -> U(Y)
   2NDSNEG(s(N), cons(X, cons(Y, Z))) -> U(Z)
   U(s(x_0)) -> U(x_0)
   U(from(x_0)) -> U(x_0)
   U(from(s(x0))) -> FROM(s(x0))

The TRS R consists of the following rules:

   from(X) -> cons(X, from(s(X)))
   2ndspos(0, Z) -> rnil
   2ndspos(s(N), cons(X, cons(Y, Z))) -> rcons(posrecip(Y), 2ndsneg(N, Z))
   2ndsneg(0, Z) -> rnil
   2ndsneg(s(N), cons(X, cons(Y, Z))) -> rcons(negrecip(Y), 2ndspos(N, Z))
   pi(X) -> 2ndspos(X, from(0))
   plus(0, Y) -> Y
   plus(s(X), Y) -> s(plus(X, Y))
   times(0, Y) -> 0
   times(s(X), Y) -> plus(Y, times(X, Y))
   square(X) -> times(X, X)

The set Q consists of the following terms:

   from(x0)
   2ndspos(0, x0)
   2ndspos(s(x0), cons(x1, cons(x2, x3)))
   2ndsneg(0, x0)
   2ndsneg(s(x0), cons(x1, cons(x2, x3)))
   pi(x0)
   plus(0, x0)
   plus(s(x0), x1)
   times(0, x0)
   times(s(x0), x1)
   square(x0)


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

(5) QCSDependencyGraphProof (EQUIVALENT)
The approximation of the Context-Sensitive Dependency Graph [LPAR08] contains 4 SCCs with 7 less nodes.
The rules PI(x0) -> 2NDSPOS(x0, from(0)) and 2NDSPOS(s(z0), cons(z1, cons(z2, z3))) -> 2NDSNEG(z0, z3) form no chain, because ECap^mu_R'(2NDSPOS(s(z0), cons(z1, cons(z2, z3)))) = 2NDSPOS(s(x_1), cons(x_2, cons(z2, z3))) does not unify with 2NDSPOS(x0, from(0)). 
R' = 
   ( cons(X, from(s(X))), from(X))


The rules PI(x0) -> 2NDSPOS(x0, from(0)) and 2NDSPOS(s(z0), cons(z1, cons(z2, z3))) -> U(z2) form no chain, because ECap^mu_R'(2NDSPOS(s(z0), cons(z1, cons(z2, z3)))) = 2NDSPOS(s(x_1), cons(x_2, cons(z2, z3))) does not unify with 2NDSPOS(x0, from(0)). 
R' = 
   ( cons(X, from(s(X))), from(X))


The rules PI(x0) -> 2NDSPOS(x0, from(0)) and 2NDSPOS(s(z0), cons(z1, cons(z2, z3))) -> U(z3) form no chain, because ECap^mu_R'(2NDSPOS(s(z0), cons(z1, cons(z2, z3)))) = 2NDSPOS(s(x_1), cons(x_2, cons(z2, z3))) does not unify with 2NDSPOS(x0, from(0)). 
R' = 
   ( cons(X, from(s(X))), from(X))



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

(6)
Complex Obligation (AND)

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

(7)
Obligation:
Q-restricted context-sensitive dependency pair problem:
The symbols in {from_1, s_1, 2ndspos_2, rcons_2, posrecip_1, 2ndsneg_2, negrecip_1, pi_1, plus_2, times_2, square_1} are replacing on all positions.
For all symbols f in {cons_2} we have mu(f) = {1}.
The symbols in {U_1} are not replacing on any position.

The TRS P consists of the following rules:

   U(s(x_0)) -> U(x_0)
   U(from(x_0)) -> U(x_0)

The TRS R consists of the following rules:

   from(X) -> cons(X, from(s(X)))
   2ndspos(0, Z) -> rnil
   2ndspos(s(N), cons(X, cons(Y, Z))) -> rcons(posrecip(Y), 2ndsneg(N, Z))
   2ndsneg(0, Z) -> rnil
   2ndsneg(s(N), cons(X, cons(Y, Z))) -> rcons(negrecip(Y), 2ndspos(N, Z))
   pi(X) -> 2ndspos(X, from(0))
   plus(0, Y) -> Y
   plus(s(X), Y) -> s(plus(X, Y))
   times(0, Y) -> 0
   times(s(X), Y) -> plus(Y, times(X, Y))
   square(X) -> times(X, X)

The set Q consists of the following terms:

   from(x0)
   2ndspos(0, x0)
   2ndspos(s(x0), cons(x1, cons(x2, x3)))
   2ndsneg(0, x0)
   2ndsneg(s(x0), cons(x1, cons(x2, x3)))
   pi(x0)
   plus(0, x0)
   plus(s(x0), x1)
   times(0, x0)
   times(s(x0), x1)
   square(x0)


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

(8) QCSDPSubtermProof (EQUIVALENT)
We use the subterm processor [DA_EMMES].


The following pairs can be oriented strictly and are deleted.

   U(s(x_0)) -> U(x_0)
   U(from(x_0)) -> U(x_0)
The remaining pairs can at least be oriented weakly.
none
Used ordering:  Combined order from the following AFS and order.
U(x1)  =  x1


Subterm Order

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

(9)
Obligation:
Q-restricted context-sensitive dependency pair problem:
The symbols in {from_1, s_1, 2ndspos_2, rcons_2, posrecip_1, 2ndsneg_2, negrecip_1, pi_1, plus_2, times_2, square_1} are replacing on all positions.
For all symbols f in {cons_2} we have mu(f) = {1}.

The TRS P consists of the following rules:
none

The TRS R consists of the following rules:

   from(X) -> cons(X, from(s(X)))
   2ndspos(0, Z) -> rnil
   2ndspos(s(N), cons(X, cons(Y, Z))) -> rcons(posrecip(Y), 2ndsneg(N, Z))
   2ndsneg(0, Z) -> rnil
   2ndsneg(s(N), cons(X, cons(Y, Z))) -> rcons(negrecip(Y), 2ndspos(N, Z))
   pi(X) -> 2ndspos(X, from(0))
   plus(0, Y) -> Y
   plus(s(X), Y) -> s(plus(X, Y))
   times(0, Y) -> 0
   times(s(X), Y) -> plus(Y, times(X, Y))
   square(X) -> times(X, X)

The set Q consists of the following terms:

   from(x0)
   2ndspos(0, x0)
   2ndspos(s(x0), cons(x1, cons(x2, x3)))
   2ndsneg(0, x0)
   2ndsneg(s(x0), cons(x1, cons(x2, x3)))
   pi(x0)
   plus(0, x0)
   plus(s(x0), x1)
   times(0, x0)
   times(s(x0), x1)
   square(x0)


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

(10) PIsEmptyProof (EQUIVALENT)
The TRS P is empty. Hence, there is no (P,Q,R,mu)-chain.
----------------------------------------

(11)
YES

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

(12)
Obligation:
Q-restricted context-sensitive dependency pair problem:
The symbols in {from_1, s_1, 2ndspos_2, rcons_2, posrecip_1, 2ndsneg_2, negrecip_1, pi_1, plus_2, times_2, square_1, PLUS_2} are replacing on all positions.
For all symbols f in {cons_2} we have mu(f) = {1}.

The TRS P consists of the following rules:

   PLUS(s(X), Y) -> PLUS(X, Y)

The TRS R consists of the following rules:

   from(X) -> cons(X, from(s(X)))
   2ndspos(0, Z) -> rnil
   2ndspos(s(N), cons(X, cons(Y, Z))) -> rcons(posrecip(Y), 2ndsneg(N, Z))
   2ndsneg(0, Z) -> rnil
   2ndsneg(s(N), cons(X, cons(Y, Z))) -> rcons(negrecip(Y), 2ndspos(N, Z))
   pi(X) -> 2ndspos(X, from(0))
   plus(0, Y) -> Y
   plus(s(X), Y) -> s(plus(X, Y))
   times(0, Y) -> 0
   times(s(X), Y) -> plus(Y, times(X, Y))
   square(X) -> times(X, X)

The set Q consists of the following terms:

   from(x0)
   2ndspos(0, x0)
   2ndspos(s(x0), cons(x1, cons(x2, x3)))
   2ndsneg(0, x0)
   2ndsneg(s(x0), cons(x1, cons(x2, x3)))
   pi(x0)
   plus(0, x0)
   plus(s(x0), x1)
   times(0, x0)
   times(s(x0), x1)
   square(x0)


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

(13) QCSDPSubtermProof (EQUIVALENT)
We use the subterm processor [DA_EMMES].


The following pairs can be oriented strictly and are deleted.

   PLUS(s(X), Y) -> PLUS(X, Y)
The remaining pairs can at least be oriented weakly.
none
Used ordering:  Combined order from the following AFS and order.
PLUS(x1, x2)  =  x1


Subterm Order

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

(14)
Obligation:
Q-restricted context-sensitive dependency pair problem:
The symbols in {from_1, s_1, 2ndspos_2, rcons_2, posrecip_1, 2ndsneg_2, negrecip_1, pi_1, plus_2, times_2, square_1} are replacing on all positions.
For all symbols f in {cons_2} we have mu(f) = {1}.

The TRS P consists of the following rules:
none

The TRS R consists of the following rules:

   from(X) -> cons(X, from(s(X)))
   2ndspos(0, Z) -> rnil
   2ndspos(s(N), cons(X, cons(Y, Z))) -> rcons(posrecip(Y), 2ndsneg(N, Z))
   2ndsneg(0, Z) -> rnil
   2ndsneg(s(N), cons(X, cons(Y, Z))) -> rcons(negrecip(Y), 2ndspos(N, Z))
   pi(X) -> 2ndspos(X, from(0))
   plus(0, Y) -> Y
   plus(s(X), Y) -> s(plus(X, Y))
   times(0, Y) -> 0
   times(s(X), Y) -> plus(Y, times(X, Y))
   square(X) -> times(X, X)

The set Q consists of the following terms:

   from(x0)
   2ndspos(0, x0)
   2ndspos(s(x0), cons(x1, cons(x2, x3)))
   2ndsneg(0, x0)
   2ndsneg(s(x0), cons(x1, cons(x2, x3)))
   pi(x0)
   plus(0, x0)
   plus(s(x0), x1)
   times(0, x0)
   times(s(x0), x1)
   square(x0)


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

(15) PIsEmptyProof (EQUIVALENT)
The TRS P is empty. Hence, there is no (P,Q,R,mu)-chain.
----------------------------------------

(16)
YES

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

(17)
Obligation:
Q-restricted context-sensitive dependency pair problem:
The symbols in {from_1, s_1, 2ndspos_2, rcons_2, posrecip_1, 2ndsneg_2, negrecip_1, pi_1, plus_2, times_2, square_1, TIMES_2} are replacing on all positions.
For all symbols f in {cons_2} we have mu(f) = {1}.

The TRS P consists of the following rules:

   TIMES(s(X), Y) -> TIMES(X, Y)

The TRS R consists of the following rules:

   from(X) -> cons(X, from(s(X)))
   2ndspos(0, Z) -> rnil
   2ndspos(s(N), cons(X, cons(Y, Z))) -> rcons(posrecip(Y), 2ndsneg(N, Z))
   2ndsneg(0, Z) -> rnil
   2ndsneg(s(N), cons(X, cons(Y, Z))) -> rcons(negrecip(Y), 2ndspos(N, Z))
   pi(X) -> 2ndspos(X, from(0))
   plus(0, Y) -> Y
   plus(s(X), Y) -> s(plus(X, Y))
   times(0, Y) -> 0
   times(s(X), Y) -> plus(Y, times(X, Y))
   square(X) -> times(X, X)

The set Q consists of the following terms:

   from(x0)
   2ndspos(0, x0)
   2ndspos(s(x0), cons(x1, cons(x2, x3)))
   2ndsneg(0, x0)
   2ndsneg(s(x0), cons(x1, cons(x2, x3)))
   pi(x0)
   plus(0, x0)
   plus(s(x0), x1)
   times(0, x0)
   times(s(x0), x1)
   square(x0)


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

(18) QCSDPSubtermProof (EQUIVALENT)
We use the subterm processor [DA_EMMES].


The following pairs can be oriented strictly and are deleted.

   TIMES(s(X), Y) -> TIMES(X, Y)
The remaining pairs can at least be oriented weakly.
none
Used ordering:  Combined order from the following AFS and order.
TIMES(x1, x2)  =  x1


Subterm Order

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

(19)
Obligation:
Q-restricted context-sensitive dependency pair problem:
The symbols in {from_1, s_1, 2ndspos_2, rcons_2, posrecip_1, 2ndsneg_2, negrecip_1, pi_1, plus_2, times_2, square_1} are replacing on all positions.
For all symbols f in {cons_2} we have mu(f) = {1}.

The TRS P consists of the following rules:
none

The TRS R consists of the following rules:

   from(X) -> cons(X, from(s(X)))
   2ndspos(0, Z) -> rnil
   2ndspos(s(N), cons(X, cons(Y, Z))) -> rcons(posrecip(Y), 2ndsneg(N, Z))
   2ndsneg(0, Z) -> rnil
   2ndsneg(s(N), cons(X, cons(Y, Z))) -> rcons(negrecip(Y), 2ndspos(N, Z))
   pi(X) -> 2ndspos(X, from(0))
   plus(0, Y) -> Y
   plus(s(X), Y) -> s(plus(X, Y))
   times(0, Y) -> 0
   times(s(X), Y) -> plus(Y, times(X, Y))
   square(X) -> times(X, X)

The set Q consists of the following terms:

   from(x0)
   2ndspos(0, x0)
   2ndspos(s(x0), cons(x1, cons(x2, x3)))
   2ndsneg(0, x0)
   2ndsneg(s(x0), cons(x1, cons(x2, x3)))
   pi(x0)
   plus(0, x0)
   plus(s(x0), x1)
   times(0, x0)
   times(s(x0), x1)
   square(x0)


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

(20) PIsEmptyProof (EQUIVALENT)
The TRS P is empty. Hence, there is no (P,Q,R,mu)-chain.
----------------------------------------

(21)
YES

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

(22)
Obligation:
Q-restricted context-sensitive dependency pair problem:
The symbols in {from_1, s_1, 2ndspos_2, rcons_2, posrecip_1, 2ndsneg_2, negrecip_1, pi_1, plus_2, times_2, square_1, 2NDSPOS_2, 2NDSNEG_2} are replacing on all positions.
For all symbols f in {cons_2} we have mu(f) = {1}.

The TRS P consists of the following rules:

   2NDSNEG(s(N), cons(X, cons(Y, Z))) -> 2NDSPOS(N, Z)
   2NDSPOS(s(N), cons(X, cons(Y, Z))) -> 2NDSNEG(N, Z)

The TRS R consists of the following rules:

   from(X) -> cons(X, from(s(X)))
   2ndspos(0, Z) -> rnil
   2ndspos(s(N), cons(X, cons(Y, Z))) -> rcons(posrecip(Y), 2ndsneg(N, Z))
   2ndsneg(0, Z) -> rnil
   2ndsneg(s(N), cons(X, cons(Y, Z))) -> rcons(negrecip(Y), 2ndspos(N, Z))
   pi(X) -> 2ndspos(X, from(0))
   plus(0, Y) -> Y
   plus(s(X), Y) -> s(plus(X, Y))
   times(0, Y) -> 0
   times(s(X), Y) -> plus(Y, times(X, Y))
   square(X) -> times(X, X)

The set Q consists of the following terms:

   from(x0)
   2ndspos(0, x0)
   2ndspos(s(x0), cons(x1, cons(x2, x3)))
   2ndsneg(0, x0)
   2ndsneg(s(x0), cons(x1, cons(x2, x3)))
   pi(x0)
   plus(0, x0)
   plus(s(x0), x1)
   times(0, x0)
   times(s(x0), x1)
   square(x0)


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

(23) QCSDPSubtermProof (EQUIVALENT)
We use the subterm processor [DA_EMMES].


The following pairs can be oriented strictly and are deleted.

   2NDSNEG(s(N), cons(X, cons(Y, Z))) -> 2NDSPOS(N, Z)
   2NDSPOS(s(N), cons(X, cons(Y, Z))) -> 2NDSNEG(N, Z)
The remaining pairs can at least be oriented weakly.
none
Used ordering:  Combined order from the following AFS and order.
2NDSPOS(x1, x2)  =  x1

2NDSNEG(x1, x2)  =  x1


Subterm Order

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

(24)
Obligation:
Q-restricted context-sensitive dependency pair problem:
The symbols in {from_1, s_1, 2ndspos_2, rcons_2, posrecip_1, 2ndsneg_2, negrecip_1, pi_1, plus_2, times_2, square_1} are replacing on all positions.
For all symbols f in {cons_2} we have mu(f) = {1}.

The TRS P consists of the following rules:
none

The TRS R consists of the following rules:

   from(X) -> cons(X, from(s(X)))
   2ndspos(0, Z) -> rnil
   2ndspos(s(N), cons(X, cons(Y, Z))) -> rcons(posrecip(Y), 2ndsneg(N, Z))
   2ndsneg(0, Z) -> rnil
   2ndsneg(s(N), cons(X, cons(Y, Z))) -> rcons(negrecip(Y), 2ndspos(N, Z))
   pi(X) -> 2ndspos(X, from(0))
   plus(0, Y) -> Y
   plus(s(X), Y) -> s(plus(X, Y))
   times(0, Y) -> 0
   times(s(X), Y) -> plus(Y, times(X, Y))
   square(X) -> times(X, X)

The set Q consists of the following terms:

   from(x0)
   2ndspos(0, x0)
   2ndspos(s(x0), cons(x1, cons(x2, x3)))
   2ndsneg(0, x0)
   2ndsneg(s(x0), cons(x1, cons(x2, x3)))
   pi(x0)
   plus(0, x0)
   plus(s(x0), x1)
   times(0, x0)
   times(s(x0), x1)
   square(x0)


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

(25) PIsEmptyProof (EQUIVALENT)
The TRS P is empty. Hence, there is no (P,Q,R,mu)-chain.
----------------------------------------

(26)
YES