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, 2413 ms] (4) IRSwT (5) IntTRSCompressionProof [EQUIVALENT, 16 ms] (6) IRSwT (7) IntTRSUnneededArgumentFilterProof [EQUIVALENT, 0 ms] (8) IRSwT (9) TempFilterProof [SOUND, 207 ms] (10) IntTRS (11) PolynomialOrderProcessor [EQUIVALENT, 34 ms] (12) AND (13) IntTRS (14) RankingReductionPairProof [EQUIVALENT, 19 ms] (15) IntTRS (16) PolynomialOrderProcessor [EQUIVALENT, 9 ms] (17) AND (18) IntTRS (19) RankingReductionPairProof [EQUIVALENT, 9 ms] (20) IntTRS (21) RankingReductionPairProof [EQUIVALENT, 0 ms] (22) YES (23) IntTRS (24) RankingReductionPairProof [EQUIVALENT, 8 ms] (25) YES (26) IntTRS (27) PolynomialOrderProcessor [EQUIVALENT, 10 ms] (28) YES ---------------------------------------- (0) Obligation: Rules: l0(NHAT0, choiceHAT0, iHAT0, posHAT0, seqHAT0, walkerHAT0, zHAT0) -> l1(NHATpost, choiceHATpost, iHATpost, posHATpost, seqHATpost, walkerHATpost, zHATpost) :|: zHAT0 = zHATpost && walkerHAT0 = walkerHATpost && seqHAT0 = seqHATpost && posHAT0 = posHATpost && iHAT0 = iHATpost && choiceHAT0 = choiceHATpost && NHAT0 = NHATpost 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 && x4 <= 1 + x l4(x14, x15, x16, x17, x18, x19, x20) -> l2(x21, x22, x23, x24, x25, x26, x27) :|: x20 = x27 && x18 = x25 && x17 = x24 && x16 = x23 && x15 = x22 && x14 = x21 && x26 = 1 + x19 && 1 <= x15 l4(x28, x29, x30, x31, x32, x33, x34) -> l2(x35, x36, x37, x38, x39, x40, x41) :|: x34 = x41 && x32 = x39 && x31 = x38 && x30 = x37 && x29 = x36 && x28 = x35 && x40 = -1 + x33 && x29 <= 0 l5(x42, x43, x44, x45, x46, x47, x48) -> l3(x49, x50, x51, x52, x53, x54, x55) :|: x43 = x50 && x54 = 1 && 2 <= x49 && x49 <= 2 && x49 = x49 && x52 = 0 && 0 <= x55 && x55 = x55 && x51 = x53 && x53 = 1 l6(x56, x57, x58, x59, x60, x61, x62) -> l4(x63, x64, x65, x66, x67, x68, x69) :|: x61 = x68 && x59 = x66 && x57 = x64 && x56 = x63 && 0 <= x69 && x69 = x69 && x65 = x67 && x67 = 1 + x60 && x58 <= 0 l6(x70, x71, x72, x73, x74, x75, x76) -> l4(x77, x78, x79, x80, x81, x82, x83) :|: x76 = x83 && x75 = x82 && x74 = x81 && x73 = x80 && x71 = x78 && x70 = x77 && x79 = -1 + x72 && x71 <= 0 && 1 <= x72 l7(x84, x85, x86, x87, x88, x89, x90) -> l4(x91, x92, x93, x94, x95, x96, x97) :|: x89 = x96 && x88 = x95 && x87 = x94 && x86 = x93 && x85 = x92 && x84 = x91 && x97 = -1 + x90 && 1 <= x90 l7(x98, x99, x100, x101, x102, x103, x104) -> l6(x105, x106, x107, x108, x109, x110, x111) :|: x104 = x111 && x103 = x110 && x102 = x109 && x101 = x108 && x100 = x107 && x99 = x106 && x98 = x105 && x104 <= 0 l8(x112, x113, x114, x115, x116, x117, x118) -> l0(x119, x120, x121, x122, x123, x124, x125) :|: x118 = x125 && x117 = x124 && x116 = x123 && x115 = x122 && x114 = x121 && x113 = x120 && x112 = x119 && 1 + x117 <= 1 l8(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 && 0 <= x134 && x134 = x134 && 1 <= x131 l9(x140, x141, x142, x143, x144, x145, x146) -> l0(x147, x148, x149, x150, x151, x152, x153) :|: x146 = x153 && x145 = x152 && x144 = x151 && x143 = x150 && x142 = x149 && x141 = x148 && x140 = x147 && 1 + x140 <= x145 l9(x154, x155, x156, x157, x158, x159, x160) -> l8(x161, x162, x163, x164, x165, x166, x167) :|: x160 = x167 && x159 = x166 && x158 = x165 && x157 = x164 && x156 = x163 && x155 = x162 && x154 = x161 && x159 <= x154 l3(x168, x169, x170, x171, x172, x173, x174) -> l9(x175, x176, x177, x178, x179, x180, x181) :|: x174 = x181 && x173 = x180 && x172 = x179 && x171 = x178 && x170 = x177 && x169 = x176 && x168 = x175 l10(x182, x183, x184, x185, x186, x187, x188) -> l5(x189, x190, x191, x192, x193, x194, x195) :|: x188 = x195 && x187 = x194 && x186 = x193 && x185 = x192 && x184 = x191 && x183 = x190 && x182 = x189 Start term: l10(NHAT0, choiceHAT0, iHAT0, posHAT0, seqHAT0, walkerHAT0, zHAT0) ---------------------------------------- (1) IRSFormatTransformerProof (EQUIVALENT) Reformatted IRS to match normalized format (transformed away non-linear left-hand sides, !=, / and %). ---------------------------------------- (2) Obligation: Rules: l0(NHAT0, choiceHAT0, iHAT0, posHAT0, seqHAT0, walkerHAT0, zHAT0) -> l1(NHATpost, choiceHATpost, iHATpost, posHATpost, seqHATpost, walkerHATpost, zHATpost) :|: zHAT0 = zHATpost && walkerHAT0 = walkerHATpost && seqHAT0 = seqHATpost && posHAT0 = posHATpost && iHAT0 = iHATpost && choiceHAT0 = choiceHATpost && NHAT0 = NHATpost 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 && x4 <= 1 + x l4(x14, x15, x16, x17, x18, x19, x20) -> l2(x21, x22, x23, x24, x25, x26, x27) :|: x20 = x27 && x18 = x25 && x17 = x24 && x16 = x23 && x15 = x22 && x14 = x21 && x26 = 1 + x19 && 1 <= x15 l4(x28, x29, x30, x31, x32, x33, x34) -> l2(x35, x36, x37, x38, x39, x40, x41) :|: x34 = x41 && x32 = x39 && x31 = x38 && x30 = x37 && x29 = x36 && x28 = x35 && x40 = -1 + x33 && x29 <= 0 l5(x42, x43, x44, x45, x46, x47, x48) -> l3(x49, x50, x51, x52, x53, x54, x55) :|: x43 = x50 && x54 = 1 && 2 <= x49 && x49 <= 2 && x49 = x49 && x52 = 0 && 0 <= x55 && x55 = x55 && x51 = x53 && x53 = 1 l6(x56, x57, x58, x59, x60, x61, x62) -> l4(x63, x64, x65, x66, x67, x68, x69) :|: x61 = x68 && x59 = x66 && x57 = x64 && x56 = x63 && 0 <= x69 && x69 = x69 && x65 = x67 && x67 = 1 + x60 && x58 <= 0 l6(x70, x71, x72, x73, x74, x75, x76) -> l4(x77, x78, x79, x80, x81, x82, x83) :|: x76 = x83 && x75 = x82 && x74 = x81 && x73 = x80 && x71 = x78 && x70 = x77 && x79 = -1 + x72 && x71 <= 0 && 1 <= x72 l7(x84, x85, x86, x87, x88, x89, x90) -> l4(x91, x92, x93, x94, x95, x96, x97) :|: x89 = x96 && x88 = x95 && x87 = x94 && x86 = x93 && x85 = x92 && x84 = x91 && x97 = -1 + x90 && 1 <= x90 l7(x98, x99, x100, x101, x102, x103, x104) -> l6(x105, x106, x107, x108, x109, x110, x111) :|: x104 = x111 && x103 = x110 && x102 = x109 && x101 = x108 && x100 = x107 && x99 = x106 && x98 = x105 && x104 <= 0 l8(x112, x113, x114, x115, x116, x117, x118) -> l0(x119, x120, x121, x122, x123, x124, x125) :|: x118 = x125 && x117 = x124 && x116 = x123 && x115 = x122 && x114 = x121 && x113 = x120 && x112 = x119 && 1 + x117 <= 1 l8(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 && 0 <= x134 && x134 = x134 && 1 <= x131 l9(x140, x141, x142, x143, x144, x145, x146) -> l0(x147, x148, x149, x150, x151, x152, x153) :|: x146 = x153 && x145 = x152 && x144 = x151 && x143 = x150 && x142 = x149 && x141 = x148 && x140 = x147 && 1 + x140 <= x145 l9(x154, x155, x156, x157, x158, x159, x160) -> l8(x161, x162, x163, x164, x165, x166, x167) :|: x160 = x167 && x159 = x166 && x158 = x165 && x157 = x164 && x156 = x163 && x155 = x162 && x154 = x161 && x159 <= x154 l3(x168, x169, x170, x171, x172, x173, x174) -> l9(x175, x176, x177, x178, x179, x180, x181) :|: x174 = x181 && x173 = x180 && x172 = x179 && x171 = x178 && x170 = x177 && x169 = x176 && x168 = x175 l10(x182, x183, x184, x185, x186, x187, x188) -> l5(x189, x190, x191, x192, x193, x194, x195) :|: x188 = x195 && x187 = x194 && x186 = x193 && x185 = x192 && x184 = x191 && x183 = x190 && x182 = x189 Start term: l10(NHAT0, choiceHAT0, iHAT0, posHAT0, seqHAT0, walkerHAT0, zHAT0) ---------------------------------------- (3) IRSwTTerminationDigraphProof (EQUIVALENT) Constructed termination digraph! Nodes: (1) l0(NHAT0, choiceHAT0, iHAT0, posHAT0, seqHAT0, walkerHAT0, zHAT0) -> l1(NHATpost, choiceHATpost, iHATpost, posHATpost, seqHATpost, walkerHATpost, zHATpost) :|: zHAT0 = zHATpost && walkerHAT0 = walkerHATpost && seqHAT0 = seqHATpost && posHAT0 = posHATpost && iHAT0 = iHATpost && choiceHAT0 = choiceHATpost && NHAT0 = NHATpost (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 && x4 <= 1 + x (3) l4(x14, x15, x16, x17, x18, x19, x20) -> l2(x21, x22, x23, x24, x25, x26, x27) :|: x20 = x27 && x18 = x25 && x17 = x24 && x16 = x23 && x15 = x22 && x14 = x21 && x26 = 1 + x19 && 1 <= x15 (4) l4(x28, x29, x30, x31, x32, x33, x34) -> l2(x35, x36, x37, x38, x39, x40, x41) :|: x34 = x41 && x32 = x39 && x31 = x38 && x30 = x37 && x29 = x36 && x28 = x35 && x40 = -1 + x33 && x29 <= 0 (5) l5(x42, x43, x44, x45, x46, x47, x48) -> l3(x49, x50, x51, x52, x53, x54, x55) :|: x43 = x50 && x54 = 1 && 2 <= x49 && x49 <= 2 && x49 = x49 && x52 = 0 && 0 <= x55 && x55 = x55 && x51 = x53 && x53 = 1 (6) l6(x56, x57, x58, x59, x60, x61, x62) -> l4(x63, x64, x65, x66, x67, x68, x69) :|: x61 = x68 && x59 = x66 && x57 = x64 && x56 = x63 && 0 <= x69 && x69 = x69 && x65 = x67 && x67 = 1 + x60 && x58 <= 0 (7) l6(x70, x71, x72, x73, x74, x75, x76) -> l4(x77, x78, x79, x80, x81, x82, x83) :|: x76 = x83 && x75 = x82 && x74 = x81 && x73 = x80 && x71 = x78 && x70 = x77 && x79 = -1 + x72 && x71 <= 0 && 1 <= x72 (8) l7(x84, x85, x86, x87, x88, x89, x90) -> l4(x91, x92, x93, x94, x95, x96, x97) :|: x89 = x96 && x88 = x95 && x87 = x94 && x86 = x93 && x85 = x92 && x84 = x91 && x97 = -1 + x90 && 1 <= x90 (9) l7(x98, x99, x100, x101, x102, x103, x104) -> l6(x105, x106, x107, x108, x109, x110, x111) :|: x104 = x111 && x103 = x110 && x102 = x109 && x101 = x108 && x100 = x107 && x99 = x106 && x98 = x105 && x104 <= 0 (10) l8(x112, x113, x114, x115, x116, x117, x118) -> l0(x119, x120, x121, x122, x123, x124, x125) :|: x118 = x125 && x117 = x124 && x116 = x123 && x115 = x122 && x114 = x121 && x113 = x120 && x112 = x119 && 1 + x117 <= 1 (11) l8(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 && 0 <= x134 && x134 = x134 && 1 <= x131 (12) l9(x140, x141, x142, x143, x144, x145, x146) -> l0(x147, x148, x149, x150, x151, x152, x153) :|: x146 = x153 && x145 = x152 && x144 = x151 && x143 = x150 && x142 = x149 && x141 = x148 && x140 = x147 && 1 + x140 <= x145 (13) l9(x154, x155, x156, x157, x158, x159, x160) -> l8(x161, x162, x163, x164, x165, x166, x167) :|: x160 = x167 && x159 = x166 && x158 = x165 && x157 = x164 && x156 = x163 && x155 = x162 && x154 = x161 && x159 <= x154 (14) l3(x168, x169, x170, x171, x172, x173, x174) -> l9(x175, x176, x177, x178, x179, x180, x181) :|: x174 = x181 && x173 = x180 && x172 = x179 && x171 = x178 && x170 = x177 && x169 = x176 && x168 = x175 (15) l10(x182, x183, x184, x185, x186, x187, x188) -> l5(x189, x190, x191, x192, x193, x194, x195) :|: x188 = x195 && x187 = x194 && x186 = x193 && x185 = x192 && x184 = x191 && x183 = x190 && x182 = x189 Arcs: (2) -> (14) (3) -> (2) (4) -> (2) (5) -> (14) (6) -> (3), (4) (7) -> (4) (8) -> (3), (4) (9) -> (6), (7) (10) -> (1) (11) -> (8), (9) (12) -> (1) (13) -> (10), (11) (14) -> (12), (13) (15) -> (5) This digraph is fully evaluated! ---------------------------------------- (4) Obligation: Termination digraph: Nodes: (1) 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 && x4 <= 1 + x (2) l4(x28, x29, x30, x31, x32, x33, x34) -> l2(x35, x36, x37, x38, x39, x40, x41) :|: x34 = x41 && x32 = x39 && x31 = x38 && x30 = x37 && x29 = x36 && x28 = x35 && x40 = -1 + x33 && x29 <= 0 (3) l6(x70, x71, x72, x73, x74, x75, x76) -> l4(x77, x78, x79, x80, x81, x82, x83) :|: x76 = x83 && x75 = x82 && x74 = x81 && x73 = x80 && x71 = x78 && x70 = x77 && x79 = -1 + x72 && x71 <= 0 && 1 <= x72 (4) l4(x14, x15, x16, x17, x18, x19, x20) -> l2(x21, x22, x23, x24, x25, x26, x27) :|: x20 = x27 && x18 = x25 && x17 = x24 && x16 = x23 && x15 = x22 && x14 = x21 && x26 = 1 + x19 && 1 <= x15 (5) l7(x84, x85, x86, x87, x88, x89, x90) -> l4(x91, x92, x93, x94, x95, x96, x97) :|: x89 = x96 && x88 = x95 && x87 = x94 && x86 = x93 && x85 = x92 && x84 = x91 && x97 = -1 + x90 && 1 <= x90 (6) l6(x56, x57, x58, x59, x60, x61, x62) -> l4(x63, x64, x65, x66, x67, x68, x69) :|: x61 = x68 && x59 = x66 && x57 = x64 && x56 = x63 && 0 <= x69 && x69 = x69 && x65 = x67 && x67 = 1 + x60 && x58 <= 0 (7) l7(x98, x99, x100, x101, x102, x103, x104) -> l6(x105, x106, x107, x108, x109, x110, x111) :|: x104 = x111 && x103 = x110 && x102 = x109 && x101 = x108 && x100 = x107 && x99 = x106 && x98 = x105 && x104 <= 0 (8) l8(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 && 0 <= x134 && x134 = x134 && 1 <= x131 (9) l9(x154, x155, x156, x157, x158, x159, x160) -> l8(x161, x162, x163, x164, x165, x166, x167) :|: x160 = x167 && x159 = x166 && x158 = x165 && x157 = x164 && x156 = x163 && x155 = x162 && x154 = x161 && x159 <= x154 (10) l3(x168, x169, x170, x171, x172, x173, x174) -> l9(x175, x176, x177, x178, x179, x180, x181) :|: x174 = x181 && x173 = x180 && x172 = x179 && x171 = x178 && x170 = x177 && x169 = x176 && x168 = x175 Arcs: (1) -> (10) (2) -> (1) (3) -> (2) (4) -> (1) (5) -> (2), (4) (6) -> (2), (4) (7) -> (3), (6) (8) -> (5), (7) (9) -> (8) (10) -> (9) This digraph is fully evaluated! ---------------------------------------- (5) IntTRSCompressionProof (EQUIVALENT) Compressed rules. ---------------------------------------- (6) Obligation: Rules: l9(x105:0, x155:0, x107:0, x108:0, x109:0, x110:0, x111:0) -> l4(x105:0, x106:0, 1 + x109:0, x108:0, 1 + x109:0, x110:0, x69:0) :|: x110:0 > 0 && x110:0 <= x105:0 && x111:0 < 1 && x107:0 < 1 && x106:0 > -1 && x69:0 > -1 && x106:0 < 2 l9(x, x1, x2, x3, x4, x5, x6) -> l4(x, x7, x2, x3, x4, x5, -1 + x6) :|: x5 > 0 && x5 <= x && x6 > 0 && x7 < 2 && x7 > -1 l9(x8, x9, x10, x11, x12, x13, x14) -> l4(x8, x15, -1 + x10, x11, x12, x13, x14) :|: x13 > 0 && x13 <= x8 && x14 < 1 && x10 > 0 && x15 > -1 && x15 < 2 && x15 < 1 l4(x175:0, x176:0, x177:0, x10:0, x11:0, x33:0, x13:0) -> l9(x175:0, x176:0, x177:0, x10:0, x11:0, -1 + x33:0, x13:0) :|: x176:0 < 1 && x11:0 <= 1 + x175:0 l4(x16, x17, x18, x19, x20, x21, x22) -> l9(x16, x17, x18, x19, x20, 1 + x21, x22) :|: x17 > 0 && x20 <= 1 + x16 ---------------------------------------- (7) 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, x3, x5, x6, x7) l4(x1, x2, x3, x4, x5, x6, x7) -> l4(x1, x2, x3, x5, x6, x7) ---------------------------------------- (8) Obligation: Rules: l9(x105:0, x107:0, x109:0, x110:0, x111:0) -> l4(x105:0, x106:0, 1 + x109:0, 1 + x109:0, x110:0, x69:0) :|: x110:0 > 0 && x110:0 <= x105:0 && x111:0 < 1 && x107:0 < 1 && x106:0 > -1 && x69:0 > -1 && x106:0 < 2 l9(x, x2, x4, x5, x6) -> l4(x, x7, x2, x4, x5, -1 + x6) :|: x5 > 0 && x5 <= x && x6 > 0 && x7 < 2 && x7 > -1 l9(x8, x10, x12, x13, x14) -> l4(x8, x15, -1 + x10, x12, x13, x14) :|: x13 > 0 && x13 <= x8 && x14 < 1 && x10 > 0 && x15 > -1 && x15 < 2 && x15 < 1 l4(x175:0, x176:0, x177:0, x11:0, x33:0, x13:0) -> l9(x175:0, x177:0, x11:0, -1 + x33:0, x13:0) :|: x176:0 < 1 && x11:0 <= 1 + x175:0 l4(x16, x17, x18, x20, x21, x22) -> l9(x16, x18, x20, 1 + x21, x22) :|: x17 > 0 && x20 <= 1 + x16 ---------------------------------------- (9) TempFilterProof (SOUND) Used the following sort dictionary for filtering: l9(INTEGER, VARIABLE, VARIABLE, INTEGER, VARIABLE) l4(INTEGER, INTEGER, VARIABLE, VARIABLE, VARIABLE, VARIABLE) Replaced non-predefined constructor symbols by 0. ---------------------------------------- (10) Obligation: Rules: l9(x105:0, x107:0, x109:0, x110:0, x111:0) -> l4(x105:0, x106:0, c, c1, x110:0, x69:0) :|: c1 = 1 + x109:0 && c = 1 + x109:0 && (x110:0 > 0 && x110:0 <= x105:0 && x111:0 < 1 && x107:0 < 1 && x106:0 > -1 && x69:0 > -1 && x106:0 < 2) l9(x, x2, x4, x5, x6) -> l4(x, x7, x2, x4, x5, c2) :|: c2 = -1 + x6 && (x5 > 0 && x5 <= x && x6 > 0 && x7 < 2 && x7 > -1) l9(x8, x10, x12, x13, x14) -> l4(x8, x15, c3, x12, x13, x14) :|: c3 = -1 + x10 && (x13 > 0 && x13 <= x8 && x14 < 1 && x10 > 0 && x15 > -1 && x15 < 2 && x15 < 1) l4(x175:0, x176:0, x177:0, x11:0, x33:0, x13:0) -> l9(x175:0, x177:0, x11:0, c4, x13:0) :|: c4 = -1 + x33:0 && (x176:0 < 1 && x11:0 <= 1 + x175:0) l4(x16, x17, x18, x20, x21, x22) -> l9(x16, x18, x20, c5, x22) :|: c5 = 1 + x21 && (x17 > 0 && x20 <= 1 + x16) ---------------------------------------- (11) PolynomialOrderProcessor (EQUIVALENT) Found the following polynomial interpretation: [l9(x, x1, x2, x3, x4)] = 1 + x - x2 [l4(x5, x6, x7, x8, x9, x10)] = 1 + x5 - x8 The following rules are decreasing: l9(x105:0, x107:0, x109:0, x110:0, x111:0) -> l4(x105:0, x106:0, c, c1, x110:0, x69:0) :|: c1 = 1 + x109:0 && c = 1 + x109:0 && (x110:0 > 0 && x110:0 <= x105:0 && x111:0 < 1 && x107:0 < 1 && x106:0 > -1 && x69:0 > -1 && x106:0 < 2) The following rules are bounded: l4(x175:0, x176:0, x177:0, x11:0, x33:0, x13:0) -> l9(x175:0, x177:0, x11:0, c4, x13:0) :|: c4 = -1 + x33:0 && (x176:0 < 1 && x11:0 <= 1 + x175:0) l4(x16, x17, x18, x20, x21, x22) -> l9(x16, x18, x20, c5, x22) :|: c5 = 1 + x21 && (x17 > 0 && x20 <= 1 + x16) ---------------------------------------- (12) Complex Obligation (AND) ---------------------------------------- (13) Obligation: Rules: l9(x, x2, x4, x5, x6) -> l4(x, x7, x2, x4, x5, c2) :|: c2 = -1 + x6 && (x5 > 0 && x5 <= x && x6 > 0 && x7 < 2 && x7 > -1) l9(x8, x10, x12, x13, x14) -> l4(x8, x15, c3, x12, x13, x14) :|: c3 = -1 + x10 && (x13 > 0 && x13 <= x8 && x14 < 1 && x10 > 0 && x15 > -1 && x15 < 2 && x15 < 1) l4(x175:0, x176:0, x177:0, x11:0, x33:0, x13:0) -> l9(x175:0, x177:0, x11:0, c4, x13:0) :|: c4 = -1 + x33:0 && (x176:0 < 1 && x11:0 <= 1 + x175:0) l4(x16, x17, x18, x20, x21, x22) -> l9(x16, x18, x20, c5, x22) :|: c5 = 1 + x21 && (x17 > 0 && x20 <= 1 + x16) ---------------------------------------- (14) RankingReductionPairProof (EQUIVALENT) Interpretation: [ l9 ] = 4*l9_5 + 1 [ l4 ] = 4*l4_6 + 1 The following rules are decreasing: l9(x, x2, x4, x5, x6) -> l4(x, x7, x2, x4, x5, c2) :|: c2 = -1 + x6 && (x5 > 0 && x5 <= x && x6 > 0 && x7 < 2 && x7 > -1) The following rules are bounded: l9(x, x2, x4, x5, x6) -> l4(x, x7, x2, x4, x5, c2) :|: c2 = -1 + x6 && (x5 > 0 && x5 <= x && x6 > 0 && x7 < 2 && x7 > -1) ---------------------------------------- (15) Obligation: Rules: l9(x8, x10, x12, x13, x14) -> l4(x8, x15, c3, x12, x13, x14) :|: c3 = -1 + x10 && (x13 > 0 && x13 <= x8 && x14 < 1 && x10 > 0 && x15 > -1 && x15 < 2 && x15 < 1) l4(x175:0, x176:0, x177:0, x11:0, x33:0, x13:0) -> l9(x175:0, x177:0, x11:0, c4, x13:0) :|: c4 = -1 + x33:0 && (x176:0 < 1 && x11:0 <= 1 + x175:0) l4(x16, x17, x18, x20, x21, x22) -> l9(x16, x18, x20, c5, x22) :|: c5 = 1 + x21 && (x17 > 0 && x20 <= 1 + x16) ---------------------------------------- (16) PolynomialOrderProcessor (EQUIVALENT) Found the following polynomial interpretation: [l9(x, x1, x2, x3, x4)] = -2 + 2*x + x1 - x3 - x4 [l4(x5, x6, x7, x8, x9, x10)] = -1 - x10 + 2*x5 + x7 - x9 The following rules are decreasing: l4(x16, x17, x18, x20, x21, x22) -> l9(x16, x18, x20, c5, x22) :|: c5 = 1 + x21 && (x17 > 0 && x20 <= 1 + x16) The following rules are bounded: l9(x8, x10, x12, x13, x14) -> l4(x8, x15, c3, x12, x13, x14) :|: c3 = -1 + x10 && (x13 > 0 && x13 <= x8 && x14 < 1 && x10 > 0 && x15 > -1 && x15 < 2 && x15 < 1) ---------------------------------------- (17) Complex Obligation (AND) ---------------------------------------- (18) Obligation: Rules: l9(x8, x10, x12, x13, x14) -> l4(x8, x15, c3, x12, x13, x14) :|: c3 = -1 + x10 && (x13 > 0 && x13 <= x8 && x14 < 1 && x10 > 0 && x15 > -1 && x15 < 2 && x15 < 1) l4(x175:0, x176:0, x177:0, x11:0, x33:0, x13:0) -> l9(x175:0, x177:0, x11:0, c4, x13:0) :|: c4 = -1 + x33:0 && (x176:0 < 1 && x11:0 <= 1 + x175:0) ---------------------------------------- (19) RankingReductionPairProof (EQUIVALENT) Interpretation: [ l9 ] = 2*l9_4 + 2*l9_2 [ l4 ] = 2*l4_5 + 2*l4_3 + 1 The following rules are decreasing: l9(x8, x10, x12, x13, x14) -> l4(x8, x15, c3, x12, x13, x14) :|: c3 = -1 + x10 && (x13 > 0 && x13 <= x8 && x14 < 1 && x10 > 0 && x15 > -1 && x15 < 2 && x15 < 1) l4(x175:0, x176:0, x177:0, x11:0, x33:0, x13:0) -> l9(x175:0, x177:0, x11:0, c4, x13:0) :|: c4 = -1 + x33:0 && (x176:0 < 1 && x11:0 <= 1 + x175:0) The following rules are bounded: l9(x8, x10, x12, x13, x14) -> l4(x8, x15, c3, x12, x13, x14) :|: c3 = -1 + x10 && (x13 > 0 && x13 <= x8 && x14 < 1 && x10 > 0 && x15 > -1 && x15 < 2 && x15 < 1) ---------------------------------------- (20) Obligation: Rules: l4(x175:0, x176:0, x177:0, x11:0, x33:0, x13:0) -> l9(x175:0, x177:0, x11:0, c4, x13:0) :|: c4 = -1 + x33:0 && (x176:0 < 1 && x11:0 <= 1 + x175:0) ---------------------------------------- (21) RankingReductionPairProof (EQUIVALENT) Interpretation: [ l4 ] = 0 [ l9 ] = -1 The following rules are decreasing: l4(x175:0, x176:0, x177:0, x11:0, x33:0, x13:0) -> l9(x175:0, x177:0, x11:0, c4, x13:0) :|: c4 = -1 + x33:0 && (x176:0 < 1 && x11:0 <= 1 + x175:0) The following rules are bounded: l4(x175:0, x176:0, x177:0, x11:0, x33:0, x13:0) -> l9(x175:0, x177:0, x11:0, c4, x13:0) :|: c4 = -1 + x33:0 && (x176:0 < 1 && x11:0 <= 1 + x175:0) ---------------------------------------- (22) YES ---------------------------------------- (23) Obligation: Rules: l4(x175:0, x176:0, x177:0, x11:0, x33:0, x13:0) -> l9(x175:0, x177:0, x11:0, c4, x13:0) :|: c4 = -1 + x33:0 && (x176:0 < 1 && x11:0 <= 1 + x175:0) l4(x16, x17, x18, x20, x21, x22) -> l9(x16, x18, x20, c5, x22) :|: c5 = 1 + x21 && (x17 > 0 && x20 <= 1 + x16) ---------------------------------------- (24) RankingReductionPairProof (EQUIVALENT) Interpretation: [ l4 ] = 0 [ l9 ] = -1 The following rules are decreasing: l4(x175:0, x176:0, x177:0, x11:0, x33:0, x13:0) -> l9(x175:0, x177:0, x11:0, c4, x13:0) :|: c4 = -1 + x33:0 && (x176:0 < 1 && x11:0 <= 1 + x175:0) l4(x16, x17, x18, x20, x21, x22) -> l9(x16, x18, x20, c5, x22) :|: c5 = 1 + x21 && (x17 > 0 && x20 <= 1 + x16) The following rules are bounded: l4(x175:0, x176:0, x177:0, x11:0, x33:0, x13:0) -> l9(x175:0, x177:0, x11:0, c4, x13:0) :|: c4 = -1 + x33:0 && (x176:0 < 1 && x11:0 <= 1 + x175:0) l4(x16, x17, x18, x20, x21, x22) -> l9(x16, x18, x20, c5, x22) :|: c5 = 1 + x21 && (x17 > 0 && x20 <= 1 + x16) ---------------------------------------- (25) YES ---------------------------------------- (26) Obligation: Rules: l9(x105:0, x107:0, x109:0, x110:0, x111:0) -> l4(x105:0, x106:0, c, c1, x110:0, x69:0) :|: c1 = 1 + x109:0 && c = 1 + x109:0 && (x110:0 > 0 && x110:0 <= x105:0 && x111:0 < 1 && x107:0 < 1 && x106:0 > -1 && x69:0 > -1 && x106:0 < 2) l9(x, x2, x4, x5, x6) -> l4(x, x7, x2, x4, x5, c2) :|: c2 = -1 + x6 && (x5 > 0 && x5 <= x && x6 > 0 && x7 < 2 && x7 > -1) l9(x8, x10, x12, x13, x14) -> l4(x8, x15, c3, x12, x13, x14) :|: c3 = -1 + x10 && (x13 > 0 && x13 <= x8 && x14 < 1 && x10 > 0 && x15 > -1 && x15 < 2 && x15 < 1) ---------------------------------------- (27) PolynomialOrderProcessor (EQUIVALENT) Found the following polynomial interpretation: [l9(x, x1, x2, x3, x4)] = 1 [l4(x5, x6, x7, x8, x9, x10)] = 0 The following rules are decreasing: l9(x105:0, x107:0, x109:0, x110:0, x111:0) -> l4(x105:0, x106:0, c, c1, x110:0, x69:0) :|: c1 = 1 + x109:0 && c = 1 + x109:0 && (x110:0 > 0 && x110:0 <= x105:0 && x111:0 < 1 && x107:0 < 1 && x106:0 > -1 && x69:0 > -1 && x106:0 < 2) l9(x, x2, x4, x5, x6) -> l4(x, x7, x2, x4, x5, c2) :|: c2 = -1 + x6 && (x5 > 0 && x5 <= x && x6 > 0 && x7 < 2 && x7 > -1) l9(x8, x10, x12, x13, x14) -> l4(x8, x15, c3, x12, x13, x14) :|: c3 = -1 + x10 && (x13 > 0 && x13 <= x8 && x14 < 1 && x10 > 0 && x15 > -1 && x15 < 2 && x15 < 1) The following rules are bounded: l9(x105:0, x107:0, x109:0, x110:0, x111:0) -> l4(x105:0, x106:0, c, c1, x110:0, x69:0) :|: c1 = 1 + x109:0 && c = 1 + x109:0 && (x110:0 > 0 && x110:0 <= x105:0 && x111:0 < 1 && x107:0 < 1 && x106:0 > -1 && x69:0 > -1 && x106:0 < 2) l9(x, x2, x4, x5, x6) -> l4(x, x7, x2, x4, x5, c2) :|: c2 = -1 + x6 && (x5 > 0 && x5 <= x && x6 > 0 && x7 < 2 && x7 > -1) l9(x8, x10, x12, x13, x14) -> l4(x8, x15, c3, x12, x13, x14) :|: c3 = -1 + x10 && (x13 > 0 && x13 <= x8 && x14 < 1 && x10 > 0 && x15 > -1 && x15 < 2 && x15 < 1) ---------------------------------------- (28) YES