/export/starexec/sandbox2/solver/bin/starexec_run_standard /export/starexec/sandbox2/benchmark/theBenchmark.itrs /export/starexec/sandbox2/output/output_files -------------------------------------------------------------------------------- YES proof of /export/starexec/sandbox2/benchmark/theBenchmark.itrs # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty Termination of the given ITRS could be proven: (0) ITRS (1) ITRStoIDPProof [EQUIVALENT, 0 ms] (2) IDP (3) ItpfGraphProof [EQUIVALENT, 7 ms] (4) IDP (5) IDependencyGraphProof [EQUIVALENT, 2 ms] (6) AND (7) IDP (8) UsableRulesProof [EQUIVALENT, 0 ms] (9) IDP (10) IDPtoQDPProof [SOUND, 54 ms] (11) QDP (12) QReductionProof [EQUIVALENT, 0 ms] (13) QDP (14) QDPSizeChangeProof [EQUIVALENT, 0 ms] (15) YES (16) IDP (17) UsableRulesProof [EQUIVALENT, 0 ms] (18) IDP (19) IDPNonInfProof [SOUND, 104 ms] (20) IDP (21) PisEmptyProof [EQUIVALENT, 0 ms] (22) YES (23) IDP (24) UsableRulesProof [EQUIVALENT, 0 ms] (25) IDP (26) IDPNonInfProof [SOUND, 214 ms] (27) IDP (28) IDependencyGraphProof [EQUIVALENT, 0 ms] (29) TRUE ---------------------------------------- (0) Obligation: ITRS problem: The following function symbols are pre-defined: <<< & ~ Bwand: (Integer, Integer) -> Integer >= ~ Ge: (Integer, Integer) -> Boolean | ~ Bwor: (Integer, Integer) -> Integer / ~ Div: (Integer, Integer) -> Integer != ~ Neq: (Integer, Integer) -> Boolean && ~ Land: (Boolean, Boolean) -> Boolean ! ~ Lnot: (Boolean) -> Boolean = ~ Eq: (Integer, Integer) -> Boolean <= ~ Le: (Integer, Integer) -> Boolean ^ ~ Bwxor: (Integer, Integer) -> Integer % ~ Mod: (Integer, Integer) -> Integer > ~ Gt: (Integer, Integer) -> Boolean + ~ Add: (Integer, Integer) -> Integer -1 ~ UnaryMinus: (Integer) -> Integer < ~ Lt: (Integer, Integer) -> Boolean || ~ Lor: (Boolean, Boolean) -> Boolean - ~ Sub: (Integer, Integer) -> Integer ~ ~ Bwnot: (Integer) -> Integer * ~ Mul: (Integer, Integer) -> Integer >>> The TRS R consists of the following rules: app(nil, zs) -> zs app(cons(x, ys), zs) -> cons(x, app(ys, zs)) split(x, e) -> pair(e, e) split(x, ins(y, zs)) -> Cond_split(x > y, x, ins(y, zs)) Cond_split(TRUE, x, ins(y, zs)) -> if_1(split(x, zs), x, y, zs) if_1(pair(zl, zh), x, y, zs) -> Cond_if_1(x > y, pair(zl, zh), x, y, zs) Cond_if_1(TRUE, pair(zl, zh), x, y, zs) -> pair(ins(y, zl), zh) split(x, ins(y, zs)) -> Cond_split1(y >= x, x, ins(y, zs)) Cond_split1(TRUE, x, ins(y, zs)) -> if_2(split(x, zs), x, y, zs) if_2(pair(zl, zh), x, y, zs) -> Cond_if_2(y >= x, pair(zl, zh), x, y, zs) Cond_if_2(TRUE, pair(zl, zh), x, y, zs) -> pair(zl, ins(y, zh)) qsort(e) -> nil qsort(ins(x, ys)) -> if_3(split(x, ys), x, ys) if_3(pair(yl, yh), x, ys) -> app(qsort(yl), cons(x, qsort(yh))) The set Q consists of the following terms: app(nil, x0) app(cons(x0, x1), x2) split(x0, e) split(x0, ins(x1, x2)) Cond_split(TRUE, x0, ins(x1, x2)) if_1(pair(x0, x1), x2, x3, x4) Cond_if_1(TRUE, pair(x0, x1), x2, x3, x4) Cond_split1(TRUE, x0, ins(x1, x2)) if_2(pair(x0, x1), x2, x3, x4) Cond_if_2(TRUE, pair(x0, x1), x2, x3, x4) qsort(e) qsort(ins(x0, x1)) if_3(pair(x0, x1), x2, x3) ---------------------------------------- (1) ITRStoIDPProof (EQUIVALENT) Added dependency pairs ---------------------------------------- (2) Obligation: IDP problem: The following function symbols are pre-defined: <<< & ~ Bwand: (Integer, Integer) -> Integer >= ~ Ge: (Integer, Integer) -> Boolean | ~ Bwor: (Integer, Integer) -> Integer / ~ Div: (Integer, Integer) -> Integer != ~ Neq: (Integer, Integer) -> Boolean && ~ Land: (Boolean, Boolean) -> Boolean ! ~ Lnot: (Boolean) -> Boolean = ~ Eq: (Integer, Integer) -> Boolean <= ~ Le: (Integer, Integer) -> Boolean ^ ~ Bwxor: (Integer, Integer) -> Integer % ~ Mod: (Integer, Integer) -> Integer > ~ Gt: (Integer, Integer) -> Boolean + ~ Add: (Integer, Integer) -> Integer -1 ~ UnaryMinus: (Integer) -> Integer < ~ Lt: (Integer, Integer) -> Boolean || ~ Lor: (Boolean, Boolean) -> Boolean - ~ Sub: (Integer, Integer) -> Integer ~ ~ Bwnot: (Integer) -> Integer * ~ Mul: (Integer, Integer) -> Integer >>> The following domains are used: Integer The ITRS R consists of the following rules: app(nil, zs) -> zs app(cons(x, ys), zs) -> cons(x, app(ys, zs)) split(x, e) -> pair(e, e) split(x, ins(y, zs)) -> Cond_split(x > y, x, ins(y, zs)) Cond_split(TRUE, x, ins(y, zs)) -> if_1(split(x, zs), x, y, zs) if_1(pair(zl, zh), x, y, zs) -> Cond_if_1(x > y, pair(zl, zh), x, y, zs) Cond_if_1(TRUE, pair(zl, zh), x, y, zs) -> pair(ins(y, zl), zh) split(x, ins(y, zs)) -> Cond_split1(y >= x, x, ins(y, zs)) Cond_split1(TRUE, x, ins(y, zs)) -> if_2(split(x, zs), x, y, zs) if_2(pair(zl, zh), x, y, zs) -> Cond_if_2(y >= x, pair(zl, zh), x, y, zs) Cond_if_2(TRUE, pair(zl, zh), x, y, zs) -> pair(zl, ins(y, zh)) qsort(e) -> nil qsort(ins(x, ys)) -> if_3(split(x, ys), x, ys) if_3(pair(yl, yh), x, ys) -> app(qsort(yl), cons(x, qsort(yh))) The integer pair graph contains the following rules and edges: (0): APP(cons(x[0], ys[0]), zs[0]) -> APP(ys[0], zs[0]) (1): SPLIT(x[1], ins(y[1], zs[1])) -> COND_SPLIT(x[1] > y[1], x[1], ins(y[1], zs[1])) (2): COND_SPLIT(TRUE, x[2], ins(y[2], zs[2])) -> IF_1(split(x[2], zs[2]), x[2], y[2], zs[2]) (3): COND_SPLIT(TRUE, x[3], ins(y[3], zs[3])) -> SPLIT(x[3], zs[3]) (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]) (5): SPLIT(x[5], ins(y[5], zs[5])) -> COND_SPLIT1(y[5] >= x[5], x[5], ins(y[5], zs[5])) (6): COND_SPLIT1(TRUE, x[6], ins(y[6], zs[6])) -> IF_2(split(x[6], zs[6]), x[6], y[6], zs[6]) (7): COND_SPLIT1(TRUE, x[7], ins(y[7], zs[7])) -> SPLIT(x[7], zs[7]) (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]) (9): QSORT(ins(x[9], ys[9])) -> IF_3(split(x[9], ys[9]), x[9], ys[9]) (10): QSORT(ins(x[10], ys[10])) -> SPLIT(x[10], ys[10]) (11): IF_3(pair(yl[11], yh[11]), x[11], ys[11]) -> APP(qsort(yl[11]), cons(x[11], qsort(yh[11]))) (12): IF_3(pair(yl[12], yh[12]), x[12], ys[12]) -> QSORT(yl[12]) (13): IF_3(pair(yl[13], yh[13]), x[13], ys[13]) -> QSORT(yh[13]) (0) -> (0), if (ys[0] ->^* cons(x[0]', ys[0]') & zs[0] ->^* zs[0]') (1) -> (2), if (x[1] > y[1] & x[1] ->^* x[2] & ins(y[1], zs[1]) ->^* ins(y[2], zs[2])) (1) -> (3), if (x[1] > y[1] & x[1] ->^* x[3] & ins(y[1], zs[1]) ->^* ins(y[3], zs[3])) (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]) (3) -> (1), if (x[3] ->^* x[1] & zs[3] ->^* ins(y[1], zs[1])) (3) -> (5), if (x[3] ->^* x[5] & zs[3] ->^* ins(y[5], zs[5])) (5) -> (6), if (y[5] >= x[5] & x[5] ->^* x[6] & ins(y[5], zs[5]) ->^* ins(y[6], zs[6])) (5) -> (7), if (y[5] >= x[5] & x[5] ->^* x[7] & ins(y[5], zs[5]) ->^* ins(y[7], zs[7])) (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]) (7) -> (1), if (x[7] ->^* x[1] & zs[7] ->^* ins(y[1], zs[1])) (7) -> (5), if (x[7] ->^* x[5] & zs[7] ->^* ins(y[5], zs[5])) (9) -> (11), if (split(x[9], ys[9]) ->^* pair(yl[11], yh[11]) & x[9] ->^* x[11] & ys[9] ->^* ys[11]) (9) -> (12), if (split(x[9], ys[9]) ->^* pair(yl[12], yh[12]) & x[9] ->^* x[12] & ys[9] ->^* ys[12]) (9) -> (13), if (split(x[9], ys[9]) ->^* pair(yl[13], yh[13]) & x[9] ->^* x[13] & ys[9] ->^* ys[13]) (10) -> (1), if (x[10] ->^* x[1] & ys[10] ->^* ins(y[1], zs[1])) (10) -> (5), if (x[10] ->^* x[5] & ys[10] ->^* ins(y[5], zs[5])) (11) -> (0), if (qsort(yl[11]) ->^* cons(x[0], ys[0]) & cons(x[11], qsort(yh[11])) ->^* zs[0]) (12) -> (9), if (yl[12] ->^* ins(x[9], ys[9])) (12) -> (10), if (yl[12] ->^* ins(x[10], ys[10])) (13) -> (9), if (yh[13] ->^* ins(x[9], ys[9])) (13) -> (10), if (yh[13] ->^* ins(x[10], ys[10])) The set Q consists of the following terms: app(nil, x0) app(cons(x0, x1), x2) split(x0, e) split(x0, ins(x1, x2)) Cond_split(TRUE, x0, ins(x1, x2)) if_1(pair(x0, x1), x2, x3, x4) Cond_if_1(TRUE, pair(x0, x1), x2, x3, x4) Cond_split1(TRUE, x0, ins(x1, x2)) if_2(pair(x0, x1), x2, x3, x4) Cond_if_2(TRUE, pair(x0, x1), x2, x3, x4) qsort(e) qsort(ins(x0, x1)) if_3(pair(x0, x1), x2, x3) ---------------------------------------- (3) ItpfGraphProof (EQUIVALENT) Applied rule ItpfICap [ICap] ---------------------------------------- (4) Obligation: IDP problem: The following function symbols are pre-defined: <<< & ~ Bwand: (Integer, Integer) -> Integer >= ~ Ge: (Integer, Integer) -> Boolean | ~ Bwor: (Integer, Integer) -> Integer / ~ Div: (Integer, Integer) -> Integer != ~ Neq: (Integer, Integer) -> Boolean && ~ Land: (Boolean, Boolean) -> Boolean ! ~ Lnot: (Boolean) -> Boolean = ~ Eq: (Integer, Integer) -> Boolean <= ~ Le: (Integer, Integer) -> Boolean ^ ~ Bwxor: (Integer, Integer) -> Integer % ~ Mod: (Integer, Integer) -> Integer > ~ Gt: (Integer, Integer) -> Boolean + ~ Add: (Integer, Integer) -> Integer -1 ~ UnaryMinus: (Integer) -> Integer < ~ Lt: (Integer, Integer) -> Boolean || ~ Lor: (Boolean, Boolean) -> Boolean - ~ Sub: (Integer, Integer) -> Integer ~ ~ Bwnot: (Integer) -> Integer * ~ Mul: (Integer, Integer) -> Integer >>> The following domains are used: Integer The ITRS R consists of the following rules: app(nil, zs) -> zs app(cons(x, ys), zs) -> cons(x, app(ys, zs)) split(x, e) -> pair(e, e) split(x, ins(y, zs)) -> Cond_split(x > y, x, ins(y, zs)) Cond_split(TRUE, x, ins(y, zs)) -> if_1(split(x, zs), x, y, zs) if_1(pair(zl, zh), x, y, zs) -> Cond_if_1(x > y, pair(zl, zh), x, y, zs) Cond_if_1(TRUE, pair(zl, zh), x, y, zs) -> pair(ins(y, zl), zh) split(x, ins(y, zs)) -> Cond_split1(y >= x, x, ins(y, zs)) Cond_split1(TRUE, x, ins(y, zs)) -> if_2(split(x, zs), x, y, zs) if_2(pair(zl, zh), x, y, zs) -> Cond_if_2(y >= x, pair(zl, zh), x, y, zs) Cond_if_2(TRUE, pair(zl, zh), x, y, zs) -> pair(zl, ins(y, zh)) qsort(e) -> nil qsort(ins(x, ys)) -> if_3(split(x, ys), x, ys) if_3(pair(yl, yh), x, ys) -> app(qsort(yl), cons(x, qsort(yh))) The integer pair graph contains the following rules and edges: (0): APP(cons(x[0], ys[0]), zs[0]) -> APP(ys[0], zs[0]) (1): SPLIT(x[1], ins(y[1], zs[1])) -> COND_SPLIT(x[1] > y[1], x[1], ins(y[1], zs[1])) (2): COND_SPLIT(TRUE, x[2], ins(y[2], zs[2])) -> IF_1(split(x[2], zs[2]), x[2], y[2], zs[2]) (3): COND_SPLIT(TRUE, x[3], ins(y[3], zs[3])) -> SPLIT(x[3], zs[3]) (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]) (5): SPLIT(x[5], ins(y[5], zs[5])) -> COND_SPLIT1(y[5] >= x[5], x[5], ins(y[5], zs[5])) (6): COND_SPLIT1(TRUE, x[6], ins(y[6], zs[6])) -> IF_2(split(x[6], zs[6]), x[6], y[6], zs[6]) (7): COND_SPLIT1(TRUE, x[7], ins(y[7], zs[7])) -> SPLIT(x[7], zs[7]) (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]) (9): QSORT(ins(x[9], ys[9])) -> IF_3(split(x[9], ys[9]), x[9], ys[9]) (10): QSORT(ins(x[10], ys[10])) -> SPLIT(x[10], ys[10]) (11): IF_3(pair(yl[11], yh[11]), x[11], ys[11]) -> APP(qsort(yl[11]), cons(x[11], qsort(yh[11]))) (12): IF_3(pair(yl[12], yh[12]), x[12], ys[12]) -> QSORT(yl[12]) (13): IF_3(pair(yl[13], yh[13]), x[13], ys[13]) -> QSORT(yh[13]) (0) -> (0), if (ys[0] ->^* cons(x[0]', ys[0]') & zs[0] ->^* zs[0]') (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]) (3) -> (1), if (x[3] ->^* x[1] & zs[3] ->^* ins(y[1], zs[1])) (3) -> (5), if (x[3] ->^* x[5] & zs[3] ->^* ins(y[5], zs[5])) (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]) (7) -> (1), if (x[7] ->^* x[1] & zs[7] ->^* ins(y[1], zs[1])) (7) -> (5), if (x[7] ->^* x[5] & zs[7] ->^* ins(y[5], zs[5])) (9) -> (11), if (split(x[9], ys[9]) ->^* pair(yl[11], yh[11]) & x[9] ->^* x[11] & ys[9] ->^* ys[11]) (9) -> (12), if (split(x[9], ys[9]) ->^* pair(yl[12], yh[12]) & x[9] ->^* x[12] & ys[9] ->^* ys[12]) (9) -> (13), if (split(x[9], ys[9]) ->^* pair(yl[13], yh[13]) & x[9] ->^* x[13] & ys[9] ->^* ys[13]) (10) -> (1), if (x[10] ->^* x[1] & ys[10] ->^* ins(y[1], zs[1])) (10) -> (5), if (x[10] ->^* x[5] & ys[10] ->^* ins(y[5], zs[5])) (11) -> (0), if (qsort(yl[11]) ->^* cons(x[0], ys[0]) & cons(x[11], qsort(yh[11])) ->^* zs[0]) (12) -> (9), if (yl[12] ->^* ins(x[9], ys[9])) (12) -> (10), if (yl[12] ->^* ins(x[10], ys[10])) (13) -> (9), if (yh[13] ->^* ins(x[9], ys[9])) (13) -> (10), if (yh[13] ->^* ins(x[10], ys[10])) (1) -> (2), if (x[1] > y[1] & x[1] ->^* x[2] & (y[1] ->^* y[2] & zs[1] ->^* zs[2])) (1) -> (3), if (x[1] > y[1] & x[1] ->^* x[3] & (y[1] ->^* y[3] & zs[1] ->^* zs[3])) (5) -> (6), if (y[5] >= x[5] & x[5] ->^* x[6] & (y[5] ->^* y[6] & zs[5] ->^* zs[6])) (5) -> (7), if (y[5] >= x[5] & x[5] ->^* x[7] & (y[5] ->^* y[7] & zs[5] ->^* zs[7])) The set Q consists of the following terms: app(nil, x0) app(cons(x0, x1), x2) split(x0, e) split(x0, ins(x1, x2)) Cond_split(TRUE, x0, ins(x1, x2)) if_1(pair(x0, x1), x2, x3, x4) Cond_if_1(TRUE, pair(x0, x1), x2, x3, x4) Cond_split1(TRUE, x0, ins(x1, x2)) if_2(pair(x0, x1), x2, x3, x4) Cond_if_2(TRUE, pair(x0, x1), x2, x3, x4) qsort(e) qsort(ins(x0, x1)) if_3(pair(x0, x1), x2, x3) ---------------------------------------- (5) IDependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 3 SCCs with 6 less nodes. ---------------------------------------- (6) Complex Obligation (AND) ---------------------------------------- (7) Obligation: IDP problem: The following function symbols are pre-defined: <<< & ~ Bwand: (Integer, Integer) -> Integer >= ~ Ge: (Integer, Integer) -> Boolean | ~ Bwor: (Integer, Integer) -> Integer / ~ Div: (Integer, Integer) -> Integer != ~ Neq: (Integer, Integer) -> Boolean && ~ Land: (Boolean, Boolean) -> Boolean ! ~ Lnot: (Boolean) -> Boolean = ~ Eq: (Integer, Integer) -> Boolean <= ~ Le: (Integer, Integer) -> Boolean ^ ~ Bwxor: (Integer, Integer) -> Integer % ~ Mod: (Integer, Integer) -> Integer > ~ Gt: (Integer, Integer) -> Boolean + ~ Add: (Integer, Integer) -> Integer -1 ~ UnaryMinus: (Integer) -> Integer < ~ Lt: (Integer, Integer) -> Boolean || ~ Lor: (Boolean, Boolean) -> Boolean - ~ Sub: (Integer, Integer) -> Integer ~ ~ Bwnot: (Integer) -> Integer * ~ Mul: (Integer, Integer) -> Integer >>> The following domains are used: Integer The ITRS R consists of the following rules: app(nil, zs) -> zs app(cons(x, ys), zs) -> cons(x, app(ys, zs)) split(x, e) -> pair(e, e) split(x, ins(y, zs)) -> Cond_split(x > y, x, ins(y, zs)) Cond_split(TRUE, x, ins(y, zs)) -> if_1(split(x, zs), x, y, zs) if_1(pair(zl, zh), x, y, zs) -> Cond_if_1(x > y, pair(zl, zh), x, y, zs) Cond_if_1(TRUE, pair(zl, zh), x, y, zs) -> pair(ins(y, zl), zh) split(x, ins(y, zs)) -> Cond_split1(y >= x, x, ins(y, zs)) Cond_split1(TRUE, x, ins(y, zs)) -> if_2(split(x, zs), x, y, zs) if_2(pair(zl, zh), x, y, zs) -> Cond_if_2(y >= x, pair(zl, zh), x, y, zs) Cond_if_2(TRUE, pair(zl, zh), x, y, zs) -> pair(zl, ins(y, zh)) qsort(e) -> nil qsort(ins(x, ys)) -> if_3(split(x, ys), x, ys) if_3(pair(yl, yh), x, ys) -> app(qsort(yl), cons(x, qsort(yh))) The integer pair graph contains the following rules and edges: (0): APP(cons(x[0], ys[0]), zs[0]) -> APP(ys[0], zs[0]) (0) -> (0), if (ys[0] ->^* cons(x[0]', ys[0]') & zs[0] ->^* zs[0]') The set Q consists of the following terms: app(nil, x0) app(cons(x0, x1), x2) split(x0, e) split(x0, ins(x1, x2)) Cond_split(TRUE, x0, ins(x1, x2)) if_1(pair(x0, x1), x2, x3, x4) Cond_if_1(TRUE, pair(x0, x1), x2, x3, x4) Cond_split1(TRUE, x0, ins(x1, x2)) if_2(pair(x0, x1), x2, x3, x4) Cond_if_2(TRUE, pair(x0, x1), x2, x3, x4) qsort(e) qsort(ins(x0, x1)) if_3(pair(x0, x1), x2, x3) ---------------------------------------- (8) UsableRulesProof (EQUIVALENT) As all Q-normal forms are R-normal forms we are in the innermost case. Hence, by the usable rules processor [LPAR04] we can delete all non-usable rules [FROCOS05] from R. ---------------------------------------- (9) Obligation: IDP problem: The following function symbols are pre-defined: <<< & ~ Bwand: (Integer, Integer) -> Integer >= ~ Ge: (Integer, Integer) -> Boolean | ~ Bwor: (Integer, Integer) -> Integer / ~ Div: (Integer, Integer) -> Integer != ~ Neq: (Integer, Integer) -> Boolean && ~ Land: (Boolean, Boolean) -> Boolean ! ~ Lnot: (Boolean) -> Boolean = ~ Eq: (Integer, Integer) -> Boolean <= ~ Le: (Integer, Integer) -> Boolean ^ ~ Bwxor: (Integer, Integer) -> Integer % ~ Mod: (Integer, Integer) -> Integer > ~ Gt: (Integer, Integer) -> Boolean + ~ Add: (Integer, Integer) -> Integer -1 ~ UnaryMinus: (Integer) -> Integer < ~ Lt: (Integer, Integer) -> Boolean || ~ Lor: (Boolean, Boolean) -> Boolean - ~ Sub: (Integer, Integer) -> Integer ~ ~ Bwnot: (Integer) -> Integer * ~ Mul: (Integer, Integer) -> Integer >>> The following domains are used: none R is empty. The integer pair graph contains the following rules and edges: (0): APP(cons(x[0], ys[0]), zs[0]) -> APP(ys[0], zs[0]) (0) -> (0), if (ys[0] ->^* cons(x[0]', ys[0]') & zs[0] ->^* zs[0]') The set Q consists of the following terms: app(nil, x0) app(cons(x0, x1), x2) split(x0, e) split(x0, ins(x1, x2)) Cond_split(TRUE, x0, ins(x1, x2)) if_1(pair(x0, x1), x2, x3, x4) Cond_if_1(TRUE, pair(x0, x1), x2, x3, x4) Cond_split1(TRUE, x0, ins(x1, x2)) if_2(pair(x0, x1), x2, x3, x4) Cond_if_2(TRUE, pair(x0, x1), x2, x3, x4) qsort(e) qsort(ins(x0, x1)) if_3(pair(x0, x1), x2, x3) ---------------------------------------- (10) IDPtoQDPProof (SOUND) Represented integers and predefined function symbols by Terms ---------------------------------------- (11) Obligation: Q DP problem: The TRS P consists of the following rules: APP(cons(x[0], ys[0]), zs[0]) -> APP(ys[0], zs[0]) R is empty. The set Q consists of the following terms: app(nil, x0) app(cons(x0, x1), x2) split(x0, e) split(x0, ins(x1, x2)) Cond_split(true, x0, ins(x1, x2)) if_1(pair(x0, x1), x2, x3, x4) Cond_if_1(true, pair(x0, x1), x2, x3, x4) Cond_split1(true, x0, ins(x1, x2)) if_2(pair(x0, x1), x2, x3, x4) Cond_if_2(true, pair(x0, x1), x2, x3, x4) qsort(e) qsort(ins(x0, x1)) if_3(pair(x0, x1), x2, x3) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (12) QReductionProof (EQUIVALENT) We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. app(nil, x0) app(cons(x0, x1), x2) split(x0, e) split(x0, ins(x1, x2)) Cond_split(true, x0, ins(x1, x2)) if_1(pair(x0, x1), x2, x3, x4) Cond_if_1(true, pair(x0, x1), x2, x3, x4) Cond_split1(true, x0, ins(x1, x2)) if_2(pair(x0, x1), x2, x3, x4) Cond_if_2(true, pair(x0, x1), x2, x3, x4) qsort(e) qsort(ins(x0, x1)) if_3(pair(x0, x1), x2, x3) ---------------------------------------- (13) Obligation: Q DP problem: The TRS P consists of the following rules: APP(cons(x[0], ys[0]), zs[0]) -> APP(ys[0], zs[0]) R is empty. Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (14) QDPSizeChangeProof (EQUIVALENT) By using the subterm criterion [SUBTERM_CRITERION] together with the size-change analysis [AAECC05] we have proven that there are no infinite chains for this DP problem. From the DPs we obtained the following set of size-change graphs: *APP(cons(x[0], ys[0]), zs[0]) -> APP(ys[0], zs[0]) The graph contains the following edges 1 > 1, 2 >= 2 ---------------------------------------- (15) YES ---------------------------------------- (16) Obligation: IDP problem: The following function symbols are pre-defined: <<< & ~ Bwand: (Integer, Integer) -> Integer >= ~ Ge: (Integer, Integer) -> Boolean | ~ Bwor: (Integer, Integer) -> Integer / ~ Div: (Integer, Integer) -> Integer != ~ Neq: (Integer, Integer) -> Boolean && ~ Land: (Boolean, Boolean) -> Boolean ! ~ Lnot: (Boolean) -> Boolean = ~ Eq: (Integer, Integer) -> Boolean <= ~ Le: (Integer, Integer) -> Boolean ^ ~ Bwxor: (Integer, Integer) -> Integer % ~ Mod: (Integer, Integer) -> Integer > ~ Gt: (Integer, Integer) -> Boolean + ~ Add: (Integer, Integer) -> Integer -1 ~ UnaryMinus: (Integer) -> Integer < ~ Lt: (Integer, Integer) -> Boolean || ~ Lor: (Boolean, Boolean) -> Boolean - ~ Sub: (Integer, Integer) -> Integer ~ ~ Bwnot: (Integer) -> Integer * ~ Mul: (Integer, Integer) -> Integer >>> The following domains are used: Integer The ITRS R consists of the following rules: app(nil, zs) -> zs app(cons(x, ys), zs) -> cons(x, app(ys, zs)) split(x, e) -> pair(e, e) split(x, ins(y, zs)) -> Cond_split(x > y, x, ins(y, zs)) Cond_split(TRUE, x, ins(y, zs)) -> if_1(split(x, zs), x, y, zs) if_1(pair(zl, zh), x, y, zs) -> Cond_if_1(x > y, pair(zl, zh), x, y, zs) Cond_if_1(TRUE, pair(zl, zh), x, y, zs) -> pair(ins(y, zl), zh) split(x, ins(y, zs)) -> Cond_split1(y >= x, x, ins(y, zs)) Cond_split1(TRUE, x, ins(y, zs)) -> if_2(split(x, zs), x, y, zs) if_2(pair(zl, zh), x, y, zs) -> Cond_if_2(y >= x, pair(zl, zh), x, y, zs) Cond_if_2(TRUE, pair(zl, zh), x, y, zs) -> pair(zl, ins(y, zh)) qsort(e) -> nil qsort(ins(x, ys)) -> if_3(split(x, ys), x, ys) if_3(pair(yl, yh), x, ys) -> app(qsort(yl), cons(x, qsort(yh))) The integer pair graph contains the following rules and edges: (7): COND_SPLIT1(TRUE, x[7], ins(y[7], zs[7])) -> SPLIT(x[7], zs[7]) (5): SPLIT(x[5], ins(y[5], zs[5])) -> COND_SPLIT1(y[5] >= x[5], x[5], ins(y[5], zs[5])) (3): COND_SPLIT(TRUE, x[3], ins(y[3], zs[3])) -> SPLIT(x[3], zs[3]) (1): SPLIT(x[1], ins(y[1], zs[1])) -> COND_SPLIT(x[1] > y[1], x[1], ins(y[1], zs[1])) (3) -> (1), if (x[3] ->^* x[1] & zs[3] ->^* ins(y[1], zs[1])) (7) -> (1), if (x[7] ->^* x[1] & zs[7] ->^* ins(y[1], zs[1])) (1) -> (3), if (x[1] > y[1] & x[1] ->^* x[3] & (y[1] ->^* y[3] & zs[1] ->^* zs[3])) (3) -> (5), if (x[3] ->^* x[5] & zs[3] ->^* ins(y[5], zs[5])) (7) -> (5), if (x[7] ->^* x[5] & zs[7] ->^* ins(y[5], zs[5])) (5) -> (7), if (y[5] >= x[5] & x[5] ->^* x[7] & (y[5] ->^* y[7] & zs[5] ->^* zs[7])) The set Q consists of the following terms: app(nil, x0) app(cons(x0, x1), x2) split(x0, e) split(x0, ins(x1, x2)) Cond_split(TRUE, x0, ins(x1, x2)) if_1(pair(x0, x1), x2, x3, x4) Cond_if_1(TRUE, pair(x0, x1), x2, x3, x4) Cond_split1(TRUE, x0, ins(x1, x2)) if_2(pair(x0, x1), x2, x3, x4) Cond_if_2(TRUE, pair(x0, x1), x2, x3, x4) qsort(e) qsort(ins(x0, x1)) if_3(pair(x0, x1), x2, x3) ---------------------------------------- (17) UsableRulesProof (EQUIVALENT) As all Q-normal forms are R-normal forms we are in the innermost case. Hence, by the usable rules processor [LPAR04] we can delete all non-usable rules [FROCOS05] from R. ---------------------------------------- (18) Obligation: IDP problem: The following function symbols are pre-defined: <<< & ~ Bwand: (Integer, Integer) -> Integer >= ~ Ge: (Integer, Integer) -> Boolean | ~ Bwor: (Integer, Integer) -> Integer / ~ Div: (Integer, Integer) -> Integer != ~ Neq: (Integer, Integer) -> Boolean && ~ Land: (Boolean, Boolean) -> Boolean ! ~ Lnot: (Boolean) -> Boolean = ~ Eq: (Integer, Integer) -> Boolean <= ~ Le: (Integer, Integer) -> Boolean ^ ~ Bwxor: (Integer, Integer) -> Integer % ~ Mod: (Integer, Integer) -> Integer > ~ Gt: (Integer, Integer) -> Boolean + ~ Add: (Integer, Integer) -> Integer -1 ~ UnaryMinus: (Integer) -> Integer < ~ Lt: (Integer, Integer) -> Boolean || ~ Lor: (Boolean, Boolean) -> Boolean - ~ Sub: (Integer, Integer) -> Integer ~ ~ Bwnot: (Integer) -> Integer * ~ Mul: (Integer, Integer) -> Integer >>> The following domains are used: Integer R is empty. The integer pair graph contains the following rules and edges: (7): COND_SPLIT1(TRUE, x[7], ins(y[7], zs[7])) -> SPLIT(x[7], zs[7]) (5): SPLIT(x[5], ins(y[5], zs[5])) -> COND_SPLIT1(y[5] >= x[5], x[5], ins(y[5], zs[5])) (3): COND_SPLIT(TRUE, x[3], ins(y[3], zs[3])) -> SPLIT(x[3], zs[3]) (1): SPLIT(x[1], ins(y[1], zs[1])) -> COND_SPLIT(x[1] > y[1], x[1], ins(y[1], zs[1])) (3) -> (1), if (x[3] ->^* x[1] & zs[3] ->^* ins(y[1], zs[1])) (7) -> (1), if (x[7] ->^* x[1] & zs[7] ->^* ins(y[1], zs[1])) (1) -> (3), if (x[1] > y[1] & x[1] ->^* x[3] & (y[1] ->^* y[3] & zs[1] ->^* zs[3])) (3) -> (5), if (x[3] ->^* x[5] & zs[3] ->^* ins(y[5], zs[5])) (7) -> (5), if (x[7] ->^* x[5] & zs[7] ->^* ins(y[5], zs[5])) (5) -> (7), if (y[5] >= x[5] & x[5] ->^* x[7] & (y[5] ->^* y[7] & zs[5] ->^* zs[7])) The set Q consists of the following terms: app(nil, x0) app(cons(x0, x1), x2) split(x0, e) split(x0, ins(x1, x2)) Cond_split(TRUE, x0, ins(x1, x2)) if_1(pair(x0, x1), x2, x3, x4) Cond_if_1(TRUE, pair(x0, x1), x2, x3, x4) Cond_split1(TRUE, x0, ins(x1, x2)) if_2(pair(x0, x1), x2, x3, x4) Cond_if_2(TRUE, pair(x0, x1), x2, x3, x4) qsort(e) qsort(ins(x0, x1)) if_3(pair(x0, x1), x2, x3) ---------------------------------------- (19) IDPNonInfProof (SOUND) Used the following options for this NonInfProof: IDPGPoloSolver: Range: [(-1,2)] IsNat: true Interpretation Shape Heuristic: aprove.DPFramework.IDPProblem.Processors.nonInf.poly.IdpDefaultShapeHeuristic@4ac745d1 Constraint Generator: NonInfConstraintGenerator: PathGenerator: MetricPathGenerator: Max Left Steps: 1 Max Right Steps: 1 The constraints were generated the following way: The DP Problem is simplified using the Induction Calculus [NONINF] with the following steps: Note that final constraints are written in bold face. For Pair COND_SPLIT1(TRUE, x[7], ins(y[7], zs[7])) -> SPLIT(x[7], zs[7]) the following chains were created: *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: (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])), >=)) We simplified constraint (1) using rules (III), (IV) which results in the following new constraint: (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])), >=)) We simplified constraint (2) using rule (POLY_CONSTRAINTS) which results in the following new constraint: (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) We simplified constraint (3) using rule (IDP_POLY_SIMPLIFY) which results in the following new constraint: (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) We simplified constraint (4) using rule (POLY_REMOVE_MIN_MAX) which results in the following new constraint: (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) We simplified constraint (5) using rule (IDP_UNRESTRICTED_VARS) which results in the following new constraint: (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) *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: (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])), >=)) We simplified constraint (1) using rules (III), (IV) which results in the following new constraint: (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])), >=)) We simplified constraint (2) using rule (POLY_CONSTRAINTS) which results in the following new constraint: (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) We simplified constraint (3) using rule (IDP_POLY_SIMPLIFY) which results in the following new constraint: (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) We simplified constraint (4) using rule (POLY_REMOVE_MIN_MAX) which results in the following new constraint: (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) We simplified constraint (5) using rule (IDP_UNRESTRICTED_VARS) which results in the following new constraint: (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) 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: *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: (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]))), >=)) We simplified constraint (1) using rule (IV) which results in the following new constraint: (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]))), >=)) We simplified constraint (2) using rule (POLY_CONSTRAINTS) which results in the following new constraint: (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) We simplified constraint (3) using rule (IDP_POLY_SIMPLIFY) which results in the following new constraint: (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) We simplified constraint (4) using rule (POLY_REMOVE_MIN_MAX) which results in the following new constraint: (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) We simplified constraint (5) using rules (IDP_UNRESTRICTED_VARS), (IDP_POLY_GCD) which results in the following new constraint: (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) For Pair COND_SPLIT(TRUE, x[3], ins(y[3], zs[3])) -> SPLIT(x[3], zs[3]) the following chains were created: *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: (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])), >=)) We simplified constraint (1) using rules (III), (IV) which results in the following new constraint: (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])), >=)) We simplified constraint (2) using rule (POLY_CONSTRAINTS) which results in the following new constraint: (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) We simplified constraint (3) using rule (IDP_POLY_SIMPLIFY) which results in the following new constraint: (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) We simplified constraint (4) using rule (POLY_REMOVE_MIN_MAX) which results in the following new constraint: (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) We simplified constraint (5) using rule (IDP_UNRESTRICTED_VARS) which results in the following new constraint: (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) *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: (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])), >=)) We simplified constraint (1) using rules (III), (IV) which results in the following new constraint: (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])), >=)) We simplified constraint (2) using rule (POLY_CONSTRAINTS) which results in the following new constraint: (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) We simplified constraint (3) using rule (IDP_POLY_SIMPLIFY) which results in the following new constraint: (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) We simplified constraint (4) using rule (POLY_REMOVE_MIN_MAX) which results in the following new constraint: (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) We simplified constraint (5) using rule (IDP_UNRESTRICTED_VARS) which results in the following new constraint: (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) 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: *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: (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]))), >=)) We simplified constraint (1) using rule (IV) which results in the following new constraint: (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]))), >=)) We simplified constraint (2) using rule (POLY_CONSTRAINTS) which results in the following new constraint: (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) We simplified constraint (3) using rule (IDP_POLY_SIMPLIFY) which results in the following new constraint: (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) We simplified constraint (4) using rule (POLY_REMOVE_MIN_MAX) which results in the following new constraint: (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) We simplified constraint (5) using rules (IDP_UNRESTRICTED_VARS), (IDP_POLY_GCD) which results in the following new constraint: (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) To summarize, we get the following constraints P__>=_ for the following pairs. *COND_SPLIT1(TRUE, x[7], ins(y[7], zs[7])) -> SPLIT(x[7], zs[7]) *(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) *(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) *SPLIT(x[5], ins(y[5], zs[5])) -> COND_SPLIT1(>=(y[5], x[5]), x[5], ins(y[5], zs[5])) *(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) *COND_SPLIT(TRUE, x[3], ins(y[3], zs[3])) -> SPLIT(x[3], zs[3]) *(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) *(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) *SPLIT(x[1], ins(y[1], zs[1])) -> COND_SPLIT(>(x[1], y[1]), x[1], ins(y[1], zs[1])) *(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) 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. Using the following integer polynomial ordering the resulting constraints can be solved Polynomial interpretation over integers with natural coefficients for non-tuple symbols [NONINF][POLO]: POL(TRUE) = 0 POL(FALSE) = 0 POL(COND_SPLIT1(x_1, x_2, x_3)) = [-1] + x_3 + [2]x_2 POL(ins(x_1, x_2)) = [3] + [2]x_2 POL(SPLIT(x_1, x_2)) = [-1] + [2]x_2 + [2]x_1 POL(>=(x_1, x_2)) = 0 POL(COND_SPLIT(x_1, x_2, x_3)) = x_3 + [2]x_2 POL(>(x_1, x_2)) = 0 The following pairs are in P_>: 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])) 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])) The following pairs are in P_bound: 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])) 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])) The following pairs are in P_>=: none There are no usable rules. ---------------------------------------- (20) Obligation: IDP problem: The following function symbols are pre-defined: <<< & ~ Bwand: (Integer, Integer) -> Integer >= ~ Ge: (Integer, Integer) -> Boolean | ~ Bwor: (Integer, Integer) -> Integer / ~ Div: (Integer, Integer) -> Integer != ~ Neq: (Integer, Integer) -> Boolean && ~ Land: (Boolean, Boolean) -> Boolean ! ~ Lnot: (Boolean) -> Boolean = ~ Eq: (Integer, Integer) -> Boolean <= ~ Le: (Integer, Integer) -> Boolean ^ ~ Bwxor: (Integer, Integer) -> Integer % ~ Mod: (Integer, Integer) -> Integer > ~ Gt: (Integer, Integer) -> Boolean + ~ Add: (Integer, Integer) -> Integer -1 ~ UnaryMinus: (Integer) -> Integer < ~ Lt: (Integer, Integer) -> Boolean || ~ Lor: (Boolean, Boolean) -> Boolean - ~ Sub: (Integer, Integer) -> Integer ~ ~ Bwnot: (Integer) -> Integer * ~ Mul: (Integer, Integer) -> Integer >>> The following domains are used: none R is empty. The integer pair graph is empty. The set Q consists of the following terms: app(nil, x0) app(cons(x0, x1), x2) split(x0, e) split(x0, ins(x1, x2)) Cond_split(TRUE, x0, ins(x1, x2)) if_1(pair(x0, x1), x2, x3, x4) Cond_if_1(TRUE, pair(x0, x1), x2, x3, x4) Cond_split1(TRUE, x0, ins(x1, x2)) if_2(pair(x0, x1), x2, x3, x4) Cond_if_2(TRUE, pair(x0, x1), x2, x3, x4) qsort(e) qsort(ins(x0, x1)) if_3(pair(x0, x1), x2, x3) ---------------------------------------- (21) PisEmptyProof (EQUIVALENT) The TRS P is empty. Hence, there is no (P,Q,R) chain. ---------------------------------------- (22) YES ---------------------------------------- (23) Obligation: IDP problem: The following function symbols are pre-defined: <<< & ~ Bwand: (Integer, Integer) -> Integer >= ~ Ge: (Integer, Integer) -> Boolean | ~ Bwor: (Integer, Integer) -> Integer / ~ Div: (Integer, Integer) -> Integer != ~ Neq: (Integer, Integer) -> Boolean && ~ Land: (Boolean, Boolean) -> Boolean ! ~ Lnot: (Boolean) -> Boolean = ~ Eq: (Integer, Integer) -> Boolean <= ~ Le: (Integer, Integer) -> Boolean ^ ~ Bwxor: (Integer, Integer) -> Integer % ~ Mod: (Integer, Integer) -> Integer > ~ Gt: (Integer, Integer) -> Boolean + ~ Add: (Integer, Integer) -> Integer -1 ~ UnaryMinus: (Integer) -> Integer < ~ Lt: (Integer, Integer) -> Boolean || ~ Lor: (Boolean, Boolean) -> Boolean - ~ Sub: (Integer, Integer) -> Integer ~ ~ Bwnot: (Integer) -> Integer * ~ Mul: (Integer, Integer) -> Integer >>> The following domains are used: Integer The ITRS R consists of the following rules: app(nil, zs) -> zs app(cons(x, ys), zs) -> cons(x, app(ys, zs)) split(x, e) -> pair(e, e) split(x, ins(y, zs)) -> Cond_split(x > y, x, ins(y, zs)) Cond_split(TRUE, x, ins(y, zs)) -> if_1(split(x, zs), x, y, zs) if_1(pair(zl, zh), x, y, zs) -> Cond_if_1(x > y, pair(zl, zh), x, y, zs) Cond_if_1(TRUE, pair(zl, zh), x, y, zs) -> pair(ins(y, zl), zh) split(x, ins(y, zs)) -> Cond_split1(y >= x, x, ins(y, zs)) Cond_split1(TRUE, x, ins(y, zs)) -> if_2(split(x, zs), x, y, zs) if_2(pair(zl, zh), x, y, zs) -> Cond_if_2(y >= x, pair(zl, zh), x, y, zs) Cond_if_2(TRUE, pair(zl, zh), x, y, zs) -> pair(zl, ins(y, zh)) qsort(e) -> nil qsort(ins(x, ys)) -> if_3(split(x, ys), x, ys) if_3(pair(yl, yh), x, ys) -> app(qsort(yl), cons(x, qsort(yh))) The integer pair graph contains the following rules and edges: (13): IF_3(pair(yl[13], yh[13]), x[13], ys[13]) -> QSORT(yh[13]) (12): IF_3(pair(yl[12], yh[12]), x[12], ys[12]) -> QSORT(yl[12]) (9): QSORT(ins(x[9], ys[9])) -> IF_3(split(x[9], ys[9]), x[9], ys[9]) (12) -> (9), if (yl[12] ->^* ins(x[9], ys[9])) (13) -> (9), if (yh[13] ->^* ins(x[9], ys[9])) (9) -> (12), if (split(x[9], ys[9]) ->^* pair(yl[12], yh[12]) & x[9] ->^* x[12] & ys[9] ->^* ys[12]) (9) -> (13), if (split(x[9], ys[9]) ->^* pair(yl[13], yh[13]) & x[9] ->^* x[13] & ys[9] ->^* ys[13]) The set Q consists of the following terms: app(nil, x0) app(cons(x0, x1), x2) split(x0, e) split(x0, ins(x1, x2)) Cond_split(TRUE, x0, ins(x1, x2)) if_1(pair(x0, x1), x2, x3, x4) Cond_if_1(TRUE, pair(x0, x1), x2, x3, x4) Cond_split1(TRUE, x0, ins(x1, x2)) if_2(pair(x0, x1), x2, x3, x4) Cond_if_2(TRUE, pair(x0, x1), x2, x3, x4) qsort(e) qsort(ins(x0, x1)) if_3(pair(x0, x1), x2, x3) ---------------------------------------- (24) UsableRulesProof (EQUIVALENT) As all Q-normal forms are R-normal forms we are in the innermost case. Hence, by the usable rules processor [LPAR04] we can delete all non-usable rules [FROCOS05] from R. ---------------------------------------- (25) Obligation: IDP problem: The following function symbols are pre-defined: <<< & ~ Bwand: (Integer, Integer) -> Integer >= ~ Ge: (Integer, Integer) -> Boolean | ~ Bwor: (Integer, Integer) -> Integer / ~ Div: (Integer, Integer) -> Integer != ~ Neq: (Integer, Integer) -> Boolean && ~ Land: (Boolean, Boolean) -> Boolean ! ~ Lnot: (Boolean) -> Boolean = ~ Eq: (Integer, Integer) -> Boolean <= ~ Le: (Integer, Integer) -> Boolean ^ ~ Bwxor: (Integer, Integer) -> Integer % ~ Mod: (Integer, Integer) -> Integer > ~ Gt: (Integer, Integer) -> Boolean + ~ Add: (Integer, Integer) -> Integer -1 ~ UnaryMinus: (Integer) -> Integer < ~ Lt: (Integer, Integer) -> Boolean || ~ Lor: (Boolean, Boolean) -> Boolean - ~ Sub: (Integer, Integer) -> Integer ~ ~ Bwnot: (Integer) -> Integer * ~ Mul: (Integer, Integer) -> Integer >>> The following domains are used: Integer The ITRS R consists of the following rules: split(x, e) -> pair(e, e) split(x, ins(y, zs)) -> Cond_split(x > y, x, ins(y, zs)) split(x, ins(y, zs)) -> Cond_split1(y >= x, x, ins(y, zs)) Cond_split(TRUE, x, ins(y, zs)) -> if_1(split(x, zs), x, y, zs) Cond_split1(TRUE, x, ins(y, zs)) -> if_2(split(x, zs), x, y, zs) if_1(pair(zl, zh), x, y, zs) -> Cond_if_1(x > y, pair(zl, zh), x, y, zs) if_2(pair(zl, zh), x, y, zs) -> Cond_if_2(y >= x, pair(zl, zh), x, y, zs) Cond_if_1(TRUE, pair(zl, zh), x, y, zs) -> pair(ins(y, zl), zh) Cond_if_2(TRUE, pair(zl, zh), x, y, zs) -> pair(zl, ins(y, zh)) The integer pair graph contains the following rules and edges: (13): IF_3(pair(yl[13], yh[13]), x[13], ys[13]) -> QSORT(yh[13]) (12): IF_3(pair(yl[12], yh[12]), x[12], ys[12]) -> QSORT(yl[12]) (9): QSORT(ins(x[9], ys[9])) -> IF_3(split(x[9], ys[9]), x[9], ys[9]) (12) -> (9), if (yl[12] ->^* ins(x[9], ys[9])) (13) -> (9), if (yh[13] ->^* ins(x[9], ys[9])) (9) -> (12), if (split(x[9], ys[9]) ->^* pair(yl[12], yh[12]) & x[9] ->^* x[12] & ys[9] ->^* ys[12]) (9) -> (13), if (split(x[9], ys[9]) ->^* pair(yl[13], yh[13]) & x[9] ->^* x[13] & ys[9] ->^* ys[13]) The set Q consists of the following terms: app(nil, x0) app(cons(x0, x1), x2) split(x0, e) split(x0, ins(x1, x2)) Cond_split(TRUE, x0, ins(x1, x2)) if_1(pair(x0, x1), x2, x3, x4) Cond_if_1(TRUE, pair(x0, x1), x2, x3, x4) Cond_split1(TRUE, x0, ins(x1, x2)) if_2(pair(x0, x1), x2, x3, x4) Cond_if_2(TRUE, pair(x0, x1), x2, x3, x4) qsort(e) qsort(ins(x0, x1)) if_3(pair(x0, x1), x2, x3) ---------------------------------------- (26) IDPNonInfProof (SOUND) Used the following options for this NonInfProof: IDPGPoloSolver: Range: [(-1,2)] IsNat: true Interpretation Shape Heuristic: aprove.DPFramework.IDPProblem.Processors.nonInf.poly.IdpDefaultShapeHeuristic@4ac745d1 Constraint Generator: NonInfConstraintGenerator: PathGenerator: MetricPathGenerator: Max Left Steps: 1 Max Right Steps: 1 The constraints were generated the following way: The DP Problem is simplified using the Induction Calculus [NONINF] with the following steps: Note that final constraints are written in bold face. For Pair IF_3(pair(yl[13], yh[13]), x[13], ys[13]) -> QSORT(yh[13]) the following chains were created: *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: (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])), >=)) We simplified constraint (1) using rule (III) which results in the following new constraint: (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])), >=)) 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: (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])), >=)) (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])), >=)) (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])), >=)) We solved constraint (3) using rules (I), (II).We simplified constraint (4) using rules (III), (VII) which results in the following new constraint: (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])), >=)) We simplified constraint (5) using rules (III), (VII) which results in the following new constraint: (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])), >=)) We simplified constraint (6) using rule (POLY_CONSTRAINTS) which results in the following new constraint: (8) ((U^Increasing(QSORT(yh[13])), >=) & [(-1)Bound*bni_47] + [(3)bni_47]ys[9]1 + [bni_47]yl[13] >= 0 & [1 + (-1)bso_48] + yl[13] >= 0) We simplified constraint (7) using rule (POLY_CONSTRAINTS) which results in the following new constraint: (9) ((U^Increasing(QSORT(yh[13])), >=) & [(-1)Bound*bni_47] + [(3)bni_47]ys[9]1 + [bni_47]yl[13] >= 0 & [1 + (-1)bso_48] + yl[13] >= 0) We simplified constraint (9) using rule (IDP_POLY_SIMPLIFY) which results in the following new constraint: (10) ((U^Increasing(QSORT(yh[13])), >=) & [(-1)Bound*bni_47] + [(3)bni_47]ys[9]1 + [bni_47]yl[13] >= 0 & [1 + (-1)bso_48] + yl[13] >= 0) We simplified constraint (8) using rule (IDP_POLY_SIMPLIFY) which results in the following new constraint: (11) ((U^Increasing(QSORT(yh[13])), >=) & [(-1)Bound*bni_47] + [(3)bni_47]ys[9]1 + [bni_47]yl[13] >= 0 & [1 + (-1)bso_48] + yl[13] >= 0) We simplified constraint (10) using rule (POLY_REMOVE_MIN_MAX) which results in the following new constraint: (12) ((U^Increasing(QSORT(yh[13])), >=) & [(-1)Bound*bni_47] + [(3)bni_47]ys[9]1 + [bni_47]yl[13] >= 0 & [1 + (-1)bso_48] + yl[13] >= 0) We simplified constraint (11) using rule (POLY_REMOVE_MIN_MAX) which results in the following new constraint: (13) ((U^Increasing(QSORT(yh[13])), >=) & [(-1)Bound*bni_47] + [(3)bni_47]ys[9]1 + [bni_47]yl[13] >= 0 & [1 + (-1)bso_48] + yl[13] >= 0) We simplified constraint (12) using rule (IDP_UNRESTRICTED_VARS) which results in the following new constraint: (14) ((U^Increasing(QSORT(yh[13])), >=) & 0 >= 0 & 0 >= 0 & 0 >= 0 & [(3)bni_47] >= 0 & 0 >= 0 & [bni_47] >= 0 & [(-1)Bound*bni_47] >= 0 & 0 >= 0 & 0 >= 0 & 0 >= 0 & [1] >= 0 & [1 + (-1)bso_48] >= 0) We simplified constraint (13) using rule (IDP_UNRESTRICTED_VARS) which results in the following new constraint: (15) ((U^Increasing(QSORT(yh[13])), >=) & 0 >= 0 & 0 >= 0 & 0 >= 0 & [(3)bni_47] >= 0 & 0 >= 0 & [bni_47] >= 0 & [(-1)Bound*bni_47] >= 0 & 0 >= 0 & 0 >= 0 & 0 >= 0 & [1] >= 0 & [1 + (-1)bso_48] >= 0) For Pair IF_3(pair(yl[12], yh[12]), x[12], ys[12]) -> QSORT(yl[12]) the following chains were created: *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: (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])), >=)) We simplified constraint (1) using rule (III) which results in the following new constraint: (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])), >=)) 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: (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])), >=)) (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])), >=)) (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])), >=)) We solved constraint (3) using rules (I), (II).We simplified constraint (4) using rules (III), (VII) which results in the following new constraint: (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])), >=)) We simplified constraint (5) using rules (III), (VII) which results in the following new constraint: (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])), >=)) We simplified constraint (6) using rule (POLY_CONSTRAINTS) which results in the following new constraint: (8) ((U^Increasing(QSORT(yl[12])), >=) & [(-1)Bound*bni_49] + [bni_49]yh[12] + [(3)bni_49]ys[9]1 >= 0 & [1 + (-1)bso_50] + yh[12] >= 0) We simplified constraint (7) using rule (POLY_CONSTRAINTS) which results in the following new constraint: (9) ((U^Increasing(QSORT(yl[12])), >=) & [(-1)Bound*bni_49] + [bni_49]yh[12] + [(3)bni_49]ys[9]1 >= 0 & [1 + (-1)bso_50] + yh[12] >= 0) We simplified constraint (9) using rule (IDP_POLY_SIMPLIFY) which results in the following new constraint: (10) ((U^Increasing(QSORT(yl[12])), >=) & [(-1)Bound*bni_49] + [bni_49]yh[12] + [(3)bni_49]ys[9]1 >= 0 & [1 + (-1)bso_50] + yh[12] >= 0) We simplified constraint (8) using rule (IDP_POLY_SIMPLIFY) which results in the following new constraint: (11) ((U^Increasing(QSORT(yl[12])), >=) & [(-1)Bound*bni_49] + [bni_49]yh[12] + [(3)bni_49]ys[9]1 >= 0 & [1 + (-1)bso_50] + yh[12] >= 0) We simplified constraint (10) using rule (POLY_REMOVE_MIN_MAX) which results in the following new constraint: (12) ((U^Increasing(QSORT(yl[12])), >=) & [(-1)Bound*bni_49] + [bni_49]yh[12] + [(3)bni_49]ys[9]1 >= 0 & [1 + (-1)bso_50] + yh[12] >= 0) We simplified constraint (11) using rule (POLY_REMOVE_MIN_MAX) which results in the following new constraint: (13) ((U^Increasing(QSORT(yl[12])), >=) & [(-1)Bound*bni_49] + [bni_49]yh[12] + [(3)bni_49]ys[9]1 >= 0 & [1 + (-1)bso_50] + yh[12] >= 0) We simplified constraint (12) using rule (IDP_UNRESTRICTED_VARS) which results in the following new constraint: (14) ((U^Increasing(QSORT(yl[12])), >=) & 0 >= 0 & 0 >= 0 & 0 >= 0 & [bni_49] >= 0 & [(3)bni_49] >= 0 & 0 >= 0 & [(-1)Bound*bni_49] >= 0 & 0 >= 0 & 0 >= 0 & 0 >= 0 & [1] >= 0 & [1 + (-1)bso_50] >= 0) We simplified constraint (13) using rule (IDP_UNRESTRICTED_VARS) which results in the following new constraint: (15) ((U^Increasing(QSORT(yl[12])), >=) & 0 >= 0 & 0 >= 0 & 0 >= 0 & [bni_49] >= 0 & [(3)bni_49] >= 0 & 0 >= 0 & [(-1)Bound*bni_49] >= 0 & 0 >= 0 & 0 >= 0 & 0 >= 0 & [1] >= 0 & [1 + (-1)bso_50] >= 0) For Pair QSORT(ins(x[9], ys[9])) -> IF_3(split(x[9], ys[9]), x[9], ys[9]) the following chains were created: *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: (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])), >=)) We simplified constraint (1) using rules (III), (IV) which results in the following new constraint: (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])), >=)) 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: (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])), >=)) (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])), >=)) (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])), >=)) We simplified constraint (3) using rules (I), (II), (IV) which results in the following new constraint: (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])), >=)) We simplified constraint (4) using rules (III), (VII) which results in the following new constraint: (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])), >=)) We simplified constraint (5) using rules (III), (VII) which results in the following new constraint: (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])), >=)) We simplified constraint (6) using rule (POLY_CONSTRAINTS) which results in the following new constraint: (9) ((U^Increasing(IF_3(split(x[9], ys[9]), x[9], ys[9])), >=) & [bni_51] = 0 & [(-1)bso_52] >= 0) We simplified constraint (7) using rule (POLY_CONSTRAINTS) which results in the following new constraint: (10) ((U^Increasing(IF_3(split(x[9], ys[9]), x[9], ys[9])), >=) & 0 >= 0 & [(-1)bso_52] >= 0) We simplified constraint (8) using rule (POLY_CONSTRAINTS) which results in the following new constraint: (11) ((U^Increasing(IF_3(split(x[9], ys[9]), x[9], ys[9])), >=) & 0 >= 0 & [(-1)bso_52] >= 0) We simplified constraint (9) using rule (IDP_POLY_SIMPLIFY) which results in the following new constraint: (12) ((U^Increasing(IF_3(split(x[9], ys[9]), x[9], ys[9])), >=) & [bni_51] = 0 & [(-1)bso_52] >= 0) We simplified constraint (11) using rule (IDP_POLY_SIMPLIFY) which results in the following new constraint: (13) ((U^Increasing(IF_3(split(x[9], ys[9]), x[9], ys[9])), >=) & 0 >= 0 & [(-1)bso_52] >= 0) We simplified constraint (10) using rule (IDP_POLY_SIMPLIFY) which results in the following new constraint: (14) ((U^Increasing(IF_3(split(x[9], ys[9]), x[9], ys[9])), >=) & 0 >= 0 & [(-1)bso_52] >= 0) We simplified constraint (12) using rule (POLY_REMOVE_MIN_MAX) which results in the following new constraint: (15) ((U^Increasing(IF_3(split(x[9], ys[9]), x[9], ys[9])), >=) & [bni_51] = 0 & [(-1)bso_52] >= 0) We simplified constraint (13) using rule (POLY_REMOVE_MIN_MAX) which results in the following new constraint: (16) ((U^Increasing(IF_3(split(x[9], ys[9]), x[9], ys[9])), >=) & 0 >= 0 & [(-1)bso_52] >= 0) We simplified constraint (14) using rule (POLY_REMOVE_MIN_MAX) which results in the following new constraint: (17) ((U^Increasing(IF_3(split(x[9], ys[9]), x[9], ys[9])), >=) & 0 >= 0 & [(-1)bso_52] >= 0) We simplified constraint (15) using rule (IDP_UNRESTRICTED_VARS) which results in the following new constraint: (18) ((U^Increasing(IF_3(split(x[9], ys[9]), x[9], ys[9])), >=) & [bni_51] = 0 & 0 >= 0 & [(-1)bso_52] >= 0) We simplified constraint (16) using rule (IDP_UNRESTRICTED_VARS) which results in the following new constraint: (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)bso_52] >= 0) We simplified constraint (17) using rule (IDP_UNRESTRICTED_VARS) which results in the following new constraint: (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)bso_52] >= 0) *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: (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])), >=)) We simplified constraint (1) using rules (III), (IV) which results in the following new constraint: (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])), >=)) 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: (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])), >=)) (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])), >=)) (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])), >=)) We simplified constraint (3) using rules (I), (II), (IV) which results in the following new constraint: (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])), >=)) We simplified constraint (4) using rules (III), (VII) which results in the following new constraint: (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])), >=)) We simplified constraint (5) using rules (III), (VII) which results in the following new constraint: (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])), >=)) We simplified constraint (6) using rule (POLY_CONSTRAINTS) which results in the following new constraint: (9) ((U^Increasing(IF_3(split(x[9], ys[9]), x[9], ys[9])), >=) & [bni_51] = 0 & [(-1)bso_52] >= 0) We simplified constraint (7) using rule (POLY_CONSTRAINTS) which results in the following new constraint: (10) ((U^Increasing(IF_3(split(x[9], ys[9]), x[9], ys[9])), >=) & 0 >= 0 & [(-1)bso_52] >= 0) We simplified constraint (8) using rule (POLY_CONSTRAINTS) which results in the following new constraint: (11) ((U^Increasing(IF_3(split(x[9], ys[9]), x[9], ys[9])), >=) & 0 >= 0 & [(-1)bso_52] >= 0) We simplified constraint (9) using rule (IDP_POLY_SIMPLIFY) which results in the following new constraint: (12) ((U^Increasing(IF_3(split(x[9], ys[9]), x[9], ys[9])), >=) & [bni_51] = 0 & [(-1)bso_52] >= 0) We simplified constraint (11) using rule (IDP_POLY_SIMPLIFY) which results in the following new constraint: (13) ((U^Increasing(IF_3(split(x[9], ys[9]), x[9], ys[9])), >=) & 0 >= 0 & [(-1)bso_52] >= 0) We simplified constraint (10) using rule (IDP_POLY_SIMPLIFY) which results in the following new constraint: (14) ((U^Increasing(IF_3(split(x[9], ys[9]), x[9], ys[9])), >=) & 0 >= 0 & [(-1)bso_52] >= 0) We simplified constraint (12) using rule (POLY_REMOVE_MIN_MAX) which results in the following new constraint: (15) ((U^Increasing(IF_3(split(x[9], ys[9]), x[9], ys[9])), >=) & [bni_51] = 0 & [(-1)bso_52] >= 0) We simplified constraint (13) using rule (POLY_REMOVE_MIN_MAX) which results in the following new constraint: (16) ((U^Increasing(IF_3(split(x[9], ys[9]), x[9], ys[9])), >=) & 0 >= 0 & [(-1)bso_52] >= 0) We simplified constraint (14) using rule (POLY_REMOVE_MIN_MAX) which results in the following new constraint: (17) ((U^Increasing(IF_3(split(x[9], ys[9]), x[9], ys[9])), >=) & 0 >= 0 & [(-1)bso_52] >= 0) We simplified constraint (15) using rule (IDP_UNRESTRICTED_VARS) which results in the following new constraint: (18) ((U^Increasing(IF_3(split(x[9], ys[9]), x[9], ys[9])), >=) & [bni_51] = 0 & 0 >= 0 & [(-1)bso_52] >= 0) We simplified constraint (16) using rule (IDP_UNRESTRICTED_VARS) which results in the following new constraint: (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)bso_52] >= 0) We simplified constraint (17) using rule (IDP_UNRESTRICTED_VARS) which results in the following new constraint: (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)bso_52] >= 0) *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: (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])), >=)) We simplified constraint (1) using rules (III), (IV) which results in the following new constraint: (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])), >=)) 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: (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])), >=)) (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])), >=)) (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])), >=)) We simplified constraint (3) using rules (I), (II), (IV) which results in the following new constraint: (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])), >=)) We simplified constraint (4) using rules (III), (VII) which results in the following new constraint: (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])), >=)) We simplified constraint (5) using rules (III), (VII) which results in the following new constraint: (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])), >=)) We simplified constraint (6) using rule (POLY_CONSTRAINTS) which results in the following new constraint: (9) ((U^Increasing(IF_3(split(x[9], ys[9]), x[9], ys[9])), >=) & [bni_51] = 0 & [(-1)bso_52] >= 0) We simplified constraint (7) using rule (POLY_CONSTRAINTS) which results in the following new constraint: (10) ((U^Increasing(IF_3(split(x[9], ys[9]), x[9], ys[9])), >=) & 0 >= 0 & [(-1)bso_52] >= 0) We simplified constraint (8) using rule (POLY_CONSTRAINTS) which results in the following new constraint: (11) ((U^Increasing(IF_3(split(x[9], ys[9]), x[9], ys[9])), >=) & 0 >= 0 & [(-1)bso_52] >= 0) We simplified constraint (9) using rule (IDP_POLY_SIMPLIFY) which results in the following new constraint: (12) ((U^Increasing(IF_3(split(x[9], ys[9]), x[9], ys[9])), >=) & [bni_51] = 0 & [(-1)bso_52] >= 0) We simplified constraint (11) using rule (IDP_POLY_SIMPLIFY) which results in the following new constraint: (13) ((U^Increasing(IF_3(split(x[9], ys[9]), x[9], ys[9])), >=) & 0 >= 0 & [(-1)bso_52] >= 0) We simplified constraint (10) using rule (IDP_POLY_SIMPLIFY) which results in the following new constraint: (14) ((U^Increasing(IF_3(split(x[9], ys[9]), x[9], ys[9])), >=) & 0 >= 0 & [(-1)bso_52] >= 0) We simplified constraint (12) using rule (POLY_REMOVE_MIN_MAX) which results in the following new constraint: (15) ((U^Increasing(IF_3(split(x[9], ys[9]), x[9], ys[9])), >=) & [bni_51] = 0 & [(-1)bso_52] >= 0) We simplified constraint (13) using rule (POLY_REMOVE_MIN_MAX) which results in the following new constraint: (16) ((U^Increasing(IF_3(split(x[9], ys[9]), x[9], ys[9])), >=) & 0 >= 0 & [(-1)bso_52] >= 0) We simplified constraint (14) using rule (POLY_REMOVE_MIN_MAX) which results in the following new constraint: (17) ((U^Increasing(IF_3(split(x[9], ys[9]), x[9], ys[9])), >=) & 0 >= 0 & [(-1)bso_52] >= 0) We simplified constraint (15) using rule (IDP_UNRESTRICTED_VARS) which results in the following new constraint: (18) ((U^Increasing(IF_3(split(x[9], ys[9]), x[9], ys[9])), >=) & [bni_51] = 0 & 0 >= 0 & [(-1)bso_52] >= 0) We simplified constraint (16) using rule (IDP_UNRESTRICTED_VARS) which results in the following new constraint: (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)bso_52] >= 0) We simplified constraint (17) using rule (IDP_UNRESTRICTED_VARS) which results in the following new constraint: (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)bso_52] >= 0) *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: (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])), >=)) We simplified constraint (1) using rules (III), (IV) which results in the following new constraint: (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])), >=)) 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: (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])), >=)) (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])), >=)) (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])), >=)) We simplified constraint (3) using rules (I), (II), (IV) which results in the following new constraint: (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])), >=)) We simplified constraint (4) using rules (III), (VII) which results in the following new constraint: (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])), >=)) We simplified constraint (5) using rules (III), (VII) which results in the following new constraint: (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])), >=)) We simplified constraint (6) using rule (POLY_CONSTRAINTS) which results in the following new constraint: (9) ((U^Increasing(IF_3(split(x[9], ys[9]), x[9], ys[9])), >=) & [bni_51] = 0 & [(-1)bso_52] >= 0) We simplified constraint (7) using rule (POLY_CONSTRAINTS) which results in the following new constraint: (10) ((U^Increasing(IF_3(split(x[9], ys[9]), x[9], ys[9])), >=) & 0 >= 0 & [(-1)bso_52] >= 0) We simplified constraint (8) using rule (POLY_CONSTRAINTS) which results in the following new constraint: (11) ((U^Increasing(IF_3(split(x[9], ys[9]), x[9], ys[9])), >=) & 0 >= 0 & [(-1)bso_52] >= 0) We simplified constraint (9) using rule (IDP_POLY_SIMPLIFY) which results in the following new constraint: (12) ((U^Increasing(IF_3(split(x[9], ys[9]), x[9], ys[9])), >=) & [bni_51] = 0 & [(-1)bso_52] >= 0) We simplified constraint (11) using rule (IDP_POLY_SIMPLIFY) which results in the following new constraint: (13) ((U^Increasing(IF_3(split(x[9], ys[9]), x[9], ys[9])), >=) & 0 >= 0 & [(-1)bso_52] >= 0) We simplified constraint (10) using rule (IDP_POLY_SIMPLIFY) which results in the following new constraint: (14) ((U^Increasing(IF_3(split(x[9], ys[9]), x[9], ys[9])), >=) & 0 >= 0 & [(-1)bso_52] >= 0) We simplified constraint (12) using rule (POLY_REMOVE_MIN_MAX) which results in the following new constraint: (15) ((U^Increasing(IF_3(split(x[9], ys[9]), x[9], ys[9])), >=) & [bni_51] = 0 & [(-1)bso_52] >= 0) We simplified constraint (13) using rule (POLY_REMOVE_MIN_MAX) which results in the following new constraint: (16) ((U^Increasing(IF_3(split(x[9], ys[9]), x[9], ys[9])), >=) & 0 >= 0 & [(-1)bso_52] >= 0) We simplified constraint (14) using rule (POLY_REMOVE_MIN_MAX) which results in the following new constraint: (17) ((U^Increasing(IF_3(split(x[9], ys[9]), x[9], ys[9])), >=) & 0 >= 0 & [(-1)bso_52] >= 0) We simplified constraint (15) using rule (IDP_UNRESTRICTED_VARS) which results in the following new constraint: (18) ((U^Increasing(IF_3(split(x[9], ys[9]), x[9], ys[9])), >=) & [bni_51] = 0 & 0 >= 0 & [(-1)bso_52] >= 0) We simplified constraint (16) using rule (IDP_UNRESTRICTED_VARS) which results in the following new constraint: (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)bso_52] >= 0) We simplified constraint (17) using rule (IDP_UNRESTRICTED_VARS) which results in the following new constraint: (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)bso_52] >= 0) To summarize, we get the following constraints P__>=_ for the following pairs. *IF_3(pair(yl[13], yh[13]), x[13], ys[13]) -> QSORT(yh[13]) *((U^Increasing(QSORT(yh[13])), >=) & 0 >= 0 & 0 >= 0 & 0 >= 0 & [(3)bni_47] >= 0 & 0 >= 0 & [bni_47] >= 0 & [(-1)Bound*bni_47] >= 0 & 0 >= 0 & 0 >= 0 & 0 >= 0 & [1] >= 0 & [1 + (-1)bso_48] >= 0) *((U^Increasing(QSORT(yh[13])), >=) & 0 >= 0 & 0 >= 0 & 0 >= 0 & [(3)bni_47] >= 0 & 0 >= 0 & [bni_47] >= 0 & [(-1)Bound*bni_47] >= 0 & 0 >= 0 & 0 >= 0 & 0 >= 0 & [1] >= 0 & [1 + (-1)bso_48] >= 0) *IF_3(pair(yl[12], yh[12]), x[12], ys[12]) -> QSORT(yl[12]) *((U^Increasing(QSORT(yl[12])), >=) & 0 >= 0 & 0 >= 0 & 0 >= 0 & [bni_49] >= 0 & [(3)bni_49] >= 0 & 0 >= 0 & [(-1)Bound*bni_49] >= 0 & 0 >= 0 & 0 >= 0 & 0 >= 0 & [1] >= 0 & [1 + (-1)bso_50] >= 0) *((U^Increasing(QSORT(yl[12])), >=) & 0 >= 0 & 0 >= 0 & 0 >= 0 & [bni_49] >= 0 & [(3)bni_49] >= 0 & 0 >= 0 & [(-1)Bound*bni_49] >= 0 & 0 >= 0 & 0 >= 0 & 0 >= 0 & [1] >= 0 & [1 + (-1)bso_50] >= 0) *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])), >=) & [bni_51] = 0 & 0 >= 0 & [(-1)bso_52] >= 0) *((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)bso_52] >= 0) *((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)bso_52] >= 0) *((U^Increasing(IF_3(split(x[9], ys[9]), x[9], ys[9])), >=) & [bni_51] = 0 & 0 >= 0 & [(-1)bso_52] >= 0) *((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)bso_52] >= 0) *((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)bso_52] >= 0) *((U^Increasing(IF_3(split(x[9], ys[9]), x[9], ys[9])), >=) & [bni_51] = 0 & 0 >= 0 & [(-1)bso_52] >= 0) *((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)bso_52] >= 0) *((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)bso_52] >= 0) *((U^Increasing(IF_3(split(x[9], ys[9]), x[9], ys[9])), >=) & [bni_51] = 0 & 0 >= 0 & [(-1)bso_52] >= 0) *((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)bso_52] >= 0) *((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)bso_52] >= 0) 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. Using the following integer polynomial ordering the resulting constraints can be solved Polynomial interpretation over integers with natural coefficients for non-tuple symbols [NONINF][POLO]: POL(TRUE) = 0 POL(FALSE) = 0 POL(split(x_1, x_2)) = [3]x_2 POL(e) = [1] POL(pair(x_1, x_2)) = [1] + x_2 + x_1 POL(ins(x_1, x_2)) = [3]x_2 POL(Cond_split(x_1, x_2, x_3)) = [3]x_3 POL(>(x_1, x_2)) = 0 POL(Cond_split1(x_1, x_2, x_3)) = [3]x_3 POL(>=(x_1, x_2)) = 0 POL(if_1(x_1, x_2, x_3, x_4)) = [3]x_1 POL(if_2(x_1, x_2, x_3, x_4)) = [3]x_1 POL(Cond_if_1(x_1, x_2, x_3, x_4, x_5)) = [3]x_2 POL(Cond_if_2(x_1, x_2, x_3, x_4, x_5)) = [3]x_2 POL(IF_3(x_1, x_2, x_3)) = [-1] + x_1 POL(QSORT(x_1)) = [-1] + x_1 The following pairs are in P_>: IF_3(pair(yl[13], yh[13]), x[13], ys[13]) -> QSORT(yh[13]) IF_3(pair(yl[12], yh[12]), x[12], ys[12]) -> QSORT(yl[12]) The following pairs are in P_bound: IF_3(pair(yl[13], yh[13]), x[13], ys[13]) -> QSORT(yh[13]) IF_3(pair(yl[12], yh[12]), x[12], ys[12]) -> QSORT(yl[12]) The following pairs are in P_>=: QSORT(ins(x[9], ys[9])) -> IF_3(split(x[9], ys[9]), x[9], ys[9]) At least the following rules have been oriented under context sensitive arithmetic replacement: split(x, e)^1 <-> pair(e, e)^1 split(x, ins(y, zs))^1 -> Cond_split(>(x, y), x, ins(y, zs))^1 split(x, ins(y, zs))^1 -> Cond_split1(>=(y, x), x, ins(y, zs))^1 Cond_split(TRUE, x, ins(y, zs))^1 <-> if_1(split(x, zs), x, y, zs)^1 Cond_split1(TRUE, x, ins(y, zs))^1 <-> if_2(split(x, zs), x, y, zs)^1 if_1(pair(zl, zh), x, y, zs)^1 <-> Cond_if_1(>(x, y), pair(zl, zh), x, y, zs)^1 if_2(pair(zl, zh), x, y, zs)^1 -> Cond_if_2(>=(y, x), pair(zl, zh), x, y, zs)^1 Cond_if_1(TRUE, pair(zl, zh), x, y, zs)^1 -> pair(ins(y, zl), zh)^1 Cond_if_2(TRUE, pair(zl, zh), x, y, zs)^1 -> pair(zl, ins(y, zh))^1 ---------------------------------------- (27) Obligation: IDP problem: The following function symbols are pre-defined: <<< & ~ Bwand: (Integer, Integer) -> Integer >= ~ Ge: (Integer, Integer) -> Boolean | ~ Bwor: (Integer, Integer) -> Integer / ~ Div: (Integer, Integer) -> Integer != ~ Neq: (Integer, Integer) -> Boolean && ~ Land: (Boolean, Boolean) -> Boolean ! ~ Lnot: (Boolean) -> Boolean = ~ Eq: (Integer, Integer) -> Boolean <= ~ Le: (Integer, Integer) -> Boolean ^ ~ Bwxor: (Integer, Integer) -> Integer % ~ Mod: (Integer, Integer) -> Integer > ~ Gt: (Integer, Integer) -> Boolean + ~ Add: (Integer, Integer) -> Integer -1 ~ UnaryMinus: (Integer) -> Integer < ~ Lt: (Integer, Integer) -> Boolean || ~ Lor: (Boolean, Boolean) -> Boolean - ~ Sub: (Integer, Integer) -> Integer ~ ~ Bwnot: (Integer) -> Integer * ~ Mul: (Integer, Integer) -> Integer >>> The following domains are used: Integer The ITRS R consists of the following rules: split(x, e) -> pair(e, e) split(x, ins(y, zs)) -> Cond_split(x > y, x, ins(y, zs)) split(x, ins(y, zs)) -> Cond_split1(y >= x, x, ins(y, zs)) Cond_split(TRUE, x, ins(y, zs)) -> if_1(split(x, zs), x, y, zs) Cond_split1(TRUE, x, ins(y, zs)) -> if_2(split(x, zs), x, y, zs) if_1(pair(zl, zh), x, y, zs) -> Cond_if_1(x > y, pair(zl, zh), x, y, zs) if_2(pair(zl, zh), x, y, zs) -> Cond_if_2(y >= x, pair(zl, zh), x, y, zs) Cond_if_1(TRUE, pair(zl, zh), x, y, zs) -> pair(ins(y, zl), zh) Cond_if_2(TRUE, pair(zl, zh), x, y, zs) -> pair(zl, ins(y, zh)) The integer pair graph contains the following rules and edges: (9): QSORT(ins(x[9], ys[9])) -> IF_3(split(x[9], ys[9]), x[9], ys[9]) The set Q consists of the following terms: app(nil, x0) app(cons(x0, x1), x2) split(x0, e) split(x0, ins(x1, x2)) Cond_split(TRUE, x0, ins(x1, x2)) if_1(pair(x0, x1), x2, x3, x4) Cond_if_1(TRUE, pair(x0, x1), x2, x3, x4) Cond_split1(TRUE, x0, ins(x1, x2)) if_2(pair(x0, x1), x2, x3, x4) Cond_if_2(TRUE, pair(x0, x1), x2, x3, x4) qsort(e) qsort(ins(x0, x1)) if_3(pair(x0, x1), x2, x3) ---------------------------------------- (28) IDependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 0 SCCs with 1 less node. ---------------------------------------- (29) TRUE