3.90/2.02 YES 3.90/2.03 proof of /export/starexec/sandbox/benchmark/theBenchmark.itrs 3.90/2.03 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 3.90/2.03 3.90/2.03 3.90/2.03 Termination of the given ITRS could be proven: 3.90/2.03 3.90/2.03 (0) ITRS 3.90/2.03 (1) ITRStoIDPProof [EQUIVALENT, 0 ms] 3.90/2.03 (2) IDP 3.90/2.03 (3) UsableRulesProof [EQUIVALENT, 0 ms] 3.90/2.03 (4) IDP 3.90/2.03 (5) IDependencyGraphProof [EQUIVALENT, 0 ms] 3.90/2.03 (6) AND 3.90/2.03 (7) IDP 3.90/2.03 (8) IDPNonInfProof [SOUND, 118 ms] 3.90/2.03 (9) IDP 3.90/2.03 (10) PisEmptyProof [EQUIVALENT, 0 ms] 3.90/2.03 (11) YES 3.90/2.03 (12) IDP 3.90/2.03 (13) IDPNonInfProof [SOUND, 36 ms] 3.90/2.03 (14) IDP 3.90/2.03 (15) IDependencyGraphProof [EQUIVALENT, 0 ms] 3.90/2.03 (16) TRUE 3.90/2.03 3.90/2.03 3.90/2.03 ---------------------------------------- 3.90/2.03 3.90/2.03 (0) 3.90/2.03 Obligation: 3.90/2.03 ITRS problem: 3.90/2.03 3.90/2.03 The following function symbols are pre-defined: 3.90/2.03 <<< 3.90/2.03 & ~ Bwand: (Integer, Integer) -> Integer 3.90/2.03 >= ~ Ge: (Integer, Integer) -> Boolean 3.90/2.03 / ~ Div: (Integer, Integer) -> Integer 3.90/2.03 | ~ Bwor: (Integer, Integer) -> Integer 3.90/2.03 != ~ Neq: (Integer, Integer) -> Boolean 3.90/2.03 && ~ Land: (Boolean, Boolean) -> Boolean 3.90/2.03 ! ~ Lnot: (Boolean) -> Boolean 3.90/2.03 = ~ Eq: (Integer, Integer) -> Boolean 3.90/2.03 <= ~ Le: (Integer, Integer) -> Boolean 3.90/2.03 ^ ~ Bwxor: (Integer, Integer) -> Integer 3.90/2.03 % ~ Mod: (Integer, Integer) -> Integer 3.90/2.03 > ~ Gt: (Integer, Integer) -> Boolean 3.90/2.03 + ~ Add: (Integer, Integer) -> Integer 3.90/2.03 -1 ~ UnaryMinus: (Integer) -> Integer 3.90/2.03 < ~ Lt: (Integer, Integer) -> Boolean 3.90/2.03 || ~ Lor: (Boolean, Boolean) -> Boolean 3.90/2.03 - ~ Sub: (Integer, Integer) -> Integer 3.90/2.03 ~ ~ Bwnot: (Integer) -> Integer 3.90/2.03 * ~ Mul: (Integer, Integer) -> Integer 3.90/2.03 >>> 3.90/2.03 3.90/2.03 The TRS R consists of the following rules: 3.90/2.03 lastbit(0) -> 0 3.90/2.03 lastbit(1) -> 1 3.90/2.03 lastbit(x) -> Cond_lastbit(x > 1, x) 3.90/2.03 Cond_lastbit(TRUE, x) -> lastbit(x - 2) 3.90/2.03 conv(0) -> cons(nil, 0) 3.90/2.03 conv(x) -> Cond_conv(x > 0, x) 3.90/2.03 Cond_conv(TRUE, x) -> cons(conv(x / 2), lastbit(x)) 3.90/2.03 The set Q consists of the following terms: 3.90/2.03 lastbit(x0) 3.90/2.03 Cond_lastbit(TRUE, x0) 3.90/2.03 conv(x0) 3.90/2.03 Cond_conv(TRUE, x0) 3.90/2.03 3.90/2.03 ---------------------------------------- 3.90/2.03 3.90/2.03 (1) ITRStoIDPProof (EQUIVALENT) 3.90/2.03 Added dependency pairs 3.90/2.03 ---------------------------------------- 3.90/2.03 3.90/2.03 (2) 3.90/2.03 Obligation: 3.90/2.03 IDP problem: 3.90/2.03 The following function symbols are pre-defined: 3.90/2.03 <<< 3.90/2.03 & ~ Bwand: (Integer, Integer) -> Integer 3.90/2.03 >= ~ Ge: (Integer, Integer) -> Boolean 3.90/2.03 / ~ Div: (Integer, Integer) -> Integer 3.90/2.03 | ~ Bwor: (Integer, Integer) -> Integer 3.90/2.03 != ~ Neq: (Integer, Integer) -> Boolean 3.90/2.03 && ~ Land: (Boolean, Boolean) -> Boolean 3.90/2.03 ! ~ Lnot: (Boolean) -> Boolean 3.90/2.03 = ~ Eq: (Integer, Integer) -> Boolean 3.90/2.03 <= ~ Le: (Integer, Integer) -> Boolean 3.90/2.03 ^ ~ Bwxor: (Integer, Integer) -> Integer 3.90/2.03 % ~ Mod: (Integer, Integer) -> Integer 3.90/2.03 > ~ Gt: (Integer, Integer) -> Boolean 3.90/2.03 + ~ Add: (Integer, Integer) -> Integer 3.90/2.03 -1 ~ UnaryMinus: (Integer) -> Integer 3.90/2.03 < ~ Lt: (Integer, Integer) -> Boolean 3.90/2.03 || ~ Lor: (Boolean, Boolean) -> Boolean 3.90/2.03 - ~ Sub: (Integer, Integer) -> Integer 3.90/2.03 ~ ~ Bwnot: (Integer) -> Integer 3.90/2.03 * ~ Mul: (Integer, Integer) -> Integer 3.90/2.03 >>> 3.90/2.03 3.90/2.03 3.90/2.03 The following domains are used: 3.90/2.03 Integer 3.90/2.03 3.90/2.03 The ITRS R consists of the following rules: 3.90/2.03 lastbit(0) -> 0 3.90/2.03 lastbit(1) -> 1 3.90/2.03 lastbit(x) -> Cond_lastbit(x > 1, x) 3.90/2.03 Cond_lastbit(TRUE, x) -> lastbit(x - 2) 3.90/2.03 conv(0) -> cons(nil, 0) 3.90/2.03 conv(x) -> Cond_conv(x > 0, x) 3.90/2.03 Cond_conv(TRUE, x) -> cons(conv(x / 2), lastbit(x)) 3.90/2.03 3.90/2.03 The integer pair graph contains the following rules and edges: 3.90/2.03 (0): LASTBIT(x[0]) -> COND_LASTBIT(x[0] > 1, x[0]) 3.90/2.03 (1): COND_LASTBIT(TRUE, x[1]) -> LASTBIT(x[1] - 2) 3.90/2.03 (2): CONV(x[2]) -> COND_CONV(x[2] > 0, x[2]) 3.90/2.03 (3): COND_CONV(TRUE, x[3]) -> CONV(x[3] / 2) 3.90/2.03 (4): COND_CONV(TRUE, x[4]) -> LASTBIT(x[4]) 3.90/2.03 3.90/2.03 (0) -> (1), if (x[0] > 1 & x[0] ->^* x[1]) 3.90/2.03 (1) -> (0), if (x[1] - 2 ->^* x[0]) 3.90/2.03 (2) -> (3), if (x[2] > 0 & x[2] ->^* x[3]) 3.90/2.03 (2) -> (4), if (x[2] > 0 & x[2] ->^* x[4]) 3.90/2.03 (3) -> (2), if (x[3] / 2 ->^* x[2]) 3.90/2.03 (4) -> (0), if (x[4] ->^* x[0]) 3.90/2.03 3.90/2.03 The set Q consists of the following terms: 3.90/2.03 lastbit(x0) 3.90/2.03 Cond_lastbit(TRUE, x0) 3.90/2.03 conv(x0) 3.90/2.03 Cond_conv(TRUE, x0) 3.90/2.03 3.90/2.03 ---------------------------------------- 3.90/2.03 3.90/2.03 (3) UsableRulesProof (EQUIVALENT) 3.90/2.03 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. 3.90/2.03 ---------------------------------------- 3.90/2.03 3.90/2.03 (4) 3.90/2.03 Obligation: 3.90/2.03 IDP problem: 3.90/2.03 The following function symbols are pre-defined: 3.90/2.03 <<< 3.90/2.03 & ~ Bwand: (Integer, Integer) -> Integer 3.90/2.03 >= ~ Ge: (Integer, Integer) -> Boolean 3.90/2.03 / ~ Div: (Integer, Integer) -> Integer 3.90/2.03 | ~ Bwor: (Integer, Integer) -> Integer 3.90/2.03 != ~ Neq: (Integer, Integer) -> Boolean 3.90/2.03 && ~ Land: (Boolean, Boolean) -> Boolean 3.90/2.03 ! ~ Lnot: (Boolean) -> Boolean 3.90/2.03 = ~ Eq: (Integer, Integer) -> Boolean 3.90/2.03 <= ~ Le: (Integer, Integer) -> Boolean 3.90/2.03 ^ ~ Bwxor: (Integer, Integer) -> Integer 3.90/2.03 % ~ Mod: (Integer, Integer) -> Integer 3.90/2.03 > ~ Gt: (Integer, Integer) -> Boolean 3.90/2.03 + ~ Add: (Integer, Integer) -> Integer 3.90/2.03 -1 ~ UnaryMinus: (Integer) -> Integer 3.90/2.03 < ~ Lt: (Integer, Integer) -> Boolean 3.90/2.03 || ~ Lor: (Boolean, Boolean) -> Boolean 3.90/2.03 - ~ Sub: (Integer, Integer) -> Integer 3.90/2.03 ~ ~ Bwnot: (Integer) -> Integer 3.90/2.03 * ~ Mul: (Integer, Integer) -> Integer 3.90/2.03 >>> 3.90/2.03 3.90/2.03 3.90/2.03 The following domains are used: 3.90/2.03 Integer 3.90/2.03 3.90/2.03 R is empty. 3.90/2.03 3.90/2.03 The integer pair graph contains the following rules and edges: 3.90/2.03 (0): LASTBIT(x[0]) -> COND_LASTBIT(x[0] > 1, x[0]) 3.90/2.03 (1): COND_LASTBIT(TRUE, x[1]) -> LASTBIT(x[1] - 2) 3.90/2.03 (2): CONV(x[2]) -> COND_CONV(x[2] > 0, x[2]) 3.90/2.03 (3): COND_CONV(TRUE, x[3]) -> CONV(x[3] / 2) 3.90/2.03 (4): COND_CONV(TRUE, x[4]) -> LASTBIT(x[4]) 3.90/2.03 3.90/2.03 (0) -> (1), if (x[0] > 1 & x[0] ->^* x[1]) 3.90/2.03 (1) -> (0), if (x[1] - 2 ->^* x[0]) 3.90/2.03 (2) -> (3), if (x[2] > 0 & x[2] ->^* x[3]) 3.90/2.03 (2) -> (4), if (x[2] > 0 & x[2] ->^* x[4]) 3.90/2.03 (3) -> (2), if (x[3] / 2 ->^* x[2]) 3.90/2.03 (4) -> (0), if (x[4] ->^* x[0]) 3.90/2.03 3.90/2.03 The set Q consists of the following terms: 3.90/2.03 lastbit(x0) 3.90/2.03 Cond_lastbit(TRUE, x0) 3.90/2.03 conv(x0) 3.90/2.03 Cond_conv(TRUE, x0) 3.90/2.03 3.90/2.03 ---------------------------------------- 3.90/2.03 3.90/2.03 (5) IDependencyGraphProof (EQUIVALENT) 3.90/2.03 The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 2 SCCs with 1 less node. 3.90/2.03 ---------------------------------------- 3.90/2.03 3.90/2.03 (6) 3.90/2.03 Complex Obligation (AND) 3.90/2.03 3.90/2.03 ---------------------------------------- 3.90/2.03 3.90/2.03 (7) 3.90/2.03 Obligation: 3.90/2.03 IDP problem: 3.90/2.03 The following function symbols are pre-defined: 3.90/2.03 <<< 3.90/2.03 & ~ Bwand: (Integer, Integer) -> Integer 3.90/2.03 >= ~ Ge: (Integer, Integer) -> Boolean 3.90/2.03 / ~ Div: (Integer, Integer) -> Integer 3.90/2.03 | ~ Bwor: (Integer, Integer) -> Integer 3.90/2.03 != ~ Neq: (Integer, Integer) -> Boolean 3.90/2.03 && ~ Land: (Boolean, Boolean) -> Boolean 3.90/2.03 ! ~ Lnot: (Boolean) -> Boolean 3.90/2.03 = ~ Eq: (Integer, Integer) -> Boolean 3.90/2.03 <= ~ Le: (Integer, Integer) -> Boolean 3.90/2.03 ^ ~ Bwxor: (Integer, Integer) -> Integer 3.90/2.03 % ~ Mod: (Integer, Integer) -> Integer 3.90/2.03 > ~ Gt: (Integer, Integer) -> Boolean 3.90/2.03 + ~ Add: (Integer, Integer) -> Integer 3.90/2.03 -1 ~ UnaryMinus: (Integer) -> Integer 3.90/2.03 < ~ Lt: (Integer, Integer) -> Boolean 3.90/2.03 || ~ Lor: (Boolean, Boolean) -> Boolean 3.90/2.03 - ~ Sub: (Integer, Integer) -> Integer 3.90/2.03 ~ ~ Bwnot: (Integer) -> Integer 3.90/2.03 * ~ Mul: (Integer, Integer) -> Integer 3.90/2.03 >>> 3.90/2.03 3.90/2.03 3.90/2.03 The following domains are used: 3.90/2.03 Integer 3.90/2.03 3.90/2.03 R is empty. 3.90/2.03 3.90/2.03 The integer pair graph contains the following rules and edges: 3.90/2.03 (1): COND_LASTBIT(TRUE, x[1]) -> LASTBIT(x[1] - 2) 3.90/2.03 (0): LASTBIT(x[0]) -> COND_LASTBIT(x[0] > 1, x[0]) 3.90/2.03 3.90/2.03 (1) -> (0), if (x[1] - 2 ->^* x[0]) 3.90/2.03 (0) -> (1), if (x[0] > 1 & x[0] ->^* x[1]) 3.90/2.03 3.90/2.03 The set Q consists of the following terms: 3.90/2.03 lastbit(x0) 3.90/2.03 Cond_lastbit(TRUE, x0) 3.90/2.03 conv(x0) 3.90/2.03 Cond_conv(TRUE, x0) 3.90/2.03 3.90/2.03 ---------------------------------------- 3.90/2.03 3.90/2.03 (8) IDPNonInfProof (SOUND) 3.90/2.03 Used the following options for this NonInfProof: 3.90/2.03 3.90/2.03 IDPGPoloSolver: 3.90/2.03 Range: [(-1,2)] 3.90/2.03 IsNat: false 3.90/2.03 Interpretation Shape Heuristic: aprove.DPFramework.IDPProblem.Processors.nonInf.poly.IdpDefaultShapeHeuristic@35700aad 3.90/2.03 Constraint Generator: NonInfConstraintGenerator: 3.90/2.03 PathGenerator: MetricPathGenerator: 3.90/2.03 Max Left Steps: 1 3.90/2.03 Max Right Steps: 1 3.90/2.03 3.90/2.03 3.90/2.03 3.90/2.03 The constraints were generated the following way: 3.90/2.03 3.90/2.03 The DP Problem is simplified using the Induction Calculus [NONINF] with the following steps: 3.90/2.03 3.90/2.03 Note that final constraints are written in bold face. 3.90/2.03 3.90/2.03 3.90/2.03 3.90/2.03 For Pair COND_LASTBIT(TRUE, x[1]) -> LASTBIT(-(x[1], 2)) the following chains were created: 3.90/2.03 *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: 3.90/2.03 3.90/2.03 (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))), >=)) 3.90/2.03 3.90/2.03 3.90/2.03 3.90/2.03 We simplified constraint (1) using rules (III), (IV) which results in the following new constraint: 3.90/2.03 3.90/2.03 (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))), >=)) 3.90/2.03 3.90/2.03 3.90/2.03 3.90/2.03 We simplified constraint (2) using rule (POLY_CONSTRAINTS) which results in the following new constraint: 3.90/2.03 3.90/2.03 (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) 3.90/2.03 3.90/2.03 3.90/2.03 3.90/2.03 We simplified constraint (3) using rule (IDP_POLY_SIMPLIFY) which results in the following new constraint: 3.90/2.03 3.90/2.03 (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) 3.90/2.03 3.90/2.03 3.90/2.03 3.90/2.03 We simplified constraint (4) using rule (POLY_REMOVE_MIN_MAX) which results in the following new constraint: 3.90/2.03 3.90/2.03 (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) 3.90/2.03 3.90/2.03 3.90/2.03 3.90/2.03 3.90/2.03 3.90/2.03 3.90/2.03 3.90/2.03 3.90/2.03 For Pair LASTBIT(x[0]) -> COND_LASTBIT(>(x[0], 1), x[0]) the following chains were created: 3.90/2.03 *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: 3.90/2.03 3.90/2.03 (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])), >=)) 3.90/2.03 3.90/2.03 3.90/2.03 3.90/2.03 We simplified constraint (1) using rule (IV) which results in the following new constraint: 3.90/2.03 3.90/2.03 (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])), >=)) 3.90/2.03 3.90/2.03 3.90/2.03 3.90/2.03 We simplified constraint (2) using rule (POLY_CONSTRAINTS) which results in the following new constraint: 3.90/2.04 3.90/2.04 (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) 3.90/2.04 3.90/2.04 3.90/2.04 3.90/2.04 We simplified constraint (3) using rule (IDP_POLY_SIMPLIFY) which results in the following new constraint: 3.90/2.04 3.90/2.04 (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) 3.90/2.04 3.90/2.04 3.90/2.04 3.90/2.04 We simplified constraint (4) using rule (POLY_REMOVE_MIN_MAX) which results in the following new constraint: 3.90/2.04 3.90/2.04 (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) 3.90/2.04 3.90/2.04 3.90/2.04 3.90/2.04 3.90/2.04 3.90/2.04 3.90/2.04 3.90/2.04 3.90/2.04 To summarize, we get the following constraints P__>=_ for the following pairs. 3.90/2.04 3.90/2.04 *COND_LASTBIT(TRUE, x[1]) -> LASTBIT(-(x[1], 2)) 3.90/2.04 3.90/2.04 *(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) 3.90/2.04 3.90/2.04 3.90/2.04 3.90/2.04 3.90/2.04 *LASTBIT(x[0]) -> COND_LASTBIT(>(x[0], 1), x[0]) 3.90/2.04 3.90/2.04 *(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) 3.90/2.04 3.90/2.04 3.90/2.04 3.90/2.04 3.90/2.04 3.90/2.04 3.90/2.04 3.90/2.04 3.90/2.04 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. 3.90/2.04 3.90/2.04 Using the following integer polynomial ordering the resulting constraints can be solved 3.90/2.04 3.90/2.04 Polynomial interpretation over integers[POLO]: 3.90/2.04 3.90/2.04 POL(TRUE) = [3] 3.90/2.04 POL(FALSE) = 0 3.90/2.04 POL(COND_LASTBIT(x_1, x_2)) = [-1] + [2]x_2 3.90/2.04 POL(LASTBIT(x_1)) = [2] + [2]x_1 3.90/2.04 POL(-(x_1, x_2)) = x_1 + [-1]x_2 3.90/2.04 POL(2) = [2] 3.90/2.04 POL(>(x_1, x_2)) = [-1] 3.90/2.04 POL(1) = [1] 3.90/2.04 3.90/2.04 3.90/2.04 The following pairs are in P_>: 3.90/2.04 3.90/2.04 3.90/2.04 COND_LASTBIT(TRUE, x[1]) -> LASTBIT(-(x[1], 2)) 3.90/2.04 LASTBIT(x[0]) -> COND_LASTBIT(>(x[0], 1), x[0]) 3.90/2.04 3.90/2.04 3.90/2.04 The following pairs are in P_bound: 3.90/2.04 3.90/2.04 3.90/2.04 COND_LASTBIT(TRUE, x[1]) -> LASTBIT(-(x[1], 2)) 3.90/2.04 LASTBIT(x[0]) -> COND_LASTBIT(>(x[0], 1), x[0]) 3.90/2.04 3.90/2.04 3.90/2.04 The following pairs are in P_>=: 3.90/2.04 3.90/2.04 none 3.90/2.04 3.90/2.04 3.90/2.04 There are no usable rules. 3.90/2.04 ---------------------------------------- 3.90/2.04 3.90/2.04 (9) 3.90/2.04 Obligation: 3.90/2.04 IDP problem: 3.90/2.04 The following function symbols are pre-defined: 3.90/2.04 <<< 3.90/2.04 & ~ Bwand: (Integer, Integer) -> Integer 3.90/2.04 >= ~ Ge: (Integer, Integer) -> Boolean 3.90/2.04 / ~ Div: (Integer, Integer) -> Integer 3.90/2.04 | ~ Bwor: (Integer, Integer) -> Integer 3.90/2.04 != ~ Neq: (Integer, Integer) -> Boolean 3.90/2.04 && ~ Land: (Boolean, Boolean) -> Boolean 3.90/2.04 ! ~ Lnot: (Boolean) -> Boolean 3.90/2.04 = ~ Eq: (Integer, Integer) -> Boolean 3.90/2.04 <= ~ Le: (Integer, Integer) -> Boolean 3.90/2.04 ^ ~ Bwxor: (Integer, Integer) -> Integer 3.90/2.04 % ~ Mod: (Integer, Integer) -> Integer 3.90/2.04 > ~ Gt: (Integer, Integer) -> Boolean 3.90/2.04 + ~ Add: (Integer, Integer) -> Integer 3.90/2.04 -1 ~ UnaryMinus: (Integer) -> Integer 3.90/2.04 < ~ Lt: (Integer, Integer) -> Boolean 3.90/2.04 || ~ Lor: (Boolean, Boolean) -> Boolean 3.90/2.04 - ~ Sub: (Integer, Integer) -> Integer 3.90/2.04 ~ ~ Bwnot: (Integer) -> Integer 3.90/2.04 * ~ Mul: (Integer, Integer) -> Integer 3.90/2.04 >>> 3.90/2.04 3.90/2.04 3.90/2.04 The following domains are used: 3.90/2.04 none 3.90/2.04 3.90/2.04 R is empty. 3.90/2.04 3.90/2.04 The integer pair graph is empty. 3.90/2.04 3.90/2.04 The set Q consists of the following terms: 3.90/2.04 lastbit(x0) 3.90/2.04 Cond_lastbit(TRUE, x0) 3.90/2.04 conv(x0) 3.90/2.04 Cond_conv(TRUE, x0) 3.90/2.04 3.90/2.04 ---------------------------------------- 3.90/2.04 3.90/2.04 (10) PisEmptyProof (EQUIVALENT) 3.90/2.04 The TRS P is empty. Hence, there is no (P,Q,R) chain. 3.90/2.04 ---------------------------------------- 3.90/2.04 3.90/2.04 (11) 3.90/2.04 YES 3.90/2.04 3.90/2.04 ---------------------------------------- 3.90/2.04 3.90/2.04 (12) 3.90/2.04 Obligation: 3.90/2.04 IDP problem: 3.90/2.04 The following function symbols are pre-defined: 3.90/2.04 <<< 3.90/2.04 & ~ Bwand: (Integer, Integer) -> Integer 3.90/2.04 >= ~ Ge: (Integer, Integer) -> Boolean 3.90/2.04 / ~ Div: (Integer, Integer) -> Integer 3.90/2.04 | ~ Bwor: (Integer, Integer) -> Integer 3.90/2.04 != ~ Neq: (Integer, Integer) -> Boolean 3.90/2.04 && ~ Land: (Boolean, Boolean) -> Boolean 3.90/2.04 ! ~ Lnot: (Boolean) -> Boolean 3.90/2.04 = ~ Eq: (Integer, Integer) -> Boolean 3.90/2.04 <= ~ Le: (Integer, Integer) -> Boolean 3.90/2.04 ^ ~ Bwxor: (Integer, Integer) -> Integer 3.90/2.04 % ~ Mod: (Integer, Integer) -> Integer 3.90/2.04 > ~ Gt: (Integer, Integer) -> Boolean 3.90/2.04 + ~ Add: (Integer, Integer) -> Integer 3.90/2.04 -1 ~ UnaryMinus: (Integer) -> Integer 3.90/2.04 < ~ Lt: (Integer, Integer) -> Boolean 3.90/2.04 || ~ Lor: (Boolean, Boolean) -> Boolean 3.90/2.04 - ~ Sub: (Integer, Integer) -> Integer 3.90/2.04 ~ ~ Bwnot: (Integer) -> Integer 3.90/2.04 * ~ Mul: (Integer, Integer) -> Integer 3.90/2.04 >>> 3.90/2.04 3.90/2.04 3.90/2.04 The following domains are used: 3.90/2.04 Integer 3.90/2.04 3.90/2.04 R is empty. 3.90/2.04 3.90/2.04 The integer pair graph contains the following rules and edges: 3.90/2.04 (3): COND_CONV(TRUE, x[3]) -> CONV(x[3] / 2) 3.90/2.04 (2): CONV(x[2]) -> COND_CONV(x[2] > 0, x[2]) 3.90/2.04 3.90/2.04 (3) -> (2), if (x[3] / 2 ->^* x[2]) 3.90/2.04 (2) -> (3), if (x[2] > 0 & x[2] ->^* x[3]) 3.90/2.04 3.90/2.04 The set Q consists of the following terms: 3.90/2.04 lastbit(x0) 3.90/2.04 Cond_lastbit(TRUE, x0) 3.90/2.04 conv(x0) 3.90/2.04 Cond_conv(TRUE, x0) 3.90/2.04 3.90/2.04 ---------------------------------------- 3.90/2.04 3.90/2.04 (13) IDPNonInfProof (SOUND) 3.90/2.04 Used the following options for this NonInfProof: 3.90/2.04 3.90/2.04 IDPGPoloSolver: 3.90/2.04 Range: [(-1,2)] 3.90/2.04 IsNat: false 3.90/2.04 Interpretation Shape Heuristic: aprove.DPFramework.IDPProblem.Processors.nonInf.poly.IdpDefaultShapeHeuristic@35700aad 3.90/2.04 Constraint Generator: NonInfConstraintGenerator: 3.90/2.04 PathGenerator: MetricPathGenerator: 3.90/2.04 Max Left Steps: 1 3.90/2.04 Max Right Steps: 1 3.90/2.04 3.90/2.04 3.90/2.04 3.90/2.04 The constraints were generated the following way: 3.90/2.04 3.90/2.04 The DP Problem is simplified using the Induction Calculus [NONINF] with the following steps: 3.90/2.04 3.90/2.04 Note that final constraints are written in bold face. 3.90/2.04 3.90/2.04 3.90/2.04 3.90/2.04 For Pair COND_CONV(TRUE, x[3]) -> CONV(/(x[3], 2)) the following chains were created: 3.90/2.04 *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: 3.90/2.04 3.90/2.04 (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))), >=)) 3.90/2.04 3.90/2.04 3.90/2.04 3.90/2.04 We simplified constraint (1) using rules (III), (IV) which results in the following new constraint: 3.90/2.04 3.90/2.04 (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))), >=)) 3.90/2.04 3.90/2.04 3.90/2.04 3.90/2.04 We simplified constraint (2) using rule (POLY_CONSTRAINTS) which results in the following new constraint: 3.90/2.04 3.90/2.04 (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) 3.90/2.04 3.90/2.04 3.90/2.04 3.90/2.04 We simplified constraint (3) using rule (IDP_POLY_SIMPLIFY) which results in the following new constraint: 3.90/2.04 3.90/2.04 (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) 3.90/2.04 3.90/2.04 3.90/2.04 3.90/2.04 We simplified constraint (4) using rule (POLY_REMOVE_MIN_MAX) which results in the following new constraint: 3.90/2.04 3.90/2.04 (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) 3.90/2.04 3.90/2.04 3.90/2.04 3.90/2.04 We simplified constraint (5) using rule (IDP_POLY_GCD) which results in the following new constraint: 3.90/2.04 3.90/2.04 (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) 3.90/2.04 3.90/2.04 3.90/2.04 3.90/2.04 3.90/2.04 3.90/2.04 3.90/2.04 3.90/2.04 3.90/2.04 For Pair CONV(x[2]) -> COND_CONV(>(x[2], 0), x[2]) the following chains were created: 3.90/2.04 *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: 3.90/2.04 3.90/2.04 (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])), >=)) 3.90/2.04 3.90/2.04 3.90/2.04 3.90/2.04 We simplified constraint (1) using rule (IV) which results in the following new constraint: 3.90/2.04 3.90/2.04 (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])), >=)) 3.90/2.04 3.90/2.04 3.90/2.04 3.90/2.04 We simplified constraint (2) using rule (POLY_CONSTRAINTS) which results in the following new constraint: 3.90/2.04 3.90/2.04 (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) 3.90/2.04 3.90/2.04 3.90/2.04 3.90/2.04 We simplified constraint (3) using rule (IDP_POLY_SIMPLIFY) which results in the following new constraint: 3.90/2.04 3.90/2.04 (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) 3.90/2.04 3.90/2.04 3.90/2.04 3.90/2.04 We simplified constraint (4) using rule (POLY_REMOVE_MIN_MAX) which results in the following new constraint: 3.90/2.04 3.90/2.04 (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) 3.90/2.04 3.90/2.04 3.90/2.04 3.90/2.04 3.90/2.04 3.90/2.04 3.90/2.04 3.90/2.04 3.90/2.04 To summarize, we get the following constraints P__>=_ for the following pairs. 3.90/2.04 3.90/2.04 *COND_CONV(TRUE, x[3]) -> CONV(/(x[3], 2)) 3.90/2.04 3.90/2.04 *(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) 3.90/2.04 3.90/2.04 3.90/2.04 3.90/2.04 3.90/2.04 *CONV(x[2]) -> COND_CONV(>(x[2], 0), x[2]) 3.90/2.04 3.90/2.04 *(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) 3.90/2.04 3.90/2.04 3.90/2.04 3.90/2.04 3.90/2.04 3.90/2.04 3.90/2.04 3.90/2.04 3.90/2.04 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. 3.90/2.04 3.90/2.04 Using the following integer polynomial ordering the resulting constraints can be solved 3.90/2.04 3.90/2.04 Polynomial interpretation over integers[POLO]: 3.90/2.04 3.90/2.04 POL(TRUE) = 0 3.90/2.04 POL(FALSE) = 0 3.90/2.04 POL(COND_CONV(x_1, x_2)) = [-1] + x_2 3.90/2.04 POL(CONV(x_1)) = [-1] + x_1 3.90/2.04 POL(2) = [2] 3.90/2.04 POL(>(x_1, x_2)) = [-1] 3.90/2.04 POL(0) = 0 3.90/2.04 3.90/2.04 Polynomial Interpretations with Context Sensitive Arithemetic Replacement 3.90/2.04 POL(Term^CSAR-Mode @ Context) 3.90/2.04 3.90/2.04 POL(/(x_1, 2)^1 @ {CONV_1/0}) = max{x_1, [-1]x_1} + [-1] 3.90/2.04 3.90/2.04 3.90/2.04 The following pairs are in P_>: 3.90/2.04 3.90/2.04 3.90/2.04 COND_CONV(TRUE, x[3]) -> CONV(/(x[3], 2)) 3.90/2.04 3.90/2.04 3.90/2.04 The following pairs are in P_bound: 3.90/2.04 3.90/2.04 3.90/2.04 COND_CONV(TRUE, x[3]) -> CONV(/(x[3], 2)) 3.90/2.04 CONV(x[2]) -> COND_CONV(>(x[2], 0), x[2]) 3.90/2.04 3.90/2.04 3.90/2.04 The following pairs are in P_>=: 3.90/2.04 3.90/2.04 3.90/2.04 CONV(x[2]) -> COND_CONV(>(x[2], 0), x[2]) 3.90/2.04 3.90/2.04 3.90/2.04 At least the following rules have been oriented under context sensitive arithmetic replacement: 3.90/2.04 3.90/2.04 /^1 -> 3.90/2.04 3.90/2.04 ---------------------------------------- 3.90/2.04 3.90/2.04 (14) 3.90/2.04 Obligation: 3.90/2.04 IDP problem: 3.90/2.04 The following function symbols are pre-defined: 3.90/2.04 <<< 3.90/2.04 & ~ Bwand: (Integer, Integer) -> Integer 3.90/2.04 >= ~ Ge: (Integer, Integer) -> Boolean 3.90/2.04 / ~ Div: (Integer, Integer) -> Integer 3.90/2.04 | ~ Bwor: (Integer, Integer) -> Integer 3.90/2.04 != ~ Neq: (Integer, Integer) -> Boolean 3.90/2.04 && ~ Land: (Boolean, Boolean) -> Boolean 3.90/2.04 ! ~ Lnot: (Boolean) -> Boolean 3.90/2.04 = ~ Eq: (Integer, Integer) -> Boolean 3.90/2.04 <= ~ Le: (Integer, Integer) -> Boolean 3.90/2.04 ^ ~ Bwxor: (Integer, Integer) -> Integer 3.90/2.04 % ~ Mod: (Integer, Integer) -> Integer 3.90/2.04 > ~ Gt: (Integer, Integer) -> Boolean 3.90/2.04 + ~ Add: (Integer, Integer) -> Integer 3.90/2.04 -1 ~ UnaryMinus: (Integer) -> Integer 3.90/2.04 < ~ Lt: (Integer, Integer) -> Boolean 3.90/2.04 || ~ Lor: (Boolean, Boolean) -> Boolean 3.90/2.04 - ~ Sub: (Integer, Integer) -> Integer 3.90/2.04 ~ ~ Bwnot: (Integer) -> Integer 3.90/2.04 * ~ Mul: (Integer, Integer) -> Integer 3.90/2.04 >>> 3.90/2.04 3.90/2.04 3.90/2.04 The following domains are used: 3.90/2.04 Integer 3.90/2.04 3.90/2.04 R is empty. 3.90/2.04 3.90/2.04 The integer pair graph contains the following rules and edges: 3.90/2.04 (2): CONV(x[2]) -> COND_CONV(x[2] > 0, x[2]) 3.90/2.04 3.90/2.04 3.90/2.04 The set Q consists of the following terms: 3.90/2.04 lastbit(x0) 3.90/2.04 Cond_lastbit(TRUE, x0) 3.90/2.04 conv(x0) 3.90/2.04 Cond_conv(TRUE, x0) 3.90/2.04 3.90/2.04 ---------------------------------------- 3.90/2.04 3.90/2.04 (15) IDependencyGraphProof (EQUIVALENT) 3.90/2.04 The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 0 SCCs with 1 less node. 3.90/2.04 ---------------------------------------- 3.90/2.04 3.90/2.04 (16) 3.90/2.04 TRUE 3.90/2.06 EOF