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, 341 ms] (4) AND (5) IRSwT (6) IntTRSCompressionProof [EQUIVALENT, 0 ms] (7) IRSwT (8) IntTRSUnneededArgumentFilterProof [EQUIVALENT, 0 ms] (9) IRSwT (10) TempFilterProof [SOUND, 36 ms] (11) IntTRS (12) RankingReductionPairProof [EQUIVALENT, 0 ms] (13) YES (14) IRSwT (15) IntTRSCompressionProof [EQUIVALENT, 0 ms] (16) IRSwT (17) IntTRSUnneededArgumentFilterProof [EQUIVALENT, 0 ms] (18) IRSwT (19) TempFilterProof [SOUND, 35 ms] (20) IRSwT (21) IRSwTTerminationDigraphProof [EQUIVALENT, 0 ms] (22) IRSwT (23) IntTRSCompressionProof [EQUIVALENT, 0 ms] (24) IRSwT ---------------------------------------- (0) Obligation: Rules: f1_0_main_Load(arg1, arg2) -> f1_0_main_Load'(arg1P, arg2P) :|: -1 <= x14 - 1 && 1 <= arg2 - 1 && x15 - 2 * x16 = 0 && -1 <= x15 - 1 && 0 <= arg1 - 1 && arg1 = arg1P && arg2 = arg2P f1_0_main_Load'(x, x1) -> f131_0_loop_LT(x2, x3) :|: -1 <= x4 - 1 && 1 <= x1 - 1 && x5 - 2 * x6 = 0 && -1 <= x5 - 1 && 0 <= x - 1 && x5 - 2 * x6 <= 1 && 0 <= x5 - 2 * x6 && 0 - x4 = x2 f1_0_main_Load(x7, x8) -> f1_0_main_Load'(x9, x10) :|: -1 <= x11 - 1 && 1 <= x8 - 1 && x12 - 2 * x13 = 1 && -1 <= x12 - 1 && 0 <= x7 - 1 && x7 = x9 && x8 = x10 f1_0_main_Load'(x17, x18) -> f130_0_loop_GT(x22, x23) :|: -1 <= x22 - 1 && 1 <= x18 - 1 && x27 - 2 * x28 = 1 && -1 <= x27 - 1 && 0 <= x17 - 1 && x27 - 2 * x28 <= 1 && 0 <= x27 - 2 * x28 f130_0_loop_GT(x29, x32) -> f163_0_loop_GE(x33, x34) :|: 0 = x33 && 0 = x29 f130_0_loop_GT(x35, x36) -> f163_0_loop_GE(x37, x38) :|: x35 - 1 = x37 && x35 <= 5 && 0 <= x35 - 1 f131_0_loop_LT(x39, x40) -> f163_0_loop_GE(x41, x42) :|: x39 = x41 && -6 <= x39 - 1 && x39 <= 5 && x39 <= 0 f163_0_loop_GE(x43, x44) -> f130_0_loop_GT(x45, x46) :|: x43 = x45 && -1 <= x43 - 1 f163_0_loop_GE(x47, x48) -> f131_0_loop_LT(x49, x50) :|: x47 + 1 = x49 && x47 <= -1 __init(x51, x52) -> f1_0_main_Load(x53, x54) :|: 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) -> f1_0_main_Load'(arg1P, arg2P) :|: -1 <= x14 - 1 && 1 <= arg2 - 1 && x15 - 2 * x16 = 0 && -1 <= x15 - 1 && 0 <= arg1 - 1 && arg1 = arg1P && arg2 = arg2P f1_0_main_Load'(x, x1) -> f131_0_loop_LT(x2, x3) :|: -1 <= x4 - 1 && 1 <= x1 - 1 && x5 - 2 * x6 = 0 && -1 <= x5 - 1 && 0 <= x - 1 && x5 - 2 * x6 <= 1 && 0 <= x5 - 2 * x6 && 0 - x4 = x2 f1_0_main_Load(x7, x8) -> f1_0_main_Load'(x9, x10) :|: -1 <= x11 - 1 && 1 <= x8 - 1 && x12 - 2 * x13 = 1 && -1 <= x12 - 1 && 0 <= x7 - 1 && x7 = x9 && x8 = x10 f1_0_main_Load'(x17, x18) -> f130_0_loop_GT(x22, x23) :|: -1 <= x22 - 1 && 1 <= x18 - 1 && x27 - 2 * x28 = 1 && -1 <= x27 - 1 && 0 <= x17 - 1 && x27 - 2 * x28 <= 1 && 0 <= x27 - 2 * x28 f130_0_loop_GT(x29, x32) -> f163_0_loop_GE(x33, x34) :|: 0 = x33 && 0 = x29 f130_0_loop_GT(x35, x36) -> f163_0_loop_GE(x37, x38) :|: x35 - 1 = x37 && x35 <= 5 && 0 <= x35 - 1 f131_0_loop_LT(x39, x40) -> f163_0_loop_GE(x41, x42) :|: x39 = x41 && -6 <= x39 - 1 && x39 <= 5 && x39 <= 0 f163_0_loop_GE(x43, x44) -> f130_0_loop_GT(x45, x46) :|: x43 = x45 && -1 <= x43 - 1 f163_0_loop_GE(x47, x48) -> f131_0_loop_LT(x49, x50) :|: x47 + 1 = x49 && x47 <= -1 __init(x51, x52) -> f1_0_main_Load(x53, x54) :|: 0 <= 0 Start term: __init(arg1, arg2) ---------------------------------------- (3) IRSwTTerminationDigraphProof (EQUIVALENT) Constructed termination digraph! Nodes: (1) f1_0_main_Load(arg1, arg2) -> f1_0_main_Load'(arg1P, arg2P) :|: -1 <= x14 - 1 && 1 <= arg2 - 1 && x15 - 2 * x16 = 0 && -1 <= x15 - 1 && 0 <= arg1 - 1 && arg1 = arg1P && arg2 = arg2P (2) f1_0_main_Load'(x, x1) -> f131_0_loop_LT(x2, x3) :|: -1 <= x4 - 1 && 1 <= x1 - 1 && x5 - 2 * x6 = 0 && -1 <= x5 - 1 && 0 <= x - 1 && x5 - 2 * x6 <= 1 && 0 <= x5 - 2 * x6 && 0 - x4 = x2 (3) f1_0_main_Load(x7, x8) -> f1_0_main_Load'(x9, x10) :|: -1 <= x11 - 1 && 1 <= x8 - 1 && x12 - 2 * x13 = 1 && -1 <= x12 - 1 && 0 <= x7 - 1 && x7 = x9 && x8 = x10 (4) f1_0_main_Load'(x17, x18) -> f130_0_loop_GT(x22, x23) :|: -1 <= x22 - 1 && 1 <= x18 - 1 && x27 - 2 * x28 = 1 && -1 <= x27 - 1 && 0 <= x17 - 1 && x27 - 2 * x28 <= 1 && 0 <= x27 - 2 * x28 (5) f130_0_loop_GT(x29, x32) -> f163_0_loop_GE(x33, x34) :|: 0 = x33 && 0 = x29 (6) f130_0_loop_GT(x35, x36) -> f163_0_loop_GE(x37, x38) :|: x35 - 1 = x37 && x35 <= 5 && 0 <= x35 - 1 (7) f131_0_loop_LT(x39, x40) -> f163_0_loop_GE(x41, x42) :|: x39 = x41 && -6 <= x39 - 1 && x39 <= 5 && x39 <= 0 (8) f163_0_loop_GE(x43, x44) -> f130_0_loop_GT(x45, x46) :|: x43 = x45 && -1 <= x43 - 1 (9) f163_0_loop_GE(x47, x48) -> f131_0_loop_LT(x49, x50) :|: x47 + 1 = x49 && x47 <= -1 (10) __init(x51, x52) -> f1_0_main_Load(x53, x54) :|: 0 <= 0 Arcs: (1) -> (2), (4) (2) -> (7) (3) -> (2), (4) (4) -> (5), (6) (5) -> (8) (6) -> (8) (7) -> (8), (9) (8) -> (5), (6) (9) -> (7) (10) -> (1), (3) This digraph is fully evaluated! ---------------------------------------- (4) Complex Obligation (AND) ---------------------------------------- (5) Obligation: Termination digraph: Nodes: (1) f131_0_loop_LT(x39, x40) -> f163_0_loop_GE(x41, x42) :|: x39 = x41 && -6 <= x39 - 1 && x39 <= 5 && x39 <= 0 (2) f163_0_loop_GE(x47, x48) -> f131_0_loop_LT(x49, x50) :|: x47 + 1 = x49 && x47 <= -1 Arcs: (1) -> (2) (2) -> (1) This digraph is fully evaluated! ---------------------------------------- (6) IntTRSCompressionProof (EQUIVALENT) Compressed rules. ---------------------------------------- (7) Obligation: Rules: f131_0_loop_LT(x39:0, x40:0) -> f131_0_loop_LT(x39:0 + 1, x50:0) :|: x39:0 < 0 && x39:0 < 1 && x39:0 > -6 && x39:0 < 6 ---------------------------------------- (8) IntTRSUnneededArgumentFilterProof (EQUIVALENT) Some arguments are removed because they cannot influence termination. We removed arguments according to the following replacements: f131_0_loop_LT(x1, x2) -> f131_0_loop_LT(x1) ---------------------------------------- (9) Obligation: Rules: f131_0_loop_LT(x39:0) -> f131_0_loop_LT(x39:0 + 1) :|: x39:0 < 0 && x39:0 < 1 && x39:0 > -6 && x39:0 < 6 ---------------------------------------- (10) TempFilterProof (SOUND) Used the following sort dictionary for filtering: f131_0_loop_LT(INTEGER) Replaced non-predefined constructor symbols by 0. ---------------------------------------- (11) Obligation: Rules: f131_0_loop_LT(x39:0) -> f131_0_loop_LT(c) :|: c = x39:0 + 1 && (x39:0 < 0 && x39:0 < 1 && x39:0 > -6 && x39:0 < 6) ---------------------------------------- (12) RankingReductionPairProof (EQUIVALENT) Interpretation: [ f131_0_loop_LT ] = -1*f131_0_loop_LT_1 The following rules are decreasing: f131_0_loop_LT(x39:0) -> f131_0_loop_LT(c) :|: c = x39:0 + 1 && (x39:0 < 0 && x39:0 < 1 && x39:0 > -6 && x39:0 < 6) The following rules are bounded: f131_0_loop_LT(x39:0) -> f131_0_loop_LT(c) :|: c = x39:0 + 1 && (x39:0 < 0 && x39:0 < 1 && x39:0 > -6 && x39:0 < 6) ---------------------------------------- (13) YES ---------------------------------------- (14) Obligation: Termination digraph: Nodes: (1) f163_0_loop_GE(x43, x44) -> f130_0_loop_GT(x45, x46) :|: x43 = x45 && -1 <= x43 - 1 (2) f130_0_loop_GT(x35, x36) -> f163_0_loop_GE(x37, x38) :|: x35 - 1 = x37 && x35 <= 5 && 0 <= x35 - 1 (3) f130_0_loop_GT(x29, x32) -> f163_0_loop_GE(x33, x34) :|: 0 = x33 && 0 = x29 Arcs: (1) -> (2), (3) (2) -> (1) (3) -> (1) This digraph is fully evaluated! ---------------------------------------- (15) IntTRSCompressionProof (EQUIVALENT) Compressed rules. ---------------------------------------- (16) Obligation: Rules: f163_0_loop_GE(cons_0, x44:0) -> f163_0_loop_GE(0, x34:0) :|: TRUE && cons_0 = 0 f163_0_loop_GE(x, x1) -> f163_0_loop_GE(x - 1, x2) :|: x < 6 && x > 0 ---------------------------------------- (17) IntTRSUnneededArgumentFilterProof (EQUIVALENT) Some arguments are removed because they cannot influence termination. We removed arguments according to the following replacements: f163_0_loop_GE(x1, x2) -> f163_0_loop_GE(x1) ---------------------------------------- (18) Obligation: Rules: f163_0_loop_GE(cons_0) -> f163_0_loop_GE(0) :|: TRUE && cons_0 = 0 f163_0_loop_GE(x) -> f163_0_loop_GE(x - 1) :|: x < 6 && x > 0 ---------------------------------------- (19) TempFilterProof (SOUND) Used the following sort dictionary for filtering: f163_0_loop_GE(VARIABLE) 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 - PolynomialOrderProcessor Rules: f163_0_loop_GE(c) -> f163_0_loop_GE(c1) :|: c1 = 0 && c = 0 && (TRUE && cons_0 = 0) f163_0_loop_GE(x) -> f163_0_loop_GE(c2) :|: c2 = x - 1 && (x < 6 && x > 0) Found the following polynomial interpretation: [f163_0_loop_GE(x)] = -1 + x The following rules are decreasing: f163_0_loop_GE(x) -> f163_0_loop_GE(c2) :|: c2 = x - 1 && (x < 6 && x > 0) The following rules are bounded: f163_0_loop_GE(x) -> f163_0_loop_GE(c2) :|: c2 = x - 1 && (x < 6 && x > 0) - IntTRS - PolynomialOrderProcessor - IntTRS Rules: f163_0_loop_GE(c) -> f163_0_loop_GE(c1) :|: c1 = 0 && c = 0 && (TRUE && cons_0 = 0) ---------------------------------------- (20) Obligation: Rules: f163_0_loop_GE(cons_0) -> f163_0_loop_GE(0) :|: TRUE && cons_0 = 0 ---------------------------------------- (21) IRSwTTerminationDigraphProof (EQUIVALENT) Constructed termination digraph! Nodes: (1) f163_0_loop_GE(cons_0) -> f163_0_loop_GE(0) :|: TRUE && cons_0 = 0 Arcs: (1) -> (1) This digraph is fully evaluated! ---------------------------------------- (22) Obligation: Termination digraph: Nodes: (1) f163_0_loop_GE(cons_0) -> f163_0_loop_GE(0) :|: TRUE && cons_0 = 0 Arcs: (1) -> (1) This digraph is fully evaluated! ---------------------------------------- (23) IntTRSCompressionProof (EQUIVALENT) Compressed rules. ---------------------------------------- (24) Obligation: Rules: f163_0_loop_GE(cons_0) -> f163_0_loop_GE(0) :|: TRUE && cons_0 = 0