8.29/3.09 YES 8.29/3.13 proof of /export/starexec/sandbox2/benchmark/theBenchmark.jar 8.29/3.13 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 8.29/3.13 8.29/3.13 8.29/3.13 termination of the given Bare JBC problem could be proven: 8.29/3.13 8.29/3.13 (0) Bare JBC problem 8.29/3.13 (1) BareJBCToJBCProof [EQUIVALENT, 97 ms] 8.29/3.13 (2) JBC problem 8.29/3.13 (3) JBCToGraph [EQUIVALENT, 505 ms] 8.29/3.13 (4) JBCTerminationGraph 8.29/3.13 (5) TerminationGraphToSCCProof [SOUND, 0 ms] 8.29/3.13 (6) JBCTerminationSCC 8.29/3.13 (7) SCCToIRSProof [SOUND, 156 ms] 8.29/3.13 (8) IRSwT 8.29/3.13 (9) IRSFormatTransformerProof [EQUIVALENT, 0 ms] 8.29/3.13 (10) IRSwT 8.29/3.13 (11) IRSwTTerminationDigraphProof [EQUIVALENT, 49 ms] 8.29/3.13 (12) AND 8.29/3.13 (13) IRSwT 8.29/3.13 (14) IntTRSCompressionProof [EQUIVALENT, 0 ms] 8.29/3.13 (15) IRSwT 8.29/3.13 (16) TempFilterProof [SOUND, 19 ms] 8.29/3.13 (17) IntTRS 8.29/3.13 (18) PolynomialOrderProcessor [EQUIVALENT, 0 ms] 8.29/3.13 (19) YES 8.29/3.13 (20) IRSwT 8.29/3.13 (21) IntTRSCompressionProof [EQUIVALENT, 0 ms] 8.29/3.13 (22) IRSwT 8.29/3.13 (23) TempFilterProof [SOUND, 48 ms] 8.29/3.13 (24) IntTRS 8.29/3.13 (25) PolynomialOrderProcessor [EQUIVALENT, 0 ms] 8.29/3.13 (26) YES 8.29/3.13 8.29/3.13 8.29/3.13 ---------------------------------------- 8.29/3.13 8.29/3.13 (0) 8.29/3.13 Obligation: 8.29/3.13 need to prove termination of the following program: 8.29/3.13 public class Et1 { 8.29/3.13 public static void main(String[] args) { 8.29/3.13 Random.args = args; 8.29/3.13 int a = - Random.random(); 8.29/3.13 int b = - Random.random(); 8.29/3.13 while (a > b) { 8.29/3.13 b = b + a; 8.29/3.13 a = a + 1; 8.29/3.13 } 8.29/3.13 } 8.29/3.13 } 8.29/3.13 8.29/3.13 8.29/3.13 public class Random { 8.29/3.13 static String[] args; 8.29/3.13 static int index = 0; 8.29/3.13 8.29/3.13 public static int random() { 8.29/3.13 if (index >= args.length) 8.29/3.13 return 0; 8.29/3.13 8.29/3.13 String string = args[index]; 8.29/3.13 index++; 8.29/3.13 return string.length(); 8.29/3.13 } 8.29/3.13 } 8.29/3.13 8.29/3.13 8.29/3.13 public class Et2 { 8.29/3.13 public static void main(String[] args) { 8.29/3.13 Random.args = args; 8.29/3.13 int a = Random.random(); 8.29/3.13 int b = Random.random(); 8.29/3.13 while (b > 0) { 8.29/3.13 int r = Random.random(); 8.29/3.13 b = a - 1 - r; 8.29/3.13 a = a - 1 - r; 8.29/3.13 } 8.29/3.13 } 8.29/3.13 } 8.29/3.13 8.29/3.13 // bin(entry593(C,D),[1*C+ -1*B>=1,1*C+ -1*A>=1,1*D>=1],entry593(A,B)) 8.29/3.13 8.29/3.13 8.29/3.13 ---------------------------------------- 8.29/3.13 8.29/3.13 (1) BareJBCToJBCProof (EQUIVALENT) 8.29/3.13 initialized classpath 8.29/3.13 ---------------------------------------- 8.29/3.13 8.29/3.13 (2) 8.29/3.13 Obligation: 8.29/3.13 need to prove termination of the following program: 8.29/3.13 public class Et1 { 8.29/3.13 public static void main(String[] args) { 8.29/3.13 Random.args = args; 8.29/3.13 int a = - Random.random(); 8.29/3.13 int b = - Random.random(); 8.29/3.13 while (a > b) { 8.29/3.13 b = b + a; 8.29/3.13 a = a + 1; 8.29/3.13 } 8.29/3.13 } 8.29/3.13 } 8.29/3.13 8.29/3.13 8.29/3.13 public class Random { 8.29/3.13 static String[] args; 8.29/3.13 static int index = 0; 8.29/3.13 8.29/3.13 public static int random() { 8.29/3.13 if (index >= args.length) 8.29/3.13 return 0; 8.29/3.13 8.29/3.13 String string = args[index]; 8.29/3.13 index++; 8.29/3.13 return string.length(); 8.29/3.13 } 8.29/3.13 } 8.29/3.13 8.29/3.13 8.29/3.13 public class Et2 { 8.29/3.13 public static void main(String[] args) { 8.29/3.13 Random.args = args; 8.29/3.13 int a = Random.random(); 8.29/3.13 int b = Random.random(); 8.29/3.13 while (b > 0) { 8.29/3.13 int r = Random.random(); 8.29/3.13 b = a - 1 - r; 8.29/3.13 a = a - 1 - r; 8.29/3.13 } 8.29/3.13 } 8.29/3.13 } 8.29/3.13 8.29/3.13 // bin(entry593(C,D),[1*C+ -1*B>=1,1*C+ -1*A>=1,1*D>=1],entry593(A,B)) 8.29/3.13 8.29/3.13 8.29/3.13 ---------------------------------------- 8.29/3.13 8.29/3.13 (3) JBCToGraph (EQUIVALENT) 8.29/3.13 Constructed TerminationGraph. 8.29/3.13 ---------------------------------------- 8.29/3.13 8.29/3.13 (4) 8.29/3.13 Obligation: 8.29/3.13 Termination Graph based on JBC Program: 8.29/3.13 Et2.main([Ljava/lang/String;)V: Graph of 312 nodes with 1 SCC. 8.29/3.13 8.29/3.13 8.29/3.13 8.29/3.13 8.29/3.13 8.29/3.13 ---------------------------------------- 8.29/3.13 8.29/3.13 (5) TerminationGraphToSCCProof (SOUND) 8.29/3.13 Splitted TerminationGraph to 1 SCCs. 8.29/3.13 ---------------------------------------- 8.29/3.13 8.29/3.13 (6) 8.29/3.13 Obligation: 8.29/3.13 SCC of termination graph based on JBC Program. 8.29/3.13 SCC contains nodes from the following methods: Et2.main([Ljava/lang/String;)V 8.29/3.13 SCC calls the following helper methods: 8.29/3.13 Performed SCC analyses: 8.29/3.13 *Used field analysis yielded the following read fields: 8.29/3.13 *java.lang.String: [count] 8.29/3.13 *Marker field analysis yielded the following relations that could be markers: 8.29/3.13 8.29/3.13 ---------------------------------------- 8.29/3.13 8.29/3.13 (7) SCCToIRSProof (SOUND) 8.29/3.13 Transformed FIGraph SCCs to intTRSs. Log: 8.29/3.13 Generated rules. Obtained 61 IRulesP rules: 8.29/3.13 f1319_0_main_LE(EOS(STATIC_1319(java.lang.Object(ARRAY(i4)), i39)), java.lang.Object(ARRAY(i4)), i381, i409) -> f1321_0_main_LE(EOS(STATIC_1321(java.lang.Object(ARRAY(i4)), i39)), java.lang.Object(ARRAY(i4)), i381, i409) :|: TRUE 8.29/3.13 f1321_0_main_LE(EOS(STATIC_1321(java.lang.Object(ARRAY(i4)), i39)), java.lang.Object(ARRAY(i4)), i381, i409) -> f1324_0_main_InvokeMethod(EOS(STATIC_1324(java.lang.Object(ARRAY(i4)), i39)), java.lang.Object(ARRAY(i4)), i381) :|: i409 > 0 8.29/3.13 f1324_0_main_InvokeMethod(EOS(STATIC_1324(java.lang.Object(ARRAY(i4)), i39)), java.lang.Object(ARRAY(i4)), i381) -> f1328_0_random_FieldAccess(EOS(STATIC_1328(java.lang.Object(ARRAY(i4)), i39)), java.lang.Object(ARRAY(i4)), i381) :|: TRUE 8.29/3.13 f1328_0_random_FieldAccess(EOS(STATIC_1328(java.lang.Object(ARRAY(i4)), i39)), java.lang.Object(ARRAY(i4)), i381) -> f1331_0_random_FieldAccess(EOS(STATIC_1331(java.lang.Object(ARRAY(i4)), i39)), java.lang.Object(ARRAY(i4)), i381, i39) :|: TRUE 8.29/3.13 f1331_0_random_FieldAccess(EOS(STATIC_1331(java.lang.Object(ARRAY(i4)), i39)), java.lang.Object(ARRAY(i4)), i381, i39) -> f1333_0_random_ArrayLength(EOS(STATIC_1333(java.lang.Object(ARRAY(i4)), i39)), java.lang.Object(ARRAY(i4)), i381, i39, java.lang.Object(ARRAY(i4))) :|: TRUE 8.29/3.13 f1333_0_random_ArrayLength(EOS(STATIC_1333(java.lang.Object(ARRAY(i4)), i39)), java.lang.Object(ARRAY(i4)), i381, i39, java.lang.Object(ARRAY(i4))) -> f1354_0_random_LT(EOS(STATIC_1354(java.lang.Object(ARRAY(i4)), i39)), java.lang.Object(ARRAY(i4)), i381, i39, i4) :|: i4 >= 0 8.29/3.13 f1354_0_random_LT(EOS(STATIC_1354(java.lang.Object(ARRAY(i4)), i39)), java.lang.Object(ARRAY(i4)), i381, i39, i4) -> f1367_0_random_LT(EOS(STATIC_1367(java.lang.Object(ARRAY(i4)), i39)), java.lang.Object(ARRAY(i4)), i381, i39, i4) :|: i39 < i4 8.29/3.13 f1354_0_random_LT(EOS(STATIC_1354(java.lang.Object(ARRAY(i4)), i39)), java.lang.Object(ARRAY(i4)), i381, i39, i4) -> f1368_0_random_LT(EOS(STATIC_1368(java.lang.Object(ARRAY(i4)), i39)), java.lang.Object(ARRAY(i4)), i381, i39, i4) :|: i39 >= i4 8.29/3.13 f1367_0_random_LT(EOS(STATIC_1367(java.lang.Object(ARRAY(i4)), i39)), java.lang.Object(ARRAY(i4)), i381, i39, i4) -> f1377_0_random_FieldAccess(EOS(STATIC_1377(java.lang.Object(ARRAY(i4)), i39)), java.lang.Object(ARRAY(i4)), i381) :|: i39 < i4 8.29/3.13 f1377_0_random_FieldAccess(EOS(STATIC_1377(java.lang.Object(ARRAY(i4)), i39)), java.lang.Object(ARRAY(i4)), i381) -> f1385_0_random_FieldAccess(EOS(STATIC_1385(java.lang.Object(ARRAY(i4)), i39)), java.lang.Object(ARRAY(i4)), i381, java.lang.Object(ARRAY(i4))) :|: TRUE 8.29/3.13 f1385_0_random_FieldAccess(EOS(STATIC_1385(java.lang.Object(ARRAY(i4)), i39)), java.lang.Object(ARRAY(i4)), i381, java.lang.Object(ARRAY(i4))) -> f1388_0_random_ArrayAccess(EOS(STATIC_1388(java.lang.Object(ARRAY(i4)), i39)), java.lang.Object(ARRAY(i4)), i381, java.lang.Object(ARRAY(i4)), i39) :|: TRUE 8.29/3.13 f1388_0_random_ArrayAccess(EOS(STATIC_1388(java.lang.Object(ARRAY(i4)), i39)), java.lang.Object(ARRAY(i4)), i381, java.lang.Object(ARRAY(i4)), i39) -> f1392_0_random_ArrayAccess(EOS(STATIC_1392(java.lang.Object(ARRAY(i4)), i39)), java.lang.Object(ARRAY(i4)), i381, java.lang.Object(ARRAY(i4)), i39) :|: TRUE 8.29/3.13 f1392_0_random_ArrayAccess(EOS(STATIC_1392(java.lang.Object(ARRAY(i4)), i39)), java.lang.Object(ARRAY(i4)), i381, java.lang.Object(ARRAY(i4)), i39) -> f1398_0_random_Store(EOS(STATIC_1398(java.lang.Object(ARRAY(i4)), i39)), java.lang.Object(ARRAY(i4)), i381, o124) :|: TRUE 8.29/3.13 f1398_0_random_Store(EOS(STATIC_1398(java.lang.Object(ARRAY(i4)), i39)), java.lang.Object(ARRAY(i4)), i381, o124) -> f1402_0_random_FieldAccess(EOS(STATIC_1402(java.lang.Object(ARRAY(i4)), i39)), java.lang.Object(ARRAY(i4)), i381, o124) :|: TRUE 8.29/3.13 f1402_0_random_FieldAccess(EOS(STATIC_1402(java.lang.Object(ARRAY(i4)), i39)), java.lang.Object(ARRAY(i4)), i381, o124) -> f1408_0_random_ConstantStackPush(EOS(STATIC_1408(java.lang.Object(ARRAY(i4)), i39)), java.lang.Object(ARRAY(i4)), i381, o124, i39) :|: TRUE 8.29/3.13 f1408_0_random_ConstantStackPush(EOS(STATIC_1408(java.lang.Object(ARRAY(i4)), i39)), java.lang.Object(ARRAY(i4)), i381, o124, i39) -> f1420_0_random_IntArithmetic(EOS(STATIC_1420(java.lang.Object(ARRAY(i4)), i39)), java.lang.Object(ARRAY(i4)), i381, o124, i39, 1) :|: TRUE 8.29/3.13 f1420_0_random_IntArithmetic(EOS(STATIC_1420(java.lang.Object(ARRAY(i4)), i39)), java.lang.Object(ARRAY(i4)), i381, o124, i39, matching1) -> f1428_0_random_FieldAccess(EOS(STATIC_1428(java.lang.Object(ARRAY(i4)), i39)), java.lang.Object(ARRAY(i4)), i381, o124, i39 + 1) :|: i39 > 0 && matching1 = 1 8.29/3.13 f1428_0_random_FieldAccess(EOS(STATIC_1428(java.lang.Object(ARRAY(i4)), i39)), java.lang.Object(ARRAY(i4)), i381, o124, i442) -> f1436_0_random_Load(EOS(STATIC_1436(java.lang.Object(ARRAY(i4)), i442)), java.lang.Object(ARRAY(i4)), i381, o124) :|: TRUE 8.29/3.13 f1436_0_random_Load(EOS(STATIC_1436(java.lang.Object(ARRAY(i4)), i442)), java.lang.Object(ARRAY(i4)), i381, o124) -> f1452_0_random_InvokeMethod(EOS(STATIC_1452(java.lang.Object(ARRAY(i4)), i442)), java.lang.Object(ARRAY(i4)), i381, o124) :|: TRUE 8.29/3.13 f1452_0_random_InvokeMethod(EOS(STATIC_1452(java.lang.Object(ARRAY(i4)), i442)), java.lang.Object(ARRAY(i4)), i381, java.lang.Object(o131sub)) -> f1455_0_random_InvokeMethod(EOS(STATIC_1455(java.lang.Object(ARRAY(i4)), i442)), java.lang.Object(ARRAY(i4)), i381, java.lang.Object(o131sub)) :|: TRUE 8.29/3.13 f1455_0_random_InvokeMethod(EOS(STATIC_1455(java.lang.Object(ARRAY(i4)), i442)), java.lang.Object(ARRAY(i4)), i381, java.lang.Object(o132sub)) -> f1458_0_random_InvokeMethod(EOS(STATIC_1458(java.lang.Object(ARRAY(i4)), i442)), java.lang.Object(ARRAY(i4)), i381, java.lang.Object(o132sub)) :|: TRUE 8.29/3.13 f1458_0_random_InvokeMethod(EOS(STATIC_1458(java.lang.Object(ARRAY(i4)), i442)), java.lang.Object(ARRAY(i4)), i381, java.lang.Object(o132sub)) -> f1462_0_length_Load(EOS(STATIC_1462(java.lang.Object(ARRAY(i4)), i442)), java.lang.Object(ARRAY(i4)), i381, java.lang.Object(o132sub)) :|: TRUE 8.29/3.13 f1462_0_length_Load(EOS(STATIC_1462(java.lang.Object(ARRAY(i4)), i442)), java.lang.Object(ARRAY(i4)), i381, java.lang.Object(o132sub)) -> f1476_0_length_FieldAccess(EOS(STATIC_1476(java.lang.Object(ARRAY(i4)), i442)), java.lang.Object(ARRAY(i4)), i381, java.lang.Object(o132sub)) :|: TRUE 8.29/3.13 f1476_0_length_FieldAccess(EOS(STATIC_1476(java.lang.Object(ARRAY(i4)), i442)), java.lang.Object(ARRAY(i4)), i381, java.lang.Object(java.lang.String(EOC, i471))) -> f1481_0_length_FieldAccess(EOS(STATIC_1481(java.lang.Object(ARRAY(i4)), i442)), java.lang.Object(ARRAY(i4)), i381, java.lang.Object(java.lang.String(EOC, i471))) :|: i471 >= 0 8.29/3.13 f1481_0_length_FieldAccess(EOS(STATIC_1481(java.lang.Object(ARRAY(i4)), i442)), java.lang.Object(ARRAY(i4)), i381, java.lang.Object(java.lang.String(EOC, i471))) -> f1548_0_length_Return(EOS(STATIC_1548(java.lang.Object(ARRAY(i4)), i442)), java.lang.Object(ARRAY(i4)), i381, i471) :|: TRUE 8.29/3.13 f1548_0_length_Return(EOS(STATIC_1548(java.lang.Object(ARRAY(i4)), i442)), java.lang.Object(ARRAY(i4)), i381, i471) -> f1550_0_random_Return(EOS(STATIC_1550(java.lang.Object(ARRAY(i4)), i442)), java.lang.Object(ARRAY(i4)), i381, i471) :|: TRUE 8.29/3.13 f1550_0_random_Return(EOS(STATIC_1550(java.lang.Object(ARRAY(i4)), i442)), java.lang.Object(ARRAY(i4)), i381, i471) -> f1558_0_main_Store(EOS(STATIC_1558(java.lang.Object(ARRAY(i4)), i442)), java.lang.Object(ARRAY(i4)), i381, i471) :|: TRUE 8.29/3.13 f1558_0_main_Store(EOS(STATIC_1558(java.lang.Object(ARRAY(i4)), i442)), java.lang.Object(ARRAY(i4)), i381, i471) -> f1563_0_main_Load(EOS(STATIC_1563(java.lang.Object(ARRAY(i4)), i442)), java.lang.Object(ARRAY(i4)), i381, i471) :|: TRUE 8.29/3.13 f1563_0_main_Load(EOS(STATIC_1563(java.lang.Object(ARRAY(i4)), i442)), java.lang.Object(ARRAY(i4)), i381, i471) -> f1572_0_main_ConstantStackPush(EOS(STATIC_1572(java.lang.Object(ARRAY(i4)), i442)), java.lang.Object(ARRAY(i4)), i381, i471, i381) :|: TRUE 8.29/3.13 f1572_0_main_ConstantStackPush(EOS(STATIC_1572(java.lang.Object(ARRAY(i4)), i442)), java.lang.Object(ARRAY(i4)), i381, i471, i381) -> f1580_0_main_IntArithmetic(EOS(STATIC_1580(java.lang.Object(ARRAY(i4)), i442)), java.lang.Object(ARRAY(i4)), i381, i471, i381, 1) :|: TRUE 8.29/3.13 f1580_0_main_IntArithmetic(EOS(STATIC_1580(java.lang.Object(ARRAY(i4)), i442)), java.lang.Object(ARRAY(i4)), i381, i471, i381, matching1) -> f1591_0_main_Load(EOS(STATIC_1591(java.lang.Object(ARRAY(i4)), i442)), java.lang.Object(ARRAY(i4)), i381, i471, i381 - 1) :|: TRUE && matching1 = 1 8.29/3.13 f1591_0_main_Load(EOS(STATIC_1591(java.lang.Object(ARRAY(i4)), i442)), java.lang.Object(ARRAY(i4)), i381, i471, i486) -> f1623_0_main_IntArithmetic(EOS(STATIC_1623(java.lang.Object(ARRAY(i4)), i442)), java.lang.Object(ARRAY(i4)), i381, i471, i486, i471) :|: TRUE 8.29/3.13 f1623_0_main_IntArithmetic(EOS(STATIC_1623(java.lang.Object(ARRAY(i4)), i442)), java.lang.Object(ARRAY(i4)), i381, i471, i486, i471) -> f1626_0_main_Store(EOS(STATIC_1626(java.lang.Object(ARRAY(i4)), i442)), java.lang.Object(ARRAY(i4)), i381, i471, i486 - i471) :|: i471 >= 0 8.29/3.13 f1626_0_main_Store(EOS(STATIC_1626(java.lang.Object(ARRAY(i4)), i442)), java.lang.Object(ARRAY(i4)), i381, i471, i495) -> f1629_0_main_Load(EOS(STATIC_1629(java.lang.Object(ARRAY(i4)), i442)), java.lang.Object(ARRAY(i4)), i381, i495, i471) :|: TRUE 8.29/3.13 f1629_0_main_Load(EOS(STATIC_1629(java.lang.Object(ARRAY(i4)), i442)), java.lang.Object(ARRAY(i4)), i381, i495, i471) -> f1632_0_main_ConstantStackPush(EOS(STATIC_1632(java.lang.Object(ARRAY(i4)), i442)), java.lang.Object(ARRAY(i4)), i495, i471, i381) :|: TRUE 8.29/3.13 f1632_0_main_ConstantStackPush(EOS(STATIC_1632(java.lang.Object(ARRAY(i4)), i442)), java.lang.Object(ARRAY(i4)), i495, i471, i381) -> f1635_0_main_IntArithmetic(EOS(STATIC_1635(java.lang.Object(ARRAY(i4)), i442)), java.lang.Object(ARRAY(i4)), i495, i471, i381, 1) :|: TRUE 8.29/3.13 f1635_0_main_IntArithmetic(EOS(STATIC_1635(java.lang.Object(ARRAY(i4)), i442)), java.lang.Object(ARRAY(i4)), i495, i471, i381, matching1) -> f1638_0_main_Load(EOS(STATIC_1638(java.lang.Object(ARRAY(i4)), i442)), java.lang.Object(ARRAY(i4)), i495, i471, i381 - 1) :|: TRUE && matching1 = 1 8.29/3.13 f1638_0_main_Load(EOS(STATIC_1638(java.lang.Object(ARRAY(i4)), i442)), java.lang.Object(ARRAY(i4)), i495, i471, i496) -> f1641_0_main_IntArithmetic(EOS(STATIC_1641(java.lang.Object(ARRAY(i4)), i442)), java.lang.Object(ARRAY(i4)), i495, i496, i471) :|: TRUE 8.29/3.13 f1641_0_main_IntArithmetic(EOS(STATIC_1641(java.lang.Object(ARRAY(i4)), i442)), java.lang.Object(ARRAY(i4)), i495, i496, i471) -> f1644_0_main_Store(EOS(STATIC_1644(java.lang.Object(ARRAY(i4)), i442)), java.lang.Object(ARRAY(i4)), i495, i496 - i471) :|: i471 >= 0 8.29/3.13 f1644_0_main_Store(EOS(STATIC_1644(java.lang.Object(ARRAY(i4)), i442)), java.lang.Object(ARRAY(i4)), i495, i497) -> f1647_0_main_JMP(EOS(STATIC_1647(java.lang.Object(ARRAY(i4)), i442)), java.lang.Object(ARRAY(i4)), i497, i495) :|: TRUE 8.29/3.13 f1647_0_main_JMP(EOS(STATIC_1647(java.lang.Object(ARRAY(i4)), i442)), java.lang.Object(ARRAY(i4)), i497, i495) -> f1656_0_main_Load(EOS(STATIC_1656(java.lang.Object(ARRAY(i4)), i442)), java.lang.Object(ARRAY(i4)), i497, i495) :|: TRUE 8.29/3.13 f1656_0_main_Load(EOS(STATIC_1656(java.lang.Object(ARRAY(i4)), i442)), java.lang.Object(ARRAY(i4)), i497, i495) -> f1300_0_main_Load(EOS(STATIC_1300(java.lang.Object(ARRAY(i4)), i442)), java.lang.Object(ARRAY(i4)), i497, i495) :|: TRUE 8.29/3.13 f1300_0_main_Load(EOS(STATIC_1300(java.lang.Object(ARRAY(i4)), i39)), java.lang.Object(ARRAY(i4)), i381, i382) -> f1319_0_main_LE(EOS(STATIC_1319(java.lang.Object(ARRAY(i4)), i39)), java.lang.Object(ARRAY(i4)), i381, i382) :|: TRUE 8.29/3.13 f1368_0_random_LT(EOS(STATIC_1368(java.lang.Object(ARRAY(i4)), i39)), java.lang.Object(ARRAY(i4)), i381, i39, i4) -> f1384_0_random_ConstantStackPush(EOS(STATIC_1384(java.lang.Object(ARRAY(i4)), i39)), java.lang.Object(ARRAY(i4)), i381) :|: i39 >= i4 8.29/3.13 f1384_0_random_ConstantStackPush(EOS(STATIC_1384(java.lang.Object(ARRAY(i4)), i39)), java.lang.Object(ARRAY(i4)), i381) -> f1386_0_random_Return(EOS(STATIC_1386(java.lang.Object(ARRAY(i4)), i39)), java.lang.Object(ARRAY(i4)), i381, 0) :|: TRUE 8.29/3.13 f1386_0_random_Return(EOS(STATIC_1386(java.lang.Object(ARRAY(i4)), i39)), java.lang.Object(ARRAY(i4)), i381, matching1) -> f1391_0_main_Store(EOS(STATIC_1391(java.lang.Object(ARRAY(i4)), i39)), java.lang.Object(ARRAY(i4)), i381, 0) :|: TRUE && matching1 = 0 8.29/3.13 f1391_0_main_Store(EOS(STATIC_1391(java.lang.Object(ARRAY(i4)), i39)), java.lang.Object(ARRAY(i4)), i381, matching1) -> f1396_0_main_Load(EOS(STATIC_1396(java.lang.Object(ARRAY(i4)), i39)), java.lang.Object(ARRAY(i4)), i381, 0) :|: TRUE && matching1 = 0 8.29/3.13 f1396_0_main_Load(EOS(STATIC_1396(java.lang.Object(ARRAY(i4)), i39)), java.lang.Object(ARRAY(i4)), i381, matching1) -> f1401_0_main_ConstantStackPush(EOS(STATIC_1401(java.lang.Object(ARRAY(i4)), i39)), java.lang.Object(ARRAY(i4)), i381, 0, i381) :|: TRUE && matching1 = 0 8.29/3.13 f1401_0_main_ConstantStackPush(EOS(STATIC_1401(java.lang.Object(ARRAY(i4)), i39)), java.lang.Object(ARRAY(i4)), i381, matching1, i381) -> f1405_0_main_IntArithmetic(EOS(STATIC_1405(java.lang.Object(ARRAY(i4)), i39)), java.lang.Object(ARRAY(i4)), i381, 0, i381, 1) :|: TRUE && matching1 = 0 8.29/3.13 f1405_0_main_IntArithmetic(EOS(STATIC_1405(java.lang.Object(ARRAY(i4)), i39)), java.lang.Object(ARRAY(i4)), i381, matching1, i381, matching2) -> f1416_0_main_Load(EOS(STATIC_1416(java.lang.Object(ARRAY(i4)), i39)), java.lang.Object(ARRAY(i4)), i381, 0, i381 - 1) :|: TRUE && matching1 = 0 && matching2 = 1 8.29/3.13 f1416_0_main_Load(EOS(STATIC_1416(java.lang.Object(ARRAY(i4)), i39)), java.lang.Object(ARRAY(i4)), i381, matching1, i441) -> f1425_0_main_IntArithmetic(EOS(STATIC_1425(java.lang.Object(ARRAY(i4)), i39)), java.lang.Object(ARRAY(i4)), i381, 0, i441, 0) :|: TRUE && matching1 = 0 8.29/3.13 f1425_0_main_IntArithmetic(EOS(STATIC_1425(java.lang.Object(ARRAY(i4)), i39)), java.lang.Object(ARRAY(i4)), i381, matching1, i441, matching2) -> f1432_0_main_Store(EOS(STATIC_1432(java.lang.Object(ARRAY(i4)), i39)), java.lang.Object(ARRAY(i4)), i381, 0, i441 - 0) :|: TRUE && matching1 = 0 && matching2 = 0 8.29/3.13 f1432_0_main_Store(EOS(STATIC_1432(java.lang.Object(ARRAY(i4)), i39)), java.lang.Object(ARRAY(i4)), i381, matching1, i441) -> f1442_0_main_Load(EOS(STATIC_1442(java.lang.Object(ARRAY(i4)), i39)), java.lang.Object(ARRAY(i4)), i381, i441, 0) :|: TRUE && matching1 = 0 8.29/3.13 f1442_0_main_Load(EOS(STATIC_1442(java.lang.Object(ARRAY(i4)), i39)), java.lang.Object(ARRAY(i4)), i381, i441, matching1) -> f1454_0_main_ConstantStackPush(EOS(STATIC_1454(java.lang.Object(ARRAY(i4)), i39)), java.lang.Object(ARRAY(i4)), i441, 0, i381) :|: TRUE && matching1 = 0 8.29/3.13 f1454_0_main_ConstantStackPush(EOS(STATIC_1454(java.lang.Object(ARRAY(i4)), i39)), java.lang.Object(ARRAY(i4)), i441, matching1, i381) -> f1457_0_main_IntArithmetic(EOS(STATIC_1457(java.lang.Object(ARRAY(i4)), i39)), java.lang.Object(ARRAY(i4)), i441, 0, i381, 1) :|: TRUE && matching1 = 0 8.29/3.13 f1457_0_main_IntArithmetic(EOS(STATIC_1457(java.lang.Object(ARRAY(i4)), i39)), java.lang.Object(ARRAY(i4)), i441, matching1, i381, matching2) -> f1461_0_main_Load(EOS(STATIC_1461(java.lang.Object(ARRAY(i4)), i39)), java.lang.Object(ARRAY(i4)), i441, 0, i381 - 1) :|: TRUE && matching1 = 0 && matching2 = 1 8.29/3.13 f1461_0_main_Load(EOS(STATIC_1461(java.lang.Object(ARRAY(i4)), i39)), java.lang.Object(ARRAY(i4)), i441, matching1, i454) -> f1468_0_main_IntArithmetic(EOS(STATIC_1468(java.lang.Object(ARRAY(i4)), i39)), java.lang.Object(ARRAY(i4)), i441, i454, 0) :|: TRUE && matching1 = 0 8.29/3.13 f1468_0_main_IntArithmetic(EOS(STATIC_1468(java.lang.Object(ARRAY(i4)), i39)), java.lang.Object(ARRAY(i4)), i441, i454, matching1) -> f1472_0_main_Store(EOS(STATIC_1472(java.lang.Object(ARRAY(i4)), i39)), java.lang.Object(ARRAY(i4)), i441, i454 - 0) :|: TRUE && matching1 = 0 8.29/3.13 f1472_0_main_Store(EOS(STATIC_1472(java.lang.Object(ARRAY(i4)), i39)), java.lang.Object(ARRAY(i4)), i441, i454) -> f1480_0_main_JMP(EOS(STATIC_1480(java.lang.Object(ARRAY(i4)), i39)), java.lang.Object(ARRAY(i4)), i454, i441) :|: TRUE 8.29/3.13 f1480_0_main_JMP(EOS(STATIC_1480(java.lang.Object(ARRAY(i4)), i39)), java.lang.Object(ARRAY(i4)), i454, i441) -> f1547_0_main_Load(EOS(STATIC_1547(java.lang.Object(ARRAY(i4)), i39)), java.lang.Object(ARRAY(i4)), i454, i441) :|: TRUE 8.29/3.13 f1547_0_main_Load(EOS(STATIC_1547(java.lang.Object(ARRAY(i4)), i39)), java.lang.Object(ARRAY(i4)), i454, i441) -> f1300_0_main_Load(EOS(STATIC_1300(java.lang.Object(ARRAY(i4)), i39)), java.lang.Object(ARRAY(i4)), i454, i441) :|: TRUE 8.29/3.13 Combined rules. Obtained 2 IRulesP rules: 8.29/3.13 f1319_0_main_LE(EOS(STATIC_1319(java.lang.Object(ARRAY(i4:0)), i39:0)), java.lang.Object(ARRAY(i4:0)), i381:0, i409:0) -> f1319_0_main_LE(EOS(STATIC_1319(java.lang.Object(ARRAY(i4:0)), i39:0 + 1)), java.lang.Object(ARRAY(i4:0)), i381:0 - 1 - i471:0, i381:0 - 1 - i471:0) :|: i409:0 > 0 && i4:0 > -1 && i4:0 > i39:0 && i39:0 > 0 && i471:0 > -1 8.29/3.13 f1319_0_main_LE(EOS(STATIC_1319(java.lang.Object(ARRAY(i4:0)), i39:0)), java.lang.Object(ARRAY(i4:0)), i381:0, i409:0) -> f1319_0_main_LE(EOS(STATIC_1319(java.lang.Object(ARRAY(i4:0)), i39:0)), java.lang.Object(ARRAY(i4:0)), i381:0 - 1, i381:0 - 1) :|: i409:0 > 0 && i4:0 > -1 && i4:0 <= i39:0 8.29/3.13 Finished conversion. Obtained 2 rules.P rules: 8.29/3.13 f1319_0_main_LE(java.lang.Object(ARRAY(i4:0)), i381:0, i409:0, i4:0, i39:0, i4:0) -> f1319_0_main_LE(java.lang.Object(ARRAY(i4:0)), i381:0 - 1 - i471:0, i381:0 - 1 - i471:0, i4:0, i39:0 + 1, i4:0) :|: i4:0 > -1 && i409:0 > 0 && i4:0 > i39:0 && i471:0 > -1 && i39:0 > 0 8.29/3.13 f1319_0_main_LE(java.lang.Object(ARRAY(i4:0)), i381:0, i409:0, i4:0, i39:0, i4:0) -> f1319_0_main_LE(java.lang.Object(ARRAY(i4:0)), i381:0 - 1, i381:0 - 1, i4:0, i39:0, i4:0) :|: i4:0 > -1 && i4:0 <= i39:0 && i409:0 > 0 8.29/3.13 8.29/3.13 ---------------------------------------- 8.29/3.13 8.29/3.13 (8) 8.29/3.13 Obligation: 8.29/3.13 Rules: 8.29/3.13 f1319_0_main_LE(java.lang.Object(ARRAY(i4:0)), i381:0, i409:0, i4:0, i39:0, i4:0) -> f1319_0_main_LE(java.lang.Object(ARRAY(i4:0)), i381:0 - 1 - i471:0, i381:0 - 1 - i471:0, i4:0, i39:0 + 1, i4:0) :|: i4:0 > -1 && i409:0 > 0 && i4:0 > i39:0 && i471:0 > -1 && i39:0 > 0 8.29/3.13 f1319_0_main_LE(java.lang.Object(ARRAY(x)), x1, x2, x, x3, x) -> f1319_0_main_LE(java.lang.Object(ARRAY(x)), x1 - 1, x1 - 1, x, x3, x) :|: x > -1 && x <= x3 && x2 > 0 8.29/3.13 8.29/3.13 ---------------------------------------- 8.29/3.13 8.29/3.13 (9) IRSFormatTransformerProof (EQUIVALENT) 8.29/3.13 Reformatted IRS to match normalized format (transformed away non-linear left-hand sides, !=, / and %). 8.29/3.13 ---------------------------------------- 8.29/3.13 8.29/3.13 (10) 8.29/3.13 Obligation: 8.29/3.13 Rules: 8.29/3.13 f1319_0_main_LE(java.lang.Object(ARRAY(i4:0)), i381:0, i409:0, i4:0, i39:0, i4:0) -> f1319_0_main_LE(java.lang.Object(ARRAY(i4:0)), arith, arith, i4:0, arith1, i4:0) :|: i4:0 > -1 && i409:0 > 0 && i4:0 > i39:0 && i471:0 > -1 && i39:0 > 0 && arith = i381:0 - 1 - i471:0 && arith = i381:0 - 1 - i471:0 && arith1 = i39:0 + 1 8.29/3.13 f1319_0_main_LE(java.lang.Object(ARRAY(x4)), x5, x6, x4, x7, x4) -> f1319_0_main_LE(java.lang.Object(ARRAY(x4)), x8, x8, x4, x7, x4) :|: x4 > -1 && x4 <= x7 && x6 > 0 && x8 = x5 - 1 && x8 = x5 - 1 8.29/3.13 8.29/3.13 ---------------------------------------- 8.29/3.13 8.29/3.13 (11) IRSwTTerminationDigraphProof (EQUIVALENT) 8.29/3.13 Constructed termination digraph! 8.29/3.13 Nodes: 8.29/3.13 (1) f1319_0_main_LE(java.lang.Object(ARRAY(i4:0)), i381:0, i409:0, i4:0, i39:0, i4:0) -> f1319_0_main_LE(java.lang.Object(ARRAY(i4:0)), arith, arith, i4:0, arith1, i4:0) :|: i4:0 > -1 && i409:0 > 0 && i4:0 > i39:0 && i471:0 > -1 && i39:0 > 0 && arith = i381:0 - 1 - i471:0 && arith = i381:0 - 1 - i471:0 && arith1 = i39:0 + 1 8.29/3.13 (2) f1319_0_main_LE(java.lang.Object(ARRAY(x4)), x5, x6, x4, x7, x4) -> f1319_0_main_LE(java.lang.Object(ARRAY(x4)), x8, x8, x4, x7, x4) :|: x4 > -1 && x4 <= x7 && x6 > 0 && x8 = x5 - 1 && x8 = x5 - 1 8.29/3.13 8.29/3.13 Arcs: 8.29/3.13 (1) -> (1), (2) 8.29/3.13 (2) -> (2) 8.29/3.13 8.29/3.13 This digraph is fully evaluated! 8.29/3.13 ---------------------------------------- 8.29/3.13 8.29/3.13 (12) 8.29/3.13 Complex Obligation (AND) 8.29/3.13 8.29/3.13 ---------------------------------------- 8.29/3.13 8.29/3.13 (13) 8.29/3.13 Obligation: 8.29/3.13 8.29/3.13 Termination digraph: 8.29/3.13 Nodes: 8.29/3.13 (1) f1319_0_main_LE(java.lang.Object(ARRAY(i4:0)), i381:0, i409:0, i4:0, i39:0, i4:0) -> f1319_0_main_LE(java.lang.Object(ARRAY(i4:0)), arith, arith, i4:0, arith1, i4:0) :|: i4:0 > -1 && i409:0 > 0 && i4:0 > i39:0 && i471:0 > -1 && i39:0 > 0 && arith = i381:0 - 1 - i471:0 && arith = i381:0 - 1 - i471:0 && arith1 = i39:0 + 1 8.29/3.13 8.29/3.13 Arcs: 8.29/3.13 (1) -> (1) 8.29/3.13 8.29/3.13 This digraph is fully evaluated! 8.29/3.13 8.29/3.13 ---------------------------------------- 8.29/3.13 8.29/3.13 (14) IntTRSCompressionProof (EQUIVALENT) 8.29/3.13 Compressed rules. 8.29/3.13 ---------------------------------------- 8.29/3.13 8.29/3.13 (15) 8.29/3.13 Obligation: 8.29/3.13 Rules: 8.29/3.13 f1319_0_main_LE(java.lang.Object(ARRAY(i4:0:0)), i381:0:0, i409:0:0, i4:0:0, i39:0:0, i4:0:0) -> f1319_0_main_LE(java.lang.Object(ARRAY(i4:0:0)), i381:0:0 - 1 - i471:0:0, i381:0:0 - 1 - i471:0:0, i4:0:0, i39:0:0 + 1, i4:0:0) :|: i471:0:0 > -1 && i39:0:0 > 0 && i4:0:0 > i39:0:0 && i409:0:0 > 0 && i4:0:0 > -1 8.29/3.13 8.29/3.13 ---------------------------------------- 8.29/3.13 8.29/3.13 (16) TempFilterProof (SOUND) 8.29/3.13 Used the following sort dictionary for filtering: 8.29/3.13 f1319_0_main_LE(VARIABLE, VARIABLE, INTEGER, INTEGER, INTEGER, INTEGER) 8.29/3.13 java.lang.Object(VARIABLE) 8.29/3.13 ARRAY(INTEGER) 8.29/3.13 Replaced non-predefined constructor symbols by 0. 8.29/3.13 ---------------------------------------- 8.29/3.13 8.29/3.13 (17) 8.29/3.13 Obligation: 8.29/3.13 Rules: 8.29/3.13 f1319_0_main_LE(c, i381:0:0, i409:0:0, i4:0:0, i39:0:0, i4:0:0) -> f1319_0_main_LE(c1, c2, c3, i4:0:0, c4, i4:0:0) :|: c4 = i39:0:0 + 1 && (c3 = i381:0:0 - 1 - i471:0:0 && (c2 = i381:0:0 - 1 - i471:0:0 && (c1 = 0 && c = 0))) && (i471:0:0 > -1 && i39:0:0 > 0 && i4:0:0 > i39:0:0 && i409:0:0 > 0 && i4:0:0 > -1) 8.29/3.13 8.29/3.13 ---------------------------------------- 8.29/3.13 8.29/3.13 (18) PolynomialOrderProcessor (EQUIVALENT) 8.29/3.13 Found the following polynomial interpretation: 8.29/3.13 [f1319_0_main_LE(x, x1, x2, x3, x4, x5)] = -1 + c*x - x4 + x5 8.29/3.13 8.29/3.13 The following rules are decreasing: 8.29/3.13 f1319_0_main_LE(c, i381:0:0, i409:0:0, i4:0:0, i39:0:0, i4:0:0) -> f1319_0_main_LE(c1, c2, c3, i4:0:0, c4, i4:0:0) :|: c4 = i39:0:0 + 1 && (c3 = i381:0:0 - 1 - i471:0:0 && (c2 = i381:0:0 - 1 - i471:0:0 && (c1 = 0 && c = 0))) && (i471:0:0 > -1 && i39:0:0 > 0 && i4:0:0 > i39:0:0 && i409:0:0 > 0 && i4:0:0 > -1) 8.29/3.13 The following rules are bounded: 8.29/3.13 f1319_0_main_LE(c, i381:0:0, i409:0:0, i4:0:0, i39:0:0, i4:0:0) -> f1319_0_main_LE(c1, c2, c3, i4:0:0, c4, i4:0:0) :|: c4 = i39:0:0 + 1 && (c3 = i381:0:0 - 1 - i471:0:0 && (c2 = i381:0:0 - 1 - i471:0:0 && (c1 = 0 && c = 0))) && (i471:0:0 > -1 && i39:0:0 > 0 && i4:0:0 > i39:0:0 && i409:0:0 > 0 && i4:0:0 > -1) 8.29/3.13 8.29/3.13 ---------------------------------------- 8.29/3.13 8.29/3.13 (19) 8.29/3.13 YES 8.29/3.13 8.29/3.13 ---------------------------------------- 8.29/3.13 8.29/3.13 (20) 8.29/3.13 Obligation: 8.29/3.13 8.29/3.13 Termination digraph: 8.29/3.13 Nodes: 8.29/3.13 (1) f1319_0_main_LE(java.lang.Object(ARRAY(x4)), x5, x6, x4, x7, x4) -> f1319_0_main_LE(java.lang.Object(ARRAY(x4)), x8, x8, x4, x7, x4) :|: x4 > -1 && x4 <= x7 && x6 > 0 && x8 = x5 - 1 && x8 = x5 - 1 8.29/3.13 8.29/3.13 Arcs: 8.29/3.13 (1) -> (1) 8.29/3.13 8.29/3.13 This digraph is fully evaluated! 8.29/3.13 8.29/3.13 ---------------------------------------- 8.29/3.13 8.29/3.13 (21) IntTRSCompressionProof (EQUIVALENT) 8.29/3.13 Compressed rules. 8.29/3.13 ---------------------------------------- 8.29/3.13 8.29/3.13 (22) 8.29/3.13 Obligation: 8.29/3.13 Rules: 8.29/3.13 f1319_0_main_LE(java.lang.Object(ARRAY(x4:0)), x5:0, x6:0, x4:0, x7:0, x4:0) -> f1319_0_main_LE(java.lang.Object(ARRAY(x4:0)), x5:0 - 1, x5:0 - 1, x4:0, x7:0, x4:0) :|: x4:0 > -1 && x7:0 >= x4:0 && x6:0 > 0 8.29/3.13 8.29/3.13 ---------------------------------------- 8.29/3.13 8.29/3.13 (23) TempFilterProof (SOUND) 8.29/3.13 Used the following sort dictionary for filtering: 8.29/3.13 f1319_0_main_LE(VARIABLE, VARIABLE, INTEGER, INTEGER, INTEGER, INTEGER) 8.29/3.13 java.lang.Object(VARIABLE) 8.29/3.13 ARRAY(INTEGER) 8.29/3.13 Replaced non-predefined constructor symbols by 0. 8.29/3.13 ---------------------------------------- 8.29/3.13 8.29/3.13 (24) 8.29/3.13 Obligation: 8.29/3.13 Rules: 8.29/3.13 f1319_0_main_LE(c, x5:0, x6:0, x4:0, x7:0, x4:0) -> f1319_0_main_LE(c1, c2, c3, x4:0, x7:0, x4:0) :|: c3 = x5:0 - 1 && (c2 = x5:0 - 1 && (c1 = 0 && c = 0)) && (x4:0 > -1 && x7:0 >= x4:0 && x6:0 > 0) 8.29/3.13 8.29/3.13 ---------------------------------------- 8.29/3.13 8.29/3.13 (25) PolynomialOrderProcessor (EQUIVALENT) 8.29/3.13 Found the following polynomial interpretation: 8.29/3.13 [f1319_0_main_LE(x, x1, x2, x3, x4, x5)] = -2 + c*x + c12*x*x1 + c13*x*x2 + c14*x*x3 + c15*x*x4 + c16*x*x5 + c1*x^2 + x1^2 + 2*x2 8.29/3.13 8.29/3.13 The following rules are decreasing: 8.29/3.13 f1319_0_main_LE(c, x5:0, x6:0, x4:0, x7:0, x4:0) -> f1319_0_main_LE(c1, c2, c3, x4:0, x7:0, x4:0) :|: c3 = x5:0 - 1 && (c2 = x5:0 - 1 && (c1 = 0 && c = 0)) && (x4:0 > -1 && x7:0 >= x4:0 && x6:0 > 0) 8.29/3.13 The following rules are bounded: 8.29/3.13 f1319_0_main_LE(c, x5:0, x6:0, x4:0, x7:0, x4:0) -> f1319_0_main_LE(c1, c2, c3, x4:0, x7:0, x4:0) :|: c3 = x5:0 - 1 && (c2 = x5:0 - 1 && (c1 = 0 && c = 0)) && (x4:0 > -1 && x7:0 >= x4:0 && x6:0 > 0) 8.29/3.13 8.29/3.13 ---------------------------------------- 8.29/3.13 8.29/3.13 (26) 8.29/3.13 YES 8.59/3.20 EOF