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


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


YES
proof of /export/starexec/sandbox/benchmark/theBenchmark.xml
# AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty


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

(0) QTRS
(1) Overlay + Local Confluence [EQUIVALENT, 19 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) QDPSizeChangeProof [EQUIVALENT, 0 ms]
        (34) YES
    (35) QDP
        (36) UsableRulesProof [EQUIVALENT, 0 ms]
        (37) QDP
        (38) QReductionProof [EQUIVALENT, 0 ms]
        (39) QDP
        (40) TransformationProof [EQUIVALENT, 3 ms]
        (41) QDP
        (42) TransformationProof [EQUIVALENT, 0 ms]
        (43) QDP
        (44) Induction-Processor [SOUND, 15 ms]
        (45) AND
            (46) QDP
                (47) UsableRulesProof [EQUIVALENT, 0 ms]
                (48) QDP
                (49) QReductionProof [EQUIVALENT, 0 ms]
                (50) QDP
                (51) Induction-Processor [SOUND, 5 ms]
                (52) AND
                    (53) QDP
                        (54) PisEmptyProof [EQUIVALENT, 0 ms]
                        (55) YES
                    (56) QTRS
                        (57) QTRSRRRProof [EQUIVALENT, 54 ms]
                        (58) QTRS
                        (59) QTRSRRRProof [EQUIVALENT, 0 ms]
                        (60) QTRS
                        (61) RisEmptyProof [EQUIVALENT, 0 ms]
                        (62) YES
            (63) QTRS
                (64) QTRSRRRProof [EQUIVALENT, 68 ms]
                (65) QTRS
                (66) QTRSRRRProof [EQUIVALENT, 0 ms]
                (67) QTRS
                (68) RisEmptyProof [EQUIVALENT, 0 ms]
                (69) YES


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

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

   qsort(nil) -> nil
   qsort(cons(x, xs)) -> append(qsort(filterlow(x, cons(x, xs))), cons(x, qsort(filterhigh(x, cons(x, xs)))))
   filterlow(n, nil) -> nil
   filterlow(n, cons(x, xs)) -> if1(ge(n, x), n, x, xs)
   if1(true, n, x, xs) -> filterlow(n, xs)
   if1(false, n, x, xs) -> cons(x, filterlow(n, xs))
   filterhigh(n, nil) -> nil
   filterhigh(n, cons(x, xs)) -> if2(ge(x, n), n, x, xs)
   if2(true, n, x, xs) -> filterhigh(n, xs)
   if2(false, n, x, xs) -> cons(x, filterhigh(n, xs))
   ge(x, 0) -> true
   ge(0, s(x)) -> false
   ge(s(x), s(y)) -> ge(x, y)
   append(nil, ys) -> ys
   append(cons(x, xs), ys) -> cons(x, append(xs, ys))

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:

   qsort(nil) -> nil
   qsort(cons(x, xs)) -> append(qsort(filterlow(x, cons(x, xs))), cons(x, qsort(filterhigh(x, cons(x, xs)))))
   filterlow(n, nil) -> nil
   filterlow(n, cons(x, xs)) -> if1(ge(n, x), n, x, xs)
   if1(true, n, x, xs) -> filterlow(n, xs)
   if1(false, n, x, xs) -> cons(x, filterlow(n, xs))
   filterhigh(n, nil) -> nil
   filterhigh(n, cons(x, xs)) -> if2(ge(x, n), n, x, xs)
   if2(true, n, x, xs) -> filterhigh(n, xs)
   if2(false, n, x, xs) -> cons(x, filterhigh(n, xs))
   ge(x, 0) -> true
   ge(0, s(x)) -> false
   ge(s(x), s(y)) -> ge(x, y)
   append(nil, ys) -> ys
   append(cons(x, xs), ys) -> cons(x, append(xs, ys))

The set Q consists of the following terms:

   qsort(nil)
   qsort(cons(x0, x1))
   filterlow(x0, nil)
   filterlow(x0, cons(x1, x2))
   if1(true, x0, x1, x2)
   if1(false, x0, x1, x2)
   filterhigh(x0, nil)
   filterhigh(x0, cons(x1, x2))
   if2(true, x0, x1, x2)
   if2(false, x0, x1, x2)
   ge(x0, 0)
   ge(0, s(x0))
   ge(s(x0), s(x1))
   append(nil, ys)
   append(cons(x0, x1), ys)


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

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

   QSORT(cons(x, xs)) -> APPEND(qsort(filterlow(x, cons(x, xs))), cons(x, qsort(filterhigh(x, cons(x, xs)))))
   QSORT(cons(x, xs)) -> QSORT(filterlow(x, cons(x, xs)))
   QSORT(cons(x, xs)) -> FILTERLOW(x, cons(x, xs))
   QSORT(cons(x, xs)) -> QSORT(filterhigh(x, cons(x, xs)))
   QSORT(cons(x, xs)) -> FILTERHIGH(x, cons(x, xs))
   FILTERLOW(n, cons(x, xs)) -> IF1(ge(n, x), n, x, xs)
   FILTERLOW(n, cons(x, xs)) -> GE(n, x)
   IF1(true, n, x, xs) -> FILTERLOW(n, xs)
   IF1(false, n, x, xs) -> FILTERLOW(n, xs)
   FILTERHIGH(n, cons(x, xs)) -> IF2(ge(x, n), n, x, xs)
   FILTERHIGH(n, cons(x, xs)) -> GE(x, n)
   IF2(true, n, x, xs) -> FILTERHIGH(n, xs)
   IF2(false, n, x, xs) -> FILTERHIGH(n, xs)
   GE(s(x), s(y)) -> GE(x, y)
   APPEND(cons(x, xs), ys) -> APPEND(xs, ys)

The TRS R consists of the following rules:

   qsort(nil) -> nil
   qsort(cons(x, xs)) -> append(qsort(filterlow(x, cons(x, xs))), cons(x, qsort(filterhigh(x, cons(x, xs)))))
   filterlow(n, nil) -> nil
   filterlow(n, cons(x, xs)) -> if1(ge(n, x), n, x, xs)
   if1(true, n, x, xs) -> filterlow(n, xs)
   if1(false, n, x, xs) -> cons(x, filterlow(n, xs))
   filterhigh(n, nil) -> nil
   filterhigh(n, cons(x, xs)) -> if2(ge(x, n), n, x, xs)
   if2(true, n, x, xs) -> filterhigh(n, xs)
   if2(false, n, x, xs) -> cons(x, filterhigh(n, xs))
   ge(x, 0) -> true
   ge(0, s(x)) -> false
   ge(s(x), s(y)) -> ge(x, y)
   append(nil, ys) -> ys
   append(cons(x, xs), ys) -> cons(x, append(xs, ys))

The set Q consists of the following terms:

   qsort(nil)
   qsort(cons(x0, x1))
   filterlow(x0, nil)
   filterlow(x0, cons(x1, x2))
   if1(true, x0, x1, x2)
   if1(false, x0, x1, x2)
   filterhigh(x0, nil)
   filterhigh(x0, cons(x1, x2))
   if2(true, x0, x1, x2)
   if2(false, x0, x1, x2)
   ge(x0, 0)
   ge(0, s(x0))
   ge(s(x0), s(x1))
   append(nil, ys)
   append(cons(x0, x1), ys)

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

(6)
Complex Obligation (AND)

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

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

   APPEND(cons(x, xs), ys) -> APPEND(xs, ys)

The TRS R consists of the following rules:

   qsort(nil) -> nil
   qsort(cons(x, xs)) -> append(qsort(filterlow(x, cons(x, xs))), cons(x, qsort(filterhigh(x, cons(x, xs)))))
   filterlow(n, nil) -> nil
   filterlow(n, cons(x, xs)) -> if1(ge(n, x), n, x, xs)
   if1(true, n, x, xs) -> filterlow(n, xs)
   if1(false, n, x, xs) -> cons(x, filterlow(n, xs))
   filterhigh(n, nil) -> nil
   filterhigh(n, cons(x, xs)) -> if2(ge(x, n), n, x, xs)
   if2(true, n, x, xs) -> filterhigh(n, xs)
   if2(false, n, x, xs) -> cons(x, filterhigh(n, xs))
   ge(x, 0) -> true
   ge(0, s(x)) -> false
   ge(s(x), s(y)) -> ge(x, y)
   append(nil, ys) -> ys
   append(cons(x, xs), ys) -> cons(x, append(xs, ys))

The set Q consists of the following terms:

   qsort(nil)
   qsort(cons(x0, x1))
   filterlow(x0, nil)
   filterlow(x0, cons(x1, x2))
   if1(true, x0, x1, x2)
   if1(false, x0, x1, x2)
   filterhigh(x0, nil)
   filterhigh(x0, cons(x1, x2))
   if2(true, x0, x1, x2)
   if2(false, x0, x1, x2)
   ge(x0, 0)
   ge(0, s(x0))
   ge(s(x0), s(x1))
   append(nil, ys)
   append(cons(x0, x1), ys)

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:

   APPEND(cons(x, xs), ys) -> APPEND(xs, ys)

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

   qsort(nil)
   qsort(cons(x0, x1))
   filterlow(x0, nil)
   filterlow(x0, cons(x1, x2))
   if1(true, x0, x1, x2)
   if1(false, x0, x1, x2)
   filterhigh(x0, nil)
   filterhigh(x0, cons(x1, x2))
   if2(true, x0, x1, x2)
   if2(false, x0, x1, x2)
   ge(x0, 0)
   ge(0, s(x0))
   ge(s(x0), s(x1))
   append(nil, ys)
   append(cons(x0, x1), ys)

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

   qsort(nil)
   qsort(cons(x0, x1))
   filterlow(x0, nil)
   filterlow(x0, cons(x1, x2))
   if1(true, x0, x1, x2)
   if1(false, x0, x1, x2)
   filterhigh(x0, nil)
   filterhigh(x0, cons(x1, x2))
   if2(true, x0, x1, x2)
   if2(false, x0, x1, x2)
   ge(x0, 0)
   ge(0, s(x0))
   ge(s(x0), s(x1))
   append(nil, ys)
   append(cons(x0, x1), ys)


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

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

   APPEND(cons(x, xs), ys) -> APPEND(xs, ys)

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:
*APPEND(cons(x, xs), ys) -> APPEND(xs, ys)
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:

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

The TRS R consists of the following rules:

   qsort(nil) -> nil
   qsort(cons(x, xs)) -> append(qsort(filterlow(x, cons(x, xs))), cons(x, qsort(filterhigh(x, cons(x, xs)))))
   filterlow(n, nil) -> nil
   filterlow(n, cons(x, xs)) -> if1(ge(n, x), n, x, xs)
   if1(true, n, x, xs) -> filterlow(n, xs)
   if1(false, n, x, xs) -> cons(x, filterlow(n, xs))
   filterhigh(n, nil) -> nil
   filterhigh(n, cons(x, xs)) -> if2(ge(x, n), n, x, xs)
   if2(true, n, x, xs) -> filterhigh(n, xs)
   if2(false, n, x, xs) -> cons(x, filterhigh(n, xs))
   ge(x, 0) -> true
   ge(0, s(x)) -> false
   ge(s(x), s(y)) -> ge(x, y)
   append(nil, ys) -> ys
   append(cons(x, xs), ys) -> cons(x, append(xs, ys))

The set Q consists of the following terms:

   qsort(nil)
   qsort(cons(x0, x1))
   filterlow(x0, nil)
   filterlow(x0, cons(x1, x2))
   if1(true, x0, x1, x2)
   if1(false, x0, x1, x2)
   filterhigh(x0, nil)
   filterhigh(x0, cons(x1, x2))
   if2(true, x0, x1, x2)
   if2(false, x0, x1, x2)
   ge(x0, 0)
   ge(0, s(x0))
   ge(s(x0), s(x1))
   append(nil, ys)
   append(cons(x0, x1), ys)

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:

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

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

   qsort(nil)
   qsort(cons(x0, x1))
   filterlow(x0, nil)
   filterlow(x0, cons(x1, x2))
   if1(true, x0, x1, x2)
   if1(false, x0, x1, x2)
   filterhigh(x0, nil)
   filterhigh(x0, cons(x1, x2))
   if2(true, x0, x1, x2)
   if2(false, x0, x1, x2)
   ge(x0, 0)
   ge(0, s(x0))
   ge(s(x0), s(x1))
   append(nil, ys)
   append(cons(x0, x1), ys)

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

   qsort(nil)
   qsort(cons(x0, x1))
   filterlow(x0, nil)
   filterlow(x0, cons(x1, x2))
   if1(true, x0, x1, x2)
   if1(false, x0, x1, x2)
   filterhigh(x0, nil)
   filterhigh(x0, cons(x1, x2))
   if2(true, x0, x1, x2)
   if2(false, x0, x1, x2)
   ge(x0, 0)
   ge(0, s(x0))
   ge(s(x0), s(x1))
   append(nil, ys)
   append(cons(x0, x1), ys)


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

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

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

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

(19) QDPSizeChangeProof (EQUIVALENT)
By using the subterm criterion [SUBTERM_CRITERION] together with the size-change analysis [AAECC05] we have proven that there are no infinite chains for this DP problem. 

From the DPs we obtained the following set of size-change graphs:
*GE(s(x), s(y)) -> GE(x, y)
The graph contains the following edges 1 > 1, 2 > 2


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

(20)
YES

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

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

   IF2(true, n, x, xs) -> FILTERHIGH(n, xs)
   FILTERHIGH(n, cons(x, xs)) -> IF2(ge(x, n), n, x, xs)
   IF2(false, n, x, xs) -> FILTERHIGH(n, xs)

The TRS R consists of the following rules:

   qsort(nil) -> nil
   qsort(cons(x, xs)) -> append(qsort(filterlow(x, cons(x, xs))), cons(x, qsort(filterhigh(x, cons(x, xs)))))
   filterlow(n, nil) -> nil
   filterlow(n, cons(x, xs)) -> if1(ge(n, x), n, x, xs)
   if1(true, n, x, xs) -> filterlow(n, xs)
   if1(false, n, x, xs) -> cons(x, filterlow(n, xs))
   filterhigh(n, nil) -> nil
   filterhigh(n, cons(x, xs)) -> if2(ge(x, n), n, x, xs)
   if2(true, n, x, xs) -> filterhigh(n, xs)
   if2(false, n, x, xs) -> cons(x, filterhigh(n, xs))
   ge(x, 0) -> true
   ge(0, s(x)) -> false
   ge(s(x), s(y)) -> ge(x, y)
   append(nil, ys) -> ys
   append(cons(x, xs), ys) -> cons(x, append(xs, ys))

The set Q consists of the following terms:

   qsort(nil)
   qsort(cons(x0, x1))
   filterlow(x0, nil)
   filterlow(x0, cons(x1, x2))
   if1(true, x0, x1, x2)
   if1(false, x0, x1, x2)
   filterhigh(x0, nil)
   filterhigh(x0, cons(x1, x2))
   if2(true, x0, x1, x2)
   if2(false, x0, x1, x2)
   ge(x0, 0)
   ge(0, s(x0))
   ge(s(x0), s(x1))
   append(nil, ys)
   append(cons(x0, x1), ys)

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:

   IF2(true, n, x, xs) -> FILTERHIGH(n, xs)
   FILTERHIGH(n, cons(x, xs)) -> IF2(ge(x, n), n, x, xs)
   IF2(false, n, x, xs) -> FILTERHIGH(n, xs)

The TRS R consists of the following rules:

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

The set Q consists of the following terms:

   qsort(nil)
   qsort(cons(x0, x1))
   filterlow(x0, nil)
   filterlow(x0, cons(x1, x2))
   if1(true, x0, x1, x2)
   if1(false, x0, x1, x2)
   filterhigh(x0, nil)
   filterhigh(x0, cons(x1, x2))
   if2(true, x0, x1, x2)
   if2(false, x0, x1, x2)
   ge(x0, 0)
   ge(0, s(x0))
   ge(s(x0), s(x1))
   append(nil, ys)
   append(cons(x0, x1), ys)

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

   qsort(nil)
   qsort(cons(x0, x1))
   filterlow(x0, nil)
   filterlow(x0, cons(x1, x2))
   if1(true, x0, x1, x2)
   if1(false, x0, x1, x2)
   filterhigh(x0, nil)
   filterhigh(x0, cons(x1, x2))
   if2(true, x0, x1, x2)
   if2(false, x0, x1, x2)
   append(nil, ys)
   append(cons(x0, x1), ys)


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

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

   IF2(true, n, x, xs) -> FILTERHIGH(n, xs)
   FILTERHIGH(n, cons(x, xs)) -> IF2(ge(x, n), n, x, xs)
   IF2(false, n, x, xs) -> FILTERHIGH(n, xs)

The TRS R consists of the following rules:

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

The set Q consists of the following terms:

   ge(x0, 0)
   ge(0, s(x0))
   ge(s(x0), s(x1))

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


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


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


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

(27)
YES

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

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

   IF1(true, n, x, xs) -> FILTERLOW(n, xs)
   FILTERLOW(n, cons(x, xs)) -> IF1(ge(n, x), n, x, xs)
   IF1(false, n, x, xs) -> FILTERLOW(n, xs)

The TRS R consists of the following rules:

   qsort(nil) -> nil
   qsort(cons(x, xs)) -> append(qsort(filterlow(x, cons(x, xs))), cons(x, qsort(filterhigh(x, cons(x, xs)))))
   filterlow(n, nil) -> nil
   filterlow(n, cons(x, xs)) -> if1(ge(n, x), n, x, xs)
   if1(true, n, x, xs) -> filterlow(n, xs)
   if1(false, n, x, xs) -> cons(x, filterlow(n, xs))
   filterhigh(n, nil) -> nil
   filterhigh(n, cons(x, xs)) -> if2(ge(x, n), n, x, xs)
   if2(true, n, x, xs) -> filterhigh(n, xs)
   if2(false, n, x, xs) -> cons(x, filterhigh(n, xs))
   ge(x, 0) -> true
   ge(0, s(x)) -> false
   ge(s(x), s(y)) -> ge(x, y)
   append(nil, ys) -> ys
   append(cons(x, xs), ys) -> cons(x, append(xs, ys))

The set Q consists of the following terms:

   qsort(nil)
   qsort(cons(x0, x1))
   filterlow(x0, nil)
   filterlow(x0, cons(x1, x2))
   if1(true, x0, x1, x2)
   if1(false, x0, x1, x2)
   filterhigh(x0, nil)
   filterhigh(x0, cons(x1, x2))
   if2(true, x0, x1, x2)
   if2(false, x0, x1, x2)
   ge(x0, 0)
   ge(0, s(x0))
   ge(s(x0), s(x1))
   append(nil, ys)
   append(cons(x0, x1), ys)

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:

   IF1(true, n, x, xs) -> FILTERLOW(n, xs)
   FILTERLOW(n, cons(x, xs)) -> IF1(ge(n, x), n, x, xs)
   IF1(false, n, x, xs) -> FILTERLOW(n, xs)

The TRS R consists of the following rules:

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

The set Q consists of the following terms:

   qsort(nil)
   qsort(cons(x0, x1))
   filterlow(x0, nil)
   filterlow(x0, cons(x1, x2))
   if1(true, x0, x1, x2)
   if1(false, x0, x1, x2)
   filterhigh(x0, nil)
   filterhigh(x0, cons(x1, x2))
   if2(true, x0, x1, x2)
   if2(false, x0, x1, x2)
   ge(x0, 0)
   ge(0, s(x0))
   ge(s(x0), s(x1))
   append(nil, ys)
   append(cons(x0, x1), ys)

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

   qsort(nil)
   qsort(cons(x0, x1))
   filterlow(x0, nil)
   filterlow(x0, cons(x1, x2))
   if1(true, x0, x1, x2)
   if1(false, x0, x1, x2)
   filterhigh(x0, nil)
   filterhigh(x0, cons(x1, x2))
   if2(true, x0, x1, x2)
   if2(false, x0, x1, x2)
   append(nil, ys)
   append(cons(x0, x1), ys)


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

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

   IF1(true, n, x, xs) -> FILTERLOW(n, xs)
   FILTERLOW(n, cons(x, xs)) -> IF1(ge(n, x), n, x, xs)
   IF1(false, n, x, xs) -> FILTERLOW(n, xs)

The TRS R consists of the following rules:

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

The set Q consists of the following terms:

   ge(x0, 0)
   ge(0, s(x0))
   ge(s(x0), s(x1))

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

(33) QDPSizeChangeProof (EQUIVALENT)
By using the subterm criterion [SUBTERM_CRITERION] together with the size-change analysis [AAECC05] we have proven that there are no infinite chains for this DP problem. 

From the DPs we obtained the following set of size-change graphs:
*FILTERLOW(n, cons(x, xs)) -> IF1(ge(n, x), n, x, xs)
The graph contains the following edges 1 >= 2, 2 > 3, 2 > 4


*IF1(true, n, x, xs) -> FILTERLOW(n, xs)
The graph contains the following edges 2 >= 1, 4 >= 2


*IF1(false, n, x, xs) -> FILTERLOW(n, xs)
The graph contains the following edges 2 >= 1, 4 >= 2


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

(34)
YES

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

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

   QSORT(cons(x, xs)) -> QSORT(filterhigh(x, cons(x, xs)))
   QSORT(cons(x, xs)) -> QSORT(filterlow(x, cons(x, xs)))

The TRS R consists of the following rules:

   qsort(nil) -> nil
   qsort(cons(x, xs)) -> append(qsort(filterlow(x, cons(x, xs))), cons(x, qsort(filterhigh(x, cons(x, xs)))))
   filterlow(n, nil) -> nil
   filterlow(n, cons(x, xs)) -> if1(ge(n, x), n, x, xs)
   if1(true, n, x, xs) -> filterlow(n, xs)
   if1(false, n, x, xs) -> cons(x, filterlow(n, xs))
   filterhigh(n, nil) -> nil
   filterhigh(n, cons(x, xs)) -> if2(ge(x, n), n, x, xs)
   if2(true, n, x, xs) -> filterhigh(n, xs)
   if2(false, n, x, xs) -> cons(x, filterhigh(n, xs))
   ge(x, 0) -> true
   ge(0, s(x)) -> false
   ge(s(x), s(y)) -> ge(x, y)
   append(nil, ys) -> ys
   append(cons(x, xs), ys) -> cons(x, append(xs, ys))

The set Q consists of the following terms:

   qsort(nil)
   qsort(cons(x0, x1))
   filterlow(x0, nil)
   filterlow(x0, cons(x1, x2))
   if1(true, x0, x1, x2)
   if1(false, x0, x1, x2)
   filterhigh(x0, nil)
   filterhigh(x0, cons(x1, x2))
   if2(true, x0, x1, x2)
   if2(false, x0, x1, x2)
   ge(x0, 0)
   ge(0, s(x0))
   ge(s(x0), s(x1))
   append(nil, ys)
   append(cons(x0, x1), ys)

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

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

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

   QSORT(cons(x, xs)) -> QSORT(filterhigh(x, cons(x, xs)))
   QSORT(cons(x, xs)) -> QSORT(filterlow(x, cons(x, xs)))

The TRS R consists of the following rules:

   filterlow(n, cons(x, xs)) -> if1(ge(n, x), n, x, xs)
   if1(true, n, x, xs) -> filterlow(n, xs)
   ge(x, 0) -> true
   ge(0, s(x)) -> false
   ge(s(x), s(y)) -> ge(x, y)
   if1(false, n, x, xs) -> cons(x, filterlow(n, xs))
   filterlow(n, nil) -> nil
   filterhigh(n, cons(x, xs)) -> if2(ge(x, n), n, x, xs)
   if2(true, n, x, xs) -> filterhigh(n, xs)
   if2(false, n, x, xs) -> cons(x, filterhigh(n, xs))
   filterhigh(n, nil) -> nil

The set Q consists of the following terms:

   qsort(nil)
   qsort(cons(x0, x1))
   filterlow(x0, nil)
   filterlow(x0, cons(x1, x2))
   if1(true, x0, x1, x2)
   if1(false, x0, x1, x2)
   filterhigh(x0, nil)
   filterhigh(x0, cons(x1, x2))
   if2(true, x0, x1, x2)
   if2(false, x0, x1, x2)
   ge(x0, 0)
   ge(0, s(x0))
   ge(s(x0), s(x1))
   append(nil, ys)
   append(cons(x0, x1), ys)

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

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

   qsort(nil)
   qsort(cons(x0, x1))
   append(nil, ys)
   append(cons(x0, x1), ys)


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

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

   QSORT(cons(x, xs)) -> QSORT(filterhigh(x, cons(x, xs)))
   QSORT(cons(x, xs)) -> QSORT(filterlow(x, cons(x, xs)))

The TRS R consists of the following rules:

   filterlow(n, cons(x, xs)) -> if1(ge(n, x), n, x, xs)
   if1(true, n, x, xs) -> filterlow(n, xs)
   ge(x, 0) -> true
   ge(0, s(x)) -> false
   ge(s(x), s(y)) -> ge(x, y)
   if1(false, n, x, xs) -> cons(x, filterlow(n, xs))
   filterlow(n, nil) -> nil
   filterhigh(n, cons(x, xs)) -> if2(ge(x, n), n, x, xs)
   if2(true, n, x, xs) -> filterhigh(n, xs)
   if2(false, n, x, xs) -> cons(x, filterhigh(n, xs))
   filterhigh(n, nil) -> nil

The set Q consists of the following terms:

   filterlow(x0, nil)
   filterlow(x0, cons(x1, x2))
   if1(true, x0, x1, x2)
   if1(false, x0, x1, x2)
   filterhigh(x0, nil)
   filterhigh(x0, cons(x1, x2))
   if2(true, x0, x1, x2)
   if2(false, x0, x1, x2)
   ge(x0, 0)
   ge(0, s(x0))
   ge(s(x0), s(x1))

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

(40) TransformationProof (EQUIVALENT)
By rewriting [LPAR04] the rule QSORT(cons(x, xs)) -> QSORT(filterhigh(x, cons(x, xs))) at position [0] we obtained the following new rules [LPAR04]:

   (QSORT(cons(x, xs)) -> QSORT(if2(ge(x, x), x, x, xs)),QSORT(cons(x, xs)) -> QSORT(if2(ge(x, x), x, x, xs)))


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

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

   QSORT(cons(x, xs)) -> QSORT(filterlow(x, cons(x, xs)))
   QSORT(cons(x, xs)) -> QSORT(if2(ge(x, x), x, x, xs))

The TRS R consists of the following rules:

   filterlow(n, cons(x, xs)) -> if1(ge(n, x), n, x, xs)
   if1(true, n, x, xs) -> filterlow(n, xs)
   ge(x, 0) -> true
   ge(0, s(x)) -> false
   ge(s(x), s(y)) -> ge(x, y)
   if1(false, n, x, xs) -> cons(x, filterlow(n, xs))
   filterlow(n, nil) -> nil
   filterhigh(n, cons(x, xs)) -> if2(ge(x, n), n, x, xs)
   if2(true, n, x, xs) -> filterhigh(n, xs)
   if2(false, n, x, xs) -> cons(x, filterhigh(n, xs))
   filterhigh(n, nil) -> nil

The set Q consists of the following terms:

   filterlow(x0, nil)
   filterlow(x0, cons(x1, x2))
   if1(true, x0, x1, x2)
   if1(false, x0, x1, x2)
   filterhigh(x0, nil)
   filterhigh(x0, cons(x1, x2))
   if2(true, x0, x1, x2)
   if2(false, x0, x1, x2)
   ge(x0, 0)
   ge(0, s(x0))
   ge(s(x0), s(x1))

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

(42) TransformationProof (EQUIVALENT)
By rewriting [LPAR04] the rule QSORT(cons(x, xs)) -> QSORT(filterlow(x, cons(x, xs))) at position [0] we obtained the following new rules [LPAR04]:

   (QSORT(cons(x, xs)) -> QSORT(if1(ge(x, x), x, x, xs)),QSORT(cons(x, xs)) -> QSORT(if1(ge(x, x), x, x, xs)))


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

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

   QSORT(cons(x, xs)) -> QSORT(if2(ge(x, x), x, x, xs))
   QSORT(cons(x, xs)) -> QSORT(if1(ge(x, x), x, x, xs))

The TRS R consists of the following rules:

   filterlow(n, cons(x, xs)) -> if1(ge(n, x), n, x, xs)
   if1(true, n, x, xs) -> filterlow(n, xs)
   ge(x, 0) -> true
   ge(0, s(x)) -> false
   ge(s(x), s(y)) -> ge(x, y)
   if1(false, n, x, xs) -> cons(x, filterlow(n, xs))
   filterlow(n, nil) -> nil
   filterhigh(n, cons(x, xs)) -> if2(ge(x, n), n, x, xs)
   if2(true, n, x, xs) -> filterhigh(n, xs)
   if2(false, n, x, xs) -> cons(x, filterhigh(n, xs))
   filterhigh(n, nil) -> nil

The set Q consists of the following terms:

   filterlow(x0, nil)
   filterlow(x0, cons(x1, x2))
   if1(true, x0, x1, x2)
   if1(false, x0, x1, x2)
   filterhigh(x0, nil)
   filterhigh(x0, cons(x1, x2))
   if2(true, x0, x1, x2)
   if2(false, x0, x1, x2)
   ge(x0, 0)
   ge(0, s(x0))
   ge(s(x0), s(x1))

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

(44) Induction-Processor (SOUND)

This DP could be deleted by the Induction-Processor:
QSORT(cons(x, xs)) -> QSORT(if2(ge(x, x), x, x, xs))


This order was computed:
Polynomial interpretation [POLO]:

   POL(0) = 1
   POL(QSORT(x_1)) = x_1
   POL(cons(x_1, x_2)) = 1 + x_1 + x_2
   POL(false_renamed) = 0
   POL(filterhigh(x_1, x_2)) = x_2
   POL(filterlow(x_1, x_2)) = x_2
   POL(ge(x_1, x_2)) = 0
   POL(if1(x_1, x_2, x_3, x_4)) = 1 + x_1 + x_3 + x_4
   POL(if2(x_1, x_2, x_3, x_4)) = 1 + x_1 + x_3 + x_4
   POL(nil) = 1
   POL(s(x_1)) = 1 + x_1
   POL(true_renamed) = 0

At least one of these decreasing rules is always used after the deleted DP:
if2(true_renamed, n1, x5, xs2) -> filterhigh(n1, xs2)


The following formula is valid:
x:sort[a0],xs:sort[a2].if2'(ge(x, x), x, x, xs)=true


The transformed set:
if2'(true_renamed, n1, x5, xs2) -> true
if2'(false_renamed, n2, x6, xs3) -> filterhigh'(n2, xs3)
filterhigh'(n3, nil) -> false
filterhigh'(n5, cons(x8, xs5)) -> if2'(ge(x8, n5), n5, x8, xs5)
if1(true_renamed, n, x'', xs'') -> filterlow(n, xs'')
ge(x1, 0) -> true_renamed
ge(0, s(x2)) -> false_renamed
ge(s(x3), s(y)) -> ge(x3, y)
if1(false_renamed, n', x4, xs1) -> cons(x4, filterlow(n', xs1))
filterlow(n'', nil) -> nil
if2(true_renamed, n1, x5, xs2) -> filterhigh(n1, xs2)
if2(false_renamed, n2, x6, xs3) -> cons(x6, filterhigh(n2, xs3))
filterhigh(n3, nil) -> nil
filterlow(n4, cons(x7, xs4)) -> if1(ge(n4, x7), n4, x7, xs4)
filterhigh(n5, cons(x8, xs5)) -> if2(ge(x8, n5), n5, x8, xs5)
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(v21)) -> false
equal_sort[a0](s(v22), 0) -> false
equal_sort[a0](s(v22), s(v23)) -> equal_sort[a0](v22, v23)
equal_sort[a2](cons(v24, v25), cons(v26, v27)) -> and(equal_sort[a0](v24, v26), equal_sort[a2](v25, v27))
equal_sort[a2](cons(v24, v25), nil) -> false
equal_sort[a2](nil, cons(v28, v29)) -> false
equal_sort[a2](nil, nil) -> true
equal_sort[a33](true_renamed, true_renamed) -> true
equal_sort[a33](true_renamed, false_renamed) -> false
equal_sort[a33](false_renamed, true_renamed) -> false
equal_sort[a33](false_renamed, false_renamed) -> true
equal_sort[a57](witness_sort[a57], witness_sort[a57]) -> true


The proof given by the theorem prover:
The following output was given by the internal theorem prover:proof of internal
# AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty


Partial correctness of the following Program

   [x, v21, v22, v23, v24, v25, v26, v27, v28, v29, n1, x5, xs2, n2, x6, x8, xs5, n3, n5, x1, x2, x3, y, n'', n4, x7, xs4, n, x'', n', x4]
   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(v21)) -> false
   equal_sort[a0](s(v22), 0) -> false
   equal_sort[a0](s(v22), s(v23)) -> equal_sort[a0](v22, v23)
   equal_sort[a2](cons(v24, v25), cons(v26, v27)) -> equal_sort[a0](v24, v26) and equal_sort[a2](v25, v27)
   equal_sort[a2](cons(v24, v25), nil) -> false
   equal_sort[a2](nil, cons(v28, v29)) -> false
   equal_sort[a2](nil, nil) -> true
   equal_sort[a33](true_renamed, true_renamed) -> true
   equal_sort[a33](true_renamed, false_renamed) -> false
   equal_sort[a33](false_renamed, true_renamed) -> false
   equal_sort[a33](false_renamed, false_renamed) -> true
   equal_sort[a57](witness_sort[a57], witness_sort[a57]) -> true
   if2'(true_renamed, n1, x5, xs2) -> true
   if2'(false_renamed, n2, x6, nil) -> false
   if2'(false_renamed, n2, x6, cons(x8, xs5)) -> if2'(ge(x8, n2), n2, x8, xs5)
   filterhigh'(n3, nil) -> false
   equal_sort[a33](ge(x8, n5), true_renamed) -> true | filterhigh'(n5, cons(x8, xs5)) -> true
   equal_sort[a33](ge(x8, n5), true_renamed) -> false | filterhigh'(n5, cons(x8, xs5)) -> filterhigh'(n5, xs5)
   ge(x1, 0) -> true_renamed
   ge(0, s(x2)) -> false_renamed
   ge(s(x3), s(y)) -> ge(x3, y)
   filterlow(n'', nil) -> nil
   equal_sort[a33](ge(n4, x7), true_renamed) -> true | filterlow(n4, cons(x7, xs4)) -> filterlow(n4, xs4)
   equal_sort[a33](ge(n4, x7), true_renamed) -> false | filterlow(n4, cons(x7, xs4)) -> cons(x7, filterlow(n4, xs4))
   filterhigh(n3, nil) -> nil
   equal_sort[a33](ge(x8, n5), true_renamed) -> true | filterhigh(n5, cons(x8, xs5)) -> filterhigh(n5, xs5)
   equal_sort[a33](ge(x8, n5), true_renamed) -> false | filterhigh(n5, cons(x8, xs5)) -> cons(x8, filterhigh(n5, xs5))
   if1(true_renamed, n, x'', nil) -> nil
   if1(true_renamed, n, x'', cons(x7, xs4)) -> if1(ge(n, x7), n, x7, xs4)
   if1(false_renamed, n', x4, nil) -> cons(x4, nil)
   if1(false_renamed, n', x4, cons(x7, xs4)) -> cons(x4, if1(ge(n', x7), n', x7, xs4))
   if2(true_renamed, n1, x5, nil) -> nil
   if2(true_renamed, n1, x5, cons(x8, xs5)) -> if2(ge(x8, n1), n1, x8, xs5)
   if2(false_renamed, n2, x6, nil) -> cons(x6, nil)
   if2(false_renamed, n2, x6, cons(x8, xs5)) -> cons(x6, if2(ge(x8, n2), n2, x8, xs5))

using the following formula:
x:sort[a0],xs:sort[a2].if2'(ge(x, x), x, x, xs)=true

could be successfully shown:
(0) Formula
(1) Induction by data structure [EQUIVALENT, 0 ms]
(2) AND
    (3) Formula
        (4) Symbolic evaluation [EQUIVALENT, 0 ms]
        (5) YES
    (6) Formula
        (7) Symbolic evaluation [EQUIVALENT, 0 ms]
        (8) Formula
        (9) Case Analysis [EQUIVALENT, 0 ms]
        (10) AND
            (11) Formula
                (12) Inverse Substitution [SOUND, 0 ms]
                (13) Formula
                (14) Induction by data structure [SOUND, 0 ms]
                (15) AND
                    (16) Formula
                        (17) Symbolic evaluation [EQUIVALENT, 0 ms]
                        (18) YES
                    (19) Formula
                        (20) Symbolic evaluation under hypothesis [EQUIVALENT, 0 ms]
                        (21) YES
            (22) Formula
                (23) Inverse Substitution [SOUND, 0 ms]
                (24) Formula
                (25) Induction by data structure [SOUND, 0 ms]
                (26) AND
                    (27) Formula
                        (28) Symbolic evaluation [EQUIVALENT, 0 ms]
                        (29) YES
                    (30) Formula
                        (31) Symbolic evaluation under hypothesis [EQUIVALENT, 0 ms]
                        (32) YES


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

(0)
Obligation:
Formula:
x:sort[a0],xs:sort[a2].if2'(ge(x, x), x, x, xs)=true

There are no hypotheses.




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

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



1. Base Case:
Formula:
xs:sort[a2].if2'(ge(0, 0), 0, 0, xs)=true

There are no hypotheses.





1. Step Case:
Formula:
n:sort[a0],xs:sort[a2].if2'(ge(s(n), s(n)), s(n), s(n), xs)=true

Hypotheses:
n:sort[a0],!xs:sort[a2].if2'(ge(n, n), n, n, xs)=true






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

(2)
Complex Obligation (AND)

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

(3)
Obligation:
Formula:
xs:sort[a2].if2'(ge(0, 0), 0, 0, xs)=true

There are no hypotheses.




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

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

(5)
YES

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

(6)
Obligation:
Formula:
n:sort[a0],xs:sort[a2].if2'(ge(s(n), s(n)), s(n), s(n), xs)=true

Hypotheses:
n:sort[a0],!xs:sort[a2].if2'(ge(n, n), n, n, xs)=true




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

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

(8)
Obligation:
Formula:
n:sort[a0],xs:sort[a2].if2'(ge(n, n), s(n), s(n), xs)=true

Hypotheses:
n:sort[a0],!xs:sort[a2].if2'(ge(n, n), n, n, xs)=true




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

(9) Case Analysis (EQUIVALENT)
Case analysis leads to the following new obligations:

Formula:
n:sort[a0],x_1:sort[a0],x_2:sort[a2].if2'(ge(n, n), s(n), s(n), cons(x_1, x_2))=true

Hypotheses:
n:sort[a0],!xs:sort[a2].if2'(ge(n, n), n, n, xs)=true





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

Hypotheses:
n:sort[a0],!xs:sort[a2].if2'(ge(n, n), n, n, xs)=true






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

(10)
Complex Obligation (AND)

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

(11)
Obligation:
Formula:
n:sort[a0],x_1:sort[a0],x_2:sort[a2].if2'(ge(n, n), s(n), s(n), cons(x_1, x_2))=true

Hypotheses:
n:sort[a0],!xs:sort[a2].if2'(ge(n, n), n, n, xs)=true




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

(12) Inverse Substitution (SOUND)
The formula could be generalised by inverse substitution to:
n:sort[a0],n':sort[a0],x_1:sort[a0],x_2:sort[a2].if2'(ge(n, n), n', n', cons(x_1, x_2))=true

Inverse substitution used:
[s(n)/n']


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

(13)
Obligation:
Formula:
n:sort[a0],n':sort[a0],x_1:sort[a0],x_2:sort[a2].if2'(ge(n, n), n', n', cons(x_1, x_2))=true

Hypotheses:
n:sort[a0],!xs:sort[a2].if2'(ge(n, n), n, n, xs)=true




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

(14) Induction by data structure (SOUND)
Induction by data structure sort[a0] generates the following cases:



1. Base Case:
Formula:
n':sort[a0],x_1:sort[a0],x_2:sort[a2].if2'(ge(0, 0), n', n', cons(x_1, x_2))=true

There are no hypotheses.





1. Step Case:
Formula:
n'':sort[a0],n':sort[a0],x_1:sort[a0],x_2:sort[a2].if2'(ge(s(n''), s(n'')), n', n', cons(x_1, x_2))=true

Hypotheses:
n'':sort[a0],!n':sort[a0],!x_1:sort[a0],!x_2:sort[a2].if2'(ge(n'', n''), n', n', cons(x_1, x_2))=true






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

(15)
Complex Obligation (AND)

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

(16)
Obligation:
Formula:
n':sort[a0],x_1:sort[a0],x_2:sort[a2].if2'(ge(0, 0), n', n', cons(x_1, x_2))=true

There are no hypotheses.




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

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

(18)
YES

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

(19)
Obligation:
Formula:
n'':sort[a0],n':sort[a0],x_1:sort[a0],x_2:sort[a2].if2'(ge(s(n''), s(n'')), n', n', cons(x_1, x_2))=true

Hypotheses:
n'':sort[a0],!n':sort[a0],!x_1:sort[a0],!x_2:sort[a2].if2'(ge(n'', n''), n', n', cons(x_1, x_2))=true




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

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

n'':sort[a0],!n':sort[a0],!x_1:sort[a0],!x_2:sort[a2].if2'(ge(n'', n''), n', n', cons(x_1, x_2))=true

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

(21)
YES

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

(22)
Obligation:
Formula:
n:sort[a0].if2'(ge(n, n), s(n), s(n), nil)=true

Hypotheses:
n:sort[a0],!xs:sort[a2].if2'(ge(n, n), n, n, xs)=true




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

(23) Inverse Substitution (SOUND)
The formula could be generalised by inverse substitution to:
n:sort[a0],n':sort[a0].if2'(ge(n, n), n', n', nil)=true

Inverse substitution used:
[s(n)/n']


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

(24)
Obligation:
Formula:
n:sort[a0],n':sort[a0].if2'(ge(n, n), n', n', nil)=true

Hypotheses:
n:sort[a0],!xs:sort[a2].if2'(ge(n, n), n, n, xs)=true




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

(25) Induction by data structure (SOUND)
Induction by data structure sort[a0] generates the following cases:



1. Base Case:
Formula:
n':sort[a0].if2'(ge(0, 0), n', n', nil)=true

There are no hypotheses.





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

Hypotheses:
n'':sort[a0],!n':sort[a0].if2'(ge(n'', n''), n', n', nil)=true






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

(26)
Complex Obligation (AND)

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

(27)
Obligation:
Formula:
n':sort[a0].if2'(ge(0, 0), n', n', nil)=true

There are no hypotheses.




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

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

(29)
YES

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

(30)
Obligation:
Formula:
n'':sort[a0],n':sort[a0].if2'(ge(s(n''), s(n'')), n', n', nil)=true

Hypotheses:
n'':sort[a0],!n':sort[a0].if2'(ge(n'', n''), n', n', nil)=true




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

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

n'':sort[a0],!n':sort[a0].if2'(ge(n'', n''), n', n', nil)=true

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

(32)
YES

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

(45)
Complex Obligation (AND)

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

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

   QSORT(cons(x, xs)) -> QSORT(if1(ge(x, x), x, x, xs))

The TRS R consists of the following rules:

   filterlow(n, cons(x, xs)) -> if1(ge(n, x), n, x, xs)
   if1(true, n, x, xs) -> filterlow(n, xs)
   ge(x, 0) -> true
   ge(0, s(x)) -> false
   ge(s(x), s(y)) -> ge(x, y)
   if1(false, n, x, xs) -> cons(x, filterlow(n, xs))
   filterlow(n, nil) -> nil
   filterhigh(n, cons(x, xs)) -> if2(ge(x, n), n, x, xs)
   if2(true, n, x, xs) -> filterhigh(n, xs)
   if2(false, n, x, xs) -> cons(x, filterhigh(n, xs))
   filterhigh(n, nil) -> nil

The set Q consists of the following terms:

   filterlow(x0, nil)
   filterlow(x0, cons(x1, x2))
   if1(true, x0, x1, x2)
   if1(false, x0, x1, x2)
   filterhigh(x0, nil)
   filterhigh(x0, cons(x1, x2))
   if2(true, x0, x1, x2)
   if2(false, x0, x1, x2)
   ge(x0, 0)
   ge(0, s(x0))
   ge(s(x0), s(x1))

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

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

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

   QSORT(cons(x, xs)) -> QSORT(if1(ge(x, x), x, x, xs))

The TRS R consists of the following rules:

   ge(x, 0) -> true
   ge(s(x), s(y)) -> ge(x, y)
   if1(true, n, x, xs) -> filterlow(n, xs)
   filterlow(n, cons(x, xs)) -> if1(ge(n, x), n, x, xs)
   if1(false, n, x, xs) -> cons(x, filterlow(n, xs))
   filterlow(n, nil) -> nil
   ge(0, s(x)) -> false

The set Q consists of the following terms:

   filterlow(x0, nil)
   filterlow(x0, cons(x1, x2))
   if1(true, x0, x1, x2)
   if1(false, x0, x1, x2)
   filterhigh(x0, nil)
   filterhigh(x0, cons(x1, x2))
   if2(true, x0, x1, x2)
   if2(false, x0, x1, x2)
   ge(x0, 0)
   ge(0, s(x0))
   ge(s(x0), s(x1))

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

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

   filterhigh(x0, nil)
   filterhigh(x0, cons(x1, x2))
   if2(true, x0, x1, x2)
   if2(false, x0, x1, x2)


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

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

   QSORT(cons(x, xs)) -> QSORT(if1(ge(x, x), x, x, xs))

The TRS R consists of the following rules:

   ge(x, 0) -> true
   ge(s(x), s(y)) -> ge(x, y)
   if1(true, n, x, xs) -> filterlow(n, xs)
   filterlow(n, cons(x, xs)) -> if1(ge(n, x), n, x, xs)
   if1(false, n, x, xs) -> cons(x, filterlow(n, xs))
   filterlow(n, nil) -> nil
   ge(0, s(x)) -> false

The set Q consists of the following terms:

   filterlow(x0, nil)
   filterlow(x0, cons(x1, x2))
   if1(true, x0, x1, x2)
   if1(false, x0, x1, x2)
   ge(x0, 0)
   ge(0, s(x0))
   ge(s(x0), s(x1))

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

(51) Induction-Processor (SOUND)

This DP could be deleted by the Induction-Processor:
QSORT(cons(x, xs)) -> QSORT(if1(ge(x, x), x, x, xs))


This order was computed:
Polynomial interpretation [POLO]:

   POL(0) = 1
   POL(QSORT(x_1)) = x_1
   POL(cons(x_1, x_2)) = 1 + x_1 + x_2
   POL(false_renamed) = 1
   POL(filterlow(x_1, x_2)) = x_2
   POL(ge(x_1, x_2)) = 1 + x_1 + x_2
   POL(if1(x_1, x_2, x_3, x_4)) = 1 + x_3 + x_4
   POL(nil) = 1
   POL(s(x_1)) = 1 + x_1
   POL(true_renamed) = 1

At least one of these decreasing rules is always used after the deleted DP:
if1(true_renamed, n, x1, xs') -> filterlow(n, xs')


The following formula is valid:
x:sort[a0],xs:sort[a5].if1'(ge(x, x), x, x, xs)=true


The transformed set:
if1'(true_renamed, n, x1, xs') -> true
filterlow'(n', cons(x2, xs'')) -> if1'(ge(n', x2), n', x2, xs'')
if1'(false_renamed, n'', x3, xs1) -> filterlow'(n'', xs1)
filterlow'(n1, nil) -> false
ge(x', 0) -> true_renamed
ge(s(x''), s(y)) -> ge(x'', y)
if1(true_renamed, n, x1, xs') -> filterlow(n, xs')
filterlow(n', cons(x2, xs'')) -> if1(ge(n', x2), n', x2, xs'')
if1(false_renamed, n'', x3, xs1) -> cons(x3, filterlow(n'', xs1))
filterlow(n1, nil) -> nil
ge(0, s(x4)) -> false_renamed
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(v13)) -> false
equal_sort[a0](s(v14), 0) -> false
equal_sort[a0](s(v14), s(v15)) -> equal_sort[a0](v14, v15)
equal_sort[a5](cons(v16, v17), cons(v18, v19)) -> and(equal_sort[a0](v16, v18), equal_sort[a5](v17, v19))
equal_sort[a5](cons(v16, v17), nil) -> false
equal_sort[a5](nil, cons(v20, v21)) -> false
equal_sort[a5](nil, nil) -> true
equal_sort[a18](true_renamed, true_renamed) -> true
equal_sort[a18](true_renamed, false_renamed) -> false
equal_sort[a18](false_renamed, true_renamed) -> false
equal_sort[a18](false_renamed, false_renamed) -> true
equal_sort[a37](witness_sort[a37], witness_sort[a37]) -> true


The proof given by the theorem prover:
The following output was given by the internal theorem prover:proof of internal
# AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty


Partial correctness of the following Program

   [x, v13, v14, v15, v16, v17, v18, v19, v20, v21, n, x1, xs', n'', x3, x2, xs'', n1, n', x', x'', y, x4]
   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(v13)) -> false
   equal_sort[a0](s(v14), 0) -> false
   equal_sort[a0](s(v14), s(v15)) -> equal_sort[a0](v14, v15)
   equal_sort[a5](cons(v16, v17), cons(v18, v19)) -> equal_sort[a0](v16, v18) and equal_sort[a5](v17, v19)
   equal_sort[a5](cons(v16, v17), nil) -> false
   equal_sort[a5](nil, cons(v20, v21)) -> false
   equal_sort[a5](nil, nil) -> true
   equal_sort[a18](true_renamed, true_renamed) -> true
   equal_sort[a18](true_renamed, false_renamed) -> false
   equal_sort[a18](false_renamed, true_renamed) -> false
   equal_sort[a18](false_renamed, false_renamed) -> true
   equal_sort[a37](witness_sort[a37], witness_sort[a37]) -> true
   if1'(true_renamed, n, x1, xs') -> true
   if1'(false_renamed, n'', x3, cons(x2, xs'')) -> if1'(ge(n'', x2), n'', x2, xs'')
   if1'(false_renamed, n'', x3, nil) -> false
   filterlow'(n1, nil) -> false
   equal_sort[a18](ge(n', x2), true_renamed) -> true | filterlow'(n', cons(x2, xs'')) -> true
   equal_sort[a18](ge(n', x2), true_renamed) -> false | filterlow'(n', cons(x2, xs'')) -> filterlow'(n', xs'')
   ge(x', 0) -> true_renamed
   ge(s(x''), s(y)) -> ge(x'', y)
   ge(0, s(x4)) -> false_renamed
   filterlow(n1, nil) -> nil
   equal_sort[a18](ge(n', x2), true_renamed) -> true | filterlow(n', cons(x2, xs'')) -> filterlow(n', xs'')
   equal_sort[a18](ge(n', x2), true_renamed) -> false | filterlow(n', cons(x2, xs'')) -> cons(x2, filterlow(n', xs''))
   if1(true_renamed, n, x1, cons(x2, xs'')) -> if1(ge(n, x2), n, x2, xs'')
   if1(true_renamed, n, x1, nil) -> nil
   if1(false_renamed, n'', x3, cons(x2, xs'')) -> cons(x3, if1(ge(n'', x2), n'', x2, xs''))
   if1(false_renamed, n'', x3, nil) -> cons(x3, nil)

using the following formula:
x:sort[a0],xs:sort[a5].if1'(ge(x, x), x, x, xs)=true

could be successfully shown:
(0) Formula
(1) Induction by data structure [EQUIVALENT, 0 ms]
(2) AND
    (3) Formula
        (4) Symbolic evaluation [EQUIVALENT, 0 ms]
        (5) YES
    (6) Formula
        (7) Symbolic evaluation [EQUIVALENT, 0 ms]
        (8) Formula
        (9) Case Analysis [EQUIVALENT, 0 ms]
        (10) AND
            (11) Formula
                (12) Inverse Substitution [SOUND, 0 ms]
                (13) Formula
                (14) Induction by data structure [SOUND, 0 ms]
                (15) AND
                    (16) Formula
                        (17) Symbolic evaluation [EQUIVALENT, 0 ms]
                        (18) YES
                    (19) Formula
                        (20) Symbolic evaluation under hypothesis [EQUIVALENT, 0 ms]
                        (21) YES
            (22) Formula
                (23) Inverse Substitution [SOUND, 0 ms]
                (24) Formula
                (25) Induction by data structure [SOUND, 0 ms]
                (26) AND
                    (27) Formula
                        (28) Symbolic evaluation [EQUIVALENT, 0 ms]
                        (29) YES
                    (30) Formula
                        (31) Symbolic evaluation under hypothesis [EQUIVALENT, 0 ms]
                        (32) YES


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

(0)
Obligation:
Formula:
x:sort[a0],xs:sort[a5].if1'(ge(x, x), x, x, xs)=true

There are no hypotheses.




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

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



1. Base Case:
Formula:
xs:sort[a5].if1'(ge(0, 0), 0, 0, xs)=true

There are no hypotheses.





1. Step Case:
Formula:
n:sort[a0],xs:sort[a5].if1'(ge(s(n), s(n)), s(n), s(n), xs)=true

Hypotheses:
n:sort[a0],!xs:sort[a5].if1'(ge(n, n), n, n, xs)=true






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

(2)
Complex Obligation (AND)

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

(3)
Obligation:
Formula:
xs:sort[a5].if1'(ge(0, 0), 0, 0, xs)=true

There are no hypotheses.




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

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

(5)
YES

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

(6)
Obligation:
Formula:
n:sort[a0],xs:sort[a5].if1'(ge(s(n), s(n)), s(n), s(n), xs)=true

Hypotheses:
n:sort[a0],!xs:sort[a5].if1'(ge(n, n), n, n, xs)=true




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

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

(8)
Obligation:
Formula:
n:sort[a0],xs:sort[a5].if1'(ge(n, n), s(n), s(n), xs)=true

Hypotheses:
n:sort[a0],!xs:sort[a5].if1'(ge(n, n), n, n, xs)=true




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

(9) Case Analysis (EQUIVALENT)
Case analysis leads to the following new obligations:

Formula:
n:sort[a0],x_1:sort[a0],x_2:sort[a5].if1'(ge(n, n), s(n), s(n), cons(x_1, x_2))=true

Hypotheses:
n:sort[a0],!xs:sort[a5].if1'(ge(n, n), n, n, xs)=true





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

Hypotheses:
n:sort[a0],!xs:sort[a5].if1'(ge(n, n), n, n, xs)=true






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

(10)
Complex Obligation (AND)

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

(11)
Obligation:
Formula:
n:sort[a0],x_1:sort[a0],x_2:sort[a5].if1'(ge(n, n), s(n), s(n), cons(x_1, x_2))=true

Hypotheses:
n:sort[a0],!xs:sort[a5].if1'(ge(n, n), n, n, xs)=true




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

(12) Inverse Substitution (SOUND)
The formula could be generalised by inverse substitution to:
n:sort[a0],n':sort[a0],x_1:sort[a0],x_2:sort[a5].if1'(ge(n, n), n', n', cons(x_1, x_2))=true

Inverse substitution used:
[s(n)/n']


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

(13)
Obligation:
Formula:
n:sort[a0],n':sort[a0],x_1:sort[a0],x_2:sort[a5].if1'(ge(n, n), n', n', cons(x_1, x_2))=true

Hypotheses:
n:sort[a0],!xs:sort[a5].if1'(ge(n, n), n, n, xs)=true




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

(14) Induction by data structure (SOUND)
Induction by data structure sort[a0] generates the following cases:



1. Base Case:
Formula:
n':sort[a0],x_1:sort[a0],x_2:sort[a5].if1'(ge(0, 0), n', n', cons(x_1, x_2))=true

There are no hypotheses.





1. Step Case:
Formula:
n'':sort[a0],n':sort[a0],x_1:sort[a0],x_2:sort[a5].if1'(ge(s(n''), s(n'')), n', n', cons(x_1, x_2))=true

Hypotheses:
n'':sort[a0],!n':sort[a0],!x_1:sort[a0],!x_2:sort[a5].if1'(ge(n'', n''), n', n', cons(x_1, x_2))=true






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

(15)
Complex Obligation (AND)

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

(16)
Obligation:
Formula:
n':sort[a0],x_1:sort[a0],x_2:sort[a5].if1'(ge(0, 0), n', n', cons(x_1, x_2))=true

There are no hypotheses.




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

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

(18)
YES

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

(19)
Obligation:
Formula:
n'':sort[a0],n':sort[a0],x_1:sort[a0],x_2:sort[a5].if1'(ge(s(n''), s(n'')), n', n', cons(x_1, x_2))=true

Hypotheses:
n'':sort[a0],!n':sort[a0],!x_1:sort[a0],!x_2:sort[a5].if1'(ge(n'', n''), n', n', cons(x_1, x_2))=true




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

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

n'':sort[a0],!n':sort[a0],!x_1:sort[a0],!x_2:sort[a5].if1'(ge(n'', n''), n', n', cons(x_1, x_2))=true

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

(21)
YES

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

(22)
Obligation:
Formula:
n:sort[a0].if1'(ge(n, n), s(n), s(n), nil)=true

Hypotheses:
n:sort[a0],!xs:sort[a5].if1'(ge(n, n), n, n, xs)=true




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

(23) Inverse Substitution (SOUND)
The formula could be generalised by inverse substitution to:
n:sort[a0],n':sort[a0].if1'(ge(n, n), n', n', nil)=true

Inverse substitution used:
[s(n)/n']


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

(24)
Obligation:
Formula:
n:sort[a0],n':sort[a0].if1'(ge(n, n), n', n', nil)=true

Hypotheses:
n:sort[a0],!xs:sort[a5].if1'(ge(n, n), n, n, xs)=true




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

(25) Induction by data structure (SOUND)
Induction by data structure sort[a0] generates the following cases:



1. Base Case:
Formula:
n':sort[a0].if1'(ge(0, 0), n', n', nil)=true

There are no hypotheses.





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

Hypotheses:
n'':sort[a0],!n':sort[a0].if1'(ge(n'', n''), n', n', nil)=true






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

(26)
Complex Obligation (AND)

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

(27)
Obligation:
Formula:
n':sort[a0].if1'(ge(0, 0), n', n', nil)=true

There are no hypotheses.




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

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

(29)
YES

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

(30)
Obligation:
Formula:
n'':sort[a0],n':sort[a0].if1'(ge(s(n''), s(n'')), n', n', nil)=true

Hypotheses:
n'':sort[a0],!n':sort[a0].if1'(ge(n'', n''), n', n', nil)=true




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

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

n'':sort[a0],!n':sort[a0].if1'(ge(n'', n''), n', n', nil)=true

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

(32)
YES

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

(52)
Complex Obligation (AND)

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

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

   ge(x, 0) -> true
   ge(s(x), s(y)) -> ge(x, y)
   if1(true, n, x, xs) -> filterlow(n, xs)
   filterlow(n, cons(x, xs)) -> if1(ge(n, x), n, x, xs)
   if1(false, n, x, xs) -> cons(x, filterlow(n, xs))
   filterlow(n, nil) -> nil
   ge(0, s(x)) -> false

The set Q consists of the following terms:

   filterlow(x0, nil)
   filterlow(x0, cons(x1, x2))
   if1(true, x0, x1, x2)
   if1(false, x0, x1, x2)
   ge(x0, 0)
   ge(0, s(x0))
   ge(s(x0), s(x1))

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

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

(55)
YES

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

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

   if1'(true_renamed, n, x1, xs') -> true
   filterlow'(n', cons(x2, xs'')) -> if1'(ge(n', x2), n', x2, xs'')
   if1'(false_renamed, n'', x3, xs1) -> filterlow'(n'', xs1)
   filterlow'(n1, nil) -> false
   ge(x', 0) -> true_renamed
   ge(s(x''), s(y)) -> ge(x'', y)
   if1(true_renamed, n, x1, xs') -> filterlow(n, xs')
   filterlow(n', cons(x2, xs'')) -> if1(ge(n', x2), n', x2, xs'')
   if1(false_renamed, n'', x3, xs1) -> cons(x3, filterlow(n'', xs1))
   filterlow(n1, nil) -> nil
   ge(0, s(x4)) -> false_renamed
   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(v13)) -> false
   equal_sort[a0](s(v14), 0) -> false
   equal_sort[a0](s(v14), s(v15)) -> equal_sort[a0](v14, v15)
   equal_sort[a5](cons(v16, v17), cons(v18, v19)) -> and(equal_sort[a0](v16, v18), equal_sort[a5](v17, v19))
   equal_sort[a5](cons(v16, v17), nil) -> false
   equal_sort[a5](nil, cons(v20, v21)) -> false
   equal_sort[a5](nil, nil) -> true
   equal_sort[a18](true_renamed, true_renamed) -> true
   equal_sort[a18](true_renamed, false_renamed) -> false
   equal_sort[a18](false_renamed, true_renamed) -> false
   equal_sort[a18](false_renamed, false_renamed) -> true
   equal_sort[a37](witness_sort[a37], witness_sort[a37]) -> true

Q is empty.

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

(57) QTRSRRRProof (EQUIVALENT)
Used ordering:
if1'/4(YES,YES,YES,YES)
true_renamed/0)
true/0)
filterlow'/2(YES,YES)
cons/2(YES,YES)
ge/2(YES,YES)
false_renamed/0)
nil/0)
false/0)
0/0)
s/1)YES(
if1/4(YES,YES,YES,YES)
filterlow/2(YES,YES)
equal_bool/2(YES,YES)
and/2(YES,YES)
or/2(YES,YES)
not/1(YES)
isa_true/1(YES)
isa_false/1(YES)
equal_sort[a0]/2(YES,YES)
equal_sort[a5]/2(YES,YES)
equal_sort[a18]/2(YES,YES)
equal_sort[a37]/2(YES,YES)
witness_sort[a37]/0)

Quasi precedence:
nil > [false, not_1, equal_sort[a0]_2] > [true_renamed, true, 0, witness_sort[a37]] > [if1'_4, filterlow'_2, false_renamed] > ge_2
[if1_4, filterlow_2] > cons_2 > [if1'_4, filterlow'_2, false_renamed] > ge_2
[if1_4, filterlow_2] > cons_2 > and_2
equal_bool_2 > [true_renamed, true, 0, witness_sort[a37]] > [if1'_4, filterlow'_2, false_renamed] > ge_2
isa_false_1 > [false, not_1, equal_sort[a0]_2] > [true_renamed, true, 0, witness_sort[a37]] > [if1'_4, filterlow'_2, false_renamed] > ge_2
equal_sort[a5]_2 > [false, not_1, equal_sort[a0]_2] > [true_renamed, true, 0, witness_sort[a37]] > [if1'_4, filterlow'_2, false_renamed] > ge_2
equal_sort[a5]_2 > and_2
equal_sort[a18]_2 > [false, not_1, equal_sort[a0]_2] > [true_renamed, true, 0, witness_sort[a37]] > [if1'_4, filterlow'_2, false_renamed] > ge_2
equal_sort[a37]_2 > [true_renamed, true, 0, witness_sort[a37]] > [if1'_4, filterlow'_2, false_renamed] > ge_2


Status:
if1'_4: [2,4,3,1]
true_renamed: multiset status
true: multiset status
filterlow'_2: [1,2]
cons_2: multiset status
ge_2: multiset status
false_renamed: multiset status
nil: multiset status
false: multiset status
0: multiset status
if1_4: [2,4,3,1]
filterlow_2: [1,2]
equal_bool_2: [1,2]
and_2: [1,2]
or_2: [1,2]
not_1: multiset status
isa_true_1: multiset status
isa_false_1: [1]
equal_sort[a0]_2: multiset status
equal_sort[a5]_2: multiset status
equal_sort[a18]_2: [1,2]
equal_sort[a37]_2: [2,1]
witness_sort[a37]: multiset status

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

   if1'(true_renamed, n, x1, xs') -> true
   filterlow'(n', cons(x2, xs'')) -> if1'(ge(n', x2), n', x2, xs'')
   if1'(false_renamed, n'', x3, xs1) -> filterlow'(n'', xs1)
   filterlow'(n1, nil) -> false
   ge(x', 0) -> true_renamed
   if1(true_renamed, n, x1, xs') -> filterlow(n, xs')
   filterlow(n', cons(x2, xs'')) -> if1(ge(n', x2), n', x2, xs'')
   if1(false_renamed, n'', x3, xs1) -> cons(x3, filterlow(n'', xs1))
   filterlow(n1, nil) -> nil
   ge(0, s(x4)) -> false_renamed
   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(v13)) -> false
   equal_sort[a0](s(v14), 0) -> false
   equal_sort[a5](cons(v16, v17), cons(v18, v19)) -> and(equal_sort[a0](v16, v18), equal_sort[a5](v17, v19))
   equal_sort[a5](cons(v16, v17), nil) -> false
   equal_sort[a5](nil, cons(v20, v21)) -> false
   equal_sort[a5](nil, nil) -> true
   equal_sort[a18](true_renamed, true_renamed) -> true
   equal_sort[a18](true_renamed, false_renamed) -> false
   equal_sort[a18](false_renamed, true_renamed) -> false
   equal_sort[a18](false_renamed, false_renamed) -> true
   equal_sort[a37](witness_sort[a37], witness_sort[a37]) -> true




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

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

   ge(s(x''), s(y)) -> ge(x'', y)
   equal_sort[a0](s(v14), s(v15)) -> equal_sort[a0](v14, v15)

Q is empty.

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

(59) QTRSRRRProof (EQUIVALENT)
Used ordering:
Knuth-Bendix order [KBO] with precedence:s_1 > equal_sort[a0]_2 > ge_2

and weight map:

   s_1=0
   ge_2=0
   equal_sort[a0]_2=0

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

   ge(s(x''), s(y)) -> ge(x'', y)
   equal_sort[a0](s(v14), s(v15)) -> equal_sort[a0](v14, v15)




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

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

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

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

(62)
YES

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

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

   if2'(true_renamed, n1, x5, xs2) -> true
   if2'(false_renamed, n2, x6, xs3) -> filterhigh'(n2, xs3)
   filterhigh'(n3, nil) -> false
   filterhigh'(n5, cons(x8, xs5)) -> if2'(ge(x8, n5), n5, x8, xs5)
   if1(true_renamed, n, x'', xs'') -> filterlow(n, xs'')
   ge(x1, 0) -> true_renamed
   ge(0, s(x2)) -> false_renamed
   ge(s(x3), s(y)) -> ge(x3, y)
   if1(false_renamed, n', x4, xs1) -> cons(x4, filterlow(n', xs1))
   filterlow(n'', nil) -> nil
   if2(true_renamed, n1, x5, xs2) -> filterhigh(n1, xs2)
   if2(false_renamed, n2, x6, xs3) -> cons(x6, filterhigh(n2, xs3))
   filterhigh(n3, nil) -> nil
   filterlow(n4, cons(x7, xs4)) -> if1(ge(n4, x7), n4, x7, xs4)
   filterhigh(n5, cons(x8, xs5)) -> if2(ge(x8, n5), n5, x8, xs5)
   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(v21)) -> false
   equal_sort[a0](s(v22), 0) -> false
   equal_sort[a0](s(v22), s(v23)) -> equal_sort[a0](v22, v23)
   equal_sort[a2](cons(v24, v25), cons(v26, v27)) -> and(equal_sort[a0](v24, v26), equal_sort[a2](v25, v27))
   equal_sort[a2](cons(v24, v25), nil) -> false
   equal_sort[a2](nil, cons(v28, v29)) -> false
   equal_sort[a2](nil, nil) -> true
   equal_sort[a33](true_renamed, true_renamed) -> true
   equal_sort[a33](true_renamed, false_renamed) -> false
   equal_sort[a33](false_renamed, true_renamed) -> false
   equal_sort[a33](false_renamed, false_renamed) -> true
   equal_sort[a57](witness_sort[a57], witness_sort[a57]) -> true

Q is empty.

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

(64) QTRSRRRProof (EQUIVALENT)
Used ordering:
if2'/4(YES,YES,YES,YES)
true_renamed/0)
true/0)
false_renamed/0)
filterhigh'/2(YES,YES)
nil/0)
false/0)
cons/2(YES,YES)
ge/2(YES,YES)
if1/4(YES,YES,YES,YES)
filterlow/2(YES,YES)
0/0)
s/1)YES(
if2/4(YES,YES,YES,YES)
filterhigh/2(YES,YES)
equal_bool/2(YES,YES)
and/2(YES,YES)
or/2(YES,YES)
not/1(YES)
isa_true/1(YES)
isa_false/1(YES)
equal_sort[a0]/2(YES,YES)
equal_sort[a2]/2(YES,YES)
equal_sort[a33]/2(YES,YES)
equal_sort[a57]/2(YES,YES)
witness_sort[a57]/0)

Quasi precedence:
[if2'_4, filterhigh'_2] > [cons_2, ge_2] > false_renamed > [true, isa_false_1, equal_sort[a57]_2] > false
[if2'_4, filterhigh'_2] > [cons_2, ge_2] > and_2
[true_renamed, 0, if2_4, filterhigh_2] > [if1_4, filterlow_2] > nil
[true_renamed, 0, if2_4, filterhigh_2] > [if1_4, filterlow_2] > [cons_2, ge_2] > false_renamed > [true, isa_false_1, equal_sort[a57]_2] > false
[true_renamed, 0, if2_4, filterhigh_2] > [if1_4, filterlow_2] > [cons_2, ge_2] > and_2
equal_bool_2 > [true, isa_false_1, equal_sort[a57]_2] > false
not_1 > [true, isa_false_1, equal_sort[a57]_2] > false
isa_true_1 > [true, isa_false_1, equal_sort[a57]_2] > false
[equal_sort[a0]_2, equal_sort[a2]_2] > [true, isa_false_1, equal_sort[a57]_2] > false
[equal_sort[a0]_2, equal_sort[a2]_2] > and_2
equal_sort[a33]_2 > [true, isa_false_1, equal_sort[a57]_2] > false
witness_sort[a57] > [true, isa_false_1, equal_sort[a57]_2] > false


Status:
if2'_4: [2,4,1,3]
true_renamed: multiset status
true: multiset status
false_renamed: multiset status
filterhigh'_2: [1,2]
nil: multiset status
false: multiset status
cons_2: multiset status
ge_2: [1,2]
if1_4: [4,2,1,3]
filterlow_2: [2,1]
0: multiset status
if2_4: [4,2,1,3]
filterhigh_2: [2,1]
equal_bool_2: multiset status
and_2: [2,1]
or_2: [2,1]
not_1: multiset status
isa_true_1: multiset status
isa_false_1: multiset status
equal_sort[a0]_2: [1,2]
equal_sort[a2]_2: [1,2]
equal_sort[a33]_2: [2,1]
equal_sort[a57]_2: multiset status
witness_sort[a57]: multiset status

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

   if2'(true_renamed, n1, x5, xs2) -> true
   if2'(false_renamed, n2, x6, xs3) -> filterhigh'(n2, xs3)
   filterhigh'(n3, nil) -> false
   filterhigh'(n5, cons(x8, xs5)) -> if2'(ge(x8, n5), n5, x8, xs5)
   if1(true_renamed, n, x'', xs'') -> filterlow(n, xs'')
   ge(x1, 0) -> true_renamed
   ge(0, s(x2)) -> false_renamed
   if1(false_renamed, n', x4, xs1) -> cons(x4, filterlow(n', xs1))
   filterlow(n'', nil) -> nil
   if2(true_renamed, n1, x5, xs2) -> filterhigh(n1, xs2)
   if2(false_renamed, n2, x6, xs3) -> cons(x6, filterhigh(n2, xs3))
   filterhigh(n3, nil) -> nil
   filterlow(n4, cons(x7, xs4)) -> if1(ge(n4, x7), n4, x7, xs4)
   filterhigh(n5, cons(x8, xs5)) -> if2(ge(x8, n5), n5, x8, xs5)
   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(v21)) -> false
   equal_sort[a0](s(v22), 0) -> false
   equal_sort[a2](cons(v24, v25), cons(v26, v27)) -> and(equal_sort[a0](v24, v26), equal_sort[a2](v25, v27))
   equal_sort[a2](cons(v24, v25), nil) -> false
   equal_sort[a2](nil, cons(v28, v29)) -> false
   equal_sort[a2](nil, nil) -> true
   equal_sort[a33](true_renamed, true_renamed) -> true
   equal_sort[a33](true_renamed, false_renamed) -> false
   equal_sort[a33](false_renamed, true_renamed) -> false
   equal_sort[a33](false_renamed, false_renamed) -> true
   equal_sort[a57](witness_sort[a57], witness_sort[a57]) -> true




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

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

   ge(s(x3), s(y)) -> ge(x3, y)
   equal_sort[a0](s(v22), s(v23)) -> equal_sort[a0](v22, v23)

Q is empty.

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

(66) QTRSRRRProof (EQUIVALENT)
Used ordering:
Knuth-Bendix order [KBO] with precedence:s_1 > equal_sort[a0]_2 > ge_2

and weight map:

   s_1=0
   ge_2=0
   equal_sort[a0]_2=0

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

   ge(s(x3), s(y)) -> ge(x3, y)
   equal_sort[a0](s(v22), s(v23)) -> equal_sort[a0](v22, v23)




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

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

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

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

(69)
YES