/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: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty


Termination w.r.t. Q of the given QTRS could be proven:

(0) QTRS
(1) Overlay + Local Confluence [EQUIVALENT, 0 ms]
(2) QTRS
(3) DependencyPairsProof [EQUIVALENT, 18 ms]
(4) QDP
(5) DependencyGraphProof [EQUIVALENT, 0 ms]
(6) AND
    (7) QDP
        (8) UsableRulesProof [EQUIVALENT, 0 ms]
        (9) QDP
        (10) QReductionProof [EQUIVALENT, 0 ms]
        (11) QDP
        (12) QDPSizeChangeProof [EQUIVALENT, 0 ms]
        (13) YES
    (14) QDP
        (15) UsableRulesProof [EQUIVALENT, 0 ms]
        (16) QDP
        (17) QReductionProof [EQUIVALENT, 0 ms]
        (18) QDP
        (19) QDPSizeChangeProof [EQUIVALENT, 0 ms]
        (20) YES
    (21) QDP
        (22) UsableRulesProof [EQUIVALENT, 0 ms]
        (23) QDP
        (24) QReductionProof [EQUIVALENT, 0 ms]
        (25) QDP
        (26) QDPSizeChangeProof [EQUIVALENT, 0 ms]
        (27) YES
    (28) QDP
        (29) UsableRulesProof [EQUIVALENT, 0 ms]
        (30) QDP
        (31) QReductionProof [EQUIVALENT, 0 ms]
        (32) QDP
        (33) QDPSizeChangeProof [EQUIVALENT, 0 ms]
        (34) YES
    (35) QDP
        (36) UsableRulesProof [EQUIVALENT, 0 ms]
        (37) QDP
        (38) QReductionProof [EQUIVALENT, 0 ms]
        (39) QDP
        (40) NonInfProof [EQUIVALENT, 101 ms]
        (41) QDP
        (42) DependencyGraphProof [EQUIVALENT, 0 ms]
        (43) TRUE


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

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

   sort(l) -> st(0, l)
   st(n, l) -> cond1(member(n, l), n, l)
   cond1(true, n, l) -> cons(n, st(s(n), l))
   cond1(false, n, l) -> cond2(gt(n, max(l)), n, l)
   cond2(true, n, l) -> nil
   cond2(false, n, l) -> st(s(n), l)
   member(n, nil) -> false
   member(n, cons(m, l)) -> or(equal(n, m), member(n, l))
   or(x, true) -> true
   or(x, false) -> x
   equal(0, 0) -> true
   equal(s(x), 0) -> false
   equal(0, s(y)) -> false
   equal(s(x), s(y)) -> equal(x, y)
   gt(0, v) -> false
   gt(s(u), 0) -> true
   gt(s(u), s(v)) -> gt(u, v)
   max(nil) -> 0
   max(cons(u, l)) -> if(gt(u, max(l)), u, max(l))
   if(true, u, v) -> u
   if(false, u, v) -> v

Q is empty.

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

(1) Overlay + Local Confluence (EQUIVALENT)
The TRS is overlay and locally confluent. By [NOC] we can switch to innermost.
----------------------------------------

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

   sort(l) -> st(0, l)
   st(n, l) -> cond1(member(n, l), n, l)
   cond1(true, n, l) -> cons(n, st(s(n), l))
   cond1(false, n, l) -> cond2(gt(n, max(l)), n, l)
   cond2(true, n, l) -> nil
   cond2(false, n, l) -> st(s(n), l)
   member(n, nil) -> false
   member(n, cons(m, l)) -> or(equal(n, m), member(n, l))
   or(x, true) -> true
   or(x, false) -> x
   equal(0, 0) -> true
   equal(s(x), 0) -> false
   equal(0, s(y)) -> false
   equal(s(x), s(y)) -> equal(x, y)
   gt(0, v) -> false
   gt(s(u), 0) -> true
   gt(s(u), s(v)) -> gt(u, v)
   max(nil) -> 0
   max(cons(u, l)) -> if(gt(u, max(l)), u, max(l))
   if(true, u, v) -> u
   if(false, u, v) -> v

The set Q consists of the following terms:

   sort(x0)
   st(x0, x1)
   cond1(true, x0, x1)
   cond1(false, x0, x1)
   cond2(true, x0, x1)
   cond2(false, x0, x1)
   member(x0, nil)
   member(x0, cons(x1, x2))
   or(x0, true)
   or(x0, false)
   equal(0, 0)
   equal(s(x0), 0)
   equal(0, s(x0))
   equal(s(x0), s(x1))
   gt(0, x0)
   gt(s(x0), 0)
   gt(s(x0), s(x1))
   max(nil)
   max(cons(x0, x1))
   if(true, x0, x1)
   if(false, x0, x1)


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

(3) DependencyPairsProof (EQUIVALENT)
Using Dependency Pairs [AG00,LPAR04] we result in the following initial DP problem.
----------------------------------------

(4)
Obligation:
Q DP problem:
The TRS P consists of the following rules:

   SORT(l) -> ST(0, l)
   ST(n, l) -> COND1(member(n, l), n, l)
   ST(n, l) -> MEMBER(n, l)
   COND1(true, n, l) -> ST(s(n), l)
   COND1(false, n, l) -> COND2(gt(n, max(l)), n, l)
   COND1(false, n, l) -> GT(n, max(l))
   COND1(false, n, l) -> MAX(l)
   COND2(false, n, l) -> ST(s(n), l)
   MEMBER(n, cons(m, l)) -> OR(equal(n, m), member(n, l))
   MEMBER(n, cons(m, l)) -> EQUAL(n, m)
   MEMBER(n, cons(m, l)) -> MEMBER(n, l)
   EQUAL(s(x), s(y)) -> EQUAL(x, y)
   GT(s(u), s(v)) -> GT(u, v)
   MAX(cons(u, l)) -> IF(gt(u, max(l)), u, max(l))
   MAX(cons(u, l)) -> GT(u, max(l))
   MAX(cons(u, l)) -> MAX(l)

The TRS R consists of the following rules:

   sort(l) -> st(0, l)
   st(n, l) -> cond1(member(n, l), n, l)
   cond1(true, n, l) -> cons(n, st(s(n), l))
   cond1(false, n, l) -> cond2(gt(n, max(l)), n, l)
   cond2(true, n, l) -> nil
   cond2(false, n, l) -> st(s(n), l)
   member(n, nil) -> false
   member(n, cons(m, l)) -> or(equal(n, m), member(n, l))
   or(x, true) -> true
   or(x, false) -> x
   equal(0, 0) -> true
   equal(s(x), 0) -> false
   equal(0, s(y)) -> false
   equal(s(x), s(y)) -> equal(x, y)
   gt(0, v) -> false
   gt(s(u), 0) -> true
   gt(s(u), s(v)) -> gt(u, v)
   max(nil) -> 0
   max(cons(u, l)) -> if(gt(u, max(l)), u, max(l))
   if(true, u, v) -> u
   if(false, u, v) -> v

