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


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


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


Termination of the given ITRS could be proven:

(0) ITRS
(1) ITRStoIDPProof [EQUIVALENT, 0 ms]
(2) IDP
(3) UsableRulesProof [EQUIVALENT, 0 ms]
(4) IDP
(5) IDependencyGraphProof [EQUIVALENT, 0 ms]
(6) AND
    (7) IDP
        (8) UsableRulesProof [EQUIVALENT, 0 ms]
        (9) IDP
        (10) IDPtoQDPProof [SOUND, 35 ms]
        (11) QDP
        (12) QReductionProof [EQUIVALENT, 0 ms]
        (13) QDP
        (14) QDPSizeChangeProof [EQUIVALENT, 0 ms]
        (15) YES
    (16) IDP
        (17) IDPtoQDPProof [SOUND, 0 ms]
        (18) QDP
        (19) QReductionProof [EQUIVALENT, 0 ms]
        (20) QDP
        (21) QDPOrderProof [EQUIVALENT, 99 ms]
        (22) QDP
        (23) DependencyGraphProof [EQUIVALENT, 0 ms]
        (24) TRUE


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

(0)
Obligation:
ITRS problem:

The following function symbols are pre-defined:
<<<
 & 	~ 	Bwand: (Integer, Integer) -> Integer
 >= 	~ 	Ge: (Integer, Integer) -> Boolean
 | 	~ 	Bwor: (Integer, Integer) -> Integer
 / 	~ 	Div: (Integer, Integer) -> Integer
 != 	~ 	Neq: (Integer, Integer) -> Boolean
 && 	~ 	Land: (Boolean, Boolean) -> Boolean
 ! 	~ 	Lnot: (Boolean) -> Boolean
 = 	~ 	Eq: (Integer, Integer) -> Boolean
 <= 	~ 	Le: (Integer, Integer) -> Boolean
 ^ 	~ 	Bwxor: (Integer, Integer) -> Integer
 % 	~ 	Mod: (Integer, Integer) -> Integer
 > 	~ 	Gt: (Integer, Integer) -> Boolean
 + 	~ 	Add: (Integer, Integer) -> Integer
 -1 	~ 	UnaryMinus: (Integer) -> Integer
 < 	~ 	Lt: (Integer, Integer) -> Boolean
 || 	~ 	Lor: (Boolean, Boolean) -> Boolean
 - 	~ 	Sub: (Integer, Integer) -> Integer
 ~ 	~ 	Bwnot: (Integer) -> Integer
 * 	~ 	Mul: (Integer, Integer) -> Integer
>>>

The TRS R consists of the following rules:
min(x, e) -> pair(x, e)
min(x, ins(y, zs)) -> if_1(min(y, zs), x, y, zs)
if_1(pair(m, zh), x, y, zs) -> Cond_if_1(m > x, pair(m, zh), x, y, zs)
Cond_if_1(TRUE, pair(m, zh), x, y, zs) -> pair(x, ins(m, zh))
min(x, ins(y, zs)) -> if_2(min(y, zs), x, y, zs)
if_2(pair(m, zh), x, y, zs) -> Cond_if_2(x >= m, pair(m, zh), x, y, zs)
Cond_if_2(TRUE, pair(m, zh), x, y, zs) -> pair(m, ins(x, zh))
msort(e) -> nil
msort(ins(x, ys)) -> if_3(min(x, ys), x, ys)
if_3(pair(m, zs), x, ys) -> cons(m, msort(zs))
The set Q consists of the following terms:
min(x0, e)
min(x0, ins(x1, x2))
if_1(pair(x0, x1), x2, x3, x4)
Cond_if_1(TRUE, pair(x0, x1), x2, x3, x4)
if_2(pair(x0, x1), x2, x3, x4)
Cond_if_2(TRUE, pair(x0, x1), x2, x3, x4)
msort(e)
msort(ins(x0, x1))
if_3(pair(x0, x1), x2, x3)

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

(1) ITRStoIDPProof (EQUIVALENT)
Added dependency pairs
----------------------------------------

(2)
Obligation:
IDP problem:
The following function symbols are pre-defined:
<<<
 & 	~ 	Bwand: (Integer, Integer) -> Integer
 >= 	~ 	Ge: (Integer, Integer) -> Boolean
 | 	~ 	Bwor: (Integer, Integer) -> Integer
 / 	~ 	Div: (Integer, Integer) -> Integer
 != 	~ 	Neq: (Integer, Integer) -> Boolean
 && 	~ 	Land: (Boolean, Boolean) -> Boolean
 ! 	~ 	Lnot: (Boolean) -> Boolean
 = 	~ 	Eq: (Integer, Integer) -> Boolean
 <= 	~ 	Le: (Integer, Integer) -> Boolean
 ^ 	~ 	Bwxor: (Integer, Integer) -> Integer
 % 	~ 	Mod: (Integer, Integer) -> Integer
 > 	~ 	Gt: (Integer, Integer) -> Boolean
 + 	~ 	Add: (Integer, Integer) -> Integer
 -1 	~ 	UnaryMinus: (Integer) -> Integer
 < 	~ 	Lt: (Integer, Integer) -> Boolean
 || 	~ 	Lor: (Boolean, Boolean) -> Boolean
 - 	~ 	Sub: (Integer, Integer) -> Integer
 ~ 	~ 	Bwnot: (Integer) -> Integer
 * 	~ 	Mul: (Integer, Integer) -> Integer
