MAYBE proof of prog.inttrs # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty Termination of the given IRSwT could not be shown: (0) IRSwT (1) IRSFormatTransformerProof [EQUIVALENT, 0 ms] (2) IRSwT (3) IRSwTTerminationDigraphProof [EQUIVALENT, 124 ms] (4) IRSwT (5) IntTRSCompressionProof [EQUIVALENT, 9 ms] (6) IRSwT (7) IntTRSUnneededArgumentFilterProof [EQUIVALENT, 0 ms] (8) IRSwT (9) TempFilterProof [SOUND, 264 ms] (10) IRSwT (11) IRSwTTerminationDigraphProof [EQUIVALENT, 0 ms] (12) IRSwT (13) IntTRSCompressionProof [EQUIVALENT, 0 ms] (14) IRSwT ---------------------------------------- (0) Obligation: Rules: f1_0_main_Load(arg1, arg2) -> f53_0_loop_LE(arg1P, arg2P) :|: arg2 = arg1P && -1 <= arg2 - 1 && 0 <= arg1 - 1 f53_0_loop_LE(x, x1) -> f74_0_loop_NE(x2, x3) :|: x - 1 = x2 && 10 <= x - 1 && x <= 20 f53_0_loop_LE(x4, x5) -> f74_0_loop_NE(x6, x7) :|: x4 + 1 = x6 && 20 <= x4 - 1 f74_0_loop_NE(x8, x9) -> f53_0_loop_LE(x10, x11) :|: x8 = x10 && x8 <= 29 f74_0_loop_NE(x12, x13) -> f53_0_loop_LE(x14, x15) :|: x12 = x14 && 30 <= x12 - 1 __init(x16, x17) -> f1_0_main_Load(x18, x19) :|: 0 <= 0 Start term: __init(arg1, arg2) ---------------------------------------- (1) IRSFormatTransformerProof (EQUIVALENT) Reformatted IRS to match normalized format (transformed away non-linear left-hand sides, !=, / and %). ---------------------------------------- (2) Obligation: Rules: f1_0_main_Load(arg1, arg2) -> f53_0_loop_LE(arg1P, arg2P) :|: arg2 = arg1P && -1 <= arg2 - 1 && 0 <= arg1 - 1 f53_0_loop_LE(x, x1) -> f74_0_loop_NE(x2, x3) :|: x - 1 = x2 && 10 <= x - 1 && x <= 20 f53_0_loop_LE(x4, x5) -> f74_0_loop_NE(x6, x7) :|: x4 + 1 = x6 && 20 <= x4 - 1 f74_0_loop_NE(x8, x9) -> f53_0_loop_LE(x10, x11) :|: x8 = x10 && x8 <= 29 f74_0_loop_NE(x12, x13) -> f53_0_loop_LE(x14, x15) :|: x12 = x14 && 30 <= x12 - 1 __init(x16, x17) -> f1_0_main_Load(x18, x19) :|: 0 <= 0 Start term: __init(arg1, arg2) ---------------------------------------- (3) IRSwTTerminationDigraphProof (EQUIVALENT) Constructed termination digraph! Nodes: (1) f1_0_main_Load(arg1, arg2) -> f53_0_loop_LE(arg1P, arg2P) :|: arg2 = arg1P && -1 <= arg2 - 1 && 0 <= arg1 - 1 (2) f53_0_loop_LE(x, x1) -> f74_0_loop_NE(x2, x3) :|: x - 1 = x2 && 10 <= x - 1 && x <= 20 (3) f53_0_loop_LE(x4, x5) -> f74_0_loop_NE(x6, x7) :|: x4 + 1 = x6 && 20 <= x4 - 1 (4) f74_0_loop_NE(x8, x9) -> f53_0_loop_LE(x10, x11) :|: x8 = x10 && x8 <= 29 (5) f74_0_loop_NE(x12, x13) -> f53_0_loop_LE(x14, x15) :|: x12 = x14 && 30 <= x12 - 1 (6) __init(x16, x17) -> f1_0_main_Load(x18, x19) :|: 0 <= 0 Arcs: (1) -> (2), (3) (2) -> (4) (3) -> (4), (5) (4) -> (2), (3) (5) -> (3) (6) -> (1) This digraph is fully evaluated! ---------------------------------------- (4) Obligation: Termination digraph: Nodes: (1) f53_0_loop_LE(x, x1) -> f74_0_loop_NE(x2, x3) :|: x - 1 = x2 && 10 <= x - 1 && x <= 20 (2) f74_0_loop_NE(x8, x9) -> f53_0_loop_LE(x10, x11) :|: x8 = x10 && x8 <= 29 (3) f53_0_loop_LE(x4, x5) -> f74_0_loop_NE(x6, x7) :|: x4 + 1 = x6 && 20 <= x4 - 1 (4) f74_0_loop_NE(x12, x13) -> f53_0_loop_LE(x14, x15) :|: x12 = x14 && 30 <= x12 - 1 Arcs: (1) -> (2) (2) -> (1), (3) (3) -> (2), (4) (4) -> (3) This digraph is fully evaluated! ---------------------------------------- (5) IntTRSCompressionProof (EQUIVALENT) Compressed rules. ---------------------------------------- (6) Obligation: Rules: f74_0_loop_NE(x12:0, x13:0) -> f53_0_loop_LE(x12:0, x15:0) :|: x12:0 > 30 f53_0_loop_LE(x:0, x1:0) -> f74_0_loop_NE(x:0 - 1, x3:0) :|: x:0 < 21 && x:0 > 10 f74_0_loop_NE(x10:0, x9:0) -> f53_0_loop_LE(x10:0, x11:0) :|: x10:0 < 30 f53_0_loop_LE(x4:0, x5:0) -> f74_0_loop_NE(x4:0 + 1, x7:0) :|: x4:0 > 20 ---------------------------------------- (7) IntTRSUnneededArgumentFilterProof (EQUIVALENT) Some arguments are removed because they cannot influence termination. We removed arguments according to the following replacements: f74_0_loop_NE(x1, x2) -> f74_0_loop_NE(x1) f53_0_loop_LE(x1, x2) -> f53_0_loop_LE(x1) ---------------------------------------- (8) Obligation: Rules: f74_0_loop_NE(x12:0) -> f53_0_loop_LE(x12:0) :|: x12:0 > 30 f53_0_loop_LE(x:0) -> f74_0_loop_NE(x:0 - 1) :|: x:0 < 21 && x:0 > 10 f74_0_loop_NE(x10:0) -> f53_0_loop_LE(x10:0) :|: x10:0 < 30 f53_0_loop_LE(x4:0) -> f74_0_loop_NE(x4:0 + 1) :|: x4:0 > 20 ---------------------------------------- (9) TempFilterProof (SOUND) Used the following sort dictionary for filtering: f74_0_loop_NE(INTEGER) f53_0_loop_LE(INTEGER) Replaced non-predefined constructor symbols by 0.The following proof was generated: # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty Termination of the given IntTRS could not be shown: - IntTRS - RankingReductionPairProof Rules: f74_0_loop_NE(x12:0) -> f53_0_loop_LE(x12:0) :|: x12:0 > 30 f53_0_loop_LE(x:0) -> f74_0_loop_NE(c) :|: c = x:0 - 1 && (x:0 < 21 && x:0 > 10) f74_0_loop_NE(x10:0) -> f53_0_loop_LE(x10:0) :|: x10:0 < 30 f53_0_loop_LE(x4:0) -> f74_0_loop_NE(c1) :|: c1 = x4:0 + 1 && x4:0 > 20 Interpretation: [ f74_0_loop_NE ] = 158*f74_0_loop_NE_1 + -4*f74_0_loop_NE_1^2 + 1 [ f53_0_loop_LE ] = 158*f53_0_loop_LE_1 + -4*f53_0_loop_LE_1^2 The following rules are decreasing: f74_0_loop_NE(x12:0) -> f53_0_loop_LE(x12:0) :|: x12:0 > 30 f53_0_loop_LE(x:0) -> f74_0_loop_NE(c) :|: c = x:0 - 1 && (x:0 < 21 && x:0 > 10) f74_0_loop_NE(x10:0) -> f53_0_loop_LE(x10:0) :|: x10:0 < 30 f53_0_loop_LE(x4:0) -> f74_0_loop_NE(c1) :|: c1 = x4:0 + 1 && x4:0 > 20 The following rules are bounded: f53_0_loop_LE(x:0) -> f74_0_loop_NE(c) :|: c = x:0 - 1 && (x:0 < 21 && x:0 > 10) - IntTRS - RankingReductionPairProof - IntTRS - PolynomialOrderProcessor Rules: f74_0_loop_NE(x12:0) -> f53_0_loop_LE(x12:0) :|: x12:0 > 30 f74_0_loop_NE(x10:0) -> f53_0_loop_LE(x10:0) :|: x10:0 < 30 f53_0_loop_LE(x4:0) -> f74_0_loop_NE(c1) :|: c1 = x4:0 + 1 && x4:0 > 20 Found the following polynomial interpretation: [f74_0_loop_NE(x)] = 29 - x [f53_0_loop_LE(x1)] = 29 - x1 The following rules are decreasing: f53_0_loop_LE(x4:0) -> f74_0_loop_NE(c1) :|: c1 = x4:0 + 1 && x4:0 > 20 The following rules are bounded: f74_0_loop_NE(x10:0) -> f53_0_loop_LE(x10:0) :|: x10:0 < 30 - IntTRS - RankingReductionPairProof - IntTRS - PolynomialOrderProcessor - AND - IntTRS - IntTRS - PolynomialOrderProcessor - IntTRS Rules: f74_0_loop_NE(x12:0) -> f53_0_loop_LE(x12:0) :|: x12:0 > 30 f74_0_loop_NE(x10:0) -> f53_0_loop_LE(x10:0) :|: x10:0 < 30 Found the following polynomial interpretation: [f74_0_loop_NE(x)] = -30 + x [f53_0_loop_LE(x1)] = -31 + x1 The following rules are decreasing: f74_0_loop_NE(x12:0) -> f53_0_loop_LE(x12:0) :|: x12:0 > 30 f74_0_loop_NE(x10:0) -> f53_0_loop_LE(x10:0) :|: x10:0 < 30 The following rules are bounded: f74_0_loop_NE(x12:0) -> f53_0_loop_LE(x12:0) :|: x12:0 > 30 - IntTRS - RankingReductionPairProof - IntTRS - PolynomialOrderProcessor - AND - IntTRS - IntTRS - PolynomialOrderProcessor - IntTRS - RankingReductionPairProof - IntTRS Rules: f74_0_loop_NE(x10:0) -> f53_0_loop_LE(x10:0) :|: x10:0 < 30 Interpretation: [ f74_0_loop_NE ] = 0 [ f53_0_loop_LE ] = -1 The following rules are decreasing: f74_0_loop_NE(x10:0) -> f53_0_loop_LE(x10:0) :|: x10:0 < 30 The following rules are bounded: f74_0_loop_NE(x10:0) -> f53_0_loop_LE(x10:0) :|: x10:0 < 30 - IntTRS - RankingReductionPairProof - IntTRS - PolynomialOrderProcessor - AND - IntTRS - IntTRS - IntTRS Rules: f74_0_loop_NE(x12:0) -> f53_0_loop_LE(x12:0) :|: x12:0 > 30 f53_0_loop_LE(x4:0) -> f74_0_loop_NE(c1) :|: c1 = x4:0 + 1 && x4:0 > 20 ---------------------------------------- (10) Obligation: Rules: f74_0_loop_NE(x12:0) -> f53_0_loop_LE(x12:0) :|: x12:0 > 30 f53_0_loop_LE(x4:0) -> f74_0_loop_NE(x4:0 + 1) :|: x4:0 > 20 ---------------------------------------- (11) IRSwTTerminationDigraphProof (EQUIVALENT) Constructed termination digraph! Nodes: (1) f74_0_loop_NE(x12:0) -> f53_0_loop_LE(x12:0) :|: x12:0 > 30 (2) f53_0_loop_LE(x4:0) -> f74_0_loop_NE(x4:0 + 1) :|: x4:0 > 20 Arcs: (1) -> (2) (2) -> (1) This digraph is fully evaluated! ---------------------------------------- (12) Obligation: Termination digraph: Nodes: (1) f74_0_loop_NE(x12:0) -> f53_0_loop_LE(x12:0) :|: x12:0 > 30 (2) f53_0_loop_LE(x4:0) -> f74_0_loop_NE(x4:0 + 1) :|: x4:0 > 20 Arcs: (1) -> (2) (2) -> (1) This digraph is fully evaluated! ---------------------------------------- (13) IntTRSCompressionProof (EQUIVALENT) Compressed rules. ---------------------------------------- (14) Obligation: Rules: f74_0_loop_NE(x12:0:0) -> f74_0_loop_NE(x12:0:0 + 1) :|: x12:0:0 > 30