The set Q consists of the following terms:

   sort(x0)
   st(x0, x1)
   cond1(true, x0, x1)
   cond1(false, x0, x1)
   cond2(true, x0, x1)
   cond2(false, x0, x1)
   member(x0, nil)
   member(x0, cons(x1, x2))
   or(x0, true)
   or(x0, false)
   equal(0, 0)
   equal(s(x0), 0)
   equal(0, s(x0))
   equal(s(x0), s(x1))
   gt(0, x0)
   gt(s(x0), 0)
   gt(s(x0), s(x1))
   max(nil)
   max(cons(x0, x1))
   if(true, x0, x1)
   if(false, x0, x1)

We have to consider all minimal (P,Q,R)-chains.
----------------------------------------

(5) DependencyGraphProof (EQUIVALENT)
The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 5 SCCs with 8 less nodes.
----------------------------------------

(6)
Complex Obligation (AND)

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

(7)
Obligation:
Q DP problem:
The TRS P consists of the following rules:

   GT(s(u), s(v)) -> GT(u, v)

The TRS R consists of the following rules:

   sort(l) -> st(0, l)
   st(n, l) -> cond1(member(n, l), n, l)
   cond1(true, n, l) -> cons(n, st(s(n), l))
   cond1(false, n, l) -> cond2(gt(n, max(l)), n, l)
   cond2(true, n, l) -> nil
   cond2(false, n, l) -> st(s(n), l)
   member(n, nil) -> false
   member(n, cons(m, l)) -> or(equal(n, m), member(n, l))
   or(x, true) -> true
   or(x, false) -> x
   equal(0, 0) -> true
   equal(s(x), 0) -> false
   equal(0, s(y)) -> false
   equal(s(x), s(y)) -> equal(x, y)
   gt(0, v) -> false
   gt(s(u), 0) -> true
   gt(s(u), s(v)) -> gt(u, v)
   max(nil) -> 0
   max(cons(u, l)) -> if(gt(u, max(l)), u, max(l))
   if(true, u, v) -> u
   if(false, u, v) -> v

The set Q consists of the following terms:

   sort(x0)
   st(x0, x1)
   cond1(true, x0, x1)
   cond1(false, x0, x1)
   cond2(true, x0, x1)
   cond2(false, x0, x1)
   member(x0, nil)
   member(x0, cons(x1, x2))
   or(x0, true)
   or(x0, false)
   equal(0, 0)
   equal(s(x0), 0)
   equal(0, s(x0))
   equal(s(x0), s(x1))
   gt(0, x0)
   gt(s(x0), 0)
   gt(s(x0), s(x1))
   max(nil)
   max(cons(x0, x1))
   if(true, x0, x1)
   if(false, x0, x1)

We have to consider all minimal (P,Q,R)-chains.
----------------------------------------

(8) UsableRulesProof (EQUIVALENT)
As all Q-normal forms are R-normal forms we are in the innermost case. Hence, by the usable rules processor [LPAR04] we can delete all non-usable rules [FROCOS05] from R.
----------------------------------------

(9)
Obligation:
Q DP problem:
The TRS P consists of the following rules:

   GT(s(u), s(v)) -> GT(u, v)

R is empty.
The set Q consists of the following terms:

   sort(x0)
   st(x0, x1)
   cond1(true, x0, x1)
   cond1(false, x0, x1)
   cond2(true, x0, x1)
   cond2(false, x0, x1)
   member(x0, nil)
   member(x0, cons(x1, x2))
   or(x0, true)
   or(x0, false)
   equal(0, 0)
   equal(s(x0), 0)
   equal(0, s(x0))
   equal(s(x0), s(x1))
   gt(0, x0)
   gt(s(x0), 0)
   gt(s(x0), s(x1))
   max(nil)
   max(cons(x0, x1))
   if(true, x0, x1)
   if(false, x0, x1)

We have to consider all minimal (P,Q,R)-chains.
----------------------------------------

(10) QReductionProof (EQUIVALENT)
We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN].

   sort(x0)
   st(x0, x1)
   cond1(true, x0, x1)
   cond1(false, x0, x1)
   cond2(true, x0, x1)
   cond2(false, x0, x1)
   member(x0, nil)
   member(x0, cons(x1, x2))
   or(x0, true)
   or(x0, false)
   equal(0, 0)
   equal(s(x0), 0)
   equal(0, s(x0))
   equal(s(x0), s(x1))
   gt(0, x0)
   gt(s(x0), 0)
   gt(s(x0), s(x1))
   max(nil)
   max(cons(x0, x1))
   if(true, x0, x1)
   if(false, x0, x1)


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

(11)
Obligation:
Q DP problem:
The TRS P consists of the following rules:

   GT(s(u), s(v)) -> GT(u, v)

R is empty.
Q is empty.
We have to consider all minimal (P,Q,R)-chains.
----------------------------------------

(12) 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:
*GT(s(u), s(v)) -> GT(u, v)
The graph contains the following edges 1 > 1, 2 > 2


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

(13)
YES

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

(14)
Obligation:
Q DP problem:
The TRS P consists of the following rules:

   MAX(cons(u, l)) -> MAX(l)

The TRS R consists of the following rules:

   sort(l) -> st(0, l)
   st(n, l) -> cond1(member(n, l), n, l)
   cond1(true, n, l) -> cons(n, st(s(n), l))
   cond1(false, n, l) -> cond2(gt(n, max(l)), n, l)
   cond2(true, n, l) -> nil
   cond2(false, n, l) -> st(s(n), l)
   member(n, nil) -> false
   member(n, cons(m, l)) -> or(equal(n, m), member(n, l))
   or(x, true) -> true
   or(x, false) -> x
   equal(0, 0) -> true
   equal(s(x), 0) -> false
   equal(0, s(y)) -> false
   equal(s(x), s(y)) -> equal(x, y)
   gt(0, v) -> false
   gt(s(u), 0) -> true
   gt(s(u), s(v)) -> gt(u, v)
   max(nil) -> 0
   max(cons(u, l)) -> if(gt(u, max(l)), u, max(l))
   if(true, u, v) -> u
   if(false, u, v) -> v

The set Q consists of the following terms:

   sort(x0)
   st(x0, x1)
   cond1(true, x0, x1)
   cond1(false, x0, x1)
   cond2(true, x0, x1)
   cond2(false, x0, x1)
   member(x0, nil)
   member(x0, cons(x1, x2))
   or(x0, true)
   or(x0, false)
   equal(0, 0)
   equal(s(x0), 0)
   equal(0, s(x0))
   equal(s(x0), s(x1))
   gt(0, x0)
   gt(s(x0), 0)
   gt(s(x0), s(x1))
   max(nil)
   max(cons(x0, x1))
   if(true, x0, x1)
   if(false, x0, x1)

We have to consider all minimal (P,Q,R)-chains.
----------------------------------------

(15) UsableRulesProof (EQUIVALENT)
As all Q-normal forms are R-normal forms we are in the innermost case. Hence, by the usable rules processor [LPAR04] we can delete all non-usable rules [FROCOS05] from R.
----------------------------------------

(16)
Obligation:
Q DP problem:
The TRS P consists of the following rules:

   MAX(cons(u, l)) -> MAX(l)

R is empty.
The set Q consists of the following terms:

   sort(x0)
   st(x0, x1)
   cond1(true, x0, x1)
   cond1(false, x0, x1)
   cond2(true, x0, x1)
   cond2(false, x0, x1)
   member(x0, nil)
   member(x0, cons(x1, x2))
   or(x0, true)
   or(x0, false)
   equal(0, 0)
   equal(s(x0), 0)
   equal(0, s(x0))
   equal(s(x0), s(x1))
   gt(0, x0)
   gt(s(x0), 0)
   gt(s(x0), s(x1))
   max(nil)
   max(cons(x0, x1))
   if(true, x0, x1)
   if(false, x0, x1)

