/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: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 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, 325 ms] (4) JBCTerminationGraph (5) TerminationGraphToSCCProof [SOUND, 0 ms] (6) AND (7) JBCTerminationSCC (8) SCCToIRSProof [SOUND, 56 ms] (9) IRSwT (10) IRSFormatTransformerProof [EQUIVALENT, 0 ms] (11) IRSwT (12) IRSwTTerminationDigraphProof [EQUIVALENT, 1 ms] (13) IRSwT (14) IntTRSCompressionProof [EQUIVALENT, 0 ms] (15) IRSwT (16) TempFilterProof [SOUND, 41 ms] (17) IntTRS (18) RankingReductionPairProof [EQUIVALENT, 22 ms] (19) YES (20) JBCTerminationSCC (21) SCCToIRSProof [SOUND, 65 ms] (22) IRSwT (23) IRSFormatTransformerProof [EQUIVALENT, 0 ms] (24) IRSwT (25) IRSwTTerminationDigraphProof [EQUIVALENT, 0 ms] (26) IRSwT (27) IntTRSCompressionProof [EQUIVALENT, 0 ms] (28) IRSwT (29) TempFilterProof [SOUND, 3 ms] (30) IntTRS (31) PolynomialOrderProcessor [EQUIVALENT, 0 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 i115) ---------------------------------------- (8) SCCToIRSProof (SOUND) Transformed FIGraph SCCs to intTRSs. Log: Generated rules. Obtained 19 IRulesP rules: f740_0_visit_NULL(EOS(STATIC_740), java.lang.Object(o68sub0), matching1, java.lang.Object(o68sub0), i115) -> f1041_0_visit_NULL(EOS(STATIC_1041), java.lang.Object(o68sub0), 0, java.lang.Object(o68sub0), i115) :|: TRUE && matching1 = 0 f1041_0_visit_NULL(EOS(STATIC_1041), java.lang.Object(o68sub0), matching1, java.lang.Object(o68sub0), i115) -> f1045_0_visit_Load(EOS(STATIC_1045), java.lang.Object(o68sub0), 0, i115) :|: TRUE && matching1 = 0 f1045_0_visit_Load(EOS(STATIC_1045), java.lang.Object(o68sub0), matching1, i115) -> f1081_0_visit_FieldAccess(EOS(STATIC_1081), java.lang.Object(o68sub0), 0, java.lang.Object(o68sub0), i115) :|: TRUE && matching1 = 0 f1081_0_visit_FieldAccess(EOS(STATIC_1081), java.lang.Object(List2(EOC, i82, o77415548671)), matching1, java.lang.Object(List2(EOC, i82, o77415548671)), i115) -> f1093_0_visit_FieldAccess(EOS(STATIC_1093), java.lang.Object(List2(EOC, i82, o77415548671)), 0, java.lang.Object(List2(EOC, i82, o77415548671)), i115) :|: TRUE && matching1 = 0 f1093_0_visit_FieldAccess(EOS(STATIC_1093), java.lang.Object(List2(EOC, i82, o77415548671)), matching1, java.lang.Object(List2(EOC, i82, o77415548671)), i115) -> f1100_0_visit_Load(EOS(STATIC_1100), java.lang.Object(List2(EOC, i82, o77415548671)), 0, i82, i115) :|: TRUE && matching1 = 0 f1100_0_visit_Load(EOS(STATIC_1100), java.lang.Object(List2(EOC, i82, o77415548671)), matching1, i82, i115) -> f1103_0_visit_NE(EOS(STATIC_1103), java.lang.Object(List2(EOC, i82, o77415548671)), 0, i82, 0, i115) :|: TRUE && matching1 = 0 f1103_0_visit_NE(EOS(STATIC_1103), java.lang.Object(List2(EOC, matching1, o77415548671)), matching2, matching3, matching4, i115) -> f1124_0_visit_NE(EOS(STATIC_1124), java.lang.Object(List2(EOC, 0, o77415548671)), 0, 0, 0, i115) :|: i82 = 0 && matching1 = 0 && matching2 = 0 && matching3 = 0 && matching4 = 0 f1124_0_visit_NE(EOS(STATIC_1124), java.lang.Object(List2(EOC, matching1, o77415548671)), matching2, matching3, matching4, i115) -> f1132_0_visit_Load(EOS(STATIC_1132), java.lang.Object(List2(EOC, 0, o77415548671)), 0, i115) :|: TRUE && matching1 = 0 && matching2 = 0 && matching3 = 0 && matching4 = 0 f1132_0_visit_Load(EOS(STATIC_1132), java.lang.Object(List2(EOC, matching1, o77415548671)), matching2, i115) -> f1141_0_visit_Load(EOS(STATIC_1141), java.lang.Object(List2(EOC, 0, o77415548671)), 0, java.lang.Object(List2(EOC, 0, o77415548671)), i115) :|: TRUE && matching1 = 0 && matching2 = 0 f1141_0_visit_Load(EOS(STATIC_1141), java.lang.Object(List2(EOC, matching1, o77415548671)), matching2, java.lang.Object(List2(EOC, matching3, o77415548671)), i115) -> f1150_0_visit_ConstantStackPush(EOS(STATIC_1150), java.lang.Object(List2(EOC, 0, o77415548671)), 0, java.lang.Object(List2(EOC, 0, o77415548671)), 0, i115) :|: TRUE && matching1 = 0 && matching2 = 0 && matching3 = 0 f1150_0_visit_ConstantStackPush(EOS(STATIC_1150), java.lang.Object(List2(EOC, matching1, o77415548671)), matching2, java.lang.Object(List2(EOC, matching3, o77415548671)), matching4, i115) -> f1159_0_visit_IntArithmetic(EOS(STATIC_1159), java.lang.Object(List2(EOC, 0, o77415548671)), 0, java.lang.Object(List2(EOC, 0, o77415548671)), 0, 1, i115) :|: TRUE && matching1 = 0 && matching2 = 0 && matching3 = 0 && matching4 = 0 f1159_0_visit_IntArithmetic(EOS(STATIC_1159), java.lang.Object(List2(EOC, matching1, o77415548671)), matching2, java.lang.Object(List2(EOC, matching3, o77415548671)), matching4, matching5, i115) -> f1173_0_visit_FieldAccess(EOS(STATIC_1173), java.lang.Object(List2(EOC, 0, o77415548671)), 0, java.lang.Object(List2(EOC, 0, o77415548671)), 1, i115) :|: TRUE && matching1 = 0 && matching2 = 0 && matching3 = 0 && matching4 = 0 && matching5 = 1 f1173_0_visit_FieldAccess(EOS(STATIC_1173), java.lang.Object(List2(EOC, matching1, o77415548671)), matching2, java.lang.Object(List2(EOC, matching3, o77415548671)), matching4, i115) -> f1185_0_visit_Load(EOS(STATIC_1185), java.lang.Object(List2(EOC, 1, o77put415548671)), 0, i115 + -1) :|: i115 >= 0 && matching1 = 0 && matching2 = 0 && matching3 = 0 && matching4 = 1 f1185_0_visit_Load(EOS(STATIC_1185), java.lang.Object(List2(EOC, matching1, o77415548671)), matching2, i115) -> f1193_0_visit_FieldAccess(EOS(STATIC_1193), 0, java.lang.Object(List2(EOC, 1, o77415548671)), i115) :|: TRUE && matching1 = 1 && matching2 = 0 f1193_0_visit_FieldAccess(EOS(STATIC_1193), matching1, java.lang.Object(List2(EOC, matching2, o77415548671)), i115) -> f1198_0_visit_Store(EOS(STATIC_1198), 0, o770, i115) :|: TRUE && matching1 = 0 && matching2 = 1 f1198_0_visit_Store(EOS(STATIC_1198), matching1, o770, i115) -> f1204_0_visit_JMP(EOS(STATIC_1204), o770, 0, i115) :|: TRUE && matching1 = 0 f1204_0_visit_JMP(EOS(STATIC_1204), o770, matching1, i115) -> f1207_0_visit_Load(EOS(STATIC_1207), o770, 0, i115) :|: TRUE && matching1 = 0 f1207_0_visit_Load(EOS(STATIC_1207), o770, matching1, i115) -> f726_0_visit_Load(EOS(STATIC_726), o770, 0, i115) :|: TRUE && matching1 = 0 f726_0_visit_Load(EOS(STATIC_726), o590, matching1, i115) -> f740_0_visit_NULL(EOS(STATIC_740), o590, 0, o590, i115) :|: TRUE && matching1 = 0 Combined rules. Obtained 1 IRulesP rules: f740_0_visit_NULL(EOS(STATIC_740), java.lang.Object(List2(EOC, 0, o77415548671:0)), 0, java.lang.Object(List2(EOC, 0, o77415548671:0)), i115:0) -> f740_0_visit_NULL(EOS(STATIC_740), o770:0, 0, o770:0, i115:0 - 1) :|: i115:0 > -1 Filtered constant ground arguments: f740_0_visit_NULL(x1, x2, x3, x4, x5) -> f740_0_visit_NULL(x2, x4, x5) EOS(x1) -> EOS List2(x1, x2, x3) -> List2(x3) Filtered duplicate arguments: f740_0_visit_NULL(x1, x2, x3) -> f740_0_visit_NULL(x2, x3) Finished conversion. Obtained 1 rules.P rules: f740_0_visit_NULL(java.lang.Object(List2(o77415548671:0)), i115:0) -> f740_0_visit_NULL(o770:0, i115:0 - 1) :|: i115:0 > -1 ---------------------------------------- (9) Obligation: Rules: f740_0_visit_NULL(java.lang.Object(List2(o77415548671:0)), i115:0) -> f740_0_visit_NULL(o770:0, i115:0 - 1) :|: i115:0 > -1 ---------------------------------------- (10) IRSFormatTransformerProof (EQUIVALENT) Reformatted IRS to match normalized format (transformed away non-linear left-hand sides, !=, / and %). ---------------------------------------- (11) Obligation: Rules: f740_0_visit_NULL(java.lang.Object(List2(o77415548671:0)), i115:0) -> f740_0_visit_NULL(o770:0, arith) :|: i115:0 > -1 && arith = i115:0 - 1 ---------------------------------------- (12) IRSwTTerminationDigraphProof (EQUIVALENT) Constructed termination digraph! Nodes: (1) f740_0_visit_NULL(java.lang.Object(List2(o77415548671:0)), i115:0) -> f740_0_visit_NULL(o770:0, arith) :|: i115:0 > -1 && arith = i115:0 - 1 Arcs: (1) -> (1) This digraph is fully evaluated! ---------------------------------------- (13) Obligation: Termination digraph: Nodes: (1) f740_0_visit_NULL(java.lang.Object(List2(o77415548671:0)), i115:0) -> f740_0_visit_NULL(o770:0, arith) :|: i115:0 > -1 && arith = i115:0 - 1 Arcs: (1) -> (1) This digraph is fully evaluated! ---------------------------------------- (14) IntTRSCompressionProof (EQUIVALENT) Compressed rules. ---------------------------------------- (15) Obligation: Rules: f740_0_visit_NULL(java.lang.Object(List2(o77415548671:0:0)), i115:0:0) -> f740_0_visit_NULL(o770:0:0, i115:0:0 - 1) :|: i115:0:0 > -1 ---------------------------------------- (16) TempFilterProof (SOUND) Used the following sort dictionary for filtering: f740_0_visit_NULL(VARIABLE, INTEGER) java.lang.Object(VARIABLE) List2(VARIABLE) Replaced non-predefined constructor symbols by 0. ---------------------------------------- (17) Obligation: Rules: f740_0_visit_NULL(c, i115:0:0) -> f740_0_visit_NULL(o770:0:0, c1) :|: c1 = i115:0:0 - 1 && c = 0 && i115:0:0 > -1 ---------------------------------------- (18) RankingReductionPairProof (EQUIVALENT) Interpretation: [ f740_0_visit_NULL ] = f740_0_visit_NULL_2 The following rules are decreasing: f740_0_visit_NULL(c, i115:0:0) -> f740_0_visit_NULL(o770:0:0, c1) :|: c1 = i115:0:0 - 1 && c = 0 && i115:0:0 > -1 The following rules are bounded: f740_0_visit_NULL(c, i115:0:0) -> f740_0_visit_NULL(o770:0:0, c1) :|: c1 = i115:0:0 - 1 && c = 0 && i115: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: f1085_0_main_Inc(EOS(STATIC_1085), i78, i78) -> f1097_0_main_LE(EOS(STATIC_1097), i78 + -1, i78) :|: TRUE f1097_0_main_LE(EOS(STATIC_1097), i83, i86) -> f1102_0_main_LE(EOS(STATIC_1102), i83, i86) :|: TRUE f1102_0_main_LE(EOS(STATIC_1102), i83, i86) -> f1105_0_main_New(EOS(STATIC_1105), i83) :|: i86 > 0 f1105_0_main_New(EOS(STATIC_1105), i83) -> f1130_0_main_Duplicate(EOS(STATIC_1130), i83) :|: TRUE f1130_0_main_Duplicate(EOS(STATIC_1130), i83) -> f1136_0_main_InvokeMethod(EOS(STATIC_1136), i83) :|: TRUE f1136_0_main_InvokeMethod(EOS(STATIC_1136), i83) -> f1147_0__init__Load(EOS(STATIC_1147), i83) :|: TRUE f1147_0__init__Load(EOS(STATIC_1147), i83) -> f1171_0__init__InvokeMethod(EOS(STATIC_1171), i83) :|: TRUE f1171_0__init__InvokeMethod(EOS(STATIC_1171), i83) -> f1183_0__init__Return(EOS(STATIC_1183), i83) :|: TRUE f1183_0__init__Return(EOS(STATIC_1183), i83) -> f1192_0_main_Store(EOS(STATIC_1192), i83) :|: TRUE f1192_0_main_Store(EOS(STATIC_1192), i83) -> f1196_0_main_Load(EOS(STATIC_1196), i83) :|: TRUE f1196_0_main_Load(EOS(STATIC_1196), i83) -> f1201_0_main_Load(EOS(STATIC_1201), i83) :|: TRUE f1201_0_main_Load(EOS(STATIC_1201), i83) -> f1205_0_main_FieldAccess(EOS(STATIC_1205), i83) :|: TRUE f1205_0_main_FieldAccess(EOS(STATIC_1205), i83) -> f1250_0_main_Load(EOS(STATIC_1250), i83) :|: TRUE f1250_0_main_Load(EOS(STATIC_1250), i83) -> f1895_0_main_Store(EOS(STATIC_1895), i83) :|: TRUE f1895_0_main_Store(EOS(STATIC_1895), i83) -> f1904_0_main_JMP(EOS(STATIC_1904), i83) :|: TRUE f1904_0_main_JMP(EOS(STATIC_1904), i83) -> f1933_0_main_Load(EOS(STATIC_1933), i83) :|: TRUE f1933_0_main_Load(EOS(STATIC_1933), i83) -> f1077_0_main_Load(EOS(STATIC_1077), i83) :|: TRUE f1077_0_main_Load(EOS(STATIC_1077), i78) -> f1085_0_main_Inc(EOS(STATIC_1085), i78, i78) :|: TRUE Combined rules. Obtained 1 IRulesP rules: f1085_0_main_Inc(EOS(STATIC_1085), i78:0, i78:0) -> f1085_0_main_Inc(EOS(STATIC_1085), i78:0 - 1, i78:0 - 1) :|: i78:0 > 0 Filtered constant ground arguments: f1085_0_main_Inc(x1, x2, x3) -> f1085_0_main_Inc(x2, x3) EOS(x1) -> EOS Filtered duplicate arguments: f1085_0_main_Inc(x1, x2) -> f1085_0_main_Inc(x2) Finished conversion. Obtained 1 rules.P rules: f1085_0_main_Inc(i78:0) -> f1085_0_main_Inc(i78:0 - 1) :|: i78:0 > 0 ---------------------------------------- (22) Obligation: Rules: f1085_0_main_Inc(i78:0) -> f1085_0_main_Inc(i78:0 - 1) :|: i78:0 > 0 ---------------------------------------- (23) IRSFormatTransformerProof (EQUIVALENT) Reformatted IRS to match normalized format (transformed away non-linear left-hand sides, !=, / and %). ---------------------------------------- (24) Obligation: Rules: f1085_0_main_Inc(i78:0) -> f1085_0_main_Inc(arith) :|: i78:0 > 0 && arith = i78:0 - 1 ---------------------------------------- (25) IRSwTTerminationDigraphProof (EQUIVALENT) Constructed termination digraph! Nodes: (1) f1085_0_main_Inc(i78:0) -> f1085_0_main_Inc(arith) :|: i78:0 > 0 && arith = i78:0 - 1 Arcs: (1) -> (1) This digraph is fully evaluated! ---------------------------------------- (26) Obligation: Termination digraph: Nodes: (1) f1085_0_main_Inc(i78:0) -> f1085_0_main_Inc(arith) :|: i78:0 > 0 && arith = i78:0 - 1 Arcs: (1) -> (1) This digraph is fully evaluated! ---------------------------------------- (27) IntTRSCompressionProof (EQUIVALENT) Compressed rules. ---------------------------------------- (28) Obligation: Rules: f1085_0_main_Inc(i78:0:0) -> f1085_0_main_Inc(i78:0:0 - 1) :|: i78:0:0 > 0 ---------------------------------------- (29) TempFilterProof (SOUND) Used the following sort dictionary for filtering: f1085_0_main_Inc(INTEGER) Replaced non-predefined constructor symbols by 0. ---------------------------------------- (30) Obligation: Rules: f1085_0_main_Inc(i78:0:0) -> f1085_0_main_Inc(c) :|: c = i78:0:0 - 1 && i78:0:0 > 0 ---------------------------------------- (31) PolynomialOrderProcessor (EQUIVALENT) Found the following polynomial interpretation: [f1085_0_main_Inc(x)] = x The following rules are decreasing: f1085_0_main_Inc(i78:0:0) -> f1085_0_main_Inc(c) :|: c = i78:0:0 - 1 && i78:0:0 > 0 The following rules are bounded: f1085_0_main_Inc(i78:0:0) -> f1085_0_main_Inc(c) :|: c = i78:0:0 - 1 && i78:0:0 > 0 ---------------------------------------- (32) YES