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