We have to consider all minimal (P,Q,R)-chains.
----------------------------------------

(17) QReductionProof (EQUIVALENT)
We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN].

   sort(x0)
   st(x0, x1)
   cond1(true, x0, x1)
   cond1(false, x0, x1)
   cond2(true, x0, x1)
   cond2(false, x0, x1)
   member(x0, nil)
   member(x0, cons(x1, x2))
   or(x0, true)
   or(x0, false)
   equal(0, 0)
   equal(s(x0), 0)
   equal(0, s(x0))
   equal(s(x0), s(x1))
   gt(0, x0)
   gt(s(x0), 0)
   gt(s(x0), s(x1))
   max(nil)
   max(cons(x0, x1))
   if(true, x0, x1)
   if(false, x0, x1)


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

(18)
Obligation:
Q DP problem:
The TRS P consists of the following rules:

   MAX(cons(u, l)) -> MAX(l)

R is empty.
Q is empty.
We have to consider all minimal (P,Q,R)-chains.
----------------------------------------

(19) 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:
*MAX(cons(u, l)) -> MAX(l)
The graph contains the following edges 1 > 1


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

(20)
YES

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

(21)
Obligation:
Q DP problem:
The TRS P consists of the following rules:

   EQUAL(s(x), s(y)) -> EQUAL(x, y)

The TRS R consists of the following rules:

   sort(l) -> st(0, l)
   st(n, l) -> cond1(member(n, l), n, l)
   cond1(true, n, l) -> cons(n, st(s(n), l))
   cond1(false, n, l) -> cond2(gt(n, max(l)), n, l)
   cond2(true, n, l) -> nil
   cond2(false, n, l) -> st(s(n), l)
   member(n, nil) -> false
   member(n, cons(m, l)) -> or(equal(n, m), member(n, l))
   or(x, true) -> true
   or(x, false) -> x
   equal(0, 0) -> true
   equal(s(x), 0) -> false
   equal(0, s(y)) -> false
   equal(s(x), s(y)) -> equal(x, y)
   gt(0, v) -> false
   gt(s(u), 0) -> true
   gt(s(u), s(v)) -> gt(u, v)
   max(nil) -> 0
   max(cons(u, l)) -> if(gt(u, max(l)), u, max(l))
   if(true, u, v) -> u
   if(false, u, v) -> v

The set Q consists of the following terms:

   sort(x0)
   st(x0, x1)
   cond1(true, x0, x1)
   cond1(false, x0, x1)
   cond2(true, x0, x1)
   cond2(false, x0, x1)
   member(x0, nil)
   member(x0, cons(x1, x2))
   or(x0, true)
   or(x0, false)
   equal(0, 0)
   equal(s(x0), 0)
   equal(0, s(x0))
   equal(s(x0), s(x1))
   gt(0, x0)
   gt(s(x0), 0)
   gt(s(x0), s(x1))
   max(nil)
   max(cons(x0, x1))
   if(true, x0, x1)
   if(false, x0, x1)

We have to consider all minimal (P,Q,R)-chains.
----------------------------------------

(22) UsableRulesProof (EQUIVALENT)
As all Q-normal forms are R-normal forms we are in the innermost case. Hence, by the usable rules processor [LPAR04] we can delete all non-usable rules [FROCOS05] from R.
----------------------------------------

(23)
Obligation:
Q DP problem:
The TRS P consists of the following rules:

   EQUAL(s(x), s(y)) -> EQUAL(x, y)

R is empty.
The set Q consists of the following terms:

   sort(x0)
   st(x0, x1)
   cond1(true, x0, x1)
   cond1(false, x0, x1)
   cond2(true, x0, x1)
   cond2(false, x0, x1)
   member(x0, nil)
   member(x0, cons(x1, x2))
   or(x0, true)
   or(x0, false)
   equal(0, 0)
   equal(s(x0), 0)
   equal(0, s(x0))
   equal(s(x0), s(x1))
   gt(0, x0)
   gt(s(x0), 0)
   gt(s(x0), s(x1))
   max(nil)
   max(cons(x0, x1))
   if(true, x0, x1)
   if(false, x0, x1)

We have to consider all minimal (P,Q,R)-chains.
----------------------------------------

(24) QReductionProof (EQUIVALENT)
We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN].

   sort(x0)
   st(x0, x1)
   cond1(true, x0, x1)
   cond1(false, x0, x1)
   cond2(true, x0, x1)
   cond2(false, x0, x1)
   member(x0, nil)
   member(x0, cons(x1, x2))
   or(x0, true)
   or(x0, false)
   equal(0, 0)
   equal(s(x0), 0)
   equal(0, s(x0))
   equal(s(x0), s(x1))
   gt(0, x0)
   gt(s(x0), 0)
   gt(s(x0), s(x1))
   max(nil)
   max(cons(x0, x1))
   if(true, x0, x1)
   if(false, x0, x1)


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

(25)
Obligation:
Q DP problem:
The TRS P consists of the following rules:

   EQUAL(s(x), s(y)) -> EQUAL(x, y)

R is empty.
Q is empty.
We have to consider all minimal (P,Q,R)-chains.
----------------------------------------

(26) 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:
*EQUAL(s(x), s(y)) -> EQUAL(x, y)
The graph contains the following edges 1 > 1, 2 > 2


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

(27)
YES

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

(28)
Obligation:
Q DP problem:
The TRS P consists of the following rules:

   MEMBER(n, cons(m, l)) -> MEMBER(n, l)

The TRS R consists of the following rules:

   sort(l) -> st(0, l)
   st(n, l) -> cond1(member(n, l), n, l)
   cond1(true, n, l) -> cons(n, st(s(n), l))
   cond1(false, n, l) -> cond2(gt(n, max(l)), n, l)
   cond2(true, n, l) -> nil
   cond2(false, n, l) -> st(s(n), l)
   member(n, nil) -> false
   member(n, cons(m, l)) -> or(equal(n, m), member(n, l))
   or(x, true) -> true
   or(x, false) -> x
   equal(0, 0) -> true
   equal(s(x), 0) -> false
   equal(0, s(y)) -> false
   equal(s(x), s(y)) -> equal(x, y)
   gt(0, v) -> false
   gt(s(u), 0) -> true
   gt(s(u), s(v)) -> gt(u, v)
   max(nil) -> 0
   max(cons(u, l)) -> if(gt(u, max(l)), u, max(l))
   if(true, u, v) -> u
   if(false, u, v) -> v

The set Q consists of the following terms:

   sort(x0)
   st(x0, x1)
   cond1(true, x0, x1)
   cond1(false, x0, x1)
   cond2(true, x0, x1)
   cond2(false, x0, x1)
   member(x0, nil)
   member(x0, cons(x1, x2))
   or(x0, true)
   or(x0, false)
   equal(0, 0)
   equal(s(x0), 0)
   equal(0, s(x0))
   equal(s(x0), s(x1))
   gt(0, x0)
   gt(s(x0), 0)
   gt(s(x0), s(x1))
   max(nil)
   max(cons(x0, x1))
   if(true, x0, x1)
   if(false, x0, x1)

