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