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, 151 ms] (4) IRSwT (5) IntTRSCompressionProof [EQUIVALENT, 37 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, 10 ms] (16) IRSwT (17) IntTRSCompressionProof [EQUIVALENT, 0 ms] (18) IRSwT (19) IRSwTChainingProof [EQUIVALENT, 0 ms] (20) IRSwT (21) IRSwTTerminationDigraphProof [EQUIVALENT, 28 ms] (22) IRSwT (23) IntTRSCompressionProof [EQUIVALENT, 0 ms] (24) IRSwT (25) TempFilterProof [SOUND, 960 ms] (26) IRSwT (27) IRSwTTerminationDigraphProof [EQUIVALENT, 11 ms] (28) IRSwT (29) IntTRSCompressionProof [EQUIVALENT, 0 ms] (30) IRSwT ---------------------------------------- (0) Obligation: Rules: f1_0_main_Load(arg1, arg2, arg3) -> f104_0_main_LE(arg1P, arg2P, arg3P) :|: -1 <= x2 - 1 && 1 <= arg2 - 1 && -1 <= x3 - 1 && 0 <= arg1 - 1 && x2 - x3 = arg1P f104_0_main_LE(x, x1, x4) -> f157_0_main_LE(x5, x6, x7) :|: x + 1 = x7 && x + 1 = x6 && x + 1 = x5 && 0 <= x - 1 f157_0_main_LE(x8, x9, x10) -> f104_0_main_LE(x11, x12, x13) :|: x8 = x11 && 0 = x10 && 0 = x9 f157_0_main_LE(x14, x15, x16) -> f157_0_main_LE(x17, x18, x19) :|: x15 - 1 = x19 && x15 - 1 = x18 && x14 = x17 && x15 = x16 && 0 <= x15 - 1 __init(x20, x21, x22) -> f1_0_main_Load(x23, x24, x25) :|: 0 <= 0 Start term: __init(arg1, arg2, arg3) ---------------------------------------- (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, arg3) -> f104_0_main_LE(arg1P, arg2P, arg3P) :|: -1 <= x2 - 1 && 1 <= arg2 - 1 && -1 <= x3 - 1 && 0 <= arg1 - 1 && x2 - x3 = arg1P f104_0_main_LE(x, x1, x4) -> f157_0_main_LE(x5, x6, x7) :|: x + 1 = x7 && x + 1 = x6 && x + 1 = x5 && 0 <= x - 1 f157_0_main_LE(x8, x9, x10) -> f104_0_main_LE(x11, x12, x13) :|: x8 = x11 && 0 = x10 && 0 = x9 f157_0_main_LE(x14, x15, x16) -> f157_0_main_LE(x17, x18, x19) :|: x15 - 1 = x19 && x15 - 1 = x18 && x14 = x17 && x15 = x16 && 0 <= x15 - 1 __init(x20, x21, x22) -> f1_0_main_Load(x23, x24, x25) :|: 0 <= 0 Start term: __init(arg1, arg2, arg3) ---------------------------------------- (3) IRSwTTerminationDigraphProof (EQUIVALENT) Constructed termination digraph! Nodes: (1) f1_0_main_Load(arg1, arg2, arg3) -> f104_0_main_LE(arg1P, arg2P, arg3P) :|: -1 <= x2 - 1 && 1 <= arg2 - 1 && -1 <= x3 - 1 && 0 <= arg1 - 1 && x2 - x3 = arg1P (2) f104_0_main_LE(x, x1, x4) -> f157_0_main_LE(x5, x6, x7) :|: x + 1 = x7 && x + 1 = x6 && x + 1 = x5 && 0 <= x - 1 (3) f157_0_main_LE(x8, x9, x10) -> f104_0_main_LE(x11, x12, x13) :|: x8 = x11 && 0 = x10 && 0 = x9 (4) f157_0_main_LE(x14, x15, x16) -> f157_0_main_LE(x17, x18, x19) :|: x15 - 1 = x19 && x15 - 1 = x18 && x14 = x17 && x15 = x16 && 0 <= x15 - 1 (5) __init(x20, x21, x22) -> f1_0_main_Load(x23, x24, x25) :|: 0 <= 0 Arcs: (1) -> (2) (2) -> (4) (3) -> (2) (4) -> (3), (4) (5) -> (1) This digraph is fully evaluated! ---------------------------------------- (4) Obligation: Termination digraph: Nodes: (1) f104_0_main_LE(x, x1, x4) -> f157_0_main_LE(x5, x6, x7) :|: x + 1 = x7 && x + 1 = x6 && x + 1 = x5 && 0 <= x - 1 (2) f157_0_main_LE(x8, x9, x10) -> f104_0_main_LE(x11, x12, x13) :|: x8 = x11 && 0 = x10 && 0 = x9 (3) f157_0_main_LE(x14, x15, x16) -> f157_0_main_LE(x17, x18, x19) :|: x15 - 1 = x19 && x15 - 1 = x18 && x14 = x17 && x15 = x16 && 0 <= x15 - 1 Arcs: (1) -> (3) (2) -> (1) (3) -> (2), (3) This digraph is fully evaluated! ---------------------------------------- (5) IntTRSCompressionProof (EQUIVALENT) Compressed rules. ---------------------------------------- (6) Obligation: Rules: f157_0_main_LE(x11:0, cons_0, cons_01) -> f157_0_main_LE(x11:0 + 1, x11:0 + 1, x11:0 + 1) :|: x11:0 > 0 && cons_0 = 0 && cons_01 = 0 f157_0_main_LE(x14:0, x15:0, x15:0) -> f157_0_main_LE(x14:0, x15:0 - 1, x15:0 - 1) :|: x15:0 > 0 ---------------------------------------- (7) IRSwTChainingProof (EQUIVALENT) Chaining! ---------------------------------------- (8) Obligation: Rules: f157_0_main_LE(x14:0, x15:0, x15:0) -> f157_0_main_LE(x14:0, x15:0 - 1, x15:0 - 1) :|: x15:0 > 0 f157_0_main_LE(x6, x7, x8) -> f157_0_main_LE(x6 + 1, x6, x6) :|: TRUE && x6 >= 1 && (x7 = 0 && x8 = 0) ---------------------------------------- (9) IRSwTTerminationDigraphProof (EQUIVALENT) Constructed termination digraph! Nodes: (1) f157_0_main_LE(x14:0, x15:0, x15:0) -> f157_0_main_LE(x14:0, x15:0 - 1, x15:0 - 1) :|: x15:0 > 0 (2) f157_0_main_LE(x6, x7, x8) -> f157_0_main_LE(x6 + 1, x6, x6) :|: TRUE && x6 >= 1 && (x7 = 0 && x8 = 0) Arcs: (1) -> (1), (2) (2) -> (1) This digraph is fully evaluated! ---------------------------------------- (10) Obligation: Termination digraph: Nodes: (1) f157_0_main_LE(x14:0, x15:0, x15:0) -> f157_0_main_LE(x14:0, x15:0 - 1, x15:0 - 1) :|: x15:0 > 0 (2) f157_0_main_LE(x6, x7, x8) -> f157_0_main_LE(x6 + 1, x6, x6) :|: TRUE && x6 >= 1 && (x7 = 0 && x8 = 0) Arcs: (1) -> (1), (2) (2) -> (1) This digraph is fully evaluated! ---------------------------------------- (11) IntTRSCompressionProof (EQUIVALENT) Compressed rules. ---------------------------------------- (12) Obligation: Rules: f157_0_main_LE(x14:0:0, x15:0:0, x15:0:0) -> f157_0_main_LE(x14:0:0, x15:0:0 - 1, x15:0:0 - 1) :|: x15:0:0 > 0 f157_0_main_LE(x6:0, cons_0, cons_01) -> f157_0_main_LE(x6:0 + 1, x6:0, x6:0) :|: x6:0 > 0 && cons_0 = 0 && cons_01 = 0 ---------------------------------------- (13) IRSwTChainingProof (EQUIVALENT) Chaining! ---------------------------------------- (14) Obligation: Rules: f157_0_main_LE(x, x1, x1) -> f157_0_main_LE(x, x1 + -2, x1 + -2) :|: TRUE && x1 >= 2 f157_0_main_LE(x6:0, cons_0, cons_01) -> f157_0_main_LE(x6:0 + 1, x6:0, x6:0) :|: x6:0 > 0 && cons_0 = 0 && cons_01 = 0 f157_0_main_LE(x4, x5, x5) -> f157_0_main_LE(x4 + 1, x4, x4) :|: TRUE && x4 >= 1 && x5 = 1 ---------------------------------------- (15) IRSwTTerminationDigraphProof (EQUIVALENT) Constructed termination digraph! Nodes: (1) f157_0_main_LE(x, x1, x1) -> f157_0_main_LE(x, x1 + -2, x1 + -2) :|: TRUE && x1 >= 2 (2) f157_0_main_LE(x6:0, cons_0, cons_01) -> f157_0_main_LE(x6:0 + 1, x6:0, x6:0) :|: x6:0 > 0 && cons_0 = 0 && cons_01 = 0 (3) f157_0_main_LE(x4, x5, x5) -> f157_0_main_LE(x4 + 1, x4, x4) :|: TRUE && x4 >= 1 && x5 = 1 Arcs: (1) -> (1), (2), (3) (2) -> (1), (3) (3) -> (1), (3) This digraph is fully evaluated! ---------------------------------------- (16) Obligation: Termination digraph: Nodes: (1) f157_0_main_LE(x, x1, x1) -> f157_0_main_LE(x, x1 + -2, x1 + -2) :|: TRUE && x1 >= 2 (2) f157_0_main_LE(x4, x5, x5) -> f157_0_main_LE(x4 + 1, x4, x4) :|: TRUE && x4 >= 1 && x5 = 1 (3) f157_0_main_LE(x6:0, cons_0, cons_01) -> f157_0_main_LE(x6:0 + 1, x6:0, x6:0) :|: x6:0 > 0 && cons_0 = 0 && cons_01 = 0 Arcs: (1) -> (1), (2), (3) (2) -> (1), (2) (3) -> (1), (2) This digraph is fully evaluated! ---------------------------------------- (17) IntTRSCompressionProof (EQUIVALENT) Compressed rules. ---------------------------------------- (18) Obligation: Rules: f157_0_main_LE(x6:0:0, cons_0, cons_01) -> f157_0_main_LE(x6:0:0 + 1, x6:0:0, x6:0:0) :|: x6:0:0 > 0 && cons_0 = 0 && cons_01 = 0 f157_0_main_LE(x:0, x1:0, x1:0) -> f157_0_main_LE(x:0, x1:0 - 2, x1:0 - 2) :|: x1:0 > 1 f157_0_main_LE(x4:0, cons_1, cons_11) -> f157_0_main_LE(x4:0 + 1, x4:0, x4:0) :|: x4:0 > 0 && cons_1 = 1 && cons_11 = 1 ---------------------------------------- (19) IRSwTChainingProof (EQUIVALENT) Chaining! ---------------------------------------- (20) Obligation: Rules: f157_0_main_LE(x:0, x1:0, x1:0) -> f157_0_main_LE(x:0, x1:0 - 2, x1:0 - 2) :|: x1:0 > 1 f157_0_main_LE(x6, x7, x8) -> f157_0_main_LE(x6 + 1, x6 + -2, x6 + -2) :|: TRUE && x6 >= 2 && (x7 = 0 && x8 = 0) f157_0_main_LE(x4:0, cons_1, cons_11) -> f157_0_main_LE(x4:0 + 1, x4:0, x4:0) :|: x4:0 > 0 && cons_1 = 1 && cons_11 = 1 f157_0_main_LE(x11, x12, x13) -> f157_0_main_LE(x11 + 2, x11 + 1, x11 + 1) :|: TRUE && x11 = 1 && (x12 = 0 && x13 = 0) ---------------------------------------- (21) IRSwTTerminationDigraphProof (EQUIVALENT) Constructed termination digraph! Nodes: (1) f157_0_main_LE(x:0, x1:0, x1:0) -> f157_0_main_LE(x:0, x1:0 - 2, x1:0 - 2) :|: x1:0 > 1 (2) f157_0_main_LE(x6, x7, x8) -> f157_0_main_LE(x6 + 1, x6 + -2, x6 + -2) :|: TRUE && x6 >= 2 && (x7 = 0 && x8 = 0) (3) f157_0_main_LE(x4:0, cons_1, cons_11) -> f157_0_main_LE(x4:0 + 1, x4:0, x4:0) :|: x4:0 > 0 && cons_1 = 1 && cons_11 = 1 (4) f157_0_main_LE(x11, x12, x13) -> f157_0_main_LE(x11 + 2, x11 + 1, x11 + 1) :|: TRUE && x11 = 1 && (x12 = 0 && x13 = 0) Arcs: (1) -> (1), (2), (3), (4) (2) -> (1), (2), (3) (3) -> (1), (3) (4) -> (1) This digraph is fully evaluated! ---------------------------------------- (22) Obligation: Termination digraph: Nodes: (1) f157_0_main_LE(x:0, x1:0, x1:0) -> f157_0_main_LE(x:0, x1:0 - 2, x1:0 - 2) :|: x1:0 > 1 (2) f157_0_main_LE(x11, x12, x13) -> f157_0_main_LE(x11 + 2, x11 + 1, x11 + 1) :|: TRUE && x11 = 1 && (x12 = 0 && x13 = 0) (3) f157_0_main_LE(x4:0, cons_1, cons_11) -> f157_0_main_LE(x4:0 + 1, x4:0, x4:0) :|: x4:0 > 0 && cons_1 = 1 && cons_11 = 1 (4) f157_0_main_LE(x6, x7, x8) -> f157_0_main_LE(x6 + 1, x6 + -2, x6 + -2) :|: TRUE && x6 >= 2 && (x7 = 0 && x8 = 0) Arcs: (1) -> (1), (2), (3), (4) (2) -> (1) (3) -> (1), (3) (4) -> (1), (3), (4) This digraph is fully evaluated! ---------------------------------------- (23) IntTRSCompressionProof (EQUIVALENT) Compressed rules. ---------------------------------------- (24) Obligation: Rules: f157_0_main_LE(x4:0:0, cons_1, cons_11) -> f157_0_main_LE(x4:0:0 + 1, x4:0:0, x4:0:0) :|: x4:0:0 > 0 && cons_1 = 1 && cons_11 = 1 f157_0_main_LE(x:0:0, x1:0:0, x1:0:0) -> f157_0_main_LE(x:0:0, x1:0:0 - 2, x1:0:0 - 2) :|: x1:0:0 > 1 f157_0_main_LE(x6:0, cons_0, cons_01) -> f157_0_main_LE(x6:0 + 1, x6:0 - 2, x6:0 - 2) :|: x6:0 > 1 && cons_0 = 0 && cons_01 = 0 f157_0_main_LE(x, x1, x2) -> f157_0_main_LE(3, 2, 2) :|: TRUE && x = 1 && x1 = 0 && x2 = 0 ---------------------------------------- (25) TempFilterProof (SOUND) Used the following sort dictionary for filtering: f157_0_main_LE(VARIABLE, VARIABLE, 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: f157_0_main_LE(x4:0:0, c, c1) -> f157_0_main_LE(c2, x4:0:0, x4:0:0) :|: c2 = x4:0:0 + 1 && (c1 = 1 && c = 1) && (x4:0:0 > 0 && cons_1 = 1 && cons_11 = 1) f157_0_main_LE(x:0:0, x1:0:0, x1:0:0) -> f157_0_main_LE(x:0:0, c3, c4) :|: c4 = x1:0:0 - 2 && c3 = x1:0:0 - 2 && x1:0:0 > 1 f157_0_main_LE(x6:0, c5, c6) -> f157_0_main_LE(c7, c8, c9) :|: c9 = x6:0 - 2 && (c8 = x6:0 - 2 && (c7 = x6:0 + 1 && (c6 = 0 && c5 = 0))) && (x6:0 > 1 && cons_0 = 0 && cons_01 = 0) f157_0_main_LE(c10, c11, c12) -> f157_0_main_LE(c13, c14, c15) :|: c15 = 2 && (c14 = 2 && (c13 = 3 && (c12 = 0 && (c11 = 0 && c10 = 1)))) && (TRUE && x = 1 && x1 = 0 && x2 = 0) Found the following polynomial interpretation: [f157_0_main_LE(x, x1, x2)] = 1 - x The following rules are decreasing: f157_0_main_LE(x4:0:0, c, c1) -> f157_0_main_LE(c2, x4:0:0, x4:0:0) :|: c2 = x4:0:0 + 1 && (c1 = 1 && c = 1) && (x4:0:0 > 0 && cons_1 = 1 && cons_11 = 1) f157_0_main_LE(x6:0, c5, c6) -> f157_0_main_LE(c7, c8, c9) :|: c9 = x6:0 - 2 && (c8 = x6:0 - 2 && (c7 = x6:0 + 1 && (c6 = 0 && c5 = 0))) && (x6:0 > 1 && cons_0 = 0 && cons_01 = 0) f157_0_main_LE(c10, c11, c12) -> f157_0_main_LE(c13, c14, c15) :|: c15 = 2 && (c14 = 2 && (c13 = 3 && (c12 = 0 && (c11 = 0 && c10 = 1)))) && (TRUE && x = 1 && x1 = 0 && x2 = 0) The following rules are bounded: f157_0_main_LE(c10, c11, c12) -> f157_0_main_LE(c13, c14, c15) :|: c15 = 2 && (c14 = 2 && (c13 = 3 && (c12 = 0 && (c11 = 0 && c10 = 1)))) && (TRUE && x = 1 && x1 = 0 && x2 = 0) - IntTRS - PolynomialOrderProcessor - IntTRS Rules: f157_0_main_LE(x4:0:0, c, c1) -> f157_0_main_LE(c2, x4:0:0, x4:0:0) :|: c2 = x4:0:0 + 1 && (c1 = 1 && c = 1) && (x4:0:0 > 0 && cons_1 = 1 && cons_11 = 1) f157_0_main_LE(x:0:0, x1:0:0, x1:0:0) -> f157_0_main_LE(x:0:0, c3, c4) :|: c4 = x1:0:0 - 2 && c3 = x1:0:0 - 2 && x1:0:0 > 1 f157_0_main_LE(x6:0, c5, c6) -> f157_0_main_LE(c7, c8, c9) :|: c9 = x6:0 - 2 && (c8 = x6:0 - 2 && (c7 = x6:0 + 1 && (c6 = 0 && c5 = 0))) && (x6:0 > 1 && cons_0 = 0 && cons_01 = 0) ---------------------------------------- (26) Obligation: Rules: f157_0_main_LE(x4:0:0, cons_1, cons_11) -> f157_0_main_LE(x4:0:0 + 1, x4:0:0, x4:0:0) :|: x4:0:0 > 0 && cons_1 = 1 && cons_11 = 1 f157_0_main_LE(x:0:0, x1:0:0, x1:0:0) -> f157_0_main_LE(x:0:0, x1:0:0 - 2, x1:0:0 - 2) :|: x1:0:0 > 1 f157_0_main_LE(x6:0, cons_0, cons_01) -> f157_0_main_LE(x6:0 + 1, x6:0 - 2, x6:0 - 2) :|: x6:0 > 1 && cons_0 = 0 && cons_01 = 0 ---------------------------------------- (27) IRSwTTerminationDigraphProof (EQUIVALENT) Constructed termination digraph! Nodes: (1) f157_0_main_LE(x4:0:0, cons_1, cons_11) -> f157_0_main_LE(x4:0:0 + 1, x4:0:0, x4:0:0) :|: x4:0:0 > 0 && cons_1 = 1 && cons_11 = 1 (2) f157_0_main_LE(x:0:0, x1:0:0, x1:0:0) -> f157_0_main_LE(x:0:0, x1:0:0 - 2, x1:0:0 - 2) :|: x1:0:0 > 1 (3) f157_0_main_LE(x6:0, cons_0, cons_01) -> f157_0_main_LE(x6:0 + 1, x6:0 - 2, x6:0 - 2) :|: x6:0 > 1 && cons_0 = 0 && cons_01 = 0 Arcs: (1) -> (1), (2) (2) -> (1), (2), (3) (3) -> (1), (2), (3) This digraph is fully evaluated! ---------------------------------------- (28) Obligation: Termination digraph: Nodes: (1) f157_0_main_LE(x4:0:0, cons_1, cons_11) -> f157_0_main_LE(x4:0:0 + 1, x4:0:0, x4:0:0) :|: x4:0:0 > 0 && cons_1 = 1 && cons_11 = 1 (2) f157_0_main_LE(x:0:0, x1:0:0, x1:0:0) -> f157_0_main_LE(x:0:0, x1:0:0 - 2, x1:0:0 - 2) :|: x1:0:0 > 1 (3) f157_0_main_LE(x6:0, cons_0, cons_01) -> f157_0_main_LE(x6:0 + 1, x6:0 - 2, x6:0 - 2) :|: x6:0 > 1 && cons_0 = 0 && cons_01 = 0 Arcs: (1) -> (1), (2) (2) -> (1), (2), (3) (3) -> (1), (2), (3) This digraph is fully evaluated! ---------------------------------------- (29) IntTRSCompressionProof (EQUIVALENT) Compressed rules. ---------------------------------------- (30) Obligation: Rules: f157_0_main_LE(x4:0:0:0, cons_1, cons_11) -> f157_0_main_LE(x4:0:0:0 + 1, x4:0:0:0, x4:0:0:0) :|: x4:0:0:0 > 0 && cons_1 = 1 && cons_11 = 1 f157_0_main_LE(x:0:0:0, x1:0:0:0, x1:0:0:0) -> f157_0_main_LE(x:0:0:0, x1:0:0:0 - 2, x1:0:0:0 - 2) :|: x1:0:0:0 > 1 f157_0_main_LE(x6:0:0, cons_0, cons_01) -> f157_0_main_LE(x6:0:0 + 1, x6:0:0 - 2, x6:0:0 - 2) :|: x6:0:0 > 1 && cons_0 = 0 && cons_01 = 0