We have to consider all minimal (P,Q,R)-chains.
----------------------------------------

(29) UsableRulesProof (EQUIVALENT)
As all Q-normal forms are R-normal forms we are in the innermost case. Hence, by the usable rules processor [LPAR04] we can delete all non-usable rules [FROCOS05] from R.
----------------------------------------

(30)
Obligation:
Q DP problem:
The TRS P consists of the following rules:

   MEMBER(n, cons(m, l)) -> MEMBER(n, l)

R is empty.
The set Q consists of the following terms:

   sort(x0)
   st(x0, x1)
   cond1(true, x0, x1)
   cond1(false, x0, x1)
   cond2(true, x0, x1)
   cond2(false, x0, x1)
   member(x0, nil)
   member(x0, cons(x1, x2))
   or(x0, true)
   or(x0, false)
   equal(0, 0)
   equal(s(x0), 0)
   equal(0, s(x0))
   equal(s(x0), s(x1))
   gt(0, x0)
   gt(s(x0), 0)
   gt(s(x0), s(x1))
   max(nil)
   max(cons(x0, x1))
   if(true, x0, x1)
   if(false, x0, x1)

We have to consider all minimal (P,Q,R)-chains.
----------------------------------------

(31) QReductionProof (EQUIVALENT)
We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN].

   sort(x0)
   st(x0, x1)
   cond1(true, x0, x1)
   cond1(false, x0, x1)
   cond2(true, x0, x1)
   cond2(false, x0, x1)
   member(x0, nil)
   member(x0, cons(x1, x2))
   or(x0, true)
   or(x0, false)
   equal(0, 0)
   equal(s(x0), 0)
   equal(0, s(x0))
   equal(s(x0), s(x1))
   gt(0, x0)
   gt(s(x0), 0)
   gt(s(x0), s(x1))
   max(nil)
   max(cons(x0, x1))
   if(true, x0, x1)
   if(false, x0, x1)


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

(32)
Obligation:
Q DP problem:
The TRS P consists of the following rules:

   MEMBER(n, cons(m, l)) -> MEMBER(n, l)

R is empty.
Q is empty.
We have to consider all minimal (P,Q,R)-chains.
----------------------------------------

(33) 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:
*MEMBER(n, cons(m, l)) -> MEMBER(n, l)
The graph contains the following edges 1 >= 1, 2 > 2


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

(34)
YES

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

(35)
Obligation:
Q DP problem:
The TRS P consists of the following rules:

   COND1(true, n, l) -> ST(s(n), l)
   ST(n, l) -> COND1(member(n, l), n, l)
   COND1(false, n, l) -> COND2(gt(n, max(l)), n, l)
   COND2(false, n, l) -> ST(s(n), l)

The TRS R consists of the following rules:

   sort(l) -> st(0, l)
   st(n, l) -> cond1(member(n, l), n, l)
   cond1(true, n, l) -> cons(n, st(s(n), l))
   cond1(false, n, l) -> cond2(gt(n, max(l)), n, l)
   cond2(true, n, l) -> nil
   cond2(false, n, l) -> st(s(n), l)
   member(n, nil) -> false
   member(n, cons(m, l)) -> or(equal(n, m), member(n, l))
   or(x, true) -> true
   or(x, false) -> x
   equal(0, 0) -> true
   equal(s(x), 0) -> false
   equal(0, s(y)) -> false
   equal(s(x), s(y)) -> equal(x, y)
   gt(0, v) -> false
   gt(s(u), 0) -> true
   gt(s(u), s(v)) -> gt(u, v)
   max(nil) -> 0
   max(cons(u, l)) -> if(gt(u, max(l)), u, max(l))
   if(true, u, v) -> u
   if(false, u, v) -> v

The set Q consists of the following terms:

   sort(x0)
   st(x0, x1)
   cond1(true, x0, x1)
   cond1(false, x0, x1)
   cond2(true, x0, x1)
   cond2(false, x0, x1)
   member(x0, nil)
   member(x0, cons(x1, x2))
   or(x0, true)
   or(x0, false)
   equal(0, 0)
   equal(s(x0), 0)
   equal(0, s(x0))
   equal(s(x0), s(x1))
   gt(0, x0)
   gt(s(x0), 0)
   gt(s(x0), s(x1))
   max(nil)
   max(cons(x0, x1))
   if(true, x0, x1)
   if(false, x0, x1)

We have to consider all minimal (P,Q,R)-chains.
----------------------------------------

(36) UsableRulesProof (EQUIVALENT)
As all Q-normal forms are R-normal forms we are in the innermost case. Hence, by the usable rules processor [LPAR04] we can delete all non-usable rules [FROCOS05] from R.
----------------------------------------

(37)
Obligation:
Q DP problem:
The TRS P consists of the following rules:

   COND1(true, n, l) -> ST(s(n), l)
   ST(n, l) -> COND1(member(n, l), n, l)
   COND1(false, n, l) -> COND2(gt(n, max(l)), n, l)
   COND2(false, n, l) -> ST(s(n), l)

The TRS R consists of the following rules:

   max(nil) -> 0
   max(cons(u, l)) -> if(gt(u, max(l)), u, max(l))
   gt(0, v) -> false
   gt(s(u), 0) -> true
   gt(s(u), s(v)) -> gt(u, v)
   if(true, u, v) -> u
   if(false, u, v) -> v
   member(n, nil) -> false
   member(n, cons(m, l)) -> or(equal(n, m), member(n, l))
   equal(0, 0) -> true
   equal(s(x), 0) -> false
   equal(0, s(y)) -> false
   equal(s(x), s(y)) -> equal(x, y)
   or(x, true) -> true
   or(x, false) -> x

The set Q consists of the following terms:

   sort(x0)
   st(x0, x1)
   cond1(true, x0, x1)
   cond1(false, x0, x1)
   cond2(true, x0, x1)
   cond2(false, x0, x1)
   member(x0, nil)
   member(x0, cons(x1, x2))
   or(x0, true)
   or(x0, false)
   equal(0, 0)
   equal(s(x0), 0)
   equal(0, s(x0))
   equal(s(x0), s(x1))
   gt(0, x0)
   gt(s(x0), 0)
   gt(s(x0), s(x1))
   max(nil)
   max(cons(x0, x1))
   if(true, x0, x1)
   if(false, x0, x1)

We have to consider all minimal (P,Q,R)-chains.
----------------------------------------

(38) QReductionProof (EQUIVALENT)
We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN].

   sort(x0)
   st(x0, x1)
   cond1(true, x0, x1)
   cond1(false, x0, x1)
   cond2(true, x0, x1)
   cond2(false, x0, x1)


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

(39)
Obligation:
Q DP problem:
The TRS P consists of the following rules:

   COND1(true, n, l) -> ST(s(n), l)
   ST(n, l) -> COND1(member(n, l), n, l)
   COND1(false, n, l) -> COND2(gt(n, max(l)), n, l)
   COND2(false, n, l) -> ST(s(n), l)

