8.44/3.09 YES 8.51/3.11 proof of /export/starexec/sandbox/benchmark/theBenchmark.jar 8.51/3.11 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 8.51/3.11 8.51/3.11 8.51/3.11 termination of the given Bare JBC problem could be proven: 8.51/3.11 8.51/3.11 (0) Bare JBC problem 8.51/3.11 (1) BareJBCToJBCProof [EQUIVALENT, 94 ms] 8.51/3.11 (2) JBC problem 8.51/3.11 (3) JBCToGraph [EQUIVALENT, 572 ms] 8.51/3.11 (4) JBCTerminationGraph 8.51/3.11 (5) TerminationGraphToSCCProof [SOUND, 0 ms] 8.51/3.11 (6) AND 8.51/3.11 (7) JBCTerminationSCC 8.51/3.11 (8) SCCToIRSProof [SOUND, 47 ms] 8.51/3.11 (9) IRSwT 8.51/3.11 (10) IRSFormatTransformerProof [EQUIVALENT, 0 ms] 8.51/3.11 (11) IRSwT 8.51/3.11 (12) IRSwTTerminationDigraphProof [EQUIVALENT, 33 ms] 8.51/3.11 (13) IRSwT 8.51/3.11 (14) IntTRSCompressionProof [EQUIVALENT, 0 ms] 8.51/3.11 (15) IRSwT 8.51/3.11 (16) TempFilterProof [SOUND, 5 ms] 8.51/3.11 (17) IntTRS 8.51/3.11 (18) PolynomialOrderProcessor [EQUIVALENT, 0 ms] 8.51/3.11 (19) YES 8.51/3.11 (20) JBCTerminationSCC 8.51/3.11 (21) SCCToIRSProof [SOUND, 50 ms] 8.51/3.11 (22) IRSwT 8.51/3.11 (23) IRSFormatTransformerProof [EQUIVALENT, 0 ms] 8.51/3.11 (24) IRSwT 8.51/3.11 (25) IRSwTTerminationDigraphProof [EQUIVALENT, 10 ms] 8.51/3.11 (26) IRSwT 8.51/3.11 (27) IntTRSCompressionProof [EQUIVALENT, 0 ms] 8.51/3.11 (28) IRSwT 8.51/3.11 (29) TempFilterProof [SOUND, 20 ms] 8.51/3.11 (30) IntTRS 8.51/3.11 (31) PolynomialOrderProcessor [EQUIVALENT, 12 ms] 8.51/3.11 (32) YES 8.51/3.11 (33) JBCTerminationSCC 8.51/3.11 (34) SCCToIRSProof [SOUND, 69 ms] 8.51/3.11 (35) IRSwT 8.51/3.11 (36) IRSFormatTransformerProof [EQUIVALENT, 0 ms] 8.51/3.11 (37) IRSwT 8.51/3.11 (38) IRSwTTerminationDigraphProof [EQUIVALENT, 14 ms] 8.51/3.11 (39) IRSwT 8.51/3.11 (40) IntTRSCompressionProof [EQUIVALENT, 0 ms] 8.51/3.11 (41) IRSwT 8.51/3.11 (42) TempFilterProof [SOUND, 27 ms] 8.51/3.11 (43) IntTRS 8.51/3.11 (44) PolynomialOrderProcessor [EQUIVALENT, 4 ms] 8.51/3.11 (45) YES 8.51/3.11 8.51/3.11 8.51/3.11 ---------------------------------------- 8.51/3.11 8.51/3.11 (0) 8.51/3.11 Obligation: 8.51/3.11 need to prove termination of the following program: 8.51/3.11 public class ListContentArbitrary{ 8.51/3.11 8.51/3.11 public static void main(String[] args) { 8.51/3.11 Random.args = args; 8.51/3.11 IntList l = IntList.createIntList(); 8.51/3.11 int n = Random.random(); 8.51/3.11 int m = l.nth(n); 8.51/3.11 8.51/3.11 while (m > 0) m--; 8.51/3.11 } 8.51/3.11 8.51/3.11 } 8.51/3.11 8.51/3.11 class IntList { 8.51/3.11 int value; 8.51/3.11 IntList next; 8.51/3.11 8.51/3.11 public IntList(int value, IntList next) { 8.51/3.11 this.value = value; 8.51/3.11 this.next = next; 8.51/3.11 } 8.51/3.11 8.51/3.11 public static IntList createIntList() { 8.51/3.11 8.51/3.11 int i = Random.random(); 8.51/3.11 IntList l = null; 8.51/3.11 8.51/3.11 while (i > 0) { 8.51/3.11 l = new IntList(Random.random(), l); 8.51/3.11 i--; 8.51/3.11 } 8.51/3.11 8.51/3.11 return l; 8.51/3.11 } 8.51/3.11 8.51/3.11 public int nth(int n){ 8.51/3.11 8.51/3.11 IntList l = this; 8.51/3.11 8.51/3.11 while (n > 1) { 8.51/3.11 n--; 8.51/3.11 l = l.next; 8.51/3.11 } 8.51/3.11 8.51/3.11 return l.value; 8.51/3.11 } 8.51/3.11 } 8.51/3.11 8.51/3.11 8.51/3.11 8.51/3.11 public class Random { 8.51/3.11 static String[] args; 8.51/3.11 static int index = 0; 8.51/3.11 8.51/3.11 public static int random() { 8.51/3.11 String string = args[index]; 8.51/3.11 index++; 8.51/3.11 return string.length(); 8.51/3.11 } 8.51/3.11 } 8.51/3.11 8.51/3.11 8.51/3.11 8.51/3.11 ---------------------------------------- 8.51/3.11 8.51/3.11 (1) BareJBCToJBCProof (EQUIVALENT) 8.51/3.11 initialized classpath 8.51/3.11 ---------------------------------------- 8.51/3.11 8.51/3.11 (2) 8.51/3.11 Obligation: 8.51/3.11 need to prove termination of the following program: 8.51/3.11 public class ListContentArbitrary{ 8.51/3.11 8.51/3.11 public static void main(String[] args) { 8.51/3.11 Random.args = args; 8.51/3.11 IntList l = IntList.createIntList(); 8.51/3.11 int n = Random.random(); 8.51/3.11 int m = l.nth(n); 8.51/3.11 8.51/3.11 while (m > 0) m--; 8.51/3.11 } 8.51/3.11 8.51/3.11 } 8.51/3.11 8.51/3.11 class IntList { 8.51/3.11 int value; 8.51/3.11 IntList next; 8.51/3.11 8.51/3.11 public IntList(int value, IntList next) { 8.51/3.11 this.value = value; 8.51/3.11 this.next = next; 8.51/3.11 } 8.51/3.11 8.51/3.11 public static IntList createIntList() { 8.51/3.11 8.51/3.11 int i = Random.random(); 8.51/3.11 IntList l = null; 8.51/3.11 8.51/3.11 while (i > 0) { 8.51/3.11 l = new IntList(Random.random(), l); 8.51/3.11 i--; 8.51/3.11 } 8.51/3.11 8.51/3.11 return l; 8.51/3.11 } 8.51/3.11 8.51/3.11 public int nth(int n){ 8.51/3.11 8.51/3.11 IntList l = this; 8.51/3.11 8.51/3.11 while (n > 1) { 8.51/3.11 n--; 8.51/3.11 l = l.next; 8.51/3.11 } 8.51/3.11 8.51/3.11 return l.value; 8.51/3.11 } 8.51/3.11 } 8.51/3.11 8.51/3.11 8.51/3.11 8.51/3.11 public class Random { 8.51/3.11 static String[] args; 8.51/3.11 static int index = 0; 8.51/3.11 8.51/3.11 public static int random() { 8.51/3.11 String string = args[index]; 8.51/3.11 index++; 8.51/3.11 return string.length(); 8.51/3.11 } 8.51/3.11 } 8.51/3.11 8.51/3.11 8.51/3.11 8.51/3.11 ---------------------------------------- 8.51/3.11 8.51/3.11 (3) JBCToGraph (EQUIVALENT) 8.51/3.11 Constructed TerminationGraph. 8.51/3.11 ---------------------------------------- 8.51/3.11 8.51/3.11 (4) 8.51/3.11 Obligation: 8.51/3.11 Termination Graph based on JBC Program: 8.51/3.11 ListContentArbitrary.main([Ljava/lang/String;)V: Graph of 192 nodes with 2 SCCs. 8.51/3.12 8.51/3.12 8.51/3.12 8.51/3.12 IntList.createIntList()LIntList;: Graph of 277 nodes with 1 SCC. 8.51/3.12 8.51/3.12 8.51/3.12 8.51/3.12 8.51/3.12 8.51/3.12 ---------------------------------------- 8.51/3.12 8.51/3.12 (5) TerminationGraphToSCCProof (SOUND) 8.51/3.12 Splitted TerminationGraph to 3 SCCss. 8.51/3.12 ---------------------------------------- 8.51/3.12 8.51/3.12 (6) 8.51/3.12 Complex Obligation (AND) 8.51/3.12 8.51/3.12 ---------------------------------------- 8.51/3.12 8.51/3.12 (7) 8.51/3.12 Obligation: 8.51/3.12 SCC of termination graph based on JBC Program. 8.51/3.12 SCC contains nodes from the following methods: IntList.createIntList()LIntList; 8.51/3.12 SCC calls the following helper methods: 8.51/3.12 Performed SCC analyses: 8.51/3.12 *Used field analysis yielded the following read fields: 8.51/3.12 *java.lang.String: [count] 8.51/3.12 *Marker field analysis yielded the following relations that could be markers: 8.51/3.12 8.51/3.12 ---------------------------------------- 8.51/3.12 8.51/3.12 (8) SCCToIRSProof (SOUND) 8.51/3.12 Transformed FIGraph SCCs to intTRSs. Log: 8.51/3.12 Generated rules. Obtained 39 IRulesP rules: 8.51/3.12 f2800_0_createIntList_LE(EOS(STATIC_2800(java.lang.Object(ARRAY(i6)))), i600, i600) -> f2833_0_createIntList_LE(EOS(STATIC_2833(java.lang.Object(ARRAY(i6)))), i600, i600) :|: TRUE 8.51/3.12 f2833_0_createIntList_LE(EOS(STATIC_2833(java.lang.Object(ARRAY(i6)))), i600, i600) -> f2844_0_createIntList_New(EOS(STATIC_2844(java.lang.Object(ARRAY(i6)))), i600) :|: i600 > 0 8.51/3.12 f2844_0_createIntList_New(EOS(STATIC_2844(java.lang.Object(ARRAY(i6)))), i600) -> f2850_0_createIntList_Duplicate(EOS(STATIC_2850(java.lang.Object(ARRAY(i6)))), i600) :|: TRUE 8.51/3.12 f2850_0_createIntList_Duplicate(EOS(STATIC_2850(java.lang.Object(ARRAY(i6)))), i600) -> f2862_0_createIntList_InvokeMethod(EOS(STATIC_2862(java.lang.Object(ARRAY(i6)))), i600) :|: TRUE 8.51/3.12 f2862_0_createIntList_InvokeMethod(EOS(STATIC_2862(java.lang.Object(ARRAY(i6)))), i600) -> f2881_0_random_FieldAccess(EOS(STATIC_2881(java.lang.Object(ARRAY(i6)))), i600) :|: TRUE 8.51/3.12 f2881_0_random_FieldAccess(EOS(STATIC_2881(java.lang.Object(ARRAY(i6)))), i600) -> f2929_0_random_FieldAccess(EOS(STATIC_2929(java.lang.Object(ARRAY(i6)))), i600, java.lang.Object(ARRAY(i6))) :|: TRUE 8.51/3.12 f2929_0_random_FieldAccess(EOS(STATIC_2929(java.lang.Object(ARRAY(i6)))), i600, java.lang.Object(ARRAY(i6))) -> f2954_0_random_ArrayAccess(EOS(STATIC_2954(java.lang.Object(ARRAY(i6)))), i600, java.lang.Object(ARRAY(i6))) :|: TRUE 8.51/3.12 f2954_0_random_ArrayAccess(EOS(STATIC_2954(java.lang.Object(ARRAY(i6)))), i600, java.lang.Object(ARRAY(i6))) -> f2975_0_random_ArrayAccess(EOS(STATIC_2975(java.lang.Object(ARRAY(i6)))), i600, java.lang.Object(ARRAY(i6))) :|: TRUE 8.51/3.12 f2975_0_random_ArrayAccess(EOS(STATIC_2975(java.lang.Object(ARRAY(i6)))), i600, java.lang.Object(ARRAY(i6))) -> f3012_0_random_Store(EOS(STATIC_3012(java.lang.Object(ARRAY(i6)))), i600, o353) :|: TRUE 8.51/3.12 f3012_0_random_Store(EOS(STATIC_3012(java.lang.Object(ARRAY(i6)))), i600, o353) -> f3023_0_random_FieldAccess(EOS(STATIC_3023(java.lang.Object(ARRAY(i6)))), i600, o353) :|: TRUE 8.51/3.12 f3023_0_random_FieldAccess(EOS(STATIC_3023(java.lang.Object(ARRAY(i6)))), i600, o353) -> f3033_0_random_ConstantStackPush(EOS(STATIC_3033(java.lang.Object(ARRAY(i6)))), i600, o353) :|: TRUE 8.51/3.12 f3033_0_random_ConstantStackPush(EOS(STATIC_3033(java.lang.Object(ARRAY(i6)))), i600, o353) -> f3051_0_random_IntArithmetic(EOS(STATIC_3051(java.lang.Object(ARRAY(i6)))), i600, o353) :|: TRUE 8.51/3.12 f3051_0_random_IntArithmetic(EOS(STATIC_3051(java.lang.Object(ARRAY(i6)))), i600, o353) -> f3072_0_random_FieldAccess(EOS(STATIC_3072(java.lang.Object(ARRAY(i6)))), i600, o353) :|: TRUE 8.51/3.12 f3072_0_random_FieldAccess(EOS(STATIC_3072(java.lang.Object(ARRAY(i6)))), i600, o353) -> f3086_0_random_Load(EOS(STATIC_3086(java.lang.Object(ARRAY(i6)))), i600, o353) :|: TRUE 8.51/3.12 f3086_0_random_Load(EOS(STATIC_3086(java.lang.Object(ARRAY(i6)))), i600, o353) -> f3112_0_random_InvokeMethod(EOS(STATIC_3112(java.lang.Object(ARRAY(i6)))), i600, o353) :|: TRUE 8.51/3.12 f3112_0_random_InvokeMethod(EOS(STATIC_3112(java.lang.Object(ARRAY(i6)))), i600, java.lang.Object(o376sub)) -> f3130_0_random_InvokeMethod(EOS(STATIC_3130(java.lang.Object(ARRAY(i6)))), i600, java.lang.Object(o376sub)) :|: TRUE 8.51/3.12 f3130_0_random_InvokeMethod(EOS(STATIC_3130(java.lang.Object(ARRAY(i6)))), i600, java.lang.Object(o378sub)) -> f3145_0_random_InvokeMethod(EOS(STATIC_3145(java.lang.Object(ARRAY(i6)))), i600, java.lang.Object(o378sub)) :|: TRUE 8.51/3.12 f3145_0_random_InvokeMethod(EOS(STATIC_3145(java.lang.Object(ARRAY(i6)))), i600, java.lang.Object(o378sub)) -> f3158_0_length_Load(EOS(STATIC_3158(java.lang.Object(ARRAY(i6)))), i600, java.lang.Object(o378sub)) :|: TRUE 8.51/3.12 f3158_0_length_Load(EOS(STATIC_3158(java.lang.Object(ARRAY(i6)))), i600, java.lang.Object(o378sub)) -> f3187_0_length_FieldAccess(EOS(STATIC_3187(java.lang.Object(ARRAY(i6)))), i600, java.lang.Object(o378sub)) :|: TRUE 8.51/3.12 f3187_0_length_FieldAccess(EOS(STATIC_3187(java.lang.Object(ARRAY(i6)))), i600, java.lang.Object(java.lang.String(EOC, i712))) -> f3220_0_length_FieldAccess(EOS(STATIC_3220(java.lang.Object(ARRAY(i6)))), i600, java.lang.Object(java.lang.String(EOC, i712))) :|: TRUE 8.51/3.12 f3220_0_length_FieldAccess(EOS(STATIC_3220(java.lang.Object(ARRAY(i6)))), i600, java.lang.Object(java.lang.String(EOC, i712))) -> f3231_0_length_Return(EOS(STATIC_3231(java.lang.Object(ARRAY(i6)))), i600) :|: TRUE 8.51/3.12 f3231_0_length_Return(EOS(STATIC_3231(java.lang.Object(ARRAY(i6)))), i600) -> f3245_0_random_Return(EOS(STATIC_3245(java.lang.Object(ARRAY(i6)))), i600) :|: TRUE 8.51/3.12 f3245_0_random_Return(EOS(STATIC_3245(java.lang.Object(ARRAY(i6)))), i600) -> f3267_0_createIntList_Load(EOS(STATIC_3267(java.lang.Object(ARRAY(i6)))), i600) :|: TRUE 8.51/3.12 f3267_0_createIntList_Load(EOS(STATIC_3267(java.lang.Object(ARRAY(i6)))), i600) -> f3278_0_createIntList_InvokeMethod(EOS(STATIC_3278(java.lang.Object(ARRAY(i6)))), i600) :|: TRUE 8.51/3.12 f3278_0_createIntList_InvokeMethod(EOS(STATIC_3278(java.lang.Object(ARRAY(i6)))), i600) -> f3323_0__init__Load(EOS(STATIC_3323(java.lang.Object(ARRAY(i6)))), i600) :|: TRUE 8.51/3.12 f3323_0__init__Load(EOS(STATIC_3323(java.lang.Object(ARRAY(i6)))), i600) -> f3388_0__init__InvokeMethod(EOS(STATIC_3388(java.lang.Object(ARRAY(i6)))), i600) :|: TRUE 8.51/3.12 f3388_0__init__InvokeMethod(EOS(STATIC_3388(java.lang.Object(ARRAY(i6)))), i600) -> f3477_0__init__Load(EOS(STATIC_3477(java.lang.Object(ARRAY(i6)))), i600) :|: TRUE 8.51/3.12 f3477_0__init__Load(EOS(STATIC_3477(java.lang.Object(ARRAY(i6)))), i600) -> f3505_0__init__Load(EOS(STATIC_3505(java.lang.Object(ARRAY(i6)))), i600) :|: TRUE 8.51/3.12 f3505_0__init__Load(EOS(STATIC_3505(java.lang.Object(ARRAY(i6)))), i600) -> f3584_0__init__FieldAccess(EOS(STATIC_3584(java.lang.Object(ARRAY(i6)))), i600) :|: TRUE 8.51/3.12 f3584_0__init__FieldAccess(EOS(STATIC_3584(java.lang.Object(ARRAY(i6)))), i600) -> f3607_0__init__Load(EOS(STATIC_3607(java.lang.Object(ARRAY(i6)))), i600) :|: TRUE 8.51/3.12 f3607_0__init__Load(EOS(STATIC_3607(java.lang.Object(ARRAY(i6)))), i600) -> f3629_0__init__Load(EOS(STATIC_3629(java.lang.Object(ARRAY(i6)))), i600) :|: TRUE 8.51/3.12 f3629_0__init__Load(EOS(STATIC_3629(java.lang.Object(ARRAY(i6)))), i600) -> f3644_0__init__FieldAccess(EOS(STATIC_3644(java.lang.Object(ARRAY(i6)))), i600) :|: TRUE 8.51/3.12 f3644_0__init__FieldAccess(EOS(STATIC_3644(java.lang.Object(ARRAY(i6)))), i600) -> f3758_0__init__Return(EOS(STATIC_3758(java.lang.Object(ARRAY(i6)))), i600) :|: TRUE 8.51/3.12 f3758_0__init__Return(EOS(STATIC_3758(java.lang.Object(ARRAY(i6)))), i600) -> f3785_0_createIntList_Store(EOS(STATIC_3785(java.lang.Object(ARRAY(i6)))), i600) :|: TRUE 8.51/3.12 f3785_0_createIntList_Store(EOS(STATIC_3785(java.lang.Object(ARRAY(i6)))), i600) -> f3813_0_createIntList_Inc(EOS(STATIC_3813(java.lang.Object(ARRAY(i6)))), i600) :|: TRUE 8.51/3.12 f3813_0_createIntList_Inc(EOS(STATIC_3813(java.lang.Object(ARRAY(i6)))), i600) -> f3820_0_createIntList_JMP(EOS(STATIC_3820(java.lang.Object(ARRAY(i6)))), i600 + -1) :|: TRUE 8.51/3.12 f3820_0_createIntList_JMP(EOS(STATIC_3820(java.lang.Object(ARRAY(i6)))), i833) -> f3957_0_createIntList_Load(EOS(STATIC_3957(java.lang.Object(ARRAY(i6)))), i833) :|: TRUE 8.51/3.12 f3957_0_createIntList_Load(EOS(STATIC_3957(java.lang.Object(ARRAY(i6)))), i833) -> f2707_0_createIntList_Load(EOS(STATIC_2707(java.lang.Object(ARRAY(i6)))), i833) :|: TRUE 8.51/3.12 f2707_0_createIntList_Load(EOS(STATIC_2707(java.lang.Object(ARRAY(i6)))), i547) -> f2800_0_createIntList_LE(EOS(STATIC_2800(java.lang.Object(ARRAY(i6)))), i547, i547) :|: TRUE 8.51/3.12 Combined rules. Obtained 1 IRulesP rules: 8.51/3.12 f2800_0_createIntList_LE(EOS(STATIC_2800(java.lang.Object(ARRAY(i6:0)))), i600:0, i600:0) -> f2800_0_createIntList_LE(EOS(STATIC_2800(java.lang.Object(ARRAY(i6:0)))), i600:0 - 1, i600:0 - 1) :|: i600:0 > 0 8.51/3.12 Filtered duplicate arguments: 8.51/3.12 f2800_0_createIntList_LE(x1, x2, x3) -> f2800_0_createIntList_LE(x1, x3) 8.51/3.12 Filtered unneeded arguments: 8.51/3.12 f2800_0_createIntList_LE(x1, x2) -> f2800_0_createIntList_LE(x2) 8.51/3.12 Finished conversion. Obtained 1 rules.P rules: 8.51/3.12 f2800_0_createIntList_LE(i600:0) -> f2800_0_createIntList_LE(i600:0 - 1) :|: i600:0 > 0 8.51/3.12 8.51/3.12 ---------------------------------------- 8.51/3.12 8.51/3.12 (9) 8.51/3.12 Obligation: 8.51/3.12 Rules: 8.51/3.12 f2800_0_createIntList_LE(i600:0) -> f2800_0_createIntList_LE(i600:0 - 1) :|: i600:0 > 0 8.51/3.12 8.51/3.12 ---------------------------------------- 8.51/3.12 8.51/3.12 (10) IRSFormatTransformerProof (EQUIVALENT) 8.51/3.12 Reformatted IRS to match normalized format (transformed away non-linear left-hand sides, !=, / and %). 8.51/3.12 ---------------------------------------- 8.51/3.12 8.51/3.12 (11) 8.51/3.12 Obligation: 8.51/3.12 Rules: 8.51/3.12 f2800_0_createIntList_LE(i600:0) -> f2800_0_createIntList_LE(arith) :|: i600:0 > 0 && arith = i600:0 - 1 8.51/3.12 8.51/3.12 ---------------------------------------- 8.51/3.12 8.51/3.12 (12) IRSwTTerminationDigraphProof (EQUIVALENT) 8.51/3.12 Constructed termination digraph! 8.51/3.12 Nodes: 8.51/3.12 (1) f2800_0_createIntList_LE(i600:0) -> f2800_0_createIntList_LE(arith) :|: i600:0 > 0 && arith = i600:0 - 1 8.51/3.12 8.51/3.12 Arcs: 8.51/3.12 (1) -> (1) 8.51/3.12 8.51/3.12 This digraph is fully evaluated! 8.51/3.12 ---------------------------------------- 8.51/3.12 8.51/3.12 (13) 8.51/3.12 Obligation: 8.51/3.12 8.51/3.12 Termination digraph: 8.51/3.12 Nodes: 8.51/3.12 (1) f2800_0_createIntList_LE(i600:0) -> f2800_0_createIntList_LE(arith) :|: i600:0 > 0 && arith = i600:0 - 1 8.51/3.12 8.51/3.12 Arcs: 8.51/3.12 (1) -> (1) 8.51/3.12 8.51/3.12 This digraph is fully evaluated! 8.51/3.12 8.51/3.12 ---------------------------------------- 8.51/3.12 8.51/3.12 (14) IntTRSCompressionProof (EQUIVALENT) 8.51/3.12 Compressed rules. 8.51/3.12 ---------------------------------------- 8.51/3.12 8.51/3.12 (15) 8.51/3.12 Obligation: 8.51/3.12 Rules: 8.51/3.12 f2800_0_createIntList_LE(i600:0:0) -> f2800_0_createIntList_LE(i600:0:0 - 1) :|: i600:0:0 > 0 8.51/3.12 8.51/3.12 ---------------------------------------- 8.51/3.12 8.51/3.12 (16) TempFilterProof (SOUND) 8.51/3.12 Used the following sort dictionary for filtering: 8.51/3.12 f2800_0_createIntList_LE(INTEGER) 8.51/3.12 Replaced non-predefined constructor symbols by 0. 8.51/3.12 ---------------------------------------- 8.51/3.12 8.51/3.12 (17) 8.51/3.12 Obligation: 8.51/3.12 Rules: 8.51/3.12 f2800_0_createIntList_LE(i600:0:0) -> f2800_0_createIntList_LE(c) :|: c = i600:0:0 - 1 && i600:0:0 > 0 8.51/3.12 8.51/3.12 ---------------------------------------- 8.51/3.12 8.51/3.12 (18) PolynomialOrderProcessor (EQUIVALENT) 8.51/3.12 Found the following polynomial interpretation: 8.51/3.12 [f2800_0_createIntList_LE(x)] = x 8.51/3.12 8.51/3.12 The following rules are decreasing: 8.51/3.12 f2800_0_createIntList_LE(i600:0:0) -> f2800_0_createIntList_LE(c) :|: c = i600:0:0 - 1 && i600:0:0 > 0 8.51/3.12 The following rules are bounded: 8.51/3.12 f2800_0_createIntList_LE(i600:0:0) -> f2800_0_createIntList_LE(c) :|: c = i600:0:0 - 1 && i600:0:0 > 0 8.51/3.12 8.51/3.12 ---------------------------------------- 8.51/3.12 8.51/3.12 (19) 8.51/3.12 YES 8.51/3.12 8.51/3.12 ---------------------------------------- 8.51/3.12 8.51/3.12 (20) 8.51/3.12 Obligation: 8.51/3.12 SCC of termination graph based on JBC Program. 8.51/3.12 SCC contains nodes from the following methods: ListContentArbitrary.main([Ljava/lang/String;)V 8.51/3.12 SCC calls the following helper methods: 8.51/3.12 Performed SCC analyses: 8.51/3.12 *Used field analysis yielded the following read fields: 8.51/3.12 8.51/3.12 *Marker field analysis yielded the following relations that could be markers: 8.51/3.12 8.51/3.12 ---------------------------------------- 8.51/3.12 8.51/3.12 (21) SCCToIRSProof (SOUND) 8.51/3.12 Transformed FIGraph SCCs to intTRSs. Log: 8.51/3.12 Generated rules. Obtained 6 IRulesP rules: 8.51/3.12 f3114_0_main_LE(EOS(STATIC_3114), i683, i683) -> f3135_0_main_LE(EOS(STATIC_3135), i683, i683) :|: TRUE 8.51/3.12 f3135_0_main_LE(EOS(STATIC_3135), i683, i683) -> f3149_0_main_Inc(EOS(STATIC_3149), i683) :|: i683 > 0 8.51/3.12 f3149_0_main_Inc(EOS(STATIC_3149), i683) -> f3165_0_main_JMP(EOS(STATIC_3165), i683 + -1) :|: TRUE 8.51/3.12 f3165_0_main_JMP(EOS(STATIC_3165), i687) -> f3176_0_main_Load(EOS(STATIC_3176), i687) :|: TRUE 8.51/3.12 f3176_0_main_Load(EOS(STATIC_3176), i687) -> f3093_0_main_Load(EOS(STATIC_3093), i687) :|: TRUE 8.51/3.12 f3093_0_main_Load(EOS(STATIC_3093), i660) -> f3114_0_main_LE(EOS(STATIC_3114), i660, i660) :|: TRUE 8.51/3.12 Combined rules. Obtained 1 IRulesP rules: 8.51/3.12 f3114_0_main_LE(EOS(STATIC_3114), i683:0, i683:0) -> f3114_0_main_LE(EOS(STATIC_3114), i683:0 - 1, i683:0 - 1) :|: i683:0 > 0 8.51/3.12 Filtered constant ground arguments: 8.51/3.12 f3114_0_main_LE(x1, x2, x3) -> f3114_0_main_LE(x2, x3) 8.51/3.12 EOS(x1) -> EOS 8.51/3.12 Filtered duplicate arguments: 8.51/3.12 f3114_0_main_LE(x1, x2) -> f3114_0_main_LE(x2) 8.51/3.12 Finished conversion. Obtained 1 rules.P rules: 8.51/3.12 f3114_0_main_LE(i683:0) -> f3114_0_main_LE(i683:0 - 1) :|: i683:0 > 0 8.51/3.12 8.51/3.12 ---------------------------------------- 8.51/3.12 8.51/3.12 (22) 8.51/3.12 Obligation: 8.51/3.12 Rules: 8.51/3.12 f3114_0_main_LE(i683:0) -> f3114_0_main_LE(i683:0 - 1) :|: i683:0 > 0 8.51/3.12 8.51/3.12 ---------------------------------------- 8.51/3.12 8.51/3.12 (23) IRSFormatTransformerProof (EQUIVALENT) 8.51/3.12 Reformatted IRS to match normalized format (transformed away non-linear left-hand sides, !=, / and %). 8.51/3.12 ---------------------------------------- 8.51/3.12 8.51/3.12 (24) 8.51/3.12 Obligation: 8.51/3.12 Rules: 8.51/3.12 f3114_0_main_LE(i683:0) -> f3114_0_main_LE(arith) :|: i683:0 > 0 && arith = i683:0 - 1 8.51/3.12 8.51/3.12 ---------------------------------------- 8.51/3.12 8.51/3.12 (25) IRSwTTerminationDigraphProof (EQUIVALENT) 8.51/3.12 Constructed termination digraph! 8.51/3.12 Nodes: 8.51/3.12 (1) f3114_0_main_LE(i683:0) -> f3114_0_main_LE(arith) :|: i683:0 > 0 && arith = i683:0 - 1 8.51/3.12 8.51/3.12 Arcs: 8.51/3.12 (1) -> (1) 8.51/3.12 8.51/3.12 This digraph is fully evaluated! 8.51/3.12 ---------------------------------------- 8.51/3.12 8.51/3.12 (26) 8.51/3.12 Obligation: 8.51/3.12 8.51/3.12 Termination digraph: 8.51/3.12 Nodes: 8.51/3.12 (1) f3114_0_main_LE(i683:0) -> f3114_0_main_LE(arith) :|: i683:0 > 0 && arith = i683:0 - 1 8.51/3.12 8.51/3.12 Arcs: 8.51/3.12 (1) -> (1) 8.51/3.12 8.51/3.12 This digraph is fully evaluated! 8.51/3.12 8.51/3.12 ---------------------------------------- 8.51/3.12 8.51/3.12 (27) IntTRSCompressionProof (EQUIVALENT) 8.51/3.12 Compressed rules. 8.51/3.12 ---------------------------------------- 8.51/3.12 8.51/3.12 (28) 8.51/3.12 Obligation: 8.51/3.12 Rules: 8.51/3.12 f3114_0_main_LE(i683:0:0) -> f3114_0_main_LE(i683:0:0 - 1) :|: i683:0:0 > 0 8.51/3.12 8.51/3.12 ---------------------------------------- 8.51/3.12 8.51/3.12 (29) TempFilterProof (SOUND) 8.51/3.12 Used the following sort dictionary for filtering: 8.51/3.12 f3114_0_main_LE(INTEGER) 8.51/3.12 Replaced non-predefined constructor symbols by 0. 8.51/3.12 ---------------------------------------- 8.51/3.12 8.51/3.12 (30) 8.51/3.12 Obligation: 8.51/3.12 Rules: 8.51/3.12 f3114_0_main_LE(i683:0:0) -> f3114_0_main_LE(c) :|: c = i683:0:0 - 1 && i683:0:0 > 0 8.51/3.12 8.51/3.12 ---------------------------------------- 8.51/3.12 8.51/3.12 (31) PolynomialOrderProcessor (EQUIVALENT) 8.51/3.12 Found the following polynomial interpretation: 8.51/3.12 [f3114_0_main_LE(x)] = x 8.51/3.12 8.51/3.12 The following rules are decreasing: 8.51/3.12 f3114_0_main_LE(i683:0:0) -> f3114_0_main_LE(c) :|: c = i683:0:0 - 1 && i683:0:0 > 0 8.51/3.12 The following rules are bounded: 8.51/3.12 f3114_0_main_LE(i683:0:0) -> f3114_0_main_LE(c) :|: c = i683:0:0 - 1 && i683:0:0 > 0 8.51/3.12 8.51/3.12 ---------------------------------------- 8.51/3.12 8.51/3.12 (32) 8.51/3.12 YES 8.51/3.12 8.51/3.12 ---------------------------------------- 8.51/3.12 8.51/3.12 (33) 8.51/3.12 Obligation: 8.51/3.12 SCC of termination graph based on JBC Program. 8.51/3.12 SCC contains nodes from the following methods: ListContentArbitrary.main([Ljava/lang/String;)V 8.51/3.12 SCC calls the following helper methods: 8.51/3.12 Performed SCC analyses: 8.51/3.12 *Used field analysis yielded the following read fields: 8.51/3.12 *IntList: [next] 8.51/3.12 *Marker field analysis yielded the following relations that could be markers: 8.51/3.12 8.51/3.12 ---------------------------------------- 8.51/3.12 8.51/3.12 (34) SCCToIRSProof (SOUND) 8.51/3.12 Transformed FIGraph SCCs to intTRSs. Log: 8.51/3.12 Generated rules. Obtained 12 IRulesP rules: 8.51/3.12 f2919_0_nth_ConstantStackPush(EOS(STATIC_2919), i622, o343, i622) -> f2932_0_nth_LE(EOS(STATIC_2932), i622, o343, i622, 1) :|: TRUE 8.51/3.12 f2932_0_nth_LE(EOS(STATIC_2932), i647, o343, i647, matching1) -> f2967_0_nth_LE(EOS(STATIC_2967), i647, o343, i647, 1) :|: TRUE && matching1 = 1 8.51/3.12 f2967_0_nth_LE(EOS(STATIC_2967), i647, o343, i647, matching1) -> f3003_0_nth_Inc(EOS(STATIC_3003), i647, o343) :|: i647 > 1 && matching1 = 1 8.51/3.12 f3003_0_nth_Inc(EOS(STATIC_3003), i647, o343) -> f3015_0_nth_Load(EOS(STATIC_3015), i647 + -1, o343) :|: TRUE 8.51/3.12 f3015_0_nth_Load(EOS(STATIC_3015), i654, o343) -> f3026_0_nth_FieldAccess(EOS(STATIC_3026), i654, o343) :|: TRUE 8.51/3.12 f3026_0_nth_FieldAccess(EOS(STATIC_3026), i654, java.lang.Object(o359sub)) -> f3044_0_nth_FieldAccess(EOS(STATIC_3044), i654, java.lang.Object(o359sub)) :|: TRUE 8.51/3.12 f3044_0_nth_FieldAccess(EOS(STATIC_3044), i654, java.lang.Object(IntList(EOC, o361))) -> f3061_0_nth_FieldAccess(EOS(STATIC_3061), i654, java.lang.Object(IntList(EOC, o361))) :|: TRUE 8.51/3.12 f3061_0_nth_FieldAccess(EOS(STATIC_3061), i654, java.lang.Object(IntList(EOC, o361))) -> f3081_0_nth_Store(EOS(STATIC_3081), i654, o361) :|: TRUE 8.51/3.12 f3081_0_nth_Store(EOS(STATIC_3081), i654, o361) -> f3096_0_nth_JMP(EOS(STATIC_3096), i654, o361) :|: TRUE 8.51/3.12 f3096_0_nth_JMP(EOS(STATIC_3096), i654, o361) -> f3124_0_nth_Load(EOS(STATIC_3124), i654, o361) :|: TRUE 8.51/3.12 f3124_0_nth_Load(EOS(STATIC_3124), i654, o361) -> f2894_0_nth_Load(EOS(STATIC_2894), i654, o361) :|: TRUE 8.51/3.12 f2894_0_nth_Load(EOS(STATIC_2894), i622, o343) -> f2919_0_nth_ConstantStackPush(EOS(STATIC_2919), i622, o343, i622) :|: TRUE 8.51/3.12 Combined rules. Obtained 1 IRulesP rules: 8.51/3.12 f2919_0_nth_ConstantStackPush(EOS(STATIC_2919), i622:0, java.lang.Object(IntList(EOC, o361:0)), i622:0) -> f2919_0_nth_ConstantStackPush(EOS(STATIC_2919), i622:0 - 1, o361:0, i622:0 - 1) :|: i622:0 > 1 8.51/3.12 Filtered constant ground arguments: 8.51/3.12 f2919_0_nth_ConstantStackPush(x1, x2, x3, x4) -> f2919_0_nth_ConstantStackPush(x2, x3, x4) 8.51/3.12 EOS(x1) -> EOS 8.51/3.12 IntList(x1, x2) -> IntList(x2) 8.51/3.12 Filtered duplicate arguments: 8.51/3.12 f2919_0_nth_ConstantStackPush(x1, x2, x3) -> f2919_0_nth_ConstantStackPush(x2, x3) 8.51/3.12 Finished conversion. Obtained 1 rules.P rules: 8.51/3.12 f2919_0_nth_ConstantStackPush(java.lang.Object(IntList(o361:0)), i622:0) -> f2919_0_nth_ConstantStackPush(o361:0, i622:0 - 1) :|: i622:0 > 1 8.51/3.12 8.51/3.12 ---------------------------------------- 8.51/3.12 8.51/3.12 (35) 8.51/3.12 Obligation: 8.51/3.12 Rules: 8.51/3.12 f2919_0_nth_ConstantStackPush(java.lang.Object(IntList(o361:0)), i622:0) -> f2919_0_nth_ConstantStackPush(o361:0, i622:0 - 1) :|: i622:0 > 1 8.51/3.12 8.51/3.12 ---------------------------------------- 8.51/3.12 8.51/3.12 (36) IRSFormatTransformerProof (EQUIVALENT) 8.51/3.12 Reformatted IRS to match normalized format (transformed away non-linear left-hand sides, !=, / and %). 8.51/3.12 ---------------------------------------- 8.51/3.12 8.51/3.12 (37) 8.51/3.12 Obligation: 8.51/3.12 Rules: 8.51/3.12 f2919_0_nth_ConstantStackPush(java.lang.Object(IntList(o361:0)), i622:0) -> f2919_0_nth_ConstantStackPush(o361:0, arith) :|: i622:0 > 1 && arith = i622:0 - 1 8.51/3.12 8.51/3.12 ---------------------------------------- 8.51/3.12 8.51/3.12 (38) IRSwTTerminationDigraphProof (EQUIVALENT) 8.51/3.12 Constructed termination digraph! 8.51/3.12 Nodes: 8.51/3.12 (1) f2919_0_nth_ConstantStackPush(java.lang.Object(IntList(o361:0)), i622:0) -> f2919_0_nth_ConstantStackPush(o361:0, arith) :|: i622:0 > 1 && arith = i622:0 - 1 8.51/3.12 8.51/3.12 Arcs: 8.51/3.12 (1) -> (1) 8.51/3.12 8.51/3.12 This digraph is fully evaluated! 8.51/3.12 ---------------------------------------- 8.51/3.12 8.51/3.12 (39) 8.51/3.12 Obligation: 8.51/3.12 8.51/3.12 Termination digraph: 8.51/3.12 Nodes: 8.51/3.12 (1) f2919_0_nth_ConstantStackPush(java.lang.Object(IntList(o361:0)), i622:0) -> f2919_0_nth_ConstantStackPush(o361:0, arith) :|: i622:0 > 1 && arith = i622:0 - 1 8.51/3.12 8.51/3.12 Arcs: 8.51/3.12 (1) -> (1) 8.51/3.12 8.51/3.12 This digraph is fully evaluated! 8.51/3.12 8.51/3.12 ---------------------------------------- 8.51/3.12 8.51/3.12 (40) IntTRSCompressionProof (EQUIVALENT) 8.51/3.12 Compressed rules. 8.51/3.12 ---------------------------------------- 8.51/3.12 8.51/3.12 (41) 8.51/3.12 Obligation: 8.51/3.12 Rules: 8.51/3.12 f2919_0_nth_ConstantStackPush(java.lang.Object(IntList(o361:0:0)), i622:0:0) -> f2919_0_nth_ConstantStackPush(o361:0:0, i622:0:0 - 1) :|: i622:0:0 > 1 8.51/3.12 8.51/3.12 ---------------------------------------- 8.51/3.12 8.51/3.12 (42) TempFilterProof (SOUND) 8.51/3.12 Used the following sort dictionary for filtering: 8.51/3.12 f2919_0_nth_ConstantStackPush(VARIABLE, INTEGER) 8.51/3.12 java.lang.Object(VARIABLE) 8.51/3.12 IntList(VARIABLE) 8.51/3.12 Replaced non-predefined constructor symbols by 0. 8.51/3.12 ---------------------------------------- 8.51/3.12 8.51/3.12 (43) 8.51/3.12 Obligation: 8.51/3.12 Rules: 8.51/3.12 f2919_0_nth_ConstantStackPush(c, i622:0:0) -> f2919_0_nth_ConstantStackPush(o361:0:0, c1) :|: c1 = i622:0:0 - 1 && c = 0 && i622:0:0 > 1 8.51/3.12 8.51/3.12 ---------------------------------------- 8.51/3.12 8.51/3.12 (44) PolynomialOrderProcessor (EQUIVALENT) 8.51/3.12 Found the following polynomial interpretation: 8.51/3.12 [f2919_0_nth_ConstantStackPush(x, x1)] = x1 8.51/3.12 8.51/3.12 The following rules are decreasing: 8.51/3.12 f2919_0_nth_ConstantStackPush(c, i622:0:0) -> f2919_0_nth_ConstantStackPush(o361:0:0, c1) :|: c1 = i622:0:0 - 1 && c = 0 && i622:0:0 > 1 8.51/3.12 The following rules are bounded: 8.51/3.12 f2919_0_nth_ConstantStackPush(c, i622:0:0) -> f2919_0_nth_ConstantStackPush(o361:0:0, c1) :|: c1 = i622:0:0 - 1 && c = 0 && i622:0:0 > 1 8.51/3.12 8.51/3.12 ---------------------------------------- 8.51/3.12 8.51/3.12 (45) 8.51/3.12 YES 8.54/3.16 EOF