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, 155 ms] (4) IRSwT (5) IntTRSCompressionProof [EQUIVALENT, 36 ms] (6) IRSwT (7) IRSwTChainingProof [EQUIVALENT, 0 ms] (8) IRSwT (9) IRSwTTerminationDigraphProof [EQUIVALENT, 10 ms] (10) IRSwT (11) IntTRSCompressionProof [EQUIVALENT, 0 ms] (12) IRSwT (13) IRSwTChainingProof [EQUIVALENT, 0 ms] (14) IRSwT (15) IRSwTTerminationDigraphProof [EQUIVALENT, 77 ms] (16) IRSwT (17) IntTRSCompressionProof [EQUIVALENT, 0 ms] (18) IRSwT (19) TempFilterProof [SOUND, 432 ms] (20) IRSwT (21) IRSwTTerminationDigraphProof [EQUIVALENT, 18 ms] (22) IRSwT (23) IntTRSCompressionProof [EQUIVALENT, 0 ms] (24) IRSwT ---------------------------------------- (0) Obligation: Rules: f1_0_main_Load(arg1, arg2) -> f162_0_main_LT(arg1P, arg2P) :|: 0 <= arg1 - 1 && -1 <= arg1P - 1 && 1 <= arg2 - 1 && -1 <= arg2P - 1 f162_0_main_LT(x, x1) -> f162_0_main_LT(x2, x3) :|: x1 = x3 && x - 1 = x2 && 0 <= x - x1 - 1 && x1 <= x && -1 <= x1 - 1 && -1 <= x - 1 f162_0_main_LT(x4, x5) -> f162_0_main_LT(x6, x7) :|: x5 + 1 = x7 && 2 * x4 + 1 = x6 && 0 <= 2 * x4 && x4 - x5 = 0 && x5 <= x4 && -1 <= x5 - 1 && -1 <= x4 - 1 __init(x8, x9) -> f1_0_main_Load(x10, x11) :|: 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) -> f162_0_main_LT(arg1P, arg2P) :|: 0 <= arg1 - 1 && -1 <= arg1P - 1 && 1 <= arg2 - 1 && -1 <= arg2P - 1 f162_0_main_LT(x, x1) -> f162_0_main_LT(x2, x3) :|: x1 = x3 && x - 1 = x2 && 0 <= x - x1 - 1 && x1 <= x && -1 <= x1 - 1 && -1 <= x - 1 f162_0_main_LT(x4, x5) -> f162_0_main_LT(x6, x7) :|: x5 + 1 = x7 && 2 * x4 + 1 = x6 && 0 <= 2 * x4 && x4 - x5 = 0 && x5 <= x4 && -1 <= x5 - 1 && -1 <= x4 - 1 __init(x8, x9) -> f1_0_main_Load(x10, x11) :|: 0 <= 0 Start term: __init(arg1, arg2) ---------------------------------------- (3) IRSwTTerminationDigraphProof (EQUIVALENT) Constructed termination digraph! Nodes: (1) f1_0_main_Load(arg1, arg2) -> f162_0_main_LT(arg1P, arg2P) :|: 0 <= arg1 - 1 && -1 <= arg1P - 1 && 1 <= arg2 - 1 && -1 <= arg2P - 1 (2) f162_0_main_LT(x, x1) -> f162_0_main_LT(x2, x3) :|: x1 = x3 && x - 1 = x2 && 0 <= x - x1 - 1 && x1 <= x && -1 <= x1 - 1 && -1 <= x - 1 (3) f162_0_main_LT(x4, x5) -> f162_0_main_LT(x6, x7) :|: x5 + 1 = x7 && 2 * x4 + 1 = x6 && 0 <= 2 * x4 && x4 - x5 = 0 && x5 <= x4 && -1 <= x5 - 1 && -1 <= x4 - 1 (4) __init(x8, x9) -> f1_0_main_Load(x10, x11) :|: 0 <= 0 Arcs: (1) -> (2), (3) (2) -> (2), (3) (3) -> (2), (3) (4) -> (1) This digraph is fully evaluated! ---------------------------------------- (4) Obligation: Termination digraph: Nodes: (1) f162_0_main_LT(x, x1) -> f162_0_main_LT(x2, x3) :|: x1 = x3 && x - 1 = x2 && 0 <= x - x1 - 1 && x1 <= x && -1 <= x1 - 1 && -1 <= x - 1 (2) f162_0_main_LT(x4, x5) -> f162_0_main_LT(x6, x7) :|: x5 + 1 = x7 && 2 * x4 + 1 = x6 && 0 <= 2 * x4 && x4 - x5 = 0 && x5 <= x4 && -1 <= x5 - 1 && -1 <= x4 - 1 Arcs: (1) -> (1), (2) (2) -> (1), (2) This digraph is fully evaluated! ---------------------------------------- (5) IntTRSCompressionProof (EQUIVALENT) Compressed rules. ---------------------------------------- (6) Obligation: Rules: f162_0_main_LT(x:0, x1:0) -> f162_0_main_LT(x:0 - 1, x1:0) :|: x1:0 > -1 && x:0 > -1 && x:0 - x1:0 >= 1 && x:0 >= x1:0 f162_0_main_LT(x4:0, x5:0) -> f162_0_main_LT(2 * x4:0 + 1, x5:0 + 1) :|: x5:0 > -1 && x4:0 > -1 && x5:0 <= x4:0 && 2 * x4:0 >= 0 && x4:0 - x5:0 = 0 ---------------------------------------- (7) IRSwTChainingProof (EQUIVALENT) Chaining! ---------------------------------------- (8) Obligation: Rules: f162_0_main_LT(x, x1) -> f162_0_main_LT(x + -2, x1) :|: TRUE && x1 >= 0 && x >= 1 && x + -1 * x1 >= 2 f162_0_main_LT(x4:0, x5:0) -> f162_0_main_LT(2 * x4:0 + 1, x5:0 + 1) :|: x5:0 > -1 && x4:0 > -1 && x5:0 <= x4:0 && 2 * x4:0 >= 0 && x4:0 - x5:0 = 0 f162_0_main_LT(x4, x5) -> f162_0_main_LT(2 * x4 + -1, x5 + 1) :|: TRUE && x5 >= 0 && x4 >= 1 && x4 + -1 * x5 = 1 ---------------------------------------- (9) IRSwTTerminationDigraphProof (EQUIVALENT) Constructed termination digraph! Nodes: (1) f162_0_main_LT(x, x1) -> f162_0_main_LT(x + -2, x1) :|: TRUE && x1 >= 0 && x >= 1 && x + -1 * x1 >= 2 (2) f162_0_main_LT(x4:0, x5:0) -> f162_0_main_LT(2 * x4:0 + 1, x5:0 + 1) :|: x5:0 > -1 && x4:0 > -1 && x5:0 <= x4:0 && 2 * x4:0 >= 0 && x4:0 - x5:0 = 0 (3) f162_0_main_LT(x4, x5) -> f162_0_main_LT(2 * x4 + -1, x5 + 1) :|: TRUE && x5 >= 0 && x4 >= 1 && x4 + -1 * x5 = 1 Arcs: (1) -> (1), (2), (3) (2) -> (1), (2), (3) (3) -> (1), (2), (3) This digraph is fully evaluated! ---------------------------------------- (10) Obligation: Termination digraph: Nodes: (1) f162_0_main_LT(x, x1) -> f162_0_main_LT(x + -2, x1) :|: TRUE && x1 >= 0 && x >= 1 && x + -1 * x1 >= 2 (2) f162_0_main_LT(x4:0, x5:0) -> f162_0_main_LT(2 * x4:0 + 1, x5:0 + 1) :|: x5:0 > -1 && x4:0 > -1 && x5:0 <= x4:0 && 2 * x4:0 >= 0 && x4:0 - x5:0 = 0 (3) f162_0_main_LT(x4, x5) -> f162_0_main_LT(2 * x4 + -1, x5 + 1) :|: TRUE && x5 >= 0 && x4 >= 1 && x4 + -1 * x5 = 1 Arcs: (1) -> (1), (2), (3) (2) -> (1), (2), (3) (3) -> (1), (2), (3) This digraph is fully evaluated! ---------------------------------------- (11) IntTRSCompressionProof (EQUIVALENT) Compressed rules. ---------------------------------------- (12) Obligation: Rules: f162_0_main_LT(x4:0:0, x5:0:0) -> f162_0_main_LT(2 * x4:0:0 + 1, x5:0:0 + 1) :|: 2 * x4:0:0 >= 0 && x4:0:0 - x5:0:0 = 0 && x5:0:0 <= x4:0:0 && x4:0:0 > -1 && x5:0:0 > -1 f162_0_main_LT(x4:0, x5:0) -> f162_0_main_LT(2 * x4:0 - 1, x5:0 + 1) :|: x4:0 > 0 && x5:0 > -1 && x4:0 + -1 * x5:0 = 1 f162_0_main_LT(x:0, x1:0) -> f162_0_main_LT(x:0 - 2, x1:0) :|: x:0 > 0 && x1:0 > -1 && x:0 + -1 * x1:0 >= 2 ---------------------------------------- (13) IRSwTChainingProof (EQUIVALENT) Chaining! ---------------------------------------- (14) Obligation: Rules: f162_0_main_LT(x, x1) -> f162_0_main_LT(4 * x + 3, x1 + 2) :|: TRUE && x >= 0 && x + -1 * x1 = 0 && x1 >= 0 && 2 * x + -1 * x1 = 0 f162_0_main_LT(x4:0, x5:0) -> f162_0_main_LT(2 * x4:0 - 1, x5:0 + 1) :|: x4:0 > 0 && x5:0 > -1 && x4:0 + -1 * x5:0 = 1 f162_0_main_LT(x4, x5) -> f162_0_main_LT(4 * x4 + 1, x5 + 2) :|: TRUE && x4 >= 0 && x4 + -1 * x5 = 0 && x5 >= 0 && 2 * x4 + -1 * x5 = 1 f162_0_main_LT(x:0, x1:0) -> f162_0_main_LT(x:0 - 2, x1:0) :|: x:0 > 0 && x1:0 > -1 && x:0 + -1 * x1:0 >= 2 f162_0_main_LT(x8, x9) -> f162_0_main_LT(2 * x8 + -1, x9 + 1) :|: TRUE && x8 >= 0 && x8 + -1 * x9 = 0 && x9 >= 0 && 2 * x8 + -1 * x9 >= 2 ---------------------------------------- (15) IRSwTTerminationDigraphProof (EQUIVALENT) Constructed termination digraph! Nodes: (1) f162_0_main_LT(x, x1) -> f162_0_main_LT(4 * x + 3, x1 + 2) :|: TRUE && x >= 0 && x + -1 * x1 = 0 && x1 >= 0 && 2 * x + -1 * x1 = 0 (2) f162_0_main_LT(x4:0, x5:0) -> f162_0_main_LT(2 * x4:0 - 1, x5:0 + 1) :|: x4:0 > 0 && x5:0 > -1 && x4:0 + -1 * x5:0 = 1 (3) f162_0_main_LT(x4, x5) -> f162_0_main_LT(4 * x4 + 1, x5 + 2) :|: TRUE && x4 >= 0 && x4 + -1 * x5 = 0 && x5 >= 0 && 2 * x4 + -1 * x5 = 1 (4) f162_0_main_LT(x:0, x1:0) -> f162_0_main_LT(x:0 - 2, x1:0) :|: x:0 > 0 && x1:0 > -1 && x:0 + -1 * x1:0 >= 2 (5) f162_0_main_LT(x8, x9) -> f162_0_main_LT(2 * x8 + -1, x9 + 1) :|: TRUE && x8 >= 0 && x8 + -1 * x9 = 0 && x9 >= 0 && 2 * x8 + -1 * x9 >= 2 Arcs: (1) -> (2) (2) -> (2), (3), (4) (3) -> (4) (4) -> (1), (2), (3), (4), (5) (5) -> (2), (4), (5) This digraph is fully evaluated! ---------------------------------------- (16) Obligation: Termination digraph: Nodes: (1) f162_0_main_LT(x, x1) -> f162_0_main_LT(4 * x + 3, x1 + 2) :|: TRUE && x >= 0 && x + -1 * x1 = 0 && x1 >= 0 && 2 * x + -1 * x1 = 0 (2) f162_0_main_LT(x:0, x1:0) -> f162_0_main_LT(x:0 - 2, x1:0) :|: x:0 > 0 && x1:0 > -1 && x:0 + -1 * x1:0 >= 2 (3) f162_0_main_LT(x4, x5) -> f162_0_main_LT(4 * x4 + 1, x5 + 2) :|: TRUE && x4 >= 0 && x4 + -1 * x5 = 0 && x5 >= 0 && 2 * x4 + -1 * x5 = 1 (4) f162_0_main_LT(x4:0, x5:0) -> f162_0_main_LT(2 * x4:0 - 1, x5:0 + 1) :|: x4:0 > 0 && x5:0 > -1 && x4:0 + -1 * x5:0 = 1 (5) f162_0_main_LT(x8, x9) -> f162_0_main_LT(2 * x8 + -1, x9 + 1) :|: TRUE && x8 >= 0 && x8 + -1 * x9 = 0 && x9 >= 0 && 2 * x8 + -1 * x9 >= 2 Arcs: (1) -> (4) (2) -> (1), (2), (3), (4), (5) (3) -> (2) (4) -> (2), (3), (4) (5) -> (2), (4), (5) This digraph is fully evaluated! ---------------------------------------- (17) IntTRSCompressionProof (EQUIVALENT) Compressed rules. ---------------------------------------- (18) Obligation: Rules: f162_0_main_LT(x4:0, x5:0) -> f162_0_main_LT(4 * x4:0 + 1, x5:0 + 2) :|: x5:0 > -1 && 2 * x4:0 + -1 * x5:0 = 1 && x4:0 > -1 && x4:0 + -1 * x5:0 = 0 f162_0_main_LT(x:0:0, x1:0:0) -> f162_0_main_LT(x:0:0 - 2, x1:0:0) :|: x:0:0 > 0 && x1:0:0 > -1 && x:0:0 + -1 * x1:0:0 >= 2 f162_0_main_LT(x8:0, x9:0) -> f162_0_main_LT(2 * x8:0 - 1, x9:0 + 1) :|: x9:0 > -1 && 2 * x8:0 + -1 * x9:0 >= 2 && x8:0 > -1 && x8:0 + -1 * x9:0 = 0 f162_0_main_LT(x:0, x1:0) -> f162_0_main_LT(4 * x:0 + 3, x1:0 + 2) :|: x1:0 > -1 && 2 * x:0 + -1 * x1:0 = 0 && x:0 > -1 && x:0 + -1 * x1:0 = 0 f162_0_main_LT(x4:0:0, x5:0:0) -> f162_0_main_LT(2 * x4:0:0 - 1, x5:0:0 + 1) :|: x4:0:0 > 0 && x5:0:0 > -1 && x4:0:0 + -1 * x5:0:0 = 1 ---------------------------------------- (19) TempFilterProof (SOUND) Used the following sort dictionary for filtering: f162_0_main_LT(INTEGER, 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: f162_0_main_LT(x4:0, x5:0) -> f162_0_main_LT(c, c1) :|: c1 = x5:0 + 2 && c = 4 * x4:0 + 1 && (x5:0 > -1 && 2 * x4:0 + -1 * x5:0 = 1 && x4:0 > -1 && x4:0 + -1 * x5:0 = 0) f162_0_main_LT(x:0:0, x1:0:0) -> f162_0_main_LT(c2, x1:0:0) :|: c2 = x:0:0 - 2 && (x:0:0 > 0 && x1:0:0 > -1 && x:0:0 + -1 * x1:0:0 >= 2) f162_0_main_LT(x8:0, x9:0) -> f162_0_main_LT(c3, c4) :|: c4 = x9:0 + 1 && c3 = 2 * x8:0 - 1 && (x9:0 > -1 && 2 * x8:0 + -1 * x9:0 >= 2 && x8:0 > -1 && x8:0 + -1 * x9:0 = 0) f162_0_main_LT(x:0, x1:0) -> f162_0_main_LT(c5, c6) :|: c6 = x1:0 + 2 && c5 = 4 * x:0 + 3 && (x1:0 > -1 && 2 * x:0 + -1 * x1:0 = 0 && x:0 > -1 && x:0 + -1 * x1:0 = 0) f162_0_main_LT(x4:0:0, x5:0:0) -> f162_0_main_LT(c7, c8) :|: c8 = x5:0:0 + 1 && c7 = 2 * x4:0:0 - 1 && (x4:0:0 > 0 && x5:0:0 > -1 && x4:0:0 + -1 * x5:0:0 = 1) Interpretation: [ f162_0_main_LT ] = -7*f162_0_main_LT_2 The following rules are decreasing: f162_0_main_LT(x4:0, x5:0) -> f162_0_main_LT(c, c1) :|: c1 = x5:0 + 2 && c = 4 * x4:0 + 1 && (x5:0 > -1 && 2 * x4:0 + -1 * x5:0 = 1 && x4:0 > -1 && x4:0 + -1 * x5:0 = 0) f162_0_main_LT(x8:0, x9:0) -> f162_0_main_LT(c3, c4) :|: c4 = x9:0 + 1 && c3 = 2 * x8:0 - 1 && (x9:0 > -1 && 2 * x8:0 + -1 * x9:0 >= 2 && x8:0 > -1 && x8:0 + -1 * x9:0 = 0) f162_0_main_LT(x:0, x1:0) -> f162_0_main_LT(c5, c6) :|: c6 = x1:0 + 2 && c5 = 4 * x:0 + 3 && (x1:0 > -1 && 2 * x:0 + -1 * x1:0 = 0 && x:0 > -1 && x:0 + -1 * x1:0 = 0) f162_0_main_LT(x4:0:0, x5:0:0) -> f162_0_main_LT(c7, c8) :|: c8 = x5:0:0 + 1 && c7 = 2 * x4:0:0 - 1 && (x4:0:0 > 0 && x5:0:0 > -1 && x4:0:0 + -1 * x5:0:0 = 1) The following rules are bounded: f162_0_main_LT(x4:0, x5:0) -> f162_0_main_LT(c, c1) :|: c1 = x5:0 + 2 && c = 4 * x4:0 + 1 && (x5:0 > -1 && 2 * x4:0 + -1 * x5:0 = 1 && x4:0 > -1 && x4:0 + -1 * x5:0 = 0) f162_0_main_LT(x:0, x1:0) -> f162_0_main_LT(c5, c6) :|: c6 = x1:0 + 2 && c5 = 4 * x:0 + 3 && (x1:0 > -1 && 2 * x:0 + -1 * x1:0 = 0 && x:0 > -1 && x:0 + -1 * x1:0 = 0) - IntTRS - RankingReductionPairProof - IntTRS Rules: f162_0_main_LT(x:0:0, x1:0:0) -> f162_0_main_LT(c2, x1:0:0) :|: c2 = x:0:0 - 2 && (x:0:0 > 0 && x1:0:0 > -1 && x:0:0 + -1 * x1:0:0 >= 2) f162_0_main_LT(x8:0, x9:0) -> f162_0_main_LT(c3, c4) :|: c4 = x9:0 + 1 && c3 = 2 * x8:0 - 1 && (x9:0 > -1 && 2 * x8:0 + -1 * x9:0 >= 2 && x8:0 > -1 && x8:0 + -1 * x9:0 = 0) f162_0_main_LT(x4:0:0, x5:0:0) -> f162_0_main_LT(c7, c8) :|: c8 = x5:0:0 + 1 && c7 = 2 * x4:0:0 - 1 && (x4:0:0 > 0 && x5:0:0 > -1 && x4:0:0 + -1 * x5:0:0 = 1) ---------------------------------------- (20) Obligation: Rules: f162_0_main_LT(x:0:0, x1:0:0) -> f162_0_main_LT(x:0:0 - 2, x1:0:0) :|: x:0:0 > 0 && x1:0:0 > -1 && x:0:0 + -1 * x1:0:0 >= 2 f162_0_main_LT(x8:0, x9:0) -> f162_0_main_LT(2 * x8:0 - 1, x9:0 + 1) :|: x9:0 > -1 && 2 * x8:0 + -1 * x9:0 >= 2 && x8:0 > -1 && x8:0 + -1 * x9:0 = 0 f162_0_main_LT(x4:0:0, x5:0:0) -> f162_0_main_LT(2 * x4:0:0 - 1, x5:0:0 + 1) :|: x4:0:0 > 0 && x5:0:0 > -1 && x4:0:0 + -1 * x5:0:0 = 1 ---------------------------------------- (21) IRSwTTerminationDigraphProof (EQUIVALENT) Constructed termination digraph! Nodes: (1) f162_0_main_LT(x:0:0, x1:0:0) -> f162_0_main_LT(x:0:0 - 2, x1:0:0) :|: x:0:0 > 0 && x1:0:0 > -1 && x:0:0 + -1 * x1:0:0 >= 2 (2) f162_0_main_LT(x8:0, x9:0) -> f162_0_main_LT(2 * x8:0 - 1, x9:0 + 1) :|: x9:0 > -1 && 2 * x8:0 + -1 * x9:0 >= 2 && x8:0 > -1 && x8:0 + -1 * x9:0 = 0 (3) f162_0_main_LT(x4:0:0, x5:0:0) -> f162_0_main_LT(2 * x4:0:0 - 1, x5:0:0 + 1) :|: x4:0:0 > 0 && x5:0:0 > -1 && x4:0:0 + -1 * x5:0:0 = 1 Arcs: (1) -> (1), (2), (3) (2) -> (1), (2), (3) (3) -> (1), (3) This digraph is fully evaluated! ---------------------------------------- (22) Obligation: Termination digraph: Nodes: (1) f162_0_main_LT(x:0:0, x1:0:0) -> f162_0_main_LT(x:0:0 - 2, x1:0:0) :|: x:0:0 > 0 && x1:0:0 > -1 && x:0:0 + -1 * x1:0:0 >= 2 (2) f162_0_main_LT(x4:0:0, x5:0:0) -> f162_0_main_LT(2 * x4:0:0 - 1, x5:0:0 + 1) :|: x4:0:0 > 0 && x5:0:0 > -1 && x4:0:0 + -1 * x5:0:0 = 1 (3) f162_0_main_LT(x8:0, x9:0) -> f162_0_main_LT(2 * x8:0 - 1, x9:0 + 1) :|: x9:0 > -1 && 2 * x8:0 + -1 * x9:0 >= 2 && x8:0 > -1 && x8:0 + -1 * x9:0 = 0 Arcs: (1) -> (1), (2), (3) (2) -> (1), (2) (3) -> (1), (2), (3) This digraph is fully evaluated! ---------------------------------------- (23) IntTRSCompressionProof (EQUIVALENT) Compressed rules. ---------------------------------------- (24) Obligation: Rules: f162_0_main_LT(x:0:0:0, x1:0:0:0) -> f162_0_main_LT(x:0:0:0 - 2, x1:0:0:0) :|: x:0:0:0 > 0 && x1:0:0:0 > -1 && x:0:0:0 + -1 * x1:0:0:0 >= 2 f162_0_main_LT(x4:0:0:0, x5:0:0:0) -> f162_0_main_LT(2 * x4:0:0:0 - 1, x5:0:0:0 + 1) :|: x4:0:0:0 > 0 && x5:0:0:0 > -1 && x4:0:0:0 + -1 * x5:0:0:0 = 1 f162_0_main_LT(x8:0:0, x9:0:0) -> f162_0_main_LT(2 * x8:0:0 - 1, x9:0:0 + 1) :|: x8:0:0 > -1 && x8:0:0 + -1 * x9:0:0 = 0 && 2 * x8:0:0 + -1 * x9:0:0 >= 2 && x9:0:0 > -1