The TRS R consists of the following rules:

   max(nil) -> 0
   max(cons(u, l)) -> if(gt(u, max(l)), u, max(l))
   gt(0, v) -> false
   gt(s(u), 0) -> true
   gt(s(u), s(v)) -> gt(u, v)
   if(true, u, v) -> u
   if(false, u, v) -> v
   member(n, nil) -> false
   member(n, cons(m, l)) -> or(equal(n, m), member(n, l))
   equal(0, 0) -> true
   equal(s(x), 0) -> false
   equal(0, s(y)) -> false
   equal(s(x), s(y)) -> equal(x, y)
   or(x, true) -> true
   or(x, false) -> x

The set Q consists of the following terms:

   member(x0, nil)
   member(x0, cons(x1, x2))
   or(x0, true)
   or(x0, false)
   equal(0, 0)
   equal(s(x0), 0)
   equal(0, s(x0))
   equal(s(x0), s(x1))
   gt(0, x0)
   gt(s(x0), 0)
   gt(s(x0), s(x1))
   max(nil)
   max(cons(x0, x1))
   if(true, x0, x1)
   if(false, x0, x1)

We have to consider all minimal (P,Q,R)-chains.
----------------------------------------

(40) NonInfProof (EQUIVALENT)
The DP Problem is simplified using the Induction Calculus [NONINF] with the following steps:

Note that final constraints are written in bold face.



For Pair COND1(true, n, l) -> ST(s(n), l) the following chains were created:
*We consider the chain ST(x2, x3) -> COND1(member(x2, x3), x2, x3), COND1(true, x4, x5) -> ST(s(x4), x5) which results in the following constraint:

(1)    (COND1(member(x2, x3), x2, x3)=COND1(true, x4, x5)  ==>  COND1(true, x4, x5)_>=_ST(s(x4), x5))



We simplified constraint (1) using rules (I), (II), (III) which results in the following new constraint:

(2)    (member(x2, x3)=true  ==>  COND1(true, x2, x3)_>=_ST(s(x2), x3))



We simplified constraint (2) using rule (V) (with possible (I) afterwards) using induction on member(x2, x3)=true which results in the following new constraint:

(3)    (or(equal(x45, x44), member(x45, x43))=true & (member(x45, x43)=true  ==>  COND1(true, x45, x43)_>=_ST(s(x45), x43))  ==>  COND1(true, x45, cons(x44, x43))_>=_ST(s(x45), cons(x44, x43)))



We simplified constraint (3) using rule (VII) which results in the following new constraint:

(4)    (equal(x45, x44)=x46 & member(x45, x43)=x47 & or(x46, x47)=true & (member(x45, x43)=true  ==>  COND1(true, x45, x43)_>=_ST(s(x45), x43))  ==>  COND1(true, x45, cons(x44, x43))_>=_ST(s(x45), cons(x44, x43)))



We simplified constraint (4) using rule (V) (with possible (I) afterwards) using induction on or(x46, x47)=true which results in the following new constraints:

(5)    (true=true & equal(x45, x44)=x48 & member(x45, x43)=true & (member(x45, x43)=true  ==>  COND1(true, x45, x43)_>=_ST(s(x45), x43))  ==>  COND1(true, x45, cons(x44, x43))_>=_ST(s(x45), cons(x44, x43)))

(6)    (x49=true & equal(x45, x44)=x49 & member(x45, x43)=false & (member(x45, x43)=true  ==>  COND1(true, x45, x43)_>=_ST(s(x45), x43))  ==>  COND1(true, x45, cons(x44, x43))_>=_ST(s(x45), cons(x44, x43)))



We simplified constraint (5) using rules (I), (II) which results in the following new constraint:

(7)    (equal(x45, x44)=x48 & member(x45, x43)=true & (member(x45, x43)=true  ==>  COND1(true, x45, x43)_>=_ST(s(x45), x43))  ==>  COND1(true, x45, cons(x44, x43))_>=_ST(s(x45), cons(x44, x43)))



We simplified constraint (6) using rules (III), (IV) which results in the following new constraint:

(8)    (equal(x45, x44)=true  ==>  COND1(true, x45, cons(x44, x43))_>=_ST(s(x45), cons(x44, x43)))



We simplified constraint (7) using rule (VI) where we applied the induction hypothesis (member(x45, x43)=true  ==>  COND1(true, x45, x43)_>=_ST(s(x45), x43)) with sigma = [ ] which results in the following new constraint:

(9)    (equal(x45, x44)=x48 & COND1(true, x45, x43)_>=_ST(s(x45), x43)  ==>  COND1(true, x45, cons(x44, x43))_>=_ST(s(x45), cons(x44, x43)))



We simplified constraint (9) using rule (IV) which results in the following new constraint:

(10)    (COND1(true, x45, x43)_>=_ST(s(x45), x43)  ==>  COND1(true, x45, cons(x44, x43))_>=_ST(s(x45), cons(x44, x43)))



We simplified constraint (8) using rule (V) (with possible (I) afterwards) using induction on equal(x45, x44)=true which results in the following new constraints:

(11)    (true=true  ==>  COND1(true, 0, cons(0, x43))_>=_ST(s(0), cons(0, x43)))

(12)    (equal(x53, x52)=true & (\/x54:equal(x53, x52)=true  ==>  COND1(true, x53, cons(x52, x54))_>=_ST(s(x53), cons(x52, x54)))  ==>  COND1(true, s(x53), cons(s(x52), x43))_>=_ST(s(s(x53)), cons(s(x52), x43)))



We simplified constraint (11) using rules (I), (II) which results in the following new constraint:

(13)    (COND1(true, 0, cons(0, x43))_>=_ST(s(0), cons(0, x43)))



We simplified constraint (12) using rule (VI) where we applied the induction hypothesis (\/x54:equal(x53, x52)=true  ==>  COND1(true, x53, cons(x52, x54))_>=_ST(s(x53), cons(x52, x54))) with sigma = [x54 / x43] which results in the following new constraint:

(14)    (COND1(true, x53, cons(x52, x43))_>=_ST(s(x53), cons(x52, x43))  ==>  COND1(true, s(x53), cons(s(x52), x43))_>=_ST(s(s(x53)), cons(s(x52), x43)))








For Pair ST(n, l) -> COND1(member(n, l), n, l) the following chains were created:
*We consider the chain COND1(true, x10, x11) -> ST(s(x10), x11), ST(x12, x13) -> COND1(member(x12, x13), x12, x13) which results in the following constraint:

(1)    (ST(s(x10), x11)=ST(x12, x13)  ==>  ST(x12, x13)_>=_COND1(member(x12, x13), x12, x13))



We simplified constraint (1) using rules (I), (II), (III) which results in the following new constraint:

(2)    (ST(s(x10), x11)_>=_COND1(member(s(x10), x11), s(x10), x11))




*We consider the chain COND2(false, x18, x19) -> ST(s(x18), x19), ST(x20, x21) -> COND1(member(x20, x21), x20, x21) which results in the following constraint:

(1)    (ST(s(x18), x19)=ST(x20, x21)  ==>  ST(x20, x21)_>=_COND1(member(x20, x21), x20, x21))



We simplified constraint (1) using rules (I), (II), (III) which results in the following new constraint:

(2)    (ST(s(x18), x19)_>=_COND1(member(s(x18), x19), s(x18), x19))








