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, 14 ms] (7) IRSwT (8) IntTRSUnneededArgumentFilterProof [EQUIVALENT, 0 ms] (9) IRSwT (10) TempFilterProof [SOUND, 25 ms] (11) IntTRS (12) PolynomialOrderProcessor [EQUIVALENT, 2 ms] (13) IntTRS (14) RankingReductionPairProof [EQUIVALENT, 0 ms] (15) YES (16) IRSwT (17) IntTRSCompressionProof [EQUIVALENT, 10 ms] (18) IRSwT (19) IntTRSUnneededArgumentFilterProof [EQUIVALENT, 0 ms] (20) IRSwT (21) TempFilterProof [SOUND, 29 ms] (22) IntTRS (23) RankingReductionPairProof [EQUIVALENT, 1 ms] (24) IntTRS (25) PolynomialOrderProcessor [EQUIVALENT, 3 ms] (26) YES (27) IRSwT (28) IntTRSCompressionProof [EQUIVALENT, 9 ms] (29) IRSwT (30) IntTRSUnneededArgumentFilterProof [EQUIVALENT, 0 ms] (31) IRSwT (32) TempFilterProof [SOUND, 26 ms] (33) IntTRS (34) RankingReductionPairProof [EQUIVALENT, 10 ms] (35) YES (36) IRSwT (37) IntTRSCompressionProof [EQUIVALENT, 22 ms] (38) IRSwT (39) IntTRSUnneededArgumentFilterProof [EQUIVALENT, 0 ms] (40) IRSwT (41) TempFilterProof [SOUND, 19 ms] (42) IntTRS (43) PolynomialOrderProcessor [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) -> l6(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) -> l2(x63, x64, x65, x66, x67, x68, x69) :|: x62 = x69 && x61 = x68 && x60 = x67 && x59 = x66 && x58 = x65 && x56 = x63 && x64 = 0 && x56 <= x57 l7(x70, x71, x72, x73, x74, x75, x76) -> l3(x77, x78, x79, x80, x81, x82, x83) :|: x74 = x81 && x73 = x80 && x72 = x79 && x71 = x78 && x70 = x77 && x83 = x83 && x82 = x82 && 1 + x71 <= x70 l8(x84, x85, x86, x87, x88, x89, x90) -> l9(x91, x92, x93, x94, x95, x96, x97) :|: x90 = x97 && x89 = x96 && x88 = x95 && x87 = x94 && x86 = x93 && x85 = x92 && x84 = x91 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 l12(x112, x113, x114, x115, x116, x117, x118) -> l8(x119, x120, x121, x122, x123, x124, x125) :|: x118 = x125 && x117 = x124 && x116 = x123 && x115 = x122 && x114 = x121 && x112 = x119 && x120 = 1 + x113 && x112 <= x114 l12(x126, x127, x128, x129, x130, x131, x132) -> l10(x133, x134, x135, x136, x137, x138, x139) :|: x130 = x137 && x129 = x136 && x128 = x135 && x127 = x134 && x126 = x133 && x139 = x139 && x138 = x138 && 1 + x128 <= x126 l9(x140, x141, x142, x143, x144, x145, x146) -> l4(x147, x148, x149, x150, x151, x152, x153) :|: x146 = x153 && x145 = x152 && x144 = x151 && x143 = x150 && x142 = x149 && x140 = x147 && x148 = 0 && x143 <= x141 l9(x154, x155, x156, x157, x158, x159, x160) -> l11(x161, x162, x163, x164, x165, x166, x167) :|: x160 = x167 && x159 = x166 && x158 = x165 && x157 = x164 && x155 = x162 && x154 = x161 && x163 = 0 && 1 + x155 <= x157 l11(x168, x169, x170, x171, x172, x173, x174) -> l12(x175, x176, x177, x178, x179, x180, x181) :|: x174 = x181 && x173 = x180 && x172 = x179 && x171 = x178 && x170 = x177 && x169 = x176 && x168 = x175 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 l14(x196, x197, x198, x199, x200, x201, x202) -> l5(x203, x204, x205, x206, x207, x208, x209) :|: x202 = x209 && x201 = x208 && x200 = x207 && x199 = x206 && x198 = x205 && x196 = x203 && x204 = 1 + 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 + x214 <= 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 + x225 <= x228 l15(x238, x239, x240, x241, x242, x243, x244) -> l14(x245, x246, x247, x248, x249, x250, x251) :|: x244 = x251 && x243 = x250 && x242 = x249 && x241 = x248 && x240 = x247 && x239 = x246 && x238 = x245 && x242 <= x239 && x239 <= x242 l6(x252, x253, x254, x255, x256, x257, x258) -> l8(x259, x260, x261, x262, x263, x264, x265) :|: x258 = x265 && x257 = x264 && x256 = x263 && x255 = x262 && x254 = x261 && x252 = x259 && x260 = 0 && x255 <= x253 l6(x266, x267, x268, x269, x270, x271, x272) -> l15(x273, x274, x275, x276, x277, x278, x279) :|: x272 = x279 && x271 = x278 && x270 = x277 && x269 = x276 && x268 = x275 && x267 = x274 && x266 = x273 && 1 + x267 <= x269 l4(x280, x281, x282, x283, x284, x285, x286) -> l7(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) -> l5(x315, x316, x317, x318, x319, x320, x321) :|: x314 = x321 && x313 = x320 && x310 = x317 && x316 = 0 && x319 = 0 && x315 = 8 && 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) -> l6(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) -> l2(x63, x64, x65, x66, x67, x68, x69) :|: x62 = x69 && x61 = x68 && x60 = x67 && x59 = x66 && x58 = x65 && x56 = x63 && x64 = 0 && x56 <= x57 l7(x70, x71, x72, x73, x74, x75, x76) -> l3(x77, x78, x79, x80, x81, x82, x83) :|: x74 = x81 && x73 = x80 && x72 = x79 && x71 = x78 && x70 = x77 && x83 = x83 && x82 = x82 && 1 + x71 <= x70 l8(x84, x85, x86, x87, x88, x89, x90) -> l9(x91, x92, x93, x94, x95, x96, x97) :|: x90 = x97 && x89 = x96 && x88 = x95 && x87 = x94 && x86 = x93 && x85 = x92 && x84 = x91 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 l12(x112, x113, x114, x115, x116, x117, x118) -> l8(x119, x120, x121, x122, x123, x124, x125) :|: x118 = x125 && x117 = x124 && x116 = x123 && x115 = x122 && x114 = x121 && x112 = x119 && x120 = 1 + x113 && x112 <= x114 l12(x126, x127, x128, x129, x130, x131, x132) -> l10(x133, x134, x135, x136, x137, x138, x139) :|: x130 = x137 && x129 = x136 && x128 = x135 && x127 = x134 && x126 = x133 && x139 = x139 && x138 = x138 && 1 + x128 <= x126 l9(x140, x141, x142, x143, x144, x145, x146) -> l4(x147, x148, x149, x150, x151, x152, x153) :|: x146 = x153 && x145 = x152 && x144 = x151 && x143 = x150 && x142 = x149 && x140 = x147 && x148 = 0 && x143 <= x141 l9(x154, x155, x156, x157, x158, x159, x160) -> l11(x161, x162, x163, x164, x165, x166, x167) :|: x160 = x167 && x159 = x166 && x158 = x165 && x157 = x164 && x155 = x162 && x154 = x161 && x163 = 0 && 1 + x155 <= x157 l11(x168, x169, x170, x171, x172, x173, x174) -> l12(x175, x176, x177, x178, x179, x180, x181) :|: x174 = x181 && x173 = x180 && x172 = x179 && x171 = x178 && x170 = x177 && x169 = x176 && x168 = x175 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 l14(x196, x197, x198, x199, x200, x201, x202) -> l5(x203, x204, x205, x206, x207, x208, x209) :|: x202 = x209 && x201 = x208 && x200 = x207 && x199 = x206 && x198 = x205 && x196 = x203 && x204 = 1 + 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 + x214 <= 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 + x225 <= x228 l15(x238, x239, x240, x241, x242, x243, x244) -> l14(x245, x246, x247, x248, x249, x250, x251) :|: x244 = x251 && x243 = x250 && x242 = x249 && x241 = x248 && x240 = x247 && x239 = x246 && x238 = x245 && x242 <= x239 && x239 <= x242 l6(x252, x253, x254, x255, x256, x257, x258) -> l8(x259, x260, x261, x262, x263, x264, x265) :|: x258 = x265 && x257 = x264 && x256 = x263 && x255 = x262 && x254 = x261 && x252 = x259 && x260 = 0 && x255 <= x253 l6(x266, x267, x268, x269, x270, x271, x272) -> l15(x273, x274, x275, x276, x277, x278, x279) :|: x272 = x279 && x271 = x278 && x270 = x277 && x269 = x276 && x268 = x275 && x267 = x274 && x266 = x273 && 1 + x267 <= x269 l4(x280, x281, x282, x283, x284, x285, x286) -> l7(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) -> l5(x315, x316, x317, x318, x319, x320, x321) :|: x314 = x321 && x313 = x320 && x310 = x317 && x316 = 0 && x319 = 0 && x315 = 8 && 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) -> l6(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) -> l2(x63, x64, x65, x66, x67, x68, x69) :|: x62 = x69 && x61 = x68 && x60 = x67 && x59 = x66 && x58 = x65 && x56 = x63 && x64 = 0 && x56 <= x57 (7) l7(x70, x71, x72, x73, x74, x75, x76) -> l3(x77, x78, x79, x80, x81, x82, x83) :|: x74 = x81 && x73 = x80 && x72 = x79 && x71 = x78 && x70 = x77 && x83 = x83 && x82 = x82 && 1 + x71 <= x70 (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 && x86 = x93 && x85 = x92 && x84 = x91 (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) l12(x112, x113, x114, x115, x116, x117, x118) -> l8(x119, x120, x121, x122, x123, x124, x125) :|: x118 = x125 && x117 = x124 && x116 = x123 && x115 = x122 && x114 = x121 && x112 = x119 && x120 = 1 + x113 && x112 <= x114 (11) l12(x126, x127, x128, x129, x130, x131, x132) -> l10(x133, x134, x135, x136, x137, x138, x139) :|: x130 = x137 && x129 = x136 && x128 = x135 && x127 = x134 && x126 = x133 && x139 = x139 && x138 = x138 && 1 + x128 <= x126 (12) l9(x140, x141, x142, x143, x144, x145, x146) -> l4(x147, x148, x149, x150, x151, x152, x153) :|: x146 = x153 && x145 = x152 && x144 = x151 && x143 = x150 && x142 = x149 && x140 = x147 && x148 = 0 && x143 <= x141 (13) l9(x154, x155, x156, x157, x158, x159, x160) -> l11(x161, x162, x163, x164, x165, x166, x167) :|: x160 = x167 && x159 = x166 && x158 = x165 && x157 = x164 && x155 = x162 && x154 = x161 && x163 = 0 && 1 + x155 <= x157 (14) l11(x168, x169, x170, x171, x172, x173, x174) -> l12(x175, x176, x177, x178, x179, x180, x181) :|: x174 = x181 && x173 = x180 && x172 = x179 && x171 = x178 && x170 = x177 && x169 = x176 && x168 = x175 (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) l14(x196, x197, x198, x199, x200, x201, x202) -> l5(x203, x204, x205, x206, x207, x208, x209) :|: x202 = x209 && x201 = x208 && x200 = x207 && x199 = x206 && x198 = x205 && x196 = x203 && x204 = 1 + 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 + x214 <= 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 + x225 <= x228 (19) l15(x238, x239, x240, x241, x242, x243, x244) -> l14(x245, x246, x247, x248, x249, x250, x251) :|: x244 = x251 && x243 = x250 && x242 = x249 && x241 = x248 && x240 = x247 && x239 = x246 && x238 = x245 && x242 <= x239 && x239 <= x242 (20) l6(x252, x253, x254, x255, x256, x257, x258) -> l8(x259, x260, x261, x262, x263, x264, x265) :|: x258 = x265 && x257 = x264 && x256 = x263 && x255 = x262 && x254 = x261 && x252 = x259 && x260 = 0 && x255 <= x253 (21) l6(x266, x267, x268, x269, x270, x271, x272) -> l15(x273, x274, x275, x276, x277, x278, x279) :|: x272 = x279 && x271 = x278 && x270 = x277 && x269 = x276 && x268 = x275 && x267 = x274 && x266 = x273 && 1 + x267 <= x269 (22) l4(x280, x281, x282, x283, x284, x285, x286) -> l7(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) -> l5(x315, x316, x317, x318, x319, x320, x321) :|: x314 = x321 && x313 = x320 && x310 = x317 && x316 = 0 && x319 = 0 && x315 = 8 && 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) -> (20), (21) (6) -> (23) (7) -> (3), (4) (8) -> (12), (13) (9) -> (14) (10) -> (8) (11) -> (9) (12) -> (22) (13) -> (14) (14) -> (10), (11) (15) -> (16) (16) -> (5) (17) -> (15) (18) -> (15) (19) -> (16) (20) -> (8) (21) -> (17), (18), (19) (22) -> (6), (7) (23) -> (1), (2) (24) -> (5) (25) -> (24) This digraph is fully evaluated! ---------------------------------------- (4) Complex Obligation (AND) ---------------------------------------- (5) Obligation: Termination digraph: Nodes: (1) l5(x42, x43, x44, x45, x46, x47, x48) -> l6(x49, x50, x51, x52, x53, x54, x55) :|: x48 = x55 && x47 = x54 && x46 = x53 && x45 = x52 && x44 = x51 && x43 = x50 && x42 = x49 (2) l14(x196, x197, x198, x199, x200, x201, x202) -> l5(x203, x204, x205, x206, x207, x208, x209) :|: x202 = x209 && x201 = x208 && x200 = x207 && x199 = x206 && x198 = x205 && x196 = x203 && x204 = 1 + x197 (3) l15(x238, x239, x240, x241, x242, x243, x244) -> l14(x245, x246, x247, x248, x249, x250, x251) :|: x244 = x251 && x243 = x250 && x242 = x249 && x241 = x248 && x240 = x247 && x239 = x246 && x238 = x245 && x242 <= x239 && x239 <= x242 (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(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 + x225 <= x228 (6) 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 + x214 <= x211 (7) l6(x266, x267, x268, x269, x270, x271, x272) -> l15(x273, x274, x275, x276, x277, x278, x279) :|: x272 = x279 && x271 = x278 && x270 = x277 && x269 = x276 && x268 = x275 && x267 = x274 && x266 = x273 && 1 + x267 <= x269 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(x189:0, x190:0, x191:0, x192:0, x193:0, x194:0, x195:0) -> l15(x189:0, 1 + x190:0, x191:0, x192:0, x193:0, x194:0, x195:0) :|: x193:0 >= 1 + x190:0 && x192: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(x203:0, x207:0, x205:0, x206:0, x207:0, x208:0, x209:0) -> l15(x203:0, 1 + x207:0, x205:0, x206:0, x207:0, x208:0, x209:0) :|: x206:0 >= 1 + (1 + x207: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(x190:0, x192:0, x193:0) -> l15(1 + x190:0, x192:0, x193:0) :|: x193:0 >= 1 + x190:0 && x192:0 >= 1 + (1 + x190:0) l15(x1, x3, x4) -> l15(1 + x1, x3, x4) :|: x1 >= 1 + x4 && x3 >= 1 + (1 + x1) l15(x207:0, x206:0, x207:0) -> l15(1 + x207:0, x206:0, x207:0) :|: x206:0 >= 1 + (1 + x207: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(x190:0, x192:0, x193:0) -> l15(c, x192:0, x193:0) :|: c = 1 + x190:0 && (x193:0 >= 1 + x190:0 && x192:0 >= 1 + (1 + x190:0)) l15(x1, x3, x4) -> l15(c1, x3, x4) :|: c1 = 1 + x1 && (x1 >= 1 + x4 && x3 >= 1 + (1 + x1)) l15(x207:0, x206:0, x207:0) -> l15(c2, x206:0, x207:0) :|: c2 = 1 + x207:0 && x206:0 >= 1 + (1 + x207:0) ---------------------------------------- (12) PolynomialOrderProcessor (EQUIVALENT) Found the following polynomial interpretation: [l15(x, x1, x2)] = -x + x1 The following rules are decreasing: l15(x190:0, x192:0, x193:0) -> l15(c, x192:0, x193:0) :|: c = 1 + x190:0 && (x193:0 >= 1 + x190:0 && x192:0 >= 1 + (1 + x190:0)) l15(x1, x3, x4) -> l15(c1, x3, x4) :|: c1 = 1 + x1 && (x1 >= 1 + x4 && x3 >= 1 + (1 + x1)) l15(x207:0, x206:0, x207:0) -> l15(c2, x206:0, x207:0) :|: c2 = 1 + x207:0 && x206:0 >= 1 + (1 + x207:0) The following rules are bounded: l15(x190:0, x192:0, x193:0) -> l15(c, x192:0, x193:0) :|: c = 1 + x190:0 && (x193:0 >= 1 + x190:0 && x192:0 >= 1 + (1 + x190:0)) l15(x207:0, x206:0, x207:0) -> l15(c2, x206:0, x207:0) :|: c2 = 1 + x207:0 && x206:0 >= 1 + (1 + x207: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) l8(x84, x85, x86, x87, x88, x89, x90) -> l9(x91, x92, x93, x94, x95, x96, x97) :|: x90 = x97 && x89 = x96 && x88 = x95 && x87 = x94 && x86 = x93 && x85 = x92 && x84 = x91 (2) l12(x112, x113, x114, x115, x116, x117, x118) -> l8(x119, x120, x121, x122, x123, x124, x125) :|: x118 = x125 && x117 = x124 && x116 = x123 && x115 = x122 && x114 = x121 && x112 = x119 && x120 = 1 + x113 && x112 <= x114 (3) l11(x168, x169, x170, x171, x172, x173, x174) -> l12(x175, x176, x177, x178, x179, x180, x181) :|: x174 = x181 && x173 = x180 && x172 = x179 && x171 = x178 && x170 = x177 && x169 = x176 && x168 = x175 (4) l9(x154, x155, x156, x157, x158, x159, x160) -> l11(x161, x162, x163, x164, x165, x166, x167) :|: x160 = x167 && x159 = x166 && x158 = x165 && x157 = x164 && x155 = x162 && x154 = x161 && x163 = 0 && 1 + x155 <= x157 (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(x126, x127, x128, x129, x130, x131, x132) -> l10(x133, x134, x135, x136, x137, x138, x139) :|: x130 = x137 && x129 = x136 && x128 = x135 && x127 = x134 && x126 = x133 && x139 = x139 && x138 = x138 && 1 + x128 <= x126 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(x119:0, x169:0, x121:0, x122:0, x123:0, x124:0, x125:0) -> l11(x119:0, 1 + x169:0, 0, x122:0, x123:0, x124:0, x125:0) :|: x121:0 >= x119:0 && x122:0 >= 1 + (1 + x169:0) l11(x105:0, x106:0, x135:0, x108:0, x109:0, x173:0, x174:0) -> l11(x105:0, x106:0, 1 + x135:0, x108:0, x109:0, x110:0, x111:0) :|: x105:0 >= 1 + x135:0 ---------------------------------------- (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(x119:0, x169:0, x121:0, x122:0) -> l11(x119:0, 1 + x169:0, 0, x122:0) :|: x121:0 >= x119:0 && x122:0 >= 1 + (1 + x169:0) l11(x105:0, x106:0, x135:0, x108:0) -> l11(x105:0, x106:0, 1 + x135:0, x108:0) :|: x105:0 >= 1 + x135:0 ---------------------------------------- (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(x119:0, x169:0, x121:0, x122:0) -> l11(x119:0, c, c1, x122:0) :|: c1 = 0 && c = 1 + x169:0 && (x121:0 >= x119:0 && x122:0 >= 1 + (1 + x169:0)) l11(x105:0, x106:0, x135:0, x108:0) -> l11(x105:0, x106:0, c2, x108:0) :|: c2 = 1 + x135:0 && x105:0 >= 1 + x135:0 ---------------------------------------- (23) RankingReductionPairProof (EQUIVALENT) Interpretation: [ l11 ] = 2*l11_4 + -2*l11_2 The following rules are decreasing: l11(x119:0, x169:0, x121:0, x122:0) -> l11(x119:0, c, c1, x122:0) :|: c1 = 0 && c = 1 + x169:0 && (x121:0 >= x119:0 && x122:0 >= 1 + (1 + x169:0)) The following rules are bounded: l11(x119:0, x169:0, x121:0, x122:0) -> l11(x119:0, c, c1, x122:0) :|: c1 = 0 && c = 1 + x169:0 && (x121:0 >= x119:0 && x122:0 >= 1 + (1 + x169:0)) ---------------------------------------- (24) Obligation: Rules: l11(x105:0, x106:0, x135:0, x108:0) -> l11(x105:0, x106:0, c2, x108:0) :|: c2 = 1 + x135:0 && x105:0 >= 1 + x135:0 ---------------------------------------- (25) PolynomialOrderProcessor (EQUIVALENT) Found the following polynomial interpretation: [l11(x, x1, x2, x3)] = x - x2 The following rules are decreasing: l11(x105:0, x106:0, x135:0, x108:0) -> l11(x105:0, x106:0, c2, x108:0) :|: c2 = 1 + x135:0 && x105:0 >= 1 + x135:0 The following rules are bounded: l11(x105:0, x106:0, x135:0, x108:0) -> l11(x105:0, x106:0, c2, x108:0) :|: c2 = 1 + x135:0 && x105:0 >= 1 + x135: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) l7(x70, x71, x72, x73, x74, x75, x76) -> l3(x77, x78, x79, x80, x81, x82, x83) :|: x74 = x81 && x73 = x80 && x72 = x79 && x71 = x78 && x70 = x77 && x83 = x83 && x82 = x82 && 1 + x71 <= x70 (3) l4(x280, x281, x282, x283, x284, x285, x286) -> l7(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: l7(x21:0, x71:0, x23:0, x24:0, x25:0, x75:0, x76:0) -> l7(x21:0, 1 + x71:0, x23:0, x24:0, x25:0, x26:0, x27:0) :|: x21:0 >= 1 + x71:0 ---------------------------------------- (30) IntTRSUnneededArgumentFilterProof (EQUIVALENT) Some arguments are removed because they cannot influence termination. We removed arguments according to the following replacements: l7(x1, x2, x3, x4, x5, x6, x7) -> l7(x1, x2) ---------------------------------------- (31) Obligation: Rules: l7(x21:0, x71:0) -> l7(x21:0, 1 + x71:0) :|: x21:0 >= 1 + x71:0 ---------------------------------------- (32) TempFilterProof (SOUND) Used the following sort dictionary for filtering: l7(INTEGER, INTEGER) Replaced non-predefined constructor symbols by 0. ---------------------------------------- (33) Obligation: Rules: l7(x21:0, x71:0) -> l7(x21:0, c) :|: c = 1 + x71:0 && x21:0 >= 1 + x71:0 ---------------------------------------- (34) RankingReductionPairProof (EQUIVALENT) Interpretation: [ l7 ] = l7_1 + -1*l7_2 The following rules are decreasing: l7(x21:0, x71:0) -> l7(x21:0, c) :|: c = 1 + x71:0 && x21:0 >= 1 + x71:0 The following rules are bounded: l7(x21:0, x71:0) -> l7(x21:0, c) :|: c = 1 + x71:0 && x21:0 >= 1 + x71: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) PolynomialOrderProcessor (EQUIVALENT) Found the following polynomial interpretation: [l0(x, x1)] = -x + x1 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