YES proof of prog.inttrs # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty Termination of the given IRSwT could be proven: (0) IRSwT (1) IRSFormatTransformerProof [EQUIVALENT, 0 ms] (2) IRSwT (3) IRSwTTerminationDigraphProof [EQUIVALENT, 139 ms] (4) IRSwT (5) IntTRSCompressionProof [EQUIVALENT, 44 ms] (6) IRSwT (7) TempFilterProof [SOUND, 51 ms] (8) IntTRS (9) PolynomialOrderProcessor [EQUIVALENT, 0 ms] (10) IntTRS (11) RankingReductionPairProof [EQUIVALENT, 0 ms] (12) YES ---------------------------------------- (0) Obligation: Rules: l0(xHAT0, yHAT0) -> l1(xHATpost, yHATpost) :|: yHATpost = 1 + yHAT0 && xHATpost = -1 + xHAT0 && yHAT0 <= 0 l0(x, x1) -> l2(x2, x3) :|: x = x2 && x3 = -1 + x1 && 1 <= x1 l2(x4, x5) -> l0(x6, x7) :|: x5 = x7 && x4 = x6 l3(x8, x9) -> l1(x10, x11) :|: x9 = x11 && x8 = x10 l1(x12, x13) -> l0(x14, x15) :|: x12 = x14 && x15 = x12 && 1 <= x12 l4(x16, x17) -> l3(x18, x19) :|: x17 = x19 && x16 = x18 Start term: l4(xHAT0, yHAT0) ---------------------------------------- (1) IRSFormatTransformerProof (EQUIVALENT) Reformatted IRS to match normalized format (transformed away non-linear left-hand sides, !=, / and %). ---------------------------------------- (2) Obligation: Rules: l0(xHAT0, yHAT0) -> l1(xHATpost, yHATpost) :|: yHATpost = 1 + yHAT0 && xHATpost = -1 + xHAT0 && yHAT0 <= 0 l0(x, x1) -> l2(x2, x3) :|: x = x2 && x3 = -1 + x1 && 1 <= x1 l2(x4, x5) -> l0(x6, x7) :|: x5 = x7 && x4 = x6 l3(x8, x9) -> l1(x10, x11) :|: x9 = x11 && x8 = x10 l1(x12, x13) -> l0(x14, x15) :|: x12 = x14 && x15 = x12 && 1 <= x12 l4(x16, x17) -> l3(x18, x19) :|: x17 = x19 && x16 = x18 Start term: l4(xHAT0, yHAT0) ---------------------------------------- (3) IRSwTTerminationDigraphProof (EQUIVALENT) Constructed termination digraph! Nodes: (1) l0(xHAT0, yHAT0) -> l1(xHATpost, yHATpost) :|: yHATpost = 1 + yHAT0 && xHATpost = -1 + xHAT0 && yHAT0 <= 0 (2) l0(x, x1) -> l2(x2, x3) :|: x = x2 && x3 = -1 + x1 && 1 <= x1 (3) l2(x4, x5) -> l0(x6, x7) :|: x5 = x7 && x4 = x6 (4) l3(x8, x9) -> l1(x10, x11) :|: x9 = x11 && x8 = x10 (5) l1(x12, x13) -> l0(x14, x15) :|: x12 = x14 && x15 = x12 && 1 <= x12 (6) l4(x16, x17) -> l3(x18, x19) :|: x17 = x19 && x16 = x18 Arcs: (1) -> (5) (2) -> (3) (3) -> (1), (2) (4) -> (5) (5) -> (2) (6) -> (4) This digraph is fully evaluated! ---------------------------------------- (4) Obligation: Termination digraph: Nodes: (1) l0(xHAT0, yHAT0) -> l1(xHATpost, yHATpost) :|: yHATpost = 1 + yHAT0 && xHATpost = -1 + xHAT0 && yHAT0 <= 0 (2) l2(x4, x5) -> l0(x6, x7) :|: x5 = x7 && x4 = x6 (3) l0(x, x1) -> l2(x2, x3) :|: x = x2 && x3 = -1 + x1 && 1 <= x1 (4) l1(x12, x13) -> l0(x14, x15) :|: x12 = x14 && x15 = x12 && 1 <= x12 Arcs: (1) -> (4) (2) -> (1), (3) (3) -> (2) (4) -> (3) This digraph is fully evaluated! ---------------------------------------- (5) IntTRSCompressionProof (EQUIVALENT) Compressed rules. ---------------------------------------- (6) Obligation: Rules: l0(x2:0, x1:0) -> l0(x2:0, -1 + x1:0) :|: x1:0 > 0 l0(xHAT0:0, yHAT0:0) -> l0(-1 + xHAT0:0, -1 + xHAT0:0) :|: yHAT0:0 < 1 && xHAT0:0 > 1 ---------------------------------------- (7) TempFilterProof (SOUND) Used the following sort dictionary for filtering: l0(VARIABLE, INTEGER) Replaced non-predefined constructor symbols by 0. ---------------------------------------- (8) Obligation: Rules: l0(x2:0, x1:0) -> l0(x2:0, c) :|: c = -1 + x1:0 && x1:0 > 0 l0(xHAT0:0, yHAT0:0) -> l0(c1, c2) :|: c2 = -1 + xHAT0:0 && c1 = -1 + xHAT0:0 && (yHAT0:0 < 1 && xHAT0:0 > 1) ---------------------------------------- (9) PolynomialOrderProcessor (EQUIVALENT) Found the following polynomial interpretation: [l0(x, x1)] = -1 + x The following rules are decreasing: l0(xHAT0:0, yHAT0:0) -> l0(c1, c2) :|: c2 = -1 + xHAT0:0 && c1 = -1 + xHAT0:0 && (yHAT0:0 < 1 && xHAT0:0 > 1) The following rules are bounded: l0(xHAT0:0, yHAT0:0) -> l0(c1, c2) :|: c2 = -1 + xHAT0:0 && c1 = -1 + xHAT0:0 && (yHAT0:0 < 1 && xHAT0:0 > 1) ---------------------------------------- (10) Obligation: Rules: l0(x2:0, x1:0) -> l0(x2:0, c) :|: c = -1 + x1:0 && x1:0 > 0 ---------------------------------------- (11) RankingReductionPairProof (EQUIVALENT) Interpretation: [ l0 ] = l0_2 The following rules are decreasing: l0(x2:0, x1:0) -> l0(x2:0, c) :|: c = -1 + x1:0 && x1:0 > 0 The following rules are bounded: l0(x2:0, x1:0) -> l0(x2:0, c) :|: c = -1 + x1:0 && x1:0 > 0 ---------------------------------------- (12) YES