For Pair COND1(false, n, l) -> COND2(gt(n, max(l)), n, l) the following chains were created:
*We consider the chain ST(x24, x25) -> COND1(member(x24, x25), x24, x25), COND1(false, x26, x27) -> COND2(gt(x26, max(x27)), x26, x27) which results in the following constraint:

(1)    (COND1(member(x24, x25), x24, x25)=COND1(false, x26, x27)  ==>  COND1(false, x26, x27)_>=_COND2(gt(x26, max(x27)), x26, x27))



We simplified constraint (1) using rules (I), (II), (III) which results in the following new constraint:

(2)    (member(x24, x25)=false  ==>  COND1(false, x24, x25)_>=_COND2(gt(x24, max(x25)), x24, x25))



We simplified constraint (2) using rule (V) (with possible (I) afterwards) using induction on member(x24, x25)=false which results in the following new constraints:

(3)    (false=false  ==>  COND1(false, x55, nil)_>=_COND2(gt(x55, max(nil)), x55, nil))

(4)    (or(equal(x58, x57), member(x58, x56))=false & (member(x58, x56)=false  ==>  COND1(false, x58, x56)_>=_COND2(gt(x58, max(x56)), x58, x56))  ==>  COND1(false, x58, cons(x57, x56))_>=_COND2(gt(x58, max(cons(x57, x56))), x58, cons(x57, x56)))



We simplified constraint (3) using rules (I), (II) which results in the following new constraint:

(5)    (COND1(false, x55, nil)_>=_COND2(gt(x55, max(nil)), x55, nil))



We simplified constraint (4) using rule (VII) which results in the following new constraint:

(6)    (equal(x58, x57)=x59 & member(x58, x56)=x60 & or(x59, x60)=false & (member(x58, x56)=false  ==>  COND1(false, x58, x56)_>=_COND2(gt(x58, max(x56)), x58, x56))  ==>  COND1(false, x58, cons(x57, x56))_>=_COND2(gt(x58, max(cons(x57, x56))), x58, cons(x57, x56)))



We simplified constraint (6) using rule (V) (with possible (I) afterwards) using induction on or(x59, x60)=false which results in the following new constraint:

(7)    (x62=false & equal(x58, x57)=x62 & member(x58, x56)=false & (member(x58, x56)=false  ==>  COND1(false, x58, x56)_>=_COND2(gt(x58, max(x56)), x58, x56))  ==>  COND1(false, x58, cons(x57, x56))_>=_COND2(gt(x58, max(cons(x57, x56))), x58, cons(x57, x56)))



We simplified constraint (7) using rule (VI) where we applied the induction hypothesis (member(x58, x56)=false  ==>  COND1(false, x58, x56)_>=_COND2(gt(x58, max(x56)), x58, x56)) with sigma = [ ] which results in the following new constraint:

(8)    (x62=false & equal(x58, x57)=x62 & COND1(false, x58, x56)_>=_COND2(gt(x58, max(x56)), x58, x56)  ==>  COND1(false, x58, cons(x57, x56))_>=_COND2(gt(x58, max(cons(x57, x56))), x58, cons(x57, x56)))



We simplified constraint (8) using rule (III) which results in the following new constraint:

(9)    (equal(x58, x57)=false & COND1(false, x58, x56)_>=_COND2(gt(x58, max(x56)), x58, x56)  ==>  COND1(false, x58, cons(x57, x56))_>=_COND2(gt(x58, max(cons(x57, x56))), x58, cons(x57, x56)))



We simplified constraint (9) using rule (V) (with possible (I) afterwards) using induction on equal(x58, x57)=false which results in the following new constraints:

(10)    (false=false & COND1(false, s(x63), x56)_>=_COND2(gt(s(x63), max(x56)), s(x63), x56)  ==>  COND1(false, s(x63), cons(0, x56))_>=_COND2(gt(s(x63), max(cons(0, x56))), s(x63), cons(0, x56)))

(11)    (false=false & COND1(false, 0, x56)_>=_COND2(gt(0, max(x56)), 0, x56)  ==>  COND1(false, 0, cons(s(x64), x56))_>=_COND2(gt(0, max(cons(s(x64), x56))), 0, cons(s(x64), x56)))

(12)    (equal(x66, x65)=false & COND1(false, s(x66), x56)_>=_COND2(gt(s(x66), max(x56)), s(x66), x56) & (\/x67:equal(x66, x65)=false & COND1(false, x66, x67)_>=_COND2(gt(x66, max(x67)), x66, x67)  ==>  COND1(false, x66, cons(x65, x67))_>=_COND2(gt(x66, max(cons(x65, x67))), x66, cons(x65, x67)))  ==>  COND1(false, s(x66), cons(s(x65), x56))_>=_COND2(gt(s(x66), max(cons(s(x65), x56))), s(x66), cons(s(x65), x56)))



We simplified constraint (10) using rules (I), (II) which results in the following new constraint:

(13)    (COND1(false, s(x63), x56)_>=_COND2(gt(s(x63), max(x56)), s(x63), x56)  ==>  COND1(false, s(x63), cons(0, x56))_>=_COND2(gt(s(x63), max(cons(0, x56))), s(x63), cons(0, x56)))



We simplified constraint (11) using rules (I), (II) which results in the following new constraint:

(14)    (COND1(false, 0, x56)_>=_COND2(gt(0, max(x56)), 0, x56)  ==>  COND1(false, 0, cons(s(x64), x56))_>=_COND2(gt(0, max(cons(s(x64), x56))), 0, cons(s(x64), x56)))



We simplified constraint (12) using rule (IV) which results in the following new constraint:

(15)    (COND1(false, s(x66), x56)_>=_COND2(gt(s(x66), max(x56)), s(x66), x56)  ==>  COND1(false, s(x66), cons(s(x65), x56))_>=_COND2(gt(s(x66), max(cons(s(x65), x56))), s(x66), cons(s(x65), x56)))








For Pair COND2(false, n, l) -> ST(s(n), l) the following chains were created:
*We consider the chain COND1(false, x36, x37) -> COND2(gt(x36, max(x37)), x36, x37), COND2(false, x38, x39) -> ST(s(x38), x39) which results in the following constraint:

(1)    (COND2(gt(x36, max(x37)), x36, x37)=COND2(false, x38, x39)  ==>  COND2(false, x38, x39)_>=_ST(s(x38), x39))



We simplified constraint (1) using rules (I), (II), (III), (VII) which results in the following new constraint:

(2)    (max(x37)=x68 & gt(x36, x68)=false  ==>  COND2(false, x36, x37)_>=_ST(s(x36), x37))



We simplified constraint (2) using rule (V) (with possible (I) afterwards) using induction on gt(x36, x68)=false which results in the following new constraints:

(3)    (false=false & max(x37)=x69  ==>  COND2(false, 0, x37)_>=_ST(s(0), x37))

(4)    (gt(x72, x71)=false & max(x37)=s(x71) & (\/x73:gt(x72, x71)=false & max(x73)=x71  ==>  COND2(false, x72, x73)_>=_ST(s(x72), x73))  ==>  COND2(false, s(x72), x37)_>=_ST(s(s(x72)), x37))



We simplified constraint (3) using rules (I), (II), (IV) which results in the following new constraint:

(5)    (COND2(false, 0, x37)_>=_ST(s(0), x37))



We simplified constraint (4) using rule (V) (with possible (I) afterwards) using induction on max(x37)=s(x71) which results in the following new constraint:

