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, 422 ms] (4) AND (5) IRSwT (6) IntTRSCompressionProof [EQUIVALENT, 0 ms] (7) IRSwT (8) IntTRSUnneededArgumentFilterProof [EQUIVALENT, 0 ms] (9) IRSwT (10) TempFilterProof [SOUND, 6 ms] (11) IntTRS (12) RankingReductionPairProof [EQUIVALENT, 0 ms] (13) YES (14) IRSwT (15) IntTRSCompressionProof [EQUIVALENT, 1 ms] (16) IRSwT (17) IntTRSUnneededArgumentFilterProof [EQUIVALENT, 0 ms] (18) IRSwT (19) TempFilterProof [SOUND, 7 ms] (20) IntTRS (21) RankingReductionPairProof [EQUIVALENT, 4 ms] (22) YES (23) IRSwT (24) IntTRSCompressionProof [EQUIVALENT, 2 ms] (25) IRSwT (26) IntTRSUnneededArgumentFilterProof [EQUIVALENT, 0 ms] (27) IRSwT (28) TempFilterProof [SOUND, 34 ms] (29) IntTRS (30) RankingReductionPairProof [EQUIVALENT, 22 ms] (31) YES (32) IRSwT (33) IntTRSCompressionProof [EQUIVALENT, 3 ms] (34) IRSwT (35) IntTRSUnneededArgumentFilterProof [EQUIVALENT, 0 ms] (36) IRSwT (37) TempFilterProof [SOUND, 5 ms] (38) IntTRS (39) RankingReductionPairProof [EQUIVALENT, 0 ms] (40) YES ---------------------------------------- (0) Obligation: Rules: l0(xHAT0, yHAT0, zHAT0) -> l1(xHATpost, yHATpost, zHATpost) :|: zHAT0 = zHATpost && yHAT0 = yHATpost && xHATpost = -1 + xHAT0 && 1 <= xHAT0 l1(x, x1, x2) -> l0(x3, x4, x5) :|: x2 = x5 && x1 = x4 && x = x3 l2(x6, x7, x8) -> l0(x9, x10, x11) :|: x8 = x11 && x7 = x10 && x6 = x9 && x7 <= 0 l2(x12, x13, x14) -> l3(x15, x16, x17) :|: x14 = x17 && x12 = x15 && x16 = -1 + x13 && 1 <= x13 l3(x18, x19, x20) -> l2(x21, x22, x23) :|: x20 = x23 && x19 = x22 && x18 = x21 l4(x24, x25, x26) -> l2(x27, x28, x29) :|: x26 = x29 && x25 = x28 && x24 = x27 && x26 <= x24 l4(x30, x31, x32) -> l5(x33, x34, x35) :|: x32 = x35 && x31 = x34 && x33 = 1 + x30 && 1 + x30 <= x32 l5(x36, x37, x38) -> l4(x39, x40, x41) :|: x38 = x41 && x37 = x40 && x36 = x39 l6(x42, x43, x44) -> l4(x45, x46, x47) :|: x44 = x47 && x43 = x46 && x42 = x45 && x43 <= x44 l6(x48, x49, x50) -> l7(x51, x52, x53) :|: x50 = x53 && x48 = x51 && x52 = -1 + x49 && 1 + x50 <= x49 l7(x54, x55, x56) -> l6(x57, x58, x59) :|: x56 = x59 && x55 = x58 && x54 = x57 l8(x60, x61, x62) -> l6(x63, x64, x65) :|: x62 = x65 && x61 = x64 && x63 = 0 l9(x66, x67, x68) -> l8(x69, x70, x71) :|: x68 = x71 && x67 = x70 && x66 = x69 Start term: l9(xHAT0, yHAT0, zHAT0) ---------------------------------------- (1) IRSFormatTransformerProof (EQUIVALENT) Reformatted IRS to match normalized format (transformed away non-linear left-hand sides, !=, / and %). ---------------------------------------- (2) Obligation: Rules: l0(xHAT0, yHAT0, zHAT0) -> l1(xHATpost, yHATpost, zHATpost) :|: zHAT0 = zHATpost && yHAT0 = yHATpost && xHATpost = -1 + xHAT0 && 1 <= xHAT0 l1(x, x1, x2) -> l0(x3, x4, x5) :|: x2 = x5 && x1 = x4 && x = x3 l2(x6, x7, x8) -> l0(x9, x10, x11) :|: x8 = x11 && x7 = x10 && x6 = x9 && x7 <= 0 l2(x12, x13, x14) -> l3(x15, x16, x17) :|: x14 = x17 && x12 = x15 && x16 = -1 + x13 && 1 <= x13 l3(x18, x19, x20) -> l2(x21, x22, x23) :|: x20 = x23 && x19 = x22 && x18 = x21 l4(x24, x25, x26) -> l2(x27, x28, x29) :|: x26 = x29 && x25 = x28 && x24 = x27 && x26 <= x24 l4(x30, x31, x32) -> l5(x33, x34, x35) :|: x32 = x35 && x31 = x34 && x33 = 1 + x30 && 1 + x30 <= x32 l5(x36, x37, x38) -> l4(x39, x40, x41) :|: x38 = x41 && x37 = x40 && x36 = x39 l6(x42, x43, x44) -> l4(x45, x46, x47) :|: x44 = x47 && x43 = x46 && x42 = x45 && x43 <= x44 l6(x48, x49, x50) -> l7(x51, x52, x53) :|: x50 = x53 && x48 = x51 && x52 = -1 + x49 && 1 + x50 <= x49 l7(x54, x55, x56) -> l6(x57, x58, x59) :|: x56 = x59 && x55 = x58 && x54 = x57 l8(x60, x61, x62) -> l6(x63, x64, x65) :|: x62 = x65 && x61 = x64 && x63 = 0 l9(x66, x67, x68) -> l8(x69, x70, x71) :|: x68 = x71 && x67 = x70 && x66 = x69 Start term: l9(xHAT0, yHAT0, zHAT0) ---------------------------------------- (3) IRSwTTerminationDigraphProof (EQUIVALENT) Constructed termination digraph! Nodes: (1) l0(xHAT0, yHAT0, zHAT0) -> l1(xHATpost, yHATpost, zHATpost) :|: zHAT0 = zHATpost && yHAT0 = yHATpost && xHATpost = -1 + xHAT0 && 1 <= xHAT0 (2) l1(x, x1, x2) -> l0(x3, x4, x5) :|: x2 = x5 && x1 = x4 && x = x3 (3) l2(x6, x7, x8) -> l0(x9, x10, x11) :|: x8 = x11 && x7 = x10 && x6 = x9 && x7 <= 0 (4) l2(x12, x13, x14) -> l3(x15, x16, x17) :|: x14 = x17 && x12 = x15 && x16 = -1 + x13 && 1 <= x13 (5) l3(x18, x19, x20) -> l2(x21, x22, x23) :|: x20 = x23 && x19 = x22 && x18 = x21 (6) l4(x24, x25, x26) -> l2(x27, x28, x29) :|: x26 = x29 && x25 = x28 && x24 = x27 && x26 <= x24 (7) l4(x30, x31, x32) -> l5(x33, x34, x35) :|: x32 = x35 && x31 = x34 && x33 = 1 + x30 && 1 + x30 <= x32 (8) l5(x36, x37, x38) -> l4(x39, x40, x41) :|: x38 = x41 && x37 = x40 && x36 = x39 (9) l6(x42, x43, x44) -> l4(x45, x46, x47) :|: x44 = x47 && x43 = x46 && x42 = x45 && x43 <= x44 (10) l6(x48, x49, x50) -> l7(x51, x52, x53) :|: x50 = x53 && x48 = x51 && x52 = -1 + x49 && 1 + x50 <= x49 (11) l7(x54, x55, x56) -> l6(x57, x58, x59) :|: x56 = x59 && x55 = x58 && x54 = x57 (12) l8(x60, x61, x62) -> l6(x63, x64, x65) :|: x62 = x65 && x61 = x64 && x63 = 0 (13) l9(x66, x67, x68) -> l8(x69, x70, x71) :|: x68 = x71 && x67 = x70 && x66 = x69 Arcs: (1) -> (2) (2) -> (1) (3) -> (1) (4) -> (5) (5) -> (3), (4) (6) -> (3), (4) (7) -> (8) (8) -> (6), (7) (9) -> (6), (7) (10) -> (11) (11) -> (9), (10) (12) -> (9), (10) (13) -> (12) This digraph is fully evaluated! ---------------------------------------- (4) Complex Obligation (AND) ---------------------------------------- (5) Obligation: Termination digraph: Nodes: (1) l6(x48, x49, x50) -> l7(x51, x52, x53) :|: x50 = x53 && x48 = x51 && x52 = -1 + x49 && 1 + x50 <= x49 (2) l7(x54, x55, x56) -> l6(x57, x58, x59) :|: x56 = x59 && x55 = x58 && x54 = x57 Arcs: (1) -> (2) (2) -> (1) This digraph is fully evaluated! ---------------------------------------- (6) IntTRSCompressionProof (EQUIVALENT) Compressed rules. ---------------------------------------- (7) Obligation: Rules: l6(x48:0, x49:0, x50:0) -> l6(x48:0, -1 + x49:0, x50:0) :|: x49:0 >= 1 + x50:0 ---------------------------------------- (8) IntTRSUnneededArgumentFilterProof (EQUIVALENT) Some arguments are removed because they cannot influence termination. We removed arguments according to the following replacements: l6(x1, x2, x3) -> l6(x2, x3) ---------------------------------------- (9) Obligation: Rules: l6(x49:0, x50:0) -> l6(-1 + x49:0, x50:0) :|: x49:0 >= 1 + x50:0 ---------------------------------------- (10) TempFilterProof (SOUND) Used the following sort dictionary for filtering: l6(INTEGER, INTEGER) Replaced non-predefined constructor symbols by 0. ---------------------------------------- (11) Obligation: Rules: l6(x49:0, x50:0) -> l6(c, x50:0) :|: c = -1 + x49:0 && x49:0 >= 1 + x50:0 ---------------------------------------- (12) RankingReductionPairProof (EQUIVALENT) Interpretation: [ l6 ] = l6_1 + -1*l6_2 The following rules are decreasing: l6(x49:0, x50:0) -> l6(c, x50:0) :|: c = -1 + x49:0 && x49:0 >= 1 + x50:0 The following rules are bounded: l6(x49:0, x50:0) -> l6(c, x50:0) :|: c = -1 + x49:0 && x49:0 >= 1 + x50:0 ---------------------------------------- (13) YES ---------------------------------------- (14) Obligation: Termination digraph: Nodes: (1) l4(x30, x31, x32) -> l5(x33, x34, x35) :|: x32 = x35 && x31 = x34 && x33 = 1 + x30 && 1 + x30 <= x32 (2) l5(x36, x37, x38) -> l4(x39, x40, x41) :|: x38 = x41 && x37 = x40 && x36 = x39 Arcs: (1) -> (2) (2) -> (1) This digraph is fully evaluated! ---------------------------------------- (15) IntTRSCompressionProof (EQUIVALENT) Compressed rules. ---------------------------------------- (16) Obligation: Rules: l4(x30:0, x31:0, x32:0) -> l4(1 + x30:0, x31:0, x32:0) :|: x32:0 >= 1 + x30:0 ---------------------------------------- (17) IntTRSUnneededArgumentFilterProof (EQUIVALENT) Some arguments are removed because they cannot influence termination. We removed arguments according to the following replacements: l4(x1, x2, x3) -> l4(x1, x3) ---------------------------------------- (18) Obligation: Rules: l4(x30:0, x32:0) -> l4(1 + x30:0, x32:0) :|: x32:0 >= 1 + x30:0 ---------------------------------------- (19) TempFilterProof (SOUND) Used the following sort dictionary for filtering: l4(INTEGER, INTEGER) Replaced non-predefined constructor symbols by 0. ---------------------------------------- (20) Obligation: Rules: l4(x30:0, x32:0) -> l4(c, x32:0) :|: c = 1 + x30:0 && x32:0 >= 1 + x30:0 ---------------------------------------- (21) RankingReductionPairProof (EQUIVALENT) Interpretation: [ l4 ] = l4_2 + -1*l4_1 The following rules are decreasing: l4(x30:0, x32:0) -> l4(c, x32:0) :|: c = 1 + x30:0 && x32:0 >= 1 + x30:0 The following rules are bounded: l4(x30:0, x32:0) -> l4(c, x32:0) :|: c = 1 + x30:0 && x32:0 >= 1 + x30:0 ---------------------------------------- (22) YES ---------------------------------------- (23) Obligation: Termination digraph: Nodes: (1) l2(x12, x13, x14) -> l3(x15, x16, x17) :|: x14 = x17 && x12 = x15 && x16 = -1 + x13 && 1 <= x13 (2) l3(x18, x19, x20) -> l2(x21, x22, x23) :|: x20 = x23 && x19 = x22 && x18 = x21 Arcs: (1) -> (2) (2) -> (1) This digraph is fully evaluated! ---------------------------------------- (24) IntTRSCompressionProof (EQUIVALENT) Compressed rules. ---------------------------------------- (25) Obligation: Rules: l2(x12:0, x13:0, x14:0) -> l2(x12:0, -1 + x13:0, x14:0) :|: x13:0 > 0 ---------------------------------------- (26) IntTRSUnneededArgumentFilterProof (EQUIVALENT) Some arguments are removed because they cannot influence termination. We removed arguments according to the following replacements: l2(x1, x2, x3) -> l2(x2) ---------------------------------------- (27) Obligation: Rules: l2(x13:0) -> l2(-1 + x13:0) :|: x13:0 > 0 ---------------------------------------- (28) TempFilterProof (SOUND) Used the following sort dictionary for filtering: l2(INTEGER) Replaced non-predefined constructor symbols by 0. ---------------------------------------- (29) Obligation: Rules: l2(x13:0) -> l2(c) :|: c = -1 + x13:0 && x13:0 > 0 ---------------------------------------- (30) RankingReductionPairProof (EQUIVALENT) Interpretation: [ l2 ] = l2_1 The following rules are decreasing: l2(x13:0) -> l2(c) :|: c = -1 + x13:0 && x13:0 > 0 The following rules are bounded: l2(x13:0) -> l2(c) :|: c = -1 + x13:0 && x13:0 > 0 ---------------------------------------- (31) YES ---------------------------------------- (32) Obligation: Termination digraph: Nodes: (1) l0(xHAT0, yHAT0, zHAT0) -> l1(xHATpost, yHATpost, zHATpost) :|: zHAT0 = zHATpost && yHAT0 = yHATpost && xHATpost = -1 + xHAT0 && 1 <= xHAT0 (2) l1(x, x1, x2) -> l0(x3, x4, x5) :|: x2 = x5 && x1 = x4 && x = x3 Arcs: (1) -> (2) (2) -> (1) This digraph is fully evaluated! ---------------------------------------- (33) IntTRSCompressionProof (EQUIVALENT) Compressed rules. ---------------------------------------- (34) Obligation: Rules: l0(xHAT0:0, x4:0, x5:0) -> l0(-1 + xHAT0:0, x4:0, x5:0) :|: xHAT0:0 > 0 ---------------------------------------- (35) IntTRSUnneededArgumentFilterProof (EQUIVALENT) Some arguments are removed because they cannot influence termination. We removed arguments according to the following replacements: l0(x1, x2, x3) -> l0(x1) ---------------------------------------- (36) Obligation: Rules: l0(xHAT0:0) -> l0(-1 + xHAT0:0) :|: xHAT0:0 > 0 ---------------------------------------- (37) TempFilterProof (SOUND) Used the following sort dictionary for filtering: l0(INTEGER) Replaced non-predefined constructor symbols by 0. ---------------------------------------- (38) Obligation: Rules: l0(xHAT0:0) -> l0(c) :|: c = -1 + xHAT0:0 && xHAT0:0 > 0 ---------------------------------------- (39) RankingReductionPairProof (EQUIVALENT) Interpretation: [ l0 ] = l0_1 The following rules are decreasing: l0(xHAT0:0) -> l0(c) :|: c = -1 + xHAT0:0 && xHAT0:0 > 0 The following rules are bounded: l0(xHAT0:0) -> l0(c) :|: c = -1 + xHAT0:0 && xHAT0:0 > 0 ---------------------------------------- (40) YES