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, 608 ms] (4) IRSwT (5) IntTRSCompressionProof [EQUIVALENT, 0 ms] (6) IRSwT (7) IntTRSUnneededArgumentFilterProof [EQUIVALENT, 3 ms] (8) IRSwT (9) TempFilterProof [SOUND, 57 ms] (10) IntTRS (11) PolynomialOrderProcessor [EQUIVALENT, 0 ms] (12) IntTRS (13) RankingReductionPairProof [EQUIVALENT, 0 ms] (14) YES ---------------------------------------- (0) Obligation: Rules: l0(result_11HAT0, temp0_14HAT0, x_13HAT0, x_27HAT0, x_32HAT0, y_16HAT0, y_28HAT0, y_33HAT0) -> l1(result_11HATpost, temp0_14HATpost, x_13HATpost, x_27HATpost, x_32HATpost, y_16HATpost, y_28HATpost, y_33HATpost) :|: y_33HAT0 = y_33HATpost && y_28HAT0 = y_28HATpost && x_32HAT0 = x_32HATpost && x_27HAT0 = x_27HATpost && temp0_14HAT0 = temp0_14HATpost && result_11HAT0 = result_11HATpost && y_16HATpost = y_16HATpost && x_13HATpost = x_13HATpost l1(x, x1, x2, x3, x4, x5, x6, x7) -> l2(x8, x9, x10, x11, x12, x13, x14, x15) :|: x7 = x15 && x6 = x14 && x4 = x12 && x3 = x11 && x2 = x10 && x1 = x9 && x = x8 && 1 <= x2 && 1 <= x13 && x13 = x13 && 1 <= x2 l1(x16, x17, x18, x19, x20, x21, x22, x23) -> l3(x24, x25, x26, x27, x28, x29, x30, x31) :|: x23 = x31 && x22 = x30 && x21 = x29 && x20 = x28 && x19 = x27 && x18 = x26 && x17 = x25 && x24 = x17 && x18 <= 0 l4(x32, x33, x34, x35, x36, x37, x38, x39) -> l2(x40, x41, x42, x43, x44, x45, x46, x47) :|: x39 = x47 && x36 = x44 && x33 = x41 && x32 = x40 && 1 <= x46 && 1 <= x43 && -1 + x46 <= x45 && x45 <= -1 + x46 && -1 + x43 <= x42 && x42 <= -1 + x43 && x45 = -1 + x37 && x42 = -1 + x34 && 1 <= x37 && x46 = x46 && x43 = x43 l2(x48, x49, x50, x51, x52, x53, x54, x55) -> l1(x56, x57, x58, x59, x60, x61, x62, x63) :|: x55 = x63 && x54 = x62 && x53 = x61 && x52 = x60 && x51 = x59 && x50 = x58 && x49 = x57 && x48 = x56 && x53 <= 0 && x53 <= 0 l2(x64, x65, x66, x67, x68, x69, x70, x71) -> l5(x72, x73, x74, x75, x76, x77, x78, x79) :|: x70 = x78 && x67 = x75 && x65 = x73 && x64 = x72 && 1 <= x79 && -1 + x79 <= x77 && x77 <= -1 + x79 && -1 + x76 <= x74 && x74 <= -1 + x76 && x77 = -1 + x69 && x74 = -1 + x66 && 1 <= x69 && x79 = x79 && x76 = x76 l5(x80, x81, x82, x83, x84, x85, x86, x87) -> l2(x88, x89, x90, x91, x92, x93, x94, x95) :|: x87 = x95 && x86 = x94 && x85 = x93 && x84 = x92 && x83 = x91 && x82 = x90 && x81 = x89 && x80 = x88 l6(x96, x97, x98, x99, x100, x101, x102, x103) -> l0(x104, x105, x106, x107, x108, x109, x110, x111) :|: x103 = x111 && x102 = x110 && x101 = x109 && x100 = x108 && x99 = x107 && x98 = x106 && x97 = x105 && x96 = x104 Start term: l6(result_11HAT0, temp0_14HAT0, x_13HAT0, x_27HAT0, x_32HAT0, y_16HAT0, y_28HAT0, y_33HAT0) ---------------------------------------- (1) IRSFormatTransformerProof (EQUIVALENT) Reformatted IRS to match normalized format (transformed away non-linear left-hand sides, !=, / and %). ---------------------------------------- (2) Obligation: Rules: l0(result_11HAT0, temp0_14HAT0, x_13HAT0, x_27HAT0, x_32HAT0, y_16HAT0, y_28HAT0, y_33HAT0) -> l1(result_11HATpost, temp0_14HATpost, x_13HATpost, x_27HATpost, x_32HATpost, y_16HATpost, y_28HATpost, y_33HATpost) :|: y_33HAT0 = y_33HATpost && y_28HAT0 = y_28HATpost && x_32HAT0 = x_32HATpost && x_27HAT0 = x_27HATpost && temp0_14HAT0 = temp0_14HATpost && result_11HAT0 = result_11HATpost && y_16HATpost = y_16HATpost && x_13HATpost = x_13HATpost l1(x, x1, x2, x3, x4, x5, x6, x7) -> l2(x8, x9, x10, x11, x12, x13, x14, x15) :|: x7 = x15 && x6 = x14 && x4 = x12 && x3 = x11 && x2 = x10 && x1 = x9 && x = x8 && 1 <= x2 && 1 <= x13 && x13 = x13 && 1 <= x2 l1(x16, x17, x18, x19, x20, x21, x22, x23) -> l3(x24, x25, x26, x27, x28, x29, x30, x31) :|: x23 = x31 && x22 = x30 && x21 = x29 && x20 = x28 && x19 = x27 && x18 = x26 && x17 = x25 && x24 = x17 && x18 <= 0 l4(x32, x33, x34, x35, x36, x37, x38, x39) -> l2(x40, x41, x42, x43, x44, x45, x46, x47) :|: x39 = x47 && x36 = x44 && x33 = x41 && x32 = x40 && 1 <= x46 && 1 <= x43 && -1 + x46 <= x45 && x45 <= -1 + x46 && -1 + x43 <= x42 && x42 <= -1 + x43 && x45 = -1 + x37 && x42 = -1 + x34 && 1 <= x37 && x46 = x46 && x43 = x43 l2(x48, x49, x50, x51, x52, x53, x54, x55) -> l1(x56, x57, x58, x59, x60, x61, x62, x63) :|: x55 = x63 && x54 = x62 && x53 = x61 && x52 = x60 && x51 = x59 && x50 = x58 && x49 = x57 && x48 = x56 && x53 <= 0 && x53 <= 0 l2(x64, x65, x66, x67, x68, x69, x70, x71) -> l5(x72, x73, x74, x75, x76, x77, x78, x79) :|: x70 = x78 && x67 = x75 && x65 = x73 && x64 = x72 && 1 <= x79 && -1 + x79 <= x77 && x77 <= -1 + x79 && -1 + x76 <= x74 && x74 <= -1 + x76 && x77 = -1 + x69 && x74 = -1 + x66 && 1 <= x69 && x79 = x79 && x76 = x76 l5(x80, x81, x82, x83, x84, x85, x86, x87) -> l2(x88, x89, x90, x91, x92, x93, x94, x95) :|: x87 = x95 && x86 = x94 && x85 = x93 && x84 = x92 && x83 = x91 && x82 = x90 && x81 = x89 && x80 = x88 l6(x96, x97, x98, x99, x100, x101, x102, x103) -> l0(x104, x105, x106, x107, x108, x109, x110, x111) :|: x103 = x111 && x102 = x110 && x101 = x109 && x100 = x108 && x99 = x107 && x98 = x106 && x97 = x105 && x96 = x104 Start term: l6(result_11HAT0, temp0_14HAT0, x_13HAT0, x_27HAT0, x_32HAT0, y_16HAT0, y_28HAT0, y_33HAT0) ---------------------------------------- (3) IRSwTTerminationDigraphProof (EQUIVALENT) Constructed termination digraph! Nodes: (1) l0(result_11HAT0, temp0_14HAT0, x_13HAT0, x_27HAT0, x_32HAT0, y_16HAT0, y_28HAT0, y_33HAT0) -> l1(result_11HATpost, temp0_14HATpost, x_13HATpost, x_27HATpost, x_32HATpost, y_16HATpost, y_28HATpost, y_33HATpost) :|: y_33HAT0 = y_33HATpost && y_28HAT0 = y_28HATpost && x_32HAT0 = x_32HATpost && x_27HAT0 = x_27HATpost && temp0_14HAT0 = temp0_14HATpost && result_11HAT0 = result_11HATpost && y_16HATpost = y_16HATpost && x_13HATpost = x_13HATpost (2) l1(x, x1, x2, x3, x4, x5, x6, x7) -> l2(x8, x9, x10, x11, x12, x13, x14, x15) :|: x7 = x15 && x6 = x14 && x4 = x12 && x3 = x11 && x2 = x10 && x1 = x9 && x = x8 && 1 <= x2 && 1 <= x13 && x13 = x13 && 1 <= x2 (3) l1(x16, x17, x18, x19, x20, x21, x22, x23) -> l3(x24, x25, x26, x27, x28, x29, x30, x31) :|: x23 = x31 && x22 = x30 && x21 = x29 && x20 = x28 && x19 = x27 && x18 = x26 && x17 = x25 && x24 = x17 && x18 <= 0 (4) l4(x32, x33, x34, x35, x36, x37, x38, x39) -> l2(x40, x41, x42, x43, x44, x45, x46, x47) :|: x39 = x47 && x36 = x44 && x33 = x41 && x32 = x40 && 1 <= x46 && 1 <= x43 && -1 + x46 <= x45 && x45 <= -1 + x46 && -1 + x43 <= x42 && x42 <= -1 + x43 && x45 = -1 + x37 && x42 = -1 + x34 && 1 <= x37 && x46 = x46 && x43 = x43 (5) l2(x48, x49, x50, x51, x52, x53, x54, x55) -> l1(x56, x57, x58, x59, x60, x61, x62, x63) :|: x55 = x63 && x54 = x62 && x53 = x61 && x52 = x60 && x51 = x59 && x50 = x58 && x49 = x57 && x48 = x56 && x53 <= 0 && x53 <= 0 (6) l2(x64, x65, x66, x67, x68, x69, x70, x71) -> l5(x72, x73, x74, x75, x76, x77, x78, x79) :|: x70 = x78 && x67 = x75 && x65 = x73 && x64 = x72 && 1 <= x79 && -1 + x79 <= x77 && x77 <= -1 + x79 && -1 + x76 <= x74 && x74 <= -1 + x76 && x77 = -1 + x69 && x74 = -1 + x66 && 1 <= x69 && x79 = x79 && x76 = x76 (7) l5(x80, x81, x82, x83, x84, x85, x86, x87) -> l2(x88, x89, x90, x91, x92, x93, x94, x95) :|: x87 = x95 && x86 = x94 && x85 = x93 && x84 = x92 && x83 = x91 && x82 = x90 && x81 = x89 && x80 = x88 (8) l6(x96, x97, x98, x99, x100, x101, x102, x103) -> l0(x104, x105, x106, x107, x108, x109, x110, x111) :|: x103 = x111 && x102 = x110 && x101 = x109 && x100 = x108 && x99 = x107 && x98 = x106 && x97 = x105 && x96 = x104 Arcs: (1) -> (2), (3) (2) -> (6) (4) -> (5), (6) (5) -> (2), (3) (6) -> (7) (7) -> (5), (6) (8) -> (1) This digraph is fully evaluated! ---------------------------------------- (4) Obligation: Termination digraph: Nodes: (1) l1(x, x1, x2, x3, x4, x5, x6, x7) -> l2(x8, x9, x10, x11, x12, x13, x14, x15) :|: x7 = x15 && x6 = x14 && x4 = x12 && x3 = x11 && x2 = x10 && x1 = x9 && x = x8 && 1 <= x2 && 1 <= x13 && x13 = x13 && 1 <= x2 (2) l2(x48, x49, x50, x51, x52, x53, x54, x55) -> l1(x56, x57, x58, x59, x60, x61, x62, x63) :|: x55 = x63 && x54 = x62 && x53 = x61 && x52 = x60 && x51 = x59 && x50 = x58 && x49 = x57 && x48 = x56 && x53 <= 0 && x53 <= 0 (3) l5(x80, x81, x82, x83, x84, x85, x86, x87) -> l2(x88, x89, x90, x91, x92, x93, x94, x95) :|: x87 = x95 && x86 = x94 && x85 = x93 && x84 = x92 && x83 = x91 && x82 = x90 && x81 = x89 && x80 = x88 (4) l2(x64, x65, x66, x67, x68, x69, x70, x71) -> l5(x72, x73, x74, x75, x76, x77, x78, x79) :|: x70 = x78 && x67 = x75 && x65 = x73 && x64 = x72 && 1 <= x79 && -1 + x79 <= x77 && x77 <= -1 + x79 && -1 + x76 <= x74 && x74 <= -1 + x76 && x77 = -1 + x69 && x74 = -1 + x66 && 1 <= x69 && x79 = x79 && x76 = x76 Arcs: (1) -> (4) (2) -> (1) (3) -> (2), (4) (4) -> (3) This digraph is fully evaluated! ---------------------------------------- (5) IntTRSCompressionProof (EQUIVALENT) Compressed rules. ---------------------------------------- (6) Obligation: Rules: l2(x64:0, x65:0, x66:0, x67:0, x68:0, x69:0, x70:0, x71:0) -> l2(x64:0, x65:0, -1 + x66:0, x67:0, x76:0, -1 + x69:0, x70:0, x79:0) :|: x79:0 > 0 && x69:0 > 0 && -1 + x79:0 = -1 + x69:0 && -1 + x76:0 = -1 + x66:0 l2(x48:0, x49:0, x10:0, x11:0, x12:0, x53:0, x14:0, x15:0) -> l2(x48:0, x49:0, x10:0, x11:0, x12:0, x13:0, x14:0, x15:0) :|: x53:0 < 1 && x10:0 > 0 && x13:0 > 0 ---------------------------------------- (7) IntTRSUnneededArgumentFilterProof (EQUIVALENT) Some arguments are removed because they cannot influence termination. We removed arguments according to the following replacements: l2(x1, x2, x3, x4, x5, x6, x7, x8) -> l2(x3, x5, x6, x8) ---------------------------------------- (8) Obligation: Rules: l2(x66:0, x68:0, x69:0, x71:0) -> l2(-1 + x66:0, x76:0, -1 + x69:0, x79:0) :|: x79:0 > 0 && x69:0 > 0 && -1 + x79:0 = -1 + x69:0 && -1 + x76:0 = -1 + x66:0 l2(x10:0, x12:0, x53:0, x15:0) -> l2(x10:0, x12:0, x13:0, x15:0) :|: x53:0 < 1 && x10:0 > 0 && x13:0 > 0 ---------------------------------------- (9) TempFilterProof (SOUND) Used the following sort dictionary for filtering: l2(INTEGER, VARIABLE, INTEGER, VARIABLE) Replaced non-predefined constructor symbols by 0. ---------------------------------------- (10) Obligation: Rules: l2(x66:0, x68:0, x69:0, x71:0) -> l2(c, x76:0, c1, x79:0) :|: c1 = -1 + x69:0 && c = -1 + x66:0 && (x79:0 > 0 && x69:0 > 0 && -1 + x79:0 = -1 + x69:0 && -1 + x76:0 = -1 + x66:0) l2(x10:0, x12:0, x53:0, x15:0) -> l2(x10:0, x12:0, x13:0, x15:0) :|: x53:0 < 1 && x10:0 > 0 && x13:0 > 0 ---------------------------------------- (11) PolynomialOrderProcessor (EQUIVALENT) Found the following polynomial interpretation: [l2(x, x1, x2, x3)] = x - x2 The following rules are decreasing: l2(x10:0, x12:0, x53:0, x15:0) -> l2(x10:0, x12:0, x13:0, x15:0) :|: x53:0 < 1 && x10:0 > 0 && x13:0 > 0 The following rules are bounded: l2(x10:0, x12:0, x53:0, x15:0) -> l2(x10:0, x12:0, x13:0, x15:0) :|: x53:0 < 1 && x10:0 > 0 && x13:0 > 0 ---------------------------------------- (12) Obligation: Rules: l2(x66:0, x68:0, x69:0, x71:0) -> l2(c, x76:0, c1, x79:0) :|: c1 = -1 + x69:0 && c = -1 + x66:0 && (x79:0 > 0 && x69:0 > 0 && -1 + x79:0 = -1 + x69:0 && -1 + x76:0 = -1 + x66:0) ---------------------------------------- (13) RankingReductionPairProof (EQUIVALENT) Interpretation: [ l2 ] = l2_3 The following rules are decreasing: l2(x66:0, x68:0, x69:0, x71:0) -> l2(c, x76:0, c1, x79:0) :|: c1 = -1 + x69:0 && c = -1 + x66:0 && (x79:0 > 0 && x69:0 > 0 && -1 + x79:0 = -1 + x69:0 && -1 + x76:0 = -1 + x66:0) The following rules are bounded: l2(x66:0, x68:0, x69:0, x71:0) -> l2(c, x76:0, c1, x79:0) :|: c1 = -1 + x69:0 && c = -1 + x66:0 && (x79:0 > 0 && x69:0 > 0 && -1 + x79:0 = -1 + x69:0 && -1 + x76:0 = -1 + x66:0) ---------------------------------------- (14) YES