/export/starexec/sandbox/solver/bin/starexec_run_standard /export/starexec/sandbox/benchmark/theBenchmark.itrs /export/starexec/sandbox/output/output_files -------------------------------------------------------------------------------- YES proof of /export/starexec/sandbox/benchmark/theBenchmark.itrs # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty Termination of the given ITRS could be proven: (0) ITRS (1) ITRStoIDPProof [EQUIVALENT, 0 ms] (2) IDP (3) UsableRulesProof [EQUIVALENT, 0 ms] (4) IDP (5) IDependencyGraphProof [EQUIVALENT, 0 ms] (6) AND (7) IDP (8) IDPNonInfProof [SOUND, 141 ms] (9) IDP (10) PisEmptyProof [EQUIVALENT, 0 ms] (11) YES (12) IDP (13) IDPNonInfProof [SOUND, 55 ms] (14) IDP (15) IDependencyGraphProof [EQUIVALENT, 0 ms] (16) TRUE ---------------------------------------- (0) Obligation: ITRS problem: The following function symbols are pre-defined: <<< & ~ Bwand: (Integer, Integer) -> Integer >= ~ Ge: (Integer, Integer) -> Boolean / ~ Div: (Integer, Integer) -> Integer | ~ Bwor: (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: lastbit(0) -> 0 lastbit(1) -> 1 lastbit(x) -> Cond_lastbit(x > 1, x) Cond_lastbit(TRUE, x) -> lastbit(x - 2) conv(0) -> cons(nil, 0) conv(x) -> Cond_conv(x > 0, x) Cond_conv(TRUE, x) -> cons(conv(x / 2), lastbit(x)) The set Q consists of the following terms: lastbit(x0) Cond_lastbit(TRUE, x0) conv(x0) Cond_conv(TRUE, x0) ---------------------------------------- (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 / ~ Div: (Integer, Integer) -> Integer | ~ Bwor: (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: lastbit(0) -> 0 lastbit(1) -> 1 lastbit(x) -> Cond_lastbit(x > 1, x) Cond_lastbit(TRUE, x) -> lastbit(x - 2) conv(0) -> cons(nil, 0) conv(x) -> Cond_conv(x > 0, x) Cond_conv(TRUE, x) -> cons(conv(x / 2), lastbit(x)) The integer pair graph contains the following rules and edges: (0): LASTBIT(x[0]) -> COND_LASTBIT(x[0] > 1, x[0]) (1): COND_LASTBIT(TRUE, x[1]) -> LASTBIT(x[1] - 2) (2): CONV(x[2]) -> COND_CONV(x[2] > 0, x[2]) (3): COND_CONV(TRUE, x[3]) -> CONV(x[3] / 2) (4): COND_CONV(TRUE, x[4]) -> LASTBIT(x[4]) (0) -> (1), if (x[0] > 1 & x[0] ->^* x[1]) (1) -> (0), if (x[1] - 2 ->^* x[0]) (2) -> (3), if (x[2] > 0 & x[2] ->^* x[3]) (2) -> (4), if (x[2] > 0 & x[2] ->^* x[4]) (3) -> (2), if (x[3] / 2 ->^* x[2]) (4) -> (0), if (x[4] ->^* x[0]) The set Q consists of the following terms: lastbit(x0) Cond_lastbit(TRUE, x0) conv(x0) Cond_conv(TRUE, x0) ---------------------------------------- (3) UsableRulesProof (EQUIVALENT) As all Q-normal forms are R-normal forms we are in the innermost case. Hence, by the usable rules processor [LPAR04] we can delete all non-usable rules [FROCOS05] from R. ---------------------------------------- (4) Obligation: IDP problem: The following function symbols are pre-defined: <<< & ~ Bwand: (Integer, Integer) -> Integer >= ~ Ge: (Integer, Integer) -> Boolean / ~ Div: (Integer, Integer) -> Integer | ~ Bwor: (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: (0): LASTBIT(x[0]) -> COND_LASTBIT(x[0] > 1, x[0]) (1): COND_LASTBIT(TRUE, x[1]) -> LASTBIT(x[1] - 2) (2): CONV(x[2]) -> COND_CONV(x[2] > 0, x[2]) (3): COND_CONV(TRUE, x[3]) -> CONV(x[3] / 2) (4): COND_CONV(TRUE, x[4]) -> LASTBIT(x[4]) (0) -> (1), if (x[0] > 1 & x[0] ->^* x[1]) (1) -> (0), if (x[1] - 2 ->^* x[0]) (2) -> (3), if (x[2] > 0 & x[2] ->^* x[3]) (2) -> (4), if (x[2] > 0 & x[2] ->^* x[4]) (3) -> (2), if (x[3] / 2 ->^* x[2]) (4) -> (0), if (x[4] ->^* x[0]) The set Q consists of the following terms: lastbit(x0) Cond_lastbit(TRUE, x0) conv(x0) Cond_conv(TRUE, x0) ---------------------------------------- (5) IDependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 2 SCCs with 1 less node. ---------------------------------------- (6) Complex Obligation (AND) ---------------------------------------- (7) Obligation: IDP problem: The following function symbols are pre-defined: <<< & ~ Bwand: (Integer, Integer) -> Integer >= ~ Ge: (Integer, Integer) -> Boolean / ~ Div: (Integer, Integer) -> Integer | ~ Bwor: (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: (1): COND_LASTBIT(TRUE, x[1]) -> LASTBIT(x[1] - 2) (0): LASTBIT(x[0]) -> COND_LASTBIT(x[0] > 1, x[0]) (1) -> (0), if (x[1] - 2 ->^* x[0]) (0) -> (1), if (x[0] > 1 & x[0] ->^* x[1]) The set Q consists of the following terms: lastbit(x0) Cond_lastbit(TRUE, x0) conv(x0) Cond_conv(TRUE, x0) ---------------------------------------- (8) IDPNonInfProof (SOUND) Used the following options for this NonInfProof: IDPGPoloSolver: Range: [(-1,2)] IsNat: false Interpretation Shape Heuristic: aprove.DPFramework.IDPProblem.Processors.nonInf.poly.IdpDefaultShapeHeuristic@531d3daa 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_LASTBIT(TRUE, x[1]) -> LASTBIT(-(x[1], 2)) the following chains were created: *We consider the chain LASTBIT(x[0]) -> COND_LASTBIT(>(x[0], 1), x[0]), COND_LASTBIT(TRUE, x[1]) -> LASTBIT(-(x[1], 2)), LASTBIT(x[0]) -> COND_LASTBIT(>(x[0], 1), x[0]) which results in the following constraint: (1) (>(x[0], 1)=TRUE & x[0]=x[1] & -(x[1], 2)=x[0]1 ==> COND_LASTBIT(TRUE, x[1])_>=_NonInfC & COND_LASTBIT(TRUE, x[1])_>=_LASTBIT(-(x[1], 2)) & (U^Increasing(LASTBIT(-(x[1], 2))), >=)) We simplified constraint (1) using rules (III), (IV) which results in the following new constraint: (2) (>(x[0], 1)=TRUE ==> COND_LASTBIT(TRUE, x[0])_>=_NonInfC & COND_LASTBIT(TRUE, x[0])_>=_LASTBIT(-(x[0], 2)) & (U^Increasing(LASTBIT(-(x[1], 2))), >=)) We simplified constraint (2) using rule (POLY_CONSTRAINTS) which results in the following new constraint: (3) (x[0] + [-2] >= 0 ==> (U^Increasing(LASTBIT(-(x[1], 2))), >=) & [(-1)bni_9 + (-1)Bound*bni_9] + [(2)bni_9]x[0] >= 0 & [1 + (-1)bso_10] >= 0) We simplified constraint (3) using rule (IDP_POLY_SIMPLIFY) which results in the following new constraint: (4) (x[0] + [-2] >= 0 ==> (U^Increasing(LASTBIT(-(x[1], 2))), >=) & [(-1)bni_9 + (-1)Bound*bni_9] + [(2)bni_9]x[0] >= 0 & [1 + (-1)bso_10] >= 0) We simplified constraint (4) using rule (POLY_REMOVE_MIN_MAX) which results in the following new constraint: (5) (x[0] + [-2] >= 0 ==> (U^Increasing(LASTBIT(-(x[1], 2))), >=) & [(-1)bni_9 + (-1)Bound*bni_9] + [(2)bni_9]x[0] >= 0 & [1 + (-1)bso_10] >= 0) For Pair LASTBIT(x[0]) -> COND_LASTBIT(>(x[0], 1), x[0]) the following chains were created: *We consider the chain LASTBIT(x[0]) -> COND_LASTBIT(>(x[0], 1), x[0]), COND_LASTBIT(TRUE, x[1]) -> LASTBIT(-(x[1], 2)) which results in the following constraint: (1) (>(x[0], 1)=TRUE & x[0]=x[1] ==> LASTBIT(x[0])_>=_NonInfC & LASTBIT(x[0])_>=_COND_LASTBIT(>(x[0], 1), x[0]) & (U^Increasing(COND_LASTBIT(>(x[0], 1), x[0])), >=)) We simplified constraint (1) using rule (IV) which results in the following new constraint: (2) (>(x[0], 1)=TRUE ==> LASTBIT(x[0])_>=_NonInfC & LASTBIT(x[0])_>=_COND_LASTBIT(>(x[0], 1), x[0]) & (U^Increasing(COND_LASTBIT(>(x[0], 1), x[0])), >=)) We simplified constraint (2) using rule (POLY_CONSTRAINTS) which results in the following new constraint: (3) (x[0] + [-2] >= 0 ==> (U^Increasing(COND_LASTBIT(>(x[0], 1), x[0])), >=) & [(2)bni_11 + (-1)Bound*bni_11] + [(2)bni_11]x[0] >= 0 & [3 + (-1)bso_12] >= 0) We simplified constraint (3) using rule (IDP_POLY_SIMPLIFY) which results in the following new constraint: (4) (x[0] + [-2] >= 0 ==> (U^Increasing(COND_LASTBIT(>(x[0], 1), x[0])), >=) & [(2)bni_11 + (-1)Bound*bni_11] + [(2)bni_11]x[0] >= 0 & [3 + (-1)bso_12] >= 0) We simplified constraint (4) using rule (POLY_REMOVE_MIN_MAX) which results in the following new constraint: (5) (x[0] + [-2] >= 0 ==> (U^Increasing(COND_LASTBIT(>(x[0], 1), x[0])), >=) & [(2)bni_11 + (-1)Bound*bni_11] + [(2)bni_11]x[0] >= 0 & [3 + (-1)bso_12] >= 0) To summarize, we get the following constraints P__>=_ for the following pairs. *COND_LASTBIT(TRUE, x[1]) -> LASTBIT(-(x[1], 2)) *(x[0] + [-2] >= 0 ==> (U^Increasing(LASTBIT(-(x[1], 2))), >=) & [(-1)bni_9 + (-1)Bound*bni_9] + [(2)bni_9]x[0] >= 0 & [1 + (-1)bso_10] >= 0) *LASTBIT(x[0]) -> COND_LASTBIT(>(x[0], 1), x[0]) *(x[0] + [-2] >= 0 ==> (U^Increasing(COND_LASTBIT(>(x[0], 1), x[0])), >=) & [(2)bni_11 + (-1)Bound*bni_11] + [(2)bni_11]x[0] >= 0 & [3 + (-1)bso_12] >= 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[POLO]: POL(TRUE) = [3] POL(FALSE) = 0 POL(COND_LASTBIT(x_1, x_2)) = [-1] + [2]x_2 POL(LASTBIT(x_1)) = [2] + [2]x_1 POL(-(x_1, x_2)) = x_1 + [-1]x_2 POL(2) = [2] POL(>(x_1, x_2)) = [-1] POL(1) = [1] The following pairs are in P_>: COND_LASTBIT(TRUE, x[1]) -> LASTBIT(-(x[1], 2)) LASTBIT(x[0]) -> COND_LASTBIT(>(x[0], 1), x[0]) The following pairs are in P_bound: COND_LASTBIT(TRUE, x[1]) -> LASTBIT(-(x[1], 2)) LASTBIT(x[0]) -> COND_LASTBIT(>(x[0], 1), x[0]) The following pairs are in P_>=: none There are no usable rules. ---------------------------------------- (9) Obligation: IDP problem: The following function symbols are pre-defined: <<< & ~ Bwand: (Integer, Integer) -> Integer >= ~ Ge: (Integer, Integer) -> Boolean / ~ Div: (Integer, Integer) -> Integer | ~ Bwor: (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: lastbit(x0) Cond_lastbit(TRUE, x0) conv(x0) Cond_conv(TRUE, x0) ---------------------------------------- (10) PisEmptyProof (EQUIVALENT) The TRS P is empty. Hence, there is no (P,Q,R) chain. ---------------------------------------- (11) YES ---------------------------------------- (12) Obligation: IDP problem: The following function symbols are pre-defined: <<< & ~ Bwand: (Integer, Integer) -> Integer >= ~ Ge: (Integer, Integer) -> Boolean / ~ Div: (Integer, Integer) -> Integer | ~ Bwor: (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: (3): COND_CONV(TRUE, x[3]) -> CONV(x[3] / 2) (2): CONV(x[2]) -> COND_CONV(x[2] > 0, x[2]) (3) -> (2), if (x[3] / 2 ->^* x[2]) (2) -> (3), if (x[2] > 0 & x[2] ->^* x[3]) The set Q consists of the following terms: lastbit(x0) Cond_lastbit(TRUE, x0) conv(x0) Cond_conv(TRUE, x0) ---------------------------------------- (13) IDPNonInfProof (SOUND) Used the following options for this NonInfProof: IDPGPoloSolver: Range: [(-1,2)] IsNat: false Interpretation Shape Heuristic: aprove.DPFramework.IDPProblem.Processors.nonInf.poly.IdpDefaultShapeHeuristic@531d3daa 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_CONV(TRUE, x[3]) -> CONV(/(x[3], 2)) the following chains were created: *We consider the chain CONV(x[2]) -> COND_CONV(>(x[2], 0), x[2]), COND_CONV(TRUE, x[3]) -> CONV(/(x[3], 2)), CONV(x[2]) -> COND_CONV(>(x[2], 0), x[2]) which results in the following constraint: (1) (>(x[2], 0)=TRUE & x[2]=x[3] & /(x[3], 2)=x[2]1 ==> COND_CONV(TRUE, x[3])_>=_NonInfC & COND_CONV(TRUE, x[3])_>=_CONV(/(x[3], 2)) & (U^Increasing(CONV(/(x[3], 2))), >=)) We simplified constraint (1) using rules (III), (IV) which results in the following new constraint: (2) (>(x[2], 0)=TRUE ==> COND_CONV(TRUE, x[2])_>=_NonInfC & COND_CONV(TRUE, x[2])_>=_CONV(/(x[2], 2)) & (U^Increasing(CONV(/(x[3], 2))), >=)) We simplified constraint (2) using rule (POLY_CONSTRAINTS) which results in the following new constraint: (3) (x[2] + [-1] >= 0 ==> (U^Increasing(CONV(/(x[3], 2))), >=) & [(-1)bni_9 + (-1)Bound*bni_9] + [bni_9]x[2] >= 0 & [1 + (-1)bso_13] + x[2] + [-1]max{x[2], [-1]x[2]} >= 0) We simplified constraint (3) using rule (IDP_POLY_SIMPLIFY) which results in the following new constraint: (4) (x[2] + [-1] >= 0 ==> (U^Increasing(CONV(/(x[3], 2))), >=) & [(-1)bni_9 + (-1)Bound*bni_9] + [bni_9]x[2] >= 0 & [1 + (-1)bso_13] + x[2] + [-1]max{x[2], [-1]x[2]} >= 0) We simplified constraint (4) using rule (POLY_REMOVE_MIN_MAX) which results in the following new constraint: (5) (x[2] + [-1] >= 0 & [2]x[2] >= 0 ==> (U^Increasing(CONV(/(x[3], 2))), >=) & [(-1)bni_9 + (-1)Bound*bni_9] + [bni_9]x[2] >= 0 & [1 + (-1)bso_13] >= 0) We simplified constraint (5) using rule (IDP_POLY_GCD) which results in the following new constraint: (6) (x[2] + [-1] >= 0 & x[2] >= 0 ==> (U^Increasing(CONV(/(x[3], 2))), >=) & [(-1)bni_9 + (-1)Bound*bni_9] + [bni_9]x[2] >= 0 & [1 + (-1)bso_13] >= 0) For Pair CONV(x[2]) -> COND_CONV(>(x[2], 0), x[2]) the following chains were created: *We consider the chain CONV(x[2]) -> COND_CONV(>(x[2], 0), x[2]), COND_CONV(TRUE, x[3]) -> CONV(/(x[3], 2)) which results in the following constraint: (1) (>(x[2], 0)=TRUE & x[2]=x[3] ==> CONV(x[2])_>=_NonInfC & CONV(x[2])_>=_COND_CONV(>(x[2], 0), x[2]) & (U^Increasing(COND_CONV(>(x[2], 0), x[2])), >=)) We simplified constraint (1) using rule (IV) which results in the following new constraint: (2) (>(x[2], 0)=TRUE ==> CONV(x[2])_>=_NonInfC & CONV(x[2])_>=_COND_CONV(>(x[2], 0), x[2]) & (U^Increasing(COND_CONV(>(x[2], 0), x[2])), >=)) We simplified constraint (2) using rule (POLY_CONSTRAINTS) which results in the following new constraint: (3) (x[2] + [-1] >= 0 ==> (U^Increasing(COND_CONV(>(x[2], 0), x[2])), >=) & [(-1)bni_14 + (-1)Bound*bni_14] + [bni_14]x[2] >= 0 & [(-1)bso_15] >= 0) We simplified constraint (3) using rule (IDP_POLY_SIMPLIFY) which results in the following new constraint: (4) (x[2] + [-1] >= 0 ==> (U^Increasing(COND_CONV(>(x[2], 0), x[2])), >=) & [(-1)bni_14 + (-1)Bound*bni_14] + [bni_14]x[2] >= 0 & [(-1)bso_15] >= 0) We simplified constraint (4) using rule (POLY_REMOVE_MIN_MAX) which results in the following new constraint: (5) (x[2] + [-1] >= 0 ==> (U^Increasing(COND_CONV(>(x[2], 0), x[2])), >=) & [(-1)bni_14 + (-1)Bound*bni_14] + [bni_14]x[2] >= 0 & [(-1)bso_15] >= 0) To summarize, we get the following constraints P__>=_ for the following pairs. *COND_CONV(TRUE, x[3]) -> CONV(/(x[3], 2)) *(x[2] + [-1] >= 0 & x[2] >= 0 ==> (U^Increasing(CONV(/(x[3], 2))), >=) & [(-1)bni_9 + (-1)Bound*bni_9] + [bni_9]x[2] >= 0 & [1 + (-1)bso_13] >= 0) *CONV(x[2]) -> COND_CONV(>(x[2], 0), x[2]) *(x[2] + [-1] >= 0 ==> (U^Increasing(COND_CONV(>(x[2], 0), x[2])), >=) & [(-1)bni_14 + (-1)Bound*bni_14] + [bni_14]x[2] >= 0 & [(-1)bso_15] >= 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[POLO]: POL(TRUE) = 0 POL(FALSE) = 0 POL(COND_CONV(x_1, x_2)) = [-1] + x_2 POL(CONV(x_1)) = [-1] + x_1 POL(2) = [2] POL(>(x_1, x_2)) = [-1] POL(0) = 0 Polynomial Interpretations with Context Sensitive Arithemetic Replacement POL(Term^CSAR-Mode @ Context) POL(/(x_1, 2)^1 @ {CONV_1/0}) = max{x_1, [-1]x_1} + [-1] The following pairs are in P_>: COND_CONV(TRUE, x[3]) -> CONV(/(x[3], 2)) The following pairs are in P_bound: COND_CONV(TRUE, x[3]) -> CONV(/(x[3], 2)) CONV(x[2]) -> COND_CONV(>(x[2], 0), x[2]) The following pairs are in P_>=: CONV(x[2]) -> COND_CONV(>(x[2], 0), x[2]) At least the following rules have been oriented under context sensitive arithmetic replacement: /^1 -> ---------------------------------------- (14) Obligation: IDP problem: The following function symbols are pre-defined: <<< & ~ Bwand: (Integer, Integer) -> Integer >= ~ Ge: (Integer, Integer) -> Boolean / ~ Div: (Integer, Integer) -> Integer | ~ Bwor: (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: (2): CONV(x[2]) -> COND_CONV(x[2] > 0, x[2]) The set Q consists of the following terms: lastbit(x0) Cond_lastbit(TRUE, x0) conv(x0) Cond_conv(TRUE, x0) ---------------------------------------- (15) IDependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 0 SCCs with 1 less node. ---------------------------------------- (16) TRUE