7.77/2.94 YES 8.01/2.97 proof of /export/starexec/sandbox/benchmark/theBenchmark.jar 8.01/2.97 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 8.01/2.97 8.01/2.97 8.01/2.97 termination of the given Bare JBC problem could be proven: 8.01/2.97 8.01/2.97 (0) Bare JBC problem 8.01/2.97 (1) BareJBCToJBCProof [EQUIVALENT, 95 ms] 8.01/2.97 (2) JBC problem 8.01/2.97 (3) JBCToGraph [EQUIVALENT, 506 ms] 8.01/2.97 (4) JBCTerminationGraph 8.01/2.97 (5) TerminationGraphToSCCProof [SOUND, 0 ms] 8.01/2.97 (6) AND 8.01/2.97 (7) JBCTerminationSCC 8.01/2.97 (8) SCCToIRSProof [SOUND, 143 ms] 8.01/2.97 (9) IRSwT 8.01/2.97 (10) IRSFormatTransformerProof [EQUIVALENT, 0 ms] 8.01/2.97 (11) IRSwT 8.01/2.97 (12) IRSwTTerminationDigraphProof [EQUIVALENT, 38 ms] 8.01/2.97 (13) IRSwT 8.01/2.97 (14) IntTRSCompressionProof [EQUIVALENT, 0 ms] 8.01/2.97 (15) IRSwT 8.01/2.97 (16) TempFilterProof [SOUND, 32 ms] 8.01/2.97 (17) IntTRS 8.01/2.97 (18) PolynomialOrderProcessor [EQUIVALENT, 13 ms] 8.01/2.97 (19) YES 8.01/2.97 (20) JBCTerminationSCC 8.01/2.97 (21) SCCToIRSProof [SOUND, 51 ms] 8.01/2.97 (22) IRSwT 8.01/2.97 (23) IRSFormatTransformerProof [EQUIVALENT, 0 ms] 8.01/2.97 (24) IRSwT 8.01/2.97 (25) IRSwTTerminationDigraphProof [EQUIVALENT, 9 ms] 8.01/2.97 (26) IRSwT 8.01/2.97 (27) IntTRSCompressionProof [EQUIVALENT, 0 ms] 8.01/2.97 (28) IRSwT 8.01/2.97 (29) TempFilterProof [SOUND, 19 ms] 8.01/2.97 (30) IntTRS 8.01/2.97 (31) RankingReductionPairProof [EQUIVALENT, 10 ms] 8.01/2.97 (32) YES 8.01/2.97 8.01/2.97 8.01/2.97 ---------------------------------------- 8.01/2.97 8.01/2.97 (0) 8.01/2.97 Obligation: 8.01/2.97 need to prove termination of the following program: 8.01/2.97 public class ListContent{ 8.01/2.97 8.01/2.97 public static void main(String[] args) { 8.01/2.97 Random.args = args; 8.01/2.97 IntList l = IntList.createIntList(); 8.01/2.97 8.01/2.97 while (l.value > 0) l.value--; 8.01/2.97 } 8.01/2.97 8.01/2.97 } 8.01/2.97 8.01/2.97 class IntList { 8.01/2.97 int value; 8.01/2.97 IntList next; 8.01/2.97 8.01/2.97 public IntList(int value, IntList next) { 8.01/2.97 this.value = value; 8.01/2.97 this.next = next; 8.01/2.97 } 8.01/2.97 8.01/2.97 public static IntList createIntList() { 8.01/2.97 8.01/2.97 int i = Random.random(); 8.01/2.97 IntList l = null; 8.01/2.97 8.01/2.97 while (i > 0) { 8.01/2.97 l = new IntList(Random.random(), l); 8.01/2.97 i--; 8.01/2.97 } 8.01/2.97 8.01/2.97 return l; 8.01/2.97 } 8.01/2.97 } 8.01/2.97 8.01/2.97 8.01/2.97 public class Random { 8.01/2.97 static String[] args; 8.01/2.97 static int index = 0; 8.01/2.97 8.01/2.97 public static int random() { 8.01/2.97 String string = args[index]; 8.01/2.97 index++; 8.01/2.97 return string.length(); 8.01/2.97 } 8.01/2.97 } 8.01/2.97 8.01/2.97 8.01/2.97 8.01/2.97 ---------------------------------------- 8.01/2.97 8.01/2.97 (1) BareJBCToJBCProof (EQUIVALENT) 8.01/2.97 initialized classpath 8.01/2.97 ---------------------------------------- 8.01/2.97 8.01/2.97 (2) 8.01/2.97 Obligation: 8.01/2.97 need to prove termination of the following program: 8.01/2.97 public class ListContent{ 8.01/2.97 8.01/2.97 public static void main(String[] args) { 8.01/2.97 Random.args = args; 8.01/2.97 IntList l = IntList.createIntList(); 8.01/2.97 8.01/2.97 while (l.value > 0) l.value--; 8.01/2.97 } 8.01/2.97 8.01/2.97 } 8.01/2.97 8.01/2.97 class IntList { 8.01/2.97 int value; 8.01/2.97 IntList next; 8.01/2.97 8.01/2.97 public IntList(int value, IntList next) { 8.01/2.97 this.value = value; 8.01/2.97 this.next = next; 8.01/2.97 } 8.01/2.97 8.01/2.97 public static IntList createIntList() { 8.01/2.97 8.01/2.97 int i = Random.random(); 8.01/2.97 IntList l = null; 8.01/2.97 8.01/2.97 while (i > 0) { 8.01/2.97 l = new IntList(Random.random(), l); 8.01/2.97 i--; 8.01/2.97 } 8.01/2.97 8.01/2.97 return l; 8.01/2.97 } 8.01/2.97 } 8.01/2.97 8.01/2.97 8.01/2.97 public class Random { 8.01/2.97 static String[] args; 8.01/2.97 static int index = 0; 8.01/2.97 8.01/2.97 public static int random() { 8.01/2.97 String string = args[index]; 8.01/2.97 index++; 8.01/2.97 return string.length(); 8.01/2.97 } 8.01/2.97 } 8.01/2.97 8.01/2.97 8.01/2.97 8.01/2.97 ---------------------------------------- 8.06/2.97 8.06/2.97 (3) JBCToGraph (EQUIVALENT) 8.06/2.97 Constructed TerminationGraph. 8.06/2.97 ---------------------------------------- 8.06/2.97 8.06/2.97 (4) 8.06/2.97 Obligation: 8.06/2.97 Termination Graph based on JBC Program: 8.06/2.97 ListContent.main([Ljava/lang/String;)V: Graph of 65 nodes with 1 SCC. 8.06/2.97 8.06/2.97 8.06/2.97 8.06/2.97 IntList.createIntList()LIntList;: Graph of 277 nodes with 1 SCC. 8.06/2.97 8.06/2.97 8.06/2.97 8.06/2.97 8.06/2.97 8.06/2.97 ---------------------------------------- 8.06/2.97 8.06/2.97 (5) TerminationGraphToSCCProof (SOUND) 8.06/2.97 Splitted TerminationGraph to 2 SCCss. 8.06/2.97 ---------------------------------------- 8.06/2.97 8.06/2.97 (6) 8.06/2.97 Complex Obligation (AND) 8.06/2.97 8.06/2.97 ---------------------------------------- 8.06/2.97 8.06/2.97 (7) 8.06/2.97 Obligation: 8.06/2.97 SCC of termination graph based on JBC Program. 8.06/2.97 SCC contains nodes from the following methods: IntList.createIntList()LIntList; 8.06/2.97 SCC calls the following helper methods: 8.06/2.97 Performed SCC analyses: 8.06/2.97 *Used field analysis yielded the following read fields: 8.06/2.97 *java.lang.String: [count] 8.06/2.97 *Marker field analysis yielded the following relations that could be markers: 8.06/2.97 8.06/2.97 ---------------------------------------- 8.06/2.97 8.06/2.97 (8) SCCToIRSProof (SOUND) 8.06/2.97 Transformed FIGraph SCCs to intTRSs. Log: 8.06/2.97 Generated rules. Obtained 39 IRulesP rules: 8.06/2.97 f2683_0_createIntList_LE(EOS(STATIC_2683(java.lang.Object(ARRAY(i6)))), i521, i521) -> f2699_0_createIntList_LE(EOS(STATIC_2699(java.lang.Object(ARRAY(i6)))), i521, i521) :|: TRUE 8.06/2.97 f2699_0_createIntList_LE(EOS(STATIC_2699(java.lang.Object(ARRAY(i6)))), i521, i521) -> f2705_0_createIntList_New(EOS(STATIC_2705(java.lang.Object(ARRAY(i6)))), i521) :|: i521 > 0 8.06/2.97 f2705_0_createIntList_New(EOS(STATIC_2705(java.lang.Object(ARRAY(i6)))), i521) -> f2711_0_createIntList_Duplicate(EOS(STATIC_2711(java.lang.Object(ARRAY(i6)))), i521) :|: TRUE 8.06/2.97 f2711_0_createIntList_Duplicate(EOS(STATIC_2711(java.lang.Object(ARRAY(i6)))), i521) -> f2715_0_createIntList_InvokeMethod(EOS(STATIC_2715(java.lang.Object(ARRAY(i6)))), i521) :|: TRUE 8.06/2.97 f2715_0_createIntList_InvokeMethod(EOS(STATIC_2715(java.lang.Object(ARRAY(i6)))), i521) -> f2730_0_random_FieldAccess(EOS(STATIC_2730(java.lang.Object(ARRAY(i6)))), i521) :|: TRUE 8.06/2.97 f2730_0_random_FieldAccess(EOS(STATIC_2730(java.lang.Object(ARRAY(i6)))), i521) -> f2743_0_random_FieldAccess(EOS(STATIC_2743(java.lang.Object(ARRAY(i6)))), i521, java.lang.Object(ARRAY(i6))) :|: TRUE 8.06/2.97 f2743_0_random_FieldAccess(EOS(STATIC_2743(java.lang.Object(ARRAY(i6)))), i521, java.lang.Object(ARRAY(i6))) -> f2752_0_random_ArrayAccess(EOS(STATIC_2752(java.lang.Object(ARRAY(i6)))), i521, java.lang.Object(ARRAY(i6))) :|: TRUE 8.06/2.97 f2752_0_random_ArrayAccess(EOS(STATIC_2752(java.lang.Object(ARRAY(i6)))), i521, java.lang.Object(ARRAY(i6))) -> f2754_0_random_ArrayAccess(EOS(STATIC_2754(java.lang.Object(ARRAY(i6)))), i521, java.lang.Object(ARRAY(i6))) :|: TRUE 8.06/2.97 f2754_0_random_ArrayAccess(EOS(STATIC_2754(java.lang.Object(ARRAY(i6)))), i521, java.lang.Object(ARRAY(i6))) -> f2760_0_random_Store(EOS(STATIC_2760(java.lang.Object(ARRAY(i6)))), i521, o294) :|: TRUE 8.06/2.97 f2760_0_random_Store(EOS(STATIC_2760(java.lang.Object(ARRAY(i6)))), i521, o294) -> f2831_0_random_FieldAccess(EOS(STATIC_2831(java.lang.Object(ARRAY(i6)))), i521, o294) :|: TRUE 8.06/2.97 f2831_0_random_FieldAccess(EOS(STATIC_2831(java.lang.Object(ARRAY(i6)))), i521, o294) -> f2836_0_random_ConstantStackPush(EOS(STATIC_2836(java.lang.Object(ARRAY(i6)))), i521, o294) :|: TRUE 8.06/2.97 f2836_0_random_ConstantStackPush(EOS(STATIC_2836(java.lang.Object(ARRAY(i6)))), i521, o294) -> f2845_0_random_IntArithmetic(EOS(STATIC_2845(java.lang.Object(ARRAY(i6)))), i521, o294) :|: TRUE 8.06/2.97 f2845_0_random_IntArithmetic(EOS(STATIC_2845(java.lang.Object(ARRAY(i6)))), i521, o294) -> f2850_0_random_FieldAccess(EOS(STATIC_2850(java.lang.Object(ARRAY(i6)))), i521, o294) :|: TRUE 8.06/2.97 f2850_0_random_FieldAccess(EOS(STATIC_2850(java.lang.Object(ARRAY(i6)))), i521, o294) -> f2855_0_random_Load(EOS(STATIC_2855(java.lang.Object(ARRAY(i6)))), i521, o294) :|: TRUE 8.06/2.97 f2855_0_random_Load(EOS(STATIC_2855(java.lang.Object(ARRAY(i6)))), i521, o294) -> f2870_0_random_InvokeMethod(EOS(STATIC_2870(java.lang.Object(ARRAY(i6)))), i521, o294) :|: TRUE 8.06/2.97 f2870_0_random_InvokeMethod(EOS(STATIC_2870(java.lang.Object(ARRAY(i6)))), i521, java.lang.Object(o306sub)) -> f2876_0_random_InvokeMethod(EOS(STATIC_2876(java.lang.Object(ARRAY(i6)))), i521, java.lang.Object(o306sub)) :|: TRUE 8.06/2.97 f2876_0_random_InvokeMethod(EOS(STATIC_2876(java.lang.Object(ARRAY(i6)))), i521, java.lang.Object(o307sub)) -> f2880_0_random_InvokeMethod(EOS(STATIC_2880(java.lang.Object(ARRAY(i6)))), i521, java.lang.Object(o307sub)) :|: TRUE 8.06/2.97 f2880_0_random_InvokeMethod(EOS(STATIC_2880(java.lang.Object(ARRAY(i6)))), i521, java.lang.Object(o307sub)) -> f2886_0_length_Load(EOS(STATIC_2886(java.lang.Object(ARRAY(i6)))), i521, java.lang.Object(o307sub)) :|: TRUE 8.06/2.97 f2886_0_length_Load(EOS(STATIC_2886(java.lang.Object(ARRAY(i6)))), i521, java.lang.Object(o307sub)) -> f2913_0_length_FieldAccess(EOS(STATIC_2913(java.lang.Object(ARRAY(i6)))), i521, java.lang.Object(o307sub)) :|: TRUE 8.06/2.97 f2913_0_length_FieldAccess(EOS(STATIC_2913(java.lang.Object(ARRAY(i6)))), i521, java.lang.Object(java.lang.String(EOC, i580))) -> f2925_0_length_FieldAccess(EOS(STATIC_2925(java.lang.Object(ARRAY(i6)))), i521, java.lang.Object(java.lang.String(EOC, i580))) :|: TRUE 8.06/2.97 f2925_0_length_FieldAccess(EOS(STATIC_2925(java.lang.Object(ARRAY(i6)))), i521, java.lang.Object(java.lang.String(EOC, i580))) -> f2931_0_length_Return(EOS(STATIC_2931(java.lang.Object(ARRAY(i6)))), i521) :|: TRUE 8.06/2.97 f2931_0_length_Return(EOS(STATIC_2931(java.lang.Object(ARRAY(i6)))), i521) -> f2938_0_random_Return(EOS(STATIC_2938(java.lang.Object(ARRAY(i6)))), i521) :|: TRUE 8.06/2.97 f2938_0_random_Return(EOS(STATIC_2938(java.lang.Object(ARRAY(i6)))), i521) -> f2949_0_createIntList_Load(EOS(STATIC_2949(java.lang.Object(ARRAY(i6)))), i521) :|: TRUE 8.06/2.97 f2949_0_createIntList_Load(EOS(STATIC_2949(java.lang.Object(ARRAY(i6)))), i521) -> f2958_0_createIntList_InvokeMethod(EOS(STATIC_2958(java.lang.Object(ARRAY(i6)))), i521) :|: TRUE 8.06/2.97 f2958_0_createIntList_InvokeMethod(EOS(STATIC_2958(java.lang.Object(ARRAY(i6)))), i521) -> f2971_0__init__Load(EOS(STATIC_2971(java.lang.Object(ARRAY(i6)))), i521) :|: TRUE 8.06/2.97 f2971_0__init__Load(EOS(STATIC_2971(java.lang.Object(ARRAY(i6)))), i521) -> f3016_0__init__InvokeMethod(EOS(STATIC_3016(java.lang.Object(ARRAY(i6)))), i521) :|: TRUE 8.06/2.97 f3016_0__init__InvokeMethod(EOS(STATIC_3016(java.lang.Object(ARRAY(i6)))), i521) -> f3030_0__init__Load(EOS(STATIC_3030(java.lang.Object(ARRAY(i6)))), i521) :|: TRUE 8.06/2.97 f3030_0__init__Load(EOS(STATIC_3030(java.lang.Object(ARRAY(i6)))), i521) -> f3043_0__init__Load(EOS(STATIC_3043(java.lang.Object(ARRAY(i6)))), i521) :|: TRUE 8.06/2.97 f3043_0__init__Load(EOS(STATIC_3043(java.lang.Object(ARRAY(i6)))), i521) -> f3053_0__init__FieldAccess(EOS(STATIC_3053(java.lang.Object(ARRAY(i6)))), i521) :|: TRUE 8.06/2.97 f3053_0__init__FieldAccess(EOS(STATIC_3053(java.lang.Object(ARRAY(i6)))), i521) -> f3066_0__init__Load(EOS(STATIC_3066(java.lang.Object(ARRAY(i6)))), i521) :|: TRUE 8.06/2.97 f3066_0__init__Load(EOS(STATIC_3066(java.lang.Object(ARRAY(i6)))), i521) -> f3084_0__init__Load(EOS(STATIC_3084(java.lang.Object(ARRAY(i6)))), i521) :|: TRUE 8.06/2.97 f3084_0__init__Load(EOS(STATIC_3084(java.lang.Object(ARRAY(i6)))), i521) -> f3096_0__init__FieldAccess(EOS(STATIC_3096(java.lang.Object(ARRAY(i6)))), i521) :|: TRUE 8.06/2.97 f3096_0__init__FieldAccess(EOS(STATIC_3096(java.lang.Object(ARRAY(i6)))), i521) -> f3111_0__init__Return(EOS(STATIC_3111(java.lang.Object(ARRAY(i6)))), i521) :|: TRUE 8.06/2.97 f3111_0__init__Return(EOS(STATIC_3111(java.lang.Object(ARRAY(i6)))), i521) -> f3122_0_createIntList_Store(EOS(STATIC_3122(java.lang.Object(ARRAY(i6)))), i521) :|: TRUE 8.06/2.97 f3122_0_createIntList_Store(EOS(STATIC_3122(java.lang.Object(ARRAY(i6)))), i521) -> f3134_0_createIntList_Inc(EOS(STATIC_3134(java.lang.Object(ARRAY(i6)))), i521) :|: TRUE 8.06/2.97 f3134_0_createIntList_Inc(EOS(STATIC_3134(java.lang.Object(ARRAY(i6)))), i521) -> f3144_0_createIntList_JMP(EOS(STATIC_3144(java.lang.Object(ARRAY(i6)))), i521 + -1) :|: TRUE 8.06/2.97 f3144_0_createIntList_JMP(EOS(STATIC_3144(java.lang.Object(ARRAY(i6)))), i620) -> f3168_0_createIntList_Load(EOS(STATIC_3168(java.lang.Object(ARRAY(i6)))), i620) :|: TRUE 8.06/2.97 f3168_0_createIntList_Load(EOS(STATIC_3168(java.lang.Object(ARRAY(i6)))), i620) -> f2647_0_createIntList_Load(EOS(STATIC_2647(java.lang.Object(ARRAY(i6)))), i620) :|: TRUE 8.06/2.97 f2647_0_createIntList_Load(EOS(STATIC_2647(java.lang.Object(ARRAY(i6)))), i489) -> f2683_0_createIntList_LE(EOS(STATIC_2683(java.lang.Object(ARRAY(i6)))), i489, i489) :|: TRUE 8.06/2.97 Combined rules. Obtained 1 IRulesP rules: 8.06/2.97 f2683_0_createIntList_LE(EOS(STATIC_2683(java.lang.Object(ARRAY(i6:0)))), i521:0, i521:0) -> f2683_0_createIntList_LE(EOS(STATIC_2683(java.lang.Object(ARRAY(i6:0)))), i521:0 - 1, i521:0 - 1) :|: i521:0 > 0 8.06/2.97 Filtered duplicate arguments: 8.06/2.97 f2683_0_createIntList_LE(x1, x2, x3) -> f2683_0_createIntList_LE(x1, x3) 8.06/2.97 Filtered unneeded arguments: 8.06/2.97 f2683_0_createIntList_LE(x1, x2) -> f2683_0_createIntList_LE(x2) 8.06/2.97 Finished conversion. Obtained 1 rules.P rules: 8.06/2.97 f2683_0_createIntList_LE(i521:0) -> f2683_0_createIntList_LE(i521:0 - 1) :|: i521:0 > 0 8.06/2.97 8.06/2.97 ---------------------------------------- 8.06/2.97 8.06/2.97 (9) 8.06/2.97 Obligation: 8.06/2.97 Rules: 8.06/2.97 f2683_0_createIntList_LE(i521:0) -> f2683_0_createIntList_LE(i521:0 - 1) :|: i521:0 > 0 8.06/2.97 8.06/2.97 ---------------------------------------- 8.06/2.97 8.06/2.97 (10) IRSFormatTransformerProof (EQUIVALENT) 8.06/2.97 Reformatted IRS to match normalized format (transformed away non-linear left-hand sides, !=, / and %). 8.06/2.97 ---------------------------------------- 8.06/2.97 8.06/2.97 (11) 8.06/2.97 Obligation: 8.06/2.97 Rules: 8.06/2.97 f2683_0_createIntList_LE(i521:0) -> f2683_0_createIntList_LE(arith) :|: i521:0 > 0 && arith = i521:0 - 1 8.06/2.97 8.06/2.97 ---------------------------------------- 8.06/2.97 8.06/2.97 (12) IRSwTTerminationDigraphProof (EQUIVALENT) 8.06/2.97 Constructed termination digraph! 8.06/2.97 Nodes: 8.06/2.97 (1) f2683_0_createIntList_LE(i521:0) -> f2683_0_createIntList_LE(arith) :|: i521:0 > 0 && arith = i521:0 - 1 8.06/2.97 8.06/2.97 Arcs: 8.06/2.97 (1) -> (1) 8.06/2.97 8.06/2.97 This digraph is fully evaluated! 8.06/2.97 ---------------------------------------- 8.06/2.97 8.06/2.97 (13) 8.06/2.97 Obligation: 8.06/2.97 8.06/2.97 Termination digraph: 8.06/2.97 Nodes: 8.06/2.97 (1) f2683_0_createIntList_LE(i521:0) -> f2683_0_createIntList_LE(arith) :|: i521:0 > 0 && arith = i521:0 - 1 8.06/2.97 8.06/2.97 Arcs: 8.06/2.97 (1) -> (1) 8.06/2.97 8.06/2.97 This digraph is fully evaluated! 8.06/2.97 8.06/2.97 ---------------------------------------- 8.06/2.97 8.06/2.97 (14) IntTRSCompressionProof (EQUIVALENT) 8.06/2.97 Compressed rules. 8.06/2.97 ---------------------------------------- 8.06/2.97 8.06/2.97 (15) 8.06/2.97 Obligation: 8.06/2.97 Rules: 8.06/2.97 f2683_0_createIntList_LE(i521:0:0) -> f2683_0_createIntList_LE(i521:0:0 - 1) :|: i521:0:0 > 0 8.06/2.97 8.06/2.97 ---------------------------------------- 8.06/2.97 8.06/2.97 (16) TempFilterProof (SOUND) 8.06/2.97 Used the following sort dictionary for filtering: 8.06/2.97 f2683_0_createIntList_LE(INTEGER) 8.06/2.97 Replaced non-predefined constructor symbols by 0. 8.06/2.97 ---------------------------------------- 8.06/2.97 8.06/2.97 (17) 8.06/2.97 Obligation: 8.06/2.97 Rules: 8.06/2.97 f2683_0_createIntList_LE(i521:0:0) -> f2683_0_createIntList_LE(c) :|: c = i521:0:0 - 1 && i521:0:0 > 0 8.06/2.97 8.06/2.97 ---------------------------------------- 8.06/2.97 8.06/2.97 (18) PolynomialOrderProcessor (EQUIVALENT) 8.06/2.97 Found the following polynomial interpretation: 8.06/2.97 [f2683_0_createIntList_LE(x)] = x 8.06/2.97 8.06/2.97 The following rules are decreasing: 8.06/2.97 f2683_0_createIntList_LE(i521:0:0) -> f2683_0_createIntList_LE(c) :|: c = i521:0:0 - 1 && i521:0:0 > 0 8.06/2.97 The following rules are bounded: 8.06/2.97 f2683_0_createIntList_LE(i521:0:0) -> f2683_0_createIntList_LE(c) :|: c = i521:0:0 - 1 && i521:0:0 > 0 8.06/2.97 8.06/2.97 ---------------------------------------- 8.06/2.97 8.06/2.97 (19) 8.06/2.97 YES 8.06/2.97 8.06/2.97 ---------------------------------------- 8.06/2.97 8.06/2.97 (20) 8.06/2.97 Obligation: 8.06/2.97 SCC of termination graph based on JBC Program. 8.06/2.97 SCC contains nodes from the following methods: ListContent.main([Ljava/lang/String;)V 8.06/2.97 SCC calls the following helper methods: 8.06/2.97 Performed SCC analyses: 8.06/2.97 *Used field analysis yielded the following read fields: 8.06/2.97 *IntList: [value] 8.06/2.97 *Marker field analysis yielded the following relations that could be markers: 8.06/2.97 8.06/2.97 ---------------------------------------- 8.06/2.97 8.06/2.97 (21) SCCToIRSProof (SOUND) 8.06/2.97 Transformed FIGraph SCCs to intTRSs. Log: 8.06/2.97 Generated rules. Obtained 14 IRulesP rules: 8.06/2.97 f2147_0_main_FieldAccess(EOS(STATIC_2147), java.lang.Object(o210sub), java.lang.Object(o210sub)) -> f2152_0_main_FieldAccess(EOS(STATIC_2152), java.lang.Object(o210sub), java.lang.Object(o210sub)) :|: TRUE 8.06/2.97 f2152_0_main_FieldAccess(EOS(STATIC_2152), java.lang.Object(IntList(EOC, i385)), java.lang.Object(IntList(EOC, i385))) -> f2165_0_main_FieldAccess(EOS(STATIC_2165), java.lang.Object(IntList(EOC, i385)), java.lang.Object(IntList(EOC, i385))) :|: TRUE 8.06/2.97 f2165_0_main_FieldAccess(EOS(STATIC_2165), java.lang.Object(IntList(EOC, i385)), java.lang.Object(IntList(EOC, i385))) -> f2169_0_main_LE(EOS(STATIC_2169), java.lang.Object(IntList(EOC, i385)), i385) :|: TRUE 8.06/2.97 f2169_0_main_LE(EOS(STATIC_2169), java.lang.Object(IntList(EOC, i389)), i389) -> f2183_0_main_LE(EOS(STATIC_2183), java.lang.Object(IntList(EOC, i389)), i389) :|: TRUE 8.06/2.97 f2183_0_main_LE(EOS(STATIC_2183), java.lang.Object(IntList(EOC, i389)), i389) -> f2194_0_main_Load(EOS(STATIC_2194), java.lang.Object(IntList(EOC, i389))) :|: i389 > 0 8.06/2.97 f2194_0_main_Load(EOS(STATIC_2194), java.lang.Object(IntList(EOC, i389))) -> f2202_0_main_Duplicate(EOS(STATIC_2202), java.lang.Object(IntList(EOC, i389)), java.lang.Object(IntList(EOC, i389))) :|: TRUE 8.06/2.97 f2202_0_main_Duplicate(EOS(STATIC_2202), java.lang.Object(IntList(EOC, i389)), java.lang.Object(IntList(EOC, i389))) -> f2212_0_main_FieldAccess(EOS(STATIC_2212), java.lang.Object(IntList(EOC, i389)), java.lang.Object(IntList(EOC, i389)), java.lang.Object(IntList(EOC, i389))) :|: TRUE 8.06/2.97 f2212_0_main_FieldAccess(EOS(STATIC_2212), java.lang.Object(IntList(EOC, i389)), java.lang.Object(IntList(EOC, i389)), java.lang.Object(IntList(EOC, i389))) -> f2229_0_main_ConstantStackPush(EOS(STATIC_2229), java.lang.Object(IntList(EOC, i389)), java.lang.Object(IntList(EOC, i389)), i389) :|: TRUE 8.06/2.97 f2229_0_main_ConstantStackPush(EOS(STATIC_2229), java.lang.Object(IntList(EOC, i389)), java.lang.Object(IntList(EOC, i389)), i389) -> f2237_0_main_IntArithmetic(EOS(STATIC_2237), java.lang.Object(IntList(EOC, i389)), java.lang.Object(IntList(EOC, i389)), i389, 1) :|: TRUE 8.06/2.97 f2237_0_main_IntArithmetic(EOS(STATIC_2237), java.lang.Object(IntList(EOC, i389)), java.lang.Object(IntList(EOC, i389)), i389, matching1) -> f2351_0_main_FieldAccess(EOS(STATIC_2351), java.lang.Object(IntList(EOC, i389)), java.lang.Object(IntList(EOC, i389)), i389 - 1) :|: i389 > 0 && matching1 = 1 8.06/2.97 f2351_0_main_FieldAccess(EOS(STATIC_2351), java.lang.Object(IntList(EOC, i389)), java.lang.Object(IntList(EOC, i389)), i416) -> f2361_0_main_JMP(EOS(STATIC_2361), java.lang.Object(IntList(EOC, i416))) :|: TRUE 8.06/2.97 f2361_0_main_JMP(EOS(STATIC_2361), java.lang.Object(IntList(EOC, i416))) -> f2379_0_main_Load(EOS(STATIC_2379), java.lang.Object(IntList(EOC, i416))) :|: TRUE 8.06/2.97 f2379_0_main_Load(EOS(STATIC_2379), java.lang.Object(IntList(EOC, i416))) -> f2137_0_main_Load(EOS(STATIC_2137), java.lang.Object(IntList(EOC, i416))) :|: TRUE 8.06/2.97 f2137_0_main_Load(EOS(STATIC_2137), o201) -> f2147_0_main_FieldAccess(EOS(STATIC_2147), o201, o201) :|: TRUE 8.06/2.97 Combined rules. Obtained 1 IRulesP rules: 8.06/2.97 f2147_0_main_FieldAccess(EOS(STATIC_2147), java.lang.Object(IntList(EOC, i385:0)), java.lang.Object(IntList(EOC, i385:0))) -> f2147_0_main_FieldAccess(EOS(STATIC_2147), java.lang.Object(IntList(EOC, i385:0 - 1)), java.lang.Object(IntList(EOC, i385:0 - 1))) :|: i385:0 > 0 8.06/2.97 Filtered constant ground arguments: 8.06/2.97 f2147_0_main_FieldAccess(x1, x2, x3) -> f2147_0_main_FieldAccess(x2, x3) 8.06/2.97 EOS(x1) -> EOS 8.06/2.97 IntList(x1, x2) -> IntList(x2) 8.06/2.97 Filtered duplicate arguments: 8.06/2.97 f2147_0_main_FieldAccess(x1, x2) -> f2147_0_main_FieldAccess(x2) 8.06/2.97 Finished conversion. Obtained 1 rules.P rules: 8.06/2.97 f2147_0_main_FieldAccess(java.lang.Object(IntList(i385:0)), i385:0) -> f2147_0_main_FieldAccess(java.lang.Object(IntList(i385:0 - 1)), i385:0 - 1) :|: i385:0 > 0 8.06/2.97 8.06/2.97 ---------------------------------------- 8.06/2.97 8.06/2.97 (22) 8.06/2.97 Obligation: 8.06/2.97 Rules: 8.06/2.97 f2147_0_main_FieldAccess(java.lang.Object(IntList(i385:0)), i385:0) -> f2147_0_main_FieldAccess(java.lang.Object(IntList(i385:0 - 1)), i385:0 - 1) :|: i385:0 > 0 8.06/2.97 8.06/2.97 ---------------------------------------- 8.06/2.97 8.06/2.97 (23) IRSFormatTransformerProof (EQUIVALENT) 8.06/2.97 Reformatted IRS to match normalized format (transformed away non-linear left-hand sides, !=, / and %). 8.06/2.97 ---------------------------------------- 8.06/2.97 8.06/2.97 (24) 8.06/2.97 Obligation: 8.06/2.97 Rules: 8.06/2.97 f2147_0_main_FieldAccess(java.lang.Object(IntList(i385:0)), i385:0) -> f2147_0_main_FieldAccess(java.lang.Object(IntList(arith)), arith) :|: i385:0 > 0 && arith = i385:0 - 1 && arith = i385:0 - 1 8.06/2.97 8.06/2.97 ---------------------------------------- 8.06/2.97 8.06/2.97 (25) IRSwTTerminationDigraphProof (EQUIVALENT) 8.06/2.97 Constructed termination digraph! 8.06/2.97 Nodes: 8.06/2.97 (1) f2147_0_main_FieldAccess(java.lang.Object(IntList(i385:0)), i385:0) -> f2147_0_main_FieldAccess(java.lang.Object(IntList(arith)), arith) :|: i385:0 > 0 && arith = i385:0 - 1 && arith = i385:0 - 1 8.06/2.97 8.06/2.97 Arcs: 8.06/2.97 (1) -> (1) 8.06/2.97 8.06/2.97 This digraph is fully evaluated! 8.06/2.97 ---------------------------------------- 8.06/2.97 8.06/2.97 (26) 8.06/2.97 Obligation: 8.06/2.97 8.06/2.97 Termination digraph: 8.06/2.97 Nodes: 8.06/2.97 (1) f2147_0_main_FieldAccess(java.lang.Object(IntList(i385:0)), i385:0) -> f2147_0_main_FieldAccess(java.lang.Object(IntList(arith)), arith) :|: i385:0 > 0 && arith = i385:0 - 1 && arith = i385:0 - 1 8.06/2.97 8.06/2.97 Arcs: 8.06/2.97 (1) -> (1) 8.06/2.97 8.06/2.97 This digraph is fully evaluated! 8.06/2.97 8.06/2.97 ---------------------------------------- 8.06/2.97 8.06/2.97 (27) IntTRSCompressionProof (EQUIVALENT) 8.06/2.97 Compressed rules. 8.06/2.97 ---------------------------------------- 8.06/2.97 8.06/2.97 (28) 8.06/2.97 Obligation: 8.06/2.97 Rules: 8.06/2.97 f2147_0_main_FieldAccess(java.lang.Object(IntList(i385:0:0)), i385:0:0) -> f2147_0_main_FieldAccess(java.lang.Object(IntList(i385:0:0 - 1)), i385:0:0 - 1) :|: i385:0:0 > 0 8.06/2.97 8.06/2.97 ---------------------------------------- 8.06/2.97 8.06/2.97 (29) TempFilterProof (SOUND) 8.06/2.97 Used the following sort dictionary for filtering: 8.06/2.97 f2147_0_main_FieldAccess(VARIABLE, INTEGER) 8.06/2.97 java.lang.Object(VARIABLE) 8.06/2.97 IntList(INTEGER) 8.06/2.97 Replaced non-predefined constructor symbols by 0. 8.06/2.97 ---------------------------------------- 8.06/2.97 8.06/2.97 (30) 8.06/2.97 Obligation: 8.06/2.97 Rules: 8.06/2.97 f2147_0_main_FieldAccess(c, i385:0:0) -> f2147_0_main_FieldAccess(c1, c2) :|: c2 = i385:0:0 - 1 && (c1 = 0 && c = 0) && i385:0:0 > 0 8.06/2.97 8.06/2.97 ---------------------------------------- 8.06/2.97 8.06/2.97 (31) RankingReductionPairProof (EQUIVALENT) 8.06/2.97 Interpretation: 8.06/2.97 [ f2147_0_main_FieldAccess ] = f2147_0_main_FieldAccess_2 8.06/2.97 8.06/2.97 The following rules are decreasing: 8.06/2.97 f2147_0_main_FieldAccess(c, i385:0:0) -> f2147_0_main_FieldAccess(c1, c2) :|: c2 = i385:0:0 - 1 && (c1 = 0 && c = 0) && i385:0:0 > 0 8.06/2.97 8.06/2.97 The following rules are bounded: 8.06/2.97 f2147_0_main_FieldAccess(c, i385:0:0) -> f2147_0_main_FieldAccess(c1, c2) :|: c2 = i385:0:0 - 1 && (c1 = 0 && c = 0) && i385:0:0 > 0 8.06/2.97 8.06/2.97 8.06/2.97 ---------------------------------------- 8.06/2.97 8.06/2.97 (32) 8.06/2.97 YES 8.06/3.00 EOF