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, 12.5 s] (4) AND (5) IRSwT (6) IntTRSCompressionProof [EQUIVALENT, 33 ms] (7) IRSwT (8) IntTRSUnneededArgumentFilterProof [EQUIVALENT, 0 ms] (9) IRSwT (10) TempFilterProof [SOUND, 37 ms] (11) IntTRS (12) PolynomialOrderProcessor [EQUIVALENT, 0 ms] (13) IntTRS (14) RankingReductionPairProof [EQUIVALENT, 0 ms] (15) YES (16) IRSwT (17) IntTRSCompressionProof [EQUIVALENT, 38 ms] (18) IRSwT (19) IntTRSUnneededArgumentFilterProof [EQUIVALENT, 0 ms] (20) IRSwT (21) TempFilterProof [SOUND, 30 ms] (22) IntTRS (23) RankingReductionPairProof [EQUIVALENT, 17 ms] (24) IntTRS (25) PolynomialOrderProcessor [EQUIVALENT, 0 ms] (26) YES (27) IRSwT (28) IntTRSCompressionProof [EQUIVALENT, 0 ms] (29) IRSwT (30) IntTRSUnneededArgumentFilterProof [EQUIVALENT, 0 ms] (31) IRSwT (32) TempFilterProof [SOUND, 14 ms] (33) IntTRS (34) PolynomialOrderProcessor [EQUIVALENT, 0 ms] (35) YES (36) IRSwT (37) IntTRSCompressionProof [EQUIVALENT, 0 ms] (38) IRSwT (39) IntTRSUnneededArgumentFilterProof [EQUIVALENT, 0 ms] (40) IRSwT (41) TempFilterProof [SOUND, 14 ms] (42) IntTRS (43) RankingReductionPairProof [EQUIVALENT, 8 ms] (44) YES ---------------------------------------- (0) Obligation: Rules: l0(edgecountHAT0, iHAT0, jHAT0, nodecountHAT0, sourceHAT0, xHAT0, yHAT0) -> l1(edgecountHATpost, iHATpost, jHATpost, nodecountHATpost, sourceHATpost, xHATpost, yHATpost) :|: yHAT0 = yHATpost && xHAT0 = xHATpost && sourceHAT0 = sourceHATpost && nodecountHAT0 = nodecountHATpost && jHAT0 = jHATpost && iHAT0 = iHATpost && edgecountHAT0 = edgecountHATpost l2(x, x1, x2, x3, x4, x5, x6) -> l3(x7, x8, x9, x10, x11, x12, x13) :|: x6 = x13 && x5 = x12 && x4 = x11 && x3 = x10 && x2 = x9 && x1 = x8 && x = x7 && x3 <= x1 l2(x14, x15, x16, x17, x18, x19, x20) -> l4(x21, x22, x23, x24, x25, x26, x27) :|: x20 = x27 && x19 = x26 && x18 = x25 && x17 = x24 && x16 = x23 && x14 = x21 && x22 = 1 + x15 && 1 + x15 <= x17 l5(x28, x29, x30, x31, x32, x33, x34) -> l6(x35, x36, x37, x38, x39, x40, x41) :|: x34 = x41 && x33 = x40 && x32 = x39 && x31 = x38 && x30 = x37 && x28 = x35 && x36 = 1 + x29 l5(x42, x43, x44, x45, x46, x47, x48) -> l3(x49, x50, x51, x52, x53, x54, x55) :|: x48 = x55 && x47 = x54 && x46 = x53 && x45 = x52 && x44 = x51 && x43 = x50 && x42 = x49 l7(x56, x57, x58, x59, x60, x61, x62) -> l8(x63, x64, x65, x66, x67, x68, x69) :|: x62 = x69 && x61 = x68 && x60 = x67 && x59 = x66 && x58 = x65 && x57 = x64 && x56 = x63 l9(x70, x71, x72, x73, x74, x75, x76) -> l4(x77, x78, x79, x80, x81, x82, x83) :|: x76 = x83 && x75 = x82 && x74 = x81 && x73 = x80 && x72 = x79 && x70 = x77 && x78 = 0 && x70 <= x71 l9(x84, x85, x86, x87, x88, x89, x90) -> l5(x91, x92, x93, x94, x95, x96, x97) :|: x88 = x95 && x87 = x94 && x86 = x93 && x85 = x92 && x84 = x91 && x97 = x97 && x96 = x96 && 1 + x85 <= x84 l10(x98, x99, x100, x101, x102, x103, x104) -> l11(x105, x106, x107, x108, x109, x110, x111) :|: x104 = x111 && x103 = x110 && x102 = x109 && x101 = x108 && x99 = x106 && x98 = x105 && x107 = 1 + x100 l11(x112, x113, x114, x115, x116, x117, x118) -> l12(x119, x120, x121, x122, x123, x124, x125) :|: x118 = x125 && x117 = x124 && x116 = x123 && x115 = x122 && x114 = x121 && x113 = x120 && x112 = x119 l12(x126, x127, x128, x129, x130, x131, x132) -> l7(x133, x134, x135, x136, x137, x138, x139) :|: x132 = x139 && x131 = x138 && x130 = x137 && x129 = x136 && x128 = x135 && x126 = x133 && x134 = 1 + x127 && x126 <= x128 l12(x140, x141, x142, x143, x144, x145, x146) -> l10(x147, x148, x149, x150, x151, x152, x153) :|: x144 = x151 && x143 = x150 && x142 = x149 && x141 = x148 && x140 = x147 && x153 = x153 && x152 = x152 && 1 + x142 <= x140 l8(x154, x155, x156, x157, x158, x159, x160) -> l6(x161, x162, x163, x164, x165, x166, x167) :|: x160 = x167 && x159 = x166 && x158 = x165 && x157 = x164 && x156 = x163 && x154 = x161 && x162 = 0 && x157 <= x155 l8(x168, x169, x170, x171, x172, x173, x174) -> l11(x175, x176, x177, x178, x179, x180, x181) :|: x174 = x181 && x173 = x180 && x172 = x179 && x171 = x178 && x169 = x176 && x168 = x175 && x177 = 0 && 1 + x169 <= x171 l13(x182, x183, x184, x185, x186, x187, x188) -> l14(x189, x190, x191, x192, x193, x194, x195) :|: x188 = x195 && x187 = x194 && x186 = x193 && x185 = x192 && x184 = x191 && x183 = x190 && x182 = x189 l6(x196, x197, x198, x199, x200, x201, x202) -> l9(x203, x204, x205, x206, x207, x208, x209) :|: x202 = x209 && x201 = x208 && x200 = x207 && x199 = x206 && x198 = x205 && x197 = x204 && x196 = x203 l14(x210, x211, x212, x213, x214, x215, x216) -> l0(x217, x218, x219, x220, x221, x222, x223) :|: x216 = x223 && x215 = x222 && x214 = x221 && x213 = x220 && x212 = x219 && x210 = x217 && x218 = 1 + x211 l15(x224, x225, x226, x227, x228, x229, x230) -> l13(x231, x232, x233, x234, x235, x236, x237) :|: x230 = x237 && x229 = x236 && x228 = x235 && x227 = x234 && x226 = x233 && x225 = x232 && x224 = x231 && 1 + x228 <= x225 l15(x238, x239, x240, x241, x242, x243, x244) -> l13(x245, x246, x247, x248, x249, x250, x251) :|: x244 = x251 && x243 = x250 && x242 = x249 && x241 = x248 && x240 = x247 && x239 = x246 && x238 = x245 && 1 + x239 <= x242 l15(x252, x253, x254, x255, x256, x257, x258) -> l14(x259, x260, x261, x262, x263, x264, x265) :|: x258 = x265 && x257 = x264 && x256 = x263 && x255 = x262 && x254 = x261 && x253 = x260 && x252 = x259 && x256 <= x253 && x253 <= x256 l1(x266, x267, x268, x269, x270, x271, x272) -> l7(x273, x274, x275, x276, x277, x278, x279) :|: x272 = x279 && x271 = x278 && x270 = x277 && x269 = x276 && x268 = x275 && x266 = x273 && x274 = 0 && x269 <= x267 l1(x280, x281, x282, x283, x284, x285, x286) -> l15(x287, x288, x289, x290, x291, x292, x293) :|: x286 = x293 && x285 = x292 && x284 = x291 && x283 = x290 && x282 = x289 && x281 = x288 && x280 = x287 && 1 + x281 <= x283 l4(x294, x295, x296, x297, x298, x299, x300) -> l2(x301, x302, x303, x304, x305, x306, x307) :|: x300 = x307 && x299 = x306 && x298 = x305 && x297 = x304 && x296 = x303 && x295 = x302 && x294 = x301 l16(x308, x309, x310, x311, x312, x313, x314) -> l0(x315, x316, x317, x318, x319, x320, x321) :|: x314 = x321 && x313 = x320 && x310 = x317 && x316 = 0 && x319 = 0 && x315 = 5 && x318 = 5 l17(x322, x323, x324, x325, x326, x327, x328) -> l16(x329, x330, x331, x332, x333, x334, x335) :|: x328 = x335 && x327 = x334 && x326 = x333 && x325 = x332 && x324 = x331 && x323 = x330 && x322 = x329 Start term: l17(edgecountHAT0, iHAT0, jHAT0, nodecountHAT0, sourceHAT0, xHAT0, yHAT0) ---------------------------------------- (1) IRSFormatTransformerProof (EQUIVALENT) Reformatted IRS to match normalized format (transformed away non-linear left-hand sides, !=, / and %). ---------------------------------------- (2) Obligation: Rules: l0(edgecountHAT0, iHAT0, jHAT0, nodecountHAT0, sourceHAT0, xHAT0, yHAT0) -> l1(edgecountHATpost, iHATpost, jHATpost, nodecountHATpost, sourceHATpost, xHATpost, yHATpost) :|: yHAT0 = yHATpost && xHAT0 = xHATpost && sourceHAT0 = sourceHATpost && nodecountHAT0 = nodecountHATpost && jHAT0 = jHATpost && iHAT0 = iHATpost && edgecountHAT0 = edgecountHATpost l2(x, x1, x2, x3, x4, x5, x6) -> l3(x7, x8, x9, x10, x11, x12, x13) :|: x6 = x13 && x5 = x12 && x4 = x11 && x3 = x10 && x2 = x9 && x1 = x8 && x = x7 && x3 <= x1 l2(x14, x15, x16, x17, x18, x19, x20) -> l4(x21, x22, x23, x24, x25, x26, x27) :|: x20 = x27 && x19 = x26 && x18 = x25 && x17 = x24 && x16 = x23 && x14 = x21 && x22 = 1 + x15 && 1 + x15 <= x17 l5(x28, x29, x30, x31, x32, x33, x34) -> l6(x35, x36, x37, x38, x39, x40, x41) :|: x34 = x41 && x33 = x40 && x32 = x39 && x31 = x38 && x30 = x37 && x28 = x35 && x36 = 1 + x29 l5(x42, x43, x44, x45, x46, x47, x48) -> l3(x49, x50, x51, x52, x53, x54, x55) :|: x48 = x55 && x47 = x54 && x46 = x53 && x45 = x52 && x44 = x51 && x43 = x50 && x42 = x49 l7(x56, x57, x58, x59, x60, x61, x62) -> l8(x63, x64, x65, x66, x67, x68, x69) :|: x62 = x69 && x61 = x68 && x60 = x67 && x59 = x66 && x58 = x65 && x57 = x64 && x56 = x63 l9(x70, x71, x72, x73, x74, x75, x76) -> l4(x77, x78, x79, x80, x81, x82, x83) :|: x76 = x83 && x75 = x82 && x74 = x81 && x73 = x80 && x72 = x79 && x70 = x77 && x78 = 0 && x70 <= x71 l9(x84, x85, x86, x87, x88, x89, x90) -> l5(x91, x92, x93, x94, x95, x96, x97) :|: x88 = x95 && x87 = x94 && x86 = x93 && x85 = x92 && x84 = x91 && x97 = x97 && x96 = x96 && 1 + x85 <= x84 l10(x98, x99, x100, x101, x102, x103, x104) -> l11(x105, x106, x107, x108, x109, x110, x111) :|: x104 = x111 && x103 = x110 && x102 = x109 && x101 = x108 && x99 = x106 && x98 = x105 && x107 = 1 + x100 l11(x112, x113, x114, x115, x116, x117, x118) -> l12(x119, x120, x121, x122, x123, x124, x125) :|: x118 = x125 && x117 = x124 && x116 = x123 && x115 = x122 && x114 = x121 && x113 = x120 && x112 = x119 l12(x126, x127, x128, x129, x130, x131, x132) -> l7(x133, x134, x135, x136, x137, x138, x139) :|: x132 = x139 && x131 = x138 && x130 = x137 && x129 = x136 && x128 = x135 && x126 = x133 && x134 = 1 + x127 && x126 <= x128 l12(x140, x141, x142, x143, x144, x145, x146) -> l10(x147, x148, x149, x150, x151, x152, x153) :|: x144 = x151 && x143 = x150 && x142 = x149 && x141 = x148 && x140 = x147 && x153 = x153 && x152 = x152 && 1 + x142 <= x140 l8(x154, x155, x156, x157, x158, x159, x160) -> l6(x161, x162, x163, x164, x165, x166, x167) :|: x160 = x167 && x159 = x166 && x158 = x165 && x157 = x164 && x156 = x163 && x154 = x161 && x162 = 0 && x157 <= x155 l8(x168, x169, x170, x171, x172, x173, x174) -> l11(x175, x176, x177, x178, x179, x180, x181) :|: x174 = x181 && x173 = x180 && x172 = x179 && x171 = x178 && x169 = x176 && x168 = x175 && x177 = 0 && 1 + x169 <= x171 l13(x182, x183, x184, x185, x186, x187, x188) -> l14(x189, x190, x191, x192, x193, x194, x195) :|: x188 = x195 && x187 = x194 && x186 = x193 && x185 = x192 && x184 = x191 && x183 = x190 && x182 = x189 l6(x196, x197, x198, x199, x200, x201, x202) -> l9(x203, x204, x205, x206, x207, x208, x209) :|: x202 = x209 && x201 = x208 && x200 = x207 && x199 = x206 && x198 = x205 && x197 = x204 && x196 = x203 l14(x210, x211, x212, x213, x214, x215, x216) -> l0(x217, x218, x219, x220, x221, x222, x223) :|: x216 = x223 && x215 = x222 && x214 = x221 && x213 = x220 && x212 = x219 && x210 = x217 && x218 = 1 + x211 l15(x224, x225, x226, x227, x228, x229, x230) -> l13(x231, x232, x233, x234, x235, x236, x237) :|: x230 = x237 && x229 = x236 && x228 = x235 && x227 = x234 && x226 = x233 && x225 = x232 && x224 = x231 && 1 + x228 <= x225 l15(x238, x239, x240, x241, x242, x243, x244) -> l13(x245, x246, x247, x248, x249, x250, x251) :|: x244 = x251 && x243 = x250 && x242 = x249 && x241 = x248 && x240 = x247 && x239 = x246 && x238 = x245 && 1 + x239 <= x242 l15(x252, x253, x254, x255, x256, x257, x258) -> l14(x259, x260, x261, x262, x263, x264, x265) :|: x258 = x265 && x257 = x264 && x256 = x263 && x255 = x262 && x254 = x261 && x253 = x260 && x252 = x259 && x256 <= x253 && x253 <= x256 l1(x266, x267, x268, x269, x270, x271, x272) -> l7(x273, x274, x275, x276, x277, x278, x279) :|: x272 = x279 && x271 = x278 && x270 = x277 && x269 = x276 && x268 = x275 && x266 = x273 && x274 = 0 && x269 <= x267 l1(x280, x281, x282, x283, x284, x285, x286) -> l15(x287, x288, x289, x290, x291, x292, x293) :|: x286 = x293 && x285 = x292 && x284 = x291 && x283 = x290 && x282 = x289 && x281 = x288 && x280 = x287 && 1 + x281 <= x283 l4(x294, x295, x296, x297, x298, x299, x300) -> l2(x301, x302, x303, x304, x305, x306, x307) :|: x300 = x307 && x299 = x306 && x298 = x305 && x297 = x304 && x296 = x303 && x295 = x302 && x294 = x301 l16(x308, x309, x310, x311, x312, x313, x314) -> l0(x315, x316, x317, x318, x319, x320, x321) :|: x314 = x321 && x313 = x320 && x310 = x317 && x316 = 0 && x319 = 0 && x315 = 5 && x318 = 5 l17(x322, x323, x324, x325, x326, x327, x328) -> l16(x329, x330, x331, x332, x333, x334, x335) :|: x328 = x335 && x327 = x334 && x326 = x333 && x325 = x332 && x324 = x331 && x323 = x330 && x322 = x329 Start term: l17(edgecountHAT0, iHAT0, jHAT0, nodecountHAT0, sourceHAT0, xHAT0, yHAT0) ---------------------------------------- (3) IRSwTTerminationDigraphProof (EQUIVALENT) Constructed termination digraph! Nodes: (1) l0(edgecountHAT0, iHAT0, jHAT0, nodecountHAT0, sourceHAT0, xHAT0, yHAT0) -> l1(edgecountHATpost, iHATpost, jHATpost, nodecountHATpost, sourceHATpost, xHATpost, yHATpost) :|: yHAT0 = yHATpost && xHAT0 = xHATpost && sourceHAT0 = sourceHATpost && nodecountHAT0 = nodecountHATpost && jHAT0 = jHATpost && iHAT0 = iHATpost && edgecountHAT0 = edgecountHATpost (2) l2(x, x1, x2, x3, x4, x5, x6) -> l3(x7, x8, x9, x10, x11, x12, x13) :|: x6 = x13 && x5 = x12 && x4 = x11 && x3 = x10 && x2 = x9 && x1 = x8 && x = x7 && x3 <= x1 (3) l2(x14, x15, x16, x17, x18, x19, x20) -> l4(x21, x22, x23, x24, x25, x26, x27) :|: x20 = x27 && x19 = x26 && x18 = x25 && x17 = x24 && x16 = x23 && x14 = x21 && x22 = 1 + x15 && 1 + x15 <= x17 (4) l5(x28, x29, x30, x31, x32, x33, x34) -> l6(x35, x36, x37, x38, x39, x40, x41) :|: x34 = x41 && x33 = x40 && x32 = x39 && x31 = x38 && x30 = x37 && x28 = x35 && x36 = 1 + x29 (5) l5(x42, x43, x44, x45, x46, x47, x48) -> l3(x49, x50, x51, x52, x53, x54, x55) :|: x48 = x55 && x47 = x54 && x46 = x53 && x45 = x52 && x44 = x51 && x43 = x50 && x42 = x49 (6) l7(x56, x57, x58, x59, x60, x61, x62) -> l8(x63, x64, x65, x66, x67, x68, x69) :|: x62 = x69 && x61 = x68 && x60 = x67 && x59 = x66 && x58 = x65 && x57 = x64 && x56 = x63 (7) l9(x70, x71, x72, x73, x74, x75, x76) -> l4(x77, x78, x79, x80, x81, x82, x83) :|: x76 = x83 && x75 = x82 && x74 = x81 && x73 = x80 && x72 = x79 && x70 = x77 && x78 = 0 && x70 <= x71 (8) l9(x84, x85, x86, x87, x88, x89, x90) -> l5(x91, x92, x93, x94, x95, x96, x97) :|: x88 = x95 && x87 = x94 && x86 = x93 && x85 = x92 && x84 = x91 && x97 = x97 && x96 = x96 && 1 + x85 <= x84 (9) l10(x98, x99, x100, x101, x102, x103, x104) -> l11(x105, x106, x107, x108, x109, x110, x111) :|: x104 = x111 && x103 = x110 && x102 = x109 && x101 = x108 && x99 = x106 && x98 = x105 && x107 = 1 + x100 (10) l11(x112, x113, x114, x115, x116, x117, x118) -> l12(x119, x120, x121, x122, x123, x124, x125) :|: x118 = x125 && x117 = x124 && x116 = x123 && x115 = x122 && x114 = x121 && x113 = x120 && x112 = x119 (11) l12(x126, x127, x128, x129, x130, x131, x132) -> l7(x133, x134, x135, x136, x137, x138, x139) :|: x132 = x139 && x131 = x138 && x130 = x137 && x129 = x136 && x128 = x135 && x126 = x133 && x134 = 1 + x127 && x126 <= x128 (12) l12(x140, x141, x142, x143, x144, x145, x146) -> l10(x147, x148, x149, x150, x151, x152, x153) :|: x144 = x151 && x143 = x150 && x142 = x149 && x141 = x148 && x140 = x147 && x153 = x153 && x152 = x152 && 1 + x142 <= x140 (13) l8(x154, x155, x156, x157, x158, x159, x160) -> l6(x161, x162, x163, x164, x165, x166, x167) :|: x160 = x167 && x159 = x166 && x158 = x165 && x157 = x164 && x156 = x163 && x154 = x161 && x162 = 0 && x157 <= x155 (14) l8(x168, x169, x170, x171, x172, x173, x174) -> l11(x175, x176, x177, x178, x179, x180, x181) :|: x174 = x181 && x173 = x180 && x172 = x179 && x171 = x178 && x169 = x176 && x168 = x175 && x177 = 0 && 1 + x169 <= x171 (15) l13(x182, x183, x184, x185, x186, x187, x188) -> l14(x189, x190, x191, x192, x193, x194, x195) :|: x188 = x195 && x187 = x194 && x186 = x193 && x185 = x192 && x184 = x191 && x183 = x190 && x182 = x189 (16) l6(x196, x197, x198, x199, x200, x201, x202) -> l9(x203, x204, x205, x206, x207, x208, x209) :|: x202 = x209 && x201 = x208 && x200 = x207 && x199 = x206 && x198 = x205 && x197 = x204 && x196 = x203 (17) l14(x210, x211, x212, x213, x214, x215, x216) -> l0(x217, x218, x219, x220, x221, x222, x223) :|: x216 = x223 && x215 = x222 && x214 = x221 && x213 = x220 && x212 = x219 && x210 = x217 && x218 = 1 + x211 (18) l15(x224, x225, x226, x227, x228, x229, x230) -> l13(x231, x232, x233, x234, x235, x236, x237) :|: x230 = x237 && x229 = x236 && x228 = x235 && x227 = x234 && x226 = x233 && x225 = x232 && x224 = x231 && 1 + x228 <= x225 (19) l15(x238, x239, x240, x241, x242, x243, x244) -> l13(x245, x246, x247, x248, x249, x250, x251) :|: x244 = x251 && x243 = x250 && x242 = x249 && x241 = x248 && x240 = x247 && x239 = x246 && x238 = x245 && 1 + x239 <= x242 (20) l15(x252, x253, x254, x255, x256, x257, x258) -> l14(x259, x260, x261, x262, x263, x264, x265) :|: x258 = x265 && x257 = x264 && x256 = x263 && x255 = x262 && x254 = x261 && x253 = x260 && x252 = x259 && x256 <= x253 && x253 <= x256 (21) l1(x266, x267, x268, x269, x270, x271, x272) -> l7(x273, x274, x275, x276, x277, x278, x279) :|: x272 = x279 && x271 = x278 && x270 = x277 && x269 = x276 && x268 = x275 && x266 = x273 && x274 = 0 && x269 <= x267 (22) l1(x280, x281, x282, x283, x284, x285, x286) -> l15(x287, x288, x289, x290, x291, x292, x293) :|: x286 = x293 && x285 = x292 && x284 = x291 && x283 = x290 && x282 = x289 && x281 = x288 && x280 = x287 && 1 + x281 <= x283 (23) l4(x294, x295, x296, x297, x298, x299, x300) -> l2(x301, x302, x303, x304, x305, x306, x307) :|: x300 = x307 && x299 = x306 && x298 = x305 && x297 = x304 && x296 = x303 && x295 = x302 && x294 = x301 (24) l16(x308, x309, x310, x311, x312, x313, x314) -> l0(x315, x316, x317, x318, x319, x320, x321) :|: x314 = x321 && x313 = x320 && x310 = x317 && x316 = 0 && x319 = 0 && x315 = 5 && x318 = 5 (25) l17(x322, x323, x324, x325, x326, x327, x328) -> l16(x329, x330, x331, x332, x333, x334, x335) :|: x328 = x335 && x327 = x334 && x326 = x333 && x325 = x332 && x324 = x331 && x323 = x330 && x322 = x329 Arcs: (1) -> (21), (22) (3) -> (23) (4) -> (16) (6) -> (13), (14) (7) -> (23) (8) -> (4), (5) (9) -> (10) (10) -> (11), (12) (11) -> (6) (12) -> (9) (13) -> (16) (14) -> (10) (15) -> (17) (16) -> (7), (8) (17) -> (1) (18) -> (15) (19) -> (15) (20) -> (17) (21) -> (6) (22) -> (18), (19), (20) (23) -> (2), (3) (24) -> (1) (25) -> (24) This digraph is fully evaluated! ---------------------------------------- (4) Complex Obligation (AND) ---------------------------------------- (5) Obligation: Termination digraph: Nodes: (1) l0(edgecountHAT0, iHAT0, jHAT0, nodecountHAT0, sourceHAT0, xHAT0, yHAT0) -> l1(edgecountHATpost, iHATpost, jHATpost, nodecountHATpost, sourceHATpost, xHATpost, yHATpost) :|: yHAT0 = yHATpost && xHAT0 = xHATpost && sourceHAT0 = sourceHATpost && nodecountHAT0 = nodecountHATpost && jHAT0 = jHATpost && iHAT0 = iHATpost && edgecountHAT0 = edgecountHATpost (2) l14(x210, x211, x212, x213, x214, x215, x216) -> l0(x217, x218, x219, x220, x221, x222, x223) :|: x216 = x223 && x215 = x222 && x214 = x221 && x213 = x220 && x212 = x219 && x210 = x217 && x218 = 1 + x211 (3) l15(x252, x253, x254, x255, x256, x257, x258) -> l14(x259, x260, x261, x262, x263, x264, x265) :|: x258 = x265 && x257 = x264 && x256 = x263 && x255 = x262 && x254 = x261 && x253 = x260 && x252 = x259 && x256 <= x253 && x253 <= x256 (4) l13(x182, x183, x184, x185, x186, x187, x188) -> l14(x189, x190, x191, x192, x193, x194, x195) :|: x188 = x195 && x187 = x194 && x186 = x193 && x185 = x192 && x184 = x191 && x183 = x190 && x182 = x189 (5) l15(x238, x239, x240, x241, x242, x243, x244) -> l13(x245, x246, x247, x248, x249, x250, x251) :|: x244 = x251 && x243 = x250 && x242 = x249 && x241 = x248 && x240 = x247 && x239 = x246 && x238 = x245 && 1 + x239 <= x242 (6) l15(x224, x225, x226, x227, x228, x229, x230) -> l13(x231, x232, x233, x234, x235, x236, x237) :|: x230 = x237 && x229 = x236 && x228 = x235 && x227 = x234 && x226 = x233 && x225 = x232 && x224 = x231 && 1 + x228 <= x225 (7) l1(x280, x281, x282, x283, x284, x285, x286) -> l15(x287, x288, x289, x290, x291, x292, x293) :|: x286 = x293 && x285 = x292 && x284 = x291 && x283 = x290 && x282 = x289 && x281 = x288 && x280 = x287 && 1 + x281 <= x283 Arcs: (1) -> (7) (2) -> (1) (3) -> (2) (4) -> (2) (5) -> (4) (6) -> (4) (7) -> (3), (5), (6) This digraph is fully evaluated! ---------------------------------------- (6) IntTRSCompressionProof (EQUIVALENT) Compressed rules. ---------------------------------------- (7) Obligation: Rules: l15(edgecountHATpost:0, x190:0, jHATpost:0, nodecountHATpost:0, sourceHATpost:0, x194:0, x195:0) -> l15(edgecountHATpost:0, 1 + x190:0, jHATpost:0, nodecountHATpost:0, sourceHATpost:0, x194:0, x195:0) :|: sourceHATpost:0 >= 1 + x190:0 && nodecountHATpost:0 >= 1 + (1 + x190:0) l15(x, x1, x2, x3, x4, x5, x6) -> l15(x, 1 + x1, x2, x3, x4, x5, x6) :|: x1 >= 1 + x4 && x3 >= 1 + (1 + x1) l15(x7, x8, x9, x10, x8, x11, x12) -> l15(x7, 1 + x8, x9, x10, x8, x11, x12) :|: x10 >= 1 + (1 + x8) ---------------------------------------- (8) IntTRSUnneededArgumentFilterProof (EQUIVALENT) Some arguments are removed because they cannot influence termination. We removed arguments according to the following replacements: l15(x1, x2, x3, x4, x5, x6, x7) -> l15(x2, x4, x5) ---------------------------------------- (9) Obligation: Rules: l15(x190:0, nodecountHATpost:0, sourceHATpost:0) -> l15(1 + x190:0, nodecountHATpost:0, sourceHATpost:0) :|: sourceHATpost:0 >= 1 + x190:0 && nodecountHATpost:0 >= 1 + (1 + x190:0) l15(x1, x3, x4) -> l15(1 + x1, x3, x4) :|: x1 >= 1 + x4 && x3 >= 1 + (1 + x1) l15(x8, x10, x8) -> l15(1 + x8, x10, x8) :|: x10 >= 1 + (1 + x8) ---------------------------------------- (10) TempFilterProof (SOUND) Used the following sort dictionary for filtering: l15(INTEGER, INTEGER, INTEGER) Replaced non-predefined constructor symbols by 0. ---------------------------------------- (11) Obligation: Rules: l15(x190:0, nodecountHATpost:0, sourceHATpost:0) -> l15(c, nodecountHATpost:0, sourceHATpost:0) :|: c = 1 + x190:0 && (sourceHATpost:0 >= 1 + x190:0 && nodecountHATpost:0 >= 1 + (1 + x190:0)) l15(x1, x3, x4) -> l15(c1, x3, x4) :|: c1 = 1 + x1 && (x1 >= 1 + x4 && x3 >= 1 + (1 + x1)) l15(x8, x10, x8) -> l15(c2, x10, x8) :|: c2 = 1 + x8 && x10 >= 1 + (1 + x8) ---------------------------------------- (12) PolynomialOrderProcessor (EQUIVALENT) Found the following polynomial interpretation: [l15(x, x1, x2)] = -x + x1 The following rules are decreasing: l15(x190:0, nodecountHATpost:0, sourceHATpost:0) -> l15(c, nodecountHATpost:0, sourceHATpost:0) :|: c = 1 + x190:0 && (sourceHATpost:0 >= 1 + x190:0 && nodecountHATpost:0 >= 1 + (1 + x190:0)) l15(x1, x3, x4) -> l15(c1, x3, x4) :|: c1 = 1 + x1 && (x1 >= 1 + x4 && x3 >= 1 + (1 + x1)) l15(x8, x10, x8) -> l15(c2, x10, x8) :|: c2 = 1 + x8 && x10 >= 1 + (1 + x8) The following rules are bounded: l15(x190:0, nodecountHATpost:0, sourceHATpost:0) -> l15(c, nodecountHATpost:0, sourceHATpost:0) :|: c = 1 + x190:0 && (sourceHATpost:0 >= 1 + x190:0 && nodecountHATpost:0 >= 1 + (1 + x190:0)) l15(x8, x10, x8) -> l15(c2, x10, x8) :|: c2 = 1 + x8 && x10 >= 1 + (1 + x8) ---------------------------------------- (13) Obligation: Rules: l15(x1, x3, x4) -> l15(c1, x3, x4) :|: c1 = 1 + x1 && (x1 >= 1 + x4 && x3 >= 1 + (1 + x1)) ---------------------------------------- (14) RankingReductionPairProof (EQUIVALENT) Interpretation: [ l15 ] = -1*l15_1 + l15_2 The following rules are decreasing: l15(x1, x3, x4) -> l15(c1, x3, x4) :|: c1 = 1 + x1 && (x1 >= 1 + x4 && x3 >= 1 + (1 + x1)) The following rules are bounded: l15(x1, x3, x4) -> l15(c1, x3, x4) :|: c1 = 1 + x1 && (x1 >= 1 + x4 && x3 >= 1 + (1 + x1)) ---------------------------------------- (15) YES ---------------------------------------- (16) Obligation: Termination digraph: Nodes: (1) l7(x56, x57, x58, x59, x60, x61, x62) -> l8(x63, x64, x65, x66, x67, x68, x69) :|: x62 = x69 && x61 = x68 && x60 = x67 && x59 = x66 && x58 = x65 && x57 = x64 && x56 = x63 (2) l12(x126, x127, x128, x129, x130, x131, x132) -> l7(x133, x134, x135, x136, x137, x138, x139) :|: x132 = x139 && x131 = x138 && x130 = x137 && x129 = x136 && x128 = x135 && x126 = x133 && x134 = 1 + x127 && x126 <= x128 (3) l11(x112, x113, x114, x115, x116, x117, x118) -> l12(x119, x120, x121, x122, x123, x124, x125) :|: x118 = x125 && x117 = x124 && x116 = x123 && x115 = x122 && x114 = x121 && x113 = x120 && x112 = x119 (4) l8(x168, x169, x170, x171, x172, x173, x174) -> l11(x175, x176, x177, x178, x179, x180, x181) :|: x174 = x181 && x173 = x180 && x172 = x179 && x171 = x178 && x169 = x176 && x168 = x175 && x177 = 0 && 1 + x169 <= x171 (5) l10(x98, x99, x100, x101, x102, x103, x104) -> l11(x105, x106, x107, x108, x109, x110, x111) :|: x104 = x111 && x103 = x110 && x102 = x109 && x101 = x108 && x99 = x106 && x98 = x105 && x107 = 1 + x100 (6) l12(x140, x141, x142, x143, x144, x145, x146) -> l10(x147, x148, x149, x150, x151, x152, x153) :|: x144 = x151 && x143 = x150 && x142 = x149 && x141 = x148 && x140 = x147 && x153 = x153 && x152 = x152 && 1 + x142 <= x140 Arcs: (1) -> (4) (2) -> (1) (3) -> (2), (6) (4) -> (3) (5) -> (3) (6) -> (5) This digraph is fully evaluated! ---------------------------------------- (17) IntTRSCompressionProof (EQUIVALENT) Compressed rules. ---------------------------------------- (18) Obligation: Rules: l11(x112:0, x113:0, x114:0, x115:0, x116:0, x117:0, x118:0) -> l11(x112:0, 1 + x113:0, 0, x115:0, x116:0, x117:0, x118:0) :|: x114:0 >= x112:0 && x115:0 >= 1 + (1 + x113:0) l11(x, x1, x2, x3, x4, x5, x6) -> l11(x, x1, 1 + x2, x3, x4, x7, x8) :|: x >= 1 + x2 ---------------------------------------- (19) IntTRSUnneededArgumentFilterProof (EQUIVALENT) Some arguments are removed because they cannot influence termination. We removed arguments according to the following replacements: l11(x1, x2, x3, x4, x5, x6, x7) -> l11(x1, x2, x3, x4) ---------------------------------------- (20) Obligation: Rules: l11(x112:0, x113:0, x114:0, x115:0) -> l11(x112:0, 1 + x113:0, 0, x115:0) :|: x114:0 >= x112:0 && x115:0 >= 1 + (1 + x113:0) l11(x, x1, x2, x3) -> l11(x, x1, 1 + x2, x3) :|: x >= 1 + x2 ---------------------------------------- (21) TempFilterProof (SOUND) Used the following sort dictionary for filtering: l11(INTEGER, VARIABLE, VARIABLE, VARIABLE) Replaced non-predefined constructor symbols by 0. ---------------------------------------- (22) Obligation: Rules: l11(x112:0, x113:0, x114:0, x115:0) -> l11(x112:0, c, c1, x115:0) :|: c1 = 0 && c = 1 + x113:0 && (x114:0 >= x112:0 && x115:0 >= 1 + (1 + x113:0)) l11(x, x1, x2, x3) -> l11(x, x1, c2, x3) :|: c2 = 1 + x2 && x >= 1 + x2 ---------------------------------------- (23) RankingReductionPairProof (EQUIVALENT) Interpretation: [ l11 ] = 2*l11_4 + -2*l11_2 The following rules are decreasing: l11(x112:0, x113:0, x114:0, x115:0) -> l11(x112:0, c, c1, x115:0) :|: c1 = 0 && c = 1 + x113:0 && (x114:0 >= x112:0 && x115:0 >= 1 + (1 + x113:0)) The following rules are bounded: l11(x112:0, x113:0, x114:0, x115:0) -> l11(x112:0, c, c1, x115:0) :|: c1 = 0 && c = 1 + x113:0 && (x114:0 >= x112:0 && x115:0 >= 1 + (1 + x113:0)) ---------------------------------------- (24) Obligation: Rules: l11(x, x1, x2, x3) -> l11(x, x1, c2, x3) :|: c2 = 1 + x2 && x >= 1 + x2 ---------------------------------------- (25) PolynomialOrderProcessor (EQUIVALENT) Found the following polynomial interpretation: [l11(x, x1, x2, x3)] = x - x2 The following rules are decreasing: l11(x, x1, x2, x3) -> l11(x, x1, c2, x3) :|: c2 = 1 + x2 && x >= 1 + x2 The following rules are bounded: l11(x, x1, x2, x3) -> l11(x, x1, c2, x3) :|: c2 = 1 + x2 && x >= 1 + x2 ---------------------------------------- (26) YES ---------------------------------------- (27) Obligation: Termination digraph: Nodes: (1) l6(x196, x197, x198, x199, x200, x201, x202) -> l9(x203, x204, x205, x206, x207, x208, x209) :|: x202 = x209 && x201 = x208 && x200 = x207 && x199 = x206 && x198 = x205 && x197 = x204 && x196 = x203 (2) l5(x28, x29, x30, x31, x32, x33, x34) -> l6(x35, x36, x37, x38, x39, x40, x41) :|: x34 = x41 && x33 = x40 && x32 = x39 && x31 = x38 && x30 = x37 && x28 = x35 && x36 = 1 + x29 (3) l9(x84, x85, x86, x87, x88, x89, x90) -> l5(x91, x92, x93, x94, x95, x96, x97) :|: x88 = x95 && x87 = x94 && x86 = x93 && x85 = x92 && x84 = x91 && x97 = x97 && x96 = x96 && 1 + x85 <= x84 Arcs: (1) -> (3) (2) -> (1) (3) -> (2) This digraph is fully evaluated! ---------------------------------------- (28) IntTRSCompressionProof (EQUIVALENT) Compressed rules. ---------------------------------------- (29) Obligation: Rules: l5(x203:0, x29:0, x205:0, x206:0, x207:0, x208:0, x209:0) -> l5(x203:0, 1 + x29:0, x205:0, x206:0, x207:0, x96:0, x97:0) :|: x203:0 >= 1 + (1 + x29:0) ---------------------------------------- (30) IntTRSUnneededArgumentFilterProof (EQUIVALENT) Some arguments are removed because they cannot influence termination. We removed arguments according to the following replacements: l5(x1, x2, x3, x4, x5, x6, x7) -> l5(x1, x2) ---------------------------------------- (31) Obligation: Rules: l5(x203:0, x29:0) -> l5(x203:0, 1 + x29:0) :|: x203:0 >= 1 + (1 + x29:0) ---------------------------------------- (32) TempFilterProof (SOUND) Used the following sort dictionary for filtering: l5(INTEGER, INTEGER) Replaced non-predefined constructor symbols by 0. ---------------------------------------- (33) Obligation: Rules: l5(x203:0, x29:0) -> l5(x203:0, c) :|: c = 1 + x29:0 && x203:0 >= 1 + (1 + x29:0) ---------------------------------------- (34) PolynomialOrderProcessor (EQUIVALENT) Found the following polynomial interpretation: [l5(x, x1)] = x - x1 The following rules are decreasing: l5(x203:0, x29:0) -> l5(x203:0, c) :|: c = 1 + x29:0 && x203:0 >= 1 + (1 + x29:0) The following rules are bounded: l5(x203:0, x29:0) -> l5(x203:0, c) :|: c = 1 + x29:0 && x203:0 >= 1 + (1 + x29:0) ---------------------------------------- (35) YES ---------------------------------------- (36) Obligation: Termination digraph: Nodes: (1) l4(x294, x295, x296, x297, x298, x299, x300) -> l2(x301, x302, x303, x304, x305, x306, x307) :|: x300 = x307 && x299 = x306 && x298 = x305 && x297 = x304 && x296 = x303 && x295 = x302 && x294 = x301 (2) l2(x14, x15, x16, x17, x18, x19, x20) -> l4(x21, x22, x23, x24, x25, x26, x27) :|: x20 = x27 && x19 = x26 && x18 = x25 && x17 = x24 && x16 = x23 && x14 = x21 && x22 = 1 + x15 && 1 + x15 <= x17 Arcs: (1) -> (2) (2) -> (1) This digraph is fully evaluated! ---------------------------------------- (37) IntTRSCompressionProof (EQUIVALENT) Compressed rules. ---------------------------------------- (38) Obligation: Rules: l4(x21:0, x295:0, x23:0, x24:0, x25:0, x26:0, x27:0) -> l4(x21:0, 1 + x295:0, x23:0, x24:0, x25:0, x26:0, x27:0) :|: x24:0 >= 1 + x295:0 ---------------------------------------- (39) IntTRSUnneededArgumentFilterProof (EQUIVALENT) Some arguments are removed because they cannot influence termination. We removed arguments according to the following replacements: l4(x1, x2, x3, x4, x5, x6, x7) -> l4(x2, x4) ---------------------------------------- (40) Obligation: Rules: l4(x295:0, x24:0) -> l4(1 + x295:0, x24:0) :|: x24:0 >= 1 + x295:0 ---------------------------------------- (41) TempFilterProof (SOUND) Used the following sort dictionary for filtering: l4(INTEGER, INTEGER) Replaced non-predefined constructor symbols by 0. ---------------------------------------- (42) Obligation: Rules: l4(x295:0, x24:0) -> l4(c, x24:0) :|: c = 1 + x295:0 && x24:0 >= 1 + x295:0 ---------------------------------------- (43) RankingReductionPairProof (EQUIVALENT) Interpretation: [ l4 ] = l4_2 + -1*l4_1 The following rules are decreasing: l4(x295:0, x24:0) -> l4(c, x24:0) :|: c = 1 + x295:0 && x24:0 >= 1 + x295:0 The following rules are bounded: l4(x295:0, x24:0) -> l4(c, x24:0) :|: c = 1 + x295:0 && x24:0 >= 1 + x295:0 ---------------------------------------- (44) YES