4.47/2.09 YES 4.55/2.11 proof of /export/starexec/sandbox/benchmark/theBenchmark.itrs 4.55/2.11 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 4.55/2.11 4.55/2.11 4.55/2.11 Termination of the given ITRS could be proven: 4.55/2.11 4.55/2.11 (0) ITRS 4.55/2.11 (1) ITRStoIDPProof [EQUIVALENT, 0 ms] 4.55/2.11 (2) IDP 4.55/2.11 (3) UsableRulesProof [EQUIVALENT, 0 ms] 4.55/2.11 (4) IDP 4.55/2.11 (5) IDependencyGraphProof [EQUIVALENT, 0 ms] 4.55/2.11 (6) IDP 4.55/2.11 (7) IDPNonInfProof [SOUND, 211 ms] 4.55/2.11 (8) IDP 4.55/2.11 (9) IDependencyGraphProof [EQUIVALENT, 0 ms] 4.55/2.11 (10) TRUE 4.55/2.11 4.55/2.11 4.55/2.11 ---------------------------------------- 4.55/2.11 4.55/2.11 (0) 4.55/2.11 Obligation: 4.55/2.11 ITRS problem: 4.55/2.11 4.55/2.11 The following function symbols are pre-defined: 4.55/2.11 <<< 4.55/2.11 & ~ Bwand: (Integer, Integer) -> Integer 4.55/2.11 >= ~ Ge: (Integer, Integer) -> Boolean 4.55/2.11 | ~ Bwor: (Integer, Integer) -> Integer 4.55/2.11 / ~ Div: (Integer, Integer) -> Integer 4.55/2.11 != ~ Neq: (Integer, Integer) -> Boolean 4.55/2.11 && ~ Land: (Boolean, Boolean) -> Boolean 4.55/2.11 ! ~ Lnot: (Boolean) -> Boolean 4.55/2.11 = ~ Eq: (Integer, Integer) -> Boolean 4.55/2.11 <= ~ Le: (Integer, Integer) -> Boolean 4.55/2.11 ^ ~ Bwxor: (Integer, Integer) -> Integer 4.55/2.11 % ~ Mod: (Integer, Integer) -> Integer 4.55/2.11 + ~ Add: (Integer, Integer) -> Integer 4.55/2.11 > ~ Gt: (Integer, Integer) -> Boolean 4.55/2.11 -1 ~ UnaryMinus: (Integer) -> Integer 4.55/2.11 < ~ Lt: (Integer, Integer) -> Boolean 4.55/2.11 || ~ Lor: (Boolean, Boolean) -> Boolean 4.55/2.11 - ~ Sub: (Integer, Integer) -> Integer 4.55/2.11 ~ ~ Bwnot: (Integer) -> Integer 4.55/2.11 * ~ Mul: (Integer, Integer) -> Integer 4.55/2.11 >>> 4.55/2.11 4.55/2.11 The TRS R consists of the following rules: 4.55/2.11 div(x, y) -> divNat(x >= 0 && y >= 1, x, y) 4.55/2.11 divNat(TRUE, x, y) -> d(x, y, 0) 4.55/2.11 d(x, y, z) -> dNat(x >= 0 && y >= 1 && z >= 0, x, y, z) 4.55/2.11 dNat(TRUE, x, y, z) -> cond(x >= z, x, y - 1, z) 4.55/2.11 cond(TRUE, x, y, z) -> 1 + d(x, y + 1, y + 1 + z) 4.55/2.11 cond(FALSE, x, y, z) -> 0 4.55/2.11 The set Q consists of the following terms: 4.55/2.11 div(x0, x1) 4.55/2.11 divNat(TRUE, x0, x1) 4.55/2.11 d(x0, x1, x2) 4.55/2.11 dNat(TRUE, x0, x1, x2) 4.55/2.11 cond(TRUE, x0, x1, x2) 4.55/2.11 cond(FALSE, x0, x1, x2) 4.55/2.11 4.55/2.11 ---------------------------------------- 4.55/2.11 4.55/2.11 (1) ITRStoIDPProof (EQUIVALENT) 4.55/2.11 Added dependency pairs 4.55/2.11 ---------------------------------------- 4.55/2.11 4.55/2.11 (2) 4.55/2.11 Obligation: 4.55/2.11 IDP problem: 4.55/2.11 The following function symbols are pre-defined: 4.55/2.11 <<< 4.55/2.11 & ~ Bwand: (Integer, Integer) -> Integer 4.55/2.11 >= ~ Ge: (Integer, Integer) -> Boolean 4.55/2.11 | ~ Bwor: (Integer, Integer) -> Integer 4.55/2.11 / ~ Div: (Integer, Integer) -> Integer 4.55/2.11 != ~ Neq: (Integer, Integer) -> Boolean 4.55/2.11 && ~ Land: (Boolean, Boolean) -> Boolean 4.55/2.11 ! ~ Lnot: (Boolean) -> Boolean 4.55/2.11 = ~ Eq: (Integer, Integer) -> Boolean 4.55/2.11 <= ~ Le: (Integer, Integer) -> Boolean 4.55/2.11 ^ ~ Bwxor: (Integer, Integer) -> Integer 4.55/2.11 % ~ Mod: (Integer, Integer) -> Integer 4.55/2.11 + ~ Add: (Integer, Integer) -> Integer 4.55/2.11 > ~ Gt: (Integer, Integer) -> Boolean 4.55/2.11 -1 ~ UnaryMinus: (Integer) -> Integer 4.55/2.11 < ~ Lt: (Integer, Integer) -> Boolean 4.55/2.11 || ~ Lor: (Boolean, Boolean) -> Boolean 4.55/2.11 - ~ Sub: (Integer, Integer) -> Integer 4.55/2.11 ~ ~ Bwnot: (Integer) -> Integer 4.55/2.11 * ~ Mul: (Integer, Integer) -> Integer 4.55/2.11 >>> 4.55/2.11 4.55/2.11 4.55/2.11 The following domains are used: 4.55/2.11 Boolean, Integer 4.55/2.11 4.55/2.11 The ITRS R consists of the following rules: 4.55/2.11 div(x, y) -> divNat(x >= 0 && y >= 1, x, y) 4.55/2.11 divNat(TRUE, x, y) -> d(x, y, 0) 4.55/2.11 d(x, y, z) -> dNat(x >= 0 && y >= 1 && z >= 0, x, y, z) 4.55/2.11 dNat(TRUE, x, y, z) -> cond(x >= z, x, y - 1, z) 4.55/2.11 cond(TRUE, x, y, z) -> 1 + d(x, y + 1, y + 1 + z) 4.55/2.11 cond(FALSE, x, y, z) -> 0 4.55/2.11 4.55/2.11 The integer pair graph contains the following rules and edges: 4.55/2.11 (0): DIV(x[0], y[0]) -> DIVNAT(x[0] >= 0 && y[0] >= 1, x[0], y[0]) 4.55/2.11 (1): DIVNAT(TRUE, x[1], y[1]) -> D(x[1], y[1], 0) 4.55/2.11 (2): D(x[2], y[2], z[2]) -> DNAT(x[2] >= 0 && y[2] >= 1 && z[2] >= 0, x[2], y[2], z[2]) 4.55/2.11 (3): DNAT(TRUE, x[3], y[3], z[3]) -> COND(x[3] >= z[3], x[3], y[3] - 1, z[3]) 4.55/2.11 (4): COND(TRUE, x[4], y[4], z[4]) -> D(x[4], y[4] + 1, y[4] + 1 + z[4]) 4.55/2.11 4.55/2.11 (0) -> (1), if (x[0] >= 0 && y[0] >= 1 & x[0] ->^* x[1] & y[0] ->^* y[1]) 4.55/2.11 (1) -> (2), if (x[1] ->^* x[2] & y[1] ->^* y[2] & 0 ->^* z[2]) 4.55/2.11 (2) -> (3), if (x[2] >= 0 && y[2] >= 1 && z[2] >= 0 & x[2] ->^* x[3] & y[2] ->^* y[3] & z[2] ->^* z[3]) 4.55/2.11 (3) -> (4), if (x[3] >= z[3] & x[3] ->^* x[4] & y[3] - 1 ->^* y[4] & z[3] ->^* z[4]) 4.55/2.11 (4) -> (2), if (x[4] ->^* x[2] & y[4] + 1 ->^* y[2] & y[4] + 1 + z[4] ->^* z[2]) 4.55/2.11 4.55/2.11 The set Q consists of the following terms: 4.55/2.11 div(x0, x1) 4.55/2.11 divNat(TRUE, x0, x1) 4.55/2.11 d(x0, x1, x2) 4.55/2.11 dNat(TRUE, x0, x1, x2) 4.55/2.11 cond(TRUE, x0, x1, x2) 4.55/2.11 cond(FALSE, x0, x1, x2) 4.55/2.11 4.55/2.11 ---------------------------------------- 4.55/2.11 4.55/2.11 (3) UsableRulesProof (EQUIVALENT) 4.55/2.11 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.55/2.11 ---------------------------------------- 4.55/2.11 4.55/2.11 (4) 4.55/2.11 Obligation: 4.55/2.11 IDP problem: 4.55/2.11 The following function symbols are pre-defined: 4.55/2.11 <<< 4.55/2.11 & ~ Bwand: (Integer, Integer) -> Integer 4.55/2.11 >= ~ Ge: (Integer, Integer) -> Boolean 4.55/2.11 | ~ Bwor: (Integer, Integer) -> Integer 4.55/2.11 / ~ Div: (Integer, Integer) -> Integer 4.55/2.11 != ~ Neq: (Integer, Integer) -> Boolean 4.55/2.11 && ~ Land: (Boolean, Boolean) -> Boolean 4.55/2.11 ! ~ Lnot: (Boolean) -> Boolean 4.55/2.11 = ~ Eq: (Integer, Integer) -> Boolean 4.55/2.11 <= ~ Le: (Integer, Integer) -> Boolean 4.55/2.11 ^ ~ Bwxor: (Integer, Integer) -> Integer 4.55/2.11 % ~ Mod: (Integer, Integer) -> Integer 4.55/2.11 + ~ Add: (Integer, Integer) -> Integer 4.55/2.11 > ~ Gt: (Integer, Integer) -> Boolean 4.55/2.11 -1 ~ UnaryMinus: (Integer) -> Integer 4.55/2.11 < ~ Lt: (Integer, Integer) -> Boolean 4.55/2.11 || ~ Lor: (Boolean, Boolean) -> Boolean 4.55/2.11 - ~ Sub: (Integer, Integer) -> Integer 4.55/2.11 ~ ~ Bwnot: (Integer) -> Integer 4.55/2.11 * ~ Mul: (Integer, Integer) -> Integer 4.55/2.11 >>> 4.55/2.11 4.55/2.11 4.55/2.11 The following domains are used: 4.55/2.11 Boolean, Integer 4.55/2.11 4.55/2.11 R is empty. 4.55/2.11 4.55/2.11 The integer pair graph contains the following rules and edges: 4.55/2.11 (0): DIV(x[0], y[0]) -> DIVNAT(x[0] >= 0 && y[0] >= 1, x[0], y[0]) 4.55/2.11 (1): DIVNAT(TRUE, x[1], y[1]) -> D(x[1], y[1], 0) 4.55/2.11 (2): D(x[2], y[2], z[2]) -> DNAT(x[2] >= 0 && y[2] >= 1 && z[2] >= 0, x[2], y[2], z[2]) 4.55/2.11 (3): DNAT(TRUE, x[3], y[3], z[3]) -> COND(x[3] >= z[3], x[3], y[3] - 1, z[3]) 4.55/2.11 (4): COND(TRUE, x[4], y[4], z[4]) -> D(x[4], y[4] + 1, y[4] + 1 + z[4]) 4.55/2.11 4.55/2.11 (0) -> (1), if (x[0] >= 0 && y[0] >= 1 & x[0] ->^* x[1] & y[0] ->^* y[1]) 4.55/2.11 (1) -> (2), if (x[1] ->^* x[2] & y[1] ->^* y[2] & 0 ->^* z[2]) 4.55/2.11 (2) -> (3), if (x[2] >= 0 && y[2] >= 1 && z[2] >= 0 & x[2] ->^* x[3] & y[2] ->^* y[3] & z[2] ->^* z[3]) 4.55/2.11 (3) -> (4), if (x[3] >= z[3] & x[3] ->^* x[4] & y[3] - 1 ->^* y[4] & z[3] ->^* z[4]) 4.55/2.11 (4) -> (2), if (x[4] ->^* x[2] & y[4] + 1 ->^* y[2] & y[4] + 1 + z[4] ->^* z[2]) 4.55/2.11 4.55/2.11 The set Q consists of the following terms: 4.55/2.11 div(x0, x1) 4.55/2.11 divNat(TRUE, x0, x1) 4.55/2.11 d(x0, x1, x2) 4.55/2.11 dNat(TRUE, x0, x1, x2) 4.55/2.11 cond(TRUE, x0, x1, x2) 4.55/2.11 cond(FALSE, x0, x1, x2) 4.55/2.11 4.55/2.11 ---------------------------------------- 4.55/2.11 4.55/2.11 (5) IDependencyGraphProof (EQUIVALENT) 4.55/2.11 The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 2 less nodes. 4.55/2.11 ---------------------------------------- 4.55/2.11 4.55/2.11 (6) 4.55/2.11 Obligation: 4.55/2.11 IDP problem: 4.55/2.11 The following function symbols are pre-defined: 4.55/2.11 <<< 4.55/2.11 & ~ Bwand: (Integer, Integer) -> Integer 4.55/2.11 >= ~ Ge: (Integer, Integer) -> Boolean 4.55/2.11 | ~ Bwor: (Integer, Integer) -> Integer 4.55/2.11 / ~ Div: (Integer, Integer) -> Integer 4.55/2.11 != ~ Neq: (Integer, Integer) -> Boolean 4.55/2.11 && ~ Land: (Boolean, Boolean) -> Boolean 4.55/2.11 ! ~ Lnot: (Boolean) -> Boolean 4.55/2.11 = ~ Eq: (Integer, Integer) -> Boolean 4.55/2.11 <= ~ Le: (Integer, Integer) -> Boolean 4.55/2.11 ^ ~ Bwxor: (Integer, Integer) -> Integer 4.55/2.11 % ~ Mod: (Integer, Integer) -> Integer 4.55/2.11 + ~ Add: (Integer, Integer) -> Integer 4.55/2.11 > ~ Gt: (Integer, Integer) -> Boolean 4.55/2.11 -1 ~ UnaryMinus: (Integer) -> Integer 4.55/2.11 < ~ Lt: (Integer, Integer) -> Boolean 4.55/2.11 || ~ Lor: (Boolean, Boolean) -> Boolean 4.55/2.11 - ~ Sub: (Integer, Integer) -> Integer 4.55/2.11 ~ ~ Bwnot: (Integer) -> Integer 4.55/2.11 * ~ Mul: (Integer, Integer) -> Integer 4.55/2.11 >>> 4.55/2.11 4.55/2.11 4.55/2.11 The following domains are used: 4.55/2.11 Integer, Boolean 4.55/2.11 4.55/2.11 R is empty. 4.55/2.11 4.55/2.11 The integer pair graph contains the following rules and edges: 4.55/2.11 (4): COND(TRUE, x[4], y[4], z[4]) -> D(x[4], y[4] + 1, y[4] + 1 + z[4]) 4.55/2.11 (3): DNAT(TRUE, x[3], y[3], z[3]) -> COND(x[3] >= z[3], x[3], y[3] - 1, z[3]) 4.55/2.11 (2): D(x[2], y[2], z[2]) -> DNAT(x[2] >= 0 && y[2] >= 1 && z[2] >= 0, x[2], y[2], z[2]) 4.55/2.11 4.55/2.11 (4) -> (2), if (x[4] ->^* x[2] & y[4] + 1 ->^* y[2] & y[4] + 1 + z[4] ->^* z[2]) 4.55/2.11 (2) -> (3), if (x[2] >= 0 && y[2] >= 1 && z[2] >= 0 & x[2] ->^* x[3] & y[2] ->^* y[3] & z[2] ->^* z[3]) 4.55/2.11 (3) -> (4), if (x[3] >= z[3] & x[3] ->^* x[4] & y[3] - 1 ->^* y[4] & z[3] ->^* z[4]) 4.55/2.11 4.55/2.11 The set Q consists of the following terms: 4.55/2.11 div(x0, x1) 4.55/2.11 divNat(TRUE, x0, x1) 4.55/2.11 d(x0, x1, x2) 4.55/2.11 dNat(TRUE, x0, x1, x2) 4.55/2.11 cond(TRUE, x0, x1, x2) 4.55/2.11 cond(FALSE, x0, x1, x2) 4.55/2.11 4.55/2.11 ---------------------------------------- 4.55/2.11 4.55/2.11 (7) IDPNonInfProof (SOUND) 4.55/2.11 Used the following options for this NonInfProof: 4.55/2.11 4.55/2.11 IDPGPoloSolver: 4.55/2.11 Range: [(-1,2)] 4.55/2.11 IsNat: false 4.55/2.11 Interpretation Shape Heuristic: aprove.DPFramework.IDPProblem.Processors.nonInf.poly.IdpDefaultShapeHeuristic@3ebf6652 4.55/2.11 Constraint Generator: NonInfConstraintGenerator: 4.55/2.11 PathGenerator: MetricPathGenerator: 4.55/2.11 Max Left Steps: 1 4.55/2.11 Max Right Steps: 1 4.55/2.11 4.55/2.11 4.55/2.11 4.55/2.11 The constraints were generated the following way: 4.55/2.11 4.55/2.11 The DP Problem is simplified using the Induction Calculus [NONINF] with the following steps: 4.55/2.11 4.55/2.11 Note that final constraints are written in bold face. 4.55/2.11 4.55/2.11 4.55/2.11 4.55/2.11 For Pair COND(TRUE, x[4], y[4], z[4]) -> D(x[4], +(y[4], 1), +(+(y[4], 1), z[4])) the following chains were created: 4.55/2.11 *We consider the chain DNAT(TRUE, x[3], y[3], z[3]) -> COND(>=(x[3], z[3]), x[3], -(y[3], 1), z[3]), COND(TRUE, x[4], y[4], z[4]) -> D(x[4], +(y[4], 1), +(+(y[4], 1), z[4])), D(x[2], y[2], z[2]) -> DNAT(&&(&&(>=(x[2], 0), >=(y[2], 1)), >=(z[2], 0)), x[2], y[2], z[2]) which results in the following constraint: 4.55/2.11 4.55/2.11 (1) (>=(x[3], z[3])=TRUE & x[3]=x[4] & -(y[3], 1)=y[4] & z[3]=z[4] & x[4]=x[2] & +(y[4], 1)=y[2] & +(+(y[4], 1), z[4])=z[2] ==> COND(TRUE, x[4], y[4], z[4])_>=_NonInfC & COND(TRUE, x[4], y[4], z[4])_>=_D(x[4], +(y[4], 1), +(+(y[4], 1), z[4])) & (U^Increasing(D(x[4], +(y[4], 1), +(+(y[4], 1), z[4]))), >=)) 4.55/2.11 4.55/2.11 4.55/2.11 4.55/2.11 We simplified constraint (1) using rules (III), (IV) which results in the following new constraint: 4.55/2.11 4.55/2.11 (2) (>=(x[3], z[3])=TRUE ==> COND(TRUE, x[3], -(y[3], 1), z[3])_>=_NonInfC & COND(TRUE, x[3], -(y[3], 1), z[3])_>=_D(x[3], +(-(y[3], 1), 1), +(+(-(y[3], 1), 1), z[3])) & (U^Increasing(D(x[4], +(y[4], 1), +(+(y[4], 1), z[4]))), >=)) 4.55/2.11 4.55/2.11 4.55/2.11 4.55/2.11 We simplified constraint (2) using rule (POLY_CONSTRAINTS) which results in the following new constraint: 4.55/2.11 4.55/2.11 (3) (x[3] + [-1]z[3] >= 0 ==> (U^Increasing(D(x[4], +(y[4], 1), +(+(y[4], 1), z[4]))), >=) & [bni_19 + (-1)Bound*bni_19] + [(-1)bni_19]z[3] + [bni_19]y[3] + [(2)bni_19]x[3] >= 0 & [(-1)bso_20] >= 0) 4.55/2.11 4.55/2.11 4.55/2.11 4.55/2.11 We simplified constraint (3) using rule (IDP_POLY_SIMPLIFY) which results in the following new constraint: 4.55/2.11 4.55/2.11 (4) (x[3] + [-1]z[3] >= 0 ==> (U^Increasing(D(x[4], +(y[4], 1), +(+(y[4], 1), z[4]))), >=) & [bni_19 + (-1)Bound*bni_19] + [(-1)bni_19]z[3] + [bni_19]y[3] + [(2)bni_19]x[3] >= 0 & [(-1)bso_20] >= 0) 4.55/2.11 4.55/2.11 4.55/2.11 4.55/2.11 We simplified constraint (4) using rule (POLY_REMOVE_MIN_MAX) which results in the following new constraint: 4.55/2.11 4.55/2.11 (5) (x[3] + [-1]z[3] >= 0 ==> (U^Increasing(D(x[4], +(y[4], 1), +(+(y[4], 1), z[4]))), >=) & [bni_19 + (-1)Bound*bni_19] + [(-1)bni_19]z[3] + [bni_19]y[3] + [(2)bni_19]x[3] >= 0 & [(-1)bso_20] >= 0) 4.55/2.11 4.55/2.11 4.55/2.11 4.55/2.11 We simplified constraint (5) using rule (IDP_UNRESTRICTED_VARS) which results in the following new constraint: 4.55/2.11 4.55/2.11 (6) (x[3] + [-1]z[3] >= 0 ==> (U^Increasing(D(x[4], +(y[4], 1), +(+(y[4], 1), z[4]))), >=) & [bni_19] = 0 & [bni_19 + (-1)Bound*bni_19] + [(-1)bni_19]z[3] + [(2)bni_19]x[3] >= 0 & 0 = 0 & [(-1)bso_20] >= 0) 4.55/2.11 4.55/2.11 4.55/2.11 4.55/2.11 We simplified constraint (6) using rule (IDP_SMT_SPLIT) which results in the following new constraint: 4.55/2.11 4.55/2.11 (7) (x[3] >= 0 ==> (U^Increasing(D(x[4], +(y[4], 1), +(+(y[4], 1), z[4]))), >=) & [bni_19] = 0 & [bni_19 + (-1)Bound*bni_19] + [bni_19]z[3] + [(2)bni_19]x[3] >= 0 & 0 = 0 & [(-1)bso_20] >= 0) 4.55/2.11 4.55/2.11 4.55/2.11 4.55/2.11 We simplified constraint (7) using rule (IDP_SMT_SPLIT) which results in the following new constraints: 4.55/2.11 4.55/2.11 (8) (x[3] >= 0 & z[3] >= 0 ==> (U^Increasing(D(x[4], +(y[4], 1), +(+(y[4], 1), z[4]))), >=) & [bni_19] = 0 & [bni_19 + (-1)Bound*bni_19] + [(-1)bni_19]z[3] + [(2)bni_19]x[3] >= 0 & 0 = 0 & [(-1)bso_20] >= 0) 4.55/2.11 4.55/2.11 (9) (x[3] >= 0 & z[3] >= 0 ==> (U^Increasing(D(x[4], +(y[4], 1), +(+(y[4], 1), z[4]))), >=) & [bni_19] = 0 & [bni_19 + (-1)Bound*bni_19] + [bni_19]z[3] + [(2)bni_19]x[3] >= 0 & 0 = 0 & [(-1)bso_20] >= 0) 4.55/2.11 4.55/2.11 4.55/2.11 4.55/2.11 4.55/2.11 4.55/2.11 4.55/2.11 4.55/2.11 4.55/2.11 For Pair DNAT(TRUE, x[3], y[3], z[3]) -> COND(>=(x[3], z[3]), x[3], -(y[3], 1), z[3]) the following chains were created: 4.55/2.11 *We consider the chain D(x[2], y[2], z[2]) -> DNAT(&&(&&(>=(x[2], 0), >=(y[2], 1)), >=(z[2], 0)), x[2], y[2], z[2]), DNAT(TRUE, x[3], y[3], z[3]) -> COND(>=(x[3], z[3]), x[3], -(y[3], 1), z[3]), COND(TRUE, x[4], y[4], z[4]) -> D(x[4], +(y[4], 1), +(+(y[4], 1), z[4])) which results in the following constraint: 4.55/2.11 4.55/2.11 (1) (&&(&&(>=(x[2], 0), >=(y[2], 1)), >=(z[2], 0))=TRUE & x[2]=x[3] & y[2]=y[3] & z[2]=z[3] & >=(x[3], z[3])=TRUE & x[3]=x[4] & -(y[3], 1)=y[4] & z[3]=z[4] ==> DNAT(TRUE, x[3], y[3], z[3])_>=_NonInfC & DNAT(TRUE, x[3], y[3], z[3])_>=_COND(>=(x[3], z[3]), x[3], -(y[3], 1), z[3]) & (U^Increasing(COND(>=(x[3], z[3]), x[3], -(y[3], 1), z[3])), >=)) 4.55/2.11 4.55/2.11 4.55/2.11 4.55/2.11 We simplified constraint (1) using rules (III), (IV), (IDP_BOOLEAN) which results in the following new constraint: 4.55/2.11 4.55/2.11 (2) (>=(x[2], z[2])=TRUE & >=(z[2], 0)=TRUE & >=(x[2], 0)=TRUE & >=(y[2], 1)=TRUE ==> DNAT(TRUE, x[2], y[2], z[2])_>=_NonInfC & DNAT(TRUE, x[2], y[2], z[2])_>=_COND(>=(x[2], z[2]), x[2], -(y[2], 1), z[2]) & (U^Increasing(COND(>=(x[3], z[3]), x[3], -(y[3], 1), z[3])), >=)) 4.55/2.11 4.55/2.11 4.55/2.11 4.55/2.11 We simplified constraint (2) using rule (POLY_CONSTRAINTS) which results in the following new constraint: 4.55/2.11 4.55/2.11 (3) (x[2] + [-1]z[2] >= 0 & z[2] >= 0 & x[2] >= 0 & y[2] + [-1] >= 0 ==> (U^Increasing(COND(>=(x[3], z[3]), x[3], -(y[3], 1), z[3])), >=) & [(2)bni_21 + (-1)Bound*bni_21] + [(-1)bni_21]z[2] + [bni_21]y[2] + [(2)bni_21]x[2] >= 0 & [1 + (-1)bso_22] >= 0) 4.55/2.11 4.55/2.11 4.55/2.11 4.55/2.11 We simplified constraint (3) using rule (IDP_POLY_SIMPLIFY) which results in the following new constraint: 4.55/2.11 4.55/2.11 (4) (x[2] + [-1]z[2] >= 0 & z[2] >= 0 & x[2] >= 0 & y[2] + [-1] >= 0 ==> (U^Increasing(COND(>=(x[3], z[3]), x[3], -(y[3], 1), z[3])), >=) & [(2)bni_21 + (-1)Bound*bni_21] + [(-1)bni_21]z[2] + [bni_21]y[2] + [(2)bni_21]x[2] >= 0 & [1 + (-1)bso_22] >= 0) 4.55/2.11 4.55/2.11 4.55/2.11 4.55/2.11 We simplified constraint (4) using rule (POLY_REMOVE_MIN_MAX) which results in the following new constraint: 4.55/2.11 4.55/2.11 (5) (x[2] + [-1]z[2] >= 0 & z[2] >= 0 & x[2] >= 0 & y[2] + [-1] >= 0 ==> (U^Increasing(COND(>=(x[3], z[3]), x[3], -(y[3], 1), z[3])), >=) & [(2)bni_21 + (-1)Bound*bni_21] + [(-1)bni_21]z[2] + [bni_21]y[2] + [(2)bni_21]x[2] >= 0 & [1 + (-1)bso_22] >= 0) 4.55/2.11 4.55/2.11 4.55/2.11 4.55/2.11 4.55/2.11 4.55/2.11 4.55/2.11 4.55/2.11 4.55/2.11 For Pair D(x[2], y[2], z[2]) -> DNAT(&&(&&(>=(x[2], 0), >=(y[2], 1)), >=(z[2], 0)), x[2], y[2], z[2]) the following chains were created: 4.55/2.11 *We consider the chain D(x[2], y[2], z[2]) -> DNAT(&&(&&(>=(x[2], 0), >=(y[2], 1)), >=(z[2], 0)), x[2], y[2], z[2]), DNAT(TRUE, x[3], y[3], z[3]) -> COND(>=(x[3], z[3]), x[3], -(y[3], 1), z[3]) which results in the following constraint: 4.55/2.11 4.55/2.11 (1) (&&(&&(>=(x[2], 0), >=(y[2], 1)), >=(z[2], 0))=TRUE & x[2]=x[3] & y[2]=y[3] & z[2]=z[3] ==> D(x[2], y[2], z[2])_>=_NonInfC & D(x[2], y[2], z[2])_>=_DNAT(&&(&&(>=(x[2], 0), >=(y[2], 1)), >=(z[2], 0)), x[2], y[2], z[2]) & (U^Increasing(DNAT(&&(&&(>=(x[2], 0), >=(y[2], 1)), >=(z[2], 0)), x[2], y[2], z[2])), >=)) 4.55/2.11 4.55/2.11 4.55/2.11 4.55/2.11 We simplified constraint (1) using rules (IV), (IDP_BOOLEAN) which results in the following new constraint: 4.55/2.11 4.55/2.11 (2) (>=(z[2], 0)=TRUE & >=(x[2], 0)=TRUE & >=(y[2], 1)=TRUE ==> D(x[2], y[2], z[2])_>=_NonInfC & D(x[2], y[2], z[2])_>=_DNAT(&&(&&(>=(x[2], 0), >=(y[2], 1)), >=(z[2], 0)), x[2], y[2], z[2]) & (U^Increasing(DNAT(&&(&&(>=(x[2], 0), >=(y[2], 1)), >=(z[2], 0)), x[2], y[2], z[2])), >=)) 4.55/2.11 4.55/2.11 4.55/2.11 4.55/2.11 We simplified constraint (2) using rule (POLY_CONSTRAINTS) which results in the following new constraint: 4.55/2.11 4.55/2.11 (3) (z[2] >= 0 & x[2] >= 0 & y[2] + [-1] >= 0 ==> (U^Increasing(DNAT(&&(&&(>=(x[2], 0), >=(y[2], 1)), >=(z[2], 0)), x[2], y[2], z[2])), >=) & [bni_23 + (-1)Bound*bni_23] + [(-1)bni_23]z[2] + [(2)bni_23]y[2] + [(2)bni_23]x[2] >= 0 & [-1 + (-1)bso_24] + y[2] >= 0) 4.55/2.11 4.55/2.11 4.55/2.11 4.55/2.11 We simplified constraint (3) using rule (IDP_POLY_SIMPLIFY) which results in the following new constraint: 4.55/2.11 4.55/2.11 (4) (z[2] >= 0 & x[2] >= 0 & y[2] + [-1] >= 0 ==> (U^Increasing(DNAT(&&(&&(>=(x[2], 0), >=(y[2], 1)), >=(z[2], 0)), x[2], y[2], z[2])), >=) & [bni_23 + (-1)Bound*bni_23] + [(-1)bni_23]z[2] + [(2)bni_23]y[2] + [(2)bni_23]x[2] >= 0 & [-1 + (-1)bso_24] + y[2] >= 0) 4.55/2.11 4.55/2.11 4.55/2.11 4.55/2.11 We simplified constraint (4) using rule (POLY_REMOVE_MIN_MAX) which results in the following new constraint: 4.55/2.11 4.55/2.11 (5) (z[2] >= 0 & x[2] >= 0 & y[2] + [-1] >= 0 ==> (U^Increasing(DNAT(&&(&&(>=(x[2], 0), >=(y[2], 1)), >=(z[2], 0)), x[2], y[2], z[2])), >=) & [bni_23 + (-1)Bound*bni_23] + [(-1)bni_23]z[2] + [(2)bni_23]y[2] + [(2)bni_23]x[2] >= 0 & [-1 + (-1)bso_24] + y[2] >= 0) 4.55/2.11 4.55/2.11 4.55/2.11 4.55/2.11 4.55/2.11 4.55/2.11 4.55/2.11 4.55/2.11 4.55/2.11 To summarize, we get the following constraints P__>=_ for the following pairs. 4.55/2.11 4.55/2.11 *COND(TRUE, x[4], y[4], z[4]) -> D(x[4], +(y[4], 1), +(+(y[4], 1), z[4])) 4.55/2.11 4.55/2.11 *(x[3] >= 0 & z[3] >= 0 ==> (U^Increasing(D(x[4], +(y[4], 1), +(+(y[4], 1), z[4]))), >=) & [bni_19] = 0 & [bni_19 + (-1)Bound*bni_19] + [(-1)bni_19]z[3] + [(2)bni_19]x[3] >= 0 & 0 = 0 & [(-1)bso_20] >= 0) 4.55/2.11 4.55/2.11 4.55/2.11 *(x[3] >= 0 & z[3] >= 0 ==> (U^Increasing(D(x[4], +(y[4], 1), +(+(y[4], 1), z[4]))), >=) & [bni_19] = 0 & [bni_19 + (-1)Bound*bni_19] + [bni_19]z[3] + [(2)bni_19]x[3] >= 0 & 0 = 0 & [(-1)bso_20] >= 0) 4.55/2.11 4.55/2.11 4.55/2.11 4.55/2.11 4.55/2.11 *DNAT(TRUE, x[3], y[3], z[3]) -> COND(>=(x[3], z[3]), x[3], -(y[3], 1), z[3]) 4.55/2.11 4.55/2.11 *(x[2] + [-1]z[2] >= 0 & z[2] >= 0 & x[2] >= 0 & y[2] + [-1] >= 0 ==> (U^Increasing(COND(>=(x[3], z[3]), x[3], -(y[3], 1), z[3])), >=) & [(2)bni_21 + (-1)Bound*bni_21] + [(-1)bni_21]z[2] + [bni_21]y[2] + [(2)bni_21]x[2] >= 0 & [1 + (-1)bso_22] >= 0) 4.55/2.11 4.55/2.11 4.55/2.11 4.55/2.11 4.55/2.11 *D(x[2], y[2], z[2]) -> DNAT(&&(&&(>=(x[2], 0), >=(y[2], 1)), >=(z[2], 0)), x[2], y[2], z[2]) 4.55/2.11 4.55/2.11 *(z[2] >= 0 & x[2] >= 0 & y[2] + [-1] >= 0 ==> (U^Increasing(DNAT(&&(&&(>=(x[2], 0), >=(y[2], 1)), >=(z[2], 0)), x[2], y[2], z[2])), >=) & [bni_23 + (-1)Bound*bni_23] + [(-1)bni_23]z[2] + [(2)bni_23]y[2] + [(2)bni_23]x[2] >= 0 & [-1 + (-1)bso_24] + y[2] >= 0) 4.55/2.11 4.55/2.11 4.55/2.11 4.55/2.11 4.55/2.11 4.55/2.11 4.55/2.11 4.55/2.11 4.55/2.11 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. 4.55/2.11 4.55/2.11 Using the following integer polynomial ordering the resulting constraints can be solved 4.55/2.11 4.55/2.11 Polynomial interpretation over integers[POLO]: 4.55/2.11 4.55/2.11 POL(TRUE) = [3] 4.55/2.11 POL(FALSE) = [2] 4.55/2.11 POL(COND(x_1, x_2, x_3, x_4)) = [2] + [-1]x_4 + x_3 + [2]x_2 4.55/2.11 POL(D(x_1, x_2, x_3)) = [1] + [-1]x_3 + [2]x_2 + [2]x_1 4.55/2.11 POL(+(x_1, x_2)) = x_1 + x_2 4.55/2.11 POL(1) = [1] 4.55/2.11 POL(DNAT(x_1, x_2, x_3, x_4)) = [2] + [-1]x_4 + x_3 + [2]x_2 4.55/2.11 POL(>=(x_1, x_2)) = [-1] 4.55/2.11 POL(-(x_1, x_2)) = x_1 + [-1]x_2 4.55/2.11 POL(&&(x_1, x_2)) = [-1] 4.55/2.11 POL(0) = 0 4.55/2.11 4.55/2.11 4.55/2.11 The following pairs are in P_>: 4.55/2.11 4.55/2.11 4.55/2.11 DNAT(TRUE, x[3], y[3], z[3]) -> COND(>=(x[3], z[3]), x[3], -(y[3], 1), z[3]) 4.55/2.11 4.55/2.11 4.55/2.11 The following pairs are in P_bound: 4.55/2.11 4.55/2.11 4.55/2.11 DNAT(TRUE, x[3], y[3], z[3]) -> COND(>=(x[3], z[3]), x[3], -(y[3], 1), z[3]) 4.55/2.11 4.55/2.11 4.55/2.11 The following pairs are in P_>=: 4.55/2.11 4.55/2.11 4.55/2.11 COND(TRUE, x[4], y[4], z[4]) -> D(x[4], +(y[4], 1), +(+(y[4], 1), z[4])) 4.55/2.11 D(x[2], y[2], z[2]) -> DNAT(&&(&&(>=(x[2], 0), >=(y[2], 1)), >=(z[2], 0)), x[2], y[2], z[2]) 4.55/2.11 4.55/2.11 4.55/2.11 At least the following rules have been oriented under context sensitive arithmetic replacement: 4.55/2.11 4.55/2.11 FALSE^1 -> &&(TRUE, FALSE)^1 4.55/2.11 FALSE^1 -> &&(FALSE, TRUE)^1 4.55/2.11 4.55/2.11 ---------------------------------------- 4.55/2.11 4.55/2.11 (8) 4.55/2.11 Obligation: 4.55/2.11 IDP problem: 4.55/2.11 The following function symbols are pre-defined: 4.55/2.11 <<< 4.55/2.11 & ~ Bwand: (Integer, Integer) -> Integer 4.55/2.11 >= ~ Ge: (Integer, Integer) -> Boolean 4.55/2.11 | ~ Bwor: (Integer, Integer) -> Integer 4.55/2.11 / ~ Div: (Integer, Integer) -> Integer 4.55/2.11 != ~ Neq: (Integer, Integer) -> Boolean 4.55/2.11 && ~ Land: (Boolean, Boolean) -> Boolean 4.55/2.11 ! ~ Lnot: (Boolean) -> Boolean 4.55/2.11 = ~ Eq: (Integer, Integer) -> Boolean 4.55/2.11 <= ~ Le: (Integer, Integer) -> Boolean 4.55/2.11 ^ ~ Bwxor: (Integer, Integer) -> Integer 4.55/2.11 % ~ Mod: (Integer, Integer) -> Integer 4.55/2.11 + ~ Add: (Integer, Integer) -> Integer 4.55/2.11 > ~ Gt: (Integer, Integer) -> Boolean 4.55/2.11 -1 ~ UnaryMinus: (Integer) -> Integer 4.55/2.11 < ~ Lt: (Integer, Integer) -> Boolean 4.55/2.11 || ~ Lor: (Boolean, Boolean) -> Boolean 4.55/2.11 - ~ Sub: (Integer, Integer) -> Integer 4.55/2.11 ~ ~ Bwnot: (Integer) -> Integer 4.55/2.11 * ~ Mul: (Integer, Integer) -> Integer 4.55/2.11 >>> 4.55/2.11 4.55/2.11 4.55/2.11 The following domains are used: 4.55/2.11 Integer, Boolean 4.55/2.11 4.55/2.11 R is empty. 4.55/2.11 4.55/2.11 The integer pair graph contains the following rules and edges: 4.55/2.11 (4): COND(TRUE, x[4], y[4], z[4]) -> D(x[4], y[4] + 1, y[4] + 1 + z[4]) 4.55/2.11 (2): D(x[2], y[2], z[2]) -> DNAT(x[2] >= 0 && y[2] >= 1 && z[2] >= 0, x[2], y[2], z[2]) 4.55/2.11 4.55/2.11 (4) -> (2), if (x[4] ->^* x[2] & y[4] + 1 ->^* y[2] & y[4] + 1 + z[4] ->^* z[2]) 4.55/2.11 4.55/2.11 The set Q consists of the following terms: 4.55/2.11 div(x0, x1) 4.55/2.11 divNat(TRUE, x0, x1) 4.55/2.11 d(x0, x1, x2) 4.55/2.11 dNat(TRUE, x0, x1, x2) 4.55/2.11 cond(TRUE, x0, x1, x2) 4.55/2.11 cond(FALSE, x0, x1, x2) 4.55/2.11 4.55/2.11 ---------------------------------------- 4.55/2.11 4.55/2.11 (9) IDependencyGraphProof (EQUIVALENT) 4.55/2.11 The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 0 SCCs with 2 less nodes. 4.55/2.11 ---------------------------------------- 4.55/2.11 4.55/2.11 (10) 4.55/2.11 TRUE 4.59/2.17 EOF