NO proof of prog.inttrs # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty Termination of the given IRSwT could be disproven: (0) IRSwT (1) IRSFormatTransformerProof [EQUIVALENT, 0 ms] (2) IRSwT (3) IRSwTTerminationDigraphProof [EQUIVALENT, 329 ms] (4) AND (5) IRSwT (6) IntTRSCompressionProof [EQUIVALENT, 3 ms] (7) IRSwT (8) TempFilterProof [SOUND, 12 ms] (9) IntTRS (10) PolynomialOrderProcessor [EQUIVALENT, 0 ms] (11) YES (12) IRSwT (13) IntTRSCompressionProof [EQUIVALENT, 4 ms] (14) IRSwT (15) FilterProof [EQUIVALENT, 0 ms] (16) IntTRS (17) IntTRSCompressionProof [EQUIVALENT, 0 ms] (18) IntTRS (19) IntTRSPeriodicNontermProof [COMPLETE, 10 ms] (20) NO (21) IRSwT (22) IntTRSCompressionProof [EQUIVALENT, 24 ms] (23) IRSwT (24) IntTRSUnneededArgumentFilterProof [EQUIVALENT, 0 ms] (25) IRSwT (26) FilterProof [EQUIVALENT, 0 ms] (27) IntTRS (28) IntTRSCompressionProof [EQUIVALENT, 0 ms] (29) IntTRS (30) RankingReductionPairProof [EQUIVALENT, 0 ms] (31) YES ---------------------------------------- (0) Obligation: Rules: f226_0_createIntList_Return(arg1, arg2) -> f570_0_main_NULL(arg1P, arg2P) :|: -1 <= arg2P - 1 && 0 <= arg1P - 1 && -1 <= arg2 - 1 && 0 <= arg1 - 1 && arg2P <= arg2 && arg1P - 1 <= arg2 && arg1P <= arg1 f1_0_main_Load(x, x1) -> f570_0_main_NULL(x2, x3) :|: -1 <= x3 - 1 && 0 <= x2 - 1 && 0 <= x - 1 && x2 <= x f570_0_main_NULL(x4, x5) -> f570_0_main_NULL(x6, x7) :|: -1 <= x7 - 1 && 0 <= x6 - 1 && 1 <= x5 - 1 && 0 <= x4 - 1 && x7 + 2 <= x5 && x7 + 1 <= x4 && x6 + 1 <= x5 && x6 <= x4 f570_0_main_NULL(x8, x9) -> f570_0_main_NULL(x10, x11) :|: 0 <= x12 - 1 && 0 <= x13 - 1 && x10 <= x8 && x10 + 2 <= x9 && 0 <= x8 - 1 && 2 <= x9 - 1 && 0 <= x10 - 1 && -1 <= x11 - 1 f1_0_main_Load(x15, x16) -> f507_0_createIntList_LE(x17, x18) :|: 1 = x18 && 0 <= x15 - 1 && -1 <= x17 - 1 && -1 <= x16 - 1 f507_0_createIntList_LE(x20, x21) -> f507_0_createIntList_LE(x22, x23) :|: x21 + 1 = x23 && x20 - 1 = x22 && 0 <= x21 - 1 && 0 <= x20 - 1 f570_0_main_NULL(x24, x26) -> f726_0_reverse_NULL(x27, x28) :|: 0 <= x30 - 1 && 0 <= x31 - 1 && x27 + 2 <= x26 && 0 <= x24 - 1 && 2 <= x26 - 1 && 0 <= x27 - 1 f726_0_reverse_NULL(x32, x33) -> f726_0_reverse_NULL(x34, x35) :|: -1 <= x34 - 1 && 0 <= x32 - 1 && x34 + 1 <= x32 __init(x36, x37) -> f1_0_main_Load(x38, x39) :|: 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: f226_0_createIntList_Return(arg1, arg2) -> f570_0_main_NULL(arg1P, arg2P) :|: -1 <= arg2P - 1 && 0 <= arg1P - 1 && -1 <= arg2 - 1 && 0 <= arg1 - 1 && arg2P <= arg2 && arg1P - 1 <= arg2 && arg1P <= arg1 f1_0_main_Load(x, x1) -> f570_0_main_NULL(x2, x3) :|: -1 <= x3 - 1 && 0 <= x2 - 1 && 0 <= x - 1 && x2 <= x f570_0_main_NULL(x4, x5) -> f570_0_main_NULL(x6, x7) :|: -1 <= x7 - 1 && 0 <= x6 - 1 && 1 <= x5 - 1 && 0 <= x4 - 1 && x7 + 2 <= x5 && x7 + 1 <= x4 && x6 + 1 <= x5 && x6 <= x4 f570_0_main_NULL(x8, x9) -> f570_0_main_NULL(x10, x11) :|: 0 <= x12 - 1 && 0 <= x13 - 1 && x10 <= x8 && x10 + 2 <= x9 && 0 <= x8 - 1 && 2 <= x9 - 1 && 0 <= x10 - 1 && -1 <= x11 - 1 f1_0_main_Load(x15, x16) -> f507_0_createIntList_LE(x17, x18) :|: 1 = x18 && 0 <= x15 - 1 && -1 <= x17 - 1 && -1 <= x16 - 1 f507_0_createIntList_LE(x20, x21) -> f507_0_createIntList_LE(x22, x23) :|: x21 + 1 = x23 && x20 - 1 = x22 && 0 <= x21 - 1 && 0 <= x20 - 1 f570_0_main_NULL(x24, x26) -> f726_0_reverse_NULL(x27, x28) :|: 0 <= x30 - 1 && 0 <= x31 - 1 && x27 + 2 <= x26 && 0 <= x24 - 1 && 2 <= x26 - 1 && 0 <= x27 - 1 f726_0_reverse_NULL(x32, x33) -> f726_0_reverse_NULL(x34, x35) :|: -1 <= x34 - 1 && 0 <= x32 - 1 && x34 + 1 <= x32 __init(x36, x37) -> f1_0_main_Load(x38, x39) :|: 0 <= 0 Start term: __init(arg1, arg2) ---------------------------------------- (3) IRSwTTerminationDigraphProof (EQUIVALENT) Constructed termination digraph! Nodes: (1) f226_0_createIntList_Return(arg1, arg2) -> f570_0_main_NULL(arg1P, arg2P) :|: -1 <= arg2P - 1 && 0 <= arg1P - 1 && -1 <= arg2 - 1 && 0 <= arg1 - 1 && arg2P <= arg2 && arg1P - 1 <= arg2 && arg1P <= arg1 (2) f1_0_main_Load(x, x1) -> f570_0_main_NULL(x2, x3) :|: -1 <= x3 - 1 && 0 <= x2 - 1 && 0 <= x - 1 && x2 <= x (3) f570_0_main_NULL(x4, x5) -> f570_0_main_NULL(x6, x7) :|: -1 <= x7 - 1 && 0 <= x6 - 1 && 1 <= x5 - 1 && 0 <= x4 - 1 && x7 + 2 <= x5 && x7 + 1 <= x4 && x6 + 1 <= x5 && x6 <= x4 (4) f570_0_main_NULL(x8, x9) -> f570_0_main_NULL(x10, x11) :|: 0 <= x12 - 1 && 0 <= x13 - 1 && x10 <= x8 && x10 + 2 <= x9 && 0 <= x8 - 1 && 2 <= x9 - 1 && 0 <= x10 - 1 && -1 <= x11 - 1 (5) f1_0_main_Load(x15, x16) -> f507_0_createIntList_LE(x17, x18) :|: 1 = x18 && 0 <= x15 - 1 && -1 <= x17 - 1 && -1 <= x16 - 1 (6) f507_0_createIntList_LE(x20, x21) -> f507_0_createIntList_LE(x22, x23) :|: x21 + 1 = x23 && x20 - 1 = x22 && 0 <= x21 - 1 && 0 <= x20 - 1 (7) f570_0_main_NULL(x24, x26) -> f726_0_reverse_NULL(x27, x28) :|: 0 <= x30 - 1 && 0 <= x31 - 1 && x27 + 2 <= x26 && 0 <= x24 - 1 && 2 <= x26 - 1 && 0 <= x27 - 1 (8) f726_0_reverse_NULL(x32, x33) -> f726_0_reverse_NULL(x34, x35) :|: -1 <= x34 - 1 && 0 <= x32 - 1 && x34 + 1 <= x32 (9) __init(x36, x37) -> f1_0_main_Load(x38, x39) :|: 0 <= 0 Arcs: (1) -> (3), (4), (7) (2) -> (3), (4), (7) (3) -> (3), (4), (7) (4) -> (3), (4), (7) (5) -> (6) (6) -> (6) (7) -> (8) (8) -> (8) (9) -> (2), (5) This digraph is fully evaluated! ---------------------------------------- (4) Complex Obligation (AND) ---------------------------------------- (5) Obligation: Termination digraph: Nodes: (1) f507_0_createIntList_LE(x20, x21) -> f507_0_createIntList_LE(x22, x23) :|: x21 + 1 = x23 && x20 - 1 = x22 && 0 <= x21 - 1 && 0 <= x20 - 1 Arcs: (1) -> (1) This digraph is fully evaluated! ---------------------------------------- (6) IntTRSCompressionProof (EQUIVALENT) Compressed rules. ---------------------------------------- (7) Obligation: Rules: f507_0_createIntList_LE(x20:0, x21:0) -> f507_0_createIntList_LE(x20:0 - 1, x21:0 + 1) :|: x20:0 > 0 && x21:0 > 0 ---------------------------------------- (8) TempFilterProof (SOUND) Used the following sort dictionary for filtering: f507_0_createIntList_LE(INTEGER, INTEGER) Replaced non-predefined constructor symbols by 0. ---------------------------------------- (9) Obligation: Rules: f507_0_createIntList_LE(x20:0, x21:0) -> f507_0_createIntList_LE(c, c1) :|: c1 = x21:0 + 1 && c = x20:0 - 1 && (x20:0 > 0 && x21:0 > 0) ---------------------------------------- (10) PolynomialOrderProcessor (EQUIVALENT) Found the following polynomial interpretation: [f507_0_createIntList_LE(x, x1)] = x The following rules are decreasing: f507_0_createIntList_LE(x20:0, x21:0) -> f507_0_createIntList_LE(c, c1) :|: c1 = x21:0 + 1 && c = x20:0 - 1 && (x20:0 > 0 && x21:0 > 0) The following rules are bounded: f507_0_createIntList_LE(x20:0, x21:0) -> f507_0_createIntList_LE(c, c1) :|: c1 = x21:0 + 1 && c = x20:0 - 1 && (x20:0 > 0 && x21:0 > 0) ---------------------------------------- (11) YES ---------------------------------------- (12) Obligation: Termination digraph: Nodes: (1) f570_0_main_NULL(x4, x5) -> f570_0_main_NULL(x6, x7) :|: -1 <= x7 - 1 && 0 <= x6 - 1 && 1 <= x5 - 1 && 0 <= x4 - 1 && x7 + 2 <= x5 && x7 + 1 <= x4 && x6 + 1 <= x5 && x6 <= x4 (2) f570_0_main_NULL(x8, x9) -> f570_0_main_NULL(x10, x11) :|: 0 <= x12 - 1 && 0 <= x13 - 1 && x10 <= x8 && x10 + 2 <= x9 && 0 <= x8 - 1 && 2 <= x9 - 1 && 0 <= x10 - 1 && -1 <= x11 - 1 Arcs: (1) -> (1), (2) (2) -> (1), (2) This digraph is fully evaluated! ---------------------------------------- (13) IntTRSCompressionProof (EQUIVALENT) Compressed rules. ---------------------------------------- (14) Obligation: Rules: f570_0_main_NULL(x4:0, x5:0) -> f570_0_main_NULL(x6:0, x7:0) :|: x6:0 + 1 <= x5:0 && x6:0 <= x4:0 && x7:0 + 1 <= x4:0 && x7:0 + 2 <= x5:0 && x4:0 > 0 && x5:0 > 1 && x6:0 > 0 && x7:0 > -1 f570_0_main_NULL(x8:0, x9:0) -> f570_0_main_NULL(x10:0, x11:0) :|: x10:0 > 0 && x11:0 > -1 && x9:0 > 2 && x8:0 > 0 && x9:0 >= x10:0 + 2 && x8:0 >= x10:0 && x13:0 > 0 && x12:0 > 0 ---------------------------------------- (15) FilterProof (EQUIVALENT) Used the following sort dictionary for filtering: f570_0_main_NULL(INTEGER, INTEGER) Replaced non-predefined constructor symbols by 0. ---------------------------------------- (16) Obligation: Rules: f570_0_main_NULL(x4:0, x5:0) -> f570_0_main_NULL(x6:0, x7:0) :|: x6:0 + 1 <= x5:0 && x6:0 <= x4:0 && x7:0 + 1 <= x4:0 && x7:0 + 2 <= x5:0 && x4:0 > 0 && x5:0 > 1 && x6:0 > 0 && x7:0 > -1 f570_0_main_NULL(x8:0, x9:0) -> f570_0_main_NULL(x10:0, x11:0) :|: x10:0 > 0 && x11:0 > -1 && x9:0 > 2 && x8:0 > 0 && x9:0 >= x10:0 + 2 && x8:0 >= x10:0 && x13:0 > 0 && x12:0 > 0 ---------------------------------------- (17) IntTRSCompressionProof (EQUIVALENT) Compressed rules. ---------------------------------------- (18) Obligation: Rules: f570_0_main_NULL(x4:0:0, x5:0:0) -> f570_0_main_NULL(x6:0:0, x7:0:0) :|: x6:0:0 > 0 && x7:0:0 > -1 && x5:0:0 > 1 && x4:0:0 > 0 && x7:0:0 + 2 <= x5:0:0 && x7:0:0 + 1 <= x4:0:0 && x6:0:0 <= x4:0:0 && x6:0:0 + 1 <= x5:0:0 f570_0_main_NULL(x8:0:0, x9:0:0) -> f570_0_main_NULL(x10:0:0, x11:0:0) :|: x13:0:0 > 0 && x12:0:0 > 0 && x8:0:0 >= x10:0:0 && x9:0:0 >= x10:0:0 + 2 && x8:0:0 > 0 && x9:0:0 > 2 && x11:0:0 > -1 && x10:0:0 > 0 ---------------------------------------- (19) IntTRSPeriodicNontermProof (COMPLETE) Normalized system to the following form: f(pc, x4:0:0, x5:0:0) -> f(1, x6:0:0, x7:0:0) :|: pc = 1 && (x6:0:0 > 0 && x7:0:0 > -1 && x5:0:0 > 1 && x4:0:0 > 0 && x7:0:0 + 2 <= x5:0:0 && x7:0:0 + 1 <= x4:0:0 && x6:0:0 <= x4:0:0 && x6:0:0 + 1 <= x5:0:0) f(pc, x8:0:0, x9:0:0) -> f(1, x10:0:0, x11:0:0) :|: pc = 1 && (x13:0:0 > 0 && x12:0:0 > 0 && x8:0:0 >= x10:0:0 && x9:0:0 >= x10:0:0 + 2 && x8:0:0 > 0 && x9:0:0 > 2 && x11:0:0 > -1 && x10:0:0 > 0) Witness term starting non-terminating reduction: f(1, 5, 7) ---------------------------------------- (20) NO ---------------------------------------- (21) Obligation: Termination digraph: Nodes: (1) f726_0_reverse_NULL(x32, x33) -> f726_0_reverse_NULL(x34, x35) :|: -1 <= x34 - 1 && 0 <= x32 - 1 && x34 + 1 <= x32 Arcs: (1) -> (1) This digraph is fully evaluated! ---------------------------------------- (22) IntTRSCompressionProof (EQUIVALENT) Compressed rules. ---------------------------------------- (23) Obligation: Rules: f726_0_reverse_NULL(x32:0, x33:0) -> f726_0_reverse_NULL(x34:0, x35:0) :|: x34:0 > -1 && x32:0 > 0 && x34:0 + 1 <= x32:0 ---------------------------------------- (24) IntTRSUnneededArgumentFilterProof (EQUIVALENT) Some arguments are removed because they cannot influence termination. We removed arguments according to the following replacements: f726_0_reverse_NULL(x1, x2) -> f726_0_reverse_NULL(x1) ---------------------------------------- (25) Obligation: Rules: f726_0_reverse_NULL(x32:0) -> f726_0_reverse_NULL(x34:0) :|: x34:0 > -1 && x32:0 > 0 && x34:0 + 1 <= x32:0 ---------------------------------------- (26) FilterProof (EQUIVALENT) Used the following sort dictionary for filtering: f726_0_reverse_NULL(INTEGER) Replaced non-predefined constructor symbols by 0. ---------------------------------------- (27) Obligation: Rules: f726_0_reverse_NULL(x32:0) -> f726_0_reverse_NULL(x34:0) :|: x34:0 > -1 && x32:0 > 0 && x34:0 + 1 <= x32:0 ---------------------------------------- (28) IntTRSCompressionProof (EQUIVALENT) Compressed rules. ---------------------------------------- (29) Obligation: Rules: f726_0_reverse_NULL(x32:0:0) -> f726_0_reverse_NULL(x34:0:0) :|: x34:0:0 > -1 && x32:0:0 > 0 && x34:0:0 + 1 <= x32:0:0 ---------------------------------------- (30) RankingReductionPairProof (EQUIVALENT) Interpretation: [ f726_0_reverse_NULL ] = f726_0_reverse_NULL_1 The following rules are decreasing: f726_0_reverse_NULL(x32:0:0) -> f726_0_reverse_NULL(x34:0:0) :|: x34:0:0 > -1 && x32:0:0 > 0 && x34:0:0 + 1 <= x32:0:0 The following rules are bounded: f726_0_reverse_NULL(x32:0:0) -> f726_0_reverse_NULL(x34:0:0) :|: x34:0:0 > -1 && x32:0:0 > 0 && x34:0:0 + 1 <= x32:0:0 ---------------------------------------- (31) YES