6.65/2.80 YES 6.65/2.82 proof of /export/starexec/sandbox2/benchmark/theBenchmark.itrs 6.65/2.82 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 6.65/2.82 6.65/2.82 6.65/2.82 Termination of the given ITRS could be proven: 6.65/2.82 6.65/2.82 (0) ITRS 6.65/2.82 (1) ITRStoIDPProof [EQUIVALENT, 0 ms] 6.65/2.82 (2) IDP 6.65/2.82 (3) ItpfGraphProof [EQUIVALENT, 11 ms] 6.65/2.82 (4) IDP 6.65/2.82 (5) IDependencyGraphProof [EQUIVALENT, 0 ms] 6.65/2.82 (6) AND 6.65/2.82 (7) IDP 6.65/2.82 (8) UsableRulesProof [EQUIVALENT, 4 ms] 6.65/2.82 (9) IDP 6.65/2.82 (10) IDPtoQDPProof [SOUND, 35 ms] 6.65/2.82 (11) QDP 6.65/2.82 (12) QReductionProof [EQUIVALENT, 0 ms] 6.65/2.82 (13) QDP 6.65/2.82 (14) QDPSizeChangeProof [EQUIVALENT, 0 ms] 6.65/2.82 (15) YES 6.65/2.82 (16) IDP 6.65/2.82 (17) UsableRulesProof [EQUIVALENT, 0 ms] 6.65/2.82 (18) IDP 6.65/2.82 (19) IDPNonInfProof [SOUND, 85 ms] 6.65/2.82 (20) IDP 6.65/2.82 (21) PisEmptyProof [EQUIVALENT, 0 ms] 6.65/2.82 (22) YES 6.65/2.82 (23) IDP 6.65/2.82 (24) UsableRulesProof [EQUIVALENT, 0 ms] 6.65/2.82 (25) IDP 6.65/2.82 (26) IDPNonInfProof [SOUND, 217 ms] 6.65/2.82 (27) IDP 6.65/2.82 (28) IDependencyGraphProof [EQUIVALENT, 0 ms] 6.65/2.82 (29) TRUE 6.65/2.82 6.65/2.82 6.65/2.82 ---------------------------------------- 6.65/2.82 6.65/2.82 (0) 6.65/2.82 Obligation: 6.65/2.82 ITRS problem: 6.65/2.82 6.65/2.82 The following function symbols are pre-defined: 6.65/2.82 <<< 6.65/2.82 & ~ Bwand: (Integer, Integer) -> Integer 6.65/2.82 >= ~ Ge: (Integer, Integer) -> Boolean 6.65/2.82 | ~ Bwor: (Integer, Integer) -> Integer 6.65/2.82 / ~ Div: (Integer, Integer) -> Integer 6.65/2.82 != ~ Neq: (Integer, Integer) -> Boolean 6.65/2.82 && ~ Land: (Boolean, Boolean) -> Boolean 6.65/2.82 ! ~ Lnot: (Boolean) -> Boolean 6.65/2.82 = ~ Eq: (Integer, Integer) -> Boolean 6.65/2.82 <= ~ Le: (Integer, Integer) -> Boolean 6.65/2.82 ^ ~ Bwxor: (Integer, Integer) -> Integer 6.65/2.82 % ~ Mod: (Integer, Integer) -> Integer 6.65/2.82 > ~ Gt: (Integer, Integer) -> Boolean 6.65/2.82 + ~ Add: (Integer, Integer) -> Integer 6.65/2.82 -1 ~ UnaryMinus: (Integer) -> Integer 6.65/2.82 < ~ Lt: (Integer, Integer) -> Boolean 6.65/2.82 || ~ Lor: (Boolean, Boolean) -> Boolean 6.65/2.82 - ~ Sub: (Integer, Integer) -> Integer 6.65/2.82 ~ ~ Bwnot: (Integer) -> Integer 6.65/2.82 * ~ Mul: (Integer, Integer) -> Integer 6.65/2.82 >>> 6.65/2.82 6.65/2.82 The TRS R consists of the following rules: 6.65/2.82 app(nil, zs) -> zs 6.65/2.82 app(cons(x, ys), zs) -> cons(x, app(ys, zs)) 6.65/2.82 split(x, e) -> pair(e, e) 6.65/2.82 split(x, ins(y, zs)) -> Cond_split(x > y, x, ins(y, zs)) 6.65/2.82 Cond_split(TRUE, x, ins(y, zs)) -> if_1(split(x, zs), x, y, zs) 6.65/2.82 if_1(pair(zl, zh), x, y, zs) -> Cond_if_1(x > y, pair(zl, zh), x, y, zs) 6.65/2.82 Cond_if_1(TRUE, pair(zl, zh), x, y, zs) -> pair(ins(y, zl), zh) 6.65/2.82 split(x, ins(y, zs)) -> Cond_split1(y >= x, x, ins(y, zs)) 6.65/2.82 Cond_split1(TRUE, x, ins(y, zs)) -> if_2(split(x, zs), x, y, zs) 6.65/2.82 if_2(pair(zl, zh), x, y, zs) -> Cond_if_2(y >= x, pair(zl, zh), x, y, zs) 6.65/2.82 Cond_if_2(TRUE, pair(zl, zh), x, y, zs) -> pair(zl, ins(y, zh)) 6.65/2.82 qsort(e) -> nil 6.65/2.82 qsort(ins(x, ys)) -> if_3(split(x, ys), x, ys) 6.65/2.82 if_3(pair(yl, yh), x, ys) -> app(qsort(yl), cons(x, qsort(yh))) 6.65/2.82 The set Q consists of the following terms: 6.65/2.82 app(nil, x0) 6.65/2.82 app(cons(x0, x1), x2) 6.65/2.82 split(x0, e) 6.65/2.82 split(x0, ins(x1, x2)) 6.65/2.82 Cond_split(TRUE, x0, ins(x1, x2)) 6.65/2.82 if_1(pair(x0, x1), x2, x3, x4) 6.65/2.82 Cond_if_1(TRUE, pair(x0, x1), x2, x3, x4) 6.65/2.82 Cond_split1(TRUE, x0, ins(x1, x2)) 6.65/2.82 if_2(pair(x0, x1), x2, x3, x4) 6.65/2.82 Cond_if_2(TRUE, pair(x0, x1), x2, x3, x4) 6.65/2.82 qsort(e) 6.65/2.82 qsort(ins(x0, x1)) 6.65/2.82 if_3(pair(x0, x1), x2, x3) 6.65/2.82 6.65/2.82 ---------------------------------------- 6.65/2.82 6.65/2.82 (1) ITRStoIDPProof (EQUIVALENT) 6.65/2.82 Added dependency pairs 6.65/2.82 ---------------------------------------- 6.65/2.82 6.65/2.82 (2) 6.65/2.82 Obligation: 6.65/2.82 IDP problem: 6.65/2.82 The following function symbols are pre-defined: 6.65/2.82 <<< 6.65/2.82 & ~ Bwand: (Integer, Integer) -> Integer 6.65/2.82 >= ~ Ge: (Integer, Integer) -> Boolean 6.65/2.82 | ~ Bwor: (Integer, Integer) -> Integer 6.65/2.82 / ~ Div: (Integer, Integer) -> Integer 6.65/2.82 != ~ Neq: (Integer, Integer) -> Boolean 6.65/2.82 && ~ Land: (Boolean, Boolean) -> Boolean 6.65/2.82 ! ~ Lnot: (Boolean) -> Boolean 6.65/2.82 = ~ Eq: (Integer, Integer) -> Boolean 6.65/2.82 <= ~ Le: (Integer, Integer) -> Boolean 6.65/2.82 ^ ~ Bwxor: (Integer, Integer) -> Integer 6.65/2.82 % ~ Mod: (Integer, Integer) -> Integer 6.65/2.82 > ~ Gt: (Integer, Integer) -> Boolean 6.65/2.82 + ~ Add: (Integer, Integer) -> Integer 6.65/2.82 -1 ~ UnaryMinus: (Integer) -> Integer 6.65/2.82 < ~ Lt: (Integer, Integer) -> Boolean 6.65/2.82 || ~ Lor: (Boolean, Boolean) -> Boolean 6.65/2.82 - ~ Sub: (Integer, Integer) -> Integer 6.65/2.82 ~ ~ Bwnot: (Integer) -> Integer 6.65/2.82 * ~ Mul: (Integer, Integer) -> Integer 6.65/2.82 >>> 6.65/2.82 6.65/2.82 6.65/2.82 The following domains are used: 6.65/2.82 Integer 6.65/2.82 6.65/2.82 The ITRS R consists of the following rules: 6.65/2.82 app(nil, zs) -> zs 6.65/2.82 app(cons(x, ys), zs) -> cons(x, app(ys, zs)) 6.65/2.82 split(x, e) -> pair(e, e) 6.65/2.82 split(x, ins(y, zs)) -> Cond_split(x > y, x, ins(y, zs)) 6.65/2.82 Cond_split(TRUE, x, ins(y, zs)) -> if_1(split(x, zs), x, y, zs) 6.65/2.82 if_1(pair(zl, zh), x, y, zs) -> Cond_if_1(x > y, pair(zl, zh), x, y, zs) 6.65/2.82 Cond_if_1(TRUE, pair(zl, zh), x, y, zs) -> pair(ins(y, zl), zh) 6.65/2.82 split(x, ins(y, zs)) -> Cond_split1(y >= x, x, ins(y, zs)) 6.65/2.82 Cond_split1(TRUE, x, ins(y, zs)) -> if_2(split(x, zs), x, y, zs) 6.65/2.82 if_2(pair(zl, zh), x, y, zs) -> Cond_if_2(y >= x, pair(zl, zh), x, y, zs) 6.65/2.82 Cond_if_2(TRUE, pair(zl, zh), x, y, zs) -> pair(zl, ins(y, zh)) 6.65/2.82 qsort(e) -> nil 6.65/2.82 qsort(ins(x, ys)) -> if_3(split(x, ys), x, ys) 6.65/2.82 if_3(pair(yl, yh), x, ys) -> app(qsort(yl), cons(x, qsort(yh))) 6.65/2.82 6.65/2.82 The integer pair graph contains the following rules and edges: 6.65/2.82 (0): APP(cons(x[0], ys[0]), zs[0]) -> APP(ys[0], zs[0]) 6.65/2.82 (1): SPLIT(x[1], ins(y[1], zs[1])) -> COND_SPLIT(x[1] > y[1], x[1], ins(y[1], zs[1])) 6.65/2.82 (2): COND_SPLIT(TRUE, x[2], ins(y[2], zs[2])) -> IF_1(split(x[2], zs[2]), x[2], y[2], zs[2]) 6.65/2.82 (3): COND_SPLIT(TRUE, x[3], ins(y[3], zs[3])) -> SPLIT(x[3], zs[3]) 6.65/2.82 (4): IF_1(pair(zl[4], zh[4]), x[4], y[4], zs[4]) -> COND_IF_1(x[4] > y[4], pair(zl[4], zh[4]), x[4], y[4], zs[4]) 6.65/2.82 (5): SPLIT(x[5], ins(y[5], zs[5])) -> COND_SPLIT1(y[5] >= x[5], x[5], ins(y[5], zs[5])) 6.65/2.82 (6): COND_SPLIT1(TRUE, x[6], ins(y[6], zs[6])) -> IF_2(split(x[6], zs[6]), x[6], y[6], zs[6]) 6.65/2.82 (7): COND_SPLIT1(TRUE, x[7], ins(y[7], zs[7])) -> SPLIT(x[7], zs[7]) 6.65/2.82 (8): IF_2(pair(zl[8], zh[8]), x[8], y[8], zs[8]) -> COND_IF_2(y[8] >= x[8], pair(zl[8], zh[8]), x[8], y[8], zs[8]) 6.65/2.82 (9): QSORT(ins(x[9], ys[9])) -> IF_3(split(x[9], ys[9]), x[9], ys[9]) 6.65/2.82 (10): QSORT(ins(x[10], ys[10])) -> SPLIT(x[10], ys[10]) 6.65/2.82 (11): IF_3(pair(yl[11], yh[11]), x[11], ys[11]) -> APP(qsort(yl[11]), cons(x[11], qsort(yh[11]))) 6.65/2.82 (12): IF_3(pair(yl[12], yh[12]), x[12], ys[12]) -> QSORT(yl[12]) 6.65/2.82 (13): IF_3(pair(yl[13], yh[13]), x[13], ys[13]) -> QSORT(yh[13]) 6.65/2.82 6.65/2.82 (0) -> (0), if (ys[0] ->^* cons(x[0]', ys[0]') & zs[0] ->^* zs[0]') 6.65/2.82 (1) -> (2), if (x[1] > y[1] & x[1] ->^* x[2] & ins(y[1], zs[1]) ->^* ins(y[2], zs[2])) 6.65/2.82 (1) -> (3), if (x[1] > y[1] & x[1] ->^* x[3] & ins(y[1], zs[1]) ->^* ins(y[3], zs[3])) 6.65/2.82 (2) -> (4), if (split(x[2], zs[2]) ->^* pair(zl[4], zh[4]) & x[2] ->^* x[4] & y[2] ->^* y[4] & zs[2] ->^* zs[4]) 6.65/2.82 (3) -> (1), if (x[3] ->^* x[1] & zs[3] ->^* ins(y[1], zs[1])) 6.65/2.82 (3) -> (5), if (x[3] ->^* x[5] & zs[3] ->^* ins(y[5], zs[5])) 6.65/2.82 (5) -> (6), if (y[5] >= x[5] & x[5] ->^* x[6] & ins(y[5], zs[5]) ->^* ins(y[6], zs[6])) 6.65/2.82 (5) -> (7), if (y[5] >= x[5] & x[5] ->^* x[7] & ins(y[5], zs[5]) ->^* ins(y[7], zs[7])) 6.65/2.82 (6) -> (8), if (split(x[6], zs[6]) ->^* pair(zl[8], zh[8]) & x[6] ->^* x[8] & y[6] ->^* y[8] & zs[6] ->^* zs[8]) 6.65/2.82 (7) -> (1), if (x[7] ->^* x[1] & zs[7] ->^* ins(y[1], zs[1])) 6.65/2.82 (7) -> (5), if (x[7] ->^* x[5] & zs[7] ->^* ins(y[5], zs[5])) 6.65/2.82 (9) -> (11), if (split(x[9], ys[9]) ->^* pair(yl[11], yh[11]) & x[9] ->^* x[11] & ys[9] ->^* ys[11]) 6.65/2.82 (9) -> (12), if (split(x[9], ys[9]) ->^* pair(yl[12], yh[12]) & x[9] ->^* x[12] & ys[9] ->^* ys[12]) 6.65/2.82 (9) -> (13), if (split(x[9], ys[9]) ->^* pair(yl[13], yh[13]) & x[9] ->^* x[13] & ys[9] ->^* ys[13]) 6.65/2.82 (10) -> (1), if (x[10] ->^* x[1] & ys[10] ->^* ins(y[1], zs[1])) 6.65/2.82 (10) -> (5), if (x[10] ->^* x[5] & ys[10] ->^* ins(y[5], zs[5])) 6.65/2.82 (11) -> (0), if (qsort(yl[11]) ->^* cons(x[0], ys[0]) & cons(x[11], qsort(yh[11])) ->^* zs[0]) 6.65/2.82 (12) -> (9), if (yl[12] ->^* ins(x[9], ys[9])) 6.65/2.82 (12) -> (10), if (yl[12] ->^* ins(x[10], ys[10])) 6.65/2.82 (13) -> (9), if (yh[13] ->^* ins(x[9], ys[9])) 6.65/2.82 (13) -> (10), if (yh[13] ->^* ins(x[10], ys[10])) 6.65/2.82 6.65/2.82 The set Q consists of the following terms: 6.65/2.82 app(nil, x0) 6.65/2.82 app(cons(x0, x1), x2) 6.65/2.82 split(x0, e) 6.65/2.82 split(x0, ins(x1, x2)) 6.65/2.82 Cond_split(TRUE, x0, ins(x1, x2)) 6.65/2.82 if_1(pair(x0, x1), x2, x3, x4) 6.65/2.82 Cond_if_1(TRUE, pair(x0, x1), x2, x3, x4) 6.65/2.82 Cond_split1(TRUE, x0, ins(x1, x2)) 6.65/2.82 if_2(pair(x0, x1), x2, x3, x4) 6.65/2.82 Cond_if_2(TRUE, pair(x0, x1), x2, x3, x4) 6.65/2.82 qsort(e) 6.65/2.82 qsort(ins(x0, x1)) 6.65/2.82 if_3(pair(x0, x1), x2, x3) 6.65/2.82 6.65/2.82 ---------------------------------------- 6.65/2.82 6.65/2.82 (3) ItpfGraphProof (EQUIVALENT) 6.65/2.82 Applied rule ItpfICap [ICap] 6.65/2.82 ---------------------------------------- 6.65/2.82 6.65/2.82 (4) 6.65/2.82 Obligation: 6.65/2.82 IDP problem: 6.65/2.82 The following function symbols are pre-defined: 6.65/2.82 <<< 6.65/2.82 & ~ Bwand: (Integer, Integer) -> Integer 6.65/2.82 >= ~ Ge: (Integer, Integer) -> Boolean 6.65/2.82 | ~ Bwor: (Integer, Integer) -> Integer 6.65/2.82 / ~ Div: (Integer, Integer) -> Integer 6.65/2.82 != ~ Neq: (Integer, Integer) -> Boolean 6.65/2.82 && ~ Land: (Boolean, Boolean) -> Boolean 6.65/2.82 ! ~ Lnot: (Boolean) -> Boolean 6.65/2.82 = ~ Eq: (Integer, Integer) -> Boolean 6.65/2.82 <= ~ Le: (Integer, Integer) -> Boolean 6.65/2.82 ^ ~ Bwxor: (Integer, Integer) -> Integer 6.65/2.82 % ~ Mod: (Integer, Integer) -> Integer 6.65/2.82 > ~ Gt: (Integer, Integer) -> Boolean 6.65/2.82 + ~ Add: (Integer, Integer) -> Integer 6.65/2.82 -1 ~ UnaryMinus: (Integer) -> Integer 6.65/2.82 < ~ Lt: (Integer, Integer) -> Boolean 6.65/2.82 || ~ Lor: (Boolean, Boolean) -> Boolean 6.65/2.82 - ~ Sub: (Integer, Integer) -> Integer 6.65/2.82 ~ ~ Bwnot: (Integer) -> Integer 6.65/2.82 * ~ Mul: (Integer, Integer) -> Integer 6.65/2.82 >>> 6.65/2.82 6.65/2.82 6.65/2.82 The following domains are used: 6.65/2.82 Integer 6.65/2.82 6.65/2.82 The ITRS R consists of the following rules: 6.65/2.82 app(nil, zs) -> zs 6.65/2.82 app(cons(x, ys), zs) -> cons(x, app(ys, zs)) 6.65/2.82 split(x, e) -> pair(e, e) 6.65/2.82 split(x, ins(y, zs)) -> Cond_split(x > y, x, ins(y, zs)) 6.65/2.82 Cond_split(TRUE, x, ins(y, zs)) -> if_1(split(x, zs), x, y, zs) 6.65/2.82 if_1(pair(zl, zh), x, y, zs) -> Cond_if_1(x > y, pair(zl, zh), x, y, zs) 6.65/2.82 Cond_if_1(TRUE, pair(zl, zh), x, y, zs) -> pair(ins(y, zl), zh) 6.65/2.82 split(x, ins(y, zs)) -> Cond_split1(y >= x, x, ins(y, zs)) 6.65/2.82 Cond_split1(TRUE, x, ins(y, zs)) -> if_2(split(x, zs), x, y, zs) 6.65/2.82 if_2(pair(zl, zh), x, y, zs) -> Cond_if_2(y >= x, pair(zl, zh), x, y, zs) 6.65/2.82 Cond_if_2(TRUE, pair(zl, zh), x, y, zs) -> pair(zl, ins(y, zh)) 6.65/2.82 qsort(e) -> nil 6.65/2.82 qsort(ins(x, ys)) -> if_3(split(x, ys), x, ys) 6.65/2.82 if_3(pair(yl, yh), x, ys) -> app(qsort(yl), cons(x, qsort(yh))) 6.65/2.82 6.65/2.82 The integer pair graph contains the following rules and edges: 6.65/2.82 (0): APP(cons(x[0], ys[0]), zs[0]) -> APP(ys[0], zs[0]) 6.65/2.82 (1): SPLIT(x[1], ins(y[1], zs[1])) -> COND_SPLIT(x[1] > y[1], x[1], ins(y[1], zs[1])) 6.65/2.82 (2): COND_SPLIT(TRUE, x[2], ins(y[2], zs[2])) -> IF_1(split(x[2], zs[2]), x[2], y[2], zs[2]) 6.65/2.82 (3): COND_SPLIT(TRUE, x[3], ins(y[3], zs[3])) -> SPLIT(x[3], zs[3]) 6.65/2.82 (4): IF_1(pair(zl[4], zh[4]), x[4], y[4], zs[4]) -> COND_IF_1(x[4] > y[4], pair(zl[4], zh[4]), x[4], y[4], zs[4]) 6.65/2.82 (5): SPLIT(x[5], ins(y[5], zs[5])) -> COND_SPLIT1(y[5] >= x[5], x[5], ins(y[5], zs[5])) 6.65/2.82 (6): COND_SPLIT1(TRUE, x[6], ins(y[6], zs[6])) -> IF_2(split(x[6], zs[6]), x[6], y[6], zs[6]) 6.65/2.82 (7): COND_SPLIT1(TRUE, x[7], ins(y[7], zs[7])) -> SPLIT(x[7], zs[7]) 6.65/2.82 (8): IF_2(pair(zl[8], zh[8]), x[8], y[8], zs[8]) -> COND_IF_2(y[8] >= x[8], pair(zl[8], zh[8]), x[8], y[8], zs[8]) 6.65/2.82 (9): QSORT(ins(x[9], ys[9])) -> IF_3(split(x[9], ys[9]), x[9], ys[9]) 6.65/2.82 (10): QSORT(ins(x[10], ys[10])) -> SPLIT(x[10], ys[10]) 6.65/2.82 (11): IF_3(pair(yl[11], yh[11]), x[11], ys[11]) -> APP(qsort(yl[11]), cons(x[11], qsort(yh[11]))) 6.65/2.82 (12): IF_3(pair(yl[12], yh[12]), x[12], ys[12]) -> QSORT(yl[12]) 6.65/2.82 (13): IF_3(pair(yl[13], yh[13]), x[13], ys[13]) -> QSORT(yh[13]) 6.65/2.82 6.65/2.82 (0) -> (0), if (ys[0] ->^* cons(x[0]', ys[0]') & zs[0] ->^* zs[0]') 6.65/2.82 (2) -> (4), if (split(x[2], zs[2]) ->^* pair(zl[4], zh[4]) & x[2] ->^* x[4] & y[2] ->^* y[4] & zs[2] ->^* zs[4]) 6.65/2.82 (3) -> (1), if (x[3] ->^* x[1] & zs[3] ->^* ins(y[1], zs[1])) 6.65/2.82 (3) -> (5), if (x[3] ->^* x[5] & zs[3] ->^* ins(y[5], zs[5])) 6.65/2.82 (6) -> (8), if (split(x[6], zs[6]) ->^* pair(zl[8], zh[8]) & x[6] ->^* x[8] & y[6] ->^* y[8] & zs[6] ->^* zs[8]) 6.65/2.82 (7) -> (1), if (x[7] ->^* x[1] & zs[7] ->^* ins(y[1], zs[1])) 6.65/2.82 (7) -> (5), if (x[7] ->^* x[5] & zs[7] ->^* ins(y[5], zs[5])) 6.65/2.82 (9) -> (11), if (split(x[9], ys[9]) ->^* pair(yl[11], yh[11]) & x[9] ->^* x[11] & ys[9] ->^* ys[11]) 6.65/2.82 (9) -> (12), if (split(x[9], ys[9]) ->^* pair(yl[12], yh[12]) & x[9] ->^* x[12] & ys[9] ->^* ys[12]) 6.65/2.82 (9) -> (13), if (split(x[9], ys[9]) ->^* pair(yl[13], yh[13]) & x[9] ->^* x[13] & ys[9] ->^* ys[13]) 6.65/2.82 (10) -> (1), if (x[10] ->^* x[1] & ys[10] ->^* ins(y[1], zs[1])) 6.65/2.82 (10) -> (5), if (x[10] ->^* x[5] & ys[10] ->^* ins(y[5], zs[5])) 6.65/2.82 (11) -> (0), if (qsort(yl[11]) ->^* cons(x[0], ys[0]) & cons(x[11], qsort(yh[11])) ->^* zs[0]) 6.65/2.82 (12) -> (9), if (yl[12] ->^* ins(x[9], ys[9])) 6.65/2.82 (12) -> (10), if (yl[12] ->^* ins(x[10], ys[10])) 6.65/2.82 (13) -> (9), if (yh[13] ->^* ins(x[9], ys[9])) 6.65/2.82 (13) -> (10), if (yh[13] ->^* ins(x[10], ys[10])) 6.65/2.82 (1) -> (2), if (x[1] > y[1] & x[1] ->^* x[2] & (y[1] ->^* y[2] & zs[1] ->^* zs[2])) 6.65/2.82 (1) -> (3), if (x[1] > y[1] & x[1] ->^* x[3] & (y[1] ->^* y[3] & zs[1] ->^* zs[3])) 6.65/2.82 (5) -> (6), if (y[5] >= x[5] & x[5] ->^* x[6] & (y[5] ->^* y[6] & zs[5] ->^* zs[6])) 6.65/2.82 (5) -> (7), if (y[5] >= x[5] & x[5] ->^* x[7] & (y[5] ->^* y[7] & zs[5] ->^* zs[7])) 6.65/2.82 6.65/2.82 The set Q consists of the following terms: 6.65/2.82 app(nil, x0) 6.65/2.82 app(cons(x0, x1), x2) 6.65/2.82 split(x0, e) 6.65/2.82 split(x0, ins(x1, x2)) 6.65/2.82 Cond_split(TRUE, x0, ins(x1, x2)) 6.65/2.82 if_1(pair(x0, x1), x2, x3, x4) 6.65/2.82 Cond_if_1(TRUE, pair(x0, x1), x2, x3, x4) 6.65/2.82 Cond_split1(TRUE, x0, ins(x1, x2)) 6.65/2.82 if_2(pair(x0, x1), x2, x3, x4) 6.65/2.82 Cond_if_2(TRUE, pair(x0, x1), x2, x3, x4) 6.65/2.82 qsort(e) 6.65/2.82 qsort(ins(x0, x1)) 6.65/2.82 if_3(pair(x0, x1), x2, x3) 6.65/2.82 6.65/2.82 ---------------------------------------- 6.65/2.82 6.65/2.82 (5) IDependencyGraphProof (EQUIVALENT) 6.65/2.82 The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 3 SCCs with 6 less nodes. 6.65/2.82 ---------------------------------------- 6.65/2.82 6.65/2.82 (6) 6.65/2.82 Complex Obligation (AND) 6.65/2.82 6.65/2.82 ---------------------------------------- 6.65/2.82 6.65/2.82 (7) 6.65/2.82 Obligation: 6.65/2.82 IDP problem: 6.65/2.82 The following function symbols are pre-defined: 6.65/2.82 <<< 6.65/2.82 & ~ Bwand: (Integer, Integer) -> Integer 6.65/2.82 >= ~ Ge: (Integer, Integer) -> Boolean 6.65/2.82 | ~ Bwor: (Integer, Integer) -> Integer 6.65/2.82 / ~ Div: (Integer, Integer) -> Integer 6.65/2.82 != ~ Neq: (Integer, Integer) -> Boolean 6.65/2.82 && ~ Land: (Boolean, Boolean) -> Boolean 6.65/2.82 ! ~ Lnot: (Boolean) -> Boolean 6.65/2.82 = ~ Eq: (Integer, Integer) -> Boolean 6.65/2.82 <= ~ Le: (Integer, Integer) -> Boolean 6.65/2.82 ^ ~ Bwxor: (Integer, Integer) -> Integer 6.65/2.82 % ~ Mod: (Integer, Integer) -> Integer 6.65/2.82 > ~ Gt: (Integer, Integer) -> Boolean 6.65/2.82 + ~ Add: (Integer, Integer) -> Integer 6.65/2.82 -1 ~ UnaryMinus: (Integer) -> Integer 6.65/2.82 < ~ Lt: (Integer, Integer) -> Boolean 6.65/2.82 || ~ Lor: (Boolean, Boolean) -> Boolean 6.65/2.82 - ~ Sub: (Integer, Integer) -> Integer 6.65/2.82 ~ ~ Bwnot: (Integer) -> Integer 6.65/2.82 * ~ Mul: (Integer, Integer) -> Integer 6.65/2.82 >>> 6.65/2.82 6.65/2.82 6.65/2.82 The following domains are used: 6.65/2.82 Integer 6.65/2.82 6.65/2.82 The ITRS R consists of the following rules: 6.65/2.82 app(nil, zs) -> zs 6.65/2.82 app(cons(x, ys), zs) -> cons(x, app(ys, zs)) 6.65/2.82 split(x, e) -> pair(e, e) 6.65/2.82 split(x, ins(y, zs)) -> Cond_split(x > y, x, ins(y, zs)) 6.65/2.82 Cond_split(TRUE, x, ins(y, zs)) -> if_1(split(x, zs), x, y, zs) 6.65/2.82 if_1(pair(zl, zh), x, y, zs) -> Cond_if_1(x > y, pair(zl, zh), x, y, zs) 6.65/2.82 Cond_if_1(TRUE, pair(zl, zh), x, y, zs) -> pair(ins(y, zl), zh) 6.65/2.82 split(x, ins(y, zs)) -> Cond_split1(y >= x, x, ins(y, zs)) 6.65/2.82 Cond_split1(TRUE, x, ins(y, zs)) -> if_2(split(x, zs), x, y, zs) 6.65/2.82 if_2(pair(zl, zh), x, y, zs) -> Cond_if_2(y >= x, pair(zl, zh), x, y, zs) 6.65/2.82 Cond_if_2(TRUE, pair(zl, zh), x, y, zs) -> pair(zl, ins(y, zh)) 6.65/2.82 qsort(e) -> nil 6.65/2.82 qsort(ins(x, ys)) -> if_3(split(x, ys), x, ys) 6.65/2.82 if_3(pair(yl, yh), x, ys) -> app(qsort(yl), cons(x, qsort(yh))) 6.65/2.82 6.65/2.82 The integer pair graph contains the following rules and edges: 6.65/2.82 (0): APP(cons(x[0], ys[0]), zs[0]) -> APP(ys[0], zs[0]) 6.65/2.82 6.65/2.82 (0) -> (0), if (ys[0] ->^* cons(x[0]', ys[0]') & zs[0] ->^* zs[0]') 6.65/2.82 6.65/2.82 The set Q consists of the following terms: 6.65/2.82 app(nil, x0) 6.65/2.82 app(cons(x0, x1), x2) 6.65/2.82 split(x0, e) 6.65/2.82 split(x0, ins(x1, x2)) 6.65/2.82 Cond_split(TRUE, x0, ins(x1, x2)) 6.65/2.82 if_1(pair(x0, x1), x2, x3, x4) 6.65/2.82 Cond_if_1(TRUE, pair(x0, x1), x2, x3, x4) 6.65/2.82 Cond_split1(TRUE, x0, ins(x1, x2)) 6.65/2.82 if_2(pair(x0, x1), x2, x3, x4) 6.65/2.82 Cond_if_2(TRUE, pair(x0, x1), x2, x3, x4) 6.65/2.82 qsort(e) 6.65/2.82 qsort(ins(x0, x1)) 6.65/2.82 if_3(pair(x0, x1), x2, x3) 6.65/2.82 6.65/2.82 ---------------------------------------- 6.65/2.82 6.65/2.82 (8) UsableRulesProof (EQUIVALENT) 6.65/2.82 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. 6.65/2.82 ---------------------------------------- 6.65/2.82 6.65/2.82 (9) 6.65/2.82 Obligation: 6.65/2.82 IDP problem: 6.65/2.82 The following function symbols are pre-defined: 6.65/2.82 <<< 6.65/2.82 & ~ Bwand: (Integer, Integer) -> Integer 6.65/2.82 >= ~ Ge: (Integer, Integer) -> Boolean 6.65/2.82 | ~ Bwor: (Integer, Integer) -> Integer 6.65/2.82 / ~ Div: (Integer, Integer) -> Integer 6.65/2.82 != ~ Neq: (Integer, Integer) -> Boolean 6.65/2.82 && ~ Land: (Boolean, Boolean) -> Boolean 6.65/2.82 ! ~ Lnot: (Boolean) -> Boolean 6.65/2.82 = ~ Eq: (Integer, Integer) -> Boolean 6.65/2.82 <= ~ Le: (Integer, Integer) -> Boolean 6.65/2.82 ^ ~ Bwxor: (Integer, Integer) -> Integer 6.65/2.82 % ~ Mod: (Integer, Integer) -> Integer 6.65/2.82 > ~ Gt: (Integer, Integer) -> Boolean 6.65/2.82 + ~ Add: (Integer, Integer) -> Integer 6.65/2.82 -1 ~ UnaryMinus: (Integer) -> Integer 6.65/2.82 < ~ Lt: (Integer, Integer) -> Boolean 6.65/2.82 || ~ Lor: (Boolean, Boolean) -> Boolean 6.65/2.82 - ~ Sub: (Integer, Integer) -> Integer 6.65/2.82 ~ ~ Bwnot: (Integer) -> Integer 6.65/2.82 * ~ Mul: (Integer, Integer) -> Integer 6.65/2.82 >>> 6.65/2.82 6.65/2.82 6.65/2.82 The following domains are used: 6.65/2.82 none 6.65/2.82 6.65/2.82 R is empty. 6.65/2.82 6.65/2.82 The integer pair graph contains the following rules and edges: 6.65/2.82 (0): APP(cons(x[0], ys[0]), zs[0]) -> APP(ys[0], zs[0]) 6.65/2.82 6.65/2.82 (0) -> (0), if (ys[0] ->^* cons(x[0]', ys[0]') & zs[0] ->^* zs[0]') 6.65/2.82 6.65/2.82 The set Q consists of the following terms: 6.65/2.82 app(nil, x0) 6.65/2.82 app(cons(x0, x1), x2) 6.65/2.82 split(x0, e) 6.65/2.82 split(x0, ins(x1, x2)) 6.65/2.82 Cond_split(TRUE, x0, ins(x1, x2)) 6.65/2.82 if_1(pair(x0, x1), x2, x3, x4) 6.65/2.82 Cond_if_1(TRUE, pair(x0, x1), x2, x3, x4) 6.65/2.82 Cond_split1(TRUE, x0, ins(x1, x2)) 6.65/2.82 if_2(pair(x0, x1), x2, x3, x4) 6.65/2.82 Cond_if_2(TRUE, pair(x0, x1), x2, x3, x4) 6.65/2.82 qsort(e) 6.65/2.82 qsort(ins(x0, x1)) 6.65/2.82 if_3(pair(x0, x1), x2, x3) 6.65/2.82 6.65/2.82 ---------------------------------------- 6.65/2.82 6.65/2.82 (10) IDPtoQDPProof (SOUND) 6.65/2.82 Represented integers and predefined function symbols by Terms 6.65/2.82 ---------------------------------------- 6.65/2.82 6.65/2.82 (11) 6.65/2.82 Obligation: 6.65/2.82 Q DP problem: 6.65/2.82 The TRS P consists of the following rules: 6.65/2.82 6.65/2.82 APP(cons(x[0], ys[0]), zs[0]) -> APP(ys[0], zs[0]) 6.65/2.82 6.65/2.82 R is empty. 6.65/2.82 The set Q consists of the following terms: 6.65/2.82 6.65/2.82 app(nil, x0) 6.65/2.82 app(cons(x0, x1), x2) 6.65/2.82 split(x0, e) 6.65/2.82 split(x0, ins(x1, x2)) 6.65/2.82 Cond_split(true, x0, ins(x1, x2)) 6.65/2.82 if_1(pair(x0, x1), x2, x3, x4) 6.65/2.82 Cond_if_1(true, pair(x0, x1), x2, x3, x4) 6.65/2.82 Cond_split1(true, x0, ins(x1, x2)) 6.65/2.82 if_2(pair(x0, x1), x2, x3, x4) 6.65/2.82 Cond_if_2(true, pair(x0, x1), x2, x3, x4) 6.65/2.82 qsort(e) 6.65/2.82 qsort(ins(x0, x1)) 6.65/2.82 if_3(pair(x0, x1), x2, x3) 6.65/2.82 6.65/2.82 We have to consider all minimal (P,Q,R)-chains. 6.65/2.82 ---------------------------------------- 6.65/2.82 6.65/2.82 (12) QReductionProof (EQUIVALENT) 6.65/2.82 We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. 6.65/2.82 6.65/2.82 app(nil, x0) 6.65/2.82 app(cons(x0, x1), x2) 6.65/2.82 split(x0, e) 6.65/2.82 split(x0, ins(x1, x2)) 6.65/2.82 Cond_split(true, x0, ins(x1, x2)) 6.65/2.82 if_1(pair(x0, x1), x2, x3, x4) 6.65/2.82 Cond_if_1(true, pair(x0, x1), x2, x3, x4) 6.65/2.82 Cond_split1(true, x0, ins(x1, x2)) 6.65/2.82 if_2(pair(x0, x1), x2, x3, x4) 6.65/2.82 Cond_if_2(true, pair(x0, x1), x2, x3, x4) 6.65/2.82 qsort(e) 6.65/2.82 qsort(ins(x0, x1)) 6.65/2.82 if_3(pair(x0, x1), x2, x3) 6.65/2.82 6.65/2.82 6.65/2.82 ---------------------------------------- 6.65/2.82 6.65/2.82 (13) 6.65/2.82 Obligation: 6.65/2.82 Q DP problem: 6.65/2.82 The TRS P consists of the following rules: 6.65/2.82 6.65/2.82 APP(cons(x[0], ys[0]), zs[0]) -> APP(ys[0], zs[0]) 6.65/2.82 6.65/2.82 R is empty. 6.65/2.82 Q is empty. 6.65/2.82 We have to consider all minimal (P,Q,R)-chains. 6.65/2.82 ---------------------------------------- 6.65/2.82 6.65/2.82 (14) QDPSizeChangeProof (EQUIVALENT) 6.65/2.82 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. 6.65/2.82 6.65/2.82 From the DPs we obtained the following set of size-change graphs: 6.65/2.82 *APP(cons(x[0], ys[0]), zs[0]) -> APP(ys[0], zs[0]) 6.65/2.82 The graph contains the following edges 1 > 1, 2 >= 2 6.65/2.82 6.65/2.82 6.65/2.82 ---------------------------------------- 6.65/2.82 6.65/2.82 (15) 6.65/2.82 YES 6.65/2.82 6.65/2.82 ---------------------------------------- 6.65/2.82 6.65/2.82 (16) 6.65/2.82 Obligation: 6.65/2.82 IDP problem: 6.65/2.82 The following function symbols are pre-defined: 6.65/2.82 <<< 6.65/2.82 & ~ Bwand: (Integer, Integer) -> Integer 6.65/2.82 >= ~ Ge: (Integer, Integer) -> Boolean 6.65/2.82 | ~ Bwor: (Integer, Integer) -> Integer 6.65/2.82 / ~ Div: (Integer, Integer) -> Integer 6.65/2.82 != ~ Neq: (Integer, Integer) -> Boolean 6.65/2.82 && ~ Land: (Boolean, Boolean) -> Boolean 6.65/2.82 ! ~ Lnot: (Boolean) -> Boolean 6.65/2.82 = ~ Eq: (Integer, Integer) -> Boolean 6.65/2.82 <= ~ Le: (Integer, Integer) -> Boolean 6.65/2.82 ^ ~ Bwxor: (Integer, Integer) -> Integer 6.65/2.82 % ~ Mod: (Integer, Integer) -> Integer 6.65/2.82 > ~ Gt: (Integer, Integer) -> Boolean 6.65/2.82 + ~ Add: (Integer, Integer) -> Integer 6.65/2.82 -1 ~ UnaryMinus: (Integer) -> Integer 6.65/2.82 < ~ Lt: (Integer, Integer) -> Boolean 6.65/2.82 || ~ Lor: (Boolean, Boolean) -> Boolean 6.65/2.82 - ~ Sub: (Integer, Integer) -> Integer 6.65/2.82 ~ ~ Bwnot: (Integer) -> Integer 6.65/2.82 * ~ Mul: (Integer, Integer) -> Integer 6.65/2.82 >>> 6.65/2.82 6.65/2.82 6.65/2.82 The following domains are used: 6.65/2.82 Integer 6.65/2.82 6.65/2.82 The ITRS R consists of the following rules: 6.65/2.82 app(nil, zs) -> zs 6.65/2.82 app(cons(x, ys), zs) -> cons(x, app(ys, zs)) 6.65/2.82 split(x, e) -> pair(e, e) 6.65/2.82 split(x, ins(y, zs)) -> Cond_split(x > y, x, ins(y, zs)) 6.65/2.82 Cond_split(TRUE, x, ins(y, zs)) -> if_1(split(x, zs), x, y, zs) 6.65/2.82 if_1(pair(zl, zh), x, y, zs) -> Cond_if_1(x > y, pair(zl, zh), x, y, zs) 6.65/2.82 Cond_if_1(TRUE, pair(zl, zh), x, y, zs) -> pair(ins(y, zl), zh) 6.65/2.82 split(x, ins(y, zs)) -> Cond_split1(y >= x, x, ins(y, zs)) 6.65/2.82 Cond_split1(TRUE, x, ins(y, zs)) -> if_2(split(x, zs), x, y, zs) 6.65/2.82 if_2(pair(zl, zh), x, y, zs) -> Cond_if_2(y >= x, pair(zl, zh), x, y, zs) 6.65/2.82 Cond_if_2(TRUE, pair(zl, zh), x, y, zs) -> pair(zl, ins(y, zh)) 6.65/2.82 qsort(e) -> nil 6.65/2.82 qsort(ins(x, ys)) -> if_3(split(x, ys), x, ys) 6.65/2.82 if_3(pair(yl, yh), x, ys) -> app(qsort(yl), cons(x, qsort(yh))) 6.65/2.82 6.65/2.82 The integer pair graph contains the following rules and edges: 6.65/2.82 (7): COND_SPLIT1(TRUE, x[7], ins(y[7], zs[7])) -> SPLIT(x[7], zs[7]) 6.65/2.82 (5): SPLIT(x[5], ins(y[5], zs[5])) -> COND_SPLIT1(y[5] >= x[5], x[5], ins(y[5], zs[5])) 6.65/2.82 (3): COND_SPLIT(TRUE, x[3], ins(y[3], zs[3])) -> SPLIT(x[3], zs[3]) 6.65/2.82 (1): SPLIT(x[1], ins(y[1], zs[1])) -> COND_SPLIT(x[1] > y[1], x[1], ins(y[1], zs[1])) 6.65/2.82 6.65/2.82 (3) -> (1), if (x[3] ->^* x[1] & zs[3] ->^* ins(y[1], zs[1])) 6.65/2.82 (7) -> (1), if (x[7] ->^* x[1] & zs[7] ->^* ins(y[1], zs[1])) 6.65/2.82 (1) -> (3), if (x[1] > y[1] & x[1] ->^* x[3] & (y[1] ->^* y[3] & zs[1] ->^* zs[3])) 6.65/2.82 (3) -> (5), if (x[3] ->^* x[5] & zs[3] ->^* ins(y[5], zs[5])) 6.65/2.82 (7) -> (5), if (x[7] ->^* x[5] & zs[7] ->^* ins(y[5], zs[5])) 6.65/2.82 (5) -> (7), if (y[5] >= x[5] & x[5] ->^* x[7] & (y[5] ->^* y[7] & zs[5] ->^* zs[7])) 6.65/2.82 6.65/2.82 The set Q consists of the following terms: 6.65/2.82 app(nil, x0) 6.65/2.82 app(cons(x0, x1), x2) 6.65/2.82 split(x0, e) 6.65/2.82 split(x0, ins(x1, x2)) 6.65/2.82 Cond_split(TRUE, x0, ins(x1, x2)) 6.65/2.82 if_1(pair(x0, x1), x2, x3, x4) 6.65/2.82 Cond_if_1(TRUE, pair(x0, x1), x2, x3, x4) 6.65/2.82 Cond_split1(TRUE, x0, ins(x1, x2)) 6.65/2.82 if_2(pair(x0, x1), x2, x3, x4) 6.65/2.82 Cond_if_2(TRUE, pair(x0, x1), x2, x3, x4) 6.65/2.82 qsort(e) 6.65/2.82 qsort(ins(x0, x1)) 6.65/2.82 if_3(pair(x0, x1), x2, x3) 6.65/2.82 6.65/2.82 ---------------------------------------- 6.65/2.82 6.65/2.82 (17) UsableRulesProof (EQUIVALENT) 6.65/2.82 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. 6.65/2.82 ---------------------------------------- 6.65/2.82 6.65/2.82 (18) 6.65/2.82 Obligation: 6.65/2.82 IDP problem: 6.65/2.82 The following function symbols are pre-defined: 6.65/2.82 <<< 6.65/2.82 & ~ Bwand: (Integer, Integer) -> Integer 6.65/2.82 >= ~ Ge: (Integer, Integer) -> Boolean 6.65/2.82 | ~ Bwor: (Integer, Integer) -> Integer 6.65/2.82 / ~ Div: (Integer, Integer) -> Integer 6.65/2.82 != ~ Neq: (Integer, Integer) -> Boolean 6.65/2.82 && ~ Land: (Boolean, Boolean) -> Boolean 6.65/2.82 ! ~ Lnot: (Boolean) -> Boolean 6.65/2.82 = ~ Eq: (Integer, Integer) -> Boolean 6.65/2.82 <= ~ Le: (Integer, Integer) -> Boolean 6.65/2.82 ^ ~ Bwxor: (Integer, Integer) -> Integer 6.65/2.82 % ~ Mod: (Integer, Integer) -> Integer 6.65/2.82 > ~ Gt: (Integer, Integer) -> Boolean 6.65/2.82 + ~ Add: (Integer, Integer) -> Integer 6.65/2.82 -1 ~ UnaryMinus: (Integer) -> Integer 6.65/2.82 < ~ Lt: (Integer, Integer) -> Boolean 6.65/2.82 || ~ Lor: (Boolean, Boolean) -> Boolean 6.65/2.82 - ~ Sub: (Integer, Integer) -> Integer 6.65/2.82 ~ ~ Bwnot: (Integer) -> Integer 6.65/2.82 * ~ Mul: (Integer, Integer) -> Integer 6.65/2.82 >>> 6.65/2.82 6.65/2.82 6.65/2.82 The following domains are used: 6.65/2.82 Integer 6.65/2.82 6.65/2.82 R is empty. 6.65/2.82 6.65/2.82 The integer pair graph contains the following rules and edges: 6.65/2.82 (7): COND_SPLIT1(TRUE, x[7], ins(y[7], zs[7])) -> SPLIT(x[7], zs[7]) 6.65/2.82 (5): SPLIT(x[5], ins(y[5], zs[5])) -> COND_SPLIT1(y[5] >= x[5], x[5], ins(y[5], zs[5])) 6.65/2.82 (3): COND_SPLIT(TRUE, x[3], ins(y[3], zs[3])) -> SPLIT(x[3], zs[3]) 6.65/2.82 (1): SPLIT(x[1], ins(y[1], zs[1])) -> COND_SPLIT(x[1] > y[1], x[1], ins(y[1], zs[1])) 6.65/2.82 6.65/2.82 (3) -> (1), if (x[3] ->^* x[1] & zs[3] ->^* ins(y[1], zs[1])) 6.65/2.82 (7) -> (1), if (x[7] ->^* x[1] & zs[7] ->^* ins(y[1], zs[1])) 6.65/2.82 (1) -> (3), if (x[1] > y[1] & x[1] ->^* x[3] & (y[1] ->^* y[3] & zs[1] ->^* zs[3])) 6.65/2.82 (3) -> (5), if (x[3] ->^* x[5] & zs[3] ->^* ins(y[5], zs[5])) 6.65/2.82 (7) -> (5), if (x[7] ->^* x[5] & zs[7] ->^* ins(y[5], zs[5])) 6.65/2.82 (5) -> (7), if (y[5] >= x[5] & x[5] ->^* x[7] & (y[5] ->^* y[7] & zs[5] ->^* zs[7])) 6.65/2.82 6.65/2.82 The set Q consists of the following terms: 6.65/2.82 app(nil, x0) 6.65/2.82 app(cons(x0, x1), x2) 6.65/2.82 split(x0, e) 6.65/2.82 split(x0, ins(x1, x2)) 6.65/2.82 Cond_split(TRUE, x0, ins(x1, x2)) 6.65/2.82 if_1(pair(x0, x1), x2, x3, x4) 6.65/2.82 Cond_if_1(TRUE, pair(x0, x1), x2, x3, x4) 6.65/2.82 Cond_split1(TRUE, x0, ins(x1, x2)) 6.65/2.82 if_2(pair(x0, x1), x2, x3, x4) 6.65/2.82 Cond_if_2(TRUE, pair(x0, x1), x2, x3, x4) 6.65/2.82 qsort(e) 6.65/2.82 qsort(ins(x0, x1)) 6.65/2.82 if_3(pair(x0, x1), x2, x3) 6.65/2.82 6.65/2.82 ---------------------------------------- 6.65/2.82 6.65/2.82 (19) IDPNonInfProof (SOUND) 6.65/2.82 Used the following options for this NonInfProof: 6.65/2.82 6.65/2.82 IDPGPoloSolver: 6.65/2.82 Range: [(-1,2)] 6.65/2.82 IsNat: true 6.65/2.82 Interpretation Shape Heuristic: aprove.DPFramework.IDPProblem.Processors.nonInf.poly.IdpDefaultShapeHeuristic@543a0a6c 6.65/2.82 Constraint Generator: NonInfConstraintGenerator: 6.65/2.82 PathGenerator: MetricPathGenerator: 6.65/2.82 Max Left Steps: 1 6.65/2.82 Max Right Steps: 1 6.65/2.82 6.65/2.82 6.65/2.82 6.65/2.82 The constraints were generated the following way: 6.65/2.82 6.65/2.82 The DP Problem is simplified using the Induction Calculus [NONINF] with the following steps: 6.65/2.82 6.65/2.82 Note that final constraints are written in bold face. 6.65/2.82 6.65/2.82 6.65/2.82 6.65/2.82 For Pair COND_SPLIT1(TRUE, x[7], ins(y[7], zs[7])) -> SPLIT(x[7], zs[7]) the following chains were created: 6.65/2.82 *We consider the chain SPLIT(x[5], ins(y[5], zs[5])) -> COND_SPLIT1(>=(y[5], x[5]), x[5], ins(y[5], zs[5])), COND_SPLIT1(TRUE, x[7], ins(y[7], zs[7])) -> SPLIT(x[7], zs[7]), SPLIT(x[1], ins(y[1], zs[1])) -> COND_SPLIT(>(x[1], y[1]), x[1], ins(y[1], zs[1])) which results in the following constraint: 6.65/2.82 6.65/2.82 (1) (>=(y[5], x[5])=TRUE & x[5]=x[7] & y[5]=y[7] & zs[5]=zs[7] & x[7]=x[1] & zs[7]=ins(y[1], zs[1]) ==> COND_SPLIT1(TRUE, x[7], ins(y[7], zs[7]))_>=_NonInfC & COND_SPLIT1(TRUE, x[7], ins(y[7], zs[7]))_>=_SPLIT(x[7], zs[7]) & (U^Increasing(SPLIT(x[7], zs[7])), >=)) 6.65/2.82 6.65/2.82 6.65/2.82 6.65/2.82 We simplified constraint (1) using rules (III), (IV) which results in the following new constraint: 6.65/2.82 6.65/2.82 (2) (>=(y[5], x[5])=TRUE ==> COND_SPLIT1(TRUE, x[5], ins(y[5], ins(y[1], zs[1])))_>=_NonInfC & COND_SPLIT1(TRUE, x[5], ins(y[5], ins(y[1], zs[1])))_>=_SPLIT(x[5], ins(y[1], zs[1])) & (U^Increasing(SPLIT(x[7], zs[7])), >=)) 6.65/2.82 6.65/2.82 6.65/2.82 6.65/2.82 We simplified constraint (2) using rule (POLY_CONSTRAINTS) which results in the following new constraint: 6.65/2.82 6.65/2.82 (3) (0 >= 0 ==> (U^Increasing(SPLIT(x[7], zs[7])), >=) & [(8)bni_15 + (-1)Bound*bni_15] + [(4)bni_15]zs[1] + [(2)bni_15]x[5] >= 0 & [3 + (-1)bso_16] >= 0) 6.65/2.82 6.65/2.82 6.65/2.82 6.65/2.82 We simplified constraint (3) using rule (IDP_POLY_SIMPLIFY) which results in the following new constraint: 6.65/2.82 6.65/2.82 (4) (0 >= 0 ==> (U^Increasing(SPLIT(x[7], zs[7])), >=) & [(8)bni_15 + (-1)Bound*bni_15] + [(4)bni_15]zs[1] + [(2)bni_15]x[5] >= 0 & [3 + (-1)bso_16] >= 0) 6.65/2.82 6.65/2.82 6.65/2.82 6.65/2.82 We simplified constraint (4) using rule (POLY_REMOVE_MIN_MAX) which results in the following new constraint: 6.65/2.82 6.65/2.82 (5) (0 >= 0 ==> (U^Increasing(SPLIT(x[7], zs[7])), >=) & [(8)bni_15 + (-1)Bound*bni_15] + [(4)bni_15]zs[1] + [(2)bni_15]x[5] >= 0 & [3 + (-1)bso_16] >= 0) 6.65/2.82 6.65/2.82 6.65/2.82 6.65/2.82 We simplified constraint (5) using rule (IDP_UNRESTRICTED_VARS) which results in the following new constraint: 6.65/2.82 6.65/2.82 (6) (0 >= 0 ==> (U^Increasing(SPLIT(x[7], zs[7])), >=) & [(4)bni_15] >= 0 & 0 >= 0 & 0 >= 0 & [(2)bni_15] >= 0 & [(8)bni_15 + (-1)Bound*bni_15] >= 0 & 0 >= 0 & 0 >= 0 & [3 + (-1)bso_16] >= 0) 6.65/2.82 6.65/2.82 6.65/2.82 6.65/2.82 6.65/2.82 *We consider the chain SPLIT(x[5], ins(y[5], zs[5])) -> COND_SPLIT1(>=(y[5], x[5]), x[5], ins(y[5], zs[5])), COND_SPLIT1(TRUE, x[7], ins(y[7], zs[7])) -> SPLIT(x[7], zs[7]), SPLIT(x[5], ins(y[5], zs[5])) -> COND_SPLIT1(>=(y[5], x[5]), x[5], ins(y[5], zs[5])) which results in the following constraint: 6.65/2.82 6.65/2.82 (1) (>=(y[5], x[5])=TRUE & x[5]=x[7] & y[5]=y[7] & zs[5]=zs[7] & x[7]=x[5]1 & zs[7]=ins(y[5]1, zs[5]1) ==> COND_SPLIT1(TRUE, x[7], ins(y[7], zs[7]))_>=_NonInfC & COND_SPLIT1(TRUE, x[7], ins(y[7], zs[7]))_>=_SPLIT(x[7], zs[7]) & (U^Increasing(SPLIT(x[7], zs[7])), >=)) 6.65/2.82 6.65/2.82 6.65/2.82 6.65/2.82 We simplified constraint (1) using rules (III), (IV) which results in the following new constraint: 6.65/2.82 6.65/2.82 (2) (>=(y[5], x[5])=TRUE ==> COND_SPLIT1(TRUE, x[5], ins(y[5], ins(y[5]1, zs[5]1)))_>=_NonInfC & COND_SPLIT1(TRUE, x[5], ins(y[5], ins(y[5]1, zs[5]1)))_>=_SPLIT(x[5], ins(y[5]1, zs[5]1)) & (U^Increasing(SPLIT(x[7], zs[7])), >=)) 6.65/2.82 6.65/2.82 6.65/2.82 6.65/2.82 We simplified constraint (2) using rule (POLY_CONSTRAINTS) which results in the following new constraint: 6.65/2.82 6.65/2.82 (3) (0 >= 0 ==> (U^Increasing(SPLIT(x[7], zs[7])), >=) & [(8)bni_15 + (-1)Bound*bni_15] + [(4)bni_15]zs[5]1 + [(2)bni_15]x[5] >= 0 & [3 + (-1)bso_16] >= 0) 6.65/2.82 6.65/2.82 6.65/2.82 6.65/2.82 We simplified constraint (3) using rule (IDP_POLY_SIMPLIFY) which results in the following new constraint: 6.65/2.82 6.65/2.82 (4) (0 >= 0 ==> (U^Increasing(SPLIT(x[7], zs[7])), >=) & [(8)bni_15 + (-1)Bound*bni_15] + [(4)bni_15]zs[5]1 + [(2)bni_15]x[5] >= 0 & [3 + (-1)bso_16] >= 0) 6.65/2.82 6.65/2.82 6.65/2.82 6.65/2.82 We simplified constraint (4) using rule (POLY_REMOVE_MIN_MAX) which results in the following new constraint: 6.65/2.82 6.65/2.82 (5) (0 >= 0 ==> (U^Increasing(SPLIT(x[7], zs[7])), >=) & [(8)bni_15 + (-1)Bound*bni_15] + [(4)bni_15]zs[5]1 + [(2)bni_15]x[5] >= 0 & [3 + (-1)bso_16] >= 0) 6.65/2.82 6.65/2.82 6.65/2.82 6.65/2.82 We simplified constraint (5) using rule (IDP_UNRESTRICTED_VARS) which results in the following new constraint: 6.65/2.82 6.65/2.82 (6) (0 >= 0 ==> (U^Increasing(SPLIT(x[7], zs[7])), >=) & [(4)bni_15] >= 0 & 0 >= 0 & 0 >= 0 & [(2)bni_15] >= 0 & [(8)bni_15 + (-1)Bound*bni_15] >= 0 & 0 >= 0 & 0 >= 0 & [3 + (-1)bso_16] >= 0) 6.65/2.82 6.65/2.82 6.65/2.82 6.65/2.82 6.65/2.82 6.65/2.82 6.65/2.82 6.65/2.82 6.65/2.82 For Pair SPLIT(x[5], ins(y[5], zs[5])) -> COND_SPLIT1(>=(y[5], x[5]), x[5], ins(y[5], zs[5])) the following chains were created: 6.65/2.82 *We consider the chain SPLIT(x[5], ins(y[5], zs[5])) -> COND_SPLIT1(>=(y[5], x[5]), x[5], ins(y[5], zs[5])), COND_SPLIT1(TRUE, x[7], ins(y[7], zs[7])) -> SPLIT(x[7], zs[7]) which results in the following constraint: 6.65/2.82 6.65/2.82 (1) (>=(y[5], x[5])=TRUE & x[5]=x[7] & y[5]=y[7] & zs[5]=zs[7] ==> SPLIT(x[5], ins(y[5], zs[5]))_>=_NonInfC & SPLIT(x[5], ins(y[5], zs[5]))_>=_COND_SPLIT1(>=(y[5], x[5]), x[5], ins(y[5], zs[5])) & (U^Increasing(COND_SPLIT1(>=(y[5], x[5]), x[5], ins(y[5], zs[5]))), >=)) 6.65/2.82 6.65/2.82 6.65/2.82 6.65/2.82 We simplified constraint (1) using rule (IV) which results in the following new constraint: 6.65/2.82 6.65/2.82 (2) (>=(y[5], x[5])=TRUE ==> SPLIT(x[5], ins(y[5], zs[5]))_>=_NonInfC & SPLIT(x[5], ins(y[5], zs[5]))_>=_COND_SPLIT1(>=(y[5], x[5]), x[5], ins(y[5], zs[5])) & (U^Increasing(COND_SPLIT1(>=(y[5], x[5]), x[5], ins(y[5], zs[5]))), >=)) 6.65/2.82 6.65/2.82 6.65/2.82 6.65/2.82 We simplified constraint (2) using rule (POLY_CONSTRAINTS) which results in the following new constraint: 6.65/2.82 6.65/2.82 (3) (0 >= 0 ==> (U^Increasing(COND_SPLIT1(>=(y[5], x[5]), x[5], ins(y[5], zs[5]))), >=) & [(5)bni_17 + (-1)Bound*bni_17] + [(4)bni_17]zs[5] + [(2)bni_17]x[5] >= 0 & [3 + (-1)bso_18] + [2]zs[5] >= 0) 6.65/2.82 6.65/2.82 6.65/2.82 6.65/2.82 We simplified constraint (3) using rule (IDP_POLY_SIMPLIFY) which results in the following new constraint: 6.65/2.82 6.65/2.82 (4) (0 >= 0 ==> (U^Increasing(COND_SPLIT1(>=(y[5], x[5]), x[5], ins(y[5], zs[5]))), >=) & [(5)bni_17 + (-1)Bound*bni_17] + [(4)bni_17]zs[5] + [(2)bni_17]x[5] >= 0 & [3 + (-1)bso_18] + [2]zs[5] >= 0) 6.65/2.82 6.65/2.82 6.65/2.82 6.65/2.82 We simplified constraint (4) using rule (POLY_REMOVE_MIN_MAX) which results in the following new constraint: 6.65/2.82 6.65/2.82 (5) (0 >= 0 ==> (U^Increasing(COND_SPLIT1(>=(y[5], x[5]), x[5], ins(y[5], zs[5]))), >=) & [(5)bni_17 + (-1)Bound*bni_17] + [(4)bni_17]zs[5] + [(2)bni_17]x[5] >= 0 & [3 + (-1)bso_18] + [2]zs[5] >= 0) 6.65/2.82 6.65/2.82 6.65/2.82 6.65/2.82 We simplified constraint (5) using rules (IDP_UNRESTRICTED_VARS), (IDP_POLY_GCD) which results in the following new constraint: 6.65/2.82 6.65/2.82 (6) (0 >= 0 ==> (U^Increasing(COND_SPLIT1(>=(y[5], x[5]), x[5], ins(y[5], zs[5]))), >=) & [(4)bni_17] >= 0 & 0 >= 0 & [(2)bni_17] >= 0 & [(5)bni_17 + (-1)Bound*bni_17] >= 0 & [3 + (-1)bso_18] >= 0 & [1] >= 0) 6.65/2.82 6.65/2.82 6.65/2.82 6.65/2.82 6.65/2.82 6.65/2.82 6.65/2.82 6.65/2.82 6.65/2.82 For Pair COND_SPLIT(TRUE, x[3], ins(y[3], zs[3])) -> SPLIT(x[3], zs[3]) the following chains were created: 6.65/2.82 *We consider the chain SPLIT(x[1], ins(y[1], zs[1])) -> COND_SPLIT(>(x[1], y[1]), x[1], ins(y[1], zs[1])), COND_SPLIT(TRUE, x[3], ins(y[3], zs[3])) -> SPLIT(x[3], zs[3]), SPLIT(x[1], ins(y[1], zs[1])) -> COND_SPLIT(>(x[1], y[1]), x[1], ins(y[1], zs[1])) which results in the following constraint: 6.65/2.82 6.65/2.82 (1) (>(x[1], y[1])=TRUE & x[1]=x[3] & y[1]=y[3] & zs[1]=zs[3] & x[3]=x[1]1 & zs[3]=ins(y[1]1, zs[1]1) ==> COND_SPLIT(TRUE, x[3], ins(y[3], zs[3]))_>=_NonInfC & COND_SPLIT(TRUE, x[3], ins(y[3], zs[3]))_>=_SPLIT(x[3], zs[3]) & (U^Increasing(SPLIT(x[3], zs[3])), >=)) 6.65/2.83 6.65/2.83 6.65/2.83 6.65/2.83 We simplified constraint (1) using rules (III), (IV) which results in the following new constraint: 6.65/2.83 6.65/2.83 (2) (>(x[1], y[1])=TRUE ==> COND_SPLIT(TRUE, x[1], ins(y[1], ins(y[1]1, zs[1]1)))_>=_NonInfC & COND_SPLIT(TRUE, x[1], ins(y[1], ins(y[1]1, zs[1]1)))_>=_SPLIT(x[1], ins(y[1]1, zs[1]1)) & (U^Increasing(SPLIT(x[3], zs[3])), >=)) 6.65/2.83 6.65/2.83 6.65/2.83 6.65/2.83 We simplified constraint (2) using rule (POLY_CONSTRAINTS) which results in the following new constraint: 6.65/2.83 6.65/2.83 (3) (0 >= 0 ==> (U^Increasing(SPLIT(x[3], zs[3])), >=) & [(9)bni_19 + (-1)Bound*bni_19] + [(4)bni_19]zs[1]1 + [(2)bni_19]x[1] >= 0 & [4 + (-1)bso_20] >= 0) 6.65/2.83 6.65/2.83 6.65/2.83 6.65/2.83 We simplified constraint (3) using rule (IDP_POLY_SIMPLIFY) which results in the following new constraint: 6.65/2.83 6.65/2.83 (4) (0 >= 0 ==> (U^Increasing(SPLIT(x[3], zs[3])), >=) & [(9)bni_19 + (-1)Bound*bni_19] + [(4)bni_19]zs[1]1 + [(2)bni_19]x[1] >= 0 & [4 + (-1)bso_20] >= 0) 6.65/2.83 6.65/2.83 6.65/2.83 6.65/2.83 We simplified constraint (4) using rule (POLY_REMOVE_MIN_MAX) which results in the following new constraint: 6.65/2.83 6.65/2.83 (5) (0 >= 0 ==> (U^Increasing(SPLIT(x[3], zs[3])), >=) & [(9)bni_19 + (-1)Bound*bni_19] + [(4)bni_19]zs[1]1 + [(2)bni_19]x[1] >= 0 & [4 + (-1)bso_20] >= 0) 6.65/2.83 6.65/2.83 6.65/2.83 6.65/2.83 We simplified constraint (5) using rule (IDP_UNRESTRICTED_VARS) which results in the following new constraint: 6.65/2.83 6.65/2.83 (6) (0 >= 0 ==> (U^Increasing(SPLIT(x[3], zs[3])), >=) & [(4)bni_19] >= 0 & 0 >= 0 & 0 >= 0 & [(2)bni_19] >= 0 & [(9)bni_19 + (-1)Bound*bni_19] >= 0 & 0 >= 0 & 0 >= 0 & [4 + (-1)bso_20] >= 0) 6.65/2.83 6.65/2.83 6.65/2.83 6.65/2.83 6.65/2.83 *We consider the chain SPLIT(x[1], ins(y[1], zs[1])) -> COND_SPLIT(>(x[1], y[1]), x[1], ins(y[1], zs[1])), COND_SPLIT(TRUE, x[3], ins(y[3], zs[3])) -> SPLIT(x[3], zs[3]), SPLIT(x[5], ins(y[5], zs[5])) -> COND_SPLIT1(>=(y[5], x[5]), x[5], ins(y[5], zs[5])) which results in the following constraint: 6.65/2.83 6.65/2.83 (1) (>(x[1], y[1])=TRUE & x[1]=x[3] & y[1]=y[3] & zs[1]=zs[3] & x[3]=x[5] & zs[3]=ins(y[5], zs[5]) ==> COND_SPLIT(TRUE, x[3], ins(y[3], zs[3]))_>=_NonInfC & COND_SPLIT(TRUE, x[3], ins(y[3], zs[3]))_>=_SPLIT(x[3], zs[3]) & (U^Increasing(SPLIT(x[3], zs[3])), >=)) 6.65/2.83 6.65/2.83 6.65/2.83 6.65/2.83 We simplified constraint (1) using rules (III), (IV) which results in the following new constraint: 6.65/2.83 6.65/2.83 (2) (>(x[1], y[1])=TRUE ==> COND_SPLIT(TRUE, x[1], ins(y[1], ins(y[5], zs[5])))_>=_NonInfC & COND_SPLIT(TRUE, x[1], ins(y[1], ins(y[5], zs[5])))_>=_SPLIT(x[1], ins(y[5], zs[5])) & (U^Increasing(SPLIT(x[3], zs[3])), >=)) 6.65/2.83 6.65/2.83 6.65/2.83 6.65/2.83 We simplified constraint (2) using rule (POLY_CONSTRAINTS) which results in the following new constraint: 6.65/2.83 6.65/2.83 (3) (0 >= 0 ==> (U^Increasing(SPLIT(x[3], zs[3])), >=) & [(9)bni_19 + (-1)Bound*bni_19] + [(4)bni_19]zs[5] + [(2)bni_19]x[1] >= 0 & [4 + (-1)bso_20] >= 0) 6.65/2.83 6.65/2.83 6.65/2.83 6.65/2.83 We simplified constraint (3) using rule (IDP_POLY_SIMPLIFY) which results in the following new constraint: 6.65/2.83 6.65/2.83 (4) (0 >= 0 ==> (U^Increasing(SPLIT(x[3], zs[3])), >=) & [(9)bni_19 + (-1)Bound*bni_19] + [(4)bni_19]zs[5] + [(2)bni_19]x[1] >= 0 & [4 + (-1)bso_20] >= 0) 6.65/2.83 6.65/2.83 6.65/2.83 6.65/2.83 We simplified constraint (4) using rule (POLY_REMOVE_MIN_MAX) which results in the following new constraint: 6.65/2.83 6.65/2.83 (5) (0 >= 0 ==> (U^Increasing(SPLIT(x[3], zs[3])), >=) & [(9)bni_19 + (-1)Bound*bni_19] + [(4)bni_19]zs[5] + [(2)bni_19]x[1] >= 0 & [4 + (-1)bso_20] >= 0) 6.65/2.83 6.65/2.83 6.65/2.83 6.65/2.83 We simplified constraint (5) using rule (IDP_UNRESTRICTED_VARS) which results in the following new constraint: 6.65/2.83 6.65/2.83 (6) (0 >= 0 ==> (U^Increasing(SPLIT(x[3], zs[3])), >=) & [(4)bni_19] >= 0 & 0 >= 0 & 0 >= 0 & [(2)bni_19] >= 0 & [(9)bni_19 + (-1)Bound*bni_19] >= 0 & 0 >= 0 & 0 >= 0 & [4 + (-1)bso_20] >= 0) 6.65/2.83 6.65/2.83 6.65/2.83 6.65/2.83 6.65/2.83 6.65/2.83 6.65/2.83 6.65/2.83 6.65/2.83 For Pair SPLIT(x[1], ins(y[1], zs[1])) -> COND_SPLIT(>(x[1], y[1]), x[1], ins(y[1], zs[1])) the following chains were created: 6.65/2.83 *We consider the chain SPLIT(x[1], ins(y[1], zs[1])) -> COND_SPLIT(>(x[1], y[1]), x[1], ins(y[1], zs[1])), COND_SPLIT(TRUE, x[3], ins(y[3], zs[3])) -> SPLIT(x[3], zs[3]) which results in the following constraint: 6.65/2.83 6.65/2.83 (1) (>(x[1], y[1])=TRUE & x[1]=x[3] & y[1]=y[3] & zs[1]=zs[3] ==> SPLIT(x[1], ins(y[1], zs[1]))_>=_NonInfC & SPLIT(x[1], ins(y[1], zs[1]))_>=_COND_SPLIT(>(x[1], y[1]), x[1], ins(y[1], zs[1])) & (U^Increasing(COND_SPLIT(>(x[1], y[1]), x[1], ins(y[1], zs[1]))), >=)) 6.65/2.83 6.65/2.83 6.65/2.83 6.65/2.83 We simplified constraint (1) using rule (IV) which results in the following new constraint: 6.65/2.83 6.65/2.83 (2) (>(x[1], y[1])=TRUE ==> SPLIT(x[1], ins(y[1], zs[1]))_>=_NonInfC & SPLIT(x[1], ins(y[1], zs[1]))_>=_COND_SPLIT(>(x[1], y[1]), x[1], ins(y[1], zs[1])) & (U^Increasing(COND_SPLIT(>(x[1], y[1]), x[1], ins(y[1], zs[1]))), >=)) 6.65/2.83 6.65/2.83 6.65/2.83 6.65/2.83 We simplified constraint (2) using rule (POLY_CONSTRAINTS) which results in the following new constraint: 6.65/2.83 6.65/2.83 (3) (0 >= 0 ==> (U^Increasing(COND_SPLIT(>(x[1], y[1]), x[1], ins(y[1], zs[1]))), >=) & [(5)bni_21 + (-1)Bound*bni_21] + [(4)bni_21]zs[1] + [(2)bni_21]x[1] >= 0 & [2 + (-1)bso_22] + [2]zs[1] >= 0) 6.65/2.83 6.65/2.83 6.65/2.83 6.65/2.83 We simplified constraint (3) using rule (IDP_POLY_SIMPLIFY) which results in the following new constraint: 6.65/2.83 6.65/2.83 (4) (0 >= 0 ==> (U^Increasing(COND_SPLIT(>(x[1], y[1]), x[1], ins(y[1], zs[1]))), >=) & [(5)bni_21 + (-1)Bound*bni_21] + [(4)bni_21]zs[1] + [(2)bni_21]x[1] >= 0 & [2 + (-1)bso_22] + [2]zs[1] >= 0) 6.65/2.83 6.65/2.83 6.65/2.83 6.65/2.83 We simplified constraint (4) using rule (POLY_REMOVE_MIN_MAX) which results in the following new constraint: 6.65/2.83 6.65/2.83 (5) (0 >= 0 ==> (U^Increasing(COND_SPLIT(>(x[1], y[1]), x[1], ins(y[1], zs[1]))), >=) & [(5)bni_21 + (-1)Bound*bni_21] + [(4)bni_21]zs[1] + [(2)bni_21]x[1] >= 0 & [2 + (-1)bso_22] + [2]zs[1] >= 0) 6.65/2.83 6.65/2.83 6.65/2.83 6.65/2.83 We simplified constraint (5) using rules (IDP_UNRESTRICTED_VARS), (IDP_POLY_GCD) which results in the following new constraint: 6.65/2.83 6.65/2.83 (6) (0 >= 0 ==> (U^Increasing(COND_SPLIT(>(x[1], y[1]), x[1], ins(y[1], zs[1]))), >=) & [(4)bni_21] >= 0 & 0 >= 0 & [(2)bni_21] >= 0 & [(5)bni_21 + (-1)Bound*bni_21] >= 0 & [2 + (-1)bso_22] >= 0 & [1] >= 0) 6.65/2.83 6.65/2.83 6.65/2.83 6.65/2.83 6.65/2.83 6.65/2.83 6.65/2.83 6.65/2.83 6.65/2.83 To summarize, we get the following constraints P__>=_ for the following pairs. 6.65/2.83 6.65/2.83 *COND_SPLIT1(TRUE, x[7], ins(y[7], zs[7])) -> SPLIT(x[7], zs[7]) 6.65/2.83 6.65/2.83 *(0 >= 0 ==> (U^Increasing(SPLIT(x[7], zs[7])), >=) & [(4)bni_15] >= 0 & 0 >= 0 & 0 >= 0 & [(2)bni_15] >= 0 & [(8)bni_15 + (-1)Bound*bni_15] >= 0 & 0 >= 0 & 0 >= 0 & [3 + (-1)bso_16] >= 0) 6.65/2.83 6.65/2.83 6.65/2.83 *(0 >= 0 ==> (U^Increasing(SPLIT(x[7], zs[7])), >=) & [(4)bni_15] >= 0 & 0 >= 0 & 0 >= 0 & [(2)bni_15] >= 0 & [(8)bni_15 + (-1)Bound*bni_15] >= 0 & 0 >= 0 & 0 >= 0 & [3 + (-1)bso_16] >= 0) 6.65/2.83 6.65/2.83 6.65/2.83 6.65/2.83 6.65/2.83 *SPLIT(x[5], ins(y[5], zs[5])) -> COND_SPLIT1(>=(y[5], x[5]), x[5], ins(y[5], zs[5])) 6.65/2.83 6.65/2.83 *(0 >= 0 ==> (U^Increasing(COND_SPLIT1(>=(y[5], x[5]), x[5], ins(y[5], zs[5]))), >=) & [(4)bni_17] >= 0 & 0 >= 0 & [(2)bni_17] >= 0 & [(5)bni_17 + (-1)Bound*bni_17] >= 0 & [3 + (-1)bso_18] >= 0 & [1] >= 0) 6.65/2.83 6.65/2.83 6.65/2.83 6.65/2.83 6.65/2.83 *COND_SPLIT(TRUE, x[3], ins(y[3], zs[3])) -> SPLIT(x[3], zs[3]) 6.65/2.83 6.65/2.83 *(0 >= 0 ==> (U^Increasing(SPLIT(x[3], zs[3])), >=) & [(4)bni_19] >= 0 & 0 >= 0 & 0 >= 0 & [(2)bni_19] >= 0 & [(9)bni_19 + (-1)Bound*bni_19] >= 0 & 0 >= 0 & 0 >= 0 & [4 + (-1)bso_20] >= 0) 6.65/2.83 6.65/2.83 6.65/2.83 *(0 >= 0 ==> (U^Increasing(SPLIT(x[3], zs[3])), >=) & [(4)bni_19] >= 0 & 0 >= 0 & 0 >= 0 & [(2)bni_19] >= 0 & [(9)bni_19 + (-1)Bound*bni_19] >= 0 & 0 >= 0 & 0 >= 0 & [4 + (-1)bso_20] >= 0) 6.65/2.83 6.65/2.83 6.65/2.83 6.65/2.83 6.65/2.83 *SPLIT(x[1], ins(y[1], zs[1])) -> COND_SPLIT(>(x[1], y[1]), x[1], ins(y[1], zs[1])) 6.65/2.83 6.65/2.83 *(0 >= 0 ==> (U^Increasing(COND_SPLIT(>(x[1], y[1]), x[1], ins(y[1], zs[1]))), >=) & [(4)bni_21] >= 0 & 0 >= 0 & [(2)bni_21] >= 0 & [(5)bni_21 + (-1)Bound*bni_21] >= 0 & [2 + (-1)bso_22] >= 0 & [1] >= 0) 6.65/2.83 6.65/2.83 6.65/2.83 6.65/2.83 6.65/2.83 6.65/2.83 6.65/2.83 6.65/2.83 6.65/2.83 The constraints for P_> respective P_bound are constructed from P__>=_ where we just replace every occurence of "t _>=_ s" in P__>=_ by "t > s" respective "t _>=_ c". Here c stands for the fresh constant used for P_bound. 6.65/2.83 6.65/2.83 Using the following integer polynomial ordering the resulting constraints can be solved 6.65/2.83 6.65/2.83 Polynomial interpretation over integers with natural coefficients for non-tuple symbols [NONINF][POLO]: 6.65/2.83 6.65/2.83 POL(TRUE) = 0 6.65/2.83 POL(FALSE) = 0 6.65/2.83 POL(COND_SPLIT1(x_1, x_2, x_3)) = [-1] + x_3 + [2]x_2 6.65/2.83 POL(ins(x_1, x_2)) = [3] + [2]x_2 6.65/2.83 POL(SPLIT(x_1, x_2)) = [-1] + [2]x_2 + [2]x_1 6.65/2.83 POL(>=(x_1, x_2)) = 0 6.65/2.83 POL(COND_SPLIT(x_1, x_2, x_3)) = x_3 + [2]x_2 6.65/2.83 POL(>(x_1, x_2)) = 0 6.65/2.83 6.65/2.83 6.65/2.83 The following pairs are in P_>: 6.65/2.83 6.65/2.83 6.65/2.83 COND_SPLIT1(TRUE, x[7], ins(y[7], zs[7])) -> SPLIT(x[7], zs[7]) 6.65/2.83 SPLIT(x[5], ins(y[5], zs[5])) -> COND_SPLIT1(>=(y[5], x[5]), x[5], ins(y[5], zs[5])) 6.65/2.83 COND_SPLIT(TRUE, x[3], ins(y[3], zs[3])) -> SPLIT(x[3], zs[3]) 6.65/2.83 SPLIT(x[1], ins(y[1], zs[1])) -> COND_SPLIT(>(x[1], y[1]), x[1], ins(y[1], zs[1])) 6.65/2.83 6.65/2.83 6.65/2.83 The following pairs are in P_bound: 6.65/2.83 6.65/2.83 6.65/2.83 COND_SPLIT1(TRUE, x[7], ins(y[7], zs[7])) -> SPLIT(x[7], zs[7]) 6.65/2.83 SPLIT(x[5], ins(y[5], zs[5])) -> COND_SPLIT1(>=(y[5], x[5]), x[5], ins(y[5], zs[5])) 6.65/2.83 COND_SPLIT(TRUE, x[3], ins(y[3], zs[3])) -> SPLIT(x[3], zs[3]) 6.65/2.83 SPLIT(x[1], ins(y[1], zs[1])) -> COND_SPLIT(>(x[1], y[1]), x[1], ins(y[1], zs[1])) 6.65/2.83 6.65/2.83 6.65/2.83 The following pairs are in P_>=: 6.65/2.83 6.65/2.83 none 6.65/2.83 6.65/2.83 6.65/2.83 There are no usable rules. 6.65/2.83 ---------------------------------------- 6.65/2.83 6.65/2.83 (20) 6.65/2.83 Obligation: 6.65/2.83 IDP problem: 6.65/2.83 The following function symbols are pre-defined: 6.65/2.83 <<< 6.65/2.83 & ~ Bwand: (Integer, Integer) -> Integer 6.65/2.83 >= ~ Ge: (Integer, Integer) -> Boolean 6.65/2.83 | ~ Bwor: (Integer, Integer) -> Integer 6.65/2.83 / ~ Div: (Integer, Integer) -> Integer 6.65/2.83 != ~ Neq: (Integer, Integer) -> Boolean 6.65/2.83 && ~ Land: (Boolean, Boolean) -> Boolean 6.65/2.83 ! ~ Lnot: (Boolean) -> Boolean 6.65/2.83 = ~ Eq: (Integer, Integer) -> Boolean 6.65/2.83 <= ~ Le: (Integer, Integer) -> Boolean 6.65/2.83 ^ ~ Bwxor: (Integer, Integer) -> Integer 6.65/2.83 % ~ Mod: (Integer, Integer) -> Integer 6.65/2.83 > ~ Gt: (Integer, Integer) -> Boolean 6.65/2.83 + ~ Add: (Integer, Integer) -> Integer 6.65/2.83 -1 ~ UnaryMinus: (Integer) -> Integer 6.65/2.83 < ~ Lt: (Integer, Integer) -> Boolean 6.65/2.83 || ~ Lor: (Boolean, Boolean) -> Boolean 6.65/2.83 - ~ Sub: (Integer, Integer) -> Integer 6.65/2.83 ~ ~ Bwnot: (Integer) -> Integer 6.65/2.83 * ~ Mul: (Integer, Integer) -> Integer 6.65/2.83 >>> 6.65/2.83 6.65/2.83 6.65/2.83 The following domains are used: 6.65/2.83 none 6.65/2.83 6.65/2.83 R is empty. 6.65/2.83 6.65/2.83 The integer pair graph is empty. 6.65/2.83 6.65/2.83 The set Q consists of the following terms: 6.65/2.83 app(nil, x0) 6.65/2.83 app(cons(x0, x1), x2) 6.65/2.83 split(x0, e) 6.65/2.83 split(x0, ins(x1, x2)) 6.65/2.83 Cond_split(TRUE, x0, ins(x1, x2)) 6.65/2.83 if_1(pair(x0, x1), x2, x3, x4) 6.65/2.83 Cond_if_1(TRUE, pair(x0, x1), x2, x3, x4) 6.65/2.83 Cond_split1(TRUE, x0, ins(x1, x2)) 6.65/2.83 if_2(pair(x0, x1), x2, x3, x4) 6.65/2.83 Cond_if_2(TRUE, pair(x0, x1), x2, x3, x4) 6.65/2.83 qsort(e) 6.65/2.83 qsort(ins(x0, x1)) 6.65/2.83 if_3(pair(x0, x1), x2, x3) 6.65/2.83 6.65/2.83 ---------------------------------------- 6.65/2.83 6.65/2.83 (21) PisEmptyProof (EQUIVALENT) 6.65/2.83 The TRS P is empty. Hence, there is no (P,Q,R) chain. 6.65/2.83 ---------------------------------------- 6.65/2.83 6.65/2.83 (22) 6.65/2.83 YES 6.65/2.83 6.65/2.83 ---------------------------------------- 6.65/2.83 6.65/2.83 (23) 6.65/2.83 Obligation: 6.65/2.83 IDP problem: 6.65/2.83 The following function symbols are pre-defined: 6.65/2.83 <<< 6.65/2.83 & ~ Bwand: (Integer, Integer) -> Integer 6.65/2.83 >= ~ Ge: (Integer, Integer) -> Boolean 6.65/2.83 | ~ Bwor: (Integer, Integer) -> Integer 6.65/2.83 / ~ Div: (Integer, Integer) -> Integer 6.65/2.83 != ~ Neq: (Integer, Integer) -> Boolean 6.65/2.83 && ~ Land: (Boolean, Boolean) -> Boolean 6.65/2.83 ! ~ Lnot: (Boolean) -> Boolean 6.65/2.83 = ~ Eq: (Integer, Integer) -> Boolean 6.65/2.83 <= ~ Le: (Integer, Integer) -> Boolean 6.65/2.83 ^ ~ Bwxor: (Integer, Integer) -> Integer 6.65/2.83 % ~ Mod: (Integer, Integer) -> Integer 6.65/2.83 > ~ Gt: (Integer, Integer) -> Boolean 6.65/2.83 + ~ Add: (Integer, Integer) -> Integer 6.65/2.83 -1 ~ UnaryMinus: (Integer) -> Integer 6.65/2.83 < ~ Lt: (Integer, Integer) -> Boolean 6.65/2.83 || ~ Lor: (Boolean, Boolean) -> Boolean 6.65/2.83 - ~ Sub: (Integer, Integer) -> Integer 6.65/2.83 ~ ~ Bwnot: (Integer) -> Integer 6.65/2.83 * ~ Mul: (Integer, Integer) -> Integer 6.65/2.83 >>> 6.65/2.83 6.65/2.83 6.65/2.83 The following domains are used: 6.65/2.83 Integer 6.65/2.83 6.65/2.83 The ITRS R consists of the following rules: 6.65/2.83 app(nil, zs) -> zs 6.65/2.83 app(cons(x, ys), zs) -> cons(x, app(ys, zs)) 6.65/2.83 split(x, e) -> pair(e, e) 6.65/2.83 split(x, ins(y, zs)) -> Cond_split(x > y, x, ins(y, zs)) 6.65/2.83 Cond_split(TRUE, x, ins(y, zs)) -> if_1(split(x, zs), x, y, zs) 6.65/2.83 if_1(pair(zl, zh), x, y, zs) -> Cond_if_1(x > y, pair(zl, zh), x, y, zs) 6.65/2.83 Cond_if_1(TRUE, pair(zl, zh), x, y, zs) -> pair(ins(y, zl), zh) 6.65/2.83 split(x, ins(y, zs)) -> Cond_split1(y >= x, x, ins(y, zs)) 6.65/2.83 Cond_split1(TRUE, x, ins(y, zs)) -> if_2(split(x, zs), x, y, zs) 6.65/2.83 if_2(pair(zl, zh), x, y, zs) -> Cond_if_2(y >= x, pair(zl, zh), x, y, zs) 6.65/2.83 Cond_if_2(TRUE, pair(zl, zh), x, y, zs) -> pair(zl, ins(y, zh)) 6.65/2.83 qsort(e) -> nil 6.65/2.83 qsort(ins(x, ys)) -> if_3(split(x, ys), x, ys) 6.65/2.83 if_3(pair(yl, yh), x, ys) -> app(qsort(yl), cons(x, qsort(yh))) 6.65/2.83 6.65/2.83 The integer pair graph contains the following rules and edges: 6.65/2.83 (13): IF_3(pair(yl[13], yh[13]), x[13], ys[13]) -> QSORT(yh[13]) 6.65/2.83 (12): IF_3(pair(yl[12], yh[12]), x[12], ys[12]) -> QSORT(yl[12]) 6.65/2.83 (9): QSORT(ins(x[9], ys[9])) -> IF_3(split(x[9], ys[9]), x[9], ys[9]) 6.65/2.83 6.65/2.83 (12) -> (9), if (yl[12] ->^* ins(x[9], ys[9])) 6.65/2.83 (13) -> (9), if (yh[13] ->^* ins(x[9], ys[9])) 6.65/2.83 (9) -> (12), if (split(x[9], ys[9]) ->^* pair(yl[12], yh[12]) & x[9] ->^* x[12] & ys[9] ->^* ys[12]) 6.65/2.83 (9) -> (13), if (split(x[9], ys[9]) ->^* pair(yl[13], yh[13]) & x[9] ->^* x[13] & ys[9] ->^* ys[13]) 6.65/2.83 6.65/2.83 The set Q consists of the following terms: 6.65/2.83 app(nil, x0) 6.65/2.83 app(cons(x0, x1), x2) 6.65/2.83 split(x0, e) 6.65/2.83 split(x0, ins(x1, x2)) 6.65/2.83 Cond_split(TRUE, x0, ins(x1, x2)) 6.65/2.83 if_1(pair(x0, x1), x2, x3, x4) 6.65/2.83 Cond_if_1(TRUE, pair(x0, x1), x2, x3, x4) 6.65/2.83 Cond_split1(TRUE, x0, ins(x1, x2)) 6.65/2.83 if_2(pair(x0, x1), x2, x3, x4) 6.65/2.83 Cond_if_2(TRUE, pair(x0, x1), x2, x3, x4) 6.65/2.83 qsort(e) 6.65/2.83 qsort(ins(x0, x1)) 6.65/2.83 if_3(pair(x0, x1), x2, x3) 6.65/2.83 6.65/2.83 ---------------------------------------- 6.65/2.83 6.65/2.83 (24) UsableRulesProof (EQUIVALENT) 6.65/2.83 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. 6.65/2.83 ---------------------------------------- 6.65/2.83 6.65/2.83 (25) 6.65/2.83 Obligation: 6.65/2.83 IDP problem: 6.65/2.83 The following function symbols are pre-defined: 6.65/2.83 <<< 6.65/2.83 & ~ Bwand: (Integer, Integer) -> Integer 6.65/2.83 >= ~ Ge: (Integer, Integer) -> Boolean 6.65/2.83 | ~ Bwor: (Integer, Integer) -> Integer 6.65/2.83 / ~ Div: (Integer, Integer) -> Integer 6.65/2.83 != ~ Neq: (Integer, Integer) -> Boolean 6.65/2.83 && ~ Land: (Boolean, Boolean) -> Boolean 6.65/2.83 ! ~ Lnot: (Boolean) -> Boolean 6.65/2.83 = ~ Eq: (Integer, Integer) -> Boolean 6.65/2.83 <= ~ Le: (Integer, Integer) -> Boolean 6.65/2.83 ^ ~ Bwxor: (Integer, Integer) -> Integer 6.65/2.83 % ~ Mod: (Integer, Integer) -> Integer 6.65/2.83 > ~ Gt: (Integer, Integer) -> Boolean 6.65/2.83 + ~ Add: (Integer, Integer) -> Integer 6.65/2.83 -1 ~ UnaryMinus: (Integer) -> Integer 6.65/2.83 < ~ Lt: (Integer, Integer) -> Boolean 6.65/2.83 || ~ Lor: (Boolean, Boolean) -> Boolean 6.65/2.83 - ~ Sub: (Integer, Integer) -> Integer 6.65/2.83 ~ ~ Bwnot: (Integer) -> Integer 6.65/2.83 * ~ Mul: (Integer, Integer) -> Integer 6.65/2.83 >>> 6.65/2.83 6.65/2.83 6.65/2.83 The following domains are used: 6.65/2.83 Integer 6.65/2.83 6.65/2.83 The ITRS R consists of the following rules: 6.65/2.83 split(x, e) -> pair(e, e) 6.65/2.83 split(x, ins(y, zs)) -> Cond_split(x > y, x, ins(y, zs)) 6.65/2.83 split(x, ins(y, zs)) -> Cond_split1(y >= x, x, ins(y, zs)) 6.65/2.83 Cond_split(TRUE, x, ins(y, zs)) -> if_1(split(x, zs), x, y, zs) 6.65/2.83 Cond_split1(TRUE, x, ins(y, zs)) -> if_2(split(x, zs), x, y, zs) 6.65/2.83 if_1(pair(zl, zh), x, y, zs) -> Cond_if_1(x > y, pair(zl, zh), x, y, zs) 6.65/2.83 if_2(pair(zl, zh), x, y, zs) -> Cond_if_2(y >= x, pair(zl, zh), x, y, zs) 6.65/2.83 Cond_if_1(TRUE, pair(zl, zh), x, y, zs) -> pair(ins(y, zl), zh) 6.65/2.83 Cond_if_2(TRUE, pair(zl, zh), x, y, zs) -> pair(zl, ins(y, zh)) 6.65/2.83 6.65/2.83 The integer pair graph contains the following rules and edges: 6.65/2.83 (13): IF_3(pair(yl[13], yh[13]), x[13], ys[13]) -> QSORT(yh[13]) 6.65/2.83 (12): IF_3(pair(yl[12], yh[12]), x[12], ys[12]) -> QSORT(yl[12]) 6.65/2.83 (9): QSORT(ins(x[9], ys[9])) -> IF_3(split(x[9], ys[9]), x[9], ys[9]) 6.65/2.83 6.65/2.83 (12) -> (9), if (yl[12] ->^* ins(x[9], ys[9])) 6.65/2.83 (13) -> (9), if (yh[13] ->^* ins(x[9], ys[9])) 6.65/2.83 (9) -> (12), if (split(x[9], ys[9]) ->^* pair(yl[12], yh[12]) & x[9] ->^* x[12] & ys[9] ->^* ys[12]) 6.65/2.83 (9) -> (13), if (split(x[9], ys[9]) ->^* pair(yl[13], yh[13]) & x[9] ->^* x[13] & ys[9] ->^* ys[13]) 6.65/2.83 6.65/2.83 The set Q consists of the following terms: 6.65/2.83 app(nil, x0) 6.65/2.83 app(cons(x0, x1), x2) 6.65/2.83 split(x0, e) 6.65/2.83 split(x0, ins(x1, x2)) 6.65/2.83 Cond_split(TRUE, x0, ins(x1, x2)) 6.65/2.83 if_1(pair(x0, x1), x2, x3, x4) 6.65/2.83 Cond_if_1(TRUE, pair(x0, x1), x2, x3, x4) 6.65/2.83 Cond_split1(TRUE, x0, ins(x1, x2)) 6.65/2.83 if_2(pair(x0, x1), x2, x3, x4) 6.65/2.83 Cond_if_2(TRUE, pair(x0, x1), x2, x3, x4) 6.65/2.83 qsort(e) 6.65/2.83 qsort(ins(x0, x1)) 6.65/2.83 if_3(pair(x0, x1), x2, x3) 6.65/2.83 6.65/2.83 ---------------------------------------- 6.65/2.83 6.65/2.83 (26) IDPNonInfProof (SOUND) 6.65/2.83 Used the following options for this NonInfProof: 6.65/2.83 6.65/2.83 IDPGPoloSolver: 6.65/2.83 Range: [(-1,2)] 6.65/2.83 IsNat: true 6.65/2.83 Interpretation Shape Heuristic: aprove.DPFramework.IDPProblem.Processors.nonInf.poly.IdpDefaultShapeHeuristic@543a0a6c 6.65/2.83 Constraint Generator: NonInfConstraintGenerator: 6.65/2.83 PathGenerator: MetricPathGenerator: 6.65/2.83 Max Left Steps: 1 6.65/2.83 Max Right Steps: 1 6.65/2.83 6.65/2.83 6.65/2.83 6.65/2.83 The constraints were generated the following way: 6.65/2.83 6.65/2.83 The DP Problem is simplified using the Induction Calculus [NONINF] with the following steps: 6.65/2.83 6.65/2.83 Note that final constraints are written in bold face. 6.65/2.83 6.65/2.83 6.65/2.83 6.65/2.83 For Pair IF_3(pair(yl[13], yh[13]), x[13], ys[13]) -> QSORT(yh[13]) the following chains were created: 6.65/2.83 *We consider the chain QSORT(ins(x[9], ys[9])) -> IF_3(split(x[9], ys[9]), x[9], ys[9]), IF_3(pair(yl[13], yh[13]), x[13], ys[13]) -> QSORT(yh[13]), QSORT(ins(x[9], ys[9])) -> IF_3(split(x[9], ys[9]), x[9], ys[9]) which results in the following constraint: 6.65/2.83 6.65/2.83 (1) (split(x[9], ys[9])=pair(yl[13], yh[13]) & x[9]=x[13] & ys[9]=ys[13] & yh[13]=ins(x[9]1, ys[9]1) ==> IF_3(pair(yl[13], yh[13]), x[13], ys[13])_>=_NonInfC & IF_3(pair(yl[13], yh[13]), x[13], ys[13])_>=_QSORT(yh[13]) & (U^Increasing(QSORT(yh[13])), >=)) 6.65/2.83 6.65/2.83 6.65/2.83 6.65/2.83 We simplified constraint (1) using rule (III) which results in the following new constraint: 6.65/2.83 6.65/2.83 (2) (split(x[9], ys[9])=pair(yl[13], ins(x[9]1, ys[9]1)) ==> IF_3(pair(yl[13], ins(x[9]1, ys[9]1)), x[9], ys[9])_>=_NonInfC & IF_3(pair(yl[13], ins(x[9]1, ys[9]1)), x[9], ys[9])_>=_QSORT(ins(x[9]1, ys[9]1)) & (U^Increasing(QSORT(yh[13])), >=)) 6.65/2.83 6.65/2.83 6.65/2.83 6.65/2.83 We simplified constraint (2) using rule (V) (with possible (I) afterwards) using induction on split(x[9], ys[9])=pair(yl[13], ins(x[9]1, ys[9]1)) which results in the following new constraints: 6.65/2.83 6.65/2.83 (3) (pair(e, e)=pair(yl[13], ins(x[9]1, ys[9]1)) ==> IF_3(pair(yl[13], ins(x[9]1, ys[9]1)), x0, e)_>=_NonInfC & IF_3(pair(yl[13], ins(x[9]1, ys[9]1)), x0, e)_>=_QSORT(ins(x[9]1, ys[9]1)) & (U^Increasing(QSORT(yh[13])), >=)) 6.65/2.83 6.65/2.83 (4) (Cond_split(>(x3, x2), x3, ins(x2, x1))=pair(yl[13], ins(x[9]1, ys[9]1)) ==> IF_3(pair(yl[13], ins(x[9]1, ys[9]1)), x3, ins(x2, x1))_>=_NonInfC & IF_3(pair(yl[13], ins(x[9]1, ys[9]1)), x3, ins(x2, x1))_>=_QSORT(ins(x[9]1, ys[9]1)) & (U^Increasing(QSORT(yh[13])), >=)) 6.65/2.83 6.65/2.83 (5) (Cond_split1(>=(x5, x6), x6, ins(x5, x4))=pair(yl[13], ins(x[9]1, ys[9]1)) ==> IF_3(pair(yl[13], ins(x[9]1, ys[9]1)), x6, ins(x5, x4))_>=_NonInfC & IF_3(pair(yl[13], ins(x[9]1, ys[9]1)), x6, ins(x5, x4))_>=_QSORT(ins(x[9]1, ys[9]1)) & (U^Increasing(QSORT(yh[13])), >=)) 6.65/2.83 6.65/2.83 6.65/2.83 6.65/2.83 We solved constraint (3) using rules (I), (II).We simplified constraint (4) using rules (III), (VII) which results in the following new constraint: 6.65/2.83 6.65/2.83 (6) (Cond_split(>(x3, x2), x3, ins(x2, x1))=pair(yl[13], ins(x[9]1, ys[9]1)) ==> IF_3(pair(yl[13], ins(x[9]1, ys[9]1)), x3, ins(x2, x1))_>=_NonInfC & IF_3(pair(yl[13], ins(x[9]1, ys[9]1)), x3, ins(x2, x1))_>=_QSORT(ins(x[9]1, ys[9]1)) & (U^Increasing(QSORT(yh[13])), >=)) 6.65/2.83 6.65/2.83 6.65/2.83 6.65/2.83 We simplified constraint (5) using rules (III), (VII) which results in the following new constraint: 6.65/2.83 6.65/2.83 (7) (Cond_split1(>=(x5, x6), x6, ins(x5, x4))=pair(yl[13], ins(x[9]1, ys[9]1)) ==> IF_3(pair(yl[13], ins(x[9]1, ys[9]1)), x6, ins(x5, x4))_>=_NonInfC & IF_3(pair(yl[13], ins(x[9]1, ys[9]1)), x6, ins(x5, x4))_>=_QSORT(ins(x[9]1, ys[9]1)) & (U^Increasing(QSORT(yh[13])), >=)) 6.65/2.83 6.65/2.83 6.65/2.83 6.65/2.83 We simplified constraint (6) using rule (POLY_CONSTRAINTS) which results in the following new constraint: 6.65/2.83 6.65/2.83 (8) ((U^Increasing(QSORT(yh[13])), >=) & [bni_47 + (-1)Bound*bni_47] + [(3)bni_47]ys[9]1 + [bni_47]yl[13] >= 0 & [1 + (-1)bso_48] + yl[13] >= 0) 6.65/2.83 6.65/2.83 6.65/2.83 6.65/2.83 We simplified constraint (7) using rule (POLY_CONSTRAINTS) which results in the following new constraint: 6.65/2.83 6.65/2.83 (9) ((U^Increasing(QSORT(yh[13])), >=) & [bni_47 + (-1)Bound*bni_47] + [(3)bni_47]ys[9]1 + [bni_47]yl[13] >= 0 & [1 + (-1)bso_48] + yl[13] >= 0) 6.65/2.83 6.65/2.83 6.65/2.83 6.65/2.83 We simplified constraint (9) using rule (IDP_POLY_SIMPLIFY) which results in the following new constraint: 6.65/2.83 6.65/2.83 (10) ((U^Increasing(QSORT(yh[13])), >=) & [bni_47 + (-1)Bound*bni_47] + [(3)bni_47]ys[9]1 + [bni_47]yl[13] >= 0 & [1 + (-1)bso_48] + yl[13] >= 0) 6.65/2.83 6.65/2.83 6.65/2.83 6.65/2.83 We simplified constraint (8) using rule (IDP_POLY_SIMPLIFY) which results in the following new constraint: 6.65/2.83 6.65/2.83 (11) ((U^Increasing(QSORT(yh[13])), >=) & [bni_47 + (-1)Bound*bni_47] + [(3)bni_47]ys[9]1 + [bni_47]yl[13] >= 0 & [1 + (-1)bso_48] + yl[13] >= 0) 6.65/2.83 6.65/2.83 6.65/2.83 6.65/2.83 We simplified constraint (10) using rule (POLY_REMOVE_MIN_MAX) which results in the following new constraint: 6.65/2.83 6.65/2.83 (12) ((U^Increasing(QSORT(yh[13])), >=) & [bni_47 + (-1)Bound*bni_47] + [(3)bni_47]ys[9]1 + [bni_47]yl[13] >= 0 & [1 + (-1)bso_48] + yl[13] >= 0) 6.65/2.83 6.65/2.83 6.65/2.83 6.65/2.83 We simplified constraint (11) using rule (POLY_REMOVE_MIN_MAX) which results in the following new constraint: 6.65/2.83 6.65/2.83 (13) ((U^Increasing(QSORT(yh[13])), >=) & [bni_47 + (-1)Bound*bni_47] + [(3)bni_47]ys[9]1 + [bni_47]yl[13] >= 0 & [1 + (-1)bso_48] + yl[13] >= 0) 6.65/2.83 6.65/2.83 6.65/2.83 6.65/2.83 We simplified constraint (12) using rule (IDP_UNRESTRICTED_VARS) which results in the following new constraint: 6.65/2.83 6.65/2.83 (14) ((U^Increasing(QSORT(yh[13])), >=) & 0 >= 0 & 0 >= 0 & 0 >= 0 & [(3)bni_47] >= 0 & 0 >= 0 & [bni_47] >= 0 & [bni_47 + (-1)Bound*bni_47] >= 0 & 0 >= 0 & 0 >= 0 & 0 >= 0 & [1] >= 0 & [1 + (-1)bso_48] >= 0) 6.65/2.83 6.65/2.83 6.65/2.83 6.65/2.83 We simplified constraint (13) using rule (IDP_UNRESTRICTED_VARS) which results in the following new constraint: 6.65/2.83 6.65/2.83 (15) ((U^Increasing(QSORT(yh[13])), >=) & 0 >= 0 & 0 >= 0 & 0 >= 0 & [(3)bni_47] >= 0 & 0 >= 0 & [bni_47] >= 0 & [bni_47 + (-1)Bound*bni_47] >= 0 & 0 >= 0 & 0 >= 0 & 0 >= 0 & [1] >= 0 & [1 + (-1)bso_48] >= 0) 6.65/2.83 6.65/2.83 6.65/2.83 6.65/2.83 6.65/2.83 6.65/2.83 6.65/2.83 6.65/2.83 6.65/2.83 For Pair IF_3(pair(yl[12], yh[12]), x[12], ys[12]) -> QSORT(yl[12]) the following chains were created: 6.65/2.83 *We consider the chain QSORT(ins(x[9], ys[9])) -> IF_3(split(x[9], ys[9]), x[9], ys[9]), IF_3(pair(yl[12], yh[12]), x[12], ys[12]) -> QSORT(yl[12]), QSORT(ins(x[9], ys[9])) -> IF_3(split(x[9], ys[9]), x[9], ys[9]) which results in the following constraint: 6.65/2.83 6.65/2.83 (1) (split(x[9], ys[9])=pair(yl[12], yh[12]) & x[9]=x[12] & ys[9]=ys[12] & yl[12]=ins(x[9]1, ys[9]1) ==> IF_3(pair(yl[12], yh[12]), x[12], ys[12])_>=_NonInfC & IF_3(pair(yl[12], yh[12]), x[12], ys[12])_>=_QSORT(yl[12]) & (U^Increasing(QSORT(yl[12])), >=)) 6.65/2.83 6.65/2.83 6.65/2.83 6.65/2.83 We simplified constraint (1) using rule (III) which results in the following new constraint: 6.65/2.83 6.65/2.83 (2) (split(x[9], ys[9])=pair(ins(x[9]1, ys[9]1), yh[12]) ==> IF_3(pair(ins(x[9]1, ys[9]1), yh[12]), x[9], ys[9])_>=_NonInfC & IF_3(pair(ins(x[9]1, ys[9]1), yh[12]), x[9], ys[9])_>=_QSORT(ins(x[9]1, ys[9]1)) & (U^Increasing(QSORT(yl[12])), >=)) 6.65/2.83 6.65/2.83 6.65/2.83 6.65/2.83 We simplified constraint (2) using rule (V) (with possible (I) afterwards) using induction on split(x[9], ys[9])=pair(ins(x[9]1, ys[9]1), yh[12]) which results in the following new constraints: 6.65/2.83 6.65/2.83 (3) (pair(e, e)=pair(ins(x[9]1, ys[9]1), yh[12]) ==> IF_3(pair(ins(x[9]1, ys[9]1), yh[12]), x11, e)_>=_NonInfC & IF_3(pair(ins(x[9]1, ys[9]1), yh[12]), x11, e)_>=_QSORT(ins(x[9]1, ys[9]1)) & (U^Increasing(QSORT(yl[12])), >=)) 6.65/2.83 6.65/2.83 (4) (Cond_split(>(x14, x13), x14, ins(x13, x12))=pair(ins(x[9]1, ys[9]1), yh[12]) ==> IF_3(pair(ins(x[9]1, ys[9]1), yh[12]), x14, ins(x13, x12))_>=_NonInfC & IF_3(pair(ins(x[9]1, ys[9]1), yh[12]), x14, ins(x13, x12))_>=_QSORT(ins(x[9]1, ys[9]1)) & (U^Increasing(QSORT(yl[12])), >=)) 6.65/2.83 6.65/2.83 (5) (Cond_split1(>=(x16, x17), x17, ins(x16, x15))=pair(ins(x[9]1, ys[9]1), yh[12]) ==> IF_3(pair(ins(x[9]1, ys[9]1), yh[12]), x17, ins(x16, x15))_>=_NonInfC & IF_3(pair(ins(x[9]1, ys[9]1), yh[12]), x17, ins(x16, x15))_>=_QSORT(ins(x[9]1, ys[9]1)) & (U^Increasing(QSORT(yl[12])), >=)) 6.65/2.83 6.65/2.83 6.65/2.83 6.65/2.83 We solved constraint (3) using rules (I), (II).We simplified constraint (4) using rules (III), (VII) which results in the following new constraint: 6.65/2.83 6.65/2.83 (6) (Cond_split(>(x14, x13), x14, ins(x13, x12))=pair(ins(x[9]1, ys[9]1), yh[12]) ==> IF_3(pair(ins(x[9]1, ys[9]1), yh[12]), x14, ins(x13, x12))_>=_NonInfC & IF_3(pair(ins(x[9]1, ys[9]1), yh[12]), x14, ins(x13, x12))_>=_QSORT(ins(x[9]1, ys[9]1)) & (U^Increasing(QSORT(yl[12])), >=)) 6.65/2.83 6.65/2.83 6.65/2.83 6.65/2.83 We simplified constraint (5) using rules (III), (VII) which results in the following new constraint: 6.65/2.83 6.65/2.83 (7) (Cond_split1(>=(x16, x17), x17, ins(x16, x15))=pair(ins(x[9]1, ys[9]1), yh[12]) ==> IF_3(pair(ins(x[9]1, ys[9]1), yh[12]), x17, ins(x16, x15))_>=_NonInfC & IF_3(pair(ins(x[9]1, ys[9]1), yh[12]), x17, ins(x16, x15))_>=_QSORT(ins(x[9]1, ys[9]1)) & (U^Increasing(QSORT(yl[12])), >=)) 6.65/2.83 6.65/2.83 6.65/2.83 6.65/2.83 We simplified constraint (6) using rule (POLY_CONSTRAINTS) which results in the following new constraint: 6.65/2.83 6.65/2.83 (8) ((U^Increasing(QSORT(yl[12])), >=) & [bni_49 + (-1)Bound*bni_49] + [bni_49]yh[12] + [(3)bni_49]ys[9]1 >= 0 & [1 + (-1)bso_50] + yh[12] >= 0) 6.65/2.83 6.65/2.83 6.65/2.83 6.65/2.83 We simplified constraint (7) using rule (POLY_CONSTRAINTS) which results in the following new constraint: 6.65/2.83 6.65/2.83 (9) ((U^Increasing(QSORT(yl[12])), >=) & [bni_49 + (-1)Bound*bni_49] + [bni_49]yh[12] + [(3)bni_49]ys[9]1 >= 0 & [1 + (-1)bso_50] + yh[12] >= 0) 6.65/2.83 6.65/2.83 6.65/2.83 6.65/2.83 We simplified constraint (9) using rule (IDP_POLY_SIMPLIFY) which results in the following new constraint: 6.65/2.83 6.65/2.83 (10) ((U^Increasing(QSORT(yl[12])), >=) & [bni_49 + (-1)Bound*bni_49] + [bni_49]yh[12] + [(3)bni_49]ys[9]1 >= 0 & [1 + (-1)bso_50] + yh[12] >= 0) 6.65/2.83 6.65/2.83 6.65/2.83 6.65/2.83 We simplified constraint (8) using rule (IDP_POLY_SIMPLIFY) which results in the following new constraint: 6.65/2.83 6.65/2.83 (11) ((U^Increasing(QSORT(yl[12])), >=) & [bni_49 + (-1)Bound*bni_49] + [bni_49]yh[12] + [(3)bni_49]ys[9]1 >= 0 & [1 + (-1)bso_50] + yh[12] >= 0) 6.65/2.83 6.65/2.83 6.65/2.83 6.65/2.83 We simplified constraint (10) using rule (POLY_REMOVE_MIN_MAX) which results in the following new constraint: 6.65/2.83 6.65/2.83 (12) ((U^Increasing(QSORT(yl[12])), >=) & [bni_49 + (-1)Bound*bni_49] + [bni_49]yh[12] + [(3)bni_49]ys[9]1 >= 0 & [1 + (-1)bso_50] + yh[12] >= 0) 6.65/2.83 6.65/2.83 6.65/2.83 6.65/2.83 We simplified constraint (11) using rule (POLY_REMOVE_MIN_MAX) which results in the following new constraint: 6.65/2.83 6.65/2.83 (13) ((U^Increasing(QSORT(yl[12])), >=) & [bni_49 + (-1)Bound*bni_49] + [bni_49]yh[12] + [(3)bni_49]ys[9]1 >= 0 & [1 + (-1)bso_50] + yh[12] >= 0) 6.65/2.83 6.65/2.83 6.65/2.83 6.65/2.83 We simplified constraint (12) using rule (IDP_UNRESTRICTED_VARS) which results in the following new constraint: 6.65/2.83 6.65/2.83 (14) ((U^Increasing(QSORT(yl[12])), >=) & 0 >= 0 & 0 >= 0 & 0 >= 0 & [bni_49] >= 0 & [(3)bni_49] >= 0 & 0 >= 0 & [bni_49 + (-1)Bound*bni_49] >= 0 & 0 >= 0 & 0 >= 0 & 0 >= 0 & [1] >= 0 & [1 + (-1)bso_50] >= 0) 6.65/2.83 6.65/2.83 6.65/2.83 6.65/2.83 We simplified constraint (13) using rule (IDP_UNRESTRICTED_VARS) which results in the following new constraint: 6.65/2.83 6.65/2.83 (15) ((U^Increasing(QSORT(yl[12])), >=) & 0 >= 0 & 0 >= 0 & 0 >= 0 & [bni_49] >= 0 & [(3)bni_49] >= 0 & 0 >= 0 & [bni_49 + (-1)Bound*bni_49] >= 0 & 0 >= 0 & 0 >= 0 & 0 >= 0 & [1] >= 0 & [1 + (-1)bso_50] >= 0) 6.65/2.83 6.65/2.83 6.65/2.83 6.65/2.83 6.65/2.83 6.65/2.83 6.65/2.83 6.65/2.83 6.65/2.83 For Pair QSORT(ins(x[9], ys[9])) -> IF_3(split(x[9], ys[9]), x[9], ys[9]) the following chains were created: 6.65/2.83 *We consider the chain IF_3(pair(yl[12], yh[12]), x[12], ys[12]) -> QSORT(yl[12]), QSORT(ins(x[9], ys[9])) -> IF_3(split(x[9], ys[9]), x[9], ys[9]), IF_3(pair(yl[12], yh[12]), x[12], ys[12]) -> QSORT(yl[12]) which results in the following constraint: 6.65/2.83 6.65/2.83 (1) (yl[12]=ins(x[9], ys[9]) & split(x[9], ys[9])=pair(yl[12]1, yh[12]1) & x[9]=x[12]1 & ys[9]=ys[12]1 ==> QSORT(ins(x[9], ys[9]))_>=_NonInfC & QSORT(ins(x[9], ys[9]))_>=_IF_3(split(x[9], ys[9]), x[9], ys[9]) & (U^Increasing(IF_3(split(x[9], ys[9]), x[9], ys[9])), >=)) 6.65/2.83 6.65/2.83 6.65/2.83 6.65/2.83 We simplified constraint (1) using rules (III), (IV) which results in the following new constraint: 6.65/2.83 6.65/2.83 (2) (split(x[9], ys[9])=pair(yl[12]1, yh[12]1) ==> QSORT(ins(x[9], ys[9]))_>=_NonInfC & QSORT(ins(x[9], ys[9]))_>=_IF_3(split(x[9], ys[9]), x[9], ys[9]) & (U^Increasing(IF_3(split(x[9], ys[9]), x[9], ys[9])), >=)) 6.65/2.83 6.65/2.83 6.65/2.83 6.65/2.83 We simplified constraint (2) using rule (V) (with possible (I) afterwards) using induction on split(x[9], ys[9])=pair(yl[12]1, yh[12]1) which results in the following new constraints: 6.65/2.83 6.65/2.83 (3) (pair(e, e)=pair(yl[12]1, yh[12]1) ==> QSORT(ins(x22, e))_>=_NonInfC & QSORT(ins(x22, e))_>=_IF_3(split(x22, e), x22, e) & (U^Increasing(IF_3(split(x[9], ys[9]), x[9], ys[9])), >=)) 6.65/2.83 6.65/2.83 (4) (Cond_split(>(x25, x24), x25, ins(x24, x23))=pair(yl[12]1, yh[12]1) ==> QSORT(ins(x25, ins(x24, x23)))_>=_NonInfC & QSORT(ins(x25, ins(x24, x23)))_>=_IF_3(split(x25, ins(x24, x23)), x25, ins(x24, x23)) & (U^Increasing(IF_3(split(x[9], ys[9]), x[9], ys[9])), >=)) 6.65/2.83 6.65/2.83 (5) (Cond_split1(>=(x27, x28), x28, ins(x27, x26))=pair(yl[12]1, yh[12]1) ==> QSORT(ins(x28, ins(x27, x26)))_>=_NonInfC & QSORT(ins(x28, ins(x27, x26)))_>=_IF_3(split(x28, ins(x27, x26)), x28, ins(x27, x26)) & (U^Increasing(IF_3(split(x[9], ys[9]), x[9], ys[9])), >=)) 6.65/2.83 6.65/2.83 6.65/2.83 6.65/2.83 We simplified constraint (3) using rules (I), (II), (IV) which results in the following new constraint: 6.65/2.83 6.65/2.83 (6) (QSORT(ins(x22, e))_>=_NonInfC & QSORT(ins(x22, e))_>=_IF_3(split(x22, e), x22, e) & (U^Increasing(IF_3(split(x[9], ys[9]), x[9], ys[9])), >=)) 6.65/2.83 6.65/2.83 6.65/2.83 6.65/2.83 We simplified constraint (4) using rules (III), (VII) which results in the following new constraint: 6.65/2.83 6.65/2.83 (7) (Cond_split(>(x25, x24), x25, ins(x24, x23))=pair(yl[12]1, yh[12]1) ==> QSORT(ins(x25, ins(x24, x23)))_>=_NonInfC & QSORT(ins(x25, ins(x24, x23)))_>=_IF_3(split(x25, ins(x24, x23)), x25, ins(x24, x23)) & (U^Increasing(IF_3(split(x[9], ys[9]), x[9], ys[9])), >=)) 6.65/2.83 6.65/2.83 6.65/2.83 6.65/2.83 We simplified constraint (5) using rules (III), (VII) which results in the following new constraint: 6.65/2.83 6.65/2.83 (8) (Cond_split1(>=(x27, x28), x28, ins(x27, x26))=pair(yl[12]1, yh[12]1) ==> QSORT(ins(x28, ins(x27, x26)))_>=_NonInfC & QSORT(ins(x28, ins(x27, x26)))_>=_IF_3(split(x28, ins(x27, x26)), x28, ins(x27, x26)) & (U^Increasing(IF_3(split(x[9], ys[9]), x[9], ys[9])), >=)) 6.65/2.83 6.65/2.83 6.65/2.83 6.65/2.83 We simplified constraint (6) using rule (POLY_CONSTRAINTS) which results in the following new constraint: 6.65/2.83 6.65/2.83 (9) ((U^Increasing(IF_3(split(x[9], ys[9]), x[9], ys[9])), >=) & [bni_51] = 0 & [1 + (-1)bso_52] >= 0) 6.65/2.83 6.65/2.83 6.65/2.83 6.65/2.83 We simplified constraint (7) using rule (POLY_CONSTRAINTS) which results in the following new constraint: 6.65/2.83 6.65/2.83 (10) ((U^Increasing(IF_3(split(x[9], ys[9]), x[9], ys[9])), >=) & 0 >= 0 & [1 + (-1)bso_52] >= 0) 6.65/2.83 6.65/2.83 6.65/2.83 6.65/2.83 We simplified constraint (8) using rule (POLY_CONSTRAINTS) which results in the following new constraint: 6.65/2.83 6.65/2.83 (11) ((U^Increasing(IF_3(split(x[9], ys[9]), x[9], ys[9])), >=) & 0 >= 0 & [1 + (-1)bso_52] >= 0) 6.65/2.83 6.65/2.83 6.65/2.83 6.65/2.83 We simplified constraint (9) using rule (IDP_POLY_SIMPLIFY) which results in the following new constraint: 6.65/2.83 6.65/2.83 (12) ((U^Increasing(IF_3(split(x[9], ys[9]), x[9], ys[9])), >=) & [bni_51] = 0 & [1 + (-1)bso_52] >= 0) 6.65/2.83 6.65/2.83 6.65/2.83 6.65/2.83 We simplified constraint (11) using rule (IDP_POLY_SIMPLIFY) which results in the following new constraint: 6.65/2.83 6.65/2.83 (13) ((U^Increasing(IF_3(split(x[9], ys[9]), x[9], ys[9])), >=) & 0 >= 0 & [1 + (-1)bso_52] >= 0) 6.65/2.83 6.65/2.83 6.65/2.83 6.65/2.83 We simplified constraint (10) using rule (IDP_POLY_SIMPLIFY) which results in the following new constraint: 6.65/2.83 6.65/2.83 (14) ((U^Increasing(IF_3(split(x[9], ys[9]), x[9], ys[9])), >=) & 0 >= 0 & [1 + (-1)bso_52] >= 0) 6.65/2.83 6.65/2.83 6.65/2.83 6.65/2.83 We simplified constraint (12) using rule (POLY_REMOVE_MIN_MAX) which results in the following new constraint: 6.65/2.83 6.65/2.83 (15) ((U^Increasing(IF_3(split(x[9], ys[9]), x[9], ys[9])), >=) & [bni_51] = 0 & [1 + (-1)bso_52] >= 0) 6.65/2.83 6.65/2.83 6.65/2.83 6.65/2.83 We simplified constraint (13) using rule (POLY_REMOVE_MIN_MAX) which results in the following new constraint: 6.65/2.83 6.65/2.83 (16) ((U^Increasing(IF_3(split(x[9], ys[9]), x[9], ys[9])), >=) & 0 >= 0 & [1 + (-1)bso_52] >= 0) 6.65/2.83 6.65/2.83 6.65/2.83 6.65/2.83 We simplified constraint (14) using rule (POLY_REMOVE_MIN_MAX) which results in the following new constraint: 6.65/2.83 6.65/2.83 (17) ((U^Increasing(IF_3(split(x[9], ys[9]), x[9], ys[9])), >=) & 0 >= 0 & [1 + (-1)bso_52] >= 0) 6.65/2.83 6.65/2.83 6.65/2.83 6.65/2.83 We simplified constraint (15) using rule (IDP_UNRESTRICTED_VARS) which results in the following new constraint: 6.65/2.83 6.65/2.83 (18) ((U^Increasing(IF_3(split(x[9], ys[9]), x[9], ys[9])), >=) & [bni_51] = 0 & 0 >= 0 & [1 + (-1)bso_52] >= 0) 6.65/2.83 6.65/2.83 6.65/2.83 6.65/2.83 We simplified constraint (16) using rule (IDP_UNRESTRICTED_VARS) which results in the following new constraint: 6.65/2.83 6.65/2.83 (19) ((U^Increasing(IF_3(split(x[9], ys[9]), x[9], ys[9])), >=) & 0 >= 0 & 0 >= 0 & 0 >= 0 & 0 >= 0 & 0 >= 0 & 0 >= 0 & [1 + (-1)bso_52] >= 0) 6.65/2.83 6.65/2.83 6.65/2.83 6.65/2.83 We simplified constraint (17) using rule (IDP_UNRESTRICTED_VARS) which results in the following new constraint: 6.65/2.83 6.65/2.83 (20) ((U^Increasing(IF_3(split(x[9], ys[9]), x[9], ys[9])), >=) & 0 >= 0 & 0 >= 0 & 0 >= 0 & 0 >= 0 & 0 >= 0 & 0 >= 0 & [1 + (-1)bso_52] >= 0) 6.65/2.83 6.65/2.83 6.65/2.83 6.65/2.83 6.65/2.83 *We consider the chain IF_3(pair(yl[13], yh[13]), x[13], ys[13]) -> QSORT(yh[13]), QSORT(ins(x[9], ys[9])) -> IF_3(split(x[9], ys[9]), x[9], ys[9]), IF_3(pair(yl[12], yh[12]), x[12], ys[12]) -> QSORT(yl[12]) which results in the following constraint: 6.65/2.83 6.65/2.83 (1) (yh[13]=ins(x[9], ys[9]) & split(x[9], ys[9])=pair(yl[12], yh[12]) & x[9]=x[12] & ys[9]=ys[12] ==> QSORT(ins(x[9], ys[9]))_>=_NonInfC & QSORT(ins(x[9], ys[9]))_>=_IF_3(split(x[9], ys[9]), x[9], ys[9]) & (U^Increasing(IF_3(split(x[9], ys[9]), x[9], ys[9])), >=)) 6.65/2.83 6.65/2.83 6.65/2.83 6.65/2.83 We simplified constraint (1) using rules (III), (IV) which results in the following new constraint: 6.65/2.83 6.65/2.83 (2) (split(x[9], ys[9])=pair(yl[12], yh[12]) ==> QSORT(ins(x[9], ys[9]))_>=_NonInfC & QSORT(ins(x[9], ys[9]))_>=_IF_3(split(x[9], ys[9]), x[9], ys[9]) & (U^Increasing(IF_3(split(x[9], ys[9]), x[9], ys[9])), >=)) 6.65/2.83 6.65/2.83 6.65/2.83 6.65/2.83 We simplified constraint (2) using rule (V) (with possible (I) afterwards) using induction on split(x[9], ys[9])=pair(yl[12], yh[12]) which results in the following new constraints: 6.65/2.83 6.65/2.83 (3) (pair(e, e)=pair(yl[12], yh[12]) ==> QSORT(ins(x33, e))_>=_NonInfC & QSORT(ins(x33, e))_>=_IF_3(split(x33, e), x33, e) & (U^Increasing(IF_3(split(x[9], ys[9]), x[9], ys[9])), >=)) 6.65/2.83 6.65/2.83 (4) (Cond_split(>(x36, x35), x36, ins(x35, x34))=pair(yl[12], yh[12]) ==> QSORT(ins(x36, ins(x35, x34)))_>=_NonInfC & QSORT(ins(x36, ins(x35, x34)))_>=_IF_3(split(x36, ins(x35, x34)), x36, ins(x35, x34)) & (U^Increasing(IF_3(split(x[9], ys[9]), x[9], ys[9])), >=)) 6.65/2.83 6.65/2.83 (5) (Cond_split1(>=(x38, x39), x39, ins(x38, x37))=pair(yl[12], yh[12]) ==> QSORT(ins(x39, ins(x38, x37)))_>=_NonInfC & QSORT(ins(x39, ins(x38, x37)))_>=_IF_3(split(x39, ins(x38, x37)), x39, ins(x38, x37)) & (U^Increasing(IF_3(split(x[9], ys[9]), x[9], ys[9])), >=)) 6.65/2.83 6.65/2.83 6.65/2.83 6.65/2.83 We simplified constraint (3) using rules (I), (II), (IV) which results in the following new constraint: 6.65/2.83 6.65/2.83 (6) (QSORT(ins(x33, e))_>=_NonInfC & QSORT(ins(x33, e))_>=_IF_3(split(x33, e), x33, e) & (U^Increasing(IF_3(split(x[9], ys[9]), x[9], ys[9])), >=)) 6.65/2.83 6.65/2.83 6.65/2.83 6.65/2.83 We simplified constraint (4) using rules (III), (VII) which results in the following new constraint: 6.65/2.83 6.65/2.83 (7) (Cond_split(>(x36, x35), x36, ins(x35, x34))=pair(yl[12], yh[12]) ==> QSORT(ins(x36, ins(x35, x34)))_>=_NonInfC & QSORT(ins(x36, ins(x35, x34)))_>=_IF_3(split(x36, ins(x35, x34)), x36, ins(x35, x34)) & (U^Increasing(IF_3(split(x[9], ys[9]), x[9], ys[9])), >=)) 6.65/2.83 6.65/2.83 6.65/2.83 6.65/2.83 We simplified constraint (5) using rules (III), (VII) which results in the following new constraint: 6.65/2.83 6.65/2.83 (8) (Cond_split1(>=(x38, x39), x39, ins(x38, x37))=pair(yl[12], yh[12]) ==> QSORT(ins(x39, ins(x38, x37)))_>=_NonInfC & QSORT(ins(x39, ins(x38, x37)))_>=_IF_3(split(x39, ins(x38, x37)), x39, ins(x38, x37)) & (U^Increasing(IF_3(split(x[9], ys[9]), x[9], ys[9])), >=)) 6.65/2.83 6.65/2.83 6.65/2.83 6.65/2.83 We simplified constraint (6) using rule (POLY_CONSTRAINTS) which results in the following new constraint: 6.65/2.83 6.65/2.83 (9) ((U^Increasing(IF_3(split(x[9], ys[9]), x[9], ys[9])), >=) & [bni_51] = 0 & [1 + (-1)bso_52] >= 0) 6.65/2.83 6.65/2.83 6.65/2.83 6.65/2.83 We simplified constraint (7) using rule (POLY_CONSTRAINTS) which results in the following new constraint: 6.65/2.83 6.65/2.83 (10) ((U^Increasing(IF_3(split(x[9], ys[9]), x[9], ys[9])), >=) & 0 >= 0 & [1 + (-1)bso_52] >= 0) 6.65/2.83 6.65/2.83 6.65/2.83 6.65/2.83 We simplified constraint (8) using rule (POLY_CONSTRAINTS) which results in the following new constraint: 6.65/2.83 6.65/2.83 (11) ((U^Increasing(IF_3(split(x[9], ys[9]), x[9], ys[9])), >=) & 0 >= 0 & [1 + (-1)bso_52] >= 0) 6.65/2.83 6.65/2.83 6.65/2.83 6.65/2.83 We simplified constraint (9) using rule (IDP_POLY_SIMPLIFY) which results in the following new constraint: 6.65/2.83 6.65/2.83 (12) ((U^Increasing(IF_3(split(x[9], ys[9]), x[9], ys[9])), >=) & [bni_51] = 0 & [1 + (-1)bso_52] >= 0) 6.65/2.83 6.65/2.83 6.65/2.83 6.65/2.83 We simplified constraint (11) using rule (IDP_POLY_SIMPLIFY) which results in the following new constraint: 6.65/2.83 6.65/2.83 (13) ((U^Increasing(IF_3(split(x[9], ys[9]), x[9], ys[9])), >=) & 0 >= 0 & [1 + (-1)bso_52] >= 0) 6.65/2.83 6.65/2.83 6.65/2.83 6.65/2.83 We simplified constraint (10) using rule (IDP_POLY_SIMPLIFY) which results in the following new constraint: 6.65/2.83 6.65/2.83 (14) ((U^Increasing(IF_3(split(x[9], ys[9]), x[9], ys[9])), >=) & 0 >= 0 & [1 + (-1)bso_52] >= 0) 6.65/2.83 6.65/2.83 6.65/2.83 6.65/2.83 We simplified constraint (12) using rule (POLY_REMOVE_MIN_MAX) which results in the following new constraint: 6.65/2.83 6.65/2.83 (15) ((U^Increasing(IF_3(split(x[9], ys[9]), x[9], ys[9])), >=) & [bni_51] = 0 & [1 + (-1)bso_52] >= 0) 6.65/2.83 6.65/2.83 6.65/2.83 6.65/2.83 We simplified constraint (13) using rule (POLY_REMOVE_MIN_MAX) which results in the following new constraint: 6.65/2.83 6.65/2.83 (16) ((U^Increasing(IF_3(split(x[9], ys[9]), x[9], ys[9])), >=) & 0 >= 0 & [1 + (-1)bso_52] >= 0) 6.65/2.83 6.65/2.83 6.65/2.83 6.65/2.83 We simplified constraint (14) using rule (POLY_REMOVE_MIN_MAX) which results in the following new constraint: 6.65/2.83 6.65/2.83 (17) ((U^Increasing(IF_3(split(x[9], ys[9]), x[9], ys[9])), >=) & 0 >= 0 & [1 + (-1)bso_52] >= 0) 6.65/2.83 6.65/2.83 6.65/2.83 6.65/2.83 We simplified constraint (15) using rule (IDP_UNRESTRICTED_VARS) which results in the following new constraint: 6.65/2.83 6.65/2.83 (18) ((U^Increasing(IF_3(split(x[9], ys[9]), x[9], ys[9])), >=) & [bni_51] = 0 & 0 >= 0 & [1 + (-1)bso_52] >= 0) 6.65/2.83 6.65/2.83 6.65/2.83 6.65/2.83 We simplified constraint (16) using rule (IDP_UNRESTRICTED_VARS) which results in the following new constraint: 6.65/2.83 6.65/2.83 (19) ((U^Increasing(IF_3(split(x[9], ys[9]), x[9], ys[9])), >=) & 0 >= 0 & 0 >= 0 & 0 >= 0 & 0 >= 0 & 0 >= 0 & 0 >= 0 & [1 + (-1)bso_52] >= 0) 6.65/2.83 6.65/2.83 6.65/2.83 6.65/2.83 We simplified constraint (17) using rule (IDP_UNRESTRICTED_VARS) which results in the following new constraint: 6.65/2.83 6.65/2.83 (20) ((U^Increasing(IF_3(split(x[9], ys[9]), x[9], ys[9])), >=) & 0 >= 0 & 0 >= 0 & 0 >= 0 & 0 >= 0 & 0 >= 0 & 0 >= 0 & [1 + (-1)bso_52] >= 0) 6.65/2.83 6.65/2.83 6.65/2.83 6.65/2.83 6.65/2.83 *We consider the chain IF_3(pair(yl[12], yh[12]), x[12], ys[12]) -> QSORT(yl[12]), QSORT(ins(x[9], ys[9])) -> IF_3(split(x[9], ys[9]), x[9], ys[9]), IF_3(pair(yl[13], yh[13]), x[13], ys[13]) -> QSORT(yh[13]) which results in the following constraint: 6.65/2.83 6.65/2.83 (1) (yl[12]=ins(x[9], ys[9]) & split(x[9], ys[9])=pair(yl[13], yh[13]) & x[9]=x[13] & ys[9]=ys[13] ==> QSORT(ins(x[9], ys[9]))_>=_NonInfC & QSORT(ins(x[9], ys[9]))_>=_IF_3(split(x[9], ys[9]), x[9], ys[9]) & (U^Increasing(IF_3(split(x[9], ys[9]), x[9], ys[9])), >=)) 6.65/2.83 6.65/2.83 6.65/2.83 6.65/2.83 We simplified constraint (1) using rules (III), (IV) which results in the following new constraint: 6.65/2.83 6.65/2.83 (2) (split(x[9], ys[9])=pair(yl[13], yh[13]) ==> QSORT(ins(x[9], ys[9]))_>=_NonInfC & QSORT(ins(x[9], ys[9]))_>=_IF_3(split(x[9], ys[9]), x[9], ys[9]) & (U^Increasing(IF_3(split(x[9], ys[9]), x[9], ys[9])), >=)) 6.65/2.83 6.65/2.83 6.65/2.83 6.65/2.83 We simplified constraint (2) using rule (V) (with possible (I) afterwards) using induction on split(x[9], ys[9])=pair(yl[13], yh[13]) which results in the following new constraints: 6.65/2.83 6.65/2.83 (3) (pair(e, e)=pair(yl[13], yh[13]) ==> QSORT(ins(x44, e))_>=_NonInfC & QSORT(ins(x44, e))_>=_IF_3(split(x44, e), x44, e) & (U^Increasing(IF_3(split(x[9], ys[9]), x[9], ys[9])), >=)) 6.65/2.83 6.65/2.83 (4) (Cond_split(>(x47, x46), x47, ins(x46, x45))=pair(yl[13], yh[13]) ==> QSORT(ins(x47, ins(x46, x45)))_>=_NonInfC & QSORT(ins(x47, ins(x46, x45)))_>=_IF_3(split(x47, ins(x46, x45)), x47, ins(x46, x45)) & (U^Increasing(IF_3(split(x[9], ys[9]), x[9], ys[9])), >=)) 6.65/2.83 6.65/2.83 (5) (Cond_split1(>=(x49, x50), x50, ins(x49, x48))=pair(yl[13], yh[13]) ==> QSORT(ins(x50, ins(x49, x48)))_>=_NonInfC & QSORT(ins(x50, ins(x49, x48)))_>=_IF_3(split(x50, ins(x49, x48)), x50, ins(x49, x48)) & (U^Increasing(IF_3(split(x[9], ys[9]), x[9], ys[9])), >=)) 6.65/2.83 6.65/2.83 6.65/2.83 6.65/2.83 We simplified constraint (3) using rules (I), (II), (IV) which results in the following new constraint: 6.65/2.83 6.65/2.83 (6) (QSORT(ins(x44, e))_>=_NonInfC & QSORT(ins(x44, e))_>=_IF_3(split(x44, e), x44, e) & (U^Increasing(IF_3(split(x[9], ys[9]), x[9], ys[9])), >=)) 6.65/2.83 6.65/2.83 6.65/2.83 6.65/2.83 We simplified constraint (4) using rules (III), (VII) which results in the following new constraint: 6.65/2.83 6.65/2.83 (7) (Cond_split(>(x47, x46), x47, ins(x46, x45))=pair(yl[13], yh[13]) ==> QSORT(ins(x47, ins(x46, x45)))_>=_NonInfC & QSORT(ins(x47, ins(x46, x45)))_>=_IF_3(split(x47, ins(x46, x45)), x47, ins(x46, x45)) & (U^Increasing(IF_3(split(x[9], ys[9]), x[9], ys[9])), >=)) 6.65/2.84 6.65/2.84 6.65/2.84 6.65/2.84 We simplified constraint (5) using rules (III), (VII) which results in the following new constraint: 6.65/2.84 6.65/2.84 (8) (Cond_split1(>=(x49, x50), x50, ins(x49, x48))=pair(yl[13], yh[13]) ==> QSORT(ins(x50, ins(x49, x48)))_>=_NonInfC & QSORT(ins(x50, ins(x49, x48)))_>=_IF_3(split(x50, ins(x49, x48)), x50, ins(x49, x48)) & (U^Increasing(IF_3(split(x[9], ys[9]), x[9], ys[9])), >=)) 6.65/2.84 6.65/2.84 6.65/2.84 6.65/2.84 We simplified constraint (6) using rule (POLY_CONSTRAINTS) which results in the following new constraint: 6.65/2.84 6.65/2.84 (9) ((U^Increasing(IF_3(split(x[9], ys[9]), x[9], ys[9])), >=) & [bni_51] = 0 & [1 + (-1)bso_52] >= 0) 6.65/2.84 6.65/2.84 6.65/2.84 6.65/2.84 We simplified constraint (7) using rule (POLY_CONSTRAINTS) which results in the following new constraint: 6.65/2.84 6.65/2.84 (10) ((U^Increasing(IF_3(split(x[9], ys[9]), x[9], ys[9])), >=) & 0 >= 0 & [1 + (-1)bso_52] >= 0) 6.65/2.84 6.65/2.84 6.65/2.84 6.65/2.84 We simplified constraint (8) using rule (POLY_CONSTRAINTS) which results in the following new constraint: 6.65/2.84 6.65/2.84 (11) ((U^Increasing(IF_3(split(x[9], ys[9]), x[9], ys[9])), >=) & 0 >= 0 & [1 + (-1)bso_52] >= 0) 6.65/2.84 6.65/2.84 6.65/2.84 6.65/2.84 We simplified constraint (9) using rule (IDP_POLY_SIMPLIFY) which results in the following new constraint: 6.65/2.84 6.65/2.84 (12) ((U^Increasing(IF_3(split(x[9], ys[9]), x[9], ys[9])), >=) & [bni_51] = 0 & [1 + (-1)bso_52] >= 0) 6.65/2.84 6.65/2.84 6.65/2.84 6.65/2.84 We simplified constraint (11) using rule (IDP_POLY_SIMPLIFY) which results in the following new constraint: 6.65/2.84 6.65/2.84 (13) ((U^Increasing(IF_3(split(x[9], ys[9]), x[9], ys[9])), >=) & 0 >= 0 & [1 + (-1)bso_52] >= 0) 6.65/2.84 6.65/2.84 6.65/2.84 6.65/2.84 We simplified constraint (10) using rule (IDP_POLY_SIMPLIFY) which results in the following new constraint: 6.65/2.84 6.65/2.84 (14) ((U^Increasing(IF_3(split(x[9], ys[9]), x[9], ys[9])), >=) & 0 >= 0 & [1 + (-1)bso_52] >= 0) 6.65/2.84 6.65/2.84 6.65/2.84 6.65/2.84 We simplified constraint (12) using rule (POLY_REMOVE_MIN_MAX) which results in the following new constraint: 6.65/2.84 6.65/2.84 (15) ((U^Increasing(IF_3(split(x[9], ys[9]), x[9], ys[9])), >=) & [bni_51] = 0 & [1 + (-1)bso_52] >= 0) 6.65/2.84 6.65/2.84 6.65/2.84 6.65/2.84 We simplified constraint (13) using rule (POLY_REMOVE_MIN_MAX) which results in the following new constraint: 6.65/2.84 6.65/2.84 (16) ((U^Increasing(IF_3(split(x[9], ys[9]), x[9], ys[9])), >=) & 0 >= 0 & [1 + (-1)bso_52] >= 0) 6.65/2.84 6.65/2.84 6.65/2.84 6.65/2.84 We simplified constraint (14) using rule (POLY_REMOVE_MIN_MAX) which results in the following new constraint: 6.65/2.84 6.65/2.84 (17) ((U^Increasing(IF_3(split(x[9], ys[9]), x[9], ys[9])), >=) & 0 >= 0 & [1 + (-1)bso_52] >= 0) 6.65/2.84 6.65/2.84 6.65/2.84 6.65/2.84 We simplified constraint (15) using rule (IDP_UNRESTRICTED_VARS) which results in the following new constraint: 6.65/2.84 6.65/2.84 (18) ((U^Increasing(IF_3(split(x[9], ys[9]), x[9], ys[9])), >=) & [bni_51] = 0 & 0 >= 0 & [1 + (-1)bso_52] >= 0) 6.65/2.84 6.65/2.84 6.65/2.84 6.65/2.84 We simplified constraint (16) using rule (IDP_UNRESTRICTED_VARS) which results in the following new constraint: 6.65/2.84 6.65/2.84 (19) ((U^Increasing(IF_3(split(x[9], ys[9]), x[9], ys[9])), >=) & 0 >= 0 & 0 >= 0 & 0 >= 0 & 0 >= 0 & 0 >= 0 & 0 >= 0 & [1 + (-1)bso_52] >= 0) 6.65/2.84 6.65/2.84 6.65/2.84 6.65/2.84 We simplified constraint (17) using rule (IDP_UNRESTRICTED_VARS) which results in the following new constraint: 6.65/2.84 6.65/2.84 (20) ((U^Increasing(IF_3(split(x[9], ys[9]), x[9], ys[9])), >=) & 0 >= 0 & 0 >= 0 & 0 >= 0 & 0 >= 0 & 0 >= 0 & 0 >= 0 & [1 + (-1)bso_52] >= 0) 6.65/2.84 6.65/2.84 6.65/2.84 6.65/2.84 6.65/2.84 *We consider the chain IF_3(pair(yl[13], yh[13]), x[13], ys[13]) -> QSORT(yh[13]), QSORT(ins(x[9], ys[9])) -> IF_3(split(x[9], ys[9]), x[9], ys[9]), IF_3(pair(yl[13], yh[13]), x[13], ys[13]) -> QSORT(yh[13]) which results in the following constraint: 6.65/2.84 6.65/2.84 (1) (yh[13]=ins(x[9], ys[9]) & split(x[9], ys[9])=pair(yl[13]1, yh[13]1) & x[9]=x[13]1 & ys[9]=ys[13]1 ==> QSORT(ins(x[9], ys[9]))_>=_NonInfC & QSORT(ins(x[9], ys[9]))_>=_IF_3(split(x[9], ys[9]), x[9], ys[9]) & (U^Increasing(IF_3(split(x[9], ys[9]), x[9], ys[9])), >=)) 6.65/2.84 6.65/2.84 6.65/2.84 6.65/2.84 We simplified constraint (1) using rules (III), (IV) which results in the following new constraint: 6.65/2.84 6.65/2.84 (2) (split(x[9], ys[9])=pair(yl[13]1, yh[13]1) ==> QSORT(ins(x[9], ys[9]))_>=_NonInfC & QSORT(ins(x[9], ys[9]))_>=_IF_3(split(x[9], ys[9]), x[9], ys[9]) & (U^Increasing(IF_3(split(x[9], ys[9]), x[9], ys[9])), >=)) 6.65/2.84 6.65/2.84 6.65/2.84 6.65/2.84 We simplified constraint (2) using rule (V) (with possible (I) afterwards) using induction on split(x[9], ys[9])=pair(yl[13]1, yh[13]1) which results in the following new constraints: 6.65/2.84 6.65/2.84 (3) (pair(e, e)=pair(yl[13]1, yh[13]1) ==> QSORT(ins(x55, e))_>=_NonInfC & QSORT(ins(x55, e))_>=_IF_3(split(x55, e), x55, e) & (U^Increasing(IF_3(split(x[9], ys[9]), x[9], ys[9])), >=)) 6.65/2.84 6.65/2.84 (4) (Cond_split(>(x58, x57), x58, ins(x57, x56))=pair(yl[13]1, yh[13]1) ==> QSORT(ins(x58, ins(x57, x56)))_>=_NonInfC & QSORT(ins(x58, ins(x57, x56)))_>=_IF_3(split(x58, ins(x57, x56)), x58, ins(x57, x56)) & (U^Increasing(IF_3(split(x[9], ys[9]), x[9], ys[9])), >=)) 6.65/2.84 6.65/2.84 (5) (Cond_split1(>=(x60, x61), x61, ins(x60, x59))=pair(yl[13]1, yh[13]1) ==> QSORT(ins(x61, ins(x60, x59)))_>=_NonInfC & QSORT(ins(x61, ins(x60, x59)))_>=_IF_3(split(x61, ins(x60, x59)), x61, ins(x60, x59)) & (U^Increasing(IF_3(split(x[9], ys[9]), x[9], ys[9])), >=)) 6.65/2.84 6.65/2.84 6.65/2.84 6.65/2.84 We simplified constraint (3) using rules (I), (II), (IV) which results in the following new constraint: 6.65/2.84 6.65/2.84 (6) (QSORT(ins(x55, e))_>=_NonInfC & QSORT(ins(x55, e))_>=_IF_3(split(x55, e), x55, e) & (U^Increasing(IF_3(split(x[9], ys[9]), x[9], ys[9])), >=)) 6.65/2.84 6.65/2.84 6.65/2.84 6.65/2.84 We simplified constraint (4) using rules (III), (VII) which results in the following new constraint: 6.65/2.84 6.65/2.84 (7) (Cond_split(>(x58, x57), x58, ins(x57, x56))=pair(yl[13]1, yh[13]1) ==> QSORT(ins(x58, ins(x57, x56)))_>=_NonInfC & QSORT(ins(x58, ins(x57, x56)))_>=_IF_3(split(x58, ins(x57, x56)), x58, ins(x57, x56)) & (U^Increasing(IF_3(split(x[9], ys[9]), x[9], ys[9])), >=)) 6.65/2.84 6.65/2.84 6.65/2.84 6.65/2.84 We simplified constraint (5) using rules (III), (VII) which results in the following new constraint: 6.65/2.84 6.65/2.84 (8) (Cond_split1(>=(x60, x61), x61, ins(x60, x59))=pair(yl[13]1, yh[13]1) ==> QSORT(ins(x61, ins(x60, x59)))_>=_NonInfC & QSORT(ins(x61, ins(x60, x59)))_>=_IF_3(split(x61, ins(x60, x59)), x61, ins(x60, x59)) & (U^Increasing(IF_3(split(x[9], ys[9]), x[9], ys[9])), >=)) 6.65/2.84 6.65/2.84 6.65/2.84 6.65/2.84 We simplified constraint (6) using rule (POLY_CONSTRAINTS) which results in the following new constraint: 6.65/2.84 6.65/2.84 (9) ((U^Increasing(IF_3(split(x[9], ys[9]), x[9], ys[9])), >=) & [bni_51] = 0 & [1 + (-1)bso_52] >= 0) 6.65/2.84 6.65/2.84 6.65/2.84 6.65/2.84 We simplified constraint (7) using rule (POLY_CONSTRAINTS) which results in the following new constraint: 6.65/2.84 6.65/2.84 (10) ((U^Increasing(IF_3(split(x[9], ys[9]), x[9], ys[9])), >=) & 0 >= 0 & [1 + (-1)bso_52] >= 0) 6.65/2.84 6.65/2.84 6.65/2.84 6.65/2.84 We simplified constraint (8) using rule (POLY_CONSTRAINTS) which results in the following new constraint: 6.65/2.84 6.65/2.84 (11) ((U^Increasing(IF_3(split(x[9], ys[9]), x[9], ys[9])), >=) & 0 >= 0 & [1 + (-1)bso_52] >= 0) 6.65/2.84 6.65/2.84 6.65/2.84 6.65/2.84 We simplified constraint (9) using rule (IDP_POLY_SIMPLIFY) which results in the following new constraint: 6.65/2.84 6.65/2.84 (12) ((U^Increasing(IF_3(split(x[9], ys[9]), x[9], ys[9])), >=) & [bni_51] = 0 & [1 + (-1)bso_52] >= 0) 6.65/2.84 6.65/2.84 6.65/2.84 6.65/2.84 We simplified constraint (11) using rule (IDP_POLY_SIMPLIFY) which results in the following new constraint: 6.65/2.84 6.65/2.84 (13) ((U^Increasing(IF_3(split(x[9], ys[9]), x[9], ys[9])), >=) & 0 >= 0 & [1 + (-1)bso_52] >= 0) 6.65/2.84 6.65/2.84 6.65/2.84 6.65/2.84 We simplified constraint (10) using rule (IDP_POLY_SIMPLIFY) which results in the following new constraint: 6.65/2.84 6.65/2.84 (14) ((U^Increasing(IF_3(split(x[9], ys[9]), x[9], ys[9])), >=) & 0 >= 0 & [1 + (-1)bso_52] >= 0) 6.65/2.84 6.65/2.84 6.65/2.84 6.65/2.84 We simplified constraint (12) using rule (POLY_REMOVE_MIN_MAX) which results in the following new constraint: 6.65/2.84 6.65/2.84 (15) ((U^Increasing(IF_3(split(x[9], ys[9]), x[9], ys[9])), >=) & [bni_51] = 0 & [1 + (-1)bso_52] >= 0) 6.65/2.84 6.65/2.84 6.65/2.84 6.65/2.84 We simplified constraint (13) using rule (POLY_REMOVE_MIN_MAX) which results in the following new constraint: 6.65/2.84 6.65/2.84 (16) ((U^Increasing(IF_3(split(x[9], ys[9]), x[9], ys[9])), >=) & 0 >= 0 & [1 + (-1)bso_52] >= 0) 6.65/2.84 6.65/2.84 6.65/2.84 6.65/2.84 We simplified constraint (14) using rule (POLY_REMOVE_MIN_MAX) which results in the following new constraint: 6.65/2.84 6.65/2.84 (17) ((U^Increasing(IF_3(split(x[9], ys[9]), x[9], ys[9])), >=) & 0 >= 0 & [1 + (-1)bso_52] >= 0) 6.65/2.84 6.65/2.84 6.65/2.84 6.65/2.84 We simplified constraint (15) using rule (IDP_UNRESTRICTED_VARS) which results in the following new constraint: 6.65/2.84 6.65/2.84 (18) ((U^Increasing(IF_3(split(x[9], ys[9]), x[9], ys[9])), >=) & [bni_51] = 0 & 0 >= 0 & [1 + (-1)bso_52] >= 0) 6.65/2.84 6.65/2.84 6.65/2.84 6.65/2.84 We simplified constraint (16) using rule (IDP_UNRESTRICTED_VARS) which results in the following new constraint: 6.65/2.84 6.65/2.84 (19) ((U^Increasing(IF_3(split(x[9], ys[9]), x[9], ys[9])), >=) & 0 >= 0 & 0 >= 0 & 0 >= 0 & 0 >= 0 & 0 >= 0 & 0 >= 0 & [1 + (-1)bso_52] >= 0) 6.65/2.84 6.65/2.84 6.65/2.84 6.65/2.84 We simplified constraint (17) using rule (IDP_UNRESTRICTED_VARS) which results in the following new constraint: 6.65/2.84 6.65/2.84 (20) ((U^Increasing(IF_3(split(x[9], ys[9]), x[9], ys[9])), >=) & 0 >= 0 & 0 >= 0 & 0 >= 0 & 0 >= 0 & 0 >= 0 & 0 >= 0 & [1 + (-1)bso_52] >= 0) 6.65/2.84 6.65/2.84 6.65/2.84 6.65/2.84 6.65/2.84 6.65/2.84 6.65/2.84 6.65/2.84 6.65/2.84 To summarize, we get the following constraints P__>=_ for the following pairs. 6.65/2.84 6.65/2.84 *IF_3(pair(yl[13], yh[13]), x[13], ys[13]) -> QSORT(yh[13]) 6.65/2.84 6.65/2.84 *((U^Increasing(QSORT(yh[13])), >=) & 0 >= 0 & 0 >= 0 & 0 >= 0 & [(3)bni_47] >= 0 & 0 >= 0 & [bni_47] >= 0 & [bni_47 + (-1)Bound*bni_47] >= 0 & 0 >= 0 & 0 >= 0 & 0 >= 0 & [1] >= 0 & [1 + (-1)bso_48] >= 0) 6.65/2.84 6.65/2.84 6.65/2.84 *((U^Increasing(QSORT(yh[13])), >=) & 0 >= 0 & 0 >= 0 & 0 >= 0 & [(3)bni_47] >= 0 & 0 >= 0 & [bni_47] >= 0 & [bni_47 + (-1)Bound*bni_47] >= 0 & 0 >= 0 & 0 >= 0 & 0 >= 0 & [1] >= 0 & [1 + (-1)bso_48] >= 0) 6.65/2.84 6.65/2.84 6.65/2.84 6.65/2.84 6.65/2.84 *IF_3(pair(yl[12], yh[12]), x[12], ys[12]) -> QSORT(yl[12]) 6.65/2.84 6.65/2.84 *((U^Increasing(QSORT(yl[12])), >=) & 0 >= 0 & 0 >= 0 & 0 >= 0 & [bni_49] >= 0 & [(3)bni_49] >= 0 & 0 >= 0 & [bni_49 + (-1)Bound*bni_49] >= 0 & 0 >= 0 & 0 >= 0 & 0 >= 0 & [1] >= 0 & [1 + (-1)bso_50] >= 0) 6.65/2.84 6.65/2.84 6.65/2.84 *((U^Increasing(QSORT(yl[12])), >=) & 0 >= 0 & 0 >= 0 & 0 >= 0 & [bni_49] >= 0 & [(3)bni_49] >= 0 & 0 >= 0 & [bni_49 + (-1)Bound*bni_49] >= 0 & 0 >= 0 & 0 >= 0 & 0 >= 0 & [1] >= 0 & [1 + (-1)bso_50] >= 0) 6.65/2.84 6.65/2.84 6.65/2.84 6.65/2.84 6.65/2.84 *QSORT(ins(x[9], ys[9])) -> IF_3(split(x[9], ys[9]), x[9], ys[9]) 6.65/2.84 6.65/2.84 *((U^Increasing(IF_3(split(x[9], ys[9]), x[9], ys[9])), >=) & [bni_51] = 0 & 0 >= 0 & [1 + (-1)bso_52] >= 0) 6.65/2.84 6.65/2.84 6.65/2.84 *((U^Increasing(IF_3(split(x[9], ys[9]), x[9], ys[9])), >=) & 0 >= 0 & 0 >= 0 & 0 >= 0 & 0 >= 0 & 0 >= 0 & 0 >= 0 & [1 + (-1)bso_52] >= 0) 6.65/2.84 6.65/2.84 6.65/2.84 *((U^Increasing(IF_3(split(x[9], ys[9]), x[9], ys[9])), >=) & 0 >= 0 & 0 >= 0 & 0 >= 0 & 0 >= 0 & 0 >= 0 & 0 >= 0 & [1 + (-1)bso_52] >= 0) 6.65/2.84 6.65/2.84 6.65/2.84 *((U^Increasing(IF_3(split(x[9], ys[9]), x[9], ys[9])), >=) & [bni_51] = 0 & 0 >= 0 & [1 + (-1)bso_52] >= 0) 6.65/2.84 6.65/2.84 6.65/2.84 *((U^Increasing(IF_3(split(x[9], ys[9]), x[9], ys[9])), >=) & 0 >= 0 & 0 >= 0 & 0 >= 0 & 0 >= 0 & 0 >= 0 & 0 >= 0 & [1 + (-1)bso_52] >= 0) 6.65/2.84 6.65/2.84 6.65/2.84 *((U^Increasing(IF_3(split(x[9], ys[9]), x[9], ys[9])), >=) & 0 >= 0 & 0 >= 0 & 0 >= 0 & 0 >= 0 & 0 >= 0 & 0 >= 0 & [1 + (-1)bso_52] >= 0) 6.65/2.84 6.65/2.84 6.65/2.84 *((U^Increasing(IF_3(split(x[9], ys[9]), x[9], ys[9])), >=) & [bni_51] = 0 & 0 >= 0 & [1 + (-1)bso_52] >= 0) 6.65/2.84 6.65/2.84 6.65/2.84 *((U^Increasing(IF_3(split(x[9], ys[9]), x[9], ys[9])), >=) & 0 >= 0 & 0 >= 0 & 0 >= 0 & 0 >= 0 & 0 >= 0 & 0 >= 0 & [1 + (-1)bso_52] >= 0) 6.65/2.84 6.65/2.84 6.65/2.84 *((U^Increasing(IF_3(split(x[9], ys[9]), x[9], ys[9])), >=) & 0 >= 0 & 0 >= 0 & 0 >= 0 & 0 >= 0 & 0 >= 0 & 0 >= 0 & [1 + (-1)bso_52] >= 0) 6.65/2.84 6.65/2.84 6.65/2.84 *((U^Increasing(IF_3(split(x[9], ys[9]), x[9], ys[9])), >=) & [bni_51] = 0 & 0 >= 0 & [1 + (-1)bso_52] >= 0) 6.65/2.84 6.65/2.84 6.65/2.84 *((U^Increasing(IF_3(split(x[9], ys[9]), x[9], ys[9])), >=) & 0 >= 0 & 0 >= 0 & 0 >= 0 & 0 >= 0 & 0 >= 0 & 0 >= 0 & [1 + (-1)bso_52] >= 0) 6.65/2.84 6.65/2.84 6.65/2.84 *((U^Increasing(IF_3(split(x[9], ys[9]), x[9], ys[9])), >=) & 0 >= 0 & 0 >= 0 & 0 >= 0 & 0 >= 0 & 0 >= 0 & 0 >= 0 & [1 + (-1)bso_52] >= 0) 6.65/2.84 6.65/2.84 6.65/2.84 6.65/2.84 6.65/2.84 6.65/2.84 6.65/2.84 6.65/2.84 6.65/2.84 The constraints for P_> respective P_bound are constructed from P__>=_ where we just replace every occurence of "t _>=_ s" in P__>=_ by "t > s" respective "t _>=_ c". Here c stands for the fresh constant used for P_bound. 6.65/2.84 6.65/2.84 Using the following integer polynomial ordering the resulting constraints can be solved 6.65/2.84 6.65/2.84 Polynomial interpretation over integers with natural coefficients for non-tuple symbols [NONINF][POLO]: 6.65/2.84 6.65/2.84 POL(TRUE) = 0 6.65/2.84 POL(FALSE) = 0 6.65/2.84 POL(split(x_1, x_2)) = [3]x_2 6.65/2.84 POL(e) = [2] 6.65/2.84 POL(pair(x_1, x_2)) = [2] + x_2 + x_1 6.65/2.84 POL(ins(x_1, x_2)) = [3]x_2 6.65/2.84 POL(Cond_split(x_1, x_2, x_3)) = [3]x_3 6.65/2.84 POL(>(x_1, x_2)) = 0 6.65/2.84 POL(Cond_split1(x_1, x_2, x_3)) = [3]x_3 6.65/2.84 POL(>=(x_1, x_2)) = 0 6.65/2.84 POL(if_1(x_1, x_2, x_3, x_4)) = [3]x_1 6.65/2.84 POL(if_2(x_1, x_2, x_3, x_4)) = [3]x_1 6.65/2.84 POL(Cond_if_1(x_1, x_2, x_3, x_4, x_5)) = [3]x_2 6.65/2.84 POL(Cond_if_2(x_1, x_2, x_3, x_4, x_5)) = [3]x_2 6.65/2.84 POL(IF_3(x_1, x_2, x_3)) = [-1] + x_1 6.65/2.84 POL(QSORT(x_1)) = x_1 6.65/2.84 6.65/2.84 6.65/2.84 The following pairs are in P_>: 6.65/2.84 6.65/2.84 6.65/2.84 IF_3(pair(yl[13], yh[13]), x[13], ys[13]) -> QSORT(yh[13]) 6.65/2.84 IF_3(pair(yl[12], yh[12]), x[12], ys[12]) -> QSORT(yl[12]) 6.65/2.84 QSORT(ins(x[9], ys[9])) -> IF_3(split(x[9], ys[9]), x[9], ys[9]) 6.65/2.84 6.65/2.84 6.65/2.84 The following pairs are in P_bound: 6.65/2.84 6.65/2.84 6.65/2.84 IF_3(pair(yl[13], yh[13]), x[13], ys[13]) -> QSORT(yh[13]) 6.65/2.84 IF_3(pair(yl[12], yh[12]), x[12], ys[12]) -> QSORT(yl[12]) 6.65/2.84 6.65/2.84 6.65/2.84 The following pairs are in P_>=: 6.65/2.84 6.65/2.84 none 6.65/2.84 6.65/2.84 6.65/2.84 At least the following rules have been oriented under context sensitive arithmetic replacement: 6.65/2.84 6.65/2.84 split(x, e)^1 <-> pair(e, e)^1 6.65/2.84 split(x, ins(y, zs))^1 -> Cond_split(>(x, y), x, ins(y, zs))^1 6.65/2.84 split(x, ins(y, zs))^1 <-> Cond_split1(>=(y, x), x, ins(y, zs))^1 6.65/2.84 Cond_split(TRUE, x, ins(y, zs))^1 <-> if_1(split(x, zs), x, y, zs)^1 6.65/2.84 Cond_split1(TRUE, x, ins(y, zs))^1 -> if_2(split(x, zs), x, y, zs)^1 6.65/2.84 if_1(pair(zl, zh), x, y, zs)^1 <-> Cond_if_1(>(x, y), pair(zl, zh), x, y, zs)^1 6.65/2.84 if_2(pair(zl, zh), x, y, zs)^1 -> Cond_if_2(>=(y, x), pair(zl, zh), x, y, zs)^1 6.65/2.84 Cond_if_1(TRUE, pair(zl, zh), x, y, zs)^1 -> pair(ins(y, zl), zh)^1 6.65/2.84 Cond_if_2(TRUE, pair(zl, zh), x, y, zs)^1 -> pair(zl, ins(y, zh))^1 6.65/2.84 6.65/2.84 ---------------------------------------- 6.65/2.84 6.65/2.84 (27) 6.65/2.84 Obligation: 6.65/2.84 IDP problem: 6.65/2.84 The following function symbols are pre-defined: 6.65/2.84 <<< 6.65/2.84 & ~ Bwand: (Integer, Integer) -> Integer 6.65/2.84 >= ~ Ge: (Integer, Integer) -> Boolean 6.65/2.84 | ~ Bwor: (Integer, Integer) -> Integer 6.65/2.84 / ~ Div: (Integer, Integer) -> Integer 6.65/2.84 != ~ Neq: (Integer, Integer) -> Boolean 6.65/2.84 && ~ Land: (Boolean, Boolean) -> Boolean 6.65/2.84 ! ~ Lnot: (Boolean) -> Boolean 6.65/2.84 = ~ Eq: (Integer, Integer) -> Boolean 6.65/2.84 <= ~ Le: (Integer, Integer) -> Boolean 6.65/2.84 ^ ~ Bwxor: (Integer, Integer) -> Integer 6.65/2.84 % ~ Mod: (Integer, Integer) -> Integer 6.65/2.84 > ~ Gt: (Integer, Integer) -> Boolean 6.65/2.84 + ~ Add: (Integer, Integer) -> Integer 6.65/2.84 -1 ~ UnaryMinus: (Integer) -> Integer 6.65/2.84 < ~ Lt: (Integer, Integer) -> Boolean 6.65/2.84 || ~ Lor: (Boolean, Boolean) -> Boolean 6.65/2.84 - ~ Sub: (Integer, Integer) -> Integer 6.65/2.84 ~ ~ Bwnot: (Integer) -> Integer 6.65/2.84 * ~ Mul: (Integer, Integer) -> Integer 6.65/2.84 >>> 6.65/2.84 6.65/2.84 6.65/2.84 The following domains are used: 6.65/2.84 Integer 6.65/2.84 6.65/2.84 The ITRS R consists of the following rules: 6.65/2.84 split(x, e) -> pair(e, e) 6.65/2.84 split(x, ins(y, zs)) -> Cond_split(x > y, x, ins(y, zs)) 6.65/2.84 split(x, ins(y, zs)) -> Cond_split1(y >= x, x, ins(y, zs)) 6.65/2.84 Cond_split(TRUE, x, ins(y, zs)) -> if_1(split(x, zs), x, y, zs) 6.65/2.84 Cond_split1(TRUE, x, ins(y, zs)) -> if_2(split(x, zs), x, y, zs) 6.65/2.84 if_1(pair(zl, zh), x, y, zs) -> Cond_if_1(x > y, pair(zl, zh), x, y, zs) 6.65/2.84 if_2(pair(zl, zh), x, y, zs) -> Cond_if_2(y >= x, pair(zl, zh), x, y, zs) 6.65/2.84 Cond_if_1(TRUE, pair(zl, zh), x, y, zs) -> pair(ins(y, zl), zh) 6.65/2.84 Cond_if_2(TRUE, pair(zl, zh), x, y, zs) -> pair(zl, ins(y, zh)) 6.65/2.84 6.65/2.84 The integer pair graph contains the following rules and edges: 6.65/2.84 (9): QSORT(ins(x[9], ys[9])) -> IF_3(split(x[9], ys[9]), x[9], ys[9]) 6.65/2.84 6.65/2.84 6.65/2.84 The set Q consists of the following terms: 6.65/2.84 app(nil, x0) 6.65/2.84 app(cons(x0, x1), x2) 6.65/2.84 split(x0, e) 6.65/2.84 split(x0, ins(x1, x2)) 6.65/2.84 Cond_split(TRUE, x0, ins(x1, x2)) 6.65/2.84 if_1(pair(x0, x1), x2, x3, x4) 6.65/2.84 Cond_if_1(TRUE, pair(x0, x1), x2, x3, x4) 6.65/2.84 Cond_split1(TRUE, x0, ins(x1, x2)) 6.65/2.84 if_2(pair(x0, x1), x2, x3, x4) 6.65/2.84 Cond_if_2(TRUE, pair(x0, x1), x2, x3, x4) 6.65/2.84 qsort(e) 6.65/2.84 qsort(ins(x0, x1)) 6.65/2.84 if_3(pair(x0, x1), x2, x3) 6.65/2.84 6.65/2.84 ---------------------------------------- 6.65/2.84 6.65/2.84 (28) IDependencyGraphProof (EQUIVALENT) 6.65/2.84 The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 0 SCCs with 1 less node. 6.65/2.84 ---------------------------------------- 6.65/2.84 6.65/2.84 (29) 6.65/2.84 TRUE 6.65/2.88 EOF