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, 811 ms] (4) IRSwT (5) IntTRSCompressionProof [EQUIVALENT, 0 ms] (6) IRSwT (7) IntTRSUnneededArgumentFilterProof [EQUIVALENT, 0 ms] (8) IRSwT (9) TempFilterProof [SOUND, 83 ms] (10) IntTRS (11) PolynomialOrderProcessor [EQUIVALENT, 0 ms] (12) IntTRS (13) RankingReductionPairProof [EQUIVALENT, 0 ms] (14) IntTRS (15) PolynomialOrderProcessor [EQUIVALENT, 0 ms] (16) YES ---------------------------------------- (0) Obligation: Rules: l0(copiedHAT0, eHAT0, nHAT0, oldeHAT0, oldnHAT0) -> l1(copiedHATpost, eHATpost, nHATpost, oldeHATpost, oldnHATpost) :|: oldnHAT0 = oldnHATpost && oldeHAT0 = oldeHATpost && nHAT0 = nHATpost && eHAT0 = eHATpost && copiedHAT0 = copiedHATpost && nHAT0 <= oldnHAT0 && oldeHAT0 <= eHAT0 && 1 <= copiedHAT0 l0(x, x1, x2, x3, x4) -> l2(x5, x6, x7, x8, x9) :|: x6 = 1 + x1 && x7 = 11 + x2 && x2 <= 100 && 1 <= x1 && x8 = x1 && x9 = x2 && x5 = 1 && x <= 0 l2(x10, x11, x12, x13, x14) -> l0(x15, x16, x17, x18, x19) :|: x14 = x19 && x13 = x18 && x12 = x17 && x11 = x16 && x10 = x15 l0(x20, x21, x22, x23, x24) -> l3(x25, x26, x27, x28, x29) :|: x26 = -1 + x21 && x27 = -10 + x22 && 101 <= x22 && 1 <= x21 && x28 = x21 && x29 = x22 && x25 = 1 && x20 <= 0 l3(x30, x31, x32, x33, x34) -> l0(x35, x36, x37, x38, x39) :|: x34 = x39 && x33 = x38 && x32 = x37 && x31 = x36 && x30 = x35 l0(x40, x41, x42, x43, x44) -> l4(x45, x46, x47, x48, x49) :|: x44 = x49 && x43 = x48 && x40 = x45 && x46 = 1 + x41 && x47 = 11 + x42 && x42 <= 100 && 1 <= x41 l4(x50, x51, x52, x53, x54) -> l0(x55, x56, x57, x58, x59) :|: x54 = x59 && x53 = x58 && x52 = x57 && x51 = x56 && x50 = x55 l0(x60, x61, x62, x63, x64) -> l5(x65, x66, x67, x68, x69) :|: x64 = x69 && x63 = x68 && x60 = x65 && x66 = -1 + x61 && x67 = -10 + x62 && 101 <= x62 && 1 <= x61 l5(x70, x71, x72, x73, x74) -> l0(x75, x76, x77, x78, x79) :|: x74 = x79 && x73 = x78 && x72 = x77 && x71 = x76 && x70 = x75 l6(x80, x81, x82, x83, x84) -> l0(x85, x86, x87, x88, x89) :|: x84 = x89 && x83 = x88 && x85 = 0 && x86 = 1 && x87 = x87 l7(x90, x91, x92, x93, x94) -> l6(x95, x96, x97, x98, x99) :|: x94 = x99 && x93 = x98 && x92 = x97 && x91 = x96 && x90 = x95 Start term: l7(copiedHAT0, eHAT0, nHAT0, oldeHAT0, oldnHAT0) ---------------------------------------- (1) IRSFormatTransformerProof (EQUIVALENT) Reformatted IRS to match normalized format (transformed away non-linear left-hand sides, !=, / and %). ---------------------------------------- (2) Obligation: Rules: l0(copiedHAT0, eHAT0, nHAT0, oldeHAT0, oldnHAT0) -> l1(copiedHATpost, eHATpost, nHATpost, oldeHATpost, oldnHATpost) :|: oldnHAT0 = oldnHATpost && oldeHAT0 = oldeHATpost && nHAT0 = nHATpost && eHAT0 = eHATpost && copiedHAT0 = copiedHATpost && nHAT0 <= oldnHAT0 && oldeHAT0 <= eHAT0 && 1 <= copiedHAT0 l0(x, x1, x2, x3, x4) -> l2(x5, x6, x7, x8, x9) :|: x6 = 1 + x1 && x7 = 11 + x2 && x2 <= 100 && 1 <= x1 && x8 = x1 && x9 = x2 && x5 = 1 && x <= 0 l2(x10, x11, x12, x13, x14) -> l0(x15, x16, x17, x18, x19) :|: x14 = x19 && x13 = x18 && x12 = x17 && x11 = x16 && x10 = x15 l0(x20, x21, x22, x23, x24) -> l3(x25, x26, x27, x28, x29) :|: x26 = -1 + x21 && x27 = -10 + x22 && 101 <= x22 && 1 <= x21 && x28 = x21 && x29 = x22 && x25 = 1 && x20 <= 0 l3(x30, x31, x32, x33, x34) -> l0(x35, x36, x37, x38, x39) :|: x34 = x39 && x33 = x38 && x32 = x37 && x31 = x36 && x30 = x35 l0(x40, x41, x42, x43, x44) -> l4(x45, x46, x47, x48, x49) :|: x44 = x49 && x43 = x48 && x40 = x45 && x46 = 1 + x41 && x47 = 11 + x42 && x42 <= 100 && 1 <= x41 l4(x50, x51, x52, x53, x54) -> l0(x55, x56, x57, x58, x59) :|: x54 = x59 && x53 = x58 && x52 = x57 && x51 = x56 && x50 = x55 l0(x60, x61, x62, x63, x64) -> l5(x65, x66, x67, x68, x69) :|: x64 = x69 && x63 = x68 && x60 = x65 && x66 = -1 + x61 && x67 = -10 + x62 && 101 <= x62 && 1 <= x61 l5(x70, x71, x72, x73, x74) -> l0(x75, x76, x77, x78, x79) :|: x74 = x79 && x73 = x78 && x72 = x77 && x71 = x76 && x70 = x75 l6(x80, x81, x82, x83, x84) -> l0(x85, x86, x87, x88, x89) :|: x84 = x89 && x83 = x88 && x85 = 0 && x86 = 1 && x87 = x87 l7(x90, x91, x92, x93, x94) -> l6(x95, x96, x97, x98, x99) :|: x94 = x99 && x93 = x98 && x92 = x97 && x91 = x96 && x90 = x95 Start term: l7(copiedHAT0, eHAT0, nHAT0, oldeHAT0, oldnHAT0) ---------------------------------------- (3) IRSwTTerminationDigraphProof (EQUIVALENT) Constructed termination digraph! Nodes: (1) l0(copiedHAT0, eHAT0, nHAT0, oldeHAT0, oldnHAT0) -> l1(copiedHATpost, eHATpost, nHATpost, oldeHATpost, oldnHATpost) :|: oldnHAT0 = oldnHATpost && oldeHAT0 = oldeHATpost && nHAT0 = nHATpost && eHAT0 = eHATpost && copiedHAT0 = copiedHATpost && nHAT0 <= oldnHAT0 && oldeHAT0 <= eHAT0 && 1 <= copiedHAT0 (2) l0(x, x1, x2, x3, x4) -> l2(x5, x6, x7, x8, x9) :|: x6 = 1 + x1 && x7 = 11 + x2 && x2 <= 100 && 1 <= x1 && x8 = x1 && x9 = x2 && x5 = 1 && x <= 0 (3) l2(x10, x11, x12, x13, x14) -> l0(x15, x16, x17, x18, x19) :|: x14 = x19 && x13 = x18 && x12 = x17 && x11 = x16 && x10 = x15 (4) l0(x20, x21, x22, x23, x24) -> l3(x25, x26, x27, x28, x29) :|: x26 = -1 + x21 && x27 = -10 + x22 && 101 <= x22 && 1 <= x21 && x28 = x21 && x29 = x22 && x25 = 1 && x20 <= 0 (5) l3(x30, x31, x32, x33, x34) -> l0(x35, x36, x37, x38, x39) :|: x34 = x39 && x33 = x38 && x32 = x37 && x31 = x36 && x30 = x35 (6) l0(x40, x41, x42, x43, x44) -> l4(x45, x46, x47, x48, x49) :|: x44 = x49 && x43 = x48 && x40 = x45 && x46 = 1 + x41 && x47 = 11 + x42 && x42 <= 100 && 1 <= x41 (7) l4(x50, x51, x52, x53, x54) -> l0(x55, x56, x57, x58, x59) :|: x54 = x59 && x53 = x58 && x52 = x57 && x51 = x56 && x50 = x55 (8) l0(x60, x61, x62, x63, x64) -> l5(x65, x66, x67, x68, x69) :|: x64 = x69 && x63 = x68 && x60 = x65 && x66 = -1 + x61 && x67 = -10 + x62 && 101 <= x62 && 1 <= x61 (9) l5(x70, x71, x72, x73, x74) -> l0(x75, x76, x77, x78, x79) :|: x74 = x79 && x73 = x78 && x72 = x77 && x71 = x76 && x70 = x75 (10) l6(x80, x81, x82, x83, x84) -> l0(x85, x86, x87, x88, x89) :|: x84 = x89 && x83 = x88 && x85 = 0 && x86 = 1 && x87 = x87 (11) l7(x90, x91, x92, x93, x94) -> l6(x95, x96, x97, x98, x99) :|: x94 = x99 && x93 = x98 && x92 = x97 && x91 = x96 && x90 = x95 Arcs: (2) -> (3) (3) -> (1), (2), (4), (6), (8) (4) -> (5) (5) -> (1), (2), (4), (6), (8) (6) -> (7) (7) -> (1), (2), (4), (6), (8) (8) -> (9) (9) -> (1), (2), (4), (6), (8) (10) -> (2), (4), (6), (8) (11) -> (10) This digraph is fully evaluated! ---------------------------------------- (4) Obligation: Termination digraph: Nodes: (1) l0(x, x1, x2, x3, x4) -> l2(x5, x6, x7, x8, x9) :|: x6 = 1 + x1 && x7 = 11 + x2 && x2 <= 100 && 1 <= x1 && x8 = x1 && x9 = x2 && x5 = 1 && x <= 0 (2) l3(x30, x31, x32, x33, x34) -> l0(x35, x36, x37, x38, x39) :|: x34 = x39 && x33 = x38 && x32 = x37 && x31 = x36 && x30 = x35 (3) l0(x20, x21, x22, x23, x24) -> l3(x25, x26, x27, x28, x29) :|: x26 = -1 + x21 && x27 = -10 + x22 && 101 <= x22 && 1 <= x21 && x28 = x21 && x29 = x22 && x25 = 1 && x20 <= 0 (4) l4(x50, x51, x52, x53, x54) -> l0(x55, x56, x57, x58, x59) :|: x54 = x59 && x53 = x58 && x52 = x57 && x51 = x56 && x50 = x55 (5) l0(x40, x41, x42, x43, x44) -> l4(x45, x46, x47, x48, x49) :|: x44 = x49 && x43 = x48 && x40 = x45 && x46 = 1 + x41 && x47 = 11 + x42 && x42 <= 100 && 1 <= x41 (6) l5(x70, x71, x72, x73, x74) -> l0(x75, x76, x77, x78, x79) :|: x74 = x79 && x73 = x78 && x72 = x77 && x71 = x76 && x70 = x75 (7) l0(x60, x61, x62, x63, x64) -> l5(x65, x66, x67, x68, x69) :|: x64 = x69 && x63 = x68 && x60 = x65 && x66 = -1 + x61 && x67 = -10 + x62 && 101 <= x62 && 1 <= x61 (8) l2(x10, x11, x12, x13, x14) -> l0(x15, x16, x17, x18, x19) :|: x14 = x19 && x13 = x18 && x12 = x17 && x11 = x16 && x10 = x15 Arcs: (1) -> (8) (2) -> (1), (3), (5), (7) (3) -> (2) (4) -> (1), (3), (5), (7) (5) -> (4) (6) -> (1), (3), (5), (7) (7) -> (6) (8) -> (1), (3), (5), (7) This digraph is fully evaluated! ---------------------------------------- (5) IntTRSCompressionProof (EQUIVALENT) Compressed rules. ---------------------------------------- (6) Obligation: Rules: l0(x:0, x18:0, x19:0, x3:0, x4:0) -> l0(1, 1 + x18:0, 11 + x19:0, x18:0, x19:0) :|: x18:0 > 0 && x19:0 < 101 && x:0 < 1 l0(x20:0, x21:0, x22:0, x23:0, x24:0) -> l0(1, -1 + x21:0, -10 + x22:0, x21:0, x22:0) :|: x21:0 > 0 && x22:0 > 100 && x20:0 < 1 l0(x40:0, x41:0, x42:0, x43:0, x44:0) -> l0(x40:0, 1 + x41:0, 11 + x42:0, x43:0, x44:0) :|: x41:0 > 0 && x42:0 < 101 l0(x60:0, x61:0, x62:0, x63:0, x64:0) -> l0(x60:0, -1 + x61:0, -10 + x62:0, x63:0, x64:0) :|: x61:0 > 0 && x62:0 > 100 ---------------------------------------- (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) -> l0(x1, x2, x3) ---------------------------------------- (8) Obligation: Rules: l0(x:0, x18:0, x19:0) -> l0(1, 1 + x18:0, 11 + x19:0) :|: x18:0 > 0 && x19:0 < 101 && x:0 < 1 l0(x20:0, x21:0, x22:0) -> l0(1, -1 + x21:0, -10 + x22:0) :|: x21:0 > 0 && x22:0 > 100 && x20:0 < 1 l0(x40:0, x41:0, x42:0) -> l0(x40:0, 1 + x41:0, 11 + x42:0) :|: x41:0 > 0 && x42:0 < 101 l0(x60:0, x61:0, x62:0) -> l0(x60:0, -1 + x61:0, -10 + x62:0) :|: x61:0 > 0 && x62:0 > 100 ---------------------------------------- (9) TempFilterProof (SOUND) Used the following sort dictionary for filtering: l0(VARIABLE, INTEGER, INTEGER) Replaced non-predefined constructor symbols by 0. ---------------------------------------- (10) Obligation: Rules: l0(x:0, x18:0, x19:0) -> l0(c, c1, c2) :|: c2 = 11 + x19:0 && (c1 = 1 + x18:0 && c = 1) && (x18:0 > 0 && x19:0 < 101 && x:0 < 1) l0(x20:0, x21:0, x22:0) -> l0(c3, c4, c5) :|: c5 = -10 + x22:0 && (c4 = -1 + x21:0 && c3 = 1) && (x21:0 > 0 && x22:0 > 100 && x20:0 < 1) l0(x40:0, x41:0, x42:0) -> l0(x40:0, c6, c7) :|: c7 = 11 + x42:0 && c6 = 1 + x41:0 && (x41:0 > 0 && x42:0 < 101) l0(x60:0, x61:0, x62:0) -> l0(x60:0, c8, c9) :|: c9 = -10 + x62:0 && c8 = -1 + x61:0 && (x61:0 > 0 && x62:0 > 100) ---------------------------------------- (11) PolynomialOrderProcessor (EQUIVALENT) Found the following polynomial interpretation: [l0(x, x1, x2)] = -x The following rules are decreasing: l0(x:0, x18:0, x19:0) -> l0(c, c1, c2) :|: c2 = 11 + x19:0 && (c1 = 1 + x18:0 && c = 1) && (x18:0 > 0 && x19:0 < 101 && x:0 < 1) l0(x20:0, x21:0, x22:0) -> l0(c3, c4, c5) :|: c5 = -10 + x22:0 && (c4 = -1 + x21:0 && c3 = 1) && (x21:0 > 0 && x22:0 > 100 && x20:0 < 1) The following rules are bounded: l0(x:0, x18:0, x19:0) -> l0(c, c1, c2) :|: c2 = 11 + x19:0 && (c1 = 1 + x18:0 && c = 1) && (x18:0 > 0 && x19:0 < 101 && x:0 < 1) l0(x20:0, x21:0, x22:0) -> l0(c3, c4, c5) :|: c5 = -10 + x22:0 && (c4 = -1 + x21:0 && c3 = 1) && (x21:0 > 0 && x22:0 > 100 && x20:0 < 1) ---------------------------------------- (12) Obligation: Rules: l0(x40:0, x41:0, x42:0) -> l0(x40:0, c6, c7) :|: c7 = 11 + x42:0 && c6 = 1 + x41:0 && (x41:0 > 0 && x42:0 < 101) l0(x60:0, x61:0, x62:0) -> l0(x60:0, c8, c9) :|: c9 = -10 + x62:0 && c8 = -1 + x61:0 && (x61:0 > 0 && x62:0 > 100) ---------------------------------------- (13) RankingReductionPairProof (EQUIVALENT) Interpretation: [ l0 ] = 31*l0_2 + -3*l0_3 The following rules are decreasing: l0(x40:0, x41:0, x42:0) -> l0(x40:0, c6, c7) :|: c7 = 11 + x42:0 && c6 = 1 + x41:0 && (x41:0 > 0 && x42:0 < 101) l0(x60:0, x61:0, x62:0) -> l0(x60:0, c8, c9) :|: c9 = -10 + x62:0 && c8 = -1 + x61:0 && (x61:0 > 0 && x62:0 > 100) The following rules are bounded: l0(x40:0, x41:0, x42:0) -> l0(x40:0, c6, c7) :|: c7 = 11 + x42:0 && c6 = 1 + x41:0 && (x41:0 > 0 && x42:0 < 101) ---------------------------------------- (14) Obligation: Rules: l0(x60:0, x61:0, x62:0) -> l0(x60:0, c8, c9) :|: c9 = -10 + x62:0 && c8 = -1 + x61:0 && (x61:0 > 0 && x62:0 > 100) ---------------------------------------- (15) PolynomialOrderProcessor (EQUIVALENT) Found the following polynomial interpretation: [l0(x, x1, x2)] = -1 + x1 The following rules are decreasing: l0(x60:0, x61:0, x62:0) -> l0(x60:0, c8, c9) :|: c9 = -10 + x62:0 && c8 = -1 + x61:0 && (x61:0 > 0 && x62:0 > 100) The following rules are bounded: l0(x60:0, x61:0, x62:0) -> l0(x60:0, c8, c9) :|: c9 = -10 + x62:0 && c8 = -1 + x61:0 && (x61:0 > 0 && x62:0 > 100) ---------------------------------------- (16) YES