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, 843 ms] (4) IRSwT (5) IntTRSCompressionProof [EQUIVALENT, 28 ms] (6) IRSwT (7) IntTRSUnneededArgumentFilterProof [EQUIVALENT, 0 ms] (8) IRSwT (9) TempFilterProof [SOUND, 35 ms] (10) IntTRS (11) PolynomialOrderProcessor [EQUIVALENT, 0 ms] (12) YES ---------------------------------------- (0) Obligation: Rules: l0(Result_4HAT0, ___cil_tmp2_6HAT0, ___cil_tmp6_12HAT0, maxRetries_9HAT0, retryCount_10HAT0, selected_11HAT0, x_5HAT0) -> l1(Result_4HATpost, ___cil_tmp2_6HATpost, ___cil_tmp6_12HATpost, maxRetries_9HATpost, retryCount_10HATpost, selected_11HATpost, x_5HATpost) :|: ___cil_tmp2_6HATpost = x_5HAT0 && Result_4HAT1 = ___cil_tmp2_6HATpost && selected_11HATpost = Result_4HAT1 && Result_4HATpost = Result_4HATpost && ___cil_tmp6_12HAT0 = ___cil_tmp6_12HATpost && maxRetries_9HAT0 = maxRetries_9HATpost && retryCount_10HAT0 = retryCount_10HATpost && x_5HAT0 = x_5HATpost l2(x, x1, x2, x3, x4, x5, x6) -> l3(x7, x8, x9, x10, x11, x12, x13) :|: x8 = x6 && x14 = x8 && x12 = x14 && x7 = x7 && x11 = 1 + x4 && x2 = x9 && x3 = x10 && x6 = x13 l3(x15, x16, x17, x18, x19, x20, x21) -> l5(x22, x23, x24, x25, x26, x27, x28) :|: x21 = x28 && x20 = x27 && x19 = x26 && x18 = x25 && x17 = x24 && x16 = x23 && x15 = x22 && 1 + x20 <= 0 l3(x29, x30, x31, x32, x33, x34, x35) -> l5(x36, x37, x38, x39, x40, x41, x42) :|: x35 = x42 && x34 = x41 && x33 = x40 && x32 = x39 && x31 = x38 && x30 = x37 && x29 = x36 && 1 <= x34 l5(x43, x44, x45, x46, x47, x48, x49) -> l4(x50, x51, x52, x53, x54, x55, x56) :|: x49 = x56 && x48 = x55 && x47 = x54 && x46 = x53 && x44 = x51 && x50 = x52 && x52 = x48 l3(x57, x58, x59, x60, x61, x62, x63) -> l6(x64, x65, x66, x67, x68, x69, x70) :|: x63 = x70 && x62 = x69 && x61 = x68 && x60 = x67 && x58 = x65 && x64 = x66 && x66 = x62 && x60 - x61 <= 0 && 0 <= x62 && x62 <= 0 l3(x71, x72, x73, x74, x75, x76, x77) -> l1(x78, x79, x80, x81, x82, x83, x84) :|: x76 <= 0 && 0 <= x76 && 0 <= -1 + x74 - x75 && x79 = x77 && x85 = x79 && x83 = x85 && x78 = x78 && x73 = x80 && x74 = x81 && x75 = x82 && x77 = x84 l1(x86, x87, x88, x89, x90, x91, x92) -> l3(x93, x94, x95, x96, x97, x98, x99) :|: x92 = x99 && x91 = x98 && x89 = x96 && x88 = x95 && x87 = x94 && x86 = x93 && x97 = 1 + x90 l7(x100, x101, x102, x103, x104, x105, x106) -> l3(x107, x108, x109, x110, x111, x112, x113) :|: x106 = x113 && x102 = x109 && x101 = x108 && x100 = x107 && x112 = 0 && x111 = 0 && x110 = 400 l8(x114, x115, x116, x117, x118, x119, x120) -> l7(x121, x122, x123, x124, x125, x126, x127) :|: x120 = x127 && x119 = x126 && x118 = x125 && x117 = x124 && x116 = x123 && x115 = x122 && x114 = x121 Start term: l8(Result_4HAT0, ___cil_tmp2_6HAT0, ___cil_tmp6_12HAT0, maxRetries_9HAT0, retryCount_10HAT0, selected_11HAT0, x_5HAT0) ---------------------------------------- (1) IRSFormatTransformerProof (EQUIVALENT) Reformatted IRS to match normalized format (transformed away non-linear left-hand sides, !=, / and %). ---------------------------------------- (2) Obligation: Rules: l0(Result_4HAT0, ___cil_tmp2_6HAT0, ___cil_tmp6_12HAT0, maxRetries_9HAT0, retryCount_10HAT0, selected_11HAT0, x_5HAT0) -> l1(Result_4HATpost, ___cil_tmp2_6HATpost, ___cil_tmp6_12HATpost, maxRetries_9HATpost, retryCount_10HATpost, selected_11HATpost, x_5HATpost) :|: ___cil_tmp2_6HATpost = x_5HAT0 && Result_4HAT1 = ___cil_tmp2_6HATpost && selected_11HATpost = Result_4HAT1 && Result_4HATpost = Result_4HATpost && ___cil_tmp6_12HAT0 = ___cil_tmp6_12HATpost && maxRetries_9HAT0 = maxRetries_9HATpost && retryCount_10HAT0 = retryCount_10HATpost && x_5HAT0 = x_5HATpost l2(x, x1, x2, x3, x4, x5, x6) -> l3(x7, x8, x9, x10, x11, x12, x13) :|: x8 = x6 && x14 = x8 && x12 = x14 && x7 = x7 && x11 = 1 + x4 && x2 = x9 && x3 = x10 && x6 = x13 l3(x15, x16, x17, x18, x19, x20, x21) -> l5(x22, x23, x24, x25, x26, x27, x28) :|: x21 = x28 && x20 = x27 && x19 = x26 && x18 = x25 && x17 = x24 && x16 = x23 && x15 = x22 && 1 + x20 <= 0 l3(x29, x30, x31, x32, x33, x34, x35) -> l5(x36, x37, x38, x39, x40, x41, x42) :|: x35 = x42 && x34 = x41 && x33 = x40 && x32 = x39 && x31 = x38 && x30 = x37 && x29 = x36 && 1 <= x34 l5(x43, x44, x45, x46, x47, x48, x49) -> l4(x50, x51, x52, x53, x54, x55, x56) :|: x49 = x56 && x48 = x55 && x47 = x54 && x46 = x53 && x44 = x51 && x50 = x52 && x52 = x48 l3(x57, x58, x59, x60, x61, x62, x63) -> l6(x64, x65, x66, x67, x68, x69, x70) :|: x63 = x70 && x62 = x69 && x61 = x68 && x60 = x67 && x58 = x65 && x64 = x66 && x66 = x62 && x60 - x61 <= 0 && 0 <= x62 && x62 <= 0 l3(x71, x72, x73, x74, x75, x76, x77) -> l1(x78, x79, x80, x81, x82, x83, x84) :|: x76 <= 0 && 0 <= x76 && 0 <= -1 + x74 - x75 && x79 = x77 && x85 = x79 && x83 = x85 && x78 = x78 && x73 = x80 && x74 = x81 && x75 = x82 && x77 = x84 l1(x86, x87, x88, x89, x90, x91, x92) -> l3(x93, x94, x95, x96, x97, x98, x99) :|: x92 = x99 && x91 = x98 && x89 = x96 && x88 = x95 && x87 = x94 && x86 = x93 && x97 = 1 + x90 l7(x100, x101, x102, x103, x104, x105, x106) -> l3(x107, x108, x109, x110, x111, x112, x113) :|: x106 = x113 && x102 = x109 && x101 = x108 && x100 = x107 && x112 = 0 && x111 = 0 && x110 = 400 l8(x114, x115, x116, x117, x118, x119, x120) -> l7(x121, x122, x123, x124, x125, x126, x127) :|: x120 = x127 && x119 = x126 && x118 = x125 && x117 = x124 && x116 = x123 && x115 = x122 && x114 = x121 Start term: l8(Result_4HAT0, ___cil_tmp2_6HAT0, ___cil_tmp6_12HAT0, maxRetries_9HAT0, retryCount_10HAT0, selected_11HAT0, x_5HAT0) ---------------------------------------- (3) IRSwTTerminationDigraphProof (EQUIVALENT) Constructed termination digraph! Nodes: (1) l0(Result_4HAT0, ___cil_tmp2_6HAT0, ___cil_tmp6_12HAT0, maxRetries_9HAT0, retryCount_10HAT0, selected_11HAT0, x_5HAT0) -> l1(Result_4HATpost, ___cil_tmp2_6HATpost, ___cil_tmp6_12HATpost, maxRetries_9HATpost, retryCount_10HATpost, selected_11HATpost, x_5HATpost) :|: ___cil_tmp2_6HATpost = x_5HAT0 && Result_4HAT1 = ___cil_tmp2_6HATpost && selected_11HATpost = Result_4HAT1 && Result_4HATpost = Result_4HATpost && ___cil_tmp6_12HAT0 = ___cil_tmp6_12HATpost && maxRetries_9HAT0 = maxRetries_9HATpost && retryCount_10HAT0 = retryCount_10HATpost && x_5HAT0 = x_5HATpost (2) l2(x, x1, x2, x3, x4, x5, x6) -> l3(x7, x8, x9, x10, x11, x12, x13) :|: x8 = x6 && x14 = x8 && x12 = x14 && x7 = x7 && x11 = 1 + x4 && x2 = x9 && x3 = x10 && x6 = x13 (3) l3(x15, x16, x17, x18, x19, x20, x21) -> l5(x22, x23, x24, x25, x26, x27, x28) :|: x21 = x28 && x20 = x27 && x19 = x26 && x18 = x25 && x17 = x24 && x16 = x23 && x15 = x22 && 1 + x20 <= 0 (4) l3(x29, x30, x31, x32, x33, x34, x35) -> l5(x36, x37, x38, x39, x40, x41, x42) :|: x35 = x42 && x34 = x41 && x33 = x40 && x32 = x39 && x31 = x38 && x30 = x37 && x29 = x36 && 1 <= x34 (5) l5(x43, x44, x45, x46, x47, x48, x49) -> l4(x50, x51, x52, x53, x54, x55, x56) :|: x49 = x56 && x48 = x55 && x47 = x54 && x46 = x53 && x44 = x51 && x50 = x52 && x52 = x48 (6) l3(x57, x58, x59, x60, x61, x62, x63) -> l6(x64, x65, x66, x67, x68, x69, x70) :|: x63 = x70 && x62 = x69 && x61 = x68 && x60 = x67 && x58 = x65 && x64 = x66 && x66 = x62 && x60 - x61 <= 0 && 0 <= x62 && x62 <= 0 (7) l3(x71, x72, x73, x74, x75, x76, x77) -> l1(x78, x79, x80, x81, x82, x83, x84) :|: x76 <= 0 && 0 <= x76 && 0 <= -1 + x74 - x75 && x79 = x77 && x85 = x79 && x83 = x85 && x78 = x78 && x73 = x80 && x74 = x81 && x75 = x82 && x77 = x84 (8) l1(x86, x87, x88, x89, x90, x91, x92) -> l3(x93, x94, x95, x96, x97, x98, x99) :|: x92 = x99 && x91 = x98 && x89 = x96 && x88 = x95 && x87 = x94 && x86 = x93 && x97 = 1 + x90 (9) l7(x100, x101, x102, x103, x104, x105, x106) -> l3(x107, x108, x109, x110, x111, x112, x113) :|: x106 = x113 && x102 = x109 && x101 = x108 && x100 = x107 && x112 = 0 && x111 = 0 && x110 = 400 (10) l8(x114, x115, x116, x117, x118, x119, x120) -> l7(x121, x122, x123, x124, x125, x126, x127) :|: x120 = x127 && x119 = x126 && x118 = x125 && x117 = x124 && x116 = x123 && x115 = x122 && x114 = x121 Arcs: (1) -> (8) (2) -> (3), (4), (6), (7) (3) -> (5) (4) -> (5) (7) -> (8) (8) -> (3), (4), (6), (7) (9) -> (7) (10) -> (9) This digraph is fully evaluated! ---------------------------------------- (4) Obligation: Termination digraph: Nodes: (1) l1(x86, x87, x88, x89, x90, x91, x92) -> l3(x93, x94, x95, x96, x97, x98, x99) :|: x92 = x99 && x91 = x98 && x89 = x96 && x88 = x95 && x87 = x94 && x86 = x93 && x97 = 1 + x90 (2) l3(x71, x72, x73, x74, x75, x76, x77) -> l1(x78, x79, x80, x81, x82, x83, x84) :|: x76 <= 0 && 0 <= x76 && 0 <= -1 + x74 - x75 && x79 = x77 && x85 = x79 && x83 = x85 && x78 = x78 && x73 = x80 && x74 = x81 && x75 = x82 && x77 = x84 Arcs: (1) -> (2) (2) -> (1) This digraph is fully evaluated! ---------------------------------------- (5) IntTRSCompressionProof (EQUIVALENT) Compressed rules. ---------------------------------------- (6) Obligation: Rules: l1(x86:0, x87:0, x80:0, x81:0, x90:0, x91:0, x79:0) -> l1(x78:0, x79:0, x80:0, x81:0, 1 + x90:0, x79:0, x79:0) :|: x91:0 < 1 && x91:0 > -1 && 0 <= -1 + x81:0 - (1 + x90:0) ---------------------------------------- (7) IntTRSUnneededArgumentFilterProof (EQUIVALENT) Some arguments are removed because they cannot influence termination. We removed arguments according to the following replacements: l1(x1, x2, x3, x4, x5, x6, x7) -> l1(x4, x5, x6, x7) ---------------------------------------- (8) Obligation: Rules: l1(x81:0, x90:0, x91:0, x79:0) -> l1(x81:0, 1 + x90:0, x79:0, x79:0) :|: x91:0 < 1 && x91:0 > -1 && 0 <= -1 + x81:0 - (1 + x90:0) ---------------------------------------- (9) TempFilterProof (SOUND) Used the following sort dictionary for filtering: l1(INTEGER, INTEGER, VARIABLE, VARIABLE) Replaced non-predefined constructor symbols by 0. ---------------------------------------- (10) Obligation: Rules: l1(x81:0, x90:0, x91:0, x79:0) -> l1(x81:0, c, x79:0, x79:0) :|: c = 1 + x90:0 && (x91:0 < 1 && x91:0 > -1 && 0 <= -1 + x81:0 - (1 + x90:0)) ---------------------------------------- (11) PolynomialOrderProcessor (EQUIVALENT) Found the following polynomial interpretation: [l1(x, x1, x2, x3)] = x - x1 The following rules are decreasing: l1(x81:0, x90:0, x91:0, x79:0) -> l1(x81:0, c, x79:0, x79:0) :|: c = 1 + x90:0 && (x91:0 < 1 && x91:0 > -1 && 0 <= -1 + x81:0 - (1 + x90:0)) The following rules are bounded: l1(x81:0, x90:0, x91:0, x79:0) -> l1(x81:0, c, x79:0, x79:0) :|: c = 1 + x90:0 && (x91:0 < 1 && x91:0 > -1 && 0 <= -1 + x81:0 - (1 + x90:0)) ---------------------------------------- (12) YES