(6)    (if(gt(x75, max(x74)), x75, max(x74))=s(x71) & gt(x72, x71)=false & (\/x73:gt(x72, x71)=false & max(x73)=x71  ==>  COND2(false, x72, x73)_>=_ST(s(x72), x73)) & (\/x76,x77,x78:max(x74)=s(x76) & gt(x77, x76)=false & (\/x78:gt(x77, x76)=false & max(x78)=x76  ==>  COND2(false, x77, x78)_>=_ST(s(x77), x78))  ==>  COND2(false, s(x77), x74)_>=_ST(s(s(x77)), x74))  ==>  COND2(false, s(x72), cons(x75, x74))_>=_ST(s(s(x72)), cons(x75, x74)))



We simplified constraint (6) using rules (IV), (VII) which results in the following new constraint:

(7)    (gt(x75, x81)=x79 & max(x74)=x80 & if(x79, x75, x80)=s(x71) & gt(x72, x71)=false & (\/x73:gt(x72, x71)=false & max(x73)=x71  ==>  COND2(false, x72, x73)_>=_ST(s(x72), x73)) & (\/x76,x77,x78:max(x74)=s(x76) & gt(x77, x76)=false & (\/x78:gt(x77, x76)=false & max(x78)=x76  ==>  COND2(false, x77, x78)_>=_ST(s(x77), x78))  ==>  COND2(false, s(x77), x74)_>=_ST(s(s(x77)), x74))  ==>  COND2(false, s(x72), cons(x75, x74))_>=_ST(s(s(x72)), cons(x75, x74)))



We simplified constraint (7) using rule (V) (with possible (I) afterwards) using induction on if(x79, x75, x80)=s(x71) which results in the following new constraints:

(8)    (x83=s(x71) & gt(x83, x81)=true & max(x74)=x82 & gt(x72, x71)=false & (\/x73:gt(x72, x71)=false & max(x73)=x71  ==>  COND2(false, x72, x73)_>=_ST(s(x72), x73)) & (\/x76,x77,x78:max(x74)=s(x76) & gt(x77, x76)=false & (\/x78:gt(x77, x76)=false & max(x78)=x76  ==>  COND2(false, x77, x78)_>=_ST(s(x77), x78))  ==>  COND2(false, s(x77), x74)_>=_ST(s(s(x77)), x74))  ==>  COND2(false, s(x72), cons(x83, x74))_>=_ST(s(s(x72)), cons(x83, x74)))

(9)    (x84=s(x71) & gt(x85, x81)=false & max(x74)=x84 & gt(x72, x71)=false & (\/x73:gt(x72, x71)=false & max(x73)=x71  ==>  COND2(false, x72, x73)_>=_ST(s(x72), x73)) & (\/x76,x77,x78:max(x74)=s(x76) & gt(x77, x76)=false & (\/x78:gt(x77, x76)=false & max(x78)=x76  ==>  COND2(false, x77, x78)_>=_ST(s(x77), x78))  ==>  COND2(false, s(x77), x74)_>=_ST(s(s(x77)), x74))  ==>  COND2(false, s(x72), cons(x85, x74))_>=_ST(s(s(x72)), cons(x85, x74)))



We simplified constraint (8) using rules (III), (IV), (VII) which results in the following new constraint:

(10)    (gt(x72, x71)=false  ==>  COND2(false, s(x72), cons(s(x71), x74))_>=_ST(s(s(x72)), cons(s(x71), x74)))



We simplified constraint (9) using rule (III) which results in the following new constraint:

(11)    (gt(x85, x81)=false & max(x74)=s(x71) & gt(x72, x71)=false & (\/x73:gt(x72, x71)=false & max(x73)=x71  ==>  COND2(false, x72, x73)_>=_ST(s(x72), x73)) & (\/x76,x77,x78:max(x74)=s(x76) & gt(x77, x76)=false & (\/x78:gt(x77, x76)=false & max(x78)=x76  ==>  COND2(false, x77, x78)_>=_ST(s(x77), x78))  ==>  COND2(false, s(x77), x74)_>=_ST(s(s(x77)), x74))  ==>  COND2(false, s(x72), cons(x85, x74))_>=_ST(s(s(x72)), cons(x85, x74)))



We simplified constraint (10) using rule (V) (with possible (I) afterwards) using induction on gt(x72, x71)=false which results in the following new constraints:

(12)    (false=false  ==>  COND2(false, s(0), cons(s(x87), x74))_>=_ST(s(s(0)), cons(s(x87), x74)))

(13)    (gt(x90, x89)=false & (\/x91:gt(x90, x89)=false  ==>  COND2(false, s(x90), cons(s(x89), x91))_>=_ST(s(s(x90)), cons(s(x89), x91)))  ==>  COND2(false, s(s(x90)), cons(s(s(x89)), x74))_>=_ST(s(s(s(x90))), cons(s(s(x89)), x74)))



We simplified constraint (12) using rules (I), (II) which results in the following new constraint:

(14)    (COND2(false, s(0), cons(s(x87), x74))_>=_ST(s(s(0)), cons(s(x87), x74)))



We simplified constraint (13) using rule (VI) where we applied the induction hypothesis (\/x91:gt(x90, x89)=false  ==>  COND2(false, s(x90), cons(s(x89), x91))_>=_ST(s(s(x90)), cons(s(x89), x91))) with sigma = [x91 / x74] which results in the following new constraint:

(15)    (COND2(false, s(x90), cons(s(x89), x74))_>=_ST(s(s(x90)), cons(s(x89), x74))  ==>  COND2(false, s(s(x90)), cons(s(s(x89)), x74))_>=_ST(s(s(s(x90))), cons(s(s(x89)), x74)))



We simplified constraint (11) using rule (VI) where we applied the induction hypothesis (\/x76,x77,x78:max(x74)=s(x76) & gt(x77, x76)=false & (\/x78:gt(x77, x76)=false & max(x78)=x76  ==>  COND2(false, x77, x78)_>=_ST(s(x77), x78))  ==>  COND2(false, s(x77), x74)_>=_ST(s(s(x77)), x74)) with sigma = [x76 / x71, x77 / x72, x78 / x73] which results in the following new constraint:

(16)    (gt(x85, x81)=false & COND2(false, s(x72), x74)_>=_ST(s(s(x72)), x74)  ==>  COND2(false, s(x72), cons(x85, x74))_>=_ST(s(s(x72)), cons(x85, x74)))



We simplified constraint (16) using rule (V) (with possible (I) afterwards) using induction on gt(x85, x81)=false which results in the following new constraints:

(17)    (false=false & COND2(false, s(x72), x74)_>=_ST(s(s(x72)), x74)  ==>  COND2(false, s(x72), cons(0, x74))_>=_ST(s(s(x72)), cons(0, x74)))

(18)    (gt(x95, x94)=false & COND2(false, s(x72), x74)_>=_ST(s(s(x72)), x74) & (\/x96,x97:gt(x95, x94)=false & COND2(false, s(x96), x97)_>=_ST(s(s(x96)), x97)  ==>  COND2(false, s(x96), cons(x95, x97))_>=_ST(s(s(x96)), cons(x95, x97)))  ==>  COND2(false, s(x72), cons(s(x95), x74))_>=_ST(s(s(x72)), cons(s(x95), x74)))