>>>


The following domains are used:
   Integer

The ITRS R consists of the following rules:
min(x, e) -> pair(x, e)
min(x, ins(y, zs)) -> if_1(min(y, zs), x, y, zs)
if_1(pair(m, zh), x, y, zs) -> Cond_if_1(m > x, pair(m, zh), x, y, zs)
Cond_if_1(TRUE, pair(m, zh), x, y, zs) -> pair(x, ins(m, zh))
min(x, ins(y, zs)) -> if_2(min(y, zs), x, y, zs)
if_2(pair(m, zh), x, y, zs) -> Cond_if_2(x >= m, pair(m, zh), x, y, zs)
Cond_if_2(TRUE, pair(m, zh), x, y, zs) -> pair(m, ins(x, zh))
msort(e) -> nil
msort(ins(x, ys)) -> if_3(min(x, ys), x, ys)
if_3(pair(m, zs), x, ys) -> cons(m, msort(zs))

The integer pair graph contains the following rules and edges:
(0): MIN(x[0], ins(y[0], zs[0])) -> IF_1(min(y[0], zs[0]), x[0], y[0], zs[0])
(1): MIN(x[1], ins(y[1], zs[1])) -> MIN(y[1], zs[1])
(2): IF_1(pair(m[2], zh[2]), x[2], y[2], zs[2]) -> COND_IF_1(m[2] > x[2], pair(m[2], zh[2]), x[2], y[2], zs[2])
(3): MIN(x[3], ins(y[3], zs[3])) -> IF_2(min(y[3], zs[3]), x[3], y[3], zs[3])
(4): IF_2(pair(m[4], zh[4]), x[4], y[4], zs[4]) -> COND_IF_2(x[4] >= m[4], pair(m[4], zh[4]), x[4], y[4], zs[4])
(5): MSORT(ins(x[5], ys[5])) -> IF_3(min(x[5], ys[5]), x[5], ys[5])
(6): MSORT(ins(x[6], ys[6])) -> MIN(x[6], ys[6])
(7): IF_3(pair(m[7], zs[7]), x[7], ys[7]) -> MSORT(zs[7])

   (0) -> (2), if (min(y[0], zs[0]) ->^* pair(m[2], zh[2]) & x[0] ->^* x[2] & y[0] ->^* y[2] & zs[0] ->^* zs[2])
   (1) -> (0), if (y[1] ->^* x[0] & zs[1] ->^* ins(y[0], zs[0]))
   (1) -> (1), if (y[1] ->^* x[1]' & zs[1] ->^* ins(y[1]', zs[1]'))
   (1) -> (3), if (y[1] ->^* x[3] & zs[1] ->^* ins(y[3], zs[3]))
   (3) -> (4), if (min(y[3], zs[3]) ->^* pair(m[4], zh[4]) & x[3] ->^* x[4] & y[3] ->^* y[4] & zs[3] ->^* zs[4])
   (5) -> (7), if (min(x[5], ys[5]) ->^* pair(m[7], zs[7]) & x[5] ->^* x[7] & ys[5] ->^* ys[7])
   (6) -> (0), if (x[6] ->^* x[0] & ys[6] ->^* ins(y[0], zs[0]))
   (6) -> (1), if (x[6] ->^* x[1] & ys[6] ->^* ins(y[1], zs[1]))
   (6) -> (3), if (x[6] ->^* x[3] & ys[6] ->^* ins(y[3], zs[3]))
   (7) -> (5), if (zs[7] ->^* ins(x[5], ys[5]))
   (7) -> (6), if (zs[7] ->^* ins(x[6], ys[6]))

The set Q consists of the following terms:
min(x0, e)
min(x0, ins(x1, x2))
if_1(pair(x0, x1), x2, x3, x4)
Cond_if_1(TRUE, pair(x0, x1), x2, x3, x4)
if_2(pair(x0, x1), x2, x3, x4)
Cond_if_2(TRUE, pair(x0, x1), x2, x3, x4)
msort(e)
msort(ins(x0, x1))
if_3(pair(x0, x1), x2, x3)

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

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

(4)
Obligation:
IDP problem:
The following function symbols are pre-defined:
<<<
 & 	~ 	Bwand: (Integer, Integer) -> Integer
 >= 	~ 	Ge: (Integer, Integer) -> Boolean
 | 	~ 	Bwor: (Integer, Integer) -> Integer
 / 	~ 	Div: (Integer, Integer) -> Integer
 != 	~ 	Neq: (Integer, Integer) -> Boolean
 && 	~ 	Land: (Boolean, Boolean) -> Boolean
 ! 	~ 	Lnot: (Boolean) -> Boolean
 = 	~ 	Eq: (Integer, Integer) -> Boolean
 <= 	~ 	Le: (Integer, Integer) -> Boolean
 ^ 	~ 	Bwxor: (Integer, Integer) -> Integer
 % 	~ 	Mod: (Integer, Integer) -> Integer
 > 	~ 	Gt: (Integer, Integer) -> Boolean
 + 	~ 	Add: (Integer, Integer) -> Integer
 -1 	~ 	UnaryMinus: (Integer) -> Integer
 < 	~ 	Lt: (Integer, Integer) -> Boolean
 || 	~ 	Lor: (Boolean, Boolean) -> Boolean
 - 	~ 	Sub: (Integer, Integer) -> Integer
 ~ 	~ 	Bwnot: (Integer) -> Integer
 * 	~ 	Mul: (Integer, Integer) -> Integer
>>>


The following domains are used:
   Integer

The ITRS R consists of the following rules:
min(x, e) -> pair(x, e)
min(x, ins(y, zs)) -> if_1(min(y, zs), x, y, zs)
min(x, ins(y, zs)) -> if_2(min(y, zs), x, y, zs)
if_2(pair(m, zh), x, y, zs) -> Cond_if_2(x >= m, pair(m, zh), x, y, zs)
if_1(pair(m, zh), x, y, zs) -> Cond_if_1(m > x, pair(m, zh), x, y, zs)
Cond_if_1(TRUE, pair(m, zh), x, y, zs) -> pair(x, ins(m, zh))
Cond_if_2(TRUE, pair(m, zh), x, y, zs) -> pair(m, ins(x, zh))

The integer pair graph contains the following rules and edges:
(0): MIN(x[0], ins(y[0], zs[0])) -> IF_1(min(y[0], zs[0]), x[0], y[0], zs[0])
(1): MIN(x[1], ins(y[1], zs[1])) -> MIN(y[1], zs[1])
(2): IF_1(pair(m[2], zh[2]), x[2], y[2], zs[2]) -> COND_IF_1(m[2] > x[2], pair(m[2], zh[2]), x[2], y[2], zs[2])
(3): MIN(x[3], ins(y[3], zs[3])) -> IF_2(min(y[3], zs[3]), x[3], y[3], zs[3])
(4): IF_2(pair(m[4], zh[4]), x[4], y[4], zs[4]) -> COND_IF_2(x[4] >= m[4], pair(m[4], zh[4]), x[4], y[4], zs[4])
(5): MSORT(ins(x[5], ys[5])) -> IF_3(min(x[5], ys[5]), x[5], ys[5])
(6): MSORT(ins(x[6], ys[6])) -> MIN(x[6], ys[6])
(7): IF_3(pair(m[7], zs[7]), x[7], ys[7]) -> MSORT(zs[7])

   (0) -> (2), if (min(y[0], zs[0]) ->^* pair(m[2], zh[2]) & x[0] ->^* x[2] & y[0] ->^* y[2] & zs[0] ->^* zs[2])
   (1) -> (0), if (y[1] ->^* x[0] & zs[1] ->^* ins(y[0], zs[0]))
   (1) -> (1), if (y[1] ->^* x[1]' & zs[1] ->^* ins(y[1]', zs[1]'))
   (1) -> (3), if (y[1] ->^* x[3] & zs[1] ->^* ins(y[3], zs[3]))
   (3) -> (4), if (min(y[3], zs[3]) ->^* pair(m[4], zh[4]) & x[3] ->^* x[4] & y[3] ->^* y[4] & zs[3] ->^* zs[4])
   (5) -> (7), if (min(x[5], ys[5]) ->^* pair(m[7], zs[7]) & x[5] ->^* x[7] & ys[5] ->^* ys[7])
   (6) -> (0), if (x[6] ->^* x[0] & ys[6] ->^* ins(y[0], zs[0]))
   (6) -> (1), if (x[6] ->^* x[1] & ys[6] ->^* ins(y[1], zs[1]))
   (6) -> (3), if (x[6] ->^* x[3] & ys[6] ->^* ins(y[3], zs[3]))
   (7) -> (5), if (zs[7] ->^* ins(x[5], ys[5]))
   (7) -> (6), if (zs[7] ->^* ins(x[6], ys[6]))

The set Q consists of the following terms:
min(x0, e)
min(x0, ins(x1, x2))
if_1(pair(x0, x1), x2, x3, x4)
Cond_if_1(TRUE, pair(x0, x1), x2, x3, x4)
if_2(pair(x0, x1), x2, x3, x4)
Cond_if_2(TRUE, pair(x0, x1), x2, x3, x4)
msort(e)
msort(ins(x0, x1))
if_3(pair(x0, x1), x2, x3)

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

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

(6)
Complex Obligation (AND)

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

(7)
Obligation:
IDP problem:
The following function symbols are pre-defined:
<<<
 & 	~ 	Bwand: (Integer, Integer) -> Integer
 >= 	~ 	Ge: (Integer, Integer) -> Boolean
 | 	~ 	Bwor: (Integer, Integer) -> Integer
 / 	~ 	Div: (Integer, Integer) -> Integer
 != 	~ 	Neq: (Integer, Integer) -> Boolean
 && 	~ 	Land: (Boolean, Boolean) -> Boolean
 ! 	~ 	Lnot: (Boolean) -> Boolean
 = 	~ 	Eq: (Integer, Integer) -> Boolean
 <= 	~ 	Le: (Integer, Integer) -> Boolean
 ^ 	~ 	Bwxor: (Integer, Integer) -> Integer
 % 	~ 	Mod: (Integer, Integer) -> Integer
 > 	~ 	Gt: (Integer, Integer) -> Boolean
 + 	~ 	Add: (Integer, Integer) -> Integer
 -1 	~ 	UnaryMinus: (Integer) -> Integer
 < 	~ 	Lt: (Integer, Integer) -> Boolean
 || 	~ 	Lor: (Boolean, Boolean) -> Boolean
 - 	~ 	Sub: (Integer, Integer) -> Integer
 ~ 	~ 	Bwnot: (Integer) -> Integer
 * 	~ 	Mul: (Integer, Integer) -> Integer
>>>


The following domains are used:
   Integer

The ITRS R consists of the following rules:
min(x, e) -> pair(x, e)
min(x, ins(y, zs)) -> if_1(min(y, zs), x, y, zs)
min(x, ins(y, zs)) -> if_2(min(y, zs), x, y, zs)
if_2(pair(m, zh), x, y, zs) -> Cond_if_2(x >= m, pair(m, zh), x, y, zs)
if_1(pair(m, zh), x, y, zs) -> Cond_if_1(m > x, pair(m, zh), x, y, zs)
Cond_if_1(TRUE, pair(m, zh), x, y, zs) -> pair(x, ins(m, zh))
Cond_if_2(TRUE, pair(m, zh), x, y, zs) -> pair(m, ins(x, zh))

The integer pair graph contains the following rules and edges:
(1): MIN(x[1], ins(y[1], zs[1])) -> MIN(y[1], zs[1])

   (1) -> (1), if (y[1] ->^* x[1]' & zs[1] ->^* ins(y[1]', zs[1]'))

The set Q consists of the following terms:
min(x0, e)
min(x0, ins(x1, x2))
if_1(pair(x0, x1), x2, x3, x4)
Cond_if_1(TRUE, pair(x0, x1), x2, x3, x4)
if_2(pair(x0, x1), x2, x3, x4)
Cond_if_2(TRUE, pair(x0, x1), x2, x3, x4)
msort(e)
msort(ins(x0, x1))
if_3(pair(x0, x1), x2, x3)

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

(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:
IDP problem:
The following function symbols are pre-defined:
<<<
 & 	~ 	Bwand: (Integer, Integer) -> Integer
 >= 	~ 	Ge: (Integer, Integer) -> Boolean
 | 	~ 	Bwor: (Integer, Integer) -> Integer
 / 	~ 	Div: (Integer, Integer) -> Integer
 != 	~ 	Neq: (Integer, Integer) -> Boolean
 && 	~ 	Land: (Boolean, Boolean) -> Boolean
 ! 	~ 	Lnot: (Boolean) -> Boolean
 = 	~ 	Eq: (Integer, Integer) -> Boolean
 <= 	~ 	Le: (Integer, Integer) -> Boolean
 ^ 	~ 	Bwxor: (Integer, Integer) -> Integer
 % 	~ 	Mod: (Integer, Integer) -> Integer
 > 	~ 	Gt: (Integer, Integer) -> Boolean
 + 	~ 	Add: (Integer, Integer) -> Integer
 -1 	~ 	UnaryMinus: (Integer) -> Integer
 < 	~ 	Lt: (Integer, Integer) -> Boolean
 || 	~ 	Lor: (Boolean, Boolean) -> Boolean
 - 	~ 	Sub: (Integer, Integer) -> Integer
 ~ 	~ 	Bwnot: (Integer) -> Integer
 * 	~ 	Mul: (Integer, Integer) -> Integer
>>>


The following domains are used:
none

R is empty.

The integer pair graph contains the following rules and edges:
(1): MIN(x[1], ins(y[1], zs[1])) -> MIN(y[1], zs[1])

   (1) -> (1), if (y[1] ->^* x[1]' & zs[1] ->^* ins(y[1]', zs[1]'))

The set Q consists of the following terms:
min(x0, e)
min(x0, ins(x1, x2))
if_1(pair(x0, x1), x2, x3, x4)
Cond_if_1(TRUE, pair(x0, x1), x2, x3, x4)
if_2(pair(x0, x1), x2, x3, x4)
Cond_if_2(TRUE, pair(x0, x1), x2, x3, x4)
msort(e)
msort(ins(x0, x1))
if_3(pair(x0, x1), x2, x3)

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

(10) IDPtoQDPProof (SOUND)
Represented integers and predefined function symbols by Terms
----------------------------------------

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

   MIN(x[1], ins(y[1], zs[1])) -> MIN(y[1], zs[1])

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

   min(x0, e)
   min(x0, ins(x1, x2))
   if_1(pair(x0, x1), x2, x3, x4)
   Cond_if_1(true, pair(x0, x1), x2, x3, x4)
   if_2(pair(x0, x1), x2, x3, x4)
   Cond_if_2(true, pair(x0, x1), x2, x3, x4)
   msort(e)
   msort(ins(x0, x1))
   if_3(pair(x0, x1), x2, x3)

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

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

   min(x0, e)
   min(x0, ins(x1, x2))
   if_1(pair(x0, x1), x2, x3, x4)
   Cond_if_1(true, pair(x0, x1), x2, x3, x4)
   if_2(pair(x0, x1), x2, x3, x4)
   Cond_if_2(true, pair(x0, x1), x2, x3, x4)
   msort(e)
   msort(ins(x0, x1))
   if_3(pair(x0, x1), x2, x3)


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

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

   MIN(x[1], ins(y[1], zs[1])) -> MIN(y[1], zs[1])

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

(14) 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:
*MIN(x[1], ins(y[1], zs[1])) -> MIN(y[1], zs[1])
The graph contains the following edges 2 > 1, 2 > 2


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

(15)
YES

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

(16)
Obligation:
IDP problem:
The following function symbols are pre-defined:
<<<
 & 	~ 	Bwand: (Integer, Integer) -> Integer
 >= 	~ 	Ge: (Integer, Integer) -> Boolean
 | 	~ 	Bwor: (Integer, Integer) -> Integer
 / 	~ 	Div: (Integer, Integer) -> Integer
 != 	~ 	Neq: (Integer, Integer) -> Boolean
 && 	~ 	Land: (Boolean, Boolean) -> Boolean
 ! 	~ 	Lnot: (Boolean) -> Boolean
 = 	~ 	Eq: (Integer, Integer) -> Boolean
 <= 	~ 	Le: (Integer, Integer) -> Boolean
 ^ 	~ 	Bwxor: (Integer, Integer) -> Integer
 % 	~ 	Mod: (Integer, Integer) -> Integer
 > 	~ 	Gt: (Integer, Integer) -> Boolean
 + 	~ 	Add: (Integer, Integer) -> Integer
 -1 	~ 	UnaryMinus: (Integer) -> Integer
 < 	~ 	Lt: (Integer, Integer) -> Boolean
 || 	~ 	Lor: (Boolean, Boolean) -> Boolean
 - 	~ 	Sub: (Integer, Integer) -> Integer
 ~ 	~ 	Bwnot: (Integer) -> Integer
 * 	~ 	Mul: (Integer, Integer) -> Integer
>>>


The following domains are used:
   Integer

The ITRS R consists of the following rules:
min(x, e) -> pair(x, e)
min(x, ins(y, zs)) -> if_1(min(y, zs), x, y, zs)
min(x, ins(y, zs)) -> if_2(min(y, zs), x, y, zs)
if_2(pair(m, zh), x, y, zs) -> Cond_if_2(x >= m, pair(m, zh), x, y, zs)
if_1(pair(m, zh), x, y, zs) -> Cond_if_1(m > x, pair(m, zh), x, y, zs)
Cond_if_1(TRUE, pair(m, zh), x, y, zs) -> pair(x, ins(m, zh))
Cond_if_2(TRUE, pair(m, zh), x, y, zs) -> pair(m, ins(x, zh))

The integer pair graph contains the following rules and edges:
(7): IF_3(pair(m[7], zs[7]), x[7], ys[7]) -> MSORT(zs[7])
(5): MSORT(ins(x[5], ys[5])) -> IF_3(min(x[5], ys[5]), x[5], ys[5])

   (7) -> (5), if (zs[7] ->^* ins(x[5], ys[5]))
   (5) -> (7), if (min(x[5], ys[5]) ->^* pair(m[7], zs[7]) & x[5] ->^* x[7] & ys[5] ->^* ys[7])

The set Q consists of the following terms:
min(x0, e)
min(x0, ins(x1, x2))
if_1(pair(x0, x1), x2, x3, x4)
Cond_if_1(TRUE, pair(x0, x1), x2, x3, x4)
if_2(pair(x0, x1), x2, x3, x4)
Cond_if_2(TRUE, pair(x0, x1), x2, x3, x4)
msort(e)
msort(ins(x0, x1))
if_3(pair(x0, x1), x2, x3)

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

(17) IDPtoQDPProof (SOUND)
Represented integers and predefined function symbols by Terms
----------------------------------------

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

   IF_3(pair(m[7], zs[7]), x[7], ys[7]) -> MSORT(zs[7])
   MSORT(ins(x[5], ys[5])) -> IF_3(min(x[5], ys[5]), x[5], ys[5])

The TRS R consists of the following rules:

   min(x, e) -> pair(x, e)
   min(x, ins(y, zs)) -> if_1(min(y, zs), x, y, zs)
   min(x, ins(y, zs)) -> if_2(min(y, zs), x, y, zs)
   if_2(pair(m, zh), x, y, zs) -> Cond_if_2(greatereq_int(x, m), pair(m, zh), x, y, zs)
   if_1(pair(m, zh), x, y, zs) -> Cond_if_1(greater_int(m, x), pair(m, zh), x, y, zs)
   Cond_if_1(true, pair(m, zh), x, y, zs) -> pair(x, ins(m, zh))
   Cond_if_2(true, pair(m, zh), x, y, zs) -> pair(m, ins(x, zh))
   greatereq_int(pos(x), pos(0)) -> true
   greatereq_int(neg(0), pos(0)) -> true
   greatereq_int(neg(0), neg(y)) -> true
   greatereq_int(pos(x), neg(y)) -> true
   greatereq_int(pos(0), pos(s(y))) -> false
   greatereq_int(neg(x), pos(s(y))) -> false
   greatereq_int(neg(s(x)), pos(0)) -> false
   greatereq_int(neg(s(x)), neg(0)) -> false
   greatereq_int(pos(s(x)), pos(s(y))) -> greatereq_int(pos(x), pos(y))
   greatereq_int(neg(s(x)), neg(s(y))) -> greatereq_int(neg(x), neg(y))
   greater_int(pos(0), pos(0)) -> false
   greater_int(pos(0), neg(0)) -> false
   greater_int(neg(0), pos(0)) -> false
   greater_int(neg(0), neg(0)) -> false
   greater_int(pos(0), pos(s(y))) -> false
   greater_int(neg(0), pos(s(y))) -> false
   greater_int(pos(0), neg(s(y))) -> true
   greater_int(neg(0), neg(s(y))) -> true
   greater_int(pos(s(x)), pos(0)) -> true
   greater_int(neg(s(x)), pos(0)) -> false
   greater_int(pos(s(x)), neg(0)) -> true
   greater_int(neg(s(x)), neg(0)) -> false
   greater_int(pos(s(x)), neg(s(y))) -> true
   greater_int(neg(s(x)), pos(s(y))) -> false
   greater_int(pos(s(x)), pos(s(y))) -> greater_int(pos(x), pos(y))
   greater_int(neg(s(x)), neg(s(y))) -> greater_int(neg(x), neg(y))

The set Q consists of the following terms:

   min(x0, e)
   min(x0, ins(x1, x2))
   if_1(pair(x0, x1), x2, x3, x4)
   Cond_if_1(true, pair(x0, x1), x2, x3, x4)
   if_2(pair(x0, x1), x2, x3, x4)
   Cond_if_2(true, pair(x0, x1), x2, x3, x4)
   msort(e)
   msort(ins(x0, x1))
   if_3(pair(x0, x1), x2, x3)
   greatereq_int(pos(x0), pos(0))
   greatereq_int(neg(0), pos(0))
   greatereq_int(neg(0), neg(x0))
   greatereq_int(pos(x0), neg(x1))
   greatereq_int(pos(0), pos(s(x0)))
   greatereq_int(neg(x0), pos(s(x1)))
   greatereq_int(neg(s(x0)), pos(0))
   greatereq_int(neg(s(x0)), neg(0))
   greatereq_int(pos(s(x0)), pos(s(x1)))
   greatereq_int(neg(s(x0)), neg(s(x1)))
   greater_int(pos(0), pos(0))
   greater_int(pos(0), neg(0))
   greater_int(neg(0), pos(0))
   greater_int(neg(0), neg(0))
   greater_int(pos(0), pos(s(x0)))
   greater_int(neg(0), pos(s(x0)))
   greater_int(pos(0), neg(s(x0)))
   greater_int(neg(0), neg(s(x0)))
   greater_int(pos(s(x0)), pos(0))
   greater_int(neg(s(x0)), pos(0))
   greater_int(pos(s(x0)), neg(0))
   greater_int(neg(s(x0)), neg(0))
   greater_int(pos(s(x0)), neg(s(x1)))
   greater_int(neg(s(x0)), pos(s(x1)))
   greater_int(pos(s(x0)), pos(s(x1)))
   greater_int(neg(s(x0)), neg(s(x1)))

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

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

   msort(e)
   msort(ins(x0, x1))
   if_3(pair(x0, x1), x2, x3)


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

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

   IF_3(pair(m[7], zs[7]), x[7], ys[7]) -> MSORT(zs[7])
   MSORT(ins(x[5], ys[5])) -> IF_3(min(x[5], ys[5]), x[5], ys[5])

The TRS R consists of the following rules:

   min(x, e) -> pair(x, e)
   min(x, ins(y, zs)) -> if_1(min(y, zs), x, y, zs)
   min(x, ins(y, zs)) -> if_2(min(y, zs), x, y, zs)
   if_2(pair(m, zh), x, y, zs) -> Cond_if_2(greatereq_int(x, m), pair(m, zh), x, y, zs)
   if_1(pair(m, zh), x, y, zs) -> Cond_if_1(greater_int(m, x), pair(m, zh), x, y, zs)
   Cond_if_1(true, pair(m, zh), x, y, zs) -> pair(x, ins(m, zh))
   Cond_if_2(true, pair(m, zh), x, y, zs) -> pair(m, ins(x, zh))
   greatereq_int(pos(x), pos(0)) -> true
   greatereq_int(neg(0), pos(0)) -> true
   greatereq_int(neg(0), neg(y)) -> true
   greatereq_int(pos(x), neg(y)) -> true
   greatereq_int(pos(0), pos(s(y))) -> false
   greatereq_int(neg(x), pos(s(y))) -> false
   greatereq_int(neg(s(x)), pos(0)) -> false
   greatereq_int(neg(s(x)), neg(0)) -> false
   greatereq_int(pos(s(x)), pos(s(y))) -> greatereq_int(pos(x), pos(y))
   greatereq_int(neg(s(x)), neg(s(y))) -> greatereq_int(neg(x), neg(y))
   greater_int(pos(0), pos(0)) -> false
   greater_int(pos(0), neg(0)) -> false
   greater_int(neg(0), pos(0)) -> false
   greater_int(neg(0), neg(0)) -> false
   greater_int(pos(0), pos(s(y))) -> false
   greater_int(neg(0), pos(s(y))) -> false
   greater_int(pos(0), neg(s(y))) -> true
   greater_int(neg(0), neg(s(y))) -> true
   greater_int(pos(s(x)), pos(0)) -> true
   greater_int(neg(s(x)), pos(0)) -> false
   greater_int(pos(s(x)), neg(0)) -> true
   greater_int(neg(s(x)), neg(0)) -> false
   greater_int(pos(s(x)), neg(s(y))) -> true
   greater_int(neg(s(x)), pos(s(y))) -> false
   greater_int(pos(s(x)), pos(s(y))) -> greater_int(pos(x), pos(y))
   greater_int(neg(s(x)), neg(s(y))) -> greater_int(neg(x), neg(y))

The set Q consists of the following terms:

   min(x0, e)
   min(x0, ins(x1, x2))
   if_1(pair(x0, x1), x2, x3, x4)
   Cond_if_1(true, pair(x0, x1), x2, x3, x4)
   if_2(pair(x0, x1), x2, x3, x4)
   Cond_if_2(true, pair(x0, x1), x2, x3, x4)
   greatereq_int(pos(x0), pos(0))
   greatereq_int(neg(0), pos(0))
   greatereq_int(neg(0), neg(x0))
   greatereq_int(pos(x0), neg(x1))
   greatereq_int(pos(0), pos(s(x0)))
   greatereq_int(neg(x0), pos(s(x1)))
   greatereq_int(neg(s(x0)), pos(0))
   greatereq_int(neg(s(x0)), neg(0))
   greatereq_int(pos(s(x0)), pos(s(x1)))
   greatereq_int(neg(s(x0)), neg(s(x1)))
   greater_int(pos(0), pos(0))
   greater_int(pos(0), neg(0))
   greater_int(neg(0), pos(0))
   greater_int(neg(0), neg(0))
   greater_int(pos(0), pos(s(x0)))
   greater_int(neg(0), pos(s(x0)))
   greater_int(pos(0), neg(s(x0)))
   greater_int(neg(0), neg(s(x0)))
   greater_int(pos(s(x0)), pos(0))
   greater_int(neg(s(x0)), pos(0))
   greater_int(pos(s(x0)), neg(0))
   greater_int(neg(s(x0)), neg(0))
   greater_int(pos(s(x0)), neg(s(x1)))
   greater_int(neg(s(x0)), pos(s(x1)))
   greater_int(pos(s(x0)), pos(s(x1)))
   greater_int(neg(s(x0)), neg(s(x1)))

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

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


The following pairs can be oriented strictly and are deleted.

   MSORT(ins(x[5], ys[5])) -> IF_3(min(x[5], ys[5]), x[5], ys[5])
The remaining pairs can at least be oriented weakly.
Used ordering:  Polynomial Order [NEGPOLO,POLO] with Interpretation:

POL( IF_3_3(x_1, ..., x_3) ) = max{0, x_1 - 2}
POL( min_2(x_1, x_2) ) = 2x_2
POL( e ) = 2
POL( pair_2(x_1, x_2) ) = x_2 + 2
POL( ins_2(x_1, x_2) ) = 2x_2 + 1
POL( if_1_4(x_1, ..., x_4) ) = max{0, 2x_1 - 1}
POL( if_2_4(x_1, ..., x_4) ) = 2x_1
POL( Cond_if_2_5(x_1, ..., x_5) ) = max{0, 2x_2 - 1}
POL( greatereq_int_2(x_1, x_2) ) = max{0, -2}
POL( Cond_if_1_5(x_1, ..., x_5) ) = max{0, x_1 + 2x_2 - 2}
POL( greater_int_2(x_1, x_2) ) = 1
POL( pos_1(x_1) ) = 0
POL( 0 ) = 0
POL( true ) = 1
POL( neg_1(x_1) ) = 0
POL( s_1(x_1) ) = 0
POL( false ) = 0
POL( MSORT_1(x_1) ) = x_1

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

   min(x, e) -> pair(x, e)
   min(x, ins(y, zs)) -> if_1(min(y, zs), x, y, zs)
   min(x, ins(y, zs)) -> if_2(min(y, zs), x, y, zs)
   if_2(pair(m, zh), x, y, zs) -> Cond_if_2(greatereq_int(x, m), pair(m, zh), x, y, zs)
   if_1(pair(m, zh), x, y, zs) -> Cond_if_1(greater_int(m, x), pair(m, zh), x, y, zs)
   Cond_if_2(true, pair(m, zh), x, y, zs) -> pair(m, ins(x, zh))
   greater_int(pos(0), pos(0)) -> false
   greater_int(pos(0), neg(0)) -> false
   greater_int(neg(0), pos(0)) -> false
   greater_int(neg(0), neg(0)) -> false
   greater_int(pos(0), pos(s(y))) -> false
   greater_int(neg(0), pos(s(y))) -> false
   greater_int(pos(0), neg(s(y))) -> true
   greater_int(neg(0), neg(s(y))) -> true
   greater_int(pos(s(x)), pos(0)) -> true
   greater_int(neg(s(x)), pos(0)) -> false
   greater_int(pos(s(x)), neg(0)) -> true
   greater_int(neg(s(x)), neg(0)) -> false
   greater_int(pos(s(x)), neg(s(y))) -> true
   greater_int(neg(s(x)), pos(s(y))) -> false
   greater_int(pos(s(x)), pos(s(y))) -> greater_int(pos(x), pos(y))
   greater_int(neg(s(x)), neg(s(y))) -> greater_int(neg(x), neg(y))
   Cond_if_1(true, pair(m, zh), x, y, zs) -> pair(x, ins(m, zh))


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

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

   IF_3(pair(m[7], zs[7]), x[7], ys[7]) -> MSORT(zs[7])

The TRS R consists of the following rules:

   min(x, e) -> pair(x, e)
   min(x, ins(y, zs)) -> if_1(min(y, zs), x, y, zs)
   min(x, ins(y, zs)) -> if_2(min(y, zs), x, y, zs)
   if_2(pair(m, zh), x, y, zs) -> Cond_if_2(greatereq_int(x, m), pair(m, zh), x, y, zs)
   if_1(pair(m, zh), x, y, zs) -> Cond_if_1(greater_int(m, x), pair(m, zh), x, y, zs)
   Cond_if_1(true, pair(m, zh), x, y, zs) -> pair(x, ins(m, zh))
   Cond_if_2(true, pair(m, zh), x, y, zs) -> pair(m, ins(x, zh))
   greatereq_int(pos(x), pos(0)) -> true
   greatereq_int(neg(0), pos(0)) -> true
   greatereq_int(neg(0), neg(y)) -> true
   greatereq_int(pos(x), neg(y)) -> true
   greatereq_int(pos(0), pos(s(y))) -> false
   greatereq_int(neg(x), pos(s(y))) -> false
   greatereq_int(neg(s(x)), pos(0)) -> false
   greatereq_int(neg(s(x)), neg(0)) -> false
   greatereq_int(pos(s(x)), pos(s(y))) -> greatereq_int(pos(x), pos(y))
   greatereq_int(neg(s(x)), neg(s(y))) -> greatereq_int(neg(x), neg(y))
   greater_int(pos(0), pos(0)) -> false
   greater_int(pos(0), neg(0)) -> false
   greater_int(neg(0), pos(0)) -> false
   greater_int(neg(0), neg(0)) -> false
   greater_int(pos(0), pos(s(y))) -> false
   greater_int(neg(0), pos(s(y))) -> false
   greater_int(pos(0), neg(s(y))) -> true
   greater_int(neg(0), neg(s(y))) -> true
   greater_int(pos(s(x)), pos(0)) -> true
   greater_int(neg(s(x)), pos(0)) -> false
   greater_int(pos(s(x)), neg(0)) -> true
   greater_int(neg(s(x)), neg(0)) -> false
   greater_int(pos(s(x)), neg(s(y))) -> true
   greater_int(neg(s(x)), pos(s(y))) -> false
   greater_int(pos(s(x)), pos(s(y))) -> greater_int(pos(x), pos(y))
   greater_int(neg(s(x)), neg(s(y))) -> greater_int(neg(x), neg(y))

The set Q consists of the following terms:

   min(x0, e)
   min(x0, ins(x1, x2))
   if_1(pair(x0, x1), x2, x3, x4)
   Cond_if_1(true, pair(x0, x1), x2, x3, x4)
   if_2(pair(x0, x1), x2, x3, x4)
   Cond_if_2(true, pair(x0, x1), x2, x3, x4)
   greatereq_int(pos(x0), pos(0))
   greatereq_int(neg(0), pos(0))
   greatereq_int(neg(0), neg(x0))
   greatereq_int(pos(x0), neg(x1))
   greatereq_int(pos(0), pos(s(x0)))
   greatereq_int(neg(x0), pos(s(x1)))
   greatereq_int(neg(s(x0)), pos(0))
   greatereq_int(neg(s(x0)), neg(0))
   greatereq_int(pos(s(x0)), pos(s(x1)))
   greatereq_int(neg(s(x0)), neg(s(x1)))
   greater_int(pos(0), pos(0))
   greater_int(pos(0), neg(0))
   greater_int(neg(0), pos(0))
   greater_int(neg(0), neg(0))
   greater_int(pos(0), pos(s(x0)))
   greater_int(neg(0), pos(s(x0)))
   greater_int(pos(0), neg(s(x0)))
   greater_int(neg(0), neg(s(x0)))
   greater_int(pos(s(x0)), pos(0))
   greater_int(neg(s(x0)), pos(0))
   greater_int(pos(s(x0)), neg(0))
   greater_int(neg(s(x0)), neg(0))
   greater_int(pos(s(x0)), neg(s(x1)))
   greater_int(neg(s(x0)), pos(s(x1)))
   greater_int(pos(s(x0)), pos(s(x1)))
   greater_int(neg(s(x0)), neg(s(x1)))

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

(23) DependencyGraphProof (EQUIVALENT)
The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 0 SCCs with 1 less node.
----------------------------------------

(24)
TRUE