NO proof of prog.inttrs # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty Termination of the given IRSwT could be disproven: (0) IRSwT (1) IRSFormatTransformerProof [EQUIVALENT, 0 ms] (2) IRSwT (3) IRSwTTerminationDigraphProof [EQUIVALENT, 1674 ms] (4) IRSwT (5) IntTRSCompressionProof [EQUIVALENT, 58 ms] (6) IRSwT (7) IntTRSUnneededArgumentFilterProof [EQUIVALENT, 0 ms] (8) IRSwT (9) FilterProof [EQUIVALENT, 0 ms] (10) IntTRS (11) IntTRSCompressionProof [EQUIVALENT, 0 ms] (12) IntTRS (13) IntTRSPeriodicNontermProof [COMPLETE, 9 ms] (14) NO ---------------------------------------- (0) Obligation: Rules: l0(Result_4HAT0, cnt_20HAT0, cnt_25HAT0, lt_10HAT0, lt_11HAT0, lt_12HAT0, p2_8HAT0, p_7HAT0, tmp_9HAT0, x_5HAT0, y_6HAT0) -> l1(Result_4HATpost, cnt_20HATpost, cnt_25HATpost, lt_10HATpost, lt_11HATpost, lt_12HATpost, p2_8HATpost, p_7HATpost, tmp_9HATpost, x_5HATpost, y_6HATpost) :|: lt_11HAT1 = cnt_20HAT0 && lt_12HAT1 = cnt_25HAT0 && -1 * lt_11HAT1 + lt_12HAT1 <= 0 && lt_11HATpost = lt_11HATpost && lt_12HATpost = lt_12HATpost && Result_4HATpost = Result_4HATpost && cnt_20HAT0 = cnt_20HATpost && cnt_25HAT0 = cnt_25HATpost && lt_10HAT0 = lt_10HATpost && p2_8HAT0 = p2_8HATpost && p_7HAT0 = p_7HATpost && tmp_9HAT0 = tmp_9HATpost && x_5HAT0 = x_5HATpost && y_6HAT0 = y_6HATpost l0(x, x1, x2, x3, x4, x5, x6, x7, x8, x9, x10) -> l2(x11, x12, x13, x14, x15, x16, x17, x18, x19, x20, x21) :|: x22 = x1 && x23 = x2 && 0 <= -1 - x22 + x23 && x15 = x15 && x16 = x16 && x19 = x19 && x19 <= 0 && 0 <= x19 && x = x11 && x1 = x12 && x2 = x13 && x3 = x14 && x6 = x17 && x7 = x18 && x9 = x20 && x10 = x21 l2(x24, x25, x26, x27, x28, x29, x30, x31, x32, x33, x34) -> l0(x35, x36, x37, x38, x39, x40, x41, x42, x43, x44, x45) :|: x34 = x45 && x33 = x44 && x32 = x43 && x31 = x42 && x30 = x41 && x29 = x40 && x28 = x39 && x27 = x38 && x26 = x37 && x25 = x36 && x24 = x35 l0(x46, x47, x48, x49, x50, x51, x52, x53, x54, x55, x56) -> l4(x57, x58, x59, x60, x61, x62, x63, x64, x65, x66, x67) :|: x68 = x47 && x69 = x48 && 0 <= -1 - x68 + x69 && x61 = x61 && x62 = x62 && x65 = x65 && x46 = x57 && x47 = x58 && x48 = x59 && x49 = x60 && x52 = x63 && x53 = x64 && x55 = x66 && x56 = x67 l4(x70, x71, x72, x73, x74, x75, x76, x77, x78, x79, x80) -> l5(x81, x82, x83, x84, x85, x86, x87, x88, x89, x90, x91) :|: x80 = x91 && x79 = x90 && x78 = x89 && x77 = x88 && x76 = x87 && x75 = x86 && x74 = x85 && x73 = x84 && x72 = x83 && x71 = x82 && x70 = x81 && 1 + x78 <= 0 l4(x92, x93, x94, x95, x96, x97, x98, x99, x100, x101, x102) -> l5(x103, x104, x105, x106, x107, x108, x109, x110, x111, x112, x113) :|: x102 = x113 && x101 = x112 && x100 = x111 && x99 = x110 && x98 = x109 && x97 = x108 && x96 = x107 && x95 = x106 && x94 = x105 && x93 = x104 && x92 = x103 && 1 <= x100 l5(x114, x115, x116, x117, x118, x119, x120, x121, x122, x123, x124) -> l3(x125, x126, x127, x128, x129, x130, x131, x132, x133, x134, x135) :|: x136 = x115 && x128 = x128 && x114 = x125 && x115 = x126 && x116 = x127 && x118 = x129 && x119 = x130 && x120 = x131 && x121 = x132 && x122 = x133 && x123 = x134 && x124 = x135 l3(x137, x138, x139, x140, x141, x142, x143, x144, x145, x146, x147) -> l0(x148, x149, x150, x151, x152, x153, x154, x155, x156, x157, x158) :|: x147 = x158 && x146 = x157 && x145 = x156 && x144 = x155 && x143 = x154 && x142 = x153 && x141 = x152 && x140 = x151 && x139 = x150 && x138 = x149 && x137 = x148 l6(x159, x160, x161, x162, x163, x164, x165, x166, x167, x168, x169) -> l0(x170, x171, x172, x173, x174, x175, x176, x177, x178, x179, x180) :|: x167 = x178 && x164 = x175 && x163 = x174 && x162 = x173 && x161 = x172 && x160 = x171 && x159 = x170 && x176 = x180 && x177 = x179 && x179 = x179 && x180 = x180 l7(x181, x182, x183, x184, x185, x186, x187, x188, x189, x190, x191) -> l6(x192, x193, x194, x195, x196, x197, x198, x199, x200, x201, x202) :|: x191 = x202 && x190 = x201 && x189 = x200 && x188 = x199 && x187 = x198 && x186 = x197 && x185 = x196 && x184 = x195 && x183 = x194 && x182 = x193 && x181 = x192 Start term: l7(Result_4HAT0, cnt_20HAT0, cnt_25HAT0, lt_10HAT0, lt_11HAT0, lt_12HAT0, p2_8HAT0, p_7HAT0, tmp_9HAT0, x_5HAT0, y_6HAT0) ---------------------------------------- (1) IRSFormatTransformerProof (EQUIVALENT) Reformatted IRS to match normalized format (transformed away non-linear left-hand sides, !=, / and %). ---------------------------------------- (2) Obligation: Rules: l0(Result_4HAT0, cnt_20HAT0, cnt_25HAT0, lt_10HAT0, lt_11HAT0, lt_12HAT0, p2_8HAT0, p_7HAT0, tmp_9HAT0, x_5HAT0, y_6HAT0) -> l1(Result_4HATpost, cnt_20HATpost, cnt_25HATpost, lt_10HATpost, lt_11HATpost, lt_12HATpost, p2_8HATpost, p_7HATpost, tmp_9HATpost, x_5HATpost, y_6HATpost) :|: lt_11HAT1 = cnt_20HAT0 && lt_12HAT1 = cnt_25HAT0 && -1 * lt_11HAT1 + lt_12HAT1 <= 0 && lt_11HATpost = lt_11HATpost && lt_12HATpost = lt_12HATpost && Result_4HATpost = Result_4HATpost && cnt_20HAT0 = cnt_20HATpost && cnt_25HAT0 = cnt_25HATpost && lt_10HAT0 = lt_10HATpost && p2_8HAT0 = p2_8HATpost && p_7HAT0 = p_7HATpost && tmp_9HAT0 = tmp_9HATpost && x_5HAT0 = x_5HATpost && y_6HAT0 = y_6HATpost l0(x, x1, x2, x3, x4, x5, x6, x7, x8, x9, x10) -> l2(x11, x12, x13, x14, x15, x16, x17, x18, x19, x20, x21) :|: x22 = x1 && x23 = x2 && 0 <= -1 - x22 + x23 && x15 = x15 && x16 = x16 && x19 = x19 && x19 <= 0 && 0 <= x19 && x = x11 && x1 = x12 && x2 = x13 && x3 = x14 && x6 = x17 && x7 = x18 && x9 = x20 && x10 = x21 l2(x24, x25, x26, x27, x28, x29, x30, x31, x32, x33, x34) -> l0(x35, x36, x37, x38, x39, x40, x41, x42, x43, x44, x45) :|: x34 = x45 && x33 = x44 && x32 = x43 && x31 = x42 && x30 = x41 && x29 = x40 && x28 = x39 && x27 = x38 && x26 = x37 && x25 = x36 && x24 = x35 l0(x46, x47, x48, x49, x50, x51, x52, x53, x54, x55, x56) -> l4(x57, x58, x59, x60, x61, x62, x63, x64, x65, x66, x67) :|: x68 = x47 && x69 = x48 && 0 <= -1 - x68 + x69 && x61 = x61 && x62 = x62 && x65 = x65 && x46 = x57 && x47 = x58 && x48 = x59 && x49 = x60 && x52 = x63 && x53 = x64 && x55 = x66 && x56 = x67 l4(x70, x71, x72, x73, x74, x75, x76, x77, x78, x79, x80) -> l5(x81, x82, x83, x84, x85, x86, x87, x88, x89, x90, x91) :|: x80 = x91 && x79 = x90 && x78 = x89 && x77 = x88 && x76 = x87 && x75 = x86 && x74 = x85 && x73 = x84 && x72 = x83 && x71 = x82 && x70 = x81 && 1 + x78 <= 0 l4(x92, x93, x94, x95, x96, x97, x98, x99, x100, x101, x102) -> l5(x103, x104, x105, x106, x107, x108, x109, x110, x111, x112, x113) :|: x102 = x113 && x101 = x112 && x100 = x111 && x99 = x110 && x98 = x109 && x97 = x108 && x96 = x107 && x95 = x106 && x94 = x105 && x93 = x104 && x92 = x103 && 1 <= x100 l5(x114, x115, x116, x117, x118, x119, x120, x121, x122, x123, x124) -> l3(x125, x126, x127, x128, x129, x130, x131, x132, x133, x134, x135) :|: x136 = x115 && x128 = x128 && x114 = x125 && x115 = x126 && x116 = x127 && x118 = x129 && x119 = x130 && x120 = x131 && x121 = x132 && x122 = x133 && x123 = x134 && x124 = x135 l3(x137, x138, x139, x140, x141, x142, x143, x144, x145, x146, x147) -> l0(x148, x149, x150, x151, x152, x153, x154, x155, x156, x157, x158) :|: x147 = x158 && x146 = x157 && x145 = x156 && x144 = x155 && x143 = x154 && x142 = x153 && x141 = x152 && x140 = x151 && x139 = x150 && x138 = x149 && x137 = x148 l6(x159, x160, x161, x162, x163, x164, x165, x166, x167, x168, x169) -> l0(x170, x171, x172, x173, x174, x175, x176, x177, x178, x179, x180) :|: x167 = x178 && x164 = x175 && x163 = x174 && x162 = x173 && x161 = x172 && x160 = x171 && x159 = x170 && x176 = x180 && x177 = x179 && x179 = x179 && x180 = x180 l7(x181, x182, x183, x184, x185, x186, x187, x188, x189, x190, x191) -> l6(x192, x193, x194, x195, x196, x197, x198, x199, x200, x201, x202) :|: x191 = x202 && x190 = x201 && x189 = x200 && x188 = x199 && x187 = x198 && x186 = x197 && x185 = x196 && x184 = x195 && x183 = x194 && x182 = x193 && x181 = x192 Start term: l7(Result_4HAT0, cnt_20HAT0, cnt_25HAT0, lt_10HAT0, lt_11HAT0, lt_12HAT0, p2_8HAT0, p_7HAT0, tmp_9HAT0, x_5HAT0, y_6HAT0) ---------------------------------------- (3) IRSwTTerminationDigraphProof (EQUIVALENT) Constructed termination digraph! Nodes: (1) l0(Result_4HAT0, cnt_20HAT0, cnt_25HAT0, lt_10HAT0, lt_11HAT0, lt_12HAT0, p2_8HAT0, p_7HAT0, tmp_9HAT0, x_5HAT0, y_6HAT0) -> l1(Result_4HATpost, cnt_20HATpost, cnt_25HATpost, lt_10HATpost, lt_11HATpost, lt_12HATpost, p2_8HATpost, p_7HATpost, tmp_9HATpost, x_5HATpost, y_6HATpost) :|: lt_11HAT1 = cnt_20HAT0 && lt_12HAT1 = cnt_25HAT0 && -1 * lt_11HAT1 + lt_12HAT1 <= 0 && lt_11HATpost = lt_11HATpost && lt_12HATpost = lt_12HATpost && Result_4HATpost = Result_4HATpost && cnt_20HAT0 = cnt_20HATpost && cnt_25HAT0 = cnt_25HATpost && lt_10HAT0 = lt_10HATpost && p2_8HAT0 = p2_8HATpost && p_7HAT0 = p_7HATpost && tmp_9HAT0 = tmp_9HATpost && x_5HAT0 = x_5HATpost && y_6HAT0 = y_6HATpost (2) l0(x, x1, x2, x3, x4, x5, x6, x7, x8, x9, x10) -> l2(x11, x12, x13, x14, x15, x16, x17, x18, x19, x20, x21) :|: x22 = x1 && x23 = x2 && 0 <= -1 - x22 + x23 && x15 = x15 && x16 = x16 && x19 = x19 && x19 <= 0 && 0 <= x19 && x = x11 && x1 = x12 && x2 = x13 && x3 = x14 && x6 = x17 && x7 = x18 && x9 = x20 && x10 = x21 (3) l2(x24, x25, x26, x27, x28, x29, x30, x31, x32, x33, x34) -> l0(x35, x36, x37, x38, x39, x40, x41, x42, x43, x44, x45) :|: x34 = x45 && x33 = x44 && x32 = x43 && x31 = x42 && x30 = x41 && x29 = x40 && x28 = x39 && x27 = x38 && x26 = x37 && x25 = x36 && x24 = x35 (4) l0(x46, x47, x48, x49, x50, x51, x52, x53, x54, x55, x56) -> l4(x57, x58, x59, x60, x61, x62, x63, x64, x65, x66, x67) :|: x68 = x47 && x69 = x48 && 0 <= -1 - x68 + x69 && x61 = x61 && x62 = x62 && x65 = x65 && x46 = x57 && x47 = x58 && x48 = x59 && x49 = x60 && x52 = x63 && x53 = x64 && x55 = x66 && x56 = x67 (5) l4(x70, x71, x72, x73, x74, x75, x76, x77, x78, x79, x80) -> l5(x81, x82, x83, x84, x85, x86, x87, x88, x89, x90, x91) :|: x80 = x91 && x79 = x90 && x78 = x89 && x77 = x88 && x76 = x87 && x75 = x86 && x74 = x85 && x73 = x84 && x72 = x83 && x71 = x82 && x70 = x81 && 1 + x78 <= 0 (6) l4(x92, x93, x94, x95, x96, x97, x98, x99, x100, x101, x102) -> l5(x103, x104, x105, x106, x107, x108, x109, x110, x111, x112, x113) :|: x102 = x113 && x101 = x112 && x100 = x111 && x99 = x110 && x98 = x109 && x97 = x108 && x96 = x107 && x95 = x106 && x94 = x105 && x93 = x104 && x92 = x103 && 1 <= x100 (7) l5(x114, x115, x116, x117, x118, x119, x120, x121, x122, x123, x124) -> l3(x125, x126, x127, x128, x129, x130, x131, x132, x133, x134, x135) :|: x136 = x115 && x128 = x128 && x114 = x125 && x115 = x126 && x116 = x127 && x118 = x129 && x119 = x130 && x120 = x131 && x121 = x132 && x122 = x133 && x123 = x134 && x124 = x135 (8) l3(x137, x138, x139, x140, x141, x142, x143, x144, x145, x146, x147) -> l0(x148, x149, x150, x151, x152, x153, x154, x155, x156, x157, x158) :|: x147 = x158 && x146 = x157 && x145 = x156 && x144 = x155 && x143 = x154 && x142 = x153 && x141 = x152 && x140 = x151 && x139 = x150 && x138 = x149 && x137 = x148 (9) l6(x159, x160, x161, x162, x163, x164, x165, x166, x167, x168, x169) -> l0(x170, x171, x172, x173, x174, x175, x176, x177, x178, x179, x180) :|: x167 = x178 && x164 = x175 && x163 = x174 && x162 = x173 && x161 = x172 && x160 = x171 && x159 = x170 && x176 = x180 && x177 = x179 && x179 = x179 && x180 = x180 (10) l7(x181, x182, x183, x184, x185, x186, x187, x188, x189, x190, x191) -> l6(x192, x193, x194, x195, x196, x197, x198, x199, x200, x201, x202) :|: x191 = x202 && x190 = x201 && x189 = x200 && x188 = x199 && x187 = x198 && x186 = x197 && x185 = x196 && x184 = x195 && x183 = x194 && x182 = x193 && x181 = x192 Arcs: (2) -> (3) (3) -> (1), (2), (4) (4) -> (5), (6) (5) -> (7) (6) -> (7) (7) -> (8) (8) -> (1), (2), (4) (9) -> (1), (2), (4) (10) -> (9) This digraph is fully evaluated! ---------------------------------------- (4) Obligation: Termination digraph: Nodes: (1) l0(x, x1, x2, x3, x4, x5, x6, x7, x8, x9, x10) -> l2(x11, x12, x13, x14, x15, x16, x17, x18, x19, x20, x21) :|: x22 = x1 && x23 = x2 && 0 <= -1 - x22 + x23 && x15 = x15 && x16 = x16 && x19 = x19 && x19 <= 0 && 0 <= x19 && x = x11 && x1 = x12 && x2 = x13 && x3 = x14 && x6 = x17 && x7 = x18 && x9 = x20 && x10 = x21 (2) l3(x137, x138, x139, x140, x141, x142, x143, x144, x145, x146, x147) -> l0(x148, x149, x150, x151, x152, x153, x154, x155, x156, x157, x158) :|: x147 = x158 && x146 = x157 && x145 = x156 && x144 = x155 && x143 = x154 && x142 = x153 && x141 = x152 && x140 = x151 && x139 = x150 && x138 = x149 && x137 = x148 (3) l5(x114, x115, x116, x117, x118, x119, x120, x121, x122, x123, x124) -> l3(x125, x126, x127, x128, x129, x130, x131, x132, x133, x134, x135) :|: x136 = x115 && x128 = x128 && x114 = x125 && x115 = x126 && x116 = x127 && x118 = x129 && x119 = x130 && x120 = x131 && x121 = x132 && x122 = x133 && x123 = x134 && x124 = x135 (4) l4(x92, x93, x94, x95, x96, x97, x98, x99, x100, x101, x102) -> l5(x103, x104, x105, x106, x107, x108, x109, x110, x111, x112, x113) :|: x102 = x113 && x101 = x112 && x100 = x111 && x99 = x110 && x98 = x109 && x97 = x108 && x96 = x107 && x95 = x106 && x94 = x105 && x93 = x104 && x92 = x103 && 1 <= x100 (5) l4(x70, x71, x72, x73, x74, x75, x76, x77, x78, x79, x80) -> l5(x81, x82, x83, x84, x85, x86, x87, x88, x89, x90, x91) :|: x80 = x91 && x79 = x90 && x78 = x89 && x77 = x88 && x76 = x87 && x75 = x86 && x74 = x85 && x73 = x84 && x72 = x83 && x71 = x82 && x70 = x81 && 1 + x78 <= 0 (6) l0(x46, x47, x48, x49, x50, x51, x52, x53, x54, x55, x56) -> l4(x57, x58, x59, x60, x61, x62, x63, x64, x65, x66, x67) :|: x68 = x47 && x69 = x48 && 0 <= -1 - x68 + x69 && x61 = x61 && x62 = x62 && x65 = x65 && x46 = x57 && x47 = x58 && x48 = x59 && x49 = x60 && x52 = x63 && x53 = x64 && x55 = x66 && x56 = x67 (7) l2(x24, x25, x26, x27, x28, x29, x30, x31, x32, x33, x34) -> l0(x35, x36, x37, x38, x39, x40, x41, x42, x43, x44, x45) :|: x34 = x45 && x33 = x44 && x32 = x43 && x31 = x42 && x30 = x41 && x29 = x40 && x28 = x39 && x27 = x38 && x26 = x37 && x25 = x36 && x24 = x35 Arcs: (1) -> (7) (2) -> (1), (6) (3) -> (2) (4) -> (3) (5) -> (3) (6) -> (4), (5) (7) -> (1), (6) This digraph is fully evaluated! ---------------------------------------- (5) IntTRSCompressionProof (EQUIVALENT) Compressed rules. ---------------------------------------- (6) Obligation: Rules: l0(x125:0, x126:0, x127:0, x49:0, x50:0, x51:0, x131:0, x132:0, x54:0, x134:0, x135:0) -> l0(x125:0, x126:0, x127:0, x128:0, x129:0, x130:0, x131:0, x132:0, x133:0, x134:0, x135:0) :|: x133:0 < 0 && 0 <= -1 - x126:0 + x127:0 l0(x11:0, x12:0, x13:0, x14:0, x4:0, x5:0, x17:0, x18:0, x8:0, x20:0, x10:0) -> l0(x11:0, x12:0, x13:0, x14:0, x15:0, x16:0, x17:0, x18:0, x19:0, x20:0, x10:0) :|: x19:0 < 1 && 0 <= -1 - x12:0 + x13:0 && x19:0 > -1 l0(x, x1, x2, x3, x4, x5, x6, x7, x8, x9, x10) -> l0(x, x1, x2, x11, x12, x13, x6, x7, x14, x9, x10) :|: x14 > 0 && 0 <= -1 - x1 + x2 ---------------------------------------- (7) 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, x8, x9, x10, x11) -> l0(x2, x3) ---------------------------------------- (8) Obligation: Rules: l0(x126:0, x127:0) -> l0(x126:0, x127:0) :|: x133:0 < 0 && 0 <= -1 - x126:0 + x127:0 l0(x12:0, x13:0) -> l0(x12:0, x13:0) :|: x19:0 < 1 && 0 <= -1 - x12:0 + x13:0 && x19:0 > -1 l0(x1, x2) -> l0(x1, x2) :|: x14 > 0 && 0 <= -1 - x1 + x2 ---------------------------------------- (9) FilterProof (EQUIVALENT) Used the following sort dictionary for filtering: l0(INTEGER, INTEGER) Replaced non-predefined constructor symbols by 0. ---------------------------------------- (10) Obligation: Rules: l0(x126:0, x127:0) -> l0(x126:0, x127:0) :|: x133:0 < 0 && 0 <= -1 - x126:0 + x127:0 l0(x12:0, x13:0) -> l0(x12:0, x13:0) :|: x19:0 < 1 && 0 <= -1 - x12:0 + x13:0 && x19:0 > -1 l0(x1, x2) -> l0(x1, x2) :|: x14 > 0 && 0 <= -1 - x1 + x2 ---------------------------------------- (11) IntTRSCompressionProof (EQUIVALENT) Compressed rules. ---------------------------------------- (12) Obligation: Rules: l0(x12:0:0, x13:0:0) -> l0(x12:0:0, x13:0:0) :|: x19:0:0 < 1 && 0 <= -1 - x12:0:0 + x13:0:0 && x19:0:0 > -1 l0(x1:0, x2:0) -> l0(x1:0, x2:0) :|: x14:0 > 0 && 0 <= -1 - x1:0 + x2:0 l0(x126:0:0, x127:0:0) -> l0(x126:0:0, x127:0:0) :|: x133:0:0 < 0 && 0 <= -1 - x126:0:0 + x127:0:0 ---------------------------------------- (13) IntTRSPeriodicNontermProof (COMPLETE) Normalized system to the following form: f(pc, x12:0:0, x13:0:0) -> f(1, x12:0:0, x13:0:0) :|: pc = 1 && (x19:0:0 < 1 && 0 <= -1 - x12:0:0 + x13:0:0 && x19:0:0 > -1) f(pc, x1:0, x2:0) -> f(1, x1:0, x2:0) :|: pc = 1 && (x14:0 > 0 && 0 <= -1 - x1:0 + x2:0) f(pc, x126:0:0, x127:0:0) -> f(1, x126:0:0, x127:0:0) :|: pc = 1 && (x133:0:0 < 0 && 0 <= -1 - x126:0:0 + x127:0:0) Witness term starting non-terminating reduction: f(1, 4, 7) ---------------------------------------- (14) NO