We simplified constraint (17) using rules (I), (II) which results in the following new constraint:

(19)    (COND2(false, s(x72), x74)_>=_ST(s(s(x72)), x74)  ==>  COND2(false, s(x72), cons(0, x74))_>=_ST(s(s(x72)), cons(0, x74)))



We simplified constraint (18) using rule (VI) where we applied the induction hypothesis (\/x96,x97:gt(x95, x94)=false & COND2(false, s(x96), x97)_>=_ST(s(s(x96)), x97)  ==>  COND2(false, s(x96), cons(x95, x97))_>=_ST(s(s(x96)), cons(x95, x97))) with sigma = [x96 / x72, x97 / x74] which results in the following new constraint:

(20)    (COND2(false, s(x72), cons(x95, x74))_>=_ST(s(s(x72)), cons(x95, x74))  ==>  COND2(false, s(x72), cons(s(x95), x74))_>=_ST(s(s(x72)), cons(s(x95), x74)))








To summarize, we get the following constraints P__>=_ for the following pairs.

*COND1(true, n, l) -> ST(s(n), l)

*(COND1(true, x45, x43)_>=_ST(s(x45), x43)  ==>  COND1(true, x45, cons(x44, x43))_>=_ST(s(x45), cons(x44, x43)))


*(COND1(true, 0, cons(0, x43))_>=_ST(s(0), cons(0, x43)))


*(COND1(true, x53, cons(x52, x43))_>=_ST(s(x53), cons(x52, x43))  ==>  COND1(true, s(x53), cons(s(x52), x43))_>=_ST(s(s(x53)), cons(s(x52), x43)))




*ST(n, l) -> COND1(member(n, l), n, l)

*(ST(s(x10), x11)_>=_COND1(member(s(x10), x11), s(x10), x11))


*(ST(s(x18), x19)_>=_COND1(member(s(x18), x19), s(x18), x19))




*COND1(false, n, l) -> COND2(gt(n, max(l)), n, l)

*(COND1(false, x55, nil)_>=_COND2(gt(x55, max(nil)), x55, nil))


*(COND1(false, s(x63), x56)_>=_COND2(gt(s(x63), max(x56)), s(x63), x56)  ==>  COND1(false, s(x63), cons(0, x56))_>=_COND2(gt(s(x63), max(cons(0, x56))), s(x63), cons(0, x56)))


*(COND1(false, 0, x56)_>=_COND2(gt(0, max(x56)), 0, x56)  ==>  COND1(false, 0, cons(s(x64), x56))_>=_COND2(gt(0, max(cons(s(x64), x56))), 0, cons(s(x64), x56)))


*(COND1(false, s(x66), x56)_>=_COND2(gt(s(x66), max(x56)), s(x66), x56)  ==>  COND1(false, s(x66), cons(s(x65), x56))_>=_COND2(gt(s(x66), max(cons(s(x65), x56))), s(x66), cons(s(x65), x56)))




*COND2(false, n, l) -> ST(s(n), l)

*(COND2(false, 0, x37)_>=_ST(s(0), x37))


*(COND2(false, s(0), cons(s(x87), x74))_>=_ST(s(s(0)), cons(s(x87), x74)))


*(COND2(false, s(x90), cons(s(x89), x74))_>=_ST(s(s(x90)), cons(s(x89), x74))  ==>  COND2(false, s(s(x90)), cons(s(s(x89)), x74))_>=_ST(s(s(s(x90))), cons(s(s(x89)), x74)))


*(COND2(false, s(x72), x74)_>=_ST(s(s(x72)), x74)  ==>  COND2(false, s(x72), cons(0, x74))_>=_ST(s(s(x72)), cons(0, x74)))


*(COND2(false, s(x72), cons(x95, x74))_>=_ST(s(s(x72)), cons(x95, x74))  ==>  COND2(false, s(x72), cons(s(x95), x74))_>=_ST(s(s(x72)), cons(s(x95), x74)))








The constraints for P_> respective P_bound are constructed from P__>=_ where we just replace every occurence of "t _>=_ s" in P__>=_ by  "t > s" respective "t _>=_ c". Here c stands for the fresh constant used for P_bound. 

Using the following integer polynomial ordering the  resulting constraints can be solved 

Polynomial interpretation [NONINF]:

   POL(0) = 0
   POL(COND1(x_1, x_2, x_3)) = -1 - x_1 - x_2 + x_3
   POL(COND2(x_1, x_2, x_3)) = -1 - x_1 - x_2 + x_3
   POL(ST(x_1, x_2)) = -1 - x_1 + x_2
   POL(c) = -2
   POL(cons(x_1, x_2)) = x_1 + x_2
   POL(equal(x_1, x_2)) = 0
   POL(false) = 0
   POL(gt(x_1, x_2)) = 0
   POL(if(x_1, x_2, x_3)) = 0
   POL(max(x_1)) = 0
   POL(member(x_1, x_2)) = 0
   POL(nil) = 0
   POL(or(x_1, x_2)) = 0
   POL(s(x_1)) = 1 + x_1
   POL(true) = 0


The following pairs  are in P_>:
   COND1(true, n, l) -> ST(s(n), l)
   COND2(false, n, l) -> ST(s(n), l)
The following pairs are in P_bound:
   COND1(true, n, l) -> ST(s(n), l)
   COND2(false, n, l) -> ST(s(n), l)
The following rules are usable:
   false -> member(n, nil)
   or(equal(n, m), member(n, l)) -> member(n, cons(m, l))
   false -> gt(0, v)
   true -> gt(s(u), 0)
   gt(u, v) -> gt(s(u), s(v))
   true -> or(x, true)
   x -> or(x, false)

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

(41)
Obligation:
Q DP problem:
The TRS P consists of the following rules:

   ST(n, l) -> COND1(member(n, l), n, l)
   COND1(false, n, l) -> COND2(gt(n, max(l)), n, l)

The TRS R consists of the following rules:

   max(nil) -> 0
   max(cons(u, l)) -> if(gt(u, max(l)), u, max(l))
   gt(0, v) -> false
   gt(s(u), 0) -> true
   gt(s(u), s(v)) -> gt(u, v)
   if(true, u, v) -> u
   if(false, u, v) -> v
   member(n, nil) -> false
   member(n, cons(m, l)) -> or(equal(n, m), member(n, l))
   equal(0, 0) -> true
   equal(s(x), 0) -> false
   equal(0, s(y)) -> false
   equal(s(x), s(y)) -> equal(x, y)
   or(x, true) -> true
   or(x, false) -> x

The set Q consists of the following terms:

   member(x0, nil)
   member(x0, cons(x1, x2))
   or(x0, true)
   or(x0, false)
   equal(0, 0)
   equal(s(x0), 0)
   equal(0, s(x0))
   equal(s(x0), s(x1))
   gt(0, x0)
   gt(s(x0), 0)
   gt(s(x0), s(x1))
   max(nil)
   max(cons(x0, x1))
   if(true, x0, x1)
   if(false, x0, x1)

We have to consider all minimal (P,Q,R)-chains.
----------------------------------------

(42) DependencyGraphProof (EQUIVALENT)
The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 0 SCCs with 2 less nodes.
----------------------------------------

(43)
TRUE