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, 557 ms] (4) AND (5) IRSwT (6) IntTRSCompressionProof [EQUIVALENT, 8 ms] (7) IRSwT (8) TempFilterProof [SOUND, 31 ms] (9) IntTRS (10) RankingReductionPairProof [EQUIVALENT, 13 ms] (11) YES (12) IRSwT (13) IntTRSCompressionProof [EQUIVALENT, 5 ms] (14) IRSwT (15) IRSwTChainingProof [EQUIVALENT, 0 ms] (16) IRSwT (17) IRSwTTerminationDigraphProof [EQUIVALENT, 0 ms] (18) IRSwT (19) IntTRSCompressionProof [EQUIVALENT, 0 ms] (20) IRSwT (21) TempFilterProof [SOUND, 11 ms] (22) IntTRS (23) RankingReductionPairProof [EQUIVALENT, 0 ms] (24) YES ---------------------------------------- (0) Obligation: Rules: f1_0_main_Load(arg1, arg2, arg3, arg4, arg5) -> f1_0_main_Load'(arg1P, arg2P, arg3P, arg4P, arg5P) :|: -1 <= arg2 - 1 && x23 <= 200 * arg2 && 0 <= arg1 - 1 && arg1 = arg1P && arg2 = arg2P f1_0_main_Load'(x, x1, x2, x3, x4) -> f1870_0_rec_LE(x5, x6, x7, x8, x9) :|: 0 = x9 && x1 = x8 && 100 * x1 + x6 = x7 && 100 * x1 = x5 && 0 <= 200 * x1 - 13 * x6 && 200 * x1 - 13 * x6 <= 12 && 0 <= x - 1 && x6 <= 200 * x1 && -1 <= x1 - 1 f1870_0_rec_LE(x10, x11, x12, x15, x16) -> f1870_0_rec_LE(x17, x18, x19, x22, x24) :|: x16 = x24 && x15 = x22 && x10 + x11 - 1 = x19 && x11 - 1 = x18 && x10 = x17 && x15 <= x16 && x11 - 1 <= x11 - 1 && -1 <= x15 - 1 && 0 <= x12 - 1 f1870_0_rec_LE(x25, x26, x27, x28, x29) -> f1870_0_rec_LE(x30, x31, x32, x33, x34) :|: 1 <= x28 - 1 && x29 + 1 <= x28 - 1 && 0 <= x27 - 1 && -1 <= x29 - 1 && -1 <= x35 - 1 && -1 <= x36 - 1 && x35 * x36 <= 9 && x29 + 2 <= x28 && x26 - 1 <= x26 - 1 && x25 = x30 && x26 - 1 = x31 && x25 + x26 - 1 = x32 && x28 = x33 && x29 + 2 = x34 f1870_0_rec_LE(x37, x38, x39, x40, x41) -> f1870_0_rec_LE(x42, x43, x44, x45, x46) :|: 1 <= x40 - 1 && x41 + 1 <= x40 - 1 && 0 <= x39 - 1 && -1 <= x41 - 1 && -1 <= x47 - 1 && -1 <= x48 - 1 && 9 <= x47 * x48 - 1 && x41 + 2 <= x40 && x37 - 1 <= x37 - 1 && x37 - 1 = x42 && x38 = x43 && x37 - 1 + x38 = x44 && x40 = x45 && x41 + 2 = x46 __init(x49, x50, x51, x52, x53) -> f1_0_main_Load(x54, x55, x56, x57, x58) :|: 0 <= 0 Start term: __init(arg1, arg2, arg3, arg4, arg5) ---------------------------------------- (1) IRSFormatTransformerProof (EQUIVALENT) Reformatted IRS to match normalized format (transformed away non-linear left-hand sides, !=, / and %). ---------------------------------------- (2) Obligation: Rules: f1_0_main_Load(arg1, arg2, arg3, arg4, arg5) -> f1_0_main_Load'(arg1P, arg2P, arg3P, arg4P, arg5P) :|: -1 <= arg2 - 1 && x23 <= 200 * arg2 && 0 <= arg1 - 1 && arg1 = arg1P && arg2 = arg2P f1_0_main_Load'(x, x1, x2, x3, x4) -> f1870_0_rec_LE(x5, x6, x7, x8, x9) :|: 0 = x9 && x1 = x8 && 100 * x1 + x6 = x7 && 100 * x1 = x5 && 0 <= 200 * x1 - 13 * x6 && 200 * x1 - 13 * x6 <= 12 && 0 <= x - 1 && x6 <= 200 * x1 && -1 <= x1 - 1 f1870_0_rec_LE(x10, x11, x12, x15, x16) -> f1870_0_rec_LE(x17, x18, x19, x22, x24) :|: x16 = x24 && x15 = x22 && x10 + x11 - 1 = x19 && x11 - 1 = x18 && x10 = x17 && x15 <= x16 && x11 - 1 <= x11 - 1 && -1 <= x15 - 1 && 0 <= x12 - 1 f1870_0_rec_LE(x25, x26, x27, x28, x29) -> f1870_0_rec_LE(x30, x31, x32, x33, x34) :|: 1 <= x28 - 1 && x29 + 1 <= x28 - 1 && 0 <= x27 - 1 && -1 <= x29 - 1 && -1 <= x35 - 1 && -1 <= x36 - 1 && x35 * x36 <= 9 && x29 + 2 <= x28 && x26 - 1 <= x26 - 1 && x25 = x30 && x26 - 1 = x31 && x25 + x26 - 1 = x32 && x28 = x33 && x29 + 2 = x34 f1870_0_rec_LE(x37, x38, x39, x40, x41) -> f1870_0_rec_LE(x42, x43, x44, x45, x46) :|: 1 <= x40 - 1 && x41 + 1 <= x40 - 1 && 0 <= x39 - 1 && -1 <= x41 - 1 && -1 <= x47 - 1 && -1 <= x48 - 1 && 9 <= x47 * x48 - 1 && x41 + 2 <= x40 && x37 - 1 <= x37 - 1 && x37 - 1 = x42 && x38 = x43 && x37 - 1 + x38 = x44 && x40 = x45 && x41 + 2 = x46 __init(x49, x50, x51, x52, x53) -> f1_0_main_Load(x54, x55, x56, x57, x58) :|: 0 <= 0 Start term: __init(arg1, arg2, arg3, arg4, arg5) ---------------------------------------- (3) IRSwTTerminationDigraphProof (EQUIVALENT) Constructed termination digraph! Nodes: (1) f1_0_main_Load(arg1, arg2, arg3, arg4, arg5) -> f1_0_main_Load'(arg1P, arg2P, arg3P, arg4P, arg5P) :|: -1 <= arg2 - 1 && x23 <= 200 * arg2 && 0 <= arg1 - 1 && arg1 = arg1P && arg2 = arg2P (2) f1_0_main_Load'(x, x1, x2, x3, x4) -> f1870_0_rec_LE(x5, x6, x7, x8, x9) :|: 0 = x9 && x1 = x8 && 100 * x1 + x6 = x7 && 100 * x1 = x5 && 0 <= 200 * x1 - 13 * x6 && 200 * x1 - 13 * x6 <= 12 && 0 <= x - 1 && x6 <= 200 * x1 && -1 <= x1 - 1 (3) f1870_0_rec_LE(x10, x11, x12, x15, x16) -> f1870_0_rec_LE(x17, x18, x19, x22, x24) :|: x16 = x24 && x15 = x22 && x10 + x11 - 1 = x19 && x11 - 1 = x18 && x10 = x17 && x15 <= x16 && x11 - 1 <= x11 - 1 && -1 <= x15 - 1 && 0 <= x12 - 1 (4) f1870_0_rec_LE(x25, x26, x27, x28, x29) -> f1870_0_rec_LE(x30, x31, x32, x33, x34) :|: 1 <= x28 - 1 && x29 + 1 <= x28 - 1 && 0 <= x27 - 1 && -1 <= x29 - 1 && -1 <= x35 - 1 && -1 <= x36 - 1 && x35 * x36 <= 9 && x29 + 2 <= x28 && x26 - 1 <= x26 - 1 && x25 = x30 && x26 - 1 = x31 && x25 + x26 - 1 = x32 && x28 = x33 && x29 + 2 = x34 (5) f1870_0_rec_LE(x37, x38, x39, x40, x41) -> f1870_0_rec_LE(x42, x43, x44, x45, x46) :|: 1 <= x40 - 1 && x41 + 1 <= x40 - 1 && 0 <= x39 - 1 && -1 <= x41 - 1 && -1 <= x47 - 1 && -1 <= x48 - 1 && 9 <= x47 * x48 - 1 && x41 + 2 <= x40 && x37 - 1 <= x37 - 1 && x37 - 1 = x42 && x38 = x43 && x37 - 1 + x38 = x44 && x40 = x45 && x41 + 2 = x46 (6) __init(x49, x50, x51, x52, x53) -> f1_0_main_Load(x54, x55, x56, x57, x58) :|: 0 <= 0 Arcs: (1) -> (2) (2) -> (4), (5) (3) -> (3) (4) -> (3), (4), (5) (5) -> (3), (4), (5) (6) -> (1) This digraph is fully evaluated! ---------------------------------------- (4) Complex Obligation (AND) ---------------------------------------- (5) Obligation: Termination digraph: Nodes: (1) f1870_0_rec_LE(x25, x26, x27, x28, x29) -> f1870_0_rec_LE(x30, x31, x32, x33, x34) :|: 1 <= x28 - 1 && x29 + 1 <= x28 - 1 && 0 <= x27 - 1 && -1 <= x29 - 1 && -1 <= x35 - 1 && -1 <= x36 - 1 && x35 * x36 <= 9 && x29 + 2 <= x28 && x26 - 1 <= x26 - 1 && x25 = x30 && x26 - 1 = x31 && x25 + x26 - 1 = x32 && x28 = x33 && x29 + 2 = x34 (2) f1870_0_rec_LE(x37, x38, x39, x40, x41) -> f1870_0_rec_LE(x42, x43, x44, x45, x46) :|: 1 <= x40 - 1 && x41 + 1 <= x40 - 1 && 0 <= x39 - 1 && -1 <= x41 - 1 && -1 <= x47 - 1 && -1 <= x48 - 1 && 9 <= x47 * x48 - 1 && x41 + 2 <= x40 && x37 - 1 <= x37 - 1 && x37 - 1 = x42 && x38 = x43 && x37 - 1 + x38 = x44 && x40 = x45 && x41 + 2 = x46 Arcs: (1) -> (1), (2) (2) -> (1), (2) This digraph is fully evaluated! ---------------------------------------- (6) IntTRSCompressionProof (EQUIVALENT) Compressed rules. ---------------------------------------- (7) Obligation: Rules: f1870_0_rec_LE(x25:0, x26:0, x27:0, x28:0, x29:0) -> f1870_0_rec_LE(x25:0, x26:0 - 1, x25:0 + x26:0 - 1, x28:0, x29:0 + 2) :|: x35:0 * x36:0 <= 9 && x29:0 + 2 <= x28:0 && x36:0 > -1 && x35:0 > -1 && x29:0 > -1 && x27:0 > 0 && x29:0 + 1 <= x28:0 - 1 && x28:0 > 1 f1870_0_rec_LE(x37:0, x38:0, x39:0, x40:0, x41:0) -> f1870_0_rec_LE(x37:0 - 1, x38:0, x37:0 - 1 + x38:0, x40:0, x41:0 + 2) :|: x47:0 * x48:0 >= 10 && x41:0 + 2 <= x40:0 && x48:0 > -1 && x47:0 > -1 && x41:0 > -1 && x39:0 > 0 && x41:0 + 1 <= x40:0 - 1 && x40:0 > 1 ---------------------------------------- (8) TempFilterProof (SOUND) Used the following sort dictionary for filtering: f1870_0_rec_LE(VARIABLE, VARIABLE, INTEGER, INTEGER, INTEGER) Replaced non-predefined constructor symbols by 0. ---------------------------------------- (9) Obligation: Rules: f1870_0_rec_LE(x25:0, x26:0, x27:0, x28:0, x29:0) -> f1870_0_rec_LE(x25:0, c, c1, x28:0, c2) :|: c2 = x29:0 + 2 && (c1 = x25:0 + x26:0 - 1 && c = x26:0 - 1) && (x35:0 * x36:0 <= 9 && x29:0 + 2 <= x28:0 && x36:0 > -1 && x35:0 > -1 && x29:0 > -1 && x27:0 > 0 && x29:0 + 1 <= x28:0 - 1 && x28:0 > 1) f1870_0_rec_LE(x37:0, x38:0, x39:0, x40:0, x41:0) -> f1870_0_rec_LE(c3, x38:0, c4, x40:0, c5) :|: c5 = x41:0 + 2 && (c4 = x37:0 - 1 + x38:0 && c3 = x37:0 - 1) && (x47:0 * x48:0 >= 10 && x41:0 + 2 <= x40:0 && x48:0 > -1 && x47:0 > -1 && x41:0 > -1 && x39:0 > 0 && x41:0 + 1 <= x40:0 - 1 && x40:0 > 1) ---------------------------------------- (10) RankingReductionPairProof (EQUIVALENT) Interpretation: [ f1870_0_rec_LE ] = -1/2*f1870_0_rec_LE_5 + 1/2*f1870_0_rec_LE_4 The following rules are decreasing: f1870_0_rec_LE(x25:0, x26:0, x27:0, x28:0, x29:0) -> f1870_0_rec_LE(x25:0, c, c1, x28:0, c2) :|: c2 = x29:0 + 2 && (c1 = x25:0 + x26:0 - 1 && c = x26:0 - 1) && (x35:0 * x36:0 <= 9 && x29:0 + 2 <= x28:0 && x36:0 > -1 && x35:0 > -1 && x29:0 > -1 && x27:0 > 0 && x29:0 + 1 <= x28:0 - 1 && x28:0 > 1) f1870_0_rec_LE(x37:0, x38:0, x39:0, x40:0, x41:0) -> f1870_0_rec_LE(c3, x38:0, c4, x40:0, c5) :|: c5 = x41:0 + 2 && (c4 = x37:0 - 1 + x38:0 && c3 = x37:0 - 1) && (x47:0 * x48:0 >= 10 && x41:0 + 2 <= x40:0 && x48:0 > -1 && x47:0 > -1 && x41:0 > -1 && x39:0 > 0 && x41:0 + 1 <= x40:0 - 1 && x40:0 > 1) The following rules are bounded: f1870_0_rec_LE(x25:0, x26:0, x27:0, x28:0, x29:0) -> f1870_0_rec_LE(x25:0, c, c1, x28:0, c2) :|: c2 = x29:0 + 2 && (c1 = x25:0 + x26:0 - 1 && c = x26:0 - 1) && (x35:0 * x36:0 <= 9 && x29:0 + 2 <= x28:0 && x36:0 > -1 && x35:0 > -1 && x29:0 > -1 && x27:0 > 0 && x29:0 + 1 <= x28:0 - 1 && x28:0 > 1) f1870_0_rec_LE(x37:0, x38:0, x39:0, x40:0, x41:0) -> f1870_0_rec_LE(c3, x38:0, c4, x40:0, c5) :|: c5 = x41:0 + 2 && (c4 = x37:0 - 1 + x38:0 && c3 = x37:0 - 1) && (x47:0 * x48:0 >= 10 && x41:0 + 2 <= x40:0 && x48:0 > -1 && x47:0 > -1 && x41:0 > -1 && x39:0 > 0 && x41:0 + 1 <= x40:0 - 1 && x40:0 > 1) ---------------------------------------- (11) YES ---------------------------------------- (12) Obligation: Termination digraph: Nodes: (1) f1870_0_rec_LE(x10, x11, x12, x15, x16) -> f1870_0_rec_LE(x17, x18, x19, x22, x24) :|: x16 = x24 && x15 = x22 && x10 + x11 - 1 = x19 && x11 - 1 = x18 && x10 = x17 && x15 <= x16 && x11 - 1 <= x11 - 1 && -1 <= x15 - 1 && 0 <= x12 - 1 Arcs: (1) -> (1) This digraph is fully evaluated! ---------------------------------------- (13) IntTRSCompressionProof (EQUIVALENT) Compressed rules. ---------------------------------------- (14) Obligation: Rules: f1870_0_rec_LE(x10:0, x11:0, x12:0, x15:0, x16:0) -> f1870_0_rec_LE(x10:0, x11:0 - 1, x10:0 + x11:0 - 1, x15:0, x16:0) :|: x15:0 > -1 && x16:0 >= x15:0 && x12:0 > 0 ---------------------------------------- (15) IRSwTChainingProof (EQUIVALENT) Chaining! ---------------------------------------- (16) Obligation: Rules: f1870_0_rec_LE(x, x1, x2, x3, x4) -> f1870_0_rec_LE(x, x1 + -2, x + x1 + -2, x3, x4) :|: TRUE && x3 >= 0 && x4 + -1 * x3 >= 0 && x2 >= 1 && x + x1 >= 2 ---------------------------------------- (17) IRSwTTerminationDigraphProof (EQUIVALENT) Constructed termination digraph! Nodes: (1) f1870_0_rec_LE(x, x1, x2, x3, x4) -> f1870_0_rec_LE(x, x1 + -2, x + x1 + -2, x3, x4) :|: TRUE && x3 >= 0 && x4 + -1 * x3 >= 0 && x2 >= 1 && x + x1 >= 2 Arcs: (1) -> (1) This digraph is fully evaluated! ---------------------------------------- (18) Obligation: Termination digraph: Nodes: (1) f1870_0_rec_LE(x, x1, x2, x3, x4) -> f1870_0_rec_LE(x, x1 + -2, x + x1 + -2, x3, x4) :|: TRUE && x3 >= 0 && x4 + -1 * x3 >= 0 && x2 >= 1 && x + x1 >= 2 Arcs: (1) -> (1) This digraph is fully evaluated! ---------------------------------------- (19) IntTRSCompressionProof (EQUIVALENT) Compressed rules. ---------------------------------------- (20) Obligation: Rules: f1870_0_rec_LE(x:0, x1:0, x2:0, x3:0, x4:0) -> f1870_0_rec_LE(x:0, x1:0 - 2, x:0 + x1:0 - 2, x3:0, x4:0) :|: x2:0 > 0 && x:0 + x1:0 >= 2 && x3:0 > -1 && x4:0 + -1 * x3:0 >= 0 ---------------------------------------- (21) TempFilterProof (SOUND) Used the following sort dictionary for filtering: f1870_0_rec_LE(INTEGER, INTEGER, INTEGER, INTEGER, INTEGER) Replaced non-predefined constructor symbols by 0. ---------------------------------------- (22) Obligation: Rules: f1870_0_rec_LE(x:0, x1:0, x2:0, x3:0, x4:0) -> f1870_0_rec_LE(x:0, c, c1, x3:0, x4:0) :|: c1 = x:0 + x1:0 - 2 && c = x1:0 - 2 && (x2:0 > 0 && x:0 + x1:0 >= 2 && x3:0 > -1 && x4:0 + -1 * x3:0 >= 0) ---------------------------------------- (23) RankingReductionPairProof (EQUIVALENT) Interpretation: [ f1870_0_rec_LE ] = 1/2*f1870_0_rec_LE_1 + 1/2*f1870_0_rec_LE_2 The following rules are decreasing: f1870_0_rec_LE(x:0, x1:0, x2:0, x3:0, x4:0) -> f1870_0_rec_LE(x:0, c, c1, x3:0, x4:0) :|: c1 = x:0 + x1:0 - 2 && c = x1:0 - 2 && (x2:0 > 0 && x:0 + x1:0 >= 2 && x3:0 > -1 && x4:0 + -1 * x3:0 >= 0) The following rules are bounded: f1870_0_rec_LE(x:0, x1:0, x2:0, x3:0, x4:0) -> f1870_0_rec_LE(x:0, c, c1, x3:0, x4:0) :|: c1 = x:0 + x1:0 - 2 && c = x1:0 - 2 && (x2:0 > 0 && x:0 + x1:0 >= 2 && x3:0 > -1 && x4:0 + -1 * x3:0 >= 0) ---------------------------------------- (24) YES