YES
proof of /export/starexec/sandbox2/benchmark/theBenchmark.xml
# AProVE Commit ID: 794c25de1cacf0d048858bcd21c9a779e1221865 marcel 20200619 unpublished dirty


Termination of the given ETRS could be proven:

(0) ETRS
(1) EquationalDependencyPairsProof [EQUIVALENT, 0 ms]
(2) EDP
(3) EDependencyGraphProof [EQUIVALENT, 0 ms]
(4) AND
    (5) EDP
        (6) ESharpUsableEquationsProof [EQUIVALENT, 0 ms]
        (7) EDP
        (8) EUsableRulesReductionPairsProof [EQUIVALENT, 0 ms]
        (9) EDP
        (10) PisEmptyProof [EQUIVALENT, 0 ms]
        (11) YES
    (12) EDP
        (13) ESharpUsableEquationsProof [EQUIVALENT, 0 ms]
        (14) EDP
        (15) EUsableRulesReductionPairsProof [EQUIVALENT, 0 ms]
        (16) EDP
        (17) PisEmptyProof [EQUIVALENT, 0 ms]
        (18) YES
    (19) EDP
        (20) ESharpUsableEquationsProof [EQUIVALENT, 0 ms]
        (21) EDP
        (22) EDPPoloProof [EQUIVALENT, 0 ms]
        (23) EDP
        (24) PisEmptyProof [EQUIVALENT, 0 ms]
        (25) YES
    (26) EDP
        (27) EUsableRulesReductionPairsProof [EQUIVALENT, 0 ms]
        (28) EDP
        (29) PisEmptyProof [EQUIVALENT, 0 ms]
        (30) YES
    (31) EDP
        (32) ESharpUsableEquationsProof [EQUIVALENT, 0 ms]
        (33) EDP
        (34) EDPPoloProof [EQUIVALENT, 0 ms]
        (35) EDP
        (36) PisEmptyProof [EQUIVALENT, 0 ms]
        (37) YES
    (38) EDP
        (39) ESharpUsableEquationsProof [EQUIVALENT, 0 ms]
        (40) EDP
        (41) EDPPoloProof [EQUIVALENT, 0 ms]
        (42) EDP
        (43) EDPPoloProof [EQUIVALENT, 22 ms]
        (44) EDP
        (45) EDependencyGraphProof [EQUIVALENT, 0 ms]
        (46) TRUE


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

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

   eq(0, 0) -> true
   eq(0, s(x)) -> false
   eq(s(x), 0) -> false
   eq(s(x), s(y)) -> eq(x, y)
   le(0, y) -> true
   le(s(x), 0) -> false
   le(s(x), s(y)) -> le(x, y)
   app(nil, y) -> y
   app(add(n, x), y) -> add(n, app(x, y))
   min(add(n, nil)) -> n
   min(add(n, add(m, x))) -> if_min(le(n, m), add(n, add(m, x)))
   if_min(true, add(n, add(m, x))) -> min(add(n, x))
   if_min(false, add(n, add(m, x))) -> min(add(m, x))
   rm(n, nil) -> nil
   rm(n, add(m, x)) -> if_rm(eq(n, m), n, add(m, x))
   if_rm(true, n, add(m, x)) -> rm(n, x)
   if_rm(false, n, add(m, x)) -> add(m, rm(n, x))
   minsort(nil, nil) -> nil
   minsort(add(n, x), y) -> if_minsort(eq(n, min(add(n, x))), add(n, x), y)
   if_minsort(true, add(n, x), y) -> add(n, minsort(app(rm(n, x), y), nil))
   if_minsort(false, add(n, x), y) -> minsort(x, add(n, y))

The set E consists of the following equations:

   eq(x, y) == eq(y, x)


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

(1) EquationalDependencyPairsProof (EQUIVALENT)
Using Dependency Pairs [AG00,DA_STEIN] we result in the following initial EDP problem:
The TRS P consists of the following rules:

   EQ(s(x), s(y)) -> EQ(x, y)
   LE(s(x), s(y)) -> LE(x, y)
   APP(add(n, x), y) -> APP(x, y)
   MIN(add(n, add(m, x))) -> IF_MIN(le(n, m), add(n, add(m, x)))
   MIN(add(n, add(m, x))) -> LE(n, m)
   IF_MIN(true, add(n, add(m, x))) -> MIN(add(n, x))
   IF_MIN(false, add(n, add(m, x))) -> MIN(add(m, x))
   RM(n, add(m, x)) -> IF_RM(eq(n, m), n, add(m, x))
   RM(n, add(m, x)) -> EQ(n, m)
   IF_RM(true, n, add(m, x)) -> RM(n, x)
   IF_RM(false, n, add(m, x)) -> RM(n, x)
   MINSORT(add(n, x), y) -> IF_MINSORT(eq(n, min(add(n, x))), add(n, x), y)
   MINSORT(add(n, x), y) -> EQ(n, min(add(n, x)))
   MINSORT(add(n, x), y) -> MIN(add(n, x))
   IF_MINSORT(true, add(n, x), y) -> MINSORT(app(rm(n, x), y), nil)
   IF_MINSORT(true, add(n, x), y) -> APP(rm(n, x), y)
   IF_MINSORT(true, add(n, x), y) -> RM(n, x)
   IF_MINSORT(false, add(n, x), y) -> MINSORT(x, add(n, y))

The TRS R consists of the following rules:

   eq(0, 0) -> true
   eq(0, s(x)) -> false
   eq(s(x), 0) -> false
   eq(s(x), s(y)) -> eq(x, y)
   le(0, y) -> true
   le(s(x), 0) -> false
   le(s(x), s(y)) -> le(x, y)
   app(nil, y) -> y
   app(add(n, x), y) -> add(n, app(x, y))
   min(add(n, nil)) -> n
   min(add(n, add(m, x))) -> if_min(le(n, m), add(n, add(m, x)))
   if_min(true, add(n, add(m, x))) -> min(add(n, x))
   if_min(false, add(n, add(m, x))) -> min(add(m, x))
   rm(n, nil) -> nil
   rm(n, add(m, x)) -> if_rm(eq(n, m), n, add(m, x))
   if_rm(true, n, add(m, x)) -> rm(n, x)
   if_rm(false, n, add(m, x)) -> add(m, rm(n, x))
   minsort(nil, nil) -> nil
   minsort(add(n, x), y) -> if_minsort(eq(n, min(add(n, x))), add(n, x), y)
   if_minsort(true, add(n, x), y) -> add(n, minsort(app(rm(n, x), y), nil))
   if_minsort(false, add(n, x), y) -> minsort(x, add(n, y))

The set E consists of the following equations:

   eq(x, y) == eq(y, x)

The set E# consists of the following equations:

   EQ(x, y) == EQ(y, x)

We have to consider all minimal (P,E#,R,E)-chains

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

(2)
Obligation:
The TRS P consists of the following rules:

   EQ(s(x), s(y)) -> EQ(x, y)
   LE(s(x), s(y)) -> LE(x, y)
   APP(add(n, x), y) -> APP(x, y)
   MIN(add(n, add(m, x))) -> IF_MIN(le(n, m), add(n, add(m, x)))
   MIN(add(n, add(m, x))) -> LE(n, m)
   IF_MIN(true, add(n, add(m, x))) -> MIN(add(n, x))
   IF_MIN(false, add(n, add(m, x))) -> MIN(add(m, x))
   RM(n, add(m, x)) -> IF_RM(eq(n, m), n, add(m, x))
   RM(n, add(m, x)) -> EQ(n, m)
   IF_RM(true, n, add(m, x)) -> RM(n, x)
   IF_RM(false, n, add(m, x)) -> RM(n, x)
   MINSORT(add(n, x), y) -> IF_MINSORT(eq(n, min(add(n, x))), add(n, x), y)
   MINSORT(add(n, x), y) -> EQ(n, min(add(n, x)))
   MINSORT(add(n, x), y) -> MIN(add(n, x))
   IF_MINSORT(true, add(n, x), y) -> MINSORT(app(rm(n, x), y), nil)
   IF_MINSORT(true, add(n, x), y) -> APP(rm(n, x), y)
   IF_MINSORT(true, add(n, x), y) -> RM(n, x)
   IF_MINSORT(false, add(n, x), y) -> MINSORT(x, add(n, y))

The TRS R consists of the following rules:

   eq(0, 0) -> true
   eq(0, s(x)) -> false
   eq(s(x), 0) -> false
   eq(s(x), s(y)) -> eq(x, y)
   le(0, y) -> true
   le(s(x), 0) -> false
   le(s(x), s(y)) -> le(x, y)
   app(nil, y) -> y
   app(add(n, x), y) -> add(n, app(x, y))
   min(add(n, nil)) -> n
   min(add(n, add(m, x))) -> if_min(le(n, m), add(n, add(m, x)))
   if_min(true, add(n, add(m, x))) -> min(add(n, x))
   if_min(false, add(n, add(m, x))) -> min(add(m, x))
   rm(n, nil) -> nil
   rm(n, add(m, x)) -> if_rm(eq(n, m), n, add(m, x))
   if_rm(true, n, add(m, x)) -> rm(n, x)
   if_rm(false, n, add(m, x)) -> add(m, rm(n, x))
   minsort(nil, nil) -> nil
   minsort(add(n, x), y) -> if_minsort(eq(n, min(add(n, x))), add(n, x), y)
   if_minsort(true, add(n, x), y) -> add(n, minsort(app(rm(n, x), y), nil))
   if_minsort(false, add(n, x), y) -> minsort(x, add(n, y))

The set E consists of the following equations:

   eq(x, y) == eq(y, x)

The set E# consists of the following equations:

   EQ(x, y) == EQ(y, x)

We have to consider all minimal (P,E#,R,E)-chains
----------------------------------------

(3) EDependencyGraphProof (EQUIVALENT)
The approximation of the Equational Dependency Graph [DA_STEIN] contains 6 SCCs with 6 less nodes.
----------------------------------------

(4)
Complex Obligation (AND)

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

(5)
Obligation:
The TRS P consists of the following rules:

   APP(add(n, x), y) -> APP(x, y)

The TRS R consists of the following rules:

   eq(0, 0) -> true
   eq(0, s(x)) -> false
   eq(s(x), 0) -> false
   eq(s(x), s(y)) -> eq(x, y)
   le(0, y) -> true
   le(s(x), 0) -> false
   le(s(x), s(y)) -> le(x, y)
   app(nil, y) -> y
   app(add(n, x), y) -> add(n, app(x, y))
   min(add(n, nil)) -> n
   min(add(n, add(m, x))) -> if_min(le(n, m), add(n, add(m, x)))
   if_min(true, add(n, add(m, x))) -> min(add(n, x))
   if_min(false, add(n, add(m, x))) -> min(add(m, x))
   rm(n, nil) -> nil
   rm(n, add(m, x)) -> if_rm(eq(n, m), n, add(m, x))
   if_rm(true, n, add(m, x)) -> rm(n, x)
   if_rm(false, n, add(m, x)) -> add(m, rm(n, x))
   minsort(nil, nil) -> nil
   minsort(add(n, x), y) -> if_minsort(eq(n, min(add(n, x))), add(n, x), y)
   if_minsort(true, add(n, x), y) -> add(n, minsort(app(rm(n, x), y), nil))
   if_minsort(false, add(n, x), y) -> minsort(x, add(n, y))

The set E consists of the following equations:

   eq(x, y) == eq(y, x)

The set E# consists of the following equations:

   EQ(x, y) == EQ(y, x)

We have to consider all minimal (P,E#,R,E)-chains
----------------------------------------

(6) ESharpUsableEquationsProof (EQUIVALENT)
We can delete the following equations of E# with the esharp usable equations processor[DA_STEIN]:
   EQ(x, y) == EQ(y, x)

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

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

   APP(add(n, x), y) -> APP(x, y)

The TRS R consists of the following rules:

   eq(0, 0) -> true
   eq(0, s(x)) -> false
   eq(s(x), 0) -> false
   eq(s(x), s(y)) -> eq(x, y)
   le(0, y) -> true
   le(s(x), 0) -> false
   le(s(x), s(y)) -> le(x, y)
   app(nil, y) -> y
   app(add(n, x), y) -> add(n, app(x, y))
   min(add(n, nil)) -> n
   min(add(n, add(m, x))) -> if_min(le(n, m), add(n, add(m, x)))
   if_min(true, add(n, add(m, x))) -> min(add(n, x))
   if_min(false, add(n, add(m, x))) -> min(add(m, x))
   rm(n, nil) -> nil
   rm(n, add(m, x)) -> if_rm(eq(n, m), n, add(m, x))
   if_rm(true, n, add(m, x)) -> rm(n, x)
   if_rm(false, n, add(m, x)) -> add(m, rm(n, x))
   minsort(nil, nil) -> nil
   minsort(add(n, x), y) -> if_minsort(eq(n, min(add(n, x))), add(n, x), y)
   if_minsort(true, add(n, x), y) -> add(n, minsort(app(rm(n, x), y), nil))
   if_minsort(false, add(n, x), y) -> minsort(x, add(n, y))

The set E consists of the following equations:

   eq(x, y) == eq(y, x)

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

(8) EUsableRulesReductionPairsProof (EQUIVALENT)
By using the improved usable rules and equations with reduction pair processor [DA_STEIN] with a polynomial ordering [POLO], all dependency pairs and the corresponding improved usable rules can be oriented non-strictly, the improved  usable equations and the esharp equations can be oriented equivalently. All non-usable rules and equations are removed, and those dependency pairs and improved usable rules that have been oriented strictly or contain non-usable symbols in their left-hand side are removed as well.

The following dependency pairs can be deleted:

   APP(add(n, x), y) -> APP(x, y)
The following rules are removed from R:

   eq(0, 0) -> true
   eq(0, s(x)) -> false
   eq(s(x), 0) -> false
   eq(s(x), s(y)) -> eq(x, y)
   le(0, y) -> true
   le(s(x), 0) -> false
   le(s(x), s(y)) -> le(x, y)
   app(nil, y) -> y
   app(add(n, x), y) -> add(n, app(x, y))
   min(add(n, nil)) -> n
   min(add(n, add(m, x))) -> if_min(le(n, m), add(n, add(m, x)))
   if_min(true, add(n, add(m, x))) -> min(add(n, x))
   if_min(false, add(n, add(m, x))) -> min(add(m, x))
   rm(n, nil) -> nil
   rm(n, add(m, x)) -> if_rm(eq(n, m), n, add(m, x))
   if_rm(true, n, add(m, x)) -> rm(n, x)
   if_rm(false, n, add(m, x)) -> add(m, rm(n, x))
   minsort(nil, nil) -> nil
   minsort(add(n, x), y) -> if_minsort(eq(n, min(add(n, x))), add(n, x), y)
   if_minsort(true, add(n, x), y) -> add(n, minsort(app(rm(n, x), y), nil))
   if_minsort(false, add(n, x), y) -> minsort(x, add(n, y))
The following equations are removed from E:

   eq(x, y) == eq(y, x)
Used ordering: POLO with Polynomial interpretation [POLO]:

   POL(APP(x_1, x_2)) = 3*x_1 + x_2
   POL(add(x_1, x_2)) = x_1 + 3*x_2


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

(9)
Obligation:
P is empty.
R is empty.
E is empty.
E# is empty.
We have to consider all minimal (P,E#,R,E)-chains
----------------------------------------

(10) PisEmptyProof (EQUIVALENT)
The TRS P is empty. Hence, there is no (P,E#,R,E) chain.
----------------------------------------

(11)
YES

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

(12)
Obligation:
The TRS P consists of the following rules:

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

The TRS R consists of the following rules:

   eq(0, 0) -> true
   eq(0, s(x)) -> false
   eq(s(x), 0) -> false
   eq(s(x), s(y)) -> eq(x, y)
   le(0, y) -> true
   le(s(x), 0) -> false
   le(s(x), s(y)) -> le(x, y)
   app(nil, y) -> y
   app(add(n, x), y) -> add(n, app(x, y))
   min(add(n, nil)) -> n
   min(add(n, add(m, x))) -> if_min(le(n, m), add(n, add(m, x)))
   if_min(true, add(n, add(m, x))) -> min(add(n, x))
   if_min(false, add(n, add(m, x))) -> min(add(m, x))
   rm(n, nil) -> nil
   rm(n, add(m, x)) -> if_rm(eq(n, m), n, add(m, x))
   if_rm(true, n, add(m, x)) -> rm(n, x)
   if_rm(false, n, add(m, x)) -> add(m, rm(n, x))
   minsort(nil, nil) -> nil
   minsort(add(n, x), y) -> if_minsort(eq(n, min(add(n, x))), add(n, x), y)
   if_minsort(true, add(n, x), y) -> add(n, minsort(app(rm(n, x), y), nil))
   if_minsort(false, add(n, x), y) -> minsort(x, add(n, y))

The set E consists of the following equations:

   eq(x, y) == eq(y, x)

The set E# consists of the following equations:

   EQ(x, y) == EQ(y, x)

We have to consider all minimal (P,E#,R,E)-chains
----------------------------------------

(13) ESharpUsableEquationsProof (EQUIVALENT)
We can delete the following equations of E# with the esharp usable equations processor[DA_STEIN]:
   EQ(x, y) == EQ(y, x)

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

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

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

The TRS R consists of the following rules:

   eq(0, 0) -> true
   eq(0, s(x)) -> false
   eq(s(x), 0) -> false
   eq(s(x), s(y)) -> eq(x, y)
   le(0, y) -> true
   le(s(x), 0) -> false
   le(s(x), s(y)) -> le(x, y)
   app(nil, y) -> y
   app(add(n, x), y) -> add(n, app(x, y))
   min(add(n, nil)) -> n
   min(add(n, add(m, x))) -> if_min(le(n, m), add(n, add(m, x)))
   if_min(true, add(n, add(m, x))) -> min(add(n, x))
   if_min(false, add(n, add(m, x))) -> min(add(m, x))
   rm(n, nil) -> nil
   rm(n, add(m, x)) -> if_rm(eq(n, m), n, add(m, x))
   if_rm(true, n, add(m, x)) -> rm(n, x)
   if_rm(false, n, add(m, x)) -> add(m, rm(n, x))
   minsort(nil, nil) -> nil
   minsort(add(n, x), y) -> if_minsort(eq(n, min(add(n, x))), add(n, x), y)
   if_minsort(true, add(n, x), y) -> add(n, minsort(app(rm(n, x), y), nil))
   if_minsort(false, add(n, x), y) -> minsort(x, add(n, y))

The set E consists of the following equations:

   eq(x, y) == eq(y, x)

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

(15) EUsableRulesReductionPairsProof (EQUIVALENT)
By using the improved usable rules and equations with reduction pair processor [DA_STEIN] with a polynomial ordering [POLO], all dependency pairs and the corresponding improved usable rules can be oriented non-strictly, the improved  usable equations and the esharp equations can be oriented equivalently. All non-usable rules and equations are removed, and those dependency pairs and improved usable rules that have been oriented strictly or contain non-usable symbols in their left-hand side are removed as well.

The following dependency pairs can be deleted:

   LE(s(x), s(y)) -> LE(x, y)
The following rules are removed from R:

   eq(0, 0) -> true
   eq(0, s(x)) -> false
   eq(s(x), 0) -> false
   eq(s(x), s(y)) -> eq(x, y)
   le(0, y) -> true
   le(s(x), 0) -> false
   le(s(x), s(y)) -> le(x, y)
   app(nil, y) -> y
   app(add(n, x), y) -> add(n, app(x, y))
   min(add(n, nil)) -> n
   min(add(n, add(m, x))) -> if_min(le(n, m), add(n, add(m, x)))
   if_min(true, add(n, add(m, x))) -> min(add(n, x))
   if_min(false, add(n, add(m, x))) -> min(add(m, x))
   rm(n, nil) -> nil
   rm(n, add(m, x)) -> if_rm(eq(n, m), n, add(m, x))
   if_rm(true, n, add(m, x)) -> rm(n, x)
   if_rm(false, n, add(m, x)) -> add(m, rm(n, x))
   minsort(nil, nil) -> nil
   minsort(add(n, x), y) -> if_minsort(eq(n, min(add(n, x))), add(n, x), y)
   if_minsort(true, add(n, x), y) -> add(n, minsort(app(rm(n, x), y), nil))
   if_minsort(false, add(n, x), y) -> minsort(x, add(n, y))
The following equations are removed from E:

   eq(x, y) == eq(y, x)
Used ordering: POLO with Polynomial interpretation [POLO]:

   POL(LE(x_1, x_2)) = 3*x_1 + 3*x_2
   POL(s(x_1)) = x_1


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

(16)
Obligation:
P is empty.
R is empty.
E is empty.
E# is empty.
We have to consider all minimal (P,E#,R,E)-chains
----------------------------------------

(17) PisEmptyProof (EQUIVALENT)
The TRS P is empty. Hence, there is no (P,E#,R,E) chain.
----------------------------------------

(18)
YES

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

(19)
Obligation:
The TRS P consists of the following rules:

   IF_MIN(true, add(n, add(m, x))) -> MIN(add(n, x))
   IF_MIN(false, add(n, add(m, x))) -> MIN(add(m, x))
   MIN(add(n, add(m, x))) -> IF_MIN(le(n, m), add(n, add(m, x)))

The TRS R consists of the following rules:

   eq(0, 0) -> true
   eq(0, s(x)) -> false
   eq(s(x), 0) -> false
   eq(s(x), s(y)) -> eq(x, y)
   le(0, y) -> true
   le(s(x), 0) -> false
   le(s(x), s(y)) -> le(x, y)
   app(nil, y) -> y
   app(add(n, x), y) -> add(n, app(x, y))
   min(add(n, nil)) -> n
   min(add(n, add(m, x))) -> if_min(le(n, m), add(n, add(m, x)))
   if_min(true, add(n, add(m, x))) -> min(add(n, x))
   if_min(false, add(n, add(m, x))) -> min(add(m, x))
   rm(n, nil) -> nil
   rm(n, add(m, x)) -> if_rm(eq(n, m), n, add(m, x))
   if_rm(true, n, add(m, x)) -> rm(n, x)
   if_rm(false, n, add(m, x)) -> add(m, rm(n, x))
   minsort(nil, nil) -> nil
   minsort(add(n, x), y) -> if_minsort(eq(n, min(add(n, x))), add(n, x), y)
   if_minsort(true, add(n, x), y) -> add(n, minsort(app(rm(n, x), y), nil))
   if_minsort(false, add(n, x), y) -> minsort(x, add(n, y))

The set E consists of the following equations:

   eq(x, y) == eq(y, x)

The set E# consists of the following equations:

   EQ(x, y) == EQ(y, x)

We have to consider all minimal (P,E#,R,E)-chains
----------------------------------------

(20) ESharpUsableEquationsProof (EQUIVALENT)
We can delete the following equations of E# with the esharp usable equations processor[DA_STEIN]:
   EQ(x, y) == EQ(y, x)

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

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

   IF_MIN(true, add(n, add(m, x))) -> MIN(add(n, x))
   IF_MIN(false, add(n, add(m, x))) -> MIN(add(m, x))
   MIN(add(n, add(m, x))) -> IF_MIN(le(n, m), add(n, add(m, x)))

The TRS R consists of the following rules:

   eq(0, 0) -> true
   eq(0, s(x)) -> false
   eq(s(x), 0) -> false
   eq(s(x), s(y)) -> eq(x, y)
   le(0, y) -> true
   le(s(x), 0) -> false
   le(s(x), s(y)) -> le(x, y)
   app(nil, y) -> y
   app(add(n, x), y) -> add(n, app(x, y))
   min(add(n, nil)) -> n
   min(add(n, add(m, x))) -> if_min(le(n, m), add(n, add(m, x)))
   if_min(true, add(n, add(m, x))) -> min(add(n, x))
   if_min(false, add(n, add(m, x))) -> min(add(m, x))
   rm(n, nil) -> nil
   rm(n, add(m, x)) -> if_rm(eq(n, m), n, add(m, x))
   if_rm(true, n, add(m, x)) -> rm(n, x)
   if_rm(false, n, add(m, x)) -> add(m, rm(n, x))
   minsort(nil, nil) -> nil
   minsort(add(n, x), y) -> if_minsort(eq(n, min(add(n, x))), add(n, x), y)
   if_minsort(true, add(n, x), y) -> add(n, minsort(app(rm(n, x), y), nil))
   if_minsort(false, add(n, x), y) -> minsort(x, add(n, y))

The set E consists of the following equations:

   eq(x, y) == eq(y, x)

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

(22) EDPPoloProof (EQUIVALENT)
We use the reduction pair processor [DA_STEIN] with a polynomial ordering [POLO]. All Dependency Pairs of this DP problem can be strictly oriented.


   IF_MIN(true, add(n, add(m, x))) -> MIN(add(n, x))
   IF_MIN(false, add(n, add(m, x))) -> MIN(add(m, x))
   MIN(add(n, add(m, x))) -> IF_MIN(le(n, m), add(n, add(m, x)))
With the implicit AFS there is no usable rule of R.


There is no equation of E#.


With the implicit AFS there is no usable equation of E.


Used ordering: POLO with Polynomial interpretation [POLO]:

   POL(0) = 0
   POL(IF_MIN(x_1, x_2)) = 2*x_2
   POL(MIN(x_1)) = 3 + 3*x_1
   POL(add(x_1, x_2)) = 3 + 3*x_2
   POL(false) = 0
   POL(le(x_1, x_2)) = 0
   POL(s(x_1)) = 3*x_1
   POL(true) = 0


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

(23)
Obligation:
P is empty.
The TRS R consists of the following rules:

   eq(0, 0) -> true
   eq(0, s(x)) -> false
   eq(s(x), 0) -> false
   eq(s(x), s(y)) -> eq(x, y)
   le(0, y) -> true
   le(s(x), 0) -> false
   le(s(x), s(y)) -> le(x, y)
   app(nil, y) -> y
   app(add(n, x), y) -> add(n, app(x, y))
   min(add(n, nil)) -> n
   min(add(n, add(m, x))) -> if_min(le(n, m), add(n, add(m, x)))
   if_min(true, add(n, add(m, x))) -> min(add(n, x))
   if_min(false, add(n, add(m, x))) -> min(add(m, x))
   rm(n, nil) -> nil
   rm(n, add(m, x)) -> if_rm(eq(n, m), n, add(m, x))
   if_rm(true, n, add(m, x)) -> rm(n, x)
   if_rm(false, n, add(m, x)) -> add(m, rm(n, x))
   minsort(nil, nil) -> nil
   minsort(add(n, x), y) -> if_minsort(eq(n, min(add(n, x))), add(n, x), y)
   if_minsort(true, add(n, x), y) -> add(n, minsort(app(rm(n, x), y), nil))
   if_minsort(false, add(n, x), y) -> minsort(x, add(n, y))

The set E consists of the following equations:

   eq(x, y) == eq(y, x)

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

(24) PisEmptyProof (EQUIVALENT)
The TRS P is empty. Hence, there is no (P,E#,R,E) chain.
----------------------------------------

(25)
YES

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

(26)
Obligation:
The TRS P consists of the following rules:

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

The TRS R consists of the following rules:

   eq(0, 0) -> true
   eq(0, s(x)) -> false
   eq(s(x), 0) -> false
   eq(s(x), s(y)) -> eq(x, y)
   le(0, y) -> true
   le(s(x), 0) -> false
   le(s(x), s(y)) -> le(x, y)
   app(nil, y) -> y
   app(add(n, x), y) -> add(n, app(x, y))
   min(add(n, nil)) -> n
   min(add(n, add(m, x))) -> if_min(le(n, m), add(n, add(m, x)))
   if_min(true, add(n, add(m, x))) -> min(add(n, x))
   if_min(false, add(n, add(m, x))) -> min(add(m, x))
   rm(n, nil) -> nil
   rm(n, add(m, x)) -> if_rm(eq(n, m), n, add(m, x))
   if_rm(true, n, add(m, x)) -> rm(n, x)
   if_rm(false, n, add(m, x)) -> add(m, rm(n, x))
   minsort(nil, nil) -> nil
   minsort(add(n, x), y) -> if_minsort(eq(n, min(add(n, x))), add(n, x), y)
   if_minsort(true, add(n, x), y) -> add(n, minsort(app(rm(n, x), y), nil))
   if_minsort(false, add(n, x), y) -> minsort(x, add(n, y))

The set E consists of the following equations:

   eq(x, y) == eq(y, x)

The set E# consists of the following equations:

   EQ(x, y) == EQ(y, x)

We have to consider all minimal (P,E#,R,E)-chains
----------------------------------------

(27) EUsableRulesReductionPairsProof (EQUIVALENT)
By using the improved usable rules and equations with reduction pair processor [DA_STEIN] with a polynomial ordering [POLO], all dependency pairs and the corresponding improved usable rules can be oriented non-strictly, the improved  usable equations and the esharp equations can be oriented equivalently. All non-usable rules and equations are removed, and those dependency pairs and improved usable rules that have been oriented strictly or contain non-usable symbols in their left-hand side are removed as well.

The following dependency pairs can be deleted:

   EQ(s(x), s(y)) -> EQ(x, y)
The following rules are removed from R:

   eq(0, 0) -> true
   eq(0, s(x)) -> false
   eq(s(x), 0) -> false
   eq(s(x), s(y)) -> eq(x, y)
   le(0, y) -> true
   le(s(x), 0) -> false
   le(s(x), s(y)) -> le(x, y)
   app(nil, y) -> y
   app(add(n, x), y) -> add(n, app(x, y))
   min(add(n, nil)) -> n
   min(add(n, add(m, x))) -> if_min(le(n, m), add(n, add(m, x)))
   if_min(true, add(n, add(m, x))) -> min(add(n, x))
   if_min(false, add(n, add(m, x))) -> min(add(m, x))
   rm(n, nil) -> nil
   rm(n, add(m, x)) -> if_rm(eq(n, m), n, add(m, x))
   if_rm(true, n, add(m, x)) -> rm(n, x)
   if_rm(false, n, add(m, x)) -> add(m, rm(n, x))
   minsort(nil, nil) -> nil
   minsort(add(n, x), y) -> if_minsort(eq(n, min(add(n, x))), add(n, x), y)
   if_minsort(true, add(n, x), y) -> add(n, minsort(app(rm(n, x), y), nil))
   if_minsort(false, add(n, x), y) -> minsort(x, add(n, y))
The following equations are removed from E:

   eq(x, y) == eq(y, x)
Used ordering: POLO with Polynomial interpretation [POLO]:

   POL(EQ(x_1, x_2)) = 3*x_1 + 3*x_2
   POL(s(x_1)) = 3*x_1


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

(28)
Obligation:
P is empty.
R is empty.
E is empty.
The set E# consists of the following equations:

   EQ(x, y) == EQ(y, x)

We have to consider all minimal (P,E#,R,E)-chains
----------------------------------------

(29) PisEmptyProof (EQUIVALENT)
The TRS P is empty. Hence, there is no (P,E#,R,E) chain.
----------------------------------------

(30)
YES

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

(31)
Obligation:
The TRS P consists of the following rules:

   IF_RM(true, n, add(m, x)) -> RM(n, x)
   RM(n, add(m, x)) -> IF_RM(eq(n, m), n, add(m, x))
   IF_RM(false, n, add(m, x)) -> RM(n, x)

The TRS R consists of the following rules:

   eq(0, 0) -> true
   eq(0, s(x)) -> false
   eq(s(x), 0) -> false
   eq(s(x), s(y)) -> eq(x, y)
   le(0, y) -> true
   le(s(x), 0) -> false
   le(s(x), s(y)) -> le(x, y)
   app(nil, y) -> y
   app(add(n, x), y) -> add(n, app(x, y))
   min(add(n, nil)) -> n
   min(add(n, add(m, x))) -> if_min(le(n, m), add(n, add(m, x)))
   if_min(true, add(n, add(m, x))) -> min(add(n, x))
   if_min(false, add(n, add(m, x))) -> min(add(m, x))
   rm(n, nil) -> nil
   rm(n, add(m, x)) -> if_rm(eq(n, m), n, add(m, x))
   if_rm(true, n, add(m, x)) -> rm(n, x)
   if_rm(false, n, add(m, x)) -> add(m, rm(n, x))
   minsort(nil, nil) -> nil
   minsort(add(n, x), y) -> if_minsort(eq(n, min(add(n, x))), add(n, x), y)
   if_minsort(true, add(n, x), y) -> add(n, minsort(app(rm(n, x), y), nil))
   if_minsort(false, add(n, x), y) -> minsort(x, add(n, y))

The set E consists of the following equations:

   eq(x, y) == eq(y, x)

The set E# consists of the following equations:

   EQ(x, y) == EQ(y, x)

We have to consider all minimal (P,E#,R,E)-chains
----------------------------------------

(32) ESharpUsableEquationsProof (EQUIVALENT)
We can delete the following equations of E# with the esharp usable equations processor[DA_STEIN]:
   EQ(x, y) == EQ(y, x)

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

(33)
Obligation:
The TRS P consists of the following rules:

   IF_RM(true, n, add(m, x)) -> RM(n, x)
   RM(n, add(m, x)) -> IF_RM(eq(n, m), n, add(m, x))
   IF_RM(false, n, add(m, x)) -> RM(n, x)

The TRS R consists of the following rules:

   eq(0, 0) -> true
   eq(0, s(x)) -> false
   eq(s(x), 0) -> false
   eq(s(x), s(y)) -> eq(x, y)
   le(0, y) -> true
   le(s(x), 0) -> false
   le(s(x), s(y)) -> le(x, y)
   app(nil, y) -> y
   app(add(n, x), y) -> add(n, app(x, y))
   min(add(n, nil)) -> n
   min(add(n, add(m, x))) -> if_min(le(n, m), add(n, add(m, x)))
   if_min(true, add(n, add(m, x))) -> min(add(n, x))
   if_min(false, add(n, add(m, x))) -> min(add(m, x))
   rm(n, nil) -> nil
   rm(n, add(m, x)) -> if_rm(eq(n, m), n, add(m, x))
   if_rm(true, n, add(m, x)) -> rm(n, x)
   if_rm(false, n, add(m, x)) -> add(m, rm(n, x))
   minsort(nil, nil) -> nil
   minsort(add(n, x), y) -> if_minsort(eq(n, min(add(n, x))), add(n, x), y)
   if_minsort(true, add(n, x), y) -> add(n, minsort(app(rm(n, x), y), nil))
   if_minsort(false, add(n, x), y) -> minsort(x, add(n, y))

The set E consists of the following equations:

   eq(x, y) == eq(y, x)

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

(34) EDPPoloProof (EQUIVALENT)
We use the reduction pair processor [DA_STEIN] with a polynomial ordering [POLO]. All Dependency Pairs of this DP problem can be strictly oriented.


   IF_RM(true, n, add(m, x)) -> RM(n, x)
   RM(n, add(m, x)) -> IF_RM(eq(n, m), n, add(m, x))
   IF_RM(false, n, add(m, x)) -> RM(n, x)
With the implicit AFS there is no usable rule of R.


There is no equation of E#.


With the implicit AFS there is no usable equation of E.


Used ordering: POLO with Polynomial interpretation [POLO]:

   POL(0) = 0
   POL(IF_RM(x_1, x_2, x_3)) = 3*x_2 + 2*x_3
   POL(RM(x_1, x_2)) = 3 + 3*x_1 + 2*x_2
   POL(add(x_1, x_2)) = 2 + x_2
   POL(eq(x_1, x_2)) = 0
   POL(false) = 0
   POL(s(x_1)) = 0
   POL(true) = 0


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

(35)
Obligation:
P is empty.
The TRS R consists of the following rules:

   eq(0, 0) -> true
   eq(0, s(x)) -> false
   eq(s(x), 0) -> false
   eq(s(x), s(y)) -> eq(x, y)
   le(0, y) -> true
   le(s(x), 0) -> false
   le(s(x), s(y)) -> le(x, y)
   app(nil, y) -> y
   app(add(n, x), y) -> add(n, app(x, y))
   min(add(n, nil)) -> n
   min(add(n, add(m, x))) -> if_min(le(n, m), add(n, add(m, x)))
   if_min(true, add(n, add(m, x))) -> min(add(n, x))
   if_min(false, add(n, add(m, x))) -> min(add(m, x))
   rm(n, nil) -> nil
   rm(n, add(m, x)) -> if_rm(eq(n, m), n, add(m, x))
   if_rm(true, n, add(m, x)) -> rm(n, x)
   if_rm(false, n, add(m, x)) -> add(m, rm(n, x))
   minsort(nil, nil) -> nil
   minsort(add(n, x), y) -> if_minsort(eq(n, min(add(n, x))), add(n, x), y)
   if_minsort(true, add(n, x), y) -> add(n, minsort(app(rm(n, x), y), nil))
   if_minsort(false, add(n, x), y) -> minsort(x, add(n, y))

The set E consists of the following equations:

   eq(x, y) == eq(y, x)

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

(36) PisEmptyProof (EQUIVALENT)
The TRS P is empty. Hence, there is no (P,E#,R,E) chain.
----------------------------------------

(37)
YES

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

(38)
Obligation:
The TRS P consists of the following rules:

   IF_MINSORT(true, add(n, x), y) -> MINSORT(app(rm(n, x), y), nil)
   MINSORT(add(n, x), y) -> IF_MINSORT(eq(n, min(add(n, x))), add(n, x), y)
   IF_MINSORT(false, add(n, x), y) -> MINSORT(x, add(n, y))

The TRS R consists of the following rules:

   eq(0, 0) -> true
   eq(0, s(x)) -> false
   eq(s(x), 0) -> false
   eq(s(x), s(y)) -> eq(x, y)
   le(0, y) -> true
   le(s(x), 0) -> false
   le(s(x), s(y)) -> le(x, y)
   app(nil, y) -> y
   app(add(n, x), y) -> add(n, app(x, y))
   min(add(n, nil)) -> n
   min(add(n, add(m, x))) -> if_min(le(n, m), add(n, add(m, x)))
   if_min(true, add(n, add(m, x))) -> min(add(n, x))
   if_min(false, add(n, add(m, x))) -> min(add(m, x))
   rm(n, nil) -> nil
   rm(n, add(m, x)) -> if_rm(eq(n, m), n, add(m, x))
   if_rm(true, n, add(m, x)) -> rm(n, x)
   if_rm(false, n, add(m, x)) -> add(m, rm(n, x))
   minsort(nil, nil) -> nil
   minsort(add(n, x), y) -> if_minsort(eq(n, min(add(n, x))), add(n, x), y)
   if_minsort(true, add(n, x), y) -> add(n, minsort(app(rm(n, x), y), nil))
   if_minsort(false, add(n, x), y) -> minsort(x, add(n, y))

The set E consists of the following equations:

   eq(x, y) == eq(y, x)

The set E# consists of the following equations:

   EQ(x, y) == EQ(y, x)

We have to consider all minimal (P,E#,R,E)-chains
----------------------------------------

(39) ESharpUsableEquationsProof (EQUIVALENT)
We can delete the following equations of E# with the esharp usable equations processor[DA_STEIN]:
   EQ(x, y) == EQ(y, x)

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

(40)
Obligation:
The TRS P consists of the following rules:

   IF_MINSORT(true, add(n, x), y) -> MINSORT(app(rm(n, x), y), nil)
   MINSORT(add(n, x), y) -> IF_MINSORT(eq(n, min(add(n, x))), add(n, x), y)
   IF_MINSORT(false, add(n, x), y) -> MINSORT(x, add(n, y))

The TRS R consists of the following rules:

   eq(0, 0) -> true
   eq(0, s(x)) -> false
   eq(s(x), 0) -> false
   eq(s(x), s(y)) -> eq(x, y)
   le(0, y) -> true
   le(s(x), 0) -> false
   le(s(x), s(y)) -> le(x, y)
   app(nil, y) -> y
   app(add(n, x), y) -> add(n, app(x, y))
   min(add(n, nil)) -> n
   min(add(n, add(m, x))) -> if_min(le(n, m), add(n, add(m, x)))
   if_min(true, add(n, add(m, x))) -> min(add(n, x))
   if_min(false, add(n, add(m, x))) -> min(add(m, x))
   rm(n, nil) -> nil
   rm(n, add(m, x)) -> if_rm(eq(n, m), n, add(m, x))
   if_rm(true, n, add(m, x)) -> rm(n, x)
   if_rm(false, n, add(m, x)) -> add(m, rm(n, x))
   minsort(nil, nil) -> nil
   minsort(add(n, x), y) -> if_minsort(eq(n, min(add(n, x))), add(n, x), y)
   if_minsort(true, add(n, x), y) -> add(n, minsort(app(rm(n, x), y), nil))
   if_minsort(false, add(n, x), y) -> minsort(x, add(n, y))

The set E consists of the following equations:

   eq(x, y) == eq(y, x)

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

(41) EDPPoloProof (EQUIVALENT)
We use the reduction pair processor [DA_STEIN] with a polynomial ordering [POLO]. The following set of Dependency Pairs of this DP problem can be strictly oriented.


   IF_MINSORT(true, add(n, x), y) -> MINSORT(app(rm(n, x), y), nil)
The remaining Dependency Pairs were at least non-strictly oriented.


   MINSORT(add(n, x), y) -> IF_MINSORT(eq(n, min(add(n, x))), add(n, x), y)
   IF_MINSORT(false, add(n, x), y) -> MINSORT(x, add(n, y))
With the implicit AFS we had to orient the following set of usable rules of R non-strictly.


   rm(n, nil) -> nil
   rm(n, add(m, x)) -> if_rm(eq(n, m), n, add(m, x))
   app(add(n, x), y) -> add(n, app(x, y))
   app(nil, y) -> y
   if_rm(false, n, add(m, x)) -> add(m, rm(n, x))
   if_rm(true, n, add(m, x)) -> rm(n, x)
There is no equation of E#.


With the implicit AFS there is no usable equation of E.


Used ordering: POLO with Polynomial interpretation [POLO]:

   POL(0) = 0
   POL(IF_MINSORT(x_1, x_2, x_3)) = x_2 + x_3
   POL(MINSORT(x_1, x_2)) = x_1 + x_2
   POL(add(x_1, x_2)) = 2 + x_2
   POL(app(x_1, x_2)) = x_1 + x_2
   POL(eq(x_1, x_2)) = 0
   POL(false) = 0
   POL(if_min(x_1, x_2)) = 2
   POL(if_rm(x_1, x_2, x_3)) = x_3
   POL(le(x_1, x_2)) = 0
   POL(min(x_1)) = 0
   POL(nil) = 0
   POL(rm(x_1, x_2)) = x_2
   POL(s(x_1)) = 0
   POL(true) = 0


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

(42)
Obligation:
The TRS P consists of the following rules:

   MINSORT(add(n, x), y) -> IF_MINSORT(eq(n, min(add(n, x))), add(n, x), y)
   IF_MINSORT(false, add(n, x), y) -> MINSORT(x, add(n, y))

The TRS R consists of the following rules:

   eq(0, 0) -> true
   eq(0, s(x)) -> false
   eq(s(x), 0) -> false
   eq(s(x), s(y)) -> eq(x, y)
   le(0, y) -> true
   le(s(x), 0) -> false
   le(s(x), s(y)) -> le(x, y)
   app(nil, y) -> y
   app(add(n, x), y) -> add(n, app(x, y))
   min(add(n, nil)) -> n
   min(add(n, add(m, x))) -> if_min(le(n, m), add(n, add(m, x)))
   if_min(true, add(n, add(m, x))) -> min(add(n, x))
   if_min(false, add(n, add(m, x))) -> min(add(m, x))
   rm(n, nil) -> nil
   rm(n, add(m, x)) -> if_rm(eq(n, m), n, add(m, x))
   if_rm(true, n, add(m, x)) -> rm(n, x)
   if_rm(false, n, add(m, x)) -> add(m, rm(n, x))
   minsort(nil, nil) -> nil
   minsort(add(n, x), y) -> if_minsort(eq(n, min(add(n, x))), add(n, x), y)
   if_minsort(true, add(n, x), y) -> add(n, minsort(app(rm(n, x), y), nil))
   if_minsort(false, add(n, x), y) -> minsort(x, add(n, y))

The set E consists of the following equations:

   eq(x, y) == eq(y, x)

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

(43) EDPPoloProof (EQUIVALENT)
We use the reduction pair processor [DA_STEIN] with a polynomial ordering [POLO]. The following set of Dependency Pairs of this DP problem can be strictly oriented.


   IF_MINSORT(false, add(n, x), y) -> MINSORT(x, add(n, y))
The remaining Dependency Pairs were at least non-strictly oriented.


   MINSORT(add(n, x), y) -> IF_MINSORT(eq(n, min(add(n, x))), add(n, x), y)
With the implicit AFS there is no usable rule of R.


There is no equation of E#.


With the implicit AFS there is no usable equation of E.


Used ordering: POLO with Polynomial interpretation [POLO]:

   POL(0) = 0
   POL(IF_MINSORT(x_1, x_2, x_3)) = 2*x_2
   POL(MINSORT(x_1, x_2)) = 2*x_1
   POL(add(x_1, x_2)) = 2 + 2*x_1 + x_2
   POL(eq(x_1, x_2)) = 0
   POL(false) = 0
   POL(if_min(x_1, x_2)) = 2
   POL(le(x_1, x_2)) = 0
   POL(min(x_1)) = 0
   POL(nil) = 0
   POL(s(x_1)) = 0
   POL(true) = 0


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

(44)
Obligation:
The TRS P consists of the following rules:

   MINSORT(add(n, x), y) -> IF_MINSORT(eq(n, min(add(n, x))), add(n, x), y)

The TRS R consists of the following rules:

   eq(0, 0) -> true
   eq(0, s(x)) -> false
   eq(s(x), 0) -> false
   eq(s(x), s(y)) -> eq(x, y)
   le(0, y) -> true
   le(s(x), 0) -> false
   le(s(x), s(y)) -> le(x, y)
   app(nil, y) -> y
   app(add(n, x), y) -> add(n, app(x, y))
   min(add(n, nil)) -> n
   min(add(n, add(m, x))) -> if_min(le(n, m), add(n, add(m, x)))
   if_min(true, add(n, add(m, x))) -> min(add(n, x))
   if_min(false, add(n, add(m, x))) -> min(add(m, x))
   rm(n, nil) -> nil
   rm(n, add(m, x)) -> if_rm(eq(n, m), n, add(m, x))
   if_rm(true, n, add(m, x)) -> rm(n, x)
   if_rm(false, n, add(m, x)) -> add(m, rm(n, x))
   minsort(nil, nil) -> nil
   minsort(add(n, x), y) -> if_minsort(eq(n, min(add(n, x))), add(n, x), y)
   if_minsort(true, add(n, x), y) -> add(n, minsort(app(rm(n, x), y), nil))
   if_minsort(false, add(n, x), y) -> minsort(x, add(n, y))

The set E consists of the following equations:

   eq(x, y) == eq(y, x)

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

(45) EDependencyGraphProof (EQUIVALENT)
The approximation of the Equational Dependency Graph [DA_STEIN] contains 0 SCCs with 1 less node.
----------------------------------------

(46)
TRUE