/export/starexec/sandbox2/solver/bin/starexec_run_standard /export/starexec/sandbox2/benchmark/theBenchmark.jar /export/starexec/sandbox2/output/output_files -------------------------------------------------------------------------------- YES proof of /export/starexec/sandbox2/benchmark/theBenchmark.jar # AProVE Commit ID: 794c25de1cacf0d048858bcd21c9a779e1221865 marcel 20200619 unpublished dirty termination of the given Bare JBC problem could be proven: (0) Bare JBC problem (1) BareJBCToJBCProof [EQUIVALENT, 96 ms] (2) JBC problem (3) JBCToGraph [EQUIVALENT, 367 ms] (4) JBCTerminationGraph (5) TerminationGraphToSCCProof [SOUND, 0 ms] (6) AND (7) JBCTerminationSCC (8) SCCToIRSProof [SOUND, 66 ms] (9) IRSwT (10) IRSFormatTransformerProof [EQUIVALENT, 0 ms] (11) IRSwT (12) IRSwTTerminationDigraphProof [EQUIVALENT, 9 ms] (13) IRSwT (14) IntTRSCompressionProof [EQUIVALENT, 0 ms] (15) IRSwT (16) TempFilterProof [SOUND, 18 ms] (17) IntTRS (18) PolynomialOrderProcessor [EQUIVALENT, 4 ms] (19) YES (20) JBCTerminationSCC (21) SCCToIRSProof [SOUND, 56 ms] (22) IRSwT (23) IRSFormatTransformerProof [EQUIVALENT, 0 ms] (24) IRSwT (25) IRSwTTerminationDigraphProof [EQUIVALENT, 2 ms] (26) IRSwT (27) IntTRSCompressionProof [EQUIVALENT, 0 ms] (28) IRSwT (29) TempFilterProof [SOUND, 28 ms] (30) IntTRS (31) PolynomialOrderProcessor [EQUIVALENT, 13 ms] (32) YES ---------------------------------------- (0) Obligation: need to prove termination of the following program: public class List2 { private List2 next; private int mark; static void visit(List2 c) { int expectedMark = c.mark; while (c != null && c.mark == expectedMark) { c.mark = expectedMark + 1; c = c.next; } } public static void main(String[] args) { //Create cyclic list: int length = args.length; List2 cur = new List2(); List2 last = cur; while (length-- > 0) { List2 n = new List2(); n.next = cur; cur = n; } last.next = cur; visit(cur); } } ---------------------------------------- (1) BareJBCToJBCProof (EQUIVALENT) initialized classpath ---------------------------------------- (2) Obligation: need to prove termination of the following program: public class List2 { private List2 next; private int mark; static void visit(List2 c) { int expectedMark = c.mark; while (c != null && c.mark == expectedMark) { c.mark = expectedMark + 1; c = c.next; } } public static void main(String[] args) { //Create cyclic list: int length = args.length; List2 cur = new List2(); List2 last = cur; while (length-- > 0) { List2 n = new List2(); n.next = cur; cur = n; } last.next = cur; visit(cur); } } ---------------------------------------- (3) JBCToGraph (EQUIVALENT) Constructed TerminationGraph. ---------------------------------------- (4) Obligation: Termination Graph based on JBC Program: List2.main([Ljava/lang/String;)V: Graph of 56 nodes with 1 SCC. List2.visit(LList2;)V: Graph of 29 nodes with 1 SCC. ---------------------------------------- (5) TerminationGraphToSCCProof (SOUND) Splitted TerminationGraph to 2 SCCss. ---------------------------------------- (6) Complex Obligation (AND) ---------------------------------------- (7) Obligation: SCC of termination graph based on JBC Program. SCC contains nodes from the following methods: List2.visit(LList2;)V SCC calls the following helper methods: Performed SCC analyses: *Used field analysis yielded the following read fields: *List2: [mark, next] *Marker field analysis yielded the following relations that could be markers: *List2.mark = iconst_0 (Introduced counter i103) ---------------------------------------- (8) SCCToIRSProof (SOUND) Transformed FIGraph SCCs to intTRSs. Log: Generated rules. Obtained 19 IRulesP rules: f615_0_visit_NULL(EOS(STATIC_615), java.lang.Object(o68sub0), matching1, java.lang.Object(o68sub0), i103) -> f964_0_visit_NULL(EOS(STATIC_964), java.lang.Object(o68sub0), 0, java.lang.Object(o68sub0), i103) :|: TRUE && matching1 = 0 f964_0_visit_NULL(EOS(STATIC_964), java.lang.Object(o68sub0), matching1, java.lang.Object(o68sub0), i103) -> f967_0_visit_Load(EOS(STATIC_967), java.lang.Object(o68sub0), 0, i103) :|: TRUE && matching1 = 0 f967_0_visit_Load(EOS(STATIC_967), java.lang.Object(o68sub0), matching1, i103) -> f1004_0_visit_FieldAccess(EOS(STATIC_1004), java.lang.Object(o68sub0), 0, java.lang.Object(o68sub0), i103) :|: TRUE && matching1 = 0 f1004_0_visit_FieldAccess(EOS(STATIC_1004), java.lang.Object(List2(EOC, i78, o76543103794)), matching1, java.lang.Object(List2(EOC, i78, o76543103794)), i103) -> f1011_0_visit_FieldAccess(EOS(STATIC_1011), java.lang.Object(List2(EOC, i78, o76543103794)), 0, java.lang.Object(List2(EOC, i78, o76543103794)), i103) :|: TRUE && matching1 = 0 f1011_0_visit_FieldAccess(EOS(STATIC_1011), java.lang.Object(List2(EOC, i78, o76543103794)), matching1, java.lang.Object(List2(EOC, i78, o76543103794)), i103) -> f1013_0_visit_Load(EOS(STATIC_1013), java.lang.Object(List2(EOC, i78, o76543103794)), 0, i78, i103) :|: TRUE && matching1 = 0 f1013_0_visit_Load(EOS(STATIC_1013), java.lang.Object(List2(EOC, i78, o76543103794)), matching1, i78, i103) -> f1021_0_visit_NE(EOS(STATIC_1021), java.lang.Object(List2(EOC, i78, o76543103794)), 0, i78, 0, i103) :|: TRUE && matching1 = 0 f1021_0_visit_NE(EOS(STATIC_1021), java.lang.Object(List2(EOC, matching1, o76543103794)), matching2, matching3, matching4, i103) -> f1077_0_visit_NE(EOS(STATIC_1077), java.lang.Object(List2(EOC, 0, o76543103794)), 0, 0, 0, i103) :|: i78 = 0 && matching1 = 0 && matching2 = 0 && matching3 = 0 && matching4 = 0 f1077_0_visit_NE(EOS(STATIC_1077), java.lang.Object(List2(EOC, matching1, o76543103794)), matching2, matching3, matching4, i103) -> f1090_0_visit_Load(EOS(STATIC_1090), java.lang.Object(List2(EOC, 0, o76543103794)), 0, i103) :|: TRUE && matching1 = 0 && matching2 = 0 && matching3 = 0 && matching4 = 0 f1090_0_visit_Load(EOS(STATIC_1090), java.lang.Object(List2(EOC, matching1, o76543103794)), matching2, i103) -> f1095_0_visit_Load(EOS(STATIC_1095), java.lang.Object(List2(EOC, 0, o76543103794)), 0, java.lang.Object(List2(EOC, 0, o76543103794)), i103) :|: TRUE && matching1 = 0 && matching2 = 0 f1095_0_visit_Load(EOS(STATIC_1095), java.lang.Object(List2(EOC, matching1, o76543103794)), matching2, java.lang.Object(List2(EOC, matching3, o76543103794)), i103) -> f1101_0_visit_ConstantStackPush(EOS(STATIC_1101), java.lang.Object(List2(EOC, 0, o76543103794)), 0, java.lang.Object(List2(EOC, 0, o76543103794)), 0, i103) :|: TRUE && matching1 = 0 && matching2 = 0 && matching3 = 0 f1101_0_visit_ConstantStackPush(EOS(STATIC_1101), java.lang.Object(List2(EOC, matching1, o76543103794)), matching2, java.lang.Object(List2(EOC, matching3, o76543103794)), matching4, i103) -> f1109_0_visit_IntArithmetic(EOS(STATIC_1109), java.lang.Object(List2(EOC, 0, o76543103794)), 0, java.lang.Object(List2(EOC, 0, o76543103794)), 0, 1, i103) :|: TRUE && matching1 = 0 && matching2 = 0 && matching3 = 0 && matching4 = 0 f1109_0_visit_IntArithmetic(EOS(STATIC_1109), java.lang.Object(List2(EOC, matching1, o76543103794)), matching2, java.lang.Object(List2(EOC, matching3, o76543103794)), matching4, matching5, i103) -> f1163_0_visit_FieldAccess(EOS(STATIC_1163), java.lang.Object(List2(EOC, 0, o76543103794)), 0, java.lang.Object(List2(EOC, 0, o76543103794)), 1, i103) :|: TRUE && matching1 = 0 && matching2 = 0 && matching3 = 0 && matching4 = 0 && matching5 = 1 f1163_0_visit_FieldAccess(EOS(STATIC_1163), java.lang.Object(List2(EOC, matching1, o76543103794)), matching2, java.lang.Object(List2(EOC, matching3, o76543103794)), matching4, i103) -> f1172_0_visit_Load(EOS(STATIC_1172), java.lang.Object(List2(EOC, 1, o76put543103794)), 0, i103 + -1) :|: i103 >= 0 && matching1 = 0 && matching2 = 0 && matching3 = 0 && matching4 = 1 f1172_0_visit_Load(EOS(STATIC_1172), java.lang.Object(List2(EOC, matching1, o76543103794)), matching2, i103) -> f1176_0_visit_FieldAccess(EOS(STATIC_1176), 0, java.lang.Object(List2(EOC, 1, o76543103794)), i103) :|: TRUE && matching1 = 1 && matching2 = 0 f1176_0_visit_FieldAccess(EOS(STATIC_1176), matching1, java.lang.Object(List2(EOC, matching2, o76543103794)), i103) -> f1209_0_visit_Store(EOS(STATIC_1209), 0, o760, i103) :|: TRUE && matching1 = 0 && matching2 = 1 f1209_0_visit_Store(EOS(STATIC_1209), matching1, o760, i103) -> f1213_0_visit_JMP(EOS(STATIC_1213), o760, 0, i103) :|: TRUE && matching1 = 0 f1213_0_visit_JMP(EOS(STATIC_1213), o760, matching1, i103) -> f1221_0_visit_Load(EOS(STATIC_1221), o760, 0, i103) :|: TRUE && matching1 = 0 f1221_0_visit_Load(EOS(STATIC_1221), o760, matching1, i103) -> f594_0_visit_Load(EOS(STATIC_594), o760, 0, i103) :|: TRUE && matching1 = 0 f594_0_visit_Load(EOS(STATIC_594), o570, matching1, i103) -> f615_0_visit_NULL(EOS(STATIC_615), o570, 0, o570, i103) :|: TRUE && matching1 = 0 Combined rules. Obtained 1 IRulesP rules: f615_0_visit_NULL(EOS(STATIC_615), java.lang.Object(List2(EOC, 0, o76543103794:0)), 0, java.lang.Object(List2(EOC, 0, o76543103794:0)), i103:0) -> f615_0_visit_NULL(EOS(STATIC_615), o760:0, 0, o760:0, i103:0 - 1) :|: i103:0 > -1 Filtered constant ground arguments: f615_0_visit_NULL(x1, x2, x3, x4, x5) -> f615_0_visit_NULL(x2, x4, x5) EOS(x1) -> EOS List2(x1, x2, x3) -> List2(x3) Filtered duplicate arguments: f615_0_visit_NULL(x1, x2, x3) -> f615_0_visit_NULL(x2, x3) Finished conversion. Obtained 1 rules.P rules: f615_0_visit_NULL(java.lang.Object(List2(o76543103794:0)), i103:0) -> f615_0_visit_NULL(o760:0, i103:0 - 1) :|: i103:0 > -1 ---------------------------------------- (9) Obligation: Rules: f615_0_visit_NULL(java.lang.Object(List2(o76543103794:0)), i103:0) -> f615_0_visit_NULL(o760:0, i103:0 - 1) :|: i103:0 > -1 ---------------------------------------- (10) IRSFormatTransformerProof (EQUIVALENT) Reformatted IRS to match normalized format (transformed away non-linear left-hand sides, !=, / and %). ---------------------------------------- (11) Obligation: Rules: f615_0_visit_NULL(java.lang.Object(List2(o76543103794:0)), i103:0) -> f615_0_visit_NULL(o760:0, arith) :|: i103:0 > -1 && arith = i103:0 - 1 ---------------------------------------- (12) IRSwTTerminationDigraphProof (EQUIVALENT) Constructed termination digraph! Nodes: (1) f615_0_visit_NULL(java.lang.Object(List2(o76543103794:0)), i103:0) -> f615_0_visit_NULL(o760:0, arith) :|: i103:0 > -1 && arith = i103:0 - 1 Arcs: (1) -> (1) This digraph is fully evaluated! ---------------------------------------- (13) Obligation: Termination digraph: Nodes: (1) f615_0_visit_NULL(java.lang.Object(List2(o76543103794:0)), i103:0) -> f615_0_visit_NULL(o760:0, arith) :|: i103:0 > -1 && arith = i103:0 - 1 Arcs: (1) -> (1) This digraph is fully evaluated! ---------------------------------------- (14) IntTRSCompressionProof (EQUIVALENT) Compressed rules. ---------------------------------------- (15) Obligation: Rules: f615_0_visit_NULL(java.lang.Object(List2(o76543103794:0:0)), i103:0:0) -> f615_0_visit_NULL(o760:0:0, i103:0:0 - 1) :|: i103:0:0 > -1 ---------------------------------------- (16) TempFilterProof (SOUND) Used the following sort dictionary for filtering: f615_0_visit_NULL(VARIABLE, INTEGER) java.lang.Object(VARIABLE) List2(VARIABLE) Replaced non-predefined constructor symbols by 0. ---------------------------------------- (17) Obligation: Rules: f615_0_visit_NULL(c, i103:0:0) -> f615_0_visit_NULL(o760:0:0, c1) :|: c1 = i103:0:0 - 1 && c = 0 && i103:0:0 > -1 ---------------------------------------- (18) PolynomialOrderProcessor (EQUIVALENT) Found the following polynomial interpretation: [f615_0_visit_NULL(x, x1)] = x1 The following rules are decreasing: f615_0_visit_NULL(c, i103:0:0) -> f615_0_visit_NULL(o760:0:0, c1) :|: c1 = i103:0:0 - 1 && c = 0 && i103:0:0 > -1 The following rules are bounded: f615_0_visit_NULL(c, i103:0:0) -> f615_0_visit_NULL(o760:0:0, c1) :|: c1 = i103:0:0 - 1 && c = 0 && i103:0:0 > -1 ---------------------------------------- (19) YES ---------------------------------------- (20) Obligation: SCC of termination graph based on JBC Program. SCC contains nodes from the following methods: List2.main([Ljava/lang/String;)V SCC calls the following helper methods: Performed SCC analyses: *Used field analysis yielded the following read fields: *Marker field analysis yielded the following relations that could be markers: ---------------------------------------- (21) SCCToIRSProof (SOUND) Transformed FIGraph SCCs to intTRSs. Log: Generated rules. Obtained 18 IRulesP rules: f1007_0_main_Inc(EOS(STATIC_1007), i74, i74) -> f1012_0_main_LE(EOS(STATIC_1012), i74 + -1, i74) :|: TRUE f1012_0_main_LE(EOS(STATIC_1012), i79, i82) -> f1020_0_main_LE(EOS(STATIC_1020), i79, i82) :|: TRUE f1020_0_main_LE(EOS(STATIC_1020), i79, i82) -> f1023_0_main_New(EOS(STATIC_1023), i79) :|: i82 > 0 f1023_0_main_New(EOS(STATIC_1023), i79) -> f1084_0_main_Duplicate(EOS(STATIC_1084), i79) :|: TRUE f1084_0_main_Duplicate(EOS(STATIC_1084), i79) -> f1092_0_main_InvokeMethod(EOS(STATIC_1092), i79) :|: TRUE f1092_0_main_InvokeMethod(EOS(STATIC_1092), i79) -> f1100_0__init__Load(EOS(STATIC_1100), i79) :|: TRUE f1100_0__init__Load(EOS(STATIC_1100), i79) -> f1162_0__init__InvokeMethod(EOS(STATIC_1162), i79) :|: TRUE f1162_0__init__InvokeMethod(EOS(STATIC_1162), i79) -> f1170_0__init__Return(EOS(STATIC_1170), i79) :|: TRUE f1170_0__init__Return(EOS(STATIC_1170), i79) -> f1175_0_main_Store(EOS(STATIC_1175), i79) :|: TRUE f1175_0_main_Store(EOS(STATIC_1175), i79) -> f1206_0_main_Load(EOS(STATIC_1206), i79) :|: TRUE f1206_0_main_Load(EOS(STATIC_1206), i79) -> f1211_0_main_Load(EOS(STATIC_1211), i79) :|: TRUE f1211_0_main_Load(EOS(STATIC_1211), i79) -> f1217_0_main_FieldAccess(EOS(STATIC_1217), i79) :|: TRUE f1217_0_main_FieldAccess(EOS(STATIC_1217), i79) -> f1250_0_main_Load(EOS(STATIC_1250), i79) :|: TRUE f1250_0_main_Load(EOS(STATIC_1250), i79) -> f1546_0_main_Store(EOS(STATIC_1546), i79) :|: TRUE f1546_0_main_Store(EOS(STATIC_1546), i79) -> f1549_0_main_JMP(EOS(STATIC_1549), i79) :|: TRUE f1549_0_main_JMP(EOS(STATIC_1549), i79) -> f1586_0_main_Load(EOS(STATIC_1586), i79) :|: TRUE f1586_0_main_Load(EOS(STATIC_1586), i79) -> f996_0_main_Load(EOS(STATIC_996), i79) :|: TRUE f996_0_main_Load(EOS(STATIC_996), i74) -> f1007_0_main_Inc(EOS(STATIC_1007), i74, i74) :|: TRUE Combined rules. Obtained 1 IRulesP rules: f1007_0_main_Inc(EOS(STATIC_1007), i74:0, i74:0) -> f1007_0_main_Inc(EOS(STATIC_1007), i74:0 - 1, i74:0 - 1) :|: i74:0 > 0 Filtered constant ground arguments: f1007_0_main_Inc(x1, x2, x3) -> f1007_0_main_Inc(x2, x3) EOS(x1) -> EOS Filtered duplicate arguments: f1007_0_main_Inc(x1, x2) -> f1007_0_main_Inc(x2) Finished conversion. Obtained 1 rules.P rules: f1007_0_main_Inc(i74:0) -> f1007_0_main_Inc(i74:0 - 1) :|: i74:0 > 0 ---------------------------------------- (22) Obligation: Rules: f1007_0_main_Inc(i74:0) -> f1007_0_main_Inc(i74:0 - 1) :|: i74:0 > 0 ---------------------------------------- (23) IRSFormatTransformerProof (EQUIVALENT) Reformatted IRS to match normalized format (transformed away non-linear left-hand sides, !=, / and %). ---------------------------------------- (24) Obligation: Rules: f1007_0_main_Inc(i74:0) -> f1007_0_main_Inc(arith) :|: i74:0 > 0 && arith = i74:0 - 1 ---------------------------------------- (25) IRSwTTerminationDigraphProof (EQUIVALENT) Constructed termination digraph! Nodes: (1) f1007_0_main_Inc(i74:0) -> f1007_0_main_Inc(arith) :|: i74:0 > 0 && arith = i74:0 - 1 Arcs: (1) -> (1) This digraph is fully evaluated! ---------------------------------------- (26) Obligation: Termination digraph: Nodes: (1) f1007_0_main_Inc(i74:0) -> f1007_0_main_Inc(arith) :|: i74:0 > 0 && arith = i74:0 - 1 Arcs: (1) -> (1) This digraph is fully evaluated! ---------------------------------------- (27) IntTRSCompressionProof (EQUIVALENT) Compressed rules. ---------------------------------------- (28) Obligation: Rules: f1007_0_main_Inc(i74:0:0) -> f1007_0_main_Inc(i74:0:0 - 1) :|: i74:0:0 > 0 ---------------------------------------- (29) TempFilterProof (SOUND) Used the following sort dictionary for filtering: f1007_0_main_Inc(INTEGER) Replaced non-predefined constructor symbols by 0. ---------------------------------------- (30) Obligation: Rules: f1007_0_main_Inc(i74:0:0) -> f1007_0_main_Inc(c) :|: c = i74:0:0 - 1 && i74:0:0 > 0 ---------------------------------------- (31) PolynomialOrderProcessor (EQUIVALENT) Found the following polynomial interpretation: [f1007_0_main_Inc(x)] = x The following rules are decreasing: f1007_0_main_Inc(i74:0:0) -> f1007_0_main_Inc(c) :|: c = i74:0:0 - 1 && i74:0:0 > 0 The following rules are bounded: f1007_0_main_Inc(i74:0:0) -> f1007_0_main_Inc(c) :|: c = i74:0:0 - 1 && i74:0:0 > 0 ---------------------------------------- (32) YES