YES
proof of /export/starexec/sandbox/benchmark/theBenchmark.xml
# AProVE Commit ID: 794c25de1cacf0d048858bcd21c9a779e1221865 marcel 20200619 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, 0 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) QDPOrderProof [EQUIVALENT, 27 ms]
        (34) QDP
        (35) DependencyGraphProof [EQUIVALENT, 0 ms]
        (36) TRUE
    (37) QDP
        (38) UsableRulesProof [EQUIVALENT, 0 ms]
        (39) QDP
        (40) QReductionProof [EQUIVALENT, 0 ms]
        (41) QDP
        (42) Induction-Processor [SOUND, 81 ms]
        (43) AND
            (44) QDP
                (45) PisEmptyProof [EQUIVALENT, 0 ms]
                (46) YES
            (47) QTRS
                (48) Overlay + Local Confluence [EQUIVALENT, 0 ms]
                (49) QTRS
                (50) DependencyPairsProof [EQUIVALENT, 0 ms]
                (51) QDP
                (52) DependencyGraphProof [EQUIVALENT, 0 ms]
                (53) AND
                    (54) QDP
                        (55) UsableRulesProof [EQUIVALENT, 0 ms]
                        (56) QDP
                        (57) QReductionProof [EQUIVALENT, 0 ms]
                        (58) QDP
                        (59) QDPSizeChangeProof [EQUIVALENT, 0 ms]
                        (60) YES
                    (61) QDP
                        (62) UsableRulesProof [EQUIVALENT, 0 ms]
                        (63) QDP
                        (64) QReductionProof [EQUIVALENT, 0 ms]
                        (65) QDP
                        (66) QDPSizeChangeProof [EQUIVALENT, 0 ms]
                        (67) YES
                    (68) QDP
                        (69) UsableRulesProof [EQUIVALENT, 0 ms]
                        (70) QDP
                        (71) QReductionProof [EQUIVALENT, 1 ms]
                        (72) QDP
                        (73) QDPSizeChangeProof [EQUIVALENT, 0 ms]
                        (74) YES
                    (75) QDP
                        (76) UsableRulesProof [EQUIVALENT, 0 ms]
                        (77) QDP
                        (78) QReductionProof [EQUIVALENT, 0 ms]
                        (79) QDP
                        (80) QDPSizeChangeProof [EQUIVALENT, 0 ms]
                        (81) YES
                    (82) QDP
                        (83) UsableRulesProof [EQUIVALENT, 0 ms]
                        (84) QDP
                        (85) QReductionProof [EQUIVALENT, 0 ms]
                        (86) QDP
                        (87) QDPSizeChangeProof [EQUIVALENT, 0 ms]
                        (88) YES
                    (89) QDP
                        (90) UsableRulesProof [EQUIVALENT, 0 ms]
                        (91) QDP
                        (92) QReductionProof [EQUIVALENT, 0 ms]
                        (93) QDP
                        (94) QDPOrderProof [EQUIVALENT, 0 ms]
                        (95) QDP
                        (96) PisEmptyProof [EQUIVALENT, 0 ms]
                        (97) YES
                    (98) QDP
                        (99) UsableRulesProof [EQUIVALENT, 0 ms]
                        (100) QDP
                        (101) QReductionProof [EQUIVALENT, 0 ms]
                        (102) QDP
                        (103) QDPSizeChangeProof [EQUIVALENT, 0 ms]
                        (104) YES


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

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

   le(0, y) -> true
   le(s(x), 0) -> false
   le(s(x), s(y)) -> le(x, y)
   eq(0, 0) -> true
   eq(0, s(y)) -> false
   eq(s(x), 0) -> false
   eq(s(x), s(y)) -> eq(x, y)
   minsort(nil) -> nil
   minsort(cons(x, xs)) -> cons(min(cons(x, xs)), minsort(rm(min(cons(x, xs)), cons(x, xs))))
   min(nil) -> 0
   min(cons(x, nil)) -> x
   min(cons(x, cons(y, xs))) -> if1(le(x, y), x, y, xs)
   if1(true, x, y, xs) -> min(cons(x, xs))
   if1(false, x, y, xs) -> min(cons(y, xs))
   rm(x, nil) -> nil
   rm(x, cons(y, xs)) -> if2(eq(x, y), x, y, xs)
   if2(true, x, y, xs) -> rm(x, xs)
   if2(false, x, y, xs) -> cons(y, rm(x, xs))

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:

   le(0, y) -> true
   le(s(x), 0) -> false
   le(s(x), s(y)) -> le(x, y)
   eq(0, 0) -> true
   eq(0, s(y)) -> false
   eq(s(x), 0) -> false
   eq(s(x), s(y)) -> eq(x, y)
   minsort(nil) -> nil
   minsort(cons(x, xs)) -> cons(min(cons(x, xs)), minsort(rm(min(cons(x, xs)), cons(x, xs))))
   min(nil) -> 0
   min(cons(x, nil)) -> x
   min(cons(x, cons(y, xs))) -> if1(le(x, y), x, y, xs)
   if1(true, x, y, xs) -> min(cons(x, xs))
   if1(false, x, y, xs) -> min(cons(y, xs))
   rm(x, nil) -> nil
   rm(x, cons(y, xs)) -> if2(eq(x, y), x, y, xs)
   if2(true, x, y, xs) -> rm(x, xs)
   if2(false, x, y, xs) -> cons(y, rm(x, xs))

The set Q consists of the following terms:

   le(0, x0)
   le(s(x0), 0)
   le(s(x0), s(x1))
   eq(0, 0)
   eq(0, s(x0))
   eq(s(x0), 0)
   eq(s(x0), s(x1))
   minsort(nil)
   minsort(cons(x0, x1))
   min(nil)
   min(cons(x0, nil))
   min(cons(x0, cons(x1, x2)))
   if1(true, x0, x1, x2)
   if1(false, x0, x1, x2)
   rm(x0, nil)
   rm(x0, cons(x1, x2))
   if2(true, x0, x1, x2)
   if2(false, x0, x1, x2)


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

(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:

   LE(s(x), s(y)) -> LE(x, y)
   EQ(s(x), s(y)) -> EQ(x, y)
   MINSORT(cons(x, xs)) -> MIN(cons(x, xs))
   MINSORT(cons(x, xs)) -> MINSORT(rm(min(cons(x, xs)), cons(x, xs)))
   MINSORT(cons(x, xs)) -> RM(min(cons(x, xs)), cons(x, xs))
   MIN(cons(x, cons(y, xs))) -> IF1(le(x, y), x, y, xs)
   MIN(cons(x, cons(y, xs))) -> LE(x, y)
   IF1(true, x, y, xs) -> MIN(cons(x, xs))
   IF1(false, x, y, xs) -> MIN(cons(y, xs))
   RM(x, cons(y, xs)) -> IF2(eq(x, y), x, y, xs)
   RM(x, cons(y, xs)) -> EQ(x, y)
   IF2(true, x, y, xs) -> RM(x, xs)
   IF2(false, x, y, xs) -> RM(x, xs)

The TRS R consists of the following rules:

   le(0, y) -> true
   le(s(x), 0) -> false
   le(s(x), s(y)) -> le(x, y)
   eq(0, 0) -> true
   eq(0, s(y)) -> false
   eq(s(x), 0) -> false
   eq(s(x), s(y)) -> eq(x, y)
   minsort(nil) -> nil
   minsort(cons(x, xs)) -> cons(min(cons(x, xs)), minsort(rm(min(cons(x, xs)), cons(x, xs))))
   min(nil) -> 0
   min(cons(x, nil)) -> x
   min(cons(x, cons(y, xs))) -> if1(le(x, y), x, y, xs)
   if1(true, x, y, xs) -> min(cons(x, xs))
   if1(false, x, y, xs) -> min(cons(y, xs))
   rm(x, nil) -> nil
   rm(x, cons(y, xs)) -> if2(eq(x, y), x, y, xs)
   if2(true, x, y, xs) -> rm(x, xs)
   if2(false, x, y, xs) -> cons(y, rm(x, xs))

The set Q consists of the following terms:

   le(0, x0)
   le(s(x0), 0)
   le(s(x0), s(x1))
   eq(0, 0)
   eq(0, s(x0))
   eq(s(x0), 0)
   eq(s(x0), s(x1))
   minsort(nil)
   minsort(cons(x0, x1))
   min(nil)
   min(cons(x0, nil))
   min(cons(x0, cons(x1, x2)))
   if1(true, x0, x1, x2)
   if1(false, x0, x1, x2)
   rm(x0, nil)
   rm(x0, cons(x1, x2))
   if2(true, x0, x1, x2)
   if2(false, x0, x1, x2)

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 4 less nodes.
----------------------------------------

(6)
Complex Obligation (AND)

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

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

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

The TRS R consists of the following rules:

   le(0, y) -> true
   le(s(x), 0) -> false
   le(s(x), s(y)) -> le(x, y)
   eq(0, 0) -> true
   eq(0, s(y)) -> false
   eq(s(x), 0) -> false
   eq(s(x), s(y)) -> eq(x, y)
   minsort(nil) -> nil
   minsort(cons(x, xs)) -> cons(min(cons(x, xs)), minsort(rm(min(cons(x, xs)), cons(x, xs))))
   min(nil) -> 0
   min(cons(x, nil)) -> x
   min(cons(x, cons(y, xs))) -> if1(le(x, y), x, y, xs)
   if1(true, x, y, xs) -> min(cons(x, xs))
   if1(false, x, y, xs) -> min(cons(y, xs))
   rm(x, nil) -> nil
   rm(x, cons(y, xs)) -> if2(eq(x, y), x, y, xs)
   if2(true, x, y, xs) -> rm(x, xs)
   if2(false, x, y, xs) -> cons(y, rm(x, xs))

The set Q consists of the following terms:

   le(0, x0)
   le(s(x0), 0)
   le(s(x0), s(x1))
   eq(0, 0)
   eq(0, s(x0))
   eq(s(x0), 0)
   eq(s(x0), s(x1))
   minsort(nil)
   minsort(cons(x0, x1))
   min(nil)
   min(cons(x0, nil))
   min(cons(x0, cons(x1, x2)))
   if1(true, x0, x1, x2)
   if1(false, x0, x1, x2)
   rm(x0, nil)
   rm(x0, cons(x1, x2))
   if2(true, x0, x1, x2)
   if2(false, x0, x1, x2)

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:

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

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

   le(0, x0)
   le(s(x0), 0)
   le(s(x0), s(x1))
   eq(0, 0)
   eq(0, s(x0))
   eq(s(x0), 0)
   eq(s(x0), s(x1))
   minsort(nil)
   minsort(cons(x0, x1))
   min(nil)
   min(cons(x0, nil))
   min(cons(x0, cons(x1, x2)))
   if1(true, x0, x1, x2)
   if1(false, x0, x1, x2)
   rm(x0, nil)
   rm(x0, cons(x1, x2))
   if2(true, x0, x1, x2)
   if2(false, x0, x1, x2)

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].

   le(0, x0)
   le(s(x0), 0)
   le(s(x0), s(x1))
   eq(0, 0)
   eq(0, s(x0))
   eq(s(x0), 0)
   eq(s(x0), s(x1))
   minsort(nil)
   minsort(cons(x0, x1))
   min(nil)
   min(cons(x0, nil))
   min(cons(x0, cons(x1, x2)))
   if1(true, x0, x1, x2)
   if1(false, x0, x1, x2)
   rm(x0, nil)
   rm(x0, cons(x1, x2))
   if2(true, x0, x1, x2)
   if2(false, x0, x1, x2)


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

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

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

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:
*EQ(s(x), s(y)) -> EQ(x, y)
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:

   RM(x, cons(y, xs)) -> IF2(eq(x, y), x, y, xs)
   IF2(true, x, y, xs) -> RM(x, xs)
   IF2(false, x, y, xs) -> RM(x, xs)

The TRS R consists of the following rules:

   le(0, y) -> true
   le(s(x), 0) -> false
   le(s(x), s(y)) -> le(x, y)
   eq(0, 0) -> true
   eq(0, s(y)) -> false
   eq(s(x), 0) -> false
   eq(s(x), s(y)) -> eq(x, y)
   minsort(nil) -> nil
   minsort(cons(x, xs)) -> cons(min(cons(x, xs)), minsort(rm(min(cons(x, xs)), cons(x, xs))))
   min(nil) -> 0
   min(cons(x, nil)) -> x
   min(cons(x, cons(y, xs))) -> if1(le(x, y), x, y, xs)
   if1(true, x, y, xs) -> min(cons(x, xs))
   if1(false, x, y, xs) -> min(cons(y, xs))
   rm(x, nil) -> nil
   rm(x, cons(y, xs)) -> if2(eq(x, y), x, y, xs)
   if2(true, x, y, xs) -> rm(x, xs)
   if2(false, x, y, xs) -> cons(y, rm(x, xs))

The set Q consists of the following terms:

   le(0, x0)
   le(s(x0), 0)
   le(s(x0), s(x1))
   eq(0, 0)
   eq(0, s(x0))
   eq(s(x0), 0)
   eq(s(x0), s(x1))
   minsort(nil)
   minsort(cons(x0, x1))
   min(nil)
   min(cons(x0, nil))
   min(cons(x0, cons(x1, x2)))
   if1(true, x0, x1, x2)
   if1(false, x0, x1, x2)
   rm(x0, nil)
   rm(x0, cons(x1, x2))
   if2(true, x0, x1, x2)
   if2(false, x0, x1, x2)

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:

   RM(x, cons(y, xs)) -> IF2(eq(x, y), x, y, xs)
   IF2(true, x, y, xs) -> RM(x, xs)
   IF2(false, x, y, xs) -> RM(x, xs)

The TRS R consists of the following rules:

   eq(0, 0) -> true
   eq(0, s(y)) -> false
   eq(s(x), 0) -> false
   eq(s(x), s(y)) -> eq(x, y)

The set Q consists of the following terms:

   le(0, x0)
   le(s(x0), 0)
   le(s(x0), s(x1))
   eq(0, 0)
   eq(0, s(x0))
   eq(s(x0), 0)
   eq(s(x0), s(x1))
   minsort(nil)
   minsort(cons(x0, x1))
   min(nil)
   min(cons(x0, nil))
   min(cons(x0, cons(x1, x2)))
   if1(true, x0, x1, x2)
   if1(false, x0, x1, x2)
   rm(x0, nil)
   rm(x0, cons(x1, x2))
   if2(true, x0, x1, x2)
   if2(false, x0, x1, x2)

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].

   le(0, x0)
   le(s(x0), 0)
   le(s(x0), s(x1))
   minsort(nil)
   minsort(cons(x0, x1))
   min(nil)
   min(cons(x0, nil))
   min(cons(x0, cons(x1, x2)))
   if1(true, x0, x1, x2)
   if1(false, x0, x1, x2)
   rm(x0, nil)
   rm(x0, cons(x1, x2))
   if2(true, x0, x1, x2)
   if2(false, x0, x1, x2)


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

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

   RM(x, cons(y, xs)) -> IF2(eq(x, y), x, y, xs)
   IF2(true, x, y, xs) -> RM(x, xs)
   IF2(false, x, y, xs) -> RM(x, xs)

The TRS R consists of the following rules:

   eq(0, 0) -> true
   eq(0, s(y)) -> false
   eq(s(x), 0) -> false
   eq(s(x), s(y)) -> eq(x, y)

The set Q consists of the following terms:

   eq(0, 0)
   eq(0, s(x0))
   eq(s(x0), 0)
   eq(s(x0), s(x1))

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:
*RM(x, cons(y, xs)) -> IF2(eq(x, y), x, y, xs)
The graph contains the following edges 1 >= 2, 2 > 3, 2 > 4


*IF2(true, x, y, xs) -> RM(x, xs)
The graph contains the following edges 2 >= 1, 4 >= 2


*IF2(false, x, y, xs) -> RM(x, xs)
The graph contains the following edges 2 >= 1, 4 >= 2


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

(20)
YES

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

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

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

The TRS R consists of the following rules:

   le(0, y) -> true
   le(s(x), 0) -> false
   le(s(x), s(y)) -> le(x, y)
   eq(0, 0) -> true
   eq(0, s(y)) -> false
   eq(s(x), 0) -> false
   eq(s(x), s(y)) -> eq(x, y)
   minsort(nil) -> nil
   minsort(cons(x, xs)) -> cons(min(cons(x, xs)), minsort(rm(min(cons(x, xs)), cons(x, xs))))
   min(nil) -> 0
   min(cons(x, nil)) -> x
   min(cons(x, cons(y, xs))) -> if1(le(x, y), x, y, xs)
   if1(true, x, y, xs) -> min(cons(x, xs))
   if1(false, x, y, xs) -> min(cons(y, xs))
   rm(x, nil) -> nil
   rm(x, cons(y, xs)) -> if2(eq(x, y), x, y, xs)
   if2(true, x, y, xs) -> rm(x, xs)
   if2(false, x, y, xs) -> cons(y, rm(x, xs))

The set Q consists of the following terms:

   le(0, x0)
   le(s(x0), 0)
   le(s(x0), s(x1))
   eq(0, 0)
   eq(0, s(x0))
   eq(s(x0), 0)
   eq(s(x0), s(x1))
   minsort(nil)
   minsort(cons(x0, x1))
   min(nil)
   min(cons(x0, nil))
   min(cons(x0, cons(x1, x2)))
   if1(true, x0, x1, x2)
   if1(false, x0, x1, x2)
   rm(x0, nil)
   rm(x0, cons(x1, x2))
   if2(true, x0, x1, x2)
   if2(false, x0, x1, x2)

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:

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

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

   le(0, x0)
   le(s(x0), 0)
   le(s(x0), s(x1))
   eq(0, 0)
   eq(0, s(x0))
   eq(s(x0), 0)
   eq(s(x0), s(x1))
   minsort(nil)
   minsort(cons(x0, x1))
   min(nil)
   min(cons(x0, nil))
   min(cons(x0, cons(x1, x2)))
   if1(true, x0, x1, x2)
   if1(false, x0, x1, x2)
   rm(x0, nil)
   rm(x0, cons(x1, x2))
   if2(true, x0, x1, x2)
   if2(false, x0, x1, x2)

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].

   le(0, x0)
   le(s(x0), 0)
   le(s(x0), s(x1))
   eq(0, 0)
   eq(0, s(x0))
   eq(s(x0), 0)
   eq(s(x0), s(x1))
   minsort(nil)
   minsort(cons(x0, x1))
   min(nil)
   min(cons(x0, nil))
   min(cons(x0, cons(x1, x2)))
   if1(true, x0, x1, x2)
   if1(false, x0, x1, x2)
   rm(x0, nil)
   rm(x0, cons(x1, x2))
   if2(true, x0, x1, x2)
   if2(false, x0, x1, x2)


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

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

   LE(s(x), s(y)) -> LE(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:
*LE(s(x), s(y)) -> LE(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:

   MIN(cons(x, cons(y, xs))) -> IF1(le(x, y), x, y, xs)
   IF1(true, x, y, xs) -> MIN(cons(x, xs))
   IF1(false, x, y, xs) -> MIN(cons(y, xs))

The TRS R consists of the following rules:

   le(0, y) -> true
   le(s(x), 0) -> false
   le(s(x), s(y)) -> le(x, y)
   eq(0, 0) -> true
   eq(0, s(y)) -> false
   eq(s(x), 0) -> false
   eq(s(x), s(y)) -> eq(x, y)
   minsort(nil) -> nil
   minsort(cons(x, xs)) -> cons(min(cons(x, xs)), minsort(rm(min(cons(x, xs)), cons(x, xs))))
   min(nil) -> 0
   min(cons(x, nil)) -> x
   min(cons(x, cons(y, xs))) -> if1(le(x, y), x, y, xs)
   if1(true, x, y, xs) -> min(cons(x, xs))
   if1(false, x, y, xs) -> min(cons(y, xs))
   rm(x, nil) -> nil
   rm(x, cons(y, xs)) -> if2(eq(x, y), x, y, xs)
   if2(true, x, y, xs) -> rm(x, xs)
   if2(false, x, y, xs) -> cons(y, rm(x, xs))

The set Q consists of the following terms:

   le(0, x0)
   le(s(x0), 0)
   le(s(x0), s(x1))
   eq(0, 0)
   eq(0, s(x0))
   eq(s(x0), 0)
   eq(s(x0), s(x1))
   minsort(nil)
   minsort(cons(x0, x1))
   min(nil)
   min(cons(x0, nil))
   min(cons(x0, cons(x1, x2)))
   if1(true, x0, x1, x2)
   if1(false, x0, x1, x2)
   rm(x0, nil)
   rm(x0, cons(x1, x2))
   if2(true, x0, x1, x2)
   if2(false, x0, x1, x2)

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:

   MIN(cons(x, cons(y, xs))) -> IF1(le(x, y), x, y, xs)
   IF1(true, x, y, xs) -> MIN(cons(x, xs))
   IF1(false, x, y, xs) -> MIN(cons(y, xs))

The TRS R consists of the following rules:

   le(0, y) -> true
   le(s(x), 0) -> false
   le(s(x), s(y)) -> le(x, y)

The set Q consists of the following terms:

   le(0, x0)
   le(s(x0), 0)
   le(s(x0), s(x1))
   eq(0, 0)
   eq(0, s(x0))
   eq(s(x0), 0)
   eq(s(x0), s(x1))
   minsort(nil)
   minsort(cons(x0, x1))
   min(nil)
   min(cons(x0, nil))
   min(cons(x0, cons(x1, x2)))
   if1(true, x0, x1, x2)
   if1(false, x0, x1, x2)
   rm(x0, nil)
   rm(x0, cons(x1, x2))
   if2(true, x0, x1, x2)
   if2(false, x0, x1, x2)

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].

   eq(0, 0)
   eq(0, s(x0))
   eq(s(x0), 0)
   eq(s(x0), s(x1))
   minsort(nil)
   minsort(cons(x0, x1))
   min(nil)
   min(cons(x0, nil))
   min(cons(x0, cons(x1, x2)))
   if1(true, x0, x1, x2)
   if1(false, x0, x1, x2)
   rm(x0, nil)
   rm(x0, cons(x1, x2))
   if2(true, x0, x1, x2)
   if2(false, x0, x1, x2)


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

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

   MIN(cons(x, cons(y, xs))) -> IF1(le(x, y), x, y, xs)
   IF1(true, x, y, xs) -> MIN(cons(x, xs))
   IF1(false, x, y, xs) -> MIN(cons(y, xs))

The TRS R consists of the following rules:

   le(0, y) -> true
   le(s(x), 0) -> false
   le(s(x), s(y)) -> le(x, y)

The set Q consists of the following terms:

   le(0, x0)
   le(s(x0), 0)
   le(s(x0), s(x1))

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

(33) QDPOrderProof (EQUIVALENT)
We use the reduction pair processor [LPAR04,JAR06].


The following pairs can be oriented strictly and are deleted.

   MIN(cons(x, cons(y, xs))) -> IF1(le(x, y), x, y, xs)
The remaining pairs can at least be oriented weakly.
Used ordering:  Polynomial Order [NEGPOLO,POLO] with Interpretation:

POL( IF1_4(x_1, ..., x_4) ) = x_4
POL( le_2(x_1, x_2) ) = 0
POL( 0 ) = 0
POL( true ) = 0
POL( s_1(x_1) ) = 2x_1 + 2
POL( false ) = 0
POL( MIN_1(x_1) ) = max{0, x_1 - 2}
POL( cons_2(x_1, x_2) ) = x_2 + 2

The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented:
none


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

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

   IF1(true, x, y, xs) -> MIN(cons(x, xs))
   IF1(false, x, y, xs) -> MIN(cons(y, xs))

The TRS R consists of the following rules:

   le(0, y) -> true
   le(s(x), 0) -> false
   le(s(x), s(y)) -> le(x, y)

The set Q consists of the following terms:

   le(0, x0)
   le(s(x0), 0)
   le(s(x0), s(x1))

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

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

(36)
TRUE

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

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

   MINSORT(cons(x, xs)) -> MINSORT(rm(min(cons(x, xs)), cons(x, xs)))

The TRS R consists of the following rules:

   le(0, y) -> true
   le(s(x), 0) -> false
   le(s(x), s(y)) -> le(x, y)
   eq(0, 0) -> true
   eq(0, s(y)) -> false
   eq(s(x), 0) -> false
   eq(s(x), s(y)) -> eq(x, y)
   minsort(nil) -> nil
   minsort(cons(x, xs)) -> cons(min(cons(x, xs)), minsort(rm(min(cons(x, xs)), cons(x, xs))))
   min(nil) -> 0
   min(cons(x, nil)) -> x
   min(cons(x, cons(y, xs))) -> if1(le(x, y), x, y, xs)
   if1(true, x, y, xs) -> min(cons(x, xs))
   if1(false, x, y, xs) -> min(cons(y, xs))
   rm(x, nil) -> nil
   rm(x, cons(y, xs)) -> if2(eq(x, y), x, y, xs)
   if2(true, x, y, xs) -> rm(x, xs)
   if2(false, x, y, xs) -> cons(y, rm(x, xs))

The set Q consists of the following terms:

   le(0, x0)
   le(s(x0), 0)
   le(s(x0), s(x1))
   eq(0, 0)
   eq(0, s(x0))
   eq(s(x0), 0)
   eq(s(x0), s(x1))
   minsort(nil)
   minsort(cons(x0, x1))
   min(nil)
   min(cons(x0, nil))
   min(cons(x0, cons(x1, x2)))
   if1(true, x0, x1, x2)
   if1(false, x0, x1, x2)
   rm(x0, nil)
   rm(x0, cons(x1, x2))
   if2(true, x0, x1, x2)
   if2(false, x0, x1, x2)

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

(38) 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.
----------------------------------------

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

   MINSORT(cons(x, xs)) -> MINSORT(rm(min(cons(x, xs)), cons(x, xs)))

The TRS R consists of the following rules:

   min(cons(x, nil)) -> x
   min(cons(x, cons(y, xs))) -> if1(le(x, y), x, y, xs)
   if1(true, x, y, xs) -> min(cons(x, xs))
   if1(false, x, y, xs) -> min(cons(y, xs))
   rm(x, cons(y, xs)) -> if2(eq(x, y), x, y, xs)
   if2(true, x, y, xs) -> rm(x, xs)
   eq(0, 0) -> true
   eq(0, s(y)) -> false
   eq(s(x), 0) -> false
   eq(s(x), s(y)) -> eq(x, y)
   if2(false, x, y, xs) -> cons(y, rm(x, xs))
   rm(x, nil) -> nil
   le(0, y) -> true
   le(s(x), 0) -> false
   le(s(x), s(y)) -> le(x, y)

The set Q consists of the following terms:

   le(0, x0)
   le(s(x0), 0)
   le(s(x0), s(x1))
   eq(0, 0)
   eq(0, s(x0))
   eq(s(x0), 0)
   eq(s(x0), s(x1))
   minsort(nil)
   minsort(cons(x0, x1))
   min(nil)
   min(cons(x0, nil))
   min(cons(x0, cons(x1, x2)))
   if1(true, x0, x1, x2)
   if1(false, x0, x1, x2)
   rm(x0, nil)
   rm(x0, cons(x1, x2))
   if2(true, x0, x1, x2)
   if2(false, x0, x1, x2)

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

(40) 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].

   minsort(nil)
   minsort(cons(x0, x1))


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

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

   MINSORT(cons(x, xs)) -> MINSORT(rm(min(cons(x, xs)), cons(x, xs)))

The TRS R consists of the following rules:

   min(cons(x, nil)) -> x
   min(cons(x, cons(y, xs))) -> if1(le(x, y), x, y, xs)
   if1(true, x, y, xs) -> min(cons(x, xs))
   if1(false, x, y, xs) -> min(cons(y, xs))
   rm(x, cons(y, xs)) -> if2(eq(x, y), x, y, xs)
   if2(true, x, y, xs) -> rm(x, xs)
   eq(0, 0) -> true
   eq(0, s(y)) -> false
   eq(s(x), 0) -> false
   eq(s(x), s(y)) -> eq(x, y)
   if2(false, x, y, xs) -> cons(y, rm(x, xs))
   rm(x, nil) -> nil
   le(0, y) -> true
   le(s(x), 0) -> false
   le(s(x), s(y)) -> le(x, y)

The set Q consists of the following terms:

   le(0, x0)
   le(s(x0), 0)
   le(s(x0), s(x1))
   eq(0, 0)
   eq(0, s(x0))
   eq(s(x0), 0)
   eq(s(x0), s(x1))
   min(nil)
   min(cons(x0, nil))
   min(cons(x0, cons(x1, x2)))
   if1(true, x0, x1, x2)
   if1(false, x0, x1, x2)
   rm(x0, nil)
   rm(x0, cons(x1, x2))
   if2(true, x0, x1, x2)
   if2(false, x0, x1, x2)

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

(42) Induction-Processor (SOUND)

This DP could be deleted by the Induction-Processor:
MINSORT(cons(x, xs)) -> MINSORT(rm(min(cons(x, xs)), cons(x, xs)))


This order was computed:
Polynomial interpretation [POLO]:

   POL(0) = 0
   POL(MINSORT(x_1)) = 2*x_1
   POL(cons(x_1, x_2)) = 1 + x_1 + 2*x_2
   POL(eq(x_1, x_2)) = 0
   POL(false_renamed) = 0
   POL(if1(x_1, x_2, x_3, x_4)) = 2 + x_2 + x_3 + 2*x_4
   POL(if2(x_1, x_2, x_3, x_4)) = 1 + x_3 + 2*x_4
   POL(le(x_1, x_2)) = 0
   POL(min(x_1)) = x_1
   POL(nil) = 0
   POL(rm(x_1, x_2)) = x_2
   POL(s(x_1)) = 3*x_1
   POL(true_renamed) = 0

At least one of these decreasing rules is always used after the deleted DP:
if2(true_renamed, x4, y2, xs3) -> rm(x4, xs3)


The following formula is valid:
z0:sort[a35].(~(z0=nil)->rm'(min(z0), z0)=true)


The transformed set:
rm'(x3, cons(y1, xs2)) -> if2'(eq(x3, y1), x3, y1, xs2)
if2'(true_renamed, x4, y2, xs3) -> true
if2'(false_renamed, x7, y5, xs4) -> rm'(x7, xs4)
rm'(x8, nil) -> false
min(cons(x', nil)) -> x'
min(cons(x'', cons(y, xs'))) -> if1(le(x'', y), x'', y, xs')
if1(true_renamed, x1, y', xs'') -> min(cons(x1, xs''))
if1(false_renamed, x2, y'', xs1) -> min(cons(y'', xs1))
rm(x3, cons(y1, xs2)) -> if2(eq(x3, y1), x3, y1, xs2)
if2(true_renamed, x4, y2, xs3) -> rm(x4, xs3)
eq(0, 0) -> true_renamed
eq(0, s(y3)) -> false_renamed
eq(s(x5), 0) -> false_renamed
eq(s(x6), s(y4)) -> eq(x6, y4)
if2(false_renamed, x7, y5, xs4) -> cons(y5, rm(x7, xs4))
rm(x8, nil) -> nil
le(0, y6) -> true_renamed
le(s(x9), 0) -> false_renamed
le(s(x10), s(y7)) -> le(x10, y7)
min(nil) -> 0
equal_bool(true, false) -> false
equal_bool(false, true) -> false
equal_bool(true, true) -> true
equal_bool(false, false) -> true
and(true, x) -> x
and(false, x) -> false
or(true, x) -> true
or(false, x) -> x
not(false) -> true
not(true) -> false
isa_true(true) -> true
isa_true(false) -> false
isa_false(true) -> false
isa_false(false) -> true
equal_sort[a0](0, 0) -> true
equal_sort[a0](0, s(v26)) -> false
equal_sort[a0](s(v27), 0) -> false
equal_sort[a0](s(v27), s(v28)) -> equal_sort[a0](v27, v28)
equal_sort[a35](cons(v29, v30), cons(v31, v32)) -> and(equal_sort[a0](v29, v31), equal_sort[a35](v30, v32))
equal_sort[a35](cons(v29, v30), nil) -> false
equal_sort[a35](nil, cons(v33, v34)) -> false
equal_sort[a35](nil, nil) -> true
equal_sort[a43](true_renamed, true_renamed) -> true
equal_sort[a43](true_renamed, false_renamed) -> false
equal_sort[a43](false_renamed, true_renamed) -> false
equal_sort[a43](false_renamed, false_renamed) -> true
equal_sort[a61](witness_sort[a61], witness_sort[a61]) -> true


The proof given by the theorem prover:
The following output was given by the internal theorem prover:proof of internal
# AProVE Commit ID: 794c25de1cacf0d048858bcd21c9a779e1221865 marcel 20200619 unpublished dirty


Partial correctness of the following Program

   [x, v26, v27, v28, v29, v30, v31, v32, v33, v34, x4, y2, xs3, x7, y5, y1, xs2, x8, x3, x', x'', y, xs', y3, x5, x6, y4, y6, x9, x10, y7, x1, y', x2, y'', xs'', xs1]
   equal_bool(true, false) -> false
   equal_bool(false, true) -> false
   equal_bool(true, true) -> true
   equal_bool(false, false) -> true
   true and x -> x
   false and x -> false
   true or x -> true
   false or x -> x
   not(false) -> true
   not(true) -> false
   isa_true(true) -> true
   isa_true(false) -> false
   isa_false(true) -> false
   isa_false(false) -> true
   equal_sort[a0](0, 0) -> true
   equal_sort[a0](0, s(v26)) -> false
   equal_sort[a0](s(v27), 0) -> false
   equal_sort[a0](s(v27), s(v28)) -> equal_sort[a0](v27, v28)
   equal_sort[a35](cons(v29, v30), cons(v31, v32)) -> equal_sort[a0](v29, v31) and equal_sort[a35](v30, v32)
   equal_sort[a35](cons(v29, v30), nil) -> false
   equal_sort[a35](nil, cons(v33, v34)) -> false
   equal_sort[a35](nil, nil) -> true
   equal_sort[a43](true_renamed, true_renamed) -> true
   equal_sort[a43](true_renamed, false_renamed) -> false
   equal_sort[a43](false_renamed, true_renamed) -> false
   equal_sort[a43](false_renamed, false_renamed) -> true
   equal_sort[a61](witness_sort[a61], witness_sort[a61]) -> true
   if2'(true_renamed, x4, y2, xs3) -> true
   if2'(false_renamed, x7, y5, cons(y1, xs2)) -> if2'(eq(x7, y1), x7, y1, xs2)
   if2'(false_renamed, x7, y5, nil) -> false
   rm'(x8, nil) -> false
   equal_sort[a43](eq(x3, y1), true_renamed) -> true | rm'(x3, cons(y1, xs2)) -> true
   equal_sort[a43](eq(x3, y1), true_renamed) -> false | rm'(x3, cons(y1, xs2)) -> rm'(x3, xs2)
   min(cons(x', nil)) -> x'
   min(nil) -> 0
   equal_sort[a43](le(x'', y), true_renamed) -> true | min(cons(x'', cons(y, xs'))) -> min(cons(x'', xs'))
   equal_sort[a43](le(x'', y), true_renamed) -> false | min(cons(x'', cons(y, xs'))) -> min(cons(y, xs'))
   eq(0, 0) -> true_renamed
   eq(0, s(y3)) -> false_renamed
   eq(s(x5), 0) -> false_renamed
   eq(s(x6), s(y4)) -> eq(x6, y4)
   rm(x8, nil) -> nil
   equal_sort[a43](eq(x3, y1), true_renamed) -> true | rm(x3, cons(y1, xs2)) -> rm(x3, xs2)
   equal_sort[a43](eq(x3, y1), true_renamed) -> false | rm(x3, cons(y1, xs2)) -> cons(y1, rm(x3, xs2))
   le(0, y6) -> true_renamed
   le(s(x9), 0) -> false_renamed
   le(s(x10), s(y7)) -> le(x10, y7)
   if1(true_renamed, x1, y', nil) -> x1
   if1(true_renamed, x1, y', cons(y, xs')) -> if1(le(x1, y), x1, y, xs')
   if1(false_renamed, x2, y'', nil) -> y''
   if1(false_renamed, x2, y'', cons(y, xs')) -> if1(le(y'', y), y'', y, xs')
   if1(true_renamed, x1, y', xs'') -> 0
   if1(false_renamed, x2, y'', xs1) -> 0
   if2(true_renamed, x4, y2, cons(y1, xs2)) -> if2(eq(x4, y1), x4, y1, xs2)
   if2(true_renamed, x4, y2, nil) -> nil
   if2(false_renamed, x7, y5, cons(y1, xs2)) -> cons(y5, if2(eq(x7, y1), x7, y1, xs2))
   if2(false_renamed, x7, y5, nil) -> cons(y5, nil)

using the following formula:
z0:sort[a35].(~(z0=nil)->rm'(min(z0), z0)=true)

could be successfully shown:
(0) Formula
(1) Induction by algorithm [EQUIVALENT, 0 ms]
(2) AND
    (3) Formula
        (4) Symbolic evaluation [EQUIVALENT, 0 ms]
        (5) Formula
        (6) Induction by data structure [EQUIVALENT, 0 ms]
        (7) AND
            (8) Formula
                (9) Symbolic evaluation [EQUIVALENT, 0 ms]
                (10) YES
            (11) Formula
                (12) Conditional Evaluation [EQUIVALENT, 0 ms]
                (13) AND
                    (14) Formula
                        (15) Symbolic evaluation [EQUIVALENT, 0 ms]
                        (16) YES
                    (17) Formula
                        (18) Symbolic evaluation [EQUIVALENT, 0 ms]
                        (19) Formula
                        (20) Hypothesis Lifting [EQUIVALENT, 0 ms]
                        (21) Formula
                        (22) Symbolic evaluation under hypothesis [SOUND, 0 ms]
                        (23) Formula
                        (24) Hypothesis Lifting [EQUIVALENT, 0 ms]
                        (25) Formula
                        (26) Hypothesis Lifting [EQUIVALENT, 0 ms]
                        (27) Formula
                        (28) Conditional Evaluation [EQUIVALENT, 0 ms]
                        (29) AND
                            (30) Formula
                                (31) Symbolic evaluation under hypothesis [EQUIVALENT, 0 ms]
                                (32) YES
                            (33) Formula
                                (34) Symbolic evaluation [EQUIVALENT, 0 ms]
                                (35) YES
    (36) Formula
        (37) Symbolic evaluation [EQUIVALENT, 0 ms]
        (38) YES
    (39) Formula
        (40) Symbolic evaluation [EQUIVALENT, 0 ms]
        (41) Formula
        (42) Conditional Evaluation [EQUIVALENT, 0 ms]
        (43) Formula
        (44) Conditional Evaluation [EQUIVALENT, 0 ms]
        (45) AND
            (46) Formula
                (47) Symbolic evaluation [EQUIVALENT, 0 ms]
                (48) YES
            (49) Formula
                (50) Conditional Evaluation [EQUIVALENT, 0 ms]
                (51) AND
                    (52) Formula
                        (53) Symbolic evaluation [EQUIVALENT, 0 ms]
                        (54) YES
                    (55) Formula
                        (56) Hypothesis Lifting [EQUIVALENT, 0 ms]
                        (57) Formula
                        (58) Conditional Evaluation [EQUIVALENT, 0 ms]
                        (59) Formula
                        (60) Symbolic evaluation [EQUIVALENT, 0 ms]
                        (61) YES
    (62) Formula
        (63) Symbolic evaluation [EQUIVALENT, 0 ms]
        (64) Formula
        (65) Conditional Evaluation [EQUIVALENT, 0 ms]
        (66) Formula
        (67) Conditional Evaluation [EQUIVALENT, 0 ms]
        (68) AND
            (69) Formula
                (70) Symbolic evaluation [EQUIVALENT, 0 ms]
                (71) YES
            (72) Formula
                (73) Symbolic evaluation under hypothesis [EQUIVALENT, 0 ms]
                (74) YES


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

(0)
Obligation:
Formula:
z0:sort[a35].(~(z0=nil)->rm'(min(z0), z0)=true)

There are no hypotheses.




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

(1) Induction by algorithm (EQUIVALENT)
Induction by algorithm min(z0) generates the following cases:

1. Base Case:
Formula:
x':sort[a0].(~(cons(x', nil)=nil)->rm'(min(cons(x', nil)), cons(x', nil))=true)

There are no hypotheses.





2. Base Case:
Formula:
(~(nil=nil)->rm'(min(nil), nil)=true)

There are no hypotheses.





1. Step Case:
Formula:
x'':sort[a0],y:sort[a0],xs':sort[a35].(~(cons(x'', cons(y, xs'))=nil)->rm'(min(cons(x'', cons(y, xs'))), cons(x'', cons(y, xs')))=true)

Hypotheses:
x'':sort[a0],xs':sort[a35].rm'(min(cons(x'', xs')), cons(x'', xs'))=true
x'':sort[a0],y:sort[a0].equal_sort[a43](le(x'', y), true_renamed)=true





2. Step Case:
Formula:
x'':sort[a0],y:sort[a0],xs':sort[a35].(~(cons(x'', cons(y, xs'))=nil)->rm'(min(cons(x'', cons(y, xs'))), cons(x'', cons(y, xs')))=true)

Hypotheses:
y:sort[a0],xs':sort[a35].rm'(min(cons(y, xs')), cons(y, xs'))=true
x'':sort[a0],y:sort[a0].equal_sort[a43](le(x'', y), true_renamed)=false






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

(2)
Complex Obligation (AND)

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

(3)
Obligation:
Formula:
x':sort[a0].(~(cons(x', nil)=nil)->rm'(min(cons(x', nil)), cons(x', nil))=true)

There are no hypotheses.




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

(4) Symbolic evaluation (EQUIVALENT)
Could be shown by simple symbolic evaluation.
----------------------------------------

(5)
Obligation:
Formula:
x':sort[a0].rm'(x', cons(x', nil))=true

There are no hypotheses.




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

(6) Induction by data structure (EQUIVALENT)
Induction by data structure sort[a0] generates the following cases:



1. Base Case:
Formula:
rm'(0, cons(0, nil))=true

There are no hypotheses.





1. Step Case:
Formula:
n:sort[a0].rm'(s(n), cons(s(n), nil))=true

Hypotheses:
n:sort[a0].rm'(n, cons(n, nil))=true






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

(7)
Complex Obligation (AND)

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

(8)
Obligation:
Formula:
rm'(0, cons(0, nil))=true

There are no hypotheses.




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

(9) Symbolic evaluation (EQUIVALENT)
Could be reduced to the following new obligation by simple symbolic evaluation:
True
----------------------------------------

(10)
YES

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

(11)
Obligation:
Formula:
n:sort[a0].rm'(s(n), cons(s(n), nil))=true

Hypotheses:
n:sort[a0].rm'(n, cons(n, nil))=true




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

(12) Conditional Evaluation (EQUIVALENT)
The formula could be reduced to the following new obligations by conditional evaluation:
Formula:
true=true

Hypotheses:
n:sort[a0].rm'(n, cons(n, nil))=true
n:sort[a0].equal_sort[a43](eq(s(n), s(n)), true_renamed)=true





Formula:
n:sort[a0].rm'(s(n), nil)=true

Hypotheses:
n:sort[a0].rm'(n, cons(n, nil))=true
n:sort[a0].equal_sort[a43](eq(s(n), s(n)), true_renamed)=false






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

(13)
Complex Obligation (AND)

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

(14)
Obligation:
Formula:
true=true

Hypotheses:
n:sort[a0].rm'(n, cons(n, nil))=true
n:sort[a0].equal_sort[a43](eq(s(n), s(n)), true_renamed)=true




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

(15) Symbolic evaluation (EQUIVALENT)
Could be reduced to the following new obligation by simple symbolic evaluation:
True
----------------------------------------

(16)
YES

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

(17)
Obligation:
Formula:
n:sort[a0].rm'(s(n), nil)=true

Hypotheses:
n:sort[a0].rm'(n, cons(n, nil))=true
n:sort[a0].equal_sort[a43](eq(s(n), s(n)), true_renamed)=false




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

(18) Symbolic evaluation (EQUIVALENT)
Could be shown by simple symbolic evaluation.
----------------------------------------

(19)
Obligation:
Formula:
False

Hypotheses:
n:sort[a0].rm'(n, cons(n, nil))=true
n:sort[a0].equal_sort[a43](eq(s(n), s(n)), true_renamed)=false




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

(20) Hypothesis Lifting (EQUIVALENT)
Formula could be generalised by hypothesis lifting to the following new obligation:
Formula:
n:sort[a0].((rm'(n, cons(n, nil))=true/\equal_sort[a43](eq(s(n), s(n)), true_renamed)=false)->False)

Hypotheses:
n:sort[a0].rm'(n, cons(n, nil))=true
n:sort[a0].equal_sort[a43](eq(s(n), s(n)), true_renamed)=false




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

(21)
Obligation:
Formula:
n:sort[a0].((rm'(n, cons(n, nil))=true/\equal_sort[a43](eq(s(n), s(n)), true_renamed)=false)->False)

Hypotheses:
n:sort[a0].rm'(n, cons(n, nil))=true
n:sort[a0].equal_sort[a43](eq(s(n), s(n)), true_renamed)=false




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

(22) Symbolic evaluation under hypothesis (SOUND)
Could be reduced by symbolic evaluation under hypothesis to:
n:sort[a0].~(equal_sort[a43](eq(n, n), true_renamed)=false)

By using the following hypotheses:
n:sort[a0].rm'(n, cons(n, nil))=true

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

(23)
Obligation:
Formula:
n:sort[a0].~(equal_sort[a43](eq(n, n), true_renamed)=false)

Hypotheses:
n:sort[a0].rm'(n, cons(n, nil))=true
n:sort[a0].equal_sort[a43](eq(s(n), s(n)), true_renamed)=false




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

(24) Hypothesis Lifting (EQUIVALENT)
Formula could be generalised by hypothesis lifting to the following new obligation:
Formula:
n:sort[a0].(equal_sort[a43](eq(n, n), true_renamed)=false->~(equal_sort[a43](eq(n, n), true_renamed)=false))

Hypotheses:
n:sort[a0].rm'(n, cons(n, nil))=true




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

(25)
Obligation:
Formula:
n:sort[a0].(equal_sort[a43](eq(n, n), true_renamed)=false->~(equal_sort[a43](eq(n, n), true_renamed)=false))

Hypotheses:
n:sort[a0].rm'(n, cons(n, nil))=true




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

(26) Hypothesis Lifting (EQUIVALENT)
Formula could be generalised by hypothesis lifting to the following new obligation:
Formula:
n:sort[a0].(rm'(n, cons(n, nil))=true->(equal_sort[a43](eq(n, n), true_renamed)=false->~(equal_sort[a43](eq(n, n), true_renamed)=false)))

There are no hypotheses.




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

(27)
Obligation:
Formula:
n:sort[a0].(rm'(n, cons(n, nil))=true->(equal_sort[a43](eq(n, n), true_renamed)=false->~(equal_sort[a43](eq(n, n), true_renamed)=false)))

There are no hypotheses.




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

(28) Conditional Evaluation (EQUIVALENT)
The formula could be reduced to the following new obligations by conditional evaluation:
Formula:
n:sort[a0].(true=true->(equal_sort[a43](eq(n, n), true_renamed)=false->~(equal_sort[a43](eq(n, n), true_renamed)=false)))

Hypotheses:
n:sort[a0].equal_sort[a43](eq(n, n), true_renamed)=true





Formula:
n:sort[a0].(rm'(n, nil)=true->(equal_sort[a43](eq(n, n), true_renamed)=false->~(equal_sort[a43](eq(n, n), true_renamed)=false)))

Hypotheses:
n:sort[a0].equal_sort[a43](eq(n, n), true_renamed)=false






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

(29)
Complex Obligation (AND)

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

(30)
Obligation:
Formula:
n:sort[a0].(true=true->(equal_sort[a43](eq(n, n), true_renamed)=false->~(equal_sort[a43](eq(n, n), true_renamed)=false)))

Hypotheses:
n:sort[a0].equal_sort[a43](eq(n, n), true_renamed)=true




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

(31) Symbolic evaluation under hypothesis (EQUIVALENT)
Could be shown using symbolic evaluation under hypothesis, by using the following hypotheses:

n:sort[a0].equal_sort[a43](eq(n, n), true_renamed)=true

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

(32)
YES

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

(33)
Obligation:
Formula:
n:sort[a0].(rm'(n, nil)=true->(equal_sort[a43](eq(n, n), true_renamed)=false->~(equal_sort[a43](eq(n, n), true_renamed)=false)))

Hypotheses:
n:sort[a0].equal_sort[a43](eq(n, n), true_renamed)=false




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

(34) Symbolic evaluation (EQUIVALENT)
Could be reduced to the following new obligation by simple symbolic evaluation:
True
----------------------------------------

(35)
YES

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

(36)
Obligation:
Formula:
(~(nil=nil)->rm'(min(nil), nil)=true)

There are no hypotheses.




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

(37) Symbolic evaluation (EQUIVALENT)
Could be reduced to the following new obligation by simple symbolic evaluation:
True
----------------------------------------

(38)
YES

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

(39)
Obligation:
Formula:
x'':sort[a0],y:sort[a0],xs':sort[a35].(~(cons(x'', cons(y, xs'))=nil)->rm'(min(cons(x'', cons(y, xs'))), cons(x'', cons(y, xs')))=true)

Hypotheses:
x'':sort[a0],xs':sort[a35].rm'(min(cons(x'', xs')), cons(x'', xs'))=true
x'':sort[a0],y:sort[a0].equal_sort[a43](le(x'', y), true_renamed)=true




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

(40) Symbolic evaluation (EQUIVALENT)
Could be shown by simple symbolic evaluation.
----------------------------------------

(41)
Obligation:
Formula:
x'':sort[a0],y:sort[a0],xs':sort[a35].rm'(min(cons(x'', cons(y, xs'))), cons(x'', cons(y, xs')))=true

Hypotheses:
x'':sort[a0],xs':sort[a35].rm'(min(cons(x'', xs')), cons(x'', xs'))=true
x'':sort[a0],y:sort[a0].equal_sort[a43](le(x'', y), true_renamed)=true




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

(42) Conditional Evaluation (EQUIVALENT)
The formula could be reduced to the following new obligations by conditional evaluation:
Formula:
x'':sort[a0],xs':sort[a35],y:sort[a0].rm'(min(cons(x'', xs')), cons(x'', cons(y, xs')))=true

Hypotheses:
x'':sort[a0],xs':sort[a35].rm'(min(cons(x'', xs')), cons(x'', xs'))=true
x'':sort[a0],y:sort[a0].equal_sort[a43](le(x'', y), true_renamed)=true






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

(43)
Obligation:
Formula:
x'':sort[a0],xs':sort[a35],y:sort[a0].rm'(min(cons(x'', xs')), cons(x'', cons(y, xs')))=true

Hypotheses:
x'':sort[a0],xs':sort[a35].rm'(min(cons(x'', xs')), cons(x'', xs'))=true
x'':sort[a0],y:sort[a0].equal_sort[a43](le(x'', y), true_renamed)=true




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

(44) Conditional Evaluation (EQUIVALENT)
The formula could be reduced to the following new obligations by conditional evaluation:
Formula:
true=true

Hypotheses:
x'':sort[a0],xs':sort[a35].rm'(min(cons(x'', xs')), cons(x'', xs'))=true
x'':sort[a0],y:sort[a0].equal_sort[a43](le(x'', y), true_renamed)=true
x'':sort[a0],xs':sort[a35].equal_sort[a43](eq(min(cons(x'', xs')), x''), true_renamed)=true





Formula:
x'':sort[a0],xs':sort[a35],y:sort[a0].rm'(min(cons(x'', xs')), cons(y, xs'))=true

Hypotheses:
x'':sort[a0],xs':sort[a35].rm'(min(cons(x'', xs')), cons(x'', xs'))=true
x'':sort[a0],y:sort[a0].equal_sort[a43](le(x'', y), true_renamed)=true
x'':sort[a0],xs':sort[a35].equal_sort[a43](eq(min(cons(x'', xs')), x''), true_renamed)=false






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

(45)
Complex Obligation (AND)

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

(46)
Obligation:
Formula:
true=true

Hypotheses:
x'':sort[a0],xs':sort[a35].rm'(min(cons(x'', xs')), cons(x'', xs'))=true
x'':sort[a0],y:sort[a0].equal_sort[a43](le(x'', y), true_renamed)=true
x'':sort[a0],xs':sort[a35].equal_sort[a43](eq(min(cons(x'', xs')), x''), true_renamed)=true




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

(47) Symbolic evaluation (EQUIVALENT)
Could be reduced to the following new obligation by simple symbolic evaluation:
True
----------------------------------------

(48)
YES

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

(49)
Obligation:
Formula:
x'':sort[a0],xs':sort[a35],y:sort[a0].rm'(min(cons(x'', xs')), cons(y, xs'))=true

Hypotheses:
x'':sort[a0],xs':sort[a35].rm'(min(cons(x'', xs')), cons(x'', xs'))=true
x'':sort[a0],y:sort[a0].equal_sort[a43](le(x'', y), true_renamed)=true
x'':sort[a0],xs':sort[a35].equal_sort[a43](eq(min(cons(x'', xs')), x''), true_renamed)=false




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

(50) Conditional Evaluation (EQUIVALENT)
The formula could be reduced to the following new obligations by conditional evaluation:
Formula:
true=true

Hypotheses:
x'':sort[a0],xs':sort[a35].rm'(min(cons(x'', xs')), cons(x'', xs'))=true
x'':sort[a0],y:sort[a0].equal_sort[a43](le(x'', y), true_renamed)=true
x'':sort[a0],xs':sort[a35].equal_sort[a43](eq(min(cons(x'', xs')), x''), true_renamed)=false
x'':sort[a0],xs':sort[a35],y:sort[a0].equal_sort[a43](eq(min(cons(x'', xs')), y), true_renamed)=true





Formula:
x'':sort[a0],xs':sort[a35].rm'(min(cons(x'', xs')), xs')=true

Hypotheses:
x'':sort[a0],xs':sort[a35].rm'(min(cons(x'', xs')), cons(x'', xs'))=true
x'':sort[a0],y:sort[a0].equal_sort[a43](le(x'', y), true_renamed)=true
x'':sort[a0],xs':sort[a35].equal_sort[a43](eq(min(cons(x'', xs')), x''), true_renamed)=false
x'':sort[a0],xs':sort[a35],y:sort[a0].equal_sort[a43](eq(min(cons(x'', xs')), y), true_renamed)=false






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

(51)
Complex Obligation (AND)

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

(52)
Obligation:
Formula:
true=true

Hypotheses:
x'':sort[a0],xs':sort[a35].rm'(min(cons(x'', xs')), cons(x'', xs'))=true
x'':sort[a0],y:sort[a0].equal_sort[a43](le(x'', y), true_renamed)=true
x'':sort[a0],xs':sort[a35].equal_sort[a43](eq(min(cons(x'', xs')), x''), true_renamed)=false
x'':sort[a0],xs':sort[a35],y:sort[a0].equal_sort[a43](eq(min(cons(x'', xs')), y), true_renamed)=true




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

(53) Symbolic evaluation (EQUIVALENT)
Could be reduced to the following new obligation by simple symbolic evaluation:
True
----------------------------------------

(54)
YES

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

(55)
Obligation:
Formula:
x'':sort[a0],xs':sort[a35].rm'(min(cons(x'', xs')), xs')=true

Hypotheses:
x'':sort[a0],xs':sort[a35].rm'(min(cons(x'', xs')), cons(x'', xs'))=true
x'':sort[a0],y:sort[a0].equal_sort[a43](le(x'', y), true_renamed)=true
x'':sort[a0],xs':sort[a35].equal_sort[a43](eq(min(cons(x'', xs')), x''), true_renamed)=false
x'':sort[a0],xs':sort[a35],y:sort[a0].equal_sort[a43](eq(min(cons(x'', xs')), y), true_renamed)=false




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

(56) Hypothesis Lifting (EQUIVALENT)
Formula could be generalised by hypothesis lifting to the following new obligation:
Formula:
x'':sort[a0],xs':sort[a35].(rm'(min(cons(x'', xs')), cons(x'', xs'))=true->rm'(min(cons(x'', xs')), xs')=true)

Hypotheses:
x'':sort[a0],y:sort[a0].equal_sort[a43](le(x'', y), true_renamed)=true
x'':sort[a0],xs':sort[a35].equal_sort[a43](eq(min(cons(x'', xs')), x''), true_renamed)=false
x'':sort[a0],xs':sort[a35],y:sort[a0].equal_sort[a43](eq(min(cons(x'', xs')), y), true_renamed)=false




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

(57)
Obligation:
Formula:
x'':sort[a0],xs':sort[a35].(rm'(min(cons(x'', xs')), cons(x'', xs'))=true->rm'(min(cons(x'', xs')), xs')=true)

Hypotheses:
x'':sort[a0],y:sort[a0].equal_sort[a43](le(x'', y), true_renamed)=true
x'':sort[a0],xs':sort[a35].equal_sort[a43](eq(min(cons(x'', xs')), x''), true_renamed)=false
x'':sort[a0],xs':sort[a35],y:sort[a0].equal_sort[a43](eq(min(cons(x'', xs')), y), true_renamed)=false




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

(58) Conditional Evaluation (EQUIVALENT)
The formula could be reduced to the following new obligations by conditional evaluation:
Formula:
x'':sort[a0],xs':sort[a35].(rm'(min(cons(x'', xs')), xs')=true->rm'(min(cons(x'', xs')), xs')=true)

Hypotheses:
x'':sort[a0],y:sort[a0].equal_sort[a43](le(x'', y), true_renamed)=true
x'':sort[a0],xs':sort[a35].equal_sort[a43](eq(min(cons(x'', xs')), x''), true_renamed)=false
x'':sort[a0],xs':sort[a35],y:sort[a0].equal_sort[a43](eq(min(cons(x'', xs')), y), true_renamed)=false






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

(59)
Obligation:
Formula:
x'':sort[a0],xs':sort[a35].(rm'(min(cons(x'', xs')), xs')=true->rm'(min(cons(x'', xs')), xs')=true)

Hypotheses:
x'':sort[a0],y:sort[a0].equal_sort[a43](le(x'', y), true_renamed)=true
x'':sort[a0],xs':sort[a35].equal_sort[a43](eq(min(cons(x'', xs')), x''), true_renamed)=false
x'':sort[a0],xs':sort[a35],y:sort[a0].equal_sort[a43](eq(min(cons(x'', xs')), y), true_renamed)=false




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

(60) Symbolic evaluation (EQUIVALENT)
Could be reduced to the following new obligation by simple symbolic evaluation:
True
----------------------------------------

(61)
YES

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

(62)
Obligation:
Formula:
x'':sort[a0],y:sort[a0],xs':sort[a35].(~(cons(x'', cons(y, xs'))=nil)->rm'(min(cons(x'', cons(y, xs'))), cons(x'', cons(y, xs')))=true)

Hypotheses:
y:sort[a0],xs':sort[a35].rm'(min(cons(y, xs')), cons(y, xs'))=true
x'':sort[a0],y:sort[a0].equal_sort[a43](le(x'', y), true_renamed)=false




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

(63) Symbolic evaluation (EQUIVALENT)
Could be shown by simple symbolic evaluation.
----------------------------------------

(64)
Obligation:
Formula:
x'':sort[a0],y:sort[a0],xs':sort[a35].rm'(min(cons(x'', cons(y, xs'))), cons(x'', cons(y, xs')))=true

Hypotheses:
y:sort[a0],xs':sort[a35].rm'(min(cons(y, xs')), cons(y, xs'))=true
x'':sort[a0],y:sort[a0].equal_sort[a43](le(x'', y), true_renamed)=false




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

(65) Conditional Evaluation (EQUIVALENT)
The formula could be reduced to the following new obligations by conditional evaluation:
Formula:
y:sort[a0],xs':sort[a35],x'':sort[a0].rm'(min(cons(y, xs')), cons(x'', cons(y, xs')))=true

Hypotheses:
y:sort[a0],xs':sort[a35].rm'(min(cons(y, xs')), cons(y, xs'))=true
x'':sort[a0],y:sort[a0].equal_sort[a43](le(x'', y), true_renamed)=false






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

(66)
Obligation:
Formula:
y:sort[a0],xs':sort[a35],x'':sort[a0].rm'(min(cons(y, xs')), cons(x'', cons(y, xs')))=true

Hypotheses:
y:sort[a0],xs':sort[a35].rm'(min(cons(y, xs')), cons(y, xs'))=true
x'':sort[a0],y:sort[a0].equal_sort[a43](le(x'', y), true_renamed)=false




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

(67) Conditional Evaluation (EQUIVALENT)
The formula could be reduced to the following new obligations by conditional evaluation:
Formula:
true=true

Hypotheses:
y:sort[a0],xs':sort[a35].rm'(min(cons(y, xs')), cons(y, xs'))=true
x'':sort[a0],y:sort[a0].equal_sort[a43](le(x'', y), true_renamed)=false
y:sort[a0],xs':sort[a35],x'':sort[a0].equal_sort[a43](eq(min(cons(y, xs')), x''), true_renamed)=true





Formula:
y:sort[a0],xs':sort[a35].rm'(min(cons(y, xs')), cons(y, xs'))=true

Hypotheses:
y:sort[a0],xs':sort[a35].rm'(min(cons(y, xs')), cons(y, xs'))=true
x'':sort[a0],y:sort[a0].equal_sort[a43](le(x'', y), true_renamed)=false
y:sort[a0],xs':sort[a35],x'':sort[a0].equal_sort[a43](eq(min(cons(y, xs')), x''), true_renamed)=false






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

(68)
Complex Obligation (AND)

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

(69)
Obligation:
Formula:
true=true

Hypotheses:
y:sort[a0],xs':sort[a35].rm'(min(cons(y, xs')), cons(y, xs'))=true
x'':sort[a0],y:sort[a0].equal_sort[a43](le(x'', y), true_renamed)=false
y:sort[a0],xs':sort[a35],x'':sort[a0].equal_sort[a43](eq(min(cons(y, xs')), x''), true_renamed)=true




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

(70) Symbolic evaluation (EQUIVALENT)
Could be reduced to the following new obligation by simple symbolic evaluation:
True
----------------------------------------

(71)
YES

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

(72)
Obligation:
Formula:
y:sort[a0],xs':sort[a35].rm'(min(cons(y, xs')), cons(y, xs'))=true

Hypotheses:
y:sort[a0],xs':sort[a35].rm'(min(cons(y, xs')), cons(y, xs'))=true
x'':sort[a0],y:sort[a0].equal_sort[a43](le(x'', y), true_renamed)=false
y:sort[a0],xs':sort[a35],x'':sort[a0].equal_sort[a43](eq(min(cons(y, xs')), x''), true_renamed)=false




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

(73) Symbolic evaluation under hypothesis (EQUIVALENT)
Could be shown using symbolic evaluation under hypothesis, by using the following hypotheses:

y:sort[a0],xs':sort[a35].rm'(min(cons(y, xs')), cons(y, xs'))=true

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

(74)
YES

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

(43)
Complex Obligation (AND)

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

(44)
Obligation:
Q DP problem:
P is empty.
The TRS R consists of the following rules:

   min(cons(x, nil)) -> x
   min(cons(x, cons(y, xs))) -> if1(le(x, y), x, y, xs)
   if1(true, x, y, xs) -> min(cons(x, xs))
   if1(false, x, y, xs) -> min(cons(y, xs))
   rm(x, cons(y, xs)) -> if2(eq(x, y), x, y, xs)
   if2(true, x, y, xs) -> rm(x, xs)
   eq(0, 0) -> true
   eq(0, s(y)) -> false
   eq(s(x), 0) -> false
   eq(s(x), s(y)) -> eq(x, y)
   if2(false, x, y, xs) -> cons(y, rm(x, xs))
   rm(x, nil) -> nil
   le(0, y) -> true
   le(s(x), 0) -> false
   le(s(x), s(y)) -> le(x, y)

The set Q consists of the following terms:

   le(0, x0)
   le(s(x0), 0)
   le(s(x0), s(x1))
   eq(0, 0)
   eq(0, s(x0))
   eq(s(x0), 0)
   eq(s(x0), s(x1))
   min(nil)
   min(cons(x0, nil))
   min(cons(x0, cons(x1, x2)))
   if1(true, x0, x1, x2)
   if1(false, x0, x1, x2)
   rm(x0, nil)
   rm(x0, cons(x1, x2))
   if2(true, x0, x1, x2)
   if2(false, x0, x1, x2)

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

(45) PisEmptyProof (EQUIVALENT)
The TRS P is empty. Hence, there is no (P,Q,R) chain.
----------------------------------------

(46)
YES

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

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

   rm'(x3, cons(y1, xs2)) -> if2'(eq(x3, y1), x3, y1, xs2)
   if2'(true_renamed, x4, y2, xs3) -> true
   if2'(false_renamed, x7, y5, xs4) -> rm'(x7, xs4)
   rm'(x8, nil) -> false
   min(cons(x', nil)) -> x'
   min(cons(x'', cons(y, xs'))) -> if1(le(x'', y), x'', y, xs')
   if1(true_renamed, x1, y', xs'') -> min(cons(x1, xs''))
   if1(false_renamed, x2, y'', xs1) -> min(cons(y'', xs1))
   rm(x3, cons(y1, xs2)) -> if2(eq(x3, y1), x3, y1, xs2)
   if2(true_renamed, x4, y2, xs3) -> rm(x4, xs3)
   eq(0, 0) -> true_renamed
   eq(0, s(y3)) -> false_renamed
   eq(s(x5), 0) -> false_renamed
   eq(s(x6), s(y4)) -> eq(x6, y4)
   if2(false_renamed, x7, y5, xs4) -> cons(y5, rm(x7, xs4))
   rm(x8, nil) -> nil
   le(0, y6) -> true_renamed
   le(s(x9), 0) -> false_renamed
   le(s(x10), s(y7)) -> le(x10, y7)
   min(nil) -> 0
   equal_bool(true, false) -> false
   equal_bool(false, true) -> false
   equal_bool(true, true) -> true
   equal_bool(false, false) -> true
   and(true, x) -> x
   and(false, x) -> false
   or(true, x) -> true
   or(false, x) -> x
   not(false) -> true
   not(true) -> false
   isa_true(true) -> true
   isa_true(false) -> false
   isa_false(true) -> false
   isa_false(false) -> true
   equal_sort[a0](0, 0) -> true
   equal_sort[a0](0, s(v26)) -> false
   equal_sort[a0](s(v27), 0) -> false
   equal_sort[a0](s(v27), s(v28)) -> equal_sort[a0](v27, v28)
   equal_sort[a35](cons(v29, v30), cons(v31, v32)) -> and(equal_sort[a0](v29, v31), equal_sort[a35](v30, v32))
   equal_sort[a35](cons(v29, v30), nil) -> false
   equal_sort[a35](nil, cons(v33, v34)) -> false
   equal_sort[a35](nil, nil) -> true
   equal_sort[a43](true_renamed, true_renamed) -> true
   equal_sort[a43](true_renamed, false_renamed) -> false
   equal_sort[a43](false_renamed, true_renamed) -> false
   equal_sort[a43](false_renamed, false_renamed) -> true
   equal_sort[a61](witness_sort[a61], witness_sort[a61]) -> true

Q is empty.

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

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

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

   rm'(x3, cons(y1, xs2)) -> if2'(eq(x3, y1), x3, y1, xs2)
   if2'(true_renamed, x4, y2, xs3) -> true
   if2'(false_renamed, x7, y5, xs4) -> rm'(x7, xs4)
   rm'(x8, nil) -> false
   min(cons(x', nil)) -> x'
   min(cons(x'', cons(y, xs'))) -> if1(le(x'', y), x'', y, xs')
   if1(true_renamed, x1, y', xs'') -> min(cons(x1, xs''))
   if1(false_renamed, x2, y'', xs1) -> min(cons(y'', xs1))
   rm(x3, cons(y1, xs2)) -> if2(eq(x3, y1), x3, y1, xs2)
   if2(true_renamed, x4, y2, xs3) -> rm(x4, xs3)
   eq(0, 0) -> true_renamed
   eq(0, s(y3)) -> false_renamed
   eq(s(x5), 0) -> false_renamed
   eq(s(x6), s(y4)) -> eq(x6, y4)
   if2(false_renamed, x7, y5, xs4) -> cons(y5, rm(x7, xs4))
   rm(x8, nil) -> nil
   le(0, y6) -> true_renamed
   le(s(x9), 0) -> false_renamed
   le(s(x10), s(y7)) -> le(x10, y7)
   min(nil) -> 0
   equal_bool(true, false) -> false
   equal_bool(false, true) -> false
   equal_bool(true, true) -> true
   equal_bool(false, false) -> true
   and(true, x) -> x
   and(false, x) -> false
   or(true, x) -> true
   or(false, x) -> x
   not(false) -> true
   not(true) -> false
   isa_true(true) -> true
   isa_true(false) -> false
   isa_false(true) -> false
   isa_false(false) -> true
   equal_sort[a0](0, 0) -> true
   equal_sort[a0](0, s(v26)) -> false
   equal_sort[a0](s(v27), 0) -> false
   equal_sort[a0](s(v27), s(v28)) -> equal_sort[a0](v27, v28)
   equal_sort[a35](cons(v29, v30), cons(v31, v32)) -> and(equal_sort[a0](v29, v31), equal_sort[a35](v30, v32))
   equal_sort[a35](cons(v29, v30), nil) -> false
   equal_sort[a35](nil, cons(v33, v34)) -> false
   equal_sort[a35](nil, nil) -> true
   equal_sort[a43](true_renamed, true_renamed) -> true
   equal_sort[a43](true_renamed, false_renamed) -> false
   equal_sort[a43](false_renamed, true_renamed) -> false
   equal_sort[a43](false_renamed, false_renamed) -> true
   equal_sort[a61](witness_sort[a61], witness_sort[a61]) -> true

The set Q consists of the following terms:

   rm'(x0, cons(x1, x2))
   if2'(true_renamed, x0, x1, x2)
   if2'(false_renamed, x0, x1, x2)
   rm'(x0, nil)
   min(cons(x0, nil))
   min(cons(x0, cons(x1, x2)))
   if1(true_renamed, x0, x1, x2)
   if1(false_renamed, x0, x1, x2)
   rm(x0, cons(x1, x2))
   if2(true_renamed, x0, x1, x2)
   eq(0, 0)
   eq(0, s(x0))
   eq(s(x0), 0)
   eq(s(x0), s(x1))
   if2(false_renamed, x0, x1, x2)
   rm(x0, nil)
   le(0, x0)
   le(s(x0), 0)
   le(s(x0), s(x1))
   min(nil)
   equal_bool(true, false)
   equal_bool(false, true)
   equal_bool(true, true)
   equal_bool(false, false)
   and(true, x0)
   and(false, x0)
   or(true, x0)
   or(false, x0)
   not(false)
   not(true)
   isa_true(true)
   isa_true(false)
   isa_false(true)
   isa_false(false)
   equal_sort[a0](0, 0)
   equal_sort[a0](0, s(x0))
   equal_sort[a0](s(x0), 0)
   equal_sort[a0](s(x0), s(x1))
   equal_sort[a35](cons(x0, x1), cons(x2, x3))
   equal_sort[a35](cons(x0, x1), nil)
   equal_sort[a35](nil, cons(x0, x1))
   equal_sort[a35](nil, nil)
   equal_sort[a43](true_renamed, true_renamed)
   equal_sort[a43](true_renamed, false_renamed)
   equal_sort[a43](false_renamed, true_renamed)
   equal_sort[a43](false_renamed, false_renamed)
   equal_sort[a61](witness_sort[a61], witness_sort[a61])


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

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

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

   RM'(x3, cons(y1, xs2)) -> IF2'(eq(x3, y1), x3, y1, xs2)
   RM'(x3, cons(y1, xs2)) -> EQ(x3, y1)
   IF2'(false_renamed, x7, y5, xs4) -> RM'(x7, xs4)
   MIN(cons(x'', cons(y, xs'))) -> IF1(le(x'', y), x'', y, xs')
   MIN(cons(x'', cons(y, xs'))) -> LE(x'', y)
   IF1(true_renamed, x1, y', xs'') -> MIN(cons(x1, xs''))
   IF1(false_renamed, x2, y'', xs1) -> MIN(cons(y'', xs1))
   RM(x3, cons(y1, xs2)) -> IF2(eq(x3, y1), x3, y1, xs2)
   RM(x3, cons(y1, xs2)) -> EQ(x3, y1)
   IF2(true_renamed, x4, y2, xs3) -> RM(x4, xs3)
   EQ(s(x6), s(y4)) -> EQ(x6, y4)
   IF2(false_renamed, x7, y5, xs4) -> RM(x7, xs4)
   LE(s(x10), s(y7)) -> LE(x10, y7)
   EQUAL_SORT[A0](s(v27), s(v28)) -> EQUAL_SORT[A0](v27, v28)
   EQUAL_SORT[A35](cons(v29, v30), cons(v31, v32)) -> AND(equal_sort[a0](v29, v31), equal_sort[a35](v30, v32))
   EQUAL_SORT[A35](cons(v29, v30), cons(v31, v32)) -> EQUAL_SORT[A0](v29, v31)
   EQUAL_SORT[A35](cons(v29, v30), cons(v31, v32)) -> EQUAL_SORT[A35](v30, v32)

The TRS R consists of the following rules:

   rm'(x3, cons(y1, xs2)) -> if2'(eq(x3, y1), x3, y1, xs2)
   if2'(true_renamed, x4, y2, xs3) -> true
   if2'(false_renamed, x7, y5, xs4) -> rm'(x7, xs4)
   rm'(x8, nil) -> false
   min(cons(x', nil)) -> x'
   min(cons(x'', cons(y, xs'))) -> if1(le(x'', y), x'', y, xs')
   if1(true_renamed, x1, y', xs'') -> min(cons(x1, xs''))
   if1(false_renamed, x2, y'', xs1) -> min(cons(y'', xs1))
   rm(x3, cons(y1, xs2)) -> if2(eq(x3, y1), x3, y1, xs2)
   if2(true_renamed, x4, y2, xs3) -> rm(x4, xs3)
   eq(0, 0) -> true_renamed
   eq(0, s(y3)) -> false_renamed
   eq(s(x5), 0) -> false_renamed
   eq(s(x6), s(y4)) -> eq(x6, y4)
   if2(false_renamed, x7, y5, xs4) -> cons(y5, rm(x7, xs4))
   rm(x8, nil) -> nil
   le(0, y6) -> true_renamed
   le(s(x9), 0) -> false_renamed
   le(s(x10), s(y7)) -> le(x10, y7)
   min(nil) -> 0
   equal_bool(true, false) -> false
   equal_bool(false, true) -> false
   equal_bool(true, true) -> true
   equal_bool(false, false) -> true
   and(true, x) -> x
   and(false, x) -> false
   or(true, x) -> true
   or(false, x) -> x
   not(false) -> true
   not(true) -> false
   isa_true(true) -> true
   isa_true(false) -> false
   isa_false(true) -> false
   isa_false(false) -> true
   equal_sort[a0](0, 0) -> true
   equal_sort[a0](0, s(v26)) -> false
   equal_sort[a0](s(v27), 0) -> false
   equal_sort[a0](s(v27), s(v28)) -> equal_sort[a0](v27, v28)
   equal_sort[a35](cons(v29, v30), cons(v31, v32)) -> and(equal_sort[a0](v29, v31), equal_sort[a35](v30, v32))
   equal_sort[a35](cons(v29, v30), nil) -> false
   equal_sort[a35](nil, cons(v33, v34)) -> false
   equal_sort[a35](nil, nil) -> true
   equal_sort[a43](true_renamed, true_renamed) -> true
   equal_sort[a43](true_renamed, false_renamed) -> false
   equal_sort[a43](false_renamed, true_renamed) -> false
   equal_sort[a43](false_renamed, false_renamed) -> true
   equal_sort[a61](witness_sort[a61], witness_sort[a61]) -> true

The set Q consists of the following terms:

   rm'(x0, cons(x1, x2))
   if2'(true_renamed, x0, x1, x2)
   if2'(false_renamed, x0, x1, x2)
   rm'(x0, nil)
   min(cons(x0, nil))
   min(cons(x0, cons(x1, x2)))
   if1(true_renamed, x0, x1, x2)
   if1(false_renamed, x0, x1, x2)
   rm(x0, cons(x1, x2))
   if2(true_renamed, x0, x1, x2)
   eq(0, 0)
   eq(0, s(x0))
   eq(s(x0), 0)
   eq(s(x0), s(x1))
   if2(false_renamed, x0, x1, x2)
   rm(x0, nil)
   le(0, x0)
   le(s(x0), 0)
   le(s(x0), s(x1))
   min(nil)
   equal_bool(true, false)
   equal_bool(false, true)
   equal_bool(true, true)
   equal_bool(false, false)
   and(true, x0)
   and(false, x0)
   or(true, x0)
   or(false, x0)
   not(false)
   not(true)
   isa_true(true)
   isa_true(false)
   isa_false(true)
   isa_false(false)
   equal_sort[a0](0, 0)
   equal_sort[a0](0, s(x0))
   equal_sort[a0](s(x0), 0)
   equal_sort[a0](s(x0), s(x1))
   equal_sort[a35](cons(x0, x1), cons(x2, x3))
   equal_sort[a35](cons(x0, x1), nil)
   equal_sort[a35](nil, cons(x0, x1))
   equal_sort[a35](nil, nil)
   equal_sort[a43](true_renamed, true_renamed)
   equal_sort[a43](true_renamed, false_renamed)
   equal_sort[a43](false_renamed, true_renamed)
   equal_sort[a43](false_renamed, false_renamed)
   equal_sort[a61](witness_sort[a61], witness_sort[a61])

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

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

(53)
Complex Obligation (AND)

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

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

   EQUAL_SORT[A0](s(v27), s(v28)) -> EQUAL_SORT[A0](v27, v28)

The TRS R consists of the following rules:

   rm'(x3, cons(y1, xs2)) -> if2'(eq(x3, y1), x3, y1, xs2)
   if2'(true_renamed, x4, y2, xs3) -> true
   if2'(false_renamed, x7, y5, xs4) -> rm'(x7, xs4)
   rm'(x8, nil) -> false
   min(cons(x', nil)) -> x'
   min(cons(x'', cons(y, xs'))) -> if1(le(x'', y), x'', y, xs')
   if1(true_renamed, x1, y', xs'') -> min(cons(x1, xs''))
   if1(false_renamed, x2, y'', xs1) -> min(cons(y'', xs1))
   rm(x3, cons(y1, xs2)) -> if2(eq(x3, y1), x3, y1, xs2)
   if2(true_renamed, x4, y2, xs3) -> rm(x4, xs3)
   eq(0, 0) -> true_renamed
   eq(0, s(y3)) -> false_renamed
   eq(s(x5), 0) -> false_renamed
   eq(s(x6), s(y4)) -> eq(x6, y4)
   if2(false_renamed, x7, y5, xs4) -> cons(y5, rm(x7, xs4))
   rm(x8, nil) -> nil
   le(0, y6) -> true_renamed
   le(s(x9), 0) -> false_renamed
   le(s(x10), s(y7)) -> le(x10, y7)
   min(nil) -> 0
   equal_bool(true, false) -> false
   equal_bool(false, true) -> false
   equal_bool(true, true) -> true
   equal_bool(false, false) -> true
   and(true, x) -> x
   and(false, x) -> false
   or(true, x) -> true
   or(false, x) -> x
   not(false) -> true
   not(true) -> false
   isa_true(true) -> true
   isa_true(false) -> false
   isa_false(true) -> false
   isa_false(false) -> true
   equal_sort[a0](0, 0) -> true
   equal_sort[a0](0, s(v26)) -> false
   equal_sort[a0](s(v27), 0) -> false
   equal_sort[a0](s(v27), s(v28)) -> equal_sort[a0](v27, v28)
   equal_sort[a35](cons(v29, v30), cons(v31, v32)) -> and(equal_sort[a0](v29, v31), equal_sort[a35](v30, v32))
   equal_sort[a35](cons(v29, v30), nil) -> false
   equal_sort[a35](nil, cons(v33, v34)) -> false
   equal_sort[a35](nil, nil) -> true
   equal_sort[a43](true_renamed, true_renamed) -> true
   equal_sort[a43](true_renamed, false_renamed) -> false
   equal_sort[a43](false_renamed, true_renamed) -> false
   equal_sort[a43](false_renamed, false_renamed) -> true
   equal_sort[a61](witness_sort[a61], witness_sort[a61]) -> true

The set Q consists of the following terms:

   rm'(x0, cons(x1, x2))
   if2'(true_renamed, x0, x1, x2)
   if2'(false_renamed, x0, x1, x2)
   rm'(x0, nil)
   min(cons(x0, nil))
   min(cons(x0, cons(x1, x2)))
   if1(true_renamed, x0, x1, x2)
   if1(false_renamed, x0, x1, x2)
   rm(x0, cons(x1, x2))
   if2(true_renamed, x0, x1, x2)
   eq(0, 0)
   eq(0, s(x0))
   eq(s(x0), 0)
   eq(s(x0), s(x1))
   if2(false_renamed, x0, x1, x2)
   rm(x0, nil)
   le(0, x0)
   le(s(x0), 0)
   le(s(x0), s(x1))
   min(nil)
   equal_bool(true, false)
   equal_bool(false, true)
   equal_bool(true, true)
   equal_bool(false, false)
   and(true, x0)
   and(false, x0)
   or(true, x0)
   or(false, x0)
   not(false)
   not(true)
   isa_true(true)
   isa_true(false)
   isa_false(true)
   isa_false(false)
   equal_sort[a0](0, 0)
   equal_sort[a0](0, s(x0))
   equal_sort[a0](s(x0), 0)
   equal_sort[a0](s(x0), s(x1))
   equal_sort[a35](cons(x0, x1), cons(x2, x3))
   equal_sort[a35](cons(x0, x1), nil)
   equal_sort[a35](nil, cons(x0, x1))
   equal_sort[a35](nil, nil)
   equal_sort[a43](true_renamed, true_renamed)
   equal_sort[a43](true_renamed, false_renamed)
   equal_sort[a43](false_renamed, true_renamed)
   equal_sort[a43](false_renamed, false_renamed)
   equal_sort[a61](witness_sort[a61], witness_sort[a61])

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

(55) 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.
----------------------------------------

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

   EQUAL_SORT[A0](s(v27), s(v28)) -> EQUAL_SORT[A0](v27, v28)

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

   rm'(x0, cons(x1, x2))
   if2'(true_renamed, x0, x1, x2)
   if2'(false_renamed, x0, x1, x2)
   rm'(x0, nil)
   min(cons(x0, nil))
   min(cons(x0, cons(x1, x2)))
   if1(true_renamed, x0, x1, x2)
   if1(false_renamed, x0, x1, x2)
   rm(x0, cons(x1, x2))
   if2(true_renamed, x0, x1, x2)
   eq(0, 0)
   eq(0, s(x0))
   eq(s(x0), 0)
   eq(s(x0), s(x1))
   if2(false_renamed, x0, x1, x2)
   rm(x0, nil)
   le(0, x0)
   le(s(x0), 0)
   le(s(x0), s(x1))
   min(nil)
   equal_bool(true, false)
   equal_bool(false, true)
   equal_bool(true, true)
   equal_bool(false, false)
   and(true, x0)
   and(false, x0)
   or(true, x0)
   or(false, x0)
   not(false)
   not(true)
   isa_true(true)
   isa_true(false)
   isa_false(true)
   isa_false(false)
   equal_sort[a0](0, 0)
   equal_sort[a0](0, s(x0))
   equal_sort[a0](s(x0), 0)
   equal_sort[a0](s(x0), s(x1))
   equal_sort[a35](cons(x0, x1), cons(x2, x3))
   equal_sort[a35](cons(x0, x1), nil)
   equal_sort[a35](nil, cons(x0, x1))
   equal_sort[a35](nil, nil)
   equal_sort[a43](true_renamed, true_renamed)
   equal_sort[a43](true_renamed, false_renamed)
   equal_sort[a43](false_renamed, true_renamed)
   equal_sort[a43](false_renamed, false_renamed)
   equal_sort[a61](witness_sort[a61], witness_sort[a61])

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

(57) 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].

   rm'(x0, cons(x1, x2))
   if2'(true_renamed, x0, x1, x2)
   if2'(false_renamed, x0, x1, x2)
   rm'(x0, nil)
   min(cons(x0, nil))
   min(cons(x0, cons(x1, x2)))
   if1(true_renamed, x0, x1, x2)
   if1(false_renamed, x0, x1, x2)
   rm(x0, cons(x1, x2))
   if2(true_renamed, x0, x1, x2)
   eq(0, 0)
   eq(0, s(x0))
   eq(s(x0), 0)
   eq(s(x0), s(x1))
   if2(false_renamed, x0, x1, x2)
   rm(x0, nil)
   le(0, x0)
   le(s(x0), 0)
   le(s(x0), s(x1))
   min(nil)
   equal_bool(true, false)
   equal_bool(false, true)
   equal_bool(true, true)
   equal_bool(false, false)
   and(true, x0)
   and(false, x0)
   or(true, x0)
   or(false, x0)
   not(false)
   not(true)
   isa_true(true)
   isa_true(false)
   isa_false(true)
   isa_false(false)
   equal_sort[a0](0, 0)
   equal_sort[a0](0, s(x0))
   equal_sort[a0](s(x0), 0)
   equal_sort[a0](s(x0), s(x1))
   equal_sort[a35](cons(x0, x1), cons(x2, x3))
   equal_sort[a35](cons(x0, x1), nil)
   equal_sort[a35](nil, cons(x0, x1))
   equal_sort[a35](nil, nil)
   equal_sort[a43](true_renamed, true_renamed)
   equal_sort[a43](true_renamed, false_renamed)
   equal_sort[a43](false_renamed, true_renamed)
   equal_sort[a43](false_renamed, false_renamed)
   equal_sort[a61](witness_sort[a61], witness_sort[a61])


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

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

   EQUAL_SORT[A0](s(v27), s(v28)) -> EQUAL_SORT[A0](v27, v28)

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

(59) 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_SORT[A0](s(v27), s(v28)) -> EQUAL_SORT[A0](v27, v28)
The graph contains the following edges 1 > 1, 2 > 2


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

(60)
YES

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

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

   EQUAL_SORT[A35](cons(v29, v30), cons(v31, v32)) -> EQUAL_SORT[A35](v30, v32)

The TRS R consists of the following rules:

   rm'(x3, cons(y1, xs2)) -> if2'(eq(x3, y1), x3, y1, xs2)
   if2'(true_renamed, x4, y2, xs3) -> true
   if2'(false_renamed, x7, y5, xs4) -> rm'(x7, xs4)
   rm'(x8, nil) -> false
   min(cons(x', nil)) -> x'
   min(cons(x'', cons(y, xs'))) -> if1(le(x'', y), x'', y, xs')
   if1(true_renamed, x1, y', xs'') -> min(cons(x1, xs''))
   if1(false_renamed, x2, y'', xs1) -> min(cons(y'', xs1))
   rm(x3, cons(y1, xs2)) -> if2(eq(x3, y1), x3, y1, xs2)
   if2(true_renamed, x4, y2, xs3) -> rm(x4, xs3)
   eq(0, 0) -> true_renamed
   eq(0, s(y3)) -> false_renamed
   eq(s(x5), 0) -> false_renamed
   eq(s(x6), s(y4)) -> eq(x6, y4)
   if2(false_renamed, x7, y5, xs4) -> cons(y5, rm(x7, xs4))
   rm(x8, nil) -> nil
   le(0, y6) -> true_renamed
   le(s(x9), 0) -> false_renamed
   le(s(x10), s(y7)) -> le(x10, y7)
   min(nil) -> 0
   equal_bool(true, false) -> false
   equal_bool(false, true) -> false
   equal_bool(true, true) -> true
   equal_bool(false, false) -> true
   and(true, x) -> x
   and(false, x) -> false
   or(true, x) -> true
   or(false, x) -> x
   not(false) -> true
   not(true) -> false
   isa_true(true) -> true
   isa_true(false) -> false
   isa_false(true) -> false
   isa_false(false) -> true
   equal_sort[a0](0, 0) -> true
   equal_sort[a0](0, s(v26)) -> false
   equal_sort[a0](s(v27), 0) -> false
   equal_sort[a0](s(v27), s(v28)) -> equal_sort[a0](v27, v28)
   equal_sort[a35](cons(v29, v30), cons(v31, v32)) -> and(equal_sort[a0](v29, v31), equal_sort[a35](v30, v32))
   equal_sort[a35](cons(v29, v30), nil) -> false
   equal_sort[a35](nil, cons(v33, v34)) -> false
   equal_sort[a35](nil, nil) -> true
   equal_sort[a43](true_renamed, true_renamed) -> true
   equal_sort[a43](true_renamed, false_renamed) -> false
   equal_sort[a43](false_renamed, true_renamed) -> false
   equal_sort[a43](false_renamed, false_renamed) -> true
   equal_sort[a61](witness_sort[a61], witness_sort[a61]) -> true

The set Q consists of the following terms:

   rm'(x0, cons(x1, x2))
   if2'(true_renamed, x0, x1, x2)
   if2'(false_renamed, x0, x1, x2)
   rm'(x0, nil)
   min(cons(x0, nil))
   min(cons(x0, cons(x1, x2)))
   if1(true_renamed, x0, x1, x2)
   if1(false_renamed, x0, x1, x2)
   rm(x0, cons(x1, x2))
   if2(true_renamed, x0, x1, x2)
   eq(0, 0)
   eq(0, s(x0))
   eq(s(x0), 0)
   eq(s(x0), s(x1))
   if2(false_renamed, x0, x1, x2)
   rm(x0, nil)
   le(0, x0)
   le(s(x0), 0)
   le(s(x0), s(x1))
   min(nil)
   equal_bool(true, false)
   equal_bool(false, true)
   equal_bool(true, true)
   equal_bool(false, false)
   and(true, x0)
   and(false, x0)
   or(true, x0)
   or(false, x0)
   not(false)
   not(true)
   isa_true(true)
   isa_true(false)
   isa_false(true)
   isa_false(false)
   equal_sort[a0](0, 0)
   equal_sort[a0](0, s(x0))
   equal_sort[a0](s(x0), 0)
   equal_sort[a0](s(x0), s(x1))
   equal_sort[a35](cons(x0, x1), cons(x2, x3))
   equal_sort[a35](cons(x0, x1), nil)
   equal_sort[a35](nil, cons(x0, x1))
   equal_sort[a35](nil, nil)
   equal_sort[a43](true_renamed, true_renamed)
   equal_sort[a43](true_renamed, false_renamed)
   equal_sort[a43](false_renamed, true_renamed)
   equal_sort[a43](false_renamed, false_renamed)
   equal_sort[a61](witness_sort[a61], witness_sort[a61])

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

(62) 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.
----------------------------------------

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

   EQUAL_SORT[A35](cons(v29, v30), cons(v31, v32)) -> EQUAL_SORT[A35](v30, v32)

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

   rm'(x0, cons(x1, x2))
   if2'(true_renamed, x0, x1, x2)
   if2'(false_renamed, x0, x1, x2)
   rm'(x0, nil)
   min(cons(x0, nil))
   min(cons(x0, cons(x1, x2)))
   if1(true_renamed, x0, x1, x2)
   if1(false_renamed, x0, x1, x2)
   rm(x0, cons(x1, x2))
   if2(true_renamed, x0, x1, x2)
   eq(0, 0)
   eq(0, s(x0))
   eq(s(x0), 0)
   eq(s(x0), s(x1))
   if2(false_renamed, x0, x1, x2)
   rm(x0, nil)
   le(0, x0)
   le(s(x0), 0)
   le(s(x0), s(x1))
   min(nil)
   equal_bool(true, false)
   equal_bool(false, true)
   equal_bool(true, true)
   equal_bool(false, false)
   and(true, x0)
   and(false, x0)
   or(true, x0)
   or(false, x0)
   not(false)
   not(true)
   isa_true(true)
   isa_true(false)
   isa_false(true)
   isa_false(false)
   equal_sort[a0](0, 0)
   equal_sort[a0](0, s(x0))
   equal_sort[a0](s(x0), 0)
   equal_sort[a0](s(x0), s(x1))
   equal_sort[a35](cons(x0, x1), cons(x2, x3))
   equal_sort[a35](cons(x0, x1), nil)
   equal_sort[a35](nil, cons(x0, x1))
   equal_sort[a35](nil, nil)
   equal_sort[a43](true_renamed, true_renamed)
   equal_sort[a43](true_renamed, false_renamed)
   equal_sort[a43](false_renamed, true_renamed)
   equal_sort[a43](false_renamed, false_renamed)
   equal_sort[a61](witness_sort[a61], witness_sort[a61])

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

(64) 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].

   rm'(x0, cons(x1, x2))
   if2'(true_renamed, x0, x1, x2)
   if2'(false_renamed, x0, x1, x2)
   rm'(x0, nil)
   min(cons(x0, nil))
   min(cons(x0, cons(x1, x2)))
   if1(true_renamed, x0, x1, x2)
   if1(false_renamed, x0, x1, x2)
   rm(x0, cons(x1, x2))
   if2(true_renamed, x0, x1, x2)
   eq(0, 0)
   eq(0, s(x0))
   eq(s(x0), 0)
   eq(s(x0), s(x1))
   if2(false_renamed, x0, x1, x2)
   rm(x0, nil)
   le(0, x0)
   le(s(x0), 0)
   le(s(x0), s(x1))
   min(nil)
   equal_bool(true, false)
   equal_bool(false, true)
   equal_bool(true, true)
   equal_bool(false, false)
   and(true, x0)
   and(false, x0)
   or(true, x0)
   or(false, x0)
   not(false)
   not(true)
   isa_true(true)
   isa_true(false)
   isa_false(true)
   isa_false(false)
   equal_sort[a0](0, 0)
   equal_sort[a0](0, s(x0))
   equal_sort[a0](s(x0), 0)
   equal_sort[a0](s(x0), s(x1))
   equal_sort[a35](cons(x0, x1), cons(x2, x3))
   equal_sort[a35](cons(x0, x1), nil)
   equal_sort[a35](nil, cons(x0, x1))
   equal_sort[a35](nil, nil)
   equal_sort[a43](true_renamed, true_renamed)
   equal_sort[a43](true_renamed, false_renamed)
   equal_sort[a43](false_renamed, true_renamed)
   equal_sort[a43](false_renamed, false_renamed)
   equal_sort[a61](witness_sort[a61], witness_sort[a61])


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

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

   EQUAL_SORT[A35](cons(v29, v30), cons(v31, v32)) -> EQUAL_SORT[A35](v30, v32)

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

(66) 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_SORT[A35](cons(v29, v30), cons(v31, v32)) -> EQUAL_SORT[A35](v30, v32)
The graph contains the following edges 1 > 1, 2 > 2


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

(67)
YES

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

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

   LE(s(x10), s(y7)) -> LE(x10, y7)

The TRS R consists of the following rules:

   rm'(x3, cons(y1, xs2)) -> if2'(eq(x3, y1), x3, y1, xs2)
   if2'(true_renamed, x4, y2, xs3) -> true
   if2'(false_renamed, x7, y5, xs4) -> rm'(x7, xs4)
   rm'(x8, nil) -> false
   min(cons(x', nil)) -> x'
   min(cons(x'', cons(y, xs'))) -> if1(le(x'', y), x'', y, xs')
   if1(true_renamed, x1, y', xs'') -> min(cons(x1, xs''))
   if1(false_renamed, x2, y'', xs1) -> min(cons(y'', xs1))
   rm(x3, cons(y1, xs2)) -> if2(eq(x3, y1), x3, y1, xs2)
   if2(true_renamed, x4, y2, xs3) -> rm(x4, xs3)
   eq(0, 0) -> true_renamed
   eq(0, s(y3)) -> false_renamed
   eq(s(x5), 0) -> false_renamed
   eq(s(x6), s(y4)) -> eq(x6, y4)
   if2(false_renamed, x7, y5, xs4) -> cons(y5, rm(x7, xs4))
   rm(x8, nil) -> nil
   le(0, y6) -> true_renamed
   le(s(x9), 0) -> false_renamed
   le(s(x10), s(y7)) -> le(x10, y7)
   min(nil) -> 0
   equal_bool(true, false) -> false
   equal_bool(false, true) -> false
   equal_bool(true, true) -> true
   equal_bool(false, false) -> true
   and(true, x) -> x
   and(false, x) -> false
   or(true, x) -> true
   or(false, x) -> x
   not(false) -> true
   not(true) -> false
   isa_true(true) -> true
   isa_true(false) -> false
   isa_false(true) -> false
   isa_false(false) -> true
   equal_sort[a0](0, 0) -> true
   equal_sort[a0](0, s(v26)) -> false
   equal_sort[a0](s(v27), 0) -> false
   equal_sort[a0](s(v27), s(v28)) -> equal_sort[a0](v27, v28)
   equal_sort[a35](cons(v29, v30), cons(v31, v32)) -> and(equal_sort[a0](v29, v31), equal_sort[a35](v30, v32))
   equal_sort[a35](cons(v29, v30), nil) -> false
   equal_sort[a35](nil, cons(v33, v34)) -> false
   equal_sort[a35](nil, nil) -> true
   equal_sort[a43](true_renamed, true_renamed) -> true
   equal_sort[a43](true_renamed, false_renamed) -> false
   equal_sort[a43](false_renamed, true_renamed) -> false
   equal_sort[a43](false_renamed, false_renamed) -> true
   equal_sort[a61](witness_sort[a61], witness_sort[a61]) -> true

The set Q consists of the following terms:

   rm'(x0, cons(x1, x2))
   if2'(true_renamed, x0, x1, x2)
   if2'(false_renamed, x0, x1, x2)
   rm'(x0, nil)
   min(cons(x0, nil))
   min(cons(x0, cons(x1, x2)))
   if1(true_renamed, x0, x1, x2)
   if1(false_renamed, x0, x1, x2)
   rm(x0, cons(x1, x2))
   if2(true_renamed, x0, x1, x2)
   eq(0, 0)
   eq(0, s(x0))
   eq(s(x0), 0)
   eq(s(x0), s(x1))
   if2(false_renamed, x0, x1, x2)
   rm(x0, nil)
   le(0, x0)
   le(s(x0), 0)
   le(s(x0), s(x1))
   min(nil)
   equal_bool(true, false)
   equal_bool(false, true)
   equal_bool(true, true)
   equal_bool(false, false)
   and(true, x0)
   and(false, x0)
   or(true, x0)
   or(false, x0)
   not(false)
   not(true)
   isa_true(true)
   isa_true(false)
   isa_false(true)
   isa_false(false)
   equal_sort[a0](0, 0)
   equal_sort[a0](0, s(x0))
   equal_sort[a0](s(x0), 0)
   equal_sort[a0](s(x0), s(x1))
   equal_sort[a35](cons(x0, x1), cons(x2, x3))
   equal_sort[a35](cons(x0, x1), nil)
   equal_sort[a35](nil, cons(x0, x1))
   equal_sort[a35](nil, nil)
   equal_sort[a43](true_renamed, true_renamed)
   equal_sort[a43](true_renamed, false_renamed)
   equal_sort[a43](false_renamed, true_renamed)
   equal_sort[a43](false_renamed, false_renamed)
   equal_sort[a61](witness_sort[a61], witness_sort[a61])

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

(69) 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.
----------------------------------------

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

   LE(s(x10), s(y7)) -> LE(x10, y7)

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

   rm'(x0, cons(x1, x2))
   if2'(true_renamed, x0, x1, x2)
   if2'(false_renamed, x0, x1, x2)
   rm'(x0, nil)
   min(cons(x0, nil))
   min(cons(x0, cons(x1, x2)))
   if1(true_renamed, x0, x1, x2)
   if1(false_renamed, x0, x1, x2)
   rm(x0, cons(x1, x2))
   if2(true_renamed, x0, x1, x2)
   eq(0, 0)
   eq(0, s(x0))
   eq(s(x0), 0)
   eq(s(x0), s(x1))
   if2(false_renamed, x0, x1, x2)
   rm(x0, nil)
   le(0, x0)
   le(s(x0), 0)
   le(s(x0), s(x1))
   min(nil)
   equal_bool(true, false)
   equal_bool(false, true)
   equal_bool(true, true)
   equal_bool(false, false)
   and(true, x0)
   and(false, x0)
   or(true, x0)
   or(false, x0)
   not(false)
   not(true)
   isa_true(true)
   isa_true(false)
   isa_false(true)
   isa_false(false)
   equal_sort[a0](0, 0)
   equal_sort[a0](0, s(x0))
   equal_sort[a0](s(x0), 0)
   equal_sort[a0](s(x0), s(x1))
   equal_sort[a35](cons(x0, x1), cons(x2, x3))
   equal_sort[a35](cons(x0, x1), nil)
   equal_sort[a35](nil, cons(x0, x1))
   equal_sort[a35](nil, nil)
   equal_sort[a43](true_renamed, true_renamed)
   equal_sort[a43](true_renamed, false_renamed)
   equal_sort[a43](false_renamed, true_renamed)
   equal_sort[a43](false_renamed, false_renamed)
   equal_sort[a61](witness_sort[a61], witness_sort[a61])

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

(71) 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].

   rm'(x0, cons(x1, x2))
   if2'(true_renamed, x0, x1, x2)
   if2'(false_renamed, x0, x1, x2)
   rm'(x0, nil)
   min(cons(x0, nil))
   min(cons(x0, cons(x1, x2)))
   if1(true_renamed, x0, x1, x2)
   if1(false_renamed, x0, x1, x2)
   rm(x0, cons(x1, x2))
   if2(true_renamed, x0, x1, x2)
   eq(0, 0)
   eq(0, s(x0))
   eq(s(x0), 0)
   eq(s(x0), s(x1))
   if2(false_renamed, x0, x1, x2)
   rm(x0, nil)
   le(0, x0)
   le(s(x0), 0)
   le(s(x0), s(x1))
   min(nil)
   equal_bool(true, false)
   equal_bool(false, true)
   equal_bool(true, true)
   equal_bool(false, false)
   and(true, x0)
   and(false, x0)
   or(true, x0)
   or(false, x0)
   not(false)
   not(true)
   isa_true(true)
   isa_true(false)
   isa_false(true)
   isa_false(false)
   equal_sort[a0](0, 0)
   equal_sort[a0](0, s(x0))
   equal_sort[a0](s(x0), 0)
   equal_sort[a0](s(x0), s(x1))
   equal_sort[a35](cons(x0, x1), cons(x2, x3))
   equal_sort[a35](cons(x0, x1), nil)
   equal_sort[a35](nil, cons(x0, x1))
   equal_sort[a35](nil, nil)
   equal_sort[a43](true_renamed, true_renamed)
   equal_sort[a43](true_renamed, false_renamed)
   equal_sort[a43](false_renamed, true_renamed)
   equal_sort[a43](false_renamed, false_renamed)
   equal_sort[a61](witness_sort[a61], witness_sort[a61])


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

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

   LE(s(x10), s(y7)) -> LE(x10, y7)

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

(73) 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:
*LE(s(x10), s(y7)) -> LE(x10, y7)
The graph contains the following edges 1 > 1, 2 > 2


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

(74)
YES

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

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

   EQ(s(x6), s(y4)) -> EQ(x6, y4)

The TRS R consists of the following rules:

   rm'(x3, cons(y1, xs2)) -> if2'(eq(x3, y1), x3, y1, xs2)
   if2'(true_renamed, x4, y2, xs3) -> true
   if2'(false_renamed, x7, y5, xs4) -> rm'(x7, xs4)
   rm'(x8, nil) -> false
   min(cons(x', nil)) -> x'
   min(cons(x'', cons(y, xs'))) -> if1(le(x'', y), x'', y, xs')
   if1(true_renamed, x1, y', xs'') -> min(cons(x1, xs''))
   if1(false_renamed, x2, y'', xs1) -> min(cons(y'', xs1))
   rm(x3, cons(y1, xs2)) -> if2(eq(x3, y1), x3, y1, xs2)
   if2(true_renamed, x4, y2, xs3) -> rm(x4, xs3)
   eq(0, 0) -> true_renamed
   eq(0, s(y3)) -> false_renamed
   eq(s(x5), 0) -> false_renamed
   eq(s(x6), s(y4)) -> eq(x6, y4)
   if2(false_renamed, x7, y5, xs4) -> cons(y5, rm(x7, xs4))
   rm(x8, nil) -> nil
   le(0, y6) -> true_renamed
   le(s(x9), 0) -> false_renamed
   le(s(x10), s(y7)) -> le(x10, y7)
   min(nil) -> 0
   equal_bool(true, false) -> false
   equal_bool(false, true) -> false
   equal_bool(true, true) -> true
   equal_bool(false, false) -> true
   and(true, x) -> x
   and(false, x) -> false
   or(true, x) -> true
   or(false, x) -> x
   not(false) -> true
   not(true) -> false
   isa_true(true) -> true
   isa_true(false) -> false
   isa_false(true) -> false
   isa_false(false) -> true
   equal_sort[a0](0, 0) -> true
   equal_sort[a0](0, s(v26)) -> false
   equal_sort[a0](s(v27), 0) -> false
   equal_sort[a0](s(v27), s(v28)) -> equal_sort[a0](v27, v28)
   equal_sort[a35](cons(v29, v30), cons(v31, v32)) -> and(equal_sort[a0](v29, v31), equal_sort[a35](v30, v32))
   equal_sort[a35](cons(v29, v30), nil) -> false
   equal_sort[a35](nil, cons(v33, v34)) -> false
   equal_sort[a35](nil, nil) -> true
   equal_sort[a43](true_renamed, true_renamed) -> true
   equal_sort[a43](true_renamed, false_renamed) -> false
   equal_sort[a43](false_renamed, true_renamed) -> false
   equal_sort[a43](false_renamed, false_renamed) -> true
   equal_sort[a61](witness_sort[a61], witness_sort[a61]) -> true

The set Q consists of the following terms:

   rm'(x0, cons(x1, x2))
   if2'(true_renamed, x0, x1, x2)
   if2'(false_renamed, x0, x1, x2)
   rm'(x0, nil)
   min(cons(x0, nil))
   min(cons(x0, cons(x1, x2)))
   if1(true_renamed, x0, x1, x2)
   if1(false_renamed, x0, x1, x2)
   rm(x0, cons(x1, x2))
   if2(true_renamed, x0, x1, x2)
   eq(0, 0)
   eq(0, s(x0))
   eq(s(x0), 0)
   eq(s(x0), s(x1))
   if2(false_renamed, x0, x1, x2)
   rm(x0, nil)
   le(0, x0)
   le(s(x0), 0)
   le(s(x0), s(x1))
   min(nil)
   equal_bool(true, false)
   equal_bool(false, true)
   equal_bool(true, true)
   equal_bool(false, false)
   and(true, x0)
   and(false, x0)
   or(true, x0)
   or(false, x0)
   not(false)
   not(true)
   isa_true(true)
   isa_true(false)
   isa_false(true)
   isa_false(false)
   equal_sort[a0](0, 0)
   equal_sort[a0](0, s(x0))
   equal_sort[a0](s(x0), 0)
   equal_sort[a0](s(x0), s(x1))
   equal_sort[a35](cons(x0, x1), cons(x2, x3))
   equal_sort[a35](cons(x0, x1), nil)
   equal_sort[a35](nil, cons(x0, x1))
   equal_sort[a35](nil, nil)
   equal_sort[a43](true_renamed, true_renamed)
   equal_sort[a43](true_renamed, false_renamed)
   equal_sort[a43](false_renamed, true_renamed)
   equal_sort[a43](false_renamed, false_renamed)
   equal_sort[a61](witness_sort[a61], witness_sort[a61])

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

(76) 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.
----------------------------------------

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

   EQ(s(x6), s(y4)) -> EQ(x6, y4)

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

   rm'(x0, cons(x1, x2))
   if2'(true_renamed, x0, x1, x2)
   if2'(false_renamed, x0, x1, x2)
   rm'(x0, nil)
   min(cons(x0, nil))
   min(cons(x0, cons(x1, x2)))
   if1(true_renamed, x0, x1, x2)
   if1(false_renamed, x0, x1, x2)
   rm(x0, cons(x1, x2))
   if2(true_renamed, x0, x1, x2)
   eq(0, 0)
   eq(0, s(x0))
   eq(s(x0), 0)
   eq(s(x0), s(x1))
   if2(false_renamed, x0, x1, x2)
   rm(x0, nil)
   le(0, x0)
   le(s(x0), 0)
   le(s(x0), s(x1))
   min(nil)
   equal_bool(true, false)
   equal_bool(false, true)
   equal_bool(true, true)
   equal_bool(false, false)
   and(true, x0)
   and(false, x0)
   or(true, x0)
   or(false, x0)
   not(false)
   not(true)
   isa_true(true)
   isa_true(false)
   isa_false(true)
   isa_false(false)
   equal_sort[a0](0, 0)
   equal_sort[a0](0, s(x0))
   equal_sort[a0](s(x0), 0)
   equal_sort[a0](s(x0), s(x1))
   equal_sort[a35](cons(x0, x1), cons(x2, x3))
   equal_sort[a35](cons(x0, x1), nil)
   equal_sort[a35](nil, cons(x0, x1))
   equal_sort[a35](nil, nil)
   equal_sort[a43](true_renamed, true_renamed)
   equal_sort[a43](true_renamed, false_renamed)
   equal_sort[a43](false_renamed, true_renamed)
   equal_sort[a43](false_renamed, false_renamed)
   equal_sort[a61](witness_sort[a61], witness_sort[a61])

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

(78) 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].

   rm'(x0, cons(x1, x2))
   if2'(true_renamed, x0, x1, x2)
   if2'(false_renamed, x0, x1, x2)
   rm'(x0, nil)
   min(cons(x0, nil))
   min(cons(x0, cons(x1, x2)))
   if1(true_renamed, x0, x1, x2)
   if1(false_renamed, x0, x1, x2)
   rm(x0, cons(x1, x2))
   if2(true_renamed, x0, x1, x2)
   eq(0, 0)
   eq(0, s(x0))
   eq(s(x0), 0)
   eq(s(x0), s(x1))
   if2(false_renamed, x0, x1, x2)
   rm(x0, nil)
   le(0, x0)
   le(s(x0), 0)
   le(s(x0), s(x1))
   min(nil)
   equal_bool(true, false)
   equal_bool(false, true)
   equal_bool(true, true)
   equal_bool(false, false)
   and(true, x0)
   and(false, x0)
   or(true, x0)
   or(false, x0)
   not(false)
   not(true)
   isa_true(true)
   isa_true(false)
   isa_false(true)
   isa_false(false)
   equal_sort[a0](0, 0)
   equal_sort[a0](0, s(x0))
   equal_sort[a0](s(x0), 0)
   equal_sort[a0](s(x0), s(x1))
   equal_sort[a35](cons(x0, x1), cons(x2, x3))
   equal_sort[a35](cons(x0, x1), nil)
   equal_sort[a35](nil, cons(x0, x1))
   equal_sort[a35](nil, nil)
   equal_sort[a43](true_renamed, true_renamed)
   equal_sort[a43](true_renamed, false_renamed)
   equal_sort[a43](false_renamed, true_renamed)
   equal_sort[a43](false_renamed, false_renamed)
   equal_sort[a61](witness_sort[a61], witness_sort[a61])


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

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

   EQ(s(x6), s(y4)) -> EQ(x6, y4)

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

(80) 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:
*EQ(s(x6), s(y4)) -> EQ(x6, y4)
The graph contains the following edges 1 > 1, 2 > 2


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

(81)
YES

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

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

   IF2(true_renamed, x4, y2, xs3) -> RM(x4, xs3)
   RM(x3, cons(y1, xs2)) -> IF2(eq(x3, y1), x3, y1, xs2)
   IF2(false_renamed, x7, y5, xs4) -> RM(x7, xs4)

The TRS R consists of the following rules:

   rm'(x3, cons(y1, xs2)) -> if2'(eq(x3, y1), x3, y1, xs2)
   if2'(true_renamed, x4, y2, xs3) -> true
   if2'(false_renamed, x7, y5, xs4) -> rm'(x7, xs4)
   rm'(x8, nil) -> false
   min(cons(x', nil)) -> x'
   min(cons(x'', cons(y, xs'))) -> if1(le(x'', y), x'', y, xs')
   if1(true_renamed, x1, y', xs'') -> min(cons(x1, xs''))
   if1(false_renamed, x2, y'', xs1) -> min(cons(y'', xs1))
   rm(x3, cons(y1, xs2)) -> if2(eq(x3, y1), x3, y1, xs2)
   if2(true_renamed, x4, y2, xs3) -> rm(x4, xs3)
   eq(0, 0) -> true_renamed
   eq(0, s(y3)) -> false_renamed
   eq(s(x5), 0) -> false_renamed
   eq(s(x6), s(y4)) -> eq(x6, y4)
   if2(false_renamed, x7, y5, xs4) -> cons(y5, rm(x7, xs4))
   rm(x8, nil) -> nil
   le(0, y6) -> true_renamed
   le(s(x9), 0) -> false_renamed
   le(s(x10), s(y7)) -> le(x10, y7)
   min(nil) -> 0
   equal_bool(true, false) -> false
   equal_bool(false, true) -> false
   equal_bool(true, true) -> true
   equal_bool(false, false) -> true
   and(true, x) -> x
   and(false, x) -> false
   or(true, x) -> true
   or(false, x) -> x
   not(false) -> true
   not(true) -> false
   isa_true(true) -> true
   isa_true(false) -> false
   isa_false(true) -> false
   isa_false(false) -> true
   equal_sort[a0](0, 0) -> true
   equal_sort[a0](0, s(v26)) -> false
   equal_sort[a0](s(v27), 0) -> false
   equal_sort[a0](s(v27), s(v28)) -> equal_sort[a0](v27, v28)
   equal_sort[a35](cons(v29, v30), cons(v31, v32)) -> and(equal_sort[a0](v29, v31), equal_sort[a35](v30, v32))
   equal_sort[a35](cons(v29, v30), nil) -> false
   equal_sort[a35](nil, cons(v33, v34)) -> false
   equal_sort[a35](nil, nil) -> true
   equal_sort[a43](true_renamed, true_renamed) -> true
   equal_sort[a43](true_renamed, false_renamed) -> false
   equal_sort[a43](false_renamed, true_renamed) -> false
   equal_sort[a43](false_renamed, false_renamed) -> true
   equal_sort[a61](witness_sort[a61], witness_sort[a61]) -> true

The set Q consists of the following terms:

   rm'(x0, cons(x1, x2))
   if2'(true_renamed, x0, x1, x2)
   if2'(false_renamed, x0, x1, x2)
   rm'(x0, nil)
   min(cons(x0, nil))
   min(cons(x0, cons(x1, x2)))
   if1(true_renamed, x0, x1, x2)
   if1(false_renamed, x0, x1, x2)
   rm(x0, cons(x1, x2))
   if2(true_renamed, x0, x1, x2)
   eq(0, 0)
   eq(0, s(x0))
   eq(s(x0), 0)
   eq(s(x0), s(x1))
   if2(false_renamed, x0, x1, x2)
   rm(x0, nil)
   le(0, x0)
   le(s(x0), 0)
   le(s(x0), s(x1))
   min(nil)
   equal_bool(true, false)
   equal_bool(false, true)
   equal_bool(true, true)
   equal_bool(false, false)
   and(true, x0)
   and(false, x0)
   or(true, x0)
   or(false, x0)
   not(false)
   not(true)
   isa_true(true)
   isa_true(false)
   isa_false(true)
   isa_false(false)
   equal_sort[a0](0, 0)
   equal_sort[a0](0, s(x0))
   equal_sort[a0](s(x0), 0)
   equal_sort[a0](s(x0), s(x1))
   equal_sort[a35](cons(x0, x1), cons(x2, x3))
   equal_sort[a35](cons(x0, x1), nil)
   equal_sort[a35](nil, cons(x0, x1))
   equal_sort[a35](nil, nil)
   equal_sort[a43](true_renamed, true_renamed)
   equal_sort[a43](true_renamed, false_renamed)
   equal_sort[a43](false_renamed, true_renamed)
   equal_sort[a43](false_renamed, false_renamed)
   equal_sort[a61](witness_sort[a61], witness_sort[a61])

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

(83) 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.
----------------------------------------

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

   IF2(true_renamed, x4, y2, xs3) -> RM(x4, xs3)
   RM(x3, cons(y1, xs2)) -> IF2(eq(x3, y1), x3, y1, xs2)
   IF2(false_renamed, x7, y5, xs4) -> RM(x7, xs4)

The TRS R consists of the following rules:

   eq(0, 0) -> true_renamed
   eq(0, s(y3)) -> false_renamed
   eq(s(x5), 0) -> false_renamed
   eq(s(x6), s(y4)) -> eq(x6, y4)

The set Q consists of the following terms:

   rm'(x0, cons(x1, x2))
   if2'(true_renamed, x0, x1, x2)
   if2'(false_renamed, x0, x1, x2)
   rm'(x0, nil)
   min(cons(x0, nil))
   min(cons(x0, cons(x1, x2)))
   if1(true_renamed, x0, x1, x2)
   if1(false_renamed, x0, x1, x2)
   rm(x0, cons(x1, x2))
   if2(true_renamed, x0, x1, x2)
   eq(0, 0)
   eq(0, s(x0))
   eq(s(x0), 0)
   eq(s(x0), s(x1))
   if2(false_renamed, x0, x1, x2)
   rm(x0, nil)
   le(0, x0)
   le(s(x0), 0)
   le(s(x0), s(x1))
   min(nil)
   equal_bool(true, false)
   equal_bool(false, true)
   equal_bool(true, true)
   equal_bool(false, false)
   and(true, x0)
   and(false, x0)
   or(true, x0)
   or(false, x0)
   not(false)
   not(true)
   isa_true(true)
   isa_true(false)
   isa_false(true)
   isa_false(false)
   equal_sort[a0](0, 0)
   equal_sort[a0](0, s(x0))
   equal_sort[a0](s(x0), 0)
   equal_sort[a0](s(x0), s(x1))
   equal_sort[a35](cons(x0, x1), cons(x2, x3))
   equal_sort[a35](cons(x0, x1), nil)
   equal_sort[a35](nil, cons(x0, x1))
   equal_sort[a35](nil, nil)
   equal_sort[a43](true_renamed, true_renamed)
   equal_sort[a43](true_renamed, false_renamed)
   equal_sort[a43](false_renamed, true_renamed)
   equal_sort[a43](false_renamed, false_renamed)
   equal_sort[a61](witness_sort[a61], witness_sort[a61])

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

(85) 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].

   rm'(x0, cons(x1, x2))
   if2'(true_renamed, x0, x1, x2)
   if2'(false_renamed, x0, x1, x2)
   rm'(x0, nil)
   min(cons(x0, nil))
   min(cons(x0, cons(x1, x2)))
   if1(true_renamed, x0, x1, x2)
   if1(false_renamed, x0, x1, x2)
   rm(x0, cons(x1, x2))
   if2(true_renamed, x0, x1, x2)
   if2(false_renamed, x0, x1, x2)
   rm(x0, nil)
   le(0, x0)
   le(s(x0), 0)
   le(s(x0), s(x1))
   min(nil)
   equal_bool(true, false)
   equal_bool(false, true)
   equal_bool(true, true)
   equal_bool(false, false)
   and(true, x0)
   and(false, x0)
   or(true, x0)
   or(false, x0)
   not(false)
   not(true)
   isa_true(true)
   isa_true(false)
   isa_false(true)
   isa_false(false)
   equal_sort[a0](0, 0)
   equal_sort[a0](0, s(x0))
   equal_sort[a0](s(x0), 0)
   equal_sort[a0](s(x0), s(x1))
   equal_sort[a35](cons(x0, x1), cons(x2, x3))
   equal_sort[a35](cons(x0, x1), nil)
   equal_sort[a35](nil, cons(x0, x1))
   equal_sort[a35](nil, nil)
   equal_sort[a43](true_renamed, true_renamed)
   equal_sort[a43](true_renamed, false_renamed)
   equal_sort[a43](false_renamed, true_renamed)
   equal_sort[a43](false_renamed, false_renamed)
   equal_sort[a61](witness_sort[a61], witness_sort[a61])


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

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

   IF2(true_renamed, x4, y2, xs3) -> RM(x4, xs3)
   RM(x3, cons(y1, xs2)) -> IF2(eq(x3, y1), x3, y1, xs2)
   IF2(false_renamed, x7, y5, xs4) -> RM(x7, xs4)

The TRS R consists of the following rules:

   eq(0, 0) -> true_renamed
   eq(0, s(y3)) -> false_renamed
   eq(s(x5), 0) -> false_renamed
   eq(s(x6), s(y4)) -> eq(x6, y4)

The set Q consists of the following terms:

   eq(0, 0)
   eq(0, s(x0))
   eq(s(x0), 0)
   eq(s(x0), s(x1))

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

(87) 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:
*RM(x3, cons(y1, xs2)) -> IF2(eq(x3, y1), x3, y1, xs2)
The graph contains the following edges 1 >= 2, 2 > 3, 2 > 4


*IF2(true_renamed, x4, y2, xs3) -> RM(x4, xs3)
The graph contains the following edges 2 >= 1, 4 >= 2


*IF2(false_renamed, x7, y5, xs4) -> RM(x7, xs4)
The graph contains the following edges 2 >= 1, 4 >= 2


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

(88)
YES

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

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

   IF1(true_renamed, x1, y', xs'') -> MIN(cons(x1, xs''))
   MIN(cons(x'', cons(y, xs'))) -> IF1(le(x'', y), x'', y, xs')
   IF1(false_renamed, x2, y'', xs1) -> MIN(cons(y'', xs1))

The TRS R consists of the following rules:

   rm'(x3, cons(y1, xs2)) -> if2'(eq(x3, y1), x3, y1, xs2)
   if2'(true_renamed, x4, y2, xs3) -> true
   if2'(false_renamed, x7, y5, xs4) -> rm'(x7, xs4)
   rm'(x8, nil) -> false
   min(cons(x', nil)) -> x'
   min(cons(x'', cons(y, xs'))) -> if1(le(x'', y), x'', y, xs')
   if1(true_renamed, x1, y', xs'') -> min(cons(x1, xs''))
   if1(false_renamed, x2, y'', xs1) -> min(cons(y'', xs1))
   rm(x3, cons(y1, xs2)) -> if2(eq(x3, y1), x3, y1, xs2)
   if2(true_renamed, x4, y2, xs3) -> rm(x4, xs3)
   eq(0, 0) -> true_renamed
   eq(0, s(y3)) -> false_renamed
   eq(s(x5), 0) -> false_renamed
   eq(s(x6), s(y4)) -> eq(x6, y4)
   if2(false_renamed, x7, y5, xs4) -> cons(y5, rm(x7, xs4))
   rm(x8, nil) -> nil
   le(0, y6) -> true_renamed
   le(s(x9), 0) -> false_renamed
   le(s(x10), s(y7)) -> le(x10, y7)
   min(nil) -> 0
   equal_bool(true, false) -> false
   equal_bool(false, true) -> false
   equal_bool(true, true) -> true
   equal_bool(false, false) -> true
   and(true, x) -> x
   and(false, x) -> false
   or(true, x) -> true
   or(false, x) -> x
   not(false) -> true
   not(true) -> false
   isa_true(true) -> true
   isa_true(false) -> false
   isa_false(true) -> false
   isa_false(false) -> true
   equal_sort[a0](0, 0) -> true
   equal_sort[a0](0, s(v26)) -> false
   equal_sort[a0](s(v27), 0) -> false
   equal_sort[a0](s(v27), s(v28)) -> equal_sort[a0](v27, v28)
   equal_sort[a35](cons(v29, v30), cons(v31, v32)) -> and(equal_sort[a0](v29, v31), equal_sort[a35](v30, v32))
   equal_sort[a35](cons(v29, v30), nil) -> false
   equal_sort[a35](nil, cons(v33, v34)) -> false
   equal_sort[a35](nil, nil) -> true
   equal_sort[a43](true_renamed, true_renamed) -> true
   equal_sort[a43](true_renamed, false_renamed) -> false
   equal_sort[a43](false_renamed, true_renamed) -> false
   equal_sort[a43](false_renamed, false_renamed) -> true
   equal_sort[a61](witness_sort[a61], witness_sort[a61]) -> true

The set Q consists of the following terms:

   rm'(x0, cons(x1, x2))
   if2'(true_renamed, x0, x1, x2)
   if2'(false_renamed, x0, x1, x2)
   rm'(x0, nil)
   min(cons(x0, nil))
   min(cons(x0, cons(x1, x2)))
   if1(true_renamed, x0, x1, x2)
   if1(false_renamed, x0, x1, x2)
   rm(x0, cons(x1, x2))
   if2(true_renamed, x0, x1, x2)
   eq(0, 0)
   eq(0, s(x0))
   eq(s(x0), 0)
   eq(s(x0), s(x1))
   if2(false_renamed, x0, x1, x2)
   rm(x0, nil)
   le(0, x0)
   le(s(x0), 0)
   le(s(x0), s(x1))
   min(nil)
   equal_bool(true, false)
   equal_bool(false, true)
   equal_bool(true, true)
   equal_bool(false, false)
   and(true, x0)
   and(false, x0)
   or(true, x0)
   or(false, x0)
   not(false)
   not(true)
   isa_true(true)
   isa_true(false)
   isa_false(true)
   isa_false(false)
   equal_sort[a0](0, 0)
   equal_sort[a0](0, s(x0))
   equal_sort[a0](s(x0), 0)
   equal_sort[a0](s(x0), s(x1))
   equal_sort[a35](cons(x0, x1), cons(x2, x3))
   equal_sort[a35](cons(x0, x1), nil)
   equal_sort[a35](nil, cons(x0, x1))
   equal_sort[a35](nil, nil)
   equal_sort[a43](true_renamed, true_renamed)
   equal_sort[a43](true_renamed, false_renamed)
   equal_sort[a43](false_renamed, true_renamed)
   equal_sort[a43](false_renamed, false_renamed)
   equal_sort[a61](witness_sort[a61], witness_sort[a61])

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

(90) 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.
----------------------------------------

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

   IF1(true_renamed, x1, y', xs'') -> MIN(cons(x1, xs''))
   MIN(cons(x'', cons(y, xs'))) -> IF1(le(x'', y), x'', y, xs')
   IF1(false_renamed, x2, y'', xs1) -> MIN(cons(y'', xs1))

The TRS R consists of the following rules:

   le(0, y6) -> true_renamed
   le(s(x9), 0) -> false_renamed
   le(s(x10), s(y7)) -> le(x10, y7)

The set Q consists of the following terms:

   rm'(x0, cons(x1, x2))
   if2'(true_renamed, x0, x1, x2)
   if2'(false_renamed, x0, x1, x2)
   rm'(x0, nil)
   min(cons(x0, nil))
   min(cons(x0, cons(x1, x2)))
   if1(true_renamed, x0, x1, x2)
   if1(false_renamed, x0, x1, x2)
   rm(x0, cons(x1, x2))
   if2(true_renamed, x0, x1, x2)
   eq(0, 0)
   eq(0, s(x0))
   eq(s(x0), 0)
   eq(s(x0), s(x1))
   if2(false_renamed, x0, x1, x2)
   rm(x0, nil)
   le(0, x0)
   le(s(x0), 0)
   le(s(x0), s(x1))
   min(nil)
   equal_bool(true, false)
   equal_bool(false, true)
   equal_bool(true, true)
   equal_bool(false, false)
   and(true, x0)
   and(false, x0)
   or(true, x0)
   or(false, x0)
   not(false)
   not(true)
   isa_true(true)
   isa_true(false)
   isa_false(true)
   isa_false(false)
   equal_sort[a0](0, 0)
   equal_sort[a0](0, s(x0))
   equal_sort[a0](s(x0), 0)
   equal_sort[a0](s(x0), s(x1))
   equal_sort[a35](cons(x0, x1), cons(x2, x3))
   equal_sort[a35](cons(x0, x1), nil)
   equal_sort[a35](nil, cons(x0, x1))
   equal_sort[a35](nil, nil)
   equal_sort[a43](true_renamed, true_renamed)
   equal_sort[a43](true_renamed, false_renamed)
   equal_sort[a43](false_renamed, true_renamed)
   equal_sort[a43](false_renamed, false_renamed)
   equal_sort[a61](witness_sort[a61], witness_sort[a61])

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

(92) 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].

   rm'(x0, cons(x1, x2))
   if2'(true_renamed, x0, x1, x2)
   if2'(false_renamed, x0, x1, x2)
   rm'(x0, nil)
   min(cons(x0, nil))
   min(cons(x0, cons(x1, x2)))
   if1(true_renamed, x0, x1, x2)
   if1(false_renamed, x0, x1, x2)
   rm(x0, cons(x1, x2))
   if2(true_renamed, x0, x1, x2)
   eq(0, 0)
   eq(0, s(x0))
   eq(s(x0), 0)
   eq(s(x0), s(x1))
   if2(false_renamed, x0, x1, x2)
   rm(x0, nil)
   min(nil)
   equal_bool(true, false)
   equal_bool(false, true)
   equal_bool(true, true)
   equal_bool(false, false)
   and(true, x0)
   and(false, x0)
   or(true, x0)
   or(false, x0)
   not(false)
   not(true)
   isa_true(true)
   isa_true(false)
   isa_false(true)
   isa_false(false)
   equal_sort[a0](0, 0)
   equal_sort[a0](0, s(x0))
   equal_sort[a0](s(x0), 0)
   equal_sort[a0](s(x0), s(x1))
   equal_sort[a35](cons(x0, x1), cons(x2, x3))
   equal_sort[a35](cons(x0, x1), nil)
   equal_sort[a35](nil, cons(x0, x1))
   equal_sort[a35](nil, nil)
   equal_sort[a43](true_renamed, true_renamed)
   equal_sort[a43](true_renamed, false_renamed)
   equal_sort[a43](false_renamed, true_renamed)
   equal_sort[a43](false_renamed, false_renamed)
   equal_sort[a61](witness_sort[a61], witness_sort[a61])


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

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

   IF1(true_renamed, x1, y', xs'') -> MIN(cons(x1, xs''))
   MIN(cons(x'', cons(y, xs'))) -> IF1(le(x'', y), x'', y, xs')
   IF1(false_renamed, x2, y'', xs1) -> MIN(cons(y'', xs1))

The TRS R consists of the following rules:

   le(0, y6) -> true_renamed
   le(s(x9), 0) -> false_renamed
   le(s(x10), s(y7)) -> le(x10, y7)

The set Q consists of the following terms:

   le(0, x0)
   le(s(x0), 0)
   le(s(x0), s(x1))

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

(94) QDPOrderProof (EQUIVALENT)
We use the reduction pair processor [LPAR04,JAR06].


The following pairs can be oriented strictly and are deleted.

   IF1(true_renamed, x1, y', xs'') -> MIN(cons(x1, xs''))
   MIN(cons(x'', cons(y, xs'))) -> IF1(le(x'', y), x'', y, xs')
   IF1(false_renamed, x2, y'', xs1) -> MIN(cons(y'', xs1))
The remaining pairs can at least be oriented weakly.
Used ordering:  Combined order from the following AFS and order.
IF1(x1, x2, x3, x4)  =  IF1(x4)

MIN(x1)  =  x1

cons(x1, x2)  =  cons(x2)


Knuth-Bendix order [KBO] with precedence:trivial

and weight map:

   dummyConstant=1
   IF1_1=3
   cons_1=2

The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented:
none


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

(95)
Obligation:
Q DP problem:
P is empty.
The TRS R consists of the following rules:

   le(0, y6) -> true_renamed
   le(s(x9), 0) -> false_renamed
   le(s(x10), s(y7)) -> le(x10, y7)

The set Q consists of the following terms:

   le(0, x0)
   le(s(x0), 0)
   le(s(x0), s(x1))

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

(96) PisEmptyProof (EQUIVALENT)
The TRS P is empty. Hence, there is no (P,Q,R) chain.
----------------------------------------

(97)
YES

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

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

   IF2'(false_renamed, x7, y5, xs4) -> RM'(x7, xs4)
   RM'(x3, cons(y1, xs2)) -> IF2'(eq(x3, y1), x3, y1, xs2)

The TRS R consists of the following rules:

   rm'(x3, cons(y1, xs2)) -> if2'(eq(x3, y1), x3, y1, xs2)
   if2'(true_renamed, x4, y2, xs3) -> true
   if2'(false_renamed, x7, y5, xs4) -> rm'(x7, xs4)
   rm'(x8, nil) -> false
   min(cons(x', nil)) -> x'
   min(cons(x'', cons(y, xs'))) -> if1(le(x'', y), x'', y, xs')
   if1(true_renamed, x1, y', xs'') -> min(cons(x1, xs''))
   if1(false_renamed, x2, y'', xs1) -> min(cons(y'', xs1))
   rm(x3, cons(y1, xs2)) -> if2(eq(x3, y1), x3, y1, xs2)
   if2(true_renamed, x4, y2, xs3) -> rm(x4, xs3)
   eq(0, 0) -> true_renamed
   eq(0, s(y3)) -> false_renamed
   eq(s(x5), 0) -> false_renamed
   eq(s(x6), s(y4)) -> eq(x6, y4)
   if2(false_renamed, x7, y5, xs4) -> cons(y5, rm(x7, xs4))
   rm(x8, nil) -> nil
   le(0, y6) -> true_renamed
   le(s(x9), 0) -> false_renamed
   le(s(x10), s(y7)) -> le(x10, y7)
   min(nil) -> 0
   equal_bool(true, false) -> false
   equal_bool(false, true) -> false
   equal_bool(true, true) -> true
   equal_bool(false, false) -> true
   and(true, x) -> x
   and(false, x) -> false
   or(true, x) -> true
   or(false, x) -> x
   not(false) -> true
   not(true) -> false
   isa_true(true) -> true
   isa_true(false) -> false
   isa_false(true) -> false
   isa_false(false) -> true
   equal_sort[a0](0, 0) -> true
   equal_sort[a0](0, s(v26)) -> false
   equal_sort[a0](s(v27), 0) -> false
   equal_sort[a0](s(v27), s(v28)) -> equal_sort[a0](v27, v28)
   equal_sort[a35](cons(v29, v30), cons(v31, v32)) -> and(equal_sort[a0](v29, v31), equal_sort[a35](v30, v32))
   equal_sort[a35](cons(v29, v30), nil) -> false
   equal_sort[a35](nil, cons(v33, v34)) -> false
   equal_sort[a35](nil, nil) -> true
   equal_sort[a43](true_renamed, true_renamed) -> true
   equal_sort[a43](true_renamed, false_renamed) -> false
   equal_sort[a43](false_renamed, true_renamed) -> false
   equal_sort[a43](false_renamed, false_renamed) -> true
   equal_sort[a61](witness_sort[a61], witness_sort[a61]) -> true

The set Q consists of the following terms:

   rm'(x0, cons(x1, x2))
   if2'(true_renamed, x0, x1, x2)
   if2'(false_renamed, x0, x1, x2)
   rm'(x0, nil)
   min(cons(x0, nil))
   min(cons(x0, cons(x1, x2)))
   if1(true_renamed, x0, x1, x2)
   if1(false_renamed, x0, x1, x2)
   rm(x0, cons(x1, x2))
   if2(true_renamed, x0, x1, x2)
   eq(0, 0)
   eq(0, s(x0))
   eq(s(x0), 0)
   eq(s(x0), s(x1))
   if2(false_renamed, x0, x1, x2)
   rm(x0, nil)
   le(0, x0)
   le(s(x0), 0)
   le(s(x0), s(x1))
   min(nil)
   equal_bool(true, false)
   equal_bool(false, true)
   equal_bool(true, true)
   equal_bool(false, false)
   and(true, x0)
   and(false, x0)
   or(true, x0)
   or(false, x0)
   not(false)
   not(true)
   isa_true(true)
   isa_true(false)
   isa_false(true)
   isa_false(false)
   equal_sort[a0](0, 0)
   equal_sort[a0](0, s(x0))
   equal_sort[a0](s(x0), 0)
   equal_sort[a0](s(x0), s(x1))
   equal_sort[a35](cons(x0, x1), cons(x2, x3))
   equal_sort[a35](cons(x0, x1), nil)
   equal_sort[a35](nil, cons(x0, x1))
   equal_sort[a35](nil, nil)
   equal_sort[a43](true_renamed, true_renamed)
   equal_sort[a43](true_renamed, false_renamed)
   equal_sort[a43](false_renamed, true_renamed)
   equal_sort[a43](false_renamed, false_renamed)
   equal_sort[a61](witness_sort[a61], witness_sort[a61])

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

(99) 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.
----------------------------------------

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

   IF2'(false_renamed, x7, y5, xs4) -> RM'(x7, xs4)
   RM'(x3, cons(y1, xs2)) -> IF2'(eq(x3, y1), x3, y1, xs2)

The TRS R consists of the following rules:

   eq(0, 0) -> true_renamed
   eq(0, s(y3)) -> false_renamed
   eq(s(x5), 0) -> false_renamed
   eq(s(x6), s(y4)) -> eq(x6, y4)

The set Q consists of the following terms:

   rm'(x0, cons(x1, x2))
   if2'(true_renamed, x0, x1, x2)
   if2'(false_renamed, x0, x1, x2)
   rm'(x0, nil)
   min(cons(x0, nil))
   min(cons(x0, cons(x1, x2)))
   if1(true_renamed, x0, x1, x2)
   if1(false_renamed, x0, x1, x2)
   rm(x0, cons(x1, x2))
   if2(true_renamed, x0, x1, x2)
   eq(0, 0)
   eq(0, s(x0))
   eq(s(x0), 0)
   eq(s(x0), s(x1))
   if2(false_renamed, x0, x1, x2)
   rm(x0, nil)
   le(0, x0)
   le(s(x0), 0)
   le(s(x0), s(x1))
   min(nil)
   equal_bool(true, false)
   equal_bool(false, true)
   equal_bool(true, true)
   equal_bool(false, false)
   and(true, x0)
   and(false, x0)
   or(true, x0)
   or(false, x0)
   not(false)
   not(true)
   isa_true(true)
   isa_true(false)
   isa_false(true)
   isa_false(false)
   equal_sort[a0](0, 0)
   equal_sort[a0](0, s(x0))
   equal_sort[a0](s(x0), 0)
   equal_sort[a0](s(x0), s(x1))
   equal_sort[a35](cons(x0, x1), cons(x2, x3))
   equal_sort[a35](cons(x0, x1), nil)
   equal_sort[a35](nil, cons(x0, x1))
   equal_sort[a35](nil, nil)
   equal_sort[a43](true_renamed, true_renamed)
   equal_sort[a43](true_renamed, false_renamed)
   equal_sort[a43](false_renamed, true_renamed)
   equal_sort[a43](false_renamed, false_renamed)
   equal_sort[a61](witness_sort[a61], witness_sort[a61])

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

(101) 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].

   rm'(x0, cons(x1, x2))
   if2'(true_renamed, x0, x1, x2)
   if2'(false_renamed, x0, x1, x2)
   rm'(x0, nil)
   min(cons(x0, nil))
   min(cons(x0, cons(x1, x2)))
   if1(true_renamed, x0, x1, x2)
   if1(false_renamed, x0, x1, x2)
   rm(x0, cons(x1, x2))
   if2(true_renamed, x0, x1, x2)
   if2(false_renamed, x0, x1, x2)
   rm(x0, nil)
   le(0, x0)
   le(s(x0), 0)
   le(s(x0), s(x1))
   min(nil)
   equal_bool(true, false)
   equal_bool(false, true)
   equal_bool(true, true)
   equal_bool(false, false)
   and(true, x0)
   and(false, x0)
   or(true, x0)
   or(false, x0)
   not(false)
   not(true)
   isa_true(true)
   isa_true(false)
   isa_false(true)
   isa_false(false)
   equal_sort[a0](0, 0)
   equal_sort[a0](0, s(x0))
   equal_sort[a0](s(x0), 0)
   equal_sort[a0](s(x0), s(x1))
   equal_sort[a35](cons(x0, x1), cons(x2, x3))
   equal_sort[a35](cons(x0, x1), nil)
   equal_sort[a35](nil, cons(x0, x1))
   equal_sort[a35](nil, nil)
   equal_sort[a43](true_renamed, true_renamed)
   equal_sort[a43](true_renamed, false_renamed)
   equal_sort[a43](false_renamed, true_renamed)
   equal_sort[a43](false_renamed, false_renamed)
   equal_sort[a61](witness_sort[a61], witness_sort[a61])


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

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

   IF2'(false_renamed, x7, y5, xs4) -> RM'(x7, xs4)
   RM'(x3, cons(y1, xs2)) -> IF2'(eq(x3, y1), x3, y1, xs2)

The TRS R consists of the following rules:

   eq(0, 0) -> true_renamed
   eq(0, s(y3)) -> false_renamed
   eq(s(x5), 0) -> false_renamed
   eq(s(x6), s(y4)) -> eq(x6, y4)

The set Q consists of the following terms:

   eq(0, 0)
   eq(0, s(x0))
   eq(s(x0), 0)
   eq(s(x0), s(x1))

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

(103) 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:
*RM'(x3, cons(y1, xs2)) -> IF2'(eq(x3, y1), x3, y1, xs2)
The graph contains the following edges 1 >= 2, 2 > 3, 2 > 4


*IF2'(false_renamed, x7, y5, xs4) -> RM'(x7, xs4)
The graph contains the following edges 2 >= 1, 4 >= 2


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

(104)
YES