YES proof of prog.inttrs # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty Termination of the given IRSwT could be proven: (0) IRSwT (1) IRSFormatTransformerProof [EQUIVALENT, 0 ms] (2) IRSwT (3) IRSwTTerminationDigraphProof [EQUIVALENT, 461 ms] (4) AND (5) IRSwT (6) IntTRSCompressionProof [EQUIVALENT, 9 ms] (7) IRSwT (8) TempFilterProof [SOUND, 53 ms] (9) IntTRS (10) PolynomialOrderProcessor [EQUIVALENT, 10 ms] (11) IntTRS (12) PolynomialOrderProcessor [EQUIVALENT, 0 ms] (13) YES (14) IRSwT (15) IntTRSCompressionProof [EQUIVALENT, 9 ms] (16) IRSwT (17) IntTRSUnneededArgumentFilterProof [EQUIVALENT, 0 ms] (18) IRSwT (19) TempFilterProof [SOUND, 27 ms] (20) IntTRS (21) PolynomialOrderProcessor [EQUIVALENT, 10 ms] (22) YES ---------------------------------------- (0) Obligation: Rules: f1_0_main_Load(arg1, arg2, arg3) -> f117_0_createList_GE(arg1P, arg2P, arg3P) :|: 0 <= arg1 - 1 && 0 <= arg2 - 1 && -1 <= arg1P - 1 f1_0_main_Load(x, x1, x2) -> f232_0_main_InvokeMethod(x3, x4, x5) :|: -1 <= x6 - 1 && 0 <= x1 - 1 && x3 <= x && 0 <= x - 1 && 0 <= x3 - 1 && 3 <= x4 - 1 && 0 = x5 f1_0_main_Load(x8, x9, x10) -> f232_0_main_InvokeMethod(x11, x13, x14) :|: -1 <= x16 - 1 && 0 <= x9 - 1 && x11 <= x8 && x13 - 1 <= x8 && 0 <= x8 - 1 && 0 <= x11 - 1 && 1 <= x13 - 1 && 0 = x14 f117_0_createList_GE(x17, x18, x19) -> f117_0_createList_GE(x20, x21, x22) :|: x17 - 1 = x20 && x17 - 1 <= x17 - 1 && -1 <= x17 - 1 f232_0_main_InvokeMethod(x23, x24, x25) -> f389_0_dupList_NONNULL(x26, x27, x28) :|: x26 <= x24 && 0 <= x29 - 1 && x27 + 2 <= x24 && 0 <= x23 - 1 && 1 <= x24 - 1 && 1 <= x26 - 1 && -1 <= x27 - 1 && 0 = x25 && 0 = x28 f389_0_dupList_NONNULL(x30, x31, x32) -> f389_0_dupList_NONNULL(x33, x34, x35) :|: x35 + 2 <= x31 && x32 + 2 <= x30 && x35 + 4 <= x30 && -1 <= x34 - 1 && 0 <= x33 - 1 && 0 <= x31 - 1 && 2 <= x30 - 1 && x34 + 1 <= x31 && x34 + 3 <= x30 && x33 <= x31 && x32 <= -1 && x33 + 2 <= x30 f389_0_dupList_NONNULL(x36, x37, x38) -> f389_0_dupList_NONNULL(x39, x40, x41) :|: x41 + 2 <= x37 && x38 + 2 <= x36 && x41 + 4 <= x36 && -1 <= x40 - 1 && 0 <= x39 - 1 && 0 <= x37 - 1 && 2 <= x36 - 1 && x40 + 1 <= x37 && x40 + 3 <= x36 && x39 <= x37 && 0 <= x38 - 1 && x39 + 2 <= x36 f389_0_dupList_NONNULL(x42, x43, x44) -> f389_0_dupList_NONNULL(x45, x46, x47) :|: 1 = x47 && 0 = x44 && 0 <= x46 - 1 && 2 <= x45 - 1 && 0 <= x43 - 1 && 2 <= x42 - 1 && x46 <= x43 && x46 + 2 <= x42 && x45 - 2 <= x43 && x45 <= x42 __init(x48, x49, x50) -> f1_0_main_Load(x51, x52, x53) :|: 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) -> f117_0_createList_GE(arg1P, arg2P, arg3P) :|: 0 <= arg1 - 1 && 0 <= arg2 - 1 && -1 <= arg1P - 1 f1_0_main_Load(x, x1, x2) -> f232_0_main_InvokeMethod(x3, x4, x5) :|: -1 <= x6 - 1 && 0 <= x1 - 1 && x3 <= x && 0 <= x - 1 && 0 <= x3 - 1 && 3 <= x4 - 1 && 0 = x5 f1_0_main_Load(x8, x9, x10) -> f232_0_main_InvokeMethod(x11, x13, x14) :|: -1 <= x16 - 1 && 0 <= x9 - 1 && x11 <= x8 && x13 - 1 <= x8 && 0 <= x8 - 1 && 0 <= x11 - 1 && 1 <= x13 - 1 && 0 = x14 f117_0_createList_GE(x17, x18, x19) -> f117_0_createList_GE(x20, x21, x22) :|: x17 - 1 = x20 && x17 - 1 <= x17 - 1 && -1 <= x17 - 1 f232_0_main_InvokeMethod(x23, x24, x25) -> f389_0_dupList_NONNULL(x26, x27, x28) :|: x26 <= x24 && 0 <= x29 - 1 && x27 + 2 <= x24 && 0 <= x23 - 1 && 1 <= x24 - 1 && 1 <= x26 - 1 && -1 <= x27 - 1 && 0 = x25 && 0 = x28 f389_0_dupList_NONNULL(x30, x31, x32) -> f389_0_dupList_NONNULL(x33, x34, x35) :|: x35 + 2 <= x31 && x32 + 2 <= x30 && x35 + 4 <= x30 && -1 <= x34 - 1 && 0 <= x33 - 1 && 0 <= x31 - 1 && 2 <= x30 - 1 && x34 + 1 <= x31 && x34 + 3 <= x30 && x33 <= x31 && x32 <= -1 && x33 + 2 <= x30 f389_0_dupList_NONNULL(x36, x37, x38) -> f389_0_dupList_NONNULL(x39, x40, x41) :|: x41 + 2 <= x37 && x38 + 2 <= x36 && x41 + 4 <= x36 && -1 <= x40 - 1 && 0 <= x39 - 1 && 0 <= x37 - 1 && 2 <= x36 - 1 && x40 + 1 <= x37 && x40 + 3 <= x36 && x39 <= x37 && 0 <= x38 - 1 && x39 + 2 <= x36 f389_0_dupList_NONNULL(x42, x43, x44) -> f389_0_dupList_NONNULL(x45, x46, x47) :|: 1 = x47 && 0 = x44 && 0 <= x46 - 1 && 2 <= x45 - 1 && 0 <= x43 - 1 && 2 <= x42 - 1 && x46 <= x43 && x46 + 2 <= x42 && x45 - 2 <= x43 && x45 <= x42 __init(x48, x49, x50) -> f1_0_main_Load(x51, x52, x53) :|: 0 <= 0 Start term: __init(arg1, arg2, arg3) ---------------------------------------- (3) IRSwTTerminationDigraphProof (EQUIVALENT) Constructed termination digraph! Nodes: (1) f1_0_main_Load(arg1, arg2, arg3) -> f117_0_createList_GE(arg1P, arg2P, arg3P) :|: 0 <= arg1 - 1 && 0 <= arg2 - 1 && -1 <= arg1P - 1 (2) f1_0_main_Load(x, x1, x2) -> f232_0_main_InvokeMethod(x3, x4, x5) :|: -1 <= x6 - 1 && 0 <= x1 - 1 && x3 <= x && 0 <= x - 1 && 0 <= x3 - 1 && 3 <= x4 - 1 && 0 = x5 (3) f1_0_main_Load(x8, x9, x10) -> f232_0_main_InvokeMethod(x11, x13, x14) :|: -1 <= x16 - 1 && 0 <= x9 - 1 && x11 <= x8 && x13 - 1 <= x8 && 0 <= x8 - 1 && 0 <= x11 - 1 && 1 <= x13 - 1 && 0 = x14 (4) f117_0_createList_GE(x17, x18, x19) -> f117_0_createList_GE(x20, x21, x22) :|: x17 - 1 = x20 && x17 - 1 <= x17 - 1 && -1 <= x17 - 1 (5) f232_0_main_InvokeMethod(x23, x24, x25) -> f389_0_dupList_NONNULL(x26, x27, x28) :|: x26 <= x24 && 0 <= x29 - 1 && x27 + 2 <= x24 && 0 <= x23 - 1 && 1 <= x24 - 1 && 1 <= x26 - 1 && -1 <= x27 - 1 && 0 = x25 && 0 = x28 (6) f389_0_dupList_NONNULL(x30, x31, x32) -> f389_0_dupList_NONNULL(x33, x34, x35) :|: x35 + 2 <= x31 && x32 + 2 <= x30 && x35 + 4 <= x30 && -1 <= x34 - 1 && 0 <= x33 - 1 && 0 <= x31 - 1 && 2 <= x30 - 1 && x34 + 1 <= x31 && x34 + 3 <= x30 && x33 <= x31 && x32 <= -1 && x33 + 2 <= x30 (7) f389_0_dupList_NONNULL(x36, x37, x38) -> f389_0_dupList_NONNULL(x39, x40, x41) :|: x41 + 2 <= x37 && x38 + 2 <= x36 && x41 + 4 <= x36 && -1 <= x40 - 1 && 0 <= x39 - 1 && 0 <= x37 - 1 && 2 <= x36 - 1 && x40 + 1 <= x37 && x40 + 3 <= x36 && x39 <= x37 && 0 <= x38 - 1 && x39 + 2 <= x36 (8) f389_0_dupList_NONNULL(x42, x43, x44) -> f389_0_dupList_NONNULL(x45, x46, x47) :|: 1 = x47 && 0 = x44 && 0 <= x46 - 1 && 2 <= x45 - 1 && 0 <= x43 - 1 && 2 <= x42 - 1 && x46 <= x43 && x46 + 2 <= x42 && x45 - 2 <= x43 && x45 <= x42 (9) __init(x48, x49, x50) -> f1_0_main_Load(x51, x52, x53) :|: 0 <= 0 Arcs: (1) -> (4) (2) -> (5) (3) -> (5) (4) -> (4) (5) -> (8) (6) -> (6), (7), (8) (7) -> (6), (7), (8) (8) -> (7) (9) -> (1), (2), (3) This digraph is fully evaluated! ---------------------------------------- (4) Complex Obligation (AND) ---------------------------------------- (5) Obligation: Termination digraph: Nodes: (1) f389_0_dupList_NONNULL(x42, x43, x44) -> f389_0_dupList_NONNULL(x45, x46, x47) :|: 1 = x47 && 0 = x44 && 0 <= x46 - 1 && 2 <= x45 - 1 && 0 <= x43 - 1 && 2 <= x42 - 1 && x46 <= x43 && x46 + 2 <= x42 && x45 - 2 <= x43 && x45 <= x42 (2) f389_0_dupList_NONNULL(x30, x31, x32) -> f389_0_dupList_NONNULL(x33, x34, x35) :|: x35 + 2 <= x31 && x32 + 2 <= x30 && x35 + 4 <= x30 && -1 <= x34 - 1 && 0 <= x33 - 1 && 0 <= x31 - 1 && 2 <= x30 - 1 && x34 + 1 <= x31 && x34 + 3 <= x30 && x33 <= x31 && x32 <= -1 && x33 + 2 <= x30 (3) f389_0_dupList_NONNULL(x36, x37, x38) -> f389_0_dupList_NONNULL(x39, x40, x41) :|: x41 + 2 <= x37 && x38 + 2 <= x36 && x41 + 4 <= x36 && -1 <= x40 - 1 && 0 <= x39 - 1 && 0 <= x37 - 1 && 2 <= x36 - 1 && x40 + 1 <= x37 && x40 + 3 <= x36 && x39 <= x37 && 0 <= x38 - 1 && x39 + 2 <= x36 Arcs: (1) -> (3) (2) -> (1), (2), (3) (3) -> (1), (2), (3) This digraph is fully evaluated! ---------------------------------------- (6) IntTRSCompressionProof (EQUIVALENT) Compressed rules. ---------------------------------------- (7) Obligation: Rules: f389_0_dupList_NONNULL(x42:0, x43:0, cons_0) -> f389_0_dupList_NONNULL(x45:0, x46:0, 1) :|: x45:0 - 2 <= x43:0 && x45:0 <= x42:0 && x46:0 + 2 <= x42:0 && x46:0 <= x43:0 && x42:0 > 2 && x43:0 > 0 && x46:0 > 0 && x45:0 > 2 && cons_0 = 0 f389_0_dupList_NONNULL(x30:0, x31:0, x32:0) -> f389_0_dupList_NONNULL(x33:0, x34:0, x35:0) :|: x32:0 < 0 && x33:0 + 2 <= x30:0 && x33:0 <= x31:0 && x34:0 + 3 <= x30:0 && x34:0 + 1 <= x31:0 && x30:0 > 2 && x31:0 > 0 && x33:0 > 0 && x34:0 > -1 && x35:0 + 4 <= x30:0 && x32:0 + 2 <= x30:0 && x35:0 + 2 <= x31:0 f389_0_dupList_NONNULL(x36:0, x37:0, x38:0) -> f389_0_dupList_NONNULL(x39:0, x40:0, x41:0) :|: x38:0 > 0 && x39:0 + 2 <= x36:0 && x39:0 <= x37:0 && x40:0 + 3 <= x36:0 && x40:0 + 1 <= x37:0 && x36:0 > 2 && x37:0 > 0 && x39:0 > 0 && x40:0 > -1 && x41:0 + 4 <= x36:0 && x38:0 + 2 <= x36:0 && x41:0 + 2 <= x37:0 ---------------------------------------- (8) TempFilterProof (SOUND) Used the following sort dictionary for filtering: f389_0_dupList_NONNULL(INTEGER, INTEGER, VARIABLE) Replaced non-predefined constructor symbols by 0. ---------------------------------------- (9) Obligation: Rules: f389_0_dupList_NONNULL(x42:0, x43:0, c) -> f389_0_dupList_NONNULL(x45:0, x46:0, c1) :|: c1 = 1 && c = 0 && (x45:0 - 2 <= x43:0 && x45:0 <= x42:0 && x46:0 + 2 <= x42:0 && x46:0 <= x43:0 && x42:0 > 2 && x43:0 > 0 && x46:0 > 0 && x45:0 > 2 && cons_0 = 0) f389_0_dupList_NONNULL(x30:0, x31:0, x32:0) -> f389_0_dupList_NONNULL(x33:0, x34:0, x35:0) :|: x32:0 < 0 && x33:0 + 2 <= x30:0 && x33:0 <= x31:0 && x34:0 + 3 <= x30:0 && x34:0 + 1 <= x31:0 && x30:0 > 2 && x31:0 > 0 && x33:0 > 0 && x34:0 > -1 && x35:0 + 4 <= x30:0 && x32:0 + 2 <= x30:0 && x35:0 + 2 <= x31:0 f389_0_dupList_NONNULL(x36:0, x37:0, x38:0) -> f389_0_dupList_NONNULL(x39:0, x40:0, x41:0) :|: x38:0 > 0 && x39:0 + 2 <= x36:0 && x39:0 <= x37:0 && x40:0 + 3 <= x36:0 && x40:0 + 1 <= x37:0 && x36:0 > 2 && x37:0 > 0 && x39:0 > 0 && x40:0 > -1 && x41:0 + 4 <= x36:0 && x38:0 + 2 <= x36:0 && x41:0 + 2 <= x37:0 ---------------------------------------- (10) PolynomialOrderProcessor (EQUIVALENT) Found the following polynomial interpretation: [f389_0_dupList_NONNULL(x, x1, x2)] = x1 The following rules are decreasing: f389_0_dupList_NONNULL(x30:0, x31:0, x32:0) -> f389_0_dupList_NONNULL(x33:0, x34:0, x35:0) :|: x32:0 < 0 && x33:0 + 2 <= x30:0 && x33:0 <= x31:0 && x34:0 + 3 <= x30:0 && x34:0 + 1 <= x31:0 && x30:0 > 2 && x31:0 > 0 && x33:0 > 0 && x34:0 > -1 && x35:0 + 4 <= x30:0 && x32:0 + 2 <= x30:0 && x35:0 + 2 <= x31:0 f389_0_dupList_NONNULL(x36:0, x37:0, x38:0) -> f389_0_dupList_NONNULL(x39:0, x40:0, x41:0) :|: x38:0 > 0 && x39:0 + 2 <= x36:0 && x39:0 <= x37:0 && x40:0 + 3 <= x36:0 && x40:0 + 1 <= x37:0 && x36:0 > 2 && x37:0 > 0 && x39:0 > 0 && x40:0 > -1 && x41:0 + 4 <= x36:0 && x38:0 + 2 <= x36:0 && x41:0 + 2 <= x37:0 The following rules are bounded: f389_0_dupList_NONNULL(x42:0, x43:0, c) -> f389_0_dupList_NONNULL(x45:0, x46:0, c1) :|: c1 = 1 && c = 0 && (x45:0 - 2 <= x43:0 && x45:0 <= x42:0 && x46:0 + 2 <= x42:0 && x46:0 <= x43:0 && x42:0 > 2 && x43:0 > 0 && x46:0 > 0 && x45:0 > 2 && cons_0 = 0) f389_0_dupList_NONNULL(x30:0, x31:0, x32:0) -> f389_0_dupList_NONNULL(x33:0, x34:0, x35:0) :|: x32:0 < 0 && x33:0 + 2 <= x30:0 && x33:0 <= x31:0 && x34:0 + 3 <= x30:0 && x34:0 + 1 <= x31:0 && x30:0 > 2 && x31:0 > 0 && x33:0 > 0 && x34:0 > -1 && x35:0 + 4 <= x30:0 && x32:0 + 2 <= x30:0 && x35:0 + 2 <= x31:0 f389_0_dupList_NONNULL(x36:0, x37:0, x38:0) -> f389_0_dupList_NONNULL(x39:0, x40:0, x41:0) :|: x38:0 > 0 && x39:0 + 2 <= x36:0 && x39:0 <= x37:0 && x40:0 + 3 <= x36:0 && x40:0 + 1 <= x37:0 && x36:0 > 2 && x37:0 > 0 && x39:0 > 0 && x40:0 > -1 && x41:0 + 4 <= x36:0 && x38:0 + 2 <= x36:0 && x41:0 + 2 <= x37:0 ---------------------------------------- (11) Obligation: Rules: f389_0_dupList_NONNULL(x42:0, x43:0, c) -> f389_0_dupList_NONNULL(x45:0, x46:0, c1) :|: c1 = 1 && c = 0 && (x45:0 - 2 <= x43:0 && x45:0 <= x42:0 && x46:0 + 2 <= x42:0 && x46:0 <= x43:0 && x42:0 > 2 && x43:0 > 0 && x46:0 > 0 && x45:0 > 2 && cons_0 = 0) ---------------------------------------- (12) PolynomialOrderProcessor (EQUIVALENT) Found the following polynomial interpretation: [f389_0_dupList_NONNULL(x, x1, x2)] = -x2 The following rules are decreasing: f389_0_dupList_NONNULL(x42:0, x43:0, c) -> f389_0_dupList_NONNULL(x45:0, x46:0, c1) :|: c1 = 1 && c = 0 && (x45:0 - 2 <= x43:0 && x45:0 <= x42:0 && x46:0 + 2 <= x42:0 && x46:0 <= x43:0 && x42:0 > 2 && x43:0 > 0 && x46:0 > 0 && x45:0 > 2 && cons_0 = 0) The following rules are bounded: f389_0_dupList_NONNULL(x42:0, x43:0, c) -> f389_0_dupList_NONNULL(x45:0, x46:0, c1) :|: c1 = 1 && c = 0 && (x45:0 - 2 <= x43:0 && x45:0 <= x42:0 && x46:0 + 2 <= x42:0 && x46:0 <= x43:0 && x42:0 > 2 && x43:0 > 0 && x46:0 > 0 && x45:0 > 2 && cons_0 = 0) ---------------------------------------- (13) YES ---------------------------------------- (14) Obligation: Termination digraph: Nodes: (1) f117_0_createList_GE(x17, x18, x19) -> f117_0_createList_GE(x20, x21, x22) :|: x17 - 1 = x20 && x17 - 1 <= x17 - 1 && -1 <= x17 - 1 Arcs: (1) -> (1) This digraph is fully evaluated! ---------------------------------------- (15) IntTRSCompressionProof (EQUIVALENT) Compressed rules. ---------------------------------------- (16) Obligation: Rules: f117_0_createList_GE(x17:0, x18:0, x19:0) -> f117_0_createList_GE(x17:0 - 1, x21:0, x22:0) :|: x17:0 > -1 ---------------------------------------- (17) IntTRSUnneededArgumentFilterProof (EQUIVALENT) Some arguments are removed because they cannot influence termination. We removed arguments according to the following replacements: f117_0_createList_GE(x1, x2, x3) -> f117_0_createList_GE(x1) ---------------------------------------- (18) Obligation: Rules: f117_0_createList_GE(x17:0) -> f117_0_createList_GE(x17:0 - 1) :|: x17:0 > -1 ---------------------------------------- (19) TempFilterProof (SOUND) Used the following sort dictionary for filtering: f117_0_createList_GE(INTEGER) Replaced non-predefined constructor symbols by 0. ---------------------------------------- (20) Obligation: Rules: f117_0_createList_GE(x17:0) -> f117_0_createList_GE(c) :|: c = x17:0 - 1 && x17:0 > -1 ---------------------------------------- (21) PolynomialOrderProcessor (EQUIVALENT) Found the following polynomial interpretation: [f117_0_createList_GE(x)] = x The following rules are decreasing: f117_0_createList_GE(x17:0) -> f117_0_createList_GE(c) :|: c = x17:0 - 1 && x17:0 > -1 The following rules are bounded: f117_0_createList_GE(x17:0) -> f117_0_createList_GE(c) :|: c = x17:0 - 1 && x17:0 > -1 ---------------------------------------- (22) YES