25.67/13.83 MAYBE 25.67/13.84 proof of /export/starexec/sandbox2/benchmark/theBenchmark.jar 25.67/13.84 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 25.67/13.84 25.67/13.84 25.67/13.84 termination of the given Bare JBC problem could not be shown: 25.67/13.84 25.67/13.84 (0) Bare JBC problem 25.67/13.84 (1) BareJBCToJBCProof [EQUIVALENT, 96 ms] 25.67/13.84 (2) JBC problem 25.67/13.84 (3) JBCToGraph [EQUIVALENT, 892 ms] 25.67/13.84 (4) JBCTerminationGraph 25.67/13.84 (5) TerminationGraphToSCCProof [SOUND, 0 ms] 25.67/13.84 (6) AND 25.67/13.84 (7) JBCTerminationSCC 25.67/13.84 (8) SCCToIRSProof [SOUND, 120 ms] 25.67/13.84 (9) IRSwT 25.67/13.84 (10) IRSFormatTransformerProof [EQUIVALENT, 0 ms] 25.67/13.84 (11) IRSwT 25.67/13.84 (12) IntTRSCompressionProof [EQUIVALENT, 0 ms] 25.67/13.84 (13) IRSwT 25.67/13.84 (14) TempFilterProof [SOUND, 1579 ms] 25.67/13.84 (15) IRSwT 25.67/13.84 (16) IntTRSCompressionProof [EQUIVALENT, 0 ms] 25.67/13.84 (17) IRSwT 25.67/13.84 (18) JBCTerminationSCC 25.67/13.84 (19) SCCToIRSProof [SOUND, 27 ms] 25.67/13.84 (20) IRSwT 25.67/13.84 (21) IRSFormatTransformerProof [EQUIVALENT, 0 ms] 25.67/13.84 (22) IRSwT 25.67/13.84 (23) IRSwTTerminationDigraphProof [EQUIVALENT, 107 ms] 25.67/13.84 (24) IRSwT 25.67/13.84 (25) IntTRSCompressionProof [EQUIVALENT, 0 ms] 25.67/13.84 (26) IRSwT 25.67/13.84 (27) FilterProof [EQUIVALENT, 0 ms] 25.67/13.84 (28) IntTRS 25.67/13.84 (29) IntTRSCompressionProof [EQUIVALENT, 0 ms] 25.67/13.84 (30) IntTRS 25.67/13.84 (31) IntTRSPeriodicNontermProof [COMPLETE, 10 ms] 25.67/13.84 (32) NO 25.67/13.84 (33) JBCTerminationSCC 25.67/13.84 (34) SCCToIRSProof [SOUND, 22 ms] 25.67/13.84 (35) IRSwT 25.67/13.84 (36) IRSFormatTransformerProof [EQUIVALENT, 0 ms] 25.67/13.84 (37) IRSwT 25.67/13.84 (38) IRSwTTerminationDigraphProof [EQUIVALENT, 0 ms] 25.67/13.84 (39) IRSwT 25.67/13.84 (40) IntTRSCompressionProof [EQUIVALENT, 0 ms] 25.67/13.84 (41) IRSwT 25.67/13.84 (42) TempFilterProof [SOUND, 37 ms] 25.67/13.84 (43) IntTRS 25.67/13.84 (44) PolynomialOrderProcessor [EQUIVALENT, 15 ms] 25.67/13.84 (45) YES 25.67/13.84 25.67/13.84 25.67/13.84 ---------------------------------------- 25.67/13.84 25.67/13.84 (0) 25.67/13.84 Obligation: 25.67/13.84 need to prove termination of the following program: 25.67/13.84 /** 25.67/13.84 * Rather inefficient random number generator that can generate infinitely 25.67/13.84 * many positive integers from a single positive integer (the 25.67/13.84 * "random source") by taking the exponents of its prime factorization. 25.67/13.84 */ 25.67/13.84 public class RandomHard { 25.67/13.84 25.67/13.84 // a single natural number, to give rise to infinitely many natural numbers 25.67/13.84 // from its prime factorization (if the datatype int had infinite precision) 25.67/13.84 final private int source; 25.67/13.84 25.67/13.84 // use the exponent of the nextPrimeIndex-th prime in the unique 25.67/13.84 // prime factorization of source as the next "randomly generated" 25.67/13.84 // natural number 25.67/13.84 private int nextPrimeIndex; 25.67/13.84 25.67/13.84 public RandomHard(int source) { 25.67/13.84 this.source = source; 25.67/13.84 this.nextPrimeIndex = 1; 25.67/13.84 } 25.67/13.84 25.67/13.84 public static void main(String[] args) { 25.67/13.84 int source = args[0].length(); 25.67/13.84 25.67/13.84 if (source < 1) { 25.67/13.84 return; 25.67/13.84 } 25.67/13.84 RandomHard random = new RandomHard(source); 25.67/13.84 int limit = args[1].length(); 25.67/13.84 for (int i = 0; i < limit; ++i) { 25.67/13.84 random.getNext(); 25.67/13.84 } 25.67/13.84 } 25.67/13.84 25.67/13.84 /** @return the next (random!) natural number */ 25.67/13.84 public int getNext() { 25.67/13.84 int prime = findKthPrime(this.nextPrimeIndex); 25.67/13.84 ++this.nextPrimeIndex; 25.67/13.84 int res = getPowerOfKInSource(prime); 25.67/13.84 return res; 25.67/13.84 } 25.67/13.84 25.67/13.84 /** @return How often can we divide source by k without remainder? */ 25.67/13.84 private int getPowerOfKInSource(int k) { 25.67/13.84 /*if (k < 2) { 25.67/13.84 throw new RuntimeException("Divide only by primes -- they are >= 2!"); 25.67/13.84 }*/ 25.67/13.84 int divisor = this.source; 25.67/13.84 int res = 0; 25.67/13.84 while (divisor % k == 0) { 25.67/13.84 divisor = divisor / k; 25.67/13.84 ++res; 25.67/13.84 } 25.67/13.84 return res; 25.67/13.84 } 25.67/13.84 25.67/13.84 /** @return the k-th prime number for k > 0 */ 25.67/13.84 private int findKthPrime(int k) { 25.67/13.84 int yippi = 0; 25.67/13.84 int cand = 1; 25.67/13.84 // termination of this loop on the integers follows from 25.67/13.84 // the existence of infinitely many prime numbers 25.67/13.84 while (yippi < k) { 25.67/13.84 ++cand; // all prime numbers are >= 2, so increment 25.67/13.84 boolean isPrime = checkPrime(cand); 25.67/13.84 if (isPrime) { 25.67/13.84 ++yippi; 25.67/13.84 } 25.67/13.84 } 25.67/13.84 return cand; 25.67/13.84 } 25.67/13.84 25.67/13.84 /** @return Is n prime? */ 25.67/13.84 private static boolean checkPrime(int n) { 25.67/13.84 if (n < 2) { 25.67/13.84 return false; 25.67/13.84 } 25.67/13.84 for (int i = 2; i < n; ++i) { 25.67/13.84 if (n % i == 0) { // i divides n and 1 < i < n 25.67/13.84 return false; 25.67/13.84 } 25.67/13.84 } 25.67/13.84 return true; 25.67/13.84 } 25.67/13.84 } 25.67/13.84 25.67/13.84 25.67/13.84 25.67/13.84 ---------------------------------------- 25.67/13.84 25.67/13.84 (1) BareJBCToJBCProof (EQUIVALENT) 25.67/13.84 initialized classpath 25.67/13.84 ---------------------------------------- 25.67/13.84 25.67/13.84 (2) 25.67/13.84 Obligation: 25.67/13.84 need to prove termination of the following program: 25.67/13.84 /** 25.67/13.84 * Rather inefficient random number generator that can generate infinitely 25.67/13.84 * many positive integers from a single positive integer (the 25.67/13.84 * "random source") by taking the exponents of its prime factorization. 25.67/13.84 */ 25.67/13.84 public class RandomHard { 25.67/13.84 25.67/13.84 // a single natural number, to give rise to infinitely many natural numbers 25.67/13.84 // from its prime factorization (if the datatype int had infinite precision) 25.67/13.84 final private int source; 25.67/13.84 25.67/13.84 // use the exponent of the nextPrimeIndex-th prime in the unique 25.67/13.84 // prime factorization of source as the next "randomly generated" 25.67/13.84 // natural number 25.67/13.84 private int nextPrimeIndex; 25.67/13.84 25.67/13.84 public RandomHard(int source) { 25.67/13.84 this.source = source; 25.67/13.84 this.nextPrimeIndex = 1; 25.67/13.84 } 25.67/13.84 25.67/13.84 public static void main(String[] args) { 25.67/13.84 int source = args[0].length(); 25.67/13.84 25.67/13.84 if (source < 1) { 25.67/13.84 return; 25.67/13.84 } 25.67/13.84 RandomHard random = new RandomHard(source); 25.67/13.84 int limit = args[1].length(); 25.67/13.84 for (int i = 0; i < limit; ++i) { 25.67/13.84 random.getNext(); 25.67/13.84 } 25.67/13.84 } 25.67/13.84 25.67/13.84 /** @return the next (random!) natural number */ 25.67/13.84 public int getNext() { 25.67/13.84 int prime = findKthPrime(this.nextPrimeIndex); 25.67/13.84 ++this.nextPrimeIndex; 25.67/13.84 int res = getPowerOfKInSource(prime); 25.67/13.84 return res; 25.67/13.84 } 25.67/13.84 25.67/13.84 /** @return How often can we divide source by k without remainder? */ 25.67/13.84 private int getPowerOfKInSource(int k) { 25.67/13.84 /*if (k < 2) { 25.67/13.84 throw new RuntimeException("Divide only by primes -- they are >= 2!"); 25.67/13.84 }*/ 25.67/13.84 int divisor = this.source; 25.67/13.84 int res = 0; 25.67/13.84 while (divisor % k == 0) { 25.67/13.84 divisor = divisor / k; 25.67/13.84 ++res; 25.67/13.84 } 25.67/13.84 return res; 25.67/13.84 } 25.67/13.84 25.67/13.84 /** @return the k-th prime number for k > 0 */ 25.67/13.84 private int findKthPrime(int k) { 25.67/13.84 int yippi = 0; 25.67/13.84 int cand = 1; 25.67/13.84 // termination of this loop on the integers follows from 25.67/13.84 // the existence of infinitely many prime numbers 25.67/13.84 while (yippi < k) { 25.67/13.84 ++cand; // all prime numbers are >= 2, so increment 25.67/13.84 boolean isPrime = checkPrime(cand); 25.67/13.84 if (isPrime) { 25.67/13.84 ++yippi; 25.67/13.84 } 25.67/13.84 } 25.67/13.84 return cand; 25.67/13.84 } 25.67/13.84 25.67/13.84 /** @return Is n prime? */ 25.67/13.84 private static boolean checkPrime(int n) { 25.67/13.84 if (n < 2) { 25.67/13.84 return false; 25.67/13.84 } 25.67/13.84 for (int i = 2; i < n; ++i) { 25.67/13.84 if (n % i == 0) { // i divides n and 1 < i < n 25.67/13.84 return false; 25.67/13.84 } 25.67/13.84 } 25.67/13.84 return true; 25.67/13.84 } 25.67/13.84 } 25.67/13.84 25.67/13.84 25.67/13.84 25.67/13.84 ---------------------------------------- 25.67/13.84 25.67/13.84 (3) JBCToGraph (EQUIVALENT) 25.67/13.84 Constructed TerminationGraph. 25.67/13.84 ---------------------------------------- 25.67/13.84 25.67/13.84 (4) 25.67/13.84 Obligation: 25.67/13.84 Termination Graph based on JBC Program: 25.67/13.84 RandomHard.main([Ljava/lang/String;)V: Graph of 161 nodes with 1 SCC. 25.67/13.84 25.67/13.84 25.67/13.84 25.67/13.84 RandomHard.getNext()I: Graph of 68 nodes with 1 SCC. 25.67/13.84 25.67/13.84 25.67/13.84 25.67/13.84 RandomHard.findKthPrime(I)I: Graph of 64 nodes with 1 SCC. 25.67/13.84 25.67/13.84 25.67/13.84 25.67/13.84 25.67/13.84 25.67/13.84 ---------------------------------------- 25.67/13.84 25.67/13.84 (5) TerminationGraphToSCCProof (SOUND) 25.67/13.84 Splitted TerminationGraph to 3 SCCss. 25.67/13.84 ---------------------------------------- 25.67/13.84 25.67/13.84 (6) 25.67/13.84 Complex Obligation (AND) 25.67/13.84 25.67/13.84 ---------------------------------------- 25.67/13.84 25.67/13.84 (7) 25.67/13.84 Obligation: 25.67/13.84 SCC of termination graph based on JBC Program. 25.67/13.84 SCC contains nodes from the following methods: RandomHard.findKthPrime(I)I 25.67/13.84 SCC calls the following helper methods: 25.67/13.84 Performed SCC analyses: 25.67/13.84 *Used field analysis yielded the following read fields: 25.67/13.84 25.67/13.84 *Marker field analysis yielded the following relations that could be markers: 25.67/13.84 25.67/13.84 ---------------------------------------- 25.67/13.84 25.67/13.84 (8) SCCToIRSProof (SOUND) 25.67/13.84 Transformed FIGraph SCCs to intTRSs. Log: 25.67/13.84 Generated rules. Obtained 56 IRulesP rules: 25.67/13.84 f4854_0_findKthPrime_Load(EOS(STATIC_4854), i547, i547, i548, i549, i548) -> f4858_0_findKthPrime_GE(EOS(STATIC_4858), i547, i547, i548, i549, i548, i547) :|: TRUE 25.67/13.84 f4858_0_findKthPrime_GE(EOS(STATIC_4858), i547, i547, i548, i549, i548, i547) -> f4908_0_findKthPrime_GE(EOS(STATIC_4908), i547, i547, i548, i549, i548, i547) :|: i548 < i547 25.67/13.84 f4908_0_findKthPrime_GE(EOS(STATIC_4908), i547, i547, i548, i549, i548, i547) -> f4916_0_findKthPrime_Inc(EOS(STATIC_4916), i547, i547, i548, i549) :|: i548 < i547 25.67/13.84 f4916_0_findKthPrime_Inc(EOS(STATIC_4916), i547, i547, i548, i549) -> f4924_0_findKthPrime_Load(EOS(STATIC_4924), i547, i547, i548, i549 + 1) :|: TRUE 25.67/13.84 f4924_0_findKthPrime_Load(EOS(STATIC_4924), i547, i547, i548, i557) -> f4929_0_findKthPrime_InvokeMethod(EOS(STATIC_4929), i547, i547, i548, i557, i557) :|: TRUE 25.67/13.84 f4929_0_findKthPrime_InvokeMethod(EOS(STATIC_4929), i547, i547, i548, i557, i557) -> f4932_0_checkPrime_Load(EOS(STATIC_4932), i547, i547, i548, i557, i557) :|: TRUE 25.67/13.84 f4932_0_checkPrime_Load(EOS(STATIC_4932), i547, i547, i548, i557, i557) -> f4939_0_checkPrime_ConstantStackPush(EOS(STATIC_4939), i547, i547, i548, i557, i557, i557) :|: TRUE 25.67/13.84 f4939_0_checkPrime_ConstantStackPush(EOS(STATIC_4939), i547, i547, i548, i557, i557, i557) -> f4941_0_checkPrime_GE(EOS(STATIC_4941), i547, i547, i548, i557, i557, i557, 2) :|: TRUE 25.67/13.84 f4941_0_checkPrime_GE(EOS(STATIC_4941), i547, i547, i548, i566, i566, i566, matching1) -> f4951_0_checkPrime_GE(EOS(STATIC_4951), i547, i547, i548, i566, i566, i566, 2) :|: TRUE && matching1 = 2 25.67/13.85 f4941_0_checkPrime_GE(EOS(STATIC_4941), i547, i547, i548, i567, i567, i567, matching1) -> f4952_0_checkPrime_GE(EOS(STATIC_4952), i547, i547, i548, i567, i567, i567, 2) :|: TRUE && matching1 = 2 25.67/13.85 f4951_0_checkPrime_GE(EOS(STATIC_4951), i547, i547, i548, i566, i566, i566, matching1) -> f4959_0_checkPrime_ConstantStackPush(EOS(STATIC_4959), i547, i547, i548, i566) :|: i566 < 2 && matching1 = 2 25.67/13.85 f4959_0_checkPrime_ConstantStackPush(EOS(STATIC_4959), i547, i547, i548, i566) -> f4968_0_checkPrime_Return(EOS(STATIC_4968), i547, i547, i548, i566, 0) :|: TRUE 25.67/13.85 f4968_0_checkPrime_Return(EOS(STATIC_4968), i547, i547, i548, i566, matching1) -> f4973_0_findKthPrime_Store(EOS(STATIC_4973), i547, i547, i548, i566, 0) :|: TRUE && matching1 = 0 25.67/13.85 f4973_0_findKthPrime_Store(EOS(STATIC_4973), i547, i547, i548, i566, matching1) -> f4977_0_findKthPrime_Load(EOS(STATIC_4977), i547, i547, i548, i566, 0) :|: TRUE && matching1 = 0 25.67/13.85 f4977_0_findKthPrime_Load(EOS(STATIC_4977), i547, i547, i548, i566, matching1) -> f4984_0_findKthPrime_EQ(EOS(STATIC_4984), i547, i547, i548, i566, 0) :|: TRUE && matching1 = 0 25.67/13.85 f4984_0_findKthPrime_EQ(EOS(STATIC_4984), i547, i547, i548, i566, matching1) -> f4991_0_findKthPrime_JMP(EOS(STATIC_4991), i547, i547, i548, i566) :|: TRUE && matching1 = 0 25.67/13.85 f4991_0_findKthPrime_JMP(EOS(STATIC_4991), i547, i547, i548, i566) -> f5021_0_findKthPrime_Load(EOS(STATIC_5021), i547, i547, i548, i566) :|: TRUE 25.67/13.85 f5021_0_findKthPrime_Load(EOS(STATIC_5021), i547, i547, i548, i566) -> f4850_0_findKthPrime_Load(EOS(STATIC_4850), i547, i547, i548, i566) :|: TRUE 25.67/13.85 f4850_0_findKthPrime_Load(EOS(STATIC_4850), i547, i547, i548, i549) -> f4854_0_findKthPrime_Load(EOS(STATIC_4854), i547, i547, i548, i549, i548) :|: TRUE 25.67/13.85 f4952_0_checkPrime_GE(EOS(STATIC_4952), i547, i547, i548, i567, i567, i567, matching1) -> f4963_0_checkPrime_ConstantStackPush(EOS(STATIC_4963), i547, i547, i548, i567, i567) :|: i567 >= 2 && matching1 = 2 25.67/13.85 f4963_0_checkPrime_ConstantStackPush(EOS(STATIC_4963), i547, i547, i548, i567, i567) -> f4970_0_checkPrime_Store(EOS(STATIC_4970), i547, i547, i548, i567, i567, 2) :|: TRUE 25.67/13.85 f4970_0_checkPrime_Store(EOS(STATIC_4970), i547, i547, i548, i567, i567, matching1) -> f4974_0_checkPrime_Load(EOS(STATIC_4974), i547, i547, i548, i567, i567, 2) :|: TRUE && matching1 = 2 25.67/13.85 f4974_0_checkPrime_Load(EOS(STATIC_4974), i547, i547, i548, i567, i567, matching1) -> f5137_0_checkPrime_Load(EOS(STATIC_5137), i547, i547, i548, i567, i567, 2) :|: TRUE && matching1 = 2 25.67/13.85 f5137_0_checkPrime_Load(EOS(STATIC_5137), i547, i547, i548, i579, i579, i580) -> f5236_0_checkPrime_Load(EOS(STATIC_5236), i547, i547, i548, i579, i579, i580) :|: TRUE 25.67/13.85 f5236_0_checkPrime_Load(EOS(STATIC_5236), i547, i547, i548, i596, i596, i597) -> f5491_0_checkPrime_Load(EOS(STATIC_5491), i547, i547, i548, i596, i596, i597) :|: TRUE 25.67/13.85 f5491_0_checkPrime_Load(EOS(STATIC_5491), i547, i547, i548, i655, i655, i656) -> f5494_0_checkPrime_Load(EOS(STATIC_5494), i547, i547, i548, i655, i655, i656, i656) :|: TRUE 25.67/13.85 f5494_0_checkPrime_Load(EOS(STATIC_5494), i547, i547, i548, i655, i655, i656, i656) -> f5498_0_checkPrime_GE(EOS(STATIC_5498), i547, i547, i548, i655, i655, i656, i656, i655) :|: TRUE 25.67/13.85 f5498_0_checkPrime_GE(EOS(STATIC_5498), i547, i547, i548, i655, i655, i656, i656, i655) -> f5502_0_checkPrime_GE(EOS(STATIC_5502), i547, i547, i548, i655, i655, i656, i656, i655) :|: i656 >= i655 25.67/13.85 f5498_0_checkPrime_GE(EOS(STATIC_5498), i547, i547, i548, i655, i655, i656, i656, i655) -> f5503_0_checkPrime_GE(EOS(STATIC_5503), i547, i547, i548, i655, i655, i656, i656, i655) :|: i656 < i655 25.67/13.85 f5502_0_checkPrime_GE(EOS(STATIC_5502), i547, i547, i548, i655, i655, i656, i656, i655) -> f5506_0_checkPrime_ConstantStackPush(EOS(STATIC_5506), i547, i547, i548, i655) :|: i656 >= i655 25.67/13.85 f5506_0_checkPrime_ConstantStackPush(EOS(STATIC_5506), i547, i547, i548, i655) -> f5511_0_checkPrime_Return(EOS(STATIC_5511), i547, i547, i548, i655, 1) :|: TRUE 25.67/13.85 f5511_0_checkPrime_Return(EOS(STATIC_5511), i547, i547, i548, i655, matching1) -> f5516_0_findKthPrime_Store(EOS(STATIC_5516), i547, i547, i548, i655, 1) :|: TRUE && matching1 = 1 25.67/13.85 f5516_0_findKthPrime_Store(EOS(STATIC_5516), i547, i547, i548, i655, matching1) -> f5521_0_findKthPrime_Load(EOS(STATIC_5521), i547, i547, i548, i655, 1) :|: TRUE && matching1 = 1 25.67/13.85 f5521_0_findKthPrime_Load(EOS(STATIC_5521), i547, i547, i548, i655, matching1) -> f5526_0_findKthPrime_EQ(EOS(STATIC_5526), i547, i547, i548, i655, 1) :|: TRUE && matching1 = 1 25.67/13.85 f5526_0_findKthPrime_EQ(EOS(STATIC_5526), i547, i547, i548, i655, matching1) -> f5532_0_findKthPrime_Inc(EOS(STATIC_5532), i547, i547, i548, i655) :|: 1 > 0 && matching1 = 1 25.67/13.85 f5532_0_findKthPrime_Inc(EOS(STATIC_5532), i547, i547, i548, i655) -> f5537_0_findKthPrime_JMP(EOS(STATIC_5537), i547, i547, i548 + 1, i655) :|: TRUE 25.67/13.85 f5537_0_findKthPrime_JMP(EOS(STATIC_5537), i547, i547, i692, i655) -> f5543_0_findKthPrime_Load(EOS(STATIC_5543), i547, i547, i692, i655) :|: TRUE 25.67/13.85 f5543_0_findKthPrime_Load(EOS(STATIC_5543), i547, i547, i692, i655) -> f4850_0_findKthPrime_Load(EOS(STATIC_4850), i547, i547, i692, i655) :|: TRUE 25.67/13.85 f5503_0_checkPrime_GE(EOS(STATIC_5503), i547, i547, i548, i655, i655, i656, i656, i655) -> f5507_0_checkPrime_Load(EOS(STATIC_5507), i547, i547, i548, i655, i655, i656) :|: i656 < i655 25.67/13.85 f5507_0_checkPrime_Load(EOS(STATIC_5507), i547, i547, i548, i655, i655, i656) -> f5512_0_checkPrime_Load(EOS(STATIC_5512), i547, i547, i548, i655, i655, i656, i655) :|: TRUE 25.67/13.85 f5512_0_checkPrime_Load(EOS(STATIC_5512), i547, i547, i548, i655, i655, i656, i655) -> f5517_0_checkPrime_IntArithmetic(EOS(STATIC_5517), i547, i547, i548, i655, i655, i656, i655, i656) :|: TRUE 25.67/13.85 f5517_0_checkPrime_IntArithmetic(EOS(STATIC_5517), i547, i547, i548, i655, i655, i656, i655, i656) -> f5522_0_checkPrime_NE(EOS(STATIC_5522), i547, i547, i548, i655, i655, i656, i655 % i656) :|: TRUE 25.67/13.85 f5522_0_checkPrime_NE(EOS(STATIC_5522), i547, i547, i548, i655, i655, i656, i691) -> f5527_0_checkPrime_NE(EOS(STATIC_5527), i547, i547, i548, i655, i655, i656, i691) :|: TRUE 25.67/13.85 f5522_0_checkPrime_NE(EOS(STATIC_5522), i547, i547, i548, i655, i655, i656, matching1) -> f5528_0_checkPrime_NE(EOS(STATIC_5528), i547, i547, i548, i655, i655, i656, 0) :|: TRUE && matching1 = 0 25.67/13.85 f5527_0_checkPrime_NE(EOS(STATIC_5527), i547, i547, i548, i655, i655, i656, i691) -> f5533_0_checkPrime_Inc(EOS(STATIC_5533), i547, i547, i548, i655, i655, i656) :|: i691 > 0 25.67/13.85 f5533_0_checkPrime_Inc(EOS(STATIC_5533), i547, i547, i548, i655, i655, i656) -> f5538_0_checkPrime_JMP(EOS(STATIC_5538), i547, i547, i548, i655, i655, i656 + 1) :|: TRUE 25.67/13.85 f5538_0_checkPrime_JMP(EOS(STATIC_5538), i547, i547, i548, i655, i655, i693) -> f5544_0_checkPrime_Load(EOS(STATIC_5544), i547, i547, i548, i655, i655, i693) :|: TRUE 25.67/13.85 f5544_0_checkPrime_Load(EOS(STATIC_5544), i547, i547, i548, i655, i655, i693) -> f5491_0_checkPrime_Load(EOS(STATIC_5491), i547, i547, i548, i655, i655, i693) :|: TRUE 25.67/13.85 f5528_0_checkPrime_NE(EOS(STATIC_5528), i547, i547, i548, i655, i655, i656, matching1) -> f5534_0_checkPrime_ConstantStackPush(EOS(STATIC_5534), i547, i547, i548, i655) :|: TRUE && matching1 = 0 25.67/13.85 f5534_0_checkPrime_ConstantStackPush(EOS(STATIC_5534), i547, i547, i548, i655) -> f5539_0_checkPrime_Return(EOS(STATIC_5539), i547, i547, i548, i655, 0) :|: TRUE 25.67/13.85 f5539_0_checkPrime_Return(EOS(STATIC_5539), i547, i547, i548, i655, matching1) -> f5545_0_findKthPrime_Store(EOS(STATIC_5545), i547, i547, i548, i655, 0) :|: TRUE && matching1 = 0 25.67/13.85 f5545_0_findKthPrime_Store(EOS(STATIC_5545), i547, i547, i548, i655, matching1) -> f5549_0_findKthPrime_Load(EOS(STATIC_5549), i547, i547, i548, i655, 0) :|: TRUE && matching1 = 0 25.67/13.85 f5549_0_findKthPrime_Load(EOS(STATIC_5549), i547, i547, i548, i655, matching1) -> f5552_0_findKthPrime_EQ(EOS(STATIC_5552), i547, i547, i548, i655, 0) :|: TRUE && matching1 = 0 25.67/13.85 f5552_0_findKthPrime_EQ(EOS(STATIC_5552), i547, i547, i548, i655, matching1) -> f5556_0_findKthPrime_JMP(EOS(STATIC_5556), i547, i547, i548, i655) :|: TRUE && matching1 = 0 25.67/13.85 f5556_0_findKthPrime_JMP(EOS(STATIC_5556), i547, i547, i548, i655) -> f5560_0_findKthPrime_Load(EOS(STATIC_5560), i547, i547, i548, i655) :|: TRUE 25.67/13.85 f5560_0_findKthPrime_Load(EOS(STATIC_5560), i547, i547, i548, i655) -> f4850_0_findKthPrime_Load(EOS(STATIC_4850), i547, i547, i548, i655) :|: TRUE 25.67/13.85 Combined rules. Obtained 7 IRulesP rules: 25.67/13.85 f4854_0_findKthPrime_Load(EOS(STATIC_4854), i547:0, i547:0, i548:0, i549:0, i548:0) -> f4854_0_findKthPrime_Load(EOS(STATIC_4854), i547:0, i547:0, i548:0, i549:0 + 1, i548:0) :|: i548:0 < i547:0 && i549:0 < 1 25.67/13.85 f5498_0_checkPrime_GE(EOS(STATIC_5498), i547:0, i547:0, i548:0, i655:0, i655:0, i656:0, i656:0, i655:0) -> f5498_0_checkPrime_GE'(EOS(STATIC_5498), i547:0, i547:0, i548:0, i655:0, i655:0, i656:0, i656:0, i655:0) :|: i656:0 < i655:0 && i655:0 - i656:0 * div > 0 25.67/13.85 f5498_0_checkPrime_GE'(EOS(STATIC_5498), i547:0, i547:0, i548:0, i655:0, i655:0, i656:0, i656:0, i655:0) -> f5498_0_checkPrime_GE(EOS(STATIC_5498), i547:0, i547:0, i548:0, i655:0, i655:0, i656:0 + 1, i656:0 + 1, i655:0) :|: i656:0 < i655:0 && i655:0 - i656:0 * div > 0 && i656:0 > i655:0 - i656:0 * div && i655:0 - i656:0 * div + i656:0 > 0 25.67/13.85 f5498_0_checkPrime_GE(EOS(STATIC_5498), i547:0, i547:0, i548:0, i655:0, i655:0, i656:0, i656:0, i655:0) -> f4854_0_findKthPrime_Load(EOS(STATIC_4854), i547:0, i547:0, i548:0 + 1, i655:0, i548:0 + 1) :|: i656:0 >= i655:0 25.67/13.85 f5498_0_checkPrime_GE(EOS(STATIC_5498), i547:0, i547:0, i548:0, i655:0, i655:0, i656:0, i656:0, i655:0) -> f5498_0_checkPrime_GE'(EOS(STATIC_5498), i547:0, i547:0, i548:0, i655:0, i655:0, i656:0, i656:0, i655:0) :|: i656:0 < i655:0 && i655:0 - i656:0 * div = 0 25.67/13.85 f5498_0_checkPrime_GE'(EOS(STATIC_5498), i547:0, i547:0, i548:0, i655:0, i655:0, i656:0, i656:0, i655:0) -> f4854_0_findKthPrime_Load(EOS(STATIC_4854), i547:0, i547:0, i548:0, i655:0, i548:0) :|: i656:0 < i655:0 && i655:0 - i656:0 * div = 0 && i656:0 > i655:0 - i656:0 * div && i655:0 - i656:0 * div + i656:0 > 0 25.67/13.85 f4854_0_findKthPrime_Load(EOS(STATIC_4854), i547:0, i547:0, i548:0, i549:0, i548:0) -> f5498_0_checkPrime_GE(EOS(STATIC_5498), i547:0, i547:0, i548:0, i549:0 + 1, i549:0 + 1, 2, 2, i549:0 + 1) :|: i548:0 < i547:0 && i549:0 > 0 25.67/13.85 Filtered constant ground arguments: 25.67/13.85 f4854_0_findKthPrime_Load(x1, x2, x3, x4, x5, x6) -> f4854_0_findKthPrime_Load(x2, x3, x4, x5, x6) 25.67/13.85 f5498_0_checkPrime_GE(x1, x2, x3, x4, x5, x6, x7, x8, x9) -> f5498_0_checkPrime_GE(x2, x3, x4, x5, x6, x7, x8, x9) 25.67/13.85 f5498_0_checkPrime_GE'(x1, x2, x3, x4, x5, x6, x7, x8, x9) -> f5498_0_checkPrime_GE'(x2, x3, x4, x5, x6, x7, x8, x9) 25.67/13.85 Filtered duplicate arguments: 25.67/13.85 f4854_0_findKthPrime_Load(x1, x2, x3, x4, x5) -> f4854_0_findKthPrime_Load(x2, x4, x5) 25.67/13.85 f5498_0_checkPrime_GE(x1, x2, x3, x4, x5, x6, x7, x8) -> f5498_0_checkPrime_GE(x2, x3, x7, x8) 25.67/13.85 f5498_0_checkPrime_GE'(x1, x2, x3, x4, x5, x6, x7, x8) -> f5498_0_checkPrime_GE'(x2, x3, x7, x8) 25.67/13.85 Finished conversion. Obtained 7 rules.P rules: 25.67/13.85 f4854_0_findKthPrime_Load(i547:0, i549:0, i548:0) -> f4854_0_findKthPrime_Load(i547:0, i549:0 + 1, i548:0) :|: i548:0 < i547:0 && i549:0 < 1 25.67/13.85 f5498_0_checkPrime_GE(i547:0, i548:0, i656:0, i655:0) -> f5498_0_checkPrime_GE'(i547:0, i548:0, i656:0, i655:0) :|: i656:0 < i655:0 && i655:0 - i656:0 * div > 0 25.67/13.85 f5498_0_checkPrime_GE'(i547:0, i548:0, i656:0, i655:0) -> f5498_0_checkPrime_GE(i547:0, i548:0, i656:0 + 1, i655:0) :|: i655:0 - i656:0 * div > 0 && i656:0 < i655:0 && i655:0 - i656:0 * div + i656:0 > 0 && i656:0 > i655:0 - i656:0 * div 25.67/13.85 f5498_0_checkPrime_GE(i547:0, i548:0, i656:0, i655:0) -> f4854_0_findKthPrime_Load(i547:0, i655:0, i548:0 + 1) :|: i656:0 >= i655:0 25.67/13.85 f5498_0_checkPrime_GE(i547:0, i548:0, i656:0, i655:0) -> f5498_0_checkPrime_GE'(i547:0, i548:0, i656:0, i655:0) :|: i656:0 < i655:0 && i655:0 - i656:0 * div = 0 25.67/13.85 f5498_0_checkPrime_GE'(i547:0, i548:0, i656:0, i655:0) -> f4854_0_findKthPrime_Load(i547:0, i655:0, i548:0) :|: i655:0 - i656:0 * div = 0 && i656:0 < i655:0 && i655:0 - i656:0 * div + i656:0 > 0 && i656:0 > i655:0 - i656:0 * div 25.67/13.85 f4854_0_findKthPrime_Load(i547:0, i549:0, i548:0) -> f5498_0_checkPrime_GE(i547:0, i548:0, 2, i549:0 + 1) :|: i548:0 < i547:0 && i549:0 > 0 25.67/13.85 25.67/13.85 ---------------------------------------- 25.67/13.85 25.67/13.85 (9) 25.67/13.85 Obligation: 25.67/13.85 Rules: 25.67/13.85 f4854_0_findKthPrime_Load(i547:0, i549:0, i548:0) -> f4854_0_findKthPrime_Load(i547:0, i549:0 + 1, i548:0) :|: i548:0 < i547:0 && i549:0 < 1 25.67/13.85 f5498_0_checkPrime_GE(x, x1, x2, x3) -> f5498_0_checkPrime_GE'(x, x1, x2, x3) :|: x2 < x3 && x3 - x2 * x4 > 0 25.67/13.85 f5498_0_checkPrime_GE'(x5, x6, x7, x8) -> f5498_0_checkPrime_GE(x5, x6, x7 + 1, x8) :|: x8 - x7 * x9 > 0 && x7 < x8 && x8 - x7 * x9 + x7 > 0 && x7 > x8 - x7 * x9 25.67/13.85 f5498_0_checkPrime_GE(x10, x11, x12, x13) -> f4854_0_findKthPrime_Load(x10, x13, x11 + 1) :|: x12 >= x13 25.67/13.85 f5498_0_checkPrime_GE(x14, x15, x16, x17) -> f5498_0_checkPrime_GE'(x14, x15, x16, x17) :|: x16 < x17 && x17 - x16 * x18 = 0 25.67/13.85 f5498_0_checkPrime_GE'(x19, x20, x21, x22) -> f4854_0_findKthPrime_Load(x19, x22, x20) :|: x22 - x21 * x23 = 0 && x21 < x22 && x22 - x21 * x23 + x21 > 0 && x21 > x22 - x21 * x23 25.67/13.85 f4854_0_findKthPrime_Load(x24, x25, x26) -> f5498_0_checkPrime_GE(x24, x26, 2, x25 + 1) :|: x26 < x24 && x25 > 0 25.67/13.85 25.67/13.85 ---------------------------------------- 25.67/13.85 25.67/13.85 (10) IRSFormatTransformerProof (EQUIVALENT) 25.67/13.85 Reformatted IRS to match normalized format (transformed away non-linear left-hand sides, !=, / and %). 25.67/13.85 ---------------------------------------- 25.67/13.85 25.67/13.85 (11) 25.67/13.85 Obligation: 25.67/13.85 Rules: 25.67/13.85 f4854_0_findKthPrime_Load(i547:0, i549:0, i548:0) -> f4854_0_findKthPrime_Load(i547:0, arith, i548:0) :|: i548:0 < i547:0 && i549:0 < 1 && arith = i549:0 + 1 25.67/13.85 f5498_0_checkPrime_GE(x, x1, x2, x3) -> f5498_0_checkPrime_GE'(x, x1, x2, x3) :|: x2 < x3 && x3 - x2 * x4 > 0 25.67/13.85 f5498_0_checkPrime_GE'(x27, x28, x29, x30) -> f5498_0_checkPrime_GE(x27, x28, x31, x30) :|: x30 - x29 * x32 > 0 && x29 < x30 && x30 - x29 * x32 + x29 > 0 && x29 > x30 - x29 * x32 && x31 = x29 + 1 25.67/13.85 f5498_0_checkPrime_GE(x33, x34, x35, x36) -> f4854_0_findKthPrime_Load(x33, x36, x37) :|: x35 >= x36 && x37 = x34 + 1 25.67/13.85 f5498_0_checkPrime_GE(x14, x15, x16, x17) -> f5498_0_checkPrime_GE'(x14, x15, x16, x17) :|: x16 < x17 && x17 - x16 * x18 = 0 25.67/13.85 f5498_0_checkPrime_GE'(x19, x20, x21, x22) -> f4854_0_findKthPrime_Load(x19, x22, x20) :|: x22 - x21 * x23 = 0 && x21 < x22 && x22 - x21 * x23 + x21 > 0 && x21 > x22 - x21 * x23 25.67/13.85 f4854_0_findKthPrime_Load(x38, x39, x40) -> f5498_0_checkPrime_GE(x38, x40, 2, x41) :|: x40 < x38 && x39 > 0 && x41 = x39 + 1 25.67/13.85 25.67/13.85 ---------------------------------------- 25.67/13.85 25.67/13.85 (12) IntTRSCompressionProof (EQUIVALENT) 25.67/13.85 Compressed rules. 25.67/13.85 ---------------------------------------- 25.67/13.85 25.67/13.85 (13) 25.67/13.85 Obligation: 25.67/13.85 Rules: 25.67/13.85 f5498_0_checkPrime_GE(x14:0, x15:0, x16:0, x17:0) -> f5498_0_checkPrime_GE'(x14:0, x15:0, x16:0, x17:0) :|: x17:0 > x16:0 && x17:0 - x16:0 * x18:0 = 0 25.67/13.85 f5498_0_checkPrime_GE(x33:0, x34:0, x35:0, x36:0) -> f4854_0_findKthPrime_Load(x33:0, x36:0, x34:0 + 1) :|: x36:0 <= x35:0 25.67/13.85 f5498_0_checkPrime_GE'(x19:0, x20:0, x21:0, x22:0) -> f4854_0_findKthPrime_Load(x19:0, x22:0, x20:0) :|: x22:0 - x21:0 * x23:0 + x21:0 > 0 && x22:0 - x21:0 * x23:0 < x21:0 && x22:0 > x21:0 && x22:0 - x21:0 * x23:0 = 0 25.67/13.85 f4854_0_findKthPrime_Load(i547:0:0, i549:0:0, i548:0:0) -> f4854_0_findKthPrime_Load(i547:0:0, i549:0:0 + 1, i548:0:0) :|: i548:0:0 < i547:0:0 && i549:0:0 < 1 25.67/13.85 f5498_0_checkPrime_GE(x:0, x1:0, x2:0, x3:0) -> f5498_0_checkPrime_GE'(x:0, x1:0, x2:0, x3:0) :|: x3:0 > x2:0 && x3:0 - x2:0 * x4:0 > 0 25.67/13.85 f5498_0_checkPrime_GE'(x27:0, x28:0, x29:0, x30:0) -> f5498_0_checkPrime_GE(x27:0, x28:0, x29:0 + 1, x30:0) :|: x30:0 - x29:0 * x32:0 + x29:0 > 0 && x30:0 - x29:0 * x32:0 < x29:0 && x30:0 > x29:0 && x30:0 - x29:0 * x32:0 > 0 25.67/13.85 f4854_0_findKthPrime_Load(x38:0, x39:0, x40:0) -> f5498_0_checkPrime_GE(x38:0, x40:0, 2, x39:0 + 1) :|: x40:0 < x38:0 && x39:0 > 0 25.67/13.85 25.67/13.85 ---------------------------------------- 25.67/13.85 25.67/13.85 (14) TempFilterProof (SOUND) 25.67/13.85 Used the following sort dictionary for filtering: 25.67/13.85 f5498_0_checkPrime_GE(VARIABLE, VARIABLE, VARIABLE, INTEGER) 25.67/13.85 f5498_0_checkPrime_GE'(VARIABLE, VARIABLE, INTEGER, INTEGER) 25.67/13.85 f4854_0_findKthPrime_Load(VARIABLE, INTEGER, VARIABLE) 25.67/13.85 Replaced non-predefined constructor symbols by 0.The following proof was generated: 25.67/13.85 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 25.67/13.85 25.67/13.85 25.67/13.85 Termination of the given IntTRS could not be shown: 25.67/13.85 25.67/13.85 25.67/13.85 25.67/13.85 - IntTRS 25.67/13.85 - PolynomialOrderProcessor 25.67/13.85 25.67/13.85 Rules: 25.67/13.85 f5498_0_checkPrime_GE(x14:0, x15:0, x16:0, x17:0) -> f5498_0_checkPrime_GE'(x14:0, x15:0, x16:0, x17:0) :|: x17:0 > x16:0 && x17:0 - x16:0 * x18:0 = 0 25.67/13.85 f5498_0_checkPrime_GE(x33:0, x34:0, x35:0, x36:0) -> f4854_0_findKthPrime_Load(x33:0, x36:0, c) :|: c = x34:0 + 1 && x36:0 <= x35:0 25.67/13.85 f5498_0_checkPrime_GE'(x19:0, x20:0, x21:0, x22:0) -> f4854_0_findKthPrime_Load(x19:0, x22:0, x20:0) :|: x22:0 - x21:0 * x23:0 + x21:0 > 0 && x22:0 - x21:0 * x23:0 < x21:0 && x22:0 > x21:0 && x22:0 - x21:0 * x23:0 = 0 25.67/13.85 f4854_0_findKthPrime_Load(i547:0:0, i549:0:0, i548:0:0) -> f4854_0_findKthPrime_Load(i547:0:0, c1, i548:0:0) :|: c1 = i549:0:0 + 1 && (i548:0:0 < i547:0:0 && i549:0:0 < 1) 25.67/13.85 f5498_0_checkPrime_GE(x:0, x1:0, x2:0, x3:0) -> f5498_0_checkPrime_GE'(x:0, x1:0, x2:0, x3:0) :|: x3:0 > x2:0 && x3:0 - x2:0 * x4:0 > 0 25.67/13.85 f5498_0_checkPrime_GE'(x27:0, x28:0, x29:0, x30:0) -> f5498_0_checkPrime_GE(x27:0, x28:0, c2, x30:0) :|: c2 = x29:0 + 1 && (x30:0 - x29:0 * x32:0 + x29:0 > 0 && x30:0 - x29:0 * x32:0 < x29:0 && x30:0 > x29:0 && x30:0 - x29:0 * x32:0 > 0) 25.67/13.85 f4854_0_findKthPrime_Load(x38:0, x39:0, x40:0) -> f5498_0_checkPrime_GE(x38:0, x40:0, c3, c4) :|: c4 = x39:0 + 1 && c3 = 2 && (x40:0 < x38:0 && x39:0 > 0) 25.67/13.85 25.67/13.85 Found the following polynomial interpretation: 25.67/13.85 [f5498_0_checkPrime_GE(x, x1, x2, x3)] = -1 + x - x1 25.67/13.85 [f5498_0_checkPrime_GE'(x4, x5, x6, x7)] = -1 + x4 - x5 25.67/13.85 [f4854_0_findKthPrime_Load(x8, x9, x10)] = -1 - x10 + x8 25.67/13.85 25.67/13.85 The following rules are decreasing: 25.67/13.85 f5498_0_checkPrime_GE(x33:0, x34:0, x35:0, x36:0) -> f4854_0_findKthPrime_Load(x33:0, x36:0, c) :|: c = x34:0 + 1 && x36:0 <= x35:0 25.67/13.85 The following rules are bounded: 25.67/13.85 f4854_0_findKthPrime_Load(i547:0:0, i549:0:0, i548:0:0) -> f4854_0_findKthPrime_Load(i547:0:0, c1, i548:0:0) :|: c1 = i549:0:0 + 1 && (i548:0:0 < i547:0:0 && i549:0:0 < 1) 25.67/13.85 f4854_0_findKthPrime_Load(x38:0, x39:0, x40:0) -> f5498_0_checkPrime_GE(x38:0, x40:0, c3, c4) :|: c4 = x39:0 + 1 && c3 = 2 && (x40:0 < x38:0 && x39:0 > 0) 25.67/13.85 25.67/13.85 25.67/13.85 25.67/13.85 - IntTRS 25.67/13.85 - PolynomialOrderProcessor 25.67/13.85 - AND 25.67/13.85 - IntTRS 25.67/13.85 - IntTRS 25.67/13.85 - PolynomialOrderProcessor 25.67/13.85 - IntTRS 25.67/13.85 25.67/13.85 Rules: 25.67/13.85 f5498_0_checkPrime_GE(x14:0, x15:0, x16:0, x17:0) -> f5498_0_checkPrime_GE'(x14:0, x15:0, x16:0, x17:0) :|: x17:0 > x16:0 && x17:0 - x16:0 * x18:0 = 0 25.67/13.85 f5498_0_checkPrime_GE'(x19:0, x20:0, x21:0, x22:0) -> f4854_0_findKthPrime_Load(x19:0, x22:0, x20:0) :|: x22:0 - x21:0 * x23:0 + x21:0 > 0 && x22:0 - x21:0 * x23:0 < x21:0 && x22:0 > x21:0 && x22:0 - x21:0 * x23:0 = 0 25.67/13.85 f4854_0_findKthPrime_Load(i547:0:0, i549:0:0, i548:0:0) -> f4854_0_findKthPrime_Load(i547:0:0, c1, i548:0:0) :|: c1 = i549:0:0 + 1 && (i548:0:0 < i547:0:0 && i549:0:0 < 1) 25.67/13.85 f5498_0_checkPrime_GE(x:0, x1:0, x2:0, x3:0) -> f5498_0_checkPrime_GE'(x:0, x1:0, x2:0, x3:0) :|: x3:0 > x2:0 && x3:0 - x2:0 * x4:0 > 0 25.67/13.85 f5498_0_checkPrime_GE'(x27:0, x28:0, x29:0, x30:0) -> f5498_0_checkPrime_GE(x27:0, x28:0, c2, x30:0) :|: c2 = x29:0 + 1 && (x30:0 - x29:0 * x32:0 + x29:0 > 0 && x30:0 - x29:0 * x32:0 < x29:0 && x30:0 > x29:0 && x30:0 - x29:0 * x32:0 > 0) 25.67/13.85 f4854_0_findKthPrime_Load(x38:0, x39:0, x40:0) -> f5498_0_checkPrime_GE(x38:0, x40:0, c3, c4) :|: c4 = x39:0 + 1 && c3 = 2 && (x40:0 < x38:0 && x39:0 > 0) 25.67/13.85 25.67/13.85 Found the following polynomial interpretation: 25.67/13.85 [f5498_0_checkPrime_GE(x, x1, x2, x3)] = x - x1 - x3 25.67/13.85 [f5498_0_checkPrime_GE'(x4, x5, x6, x7)] = x4 - x5 - x7 25.67/13.85 [f4854_0_findKthPrime_Load(x8, x9, x10)] = -1 - x10 + x8 - x9 25.67/13.85 25.67/13.85 The following rules are decreasing: 25.67/13.85 f5498_0_checkPrime_GE'(x19:0, x20:0, x21:0, x22:0) -> f4854_0_findKthPrime_Load(x19:0, x22:0, x20:0) :|: x22:0 - x21:0 * x23:0 + x21:0 > 0 && x22:0 - x21:0 * x23:0 < x21:0 && x22:0 > x21:0 && x22:0 - x21:0 * x23:0 = 0 25.67/13.85 f4854_0_findKthPrime_Load(i547:0:0, i549:0:0, i548:0:0) -> f4854_0_findKthPrime_Load(i547:0:0, c1, i548:0:0) :|: c1 = i549:0:0 + 1 && (i548:0:0 < i547:0:0 && i549:0:0 < 1) 25.67/13.85 The following rules are bounded: 25.67/13.85 f4854_0_findKthPrime_Load(i547:0:0, i549:0:0, i548:0:0) -> f4854_0_findKthPrime_Load(i547:0:0, c1, i548:0:0) :|: c1 = i549:0:0 + 1 && (i548:0:0 < i547:0:0 && i549:0:0 < 1) 25.67/13.85 25.67/13.85 25.67/13.85 - IntTRS 25.67/13.85 - PolynomialOrderProcessor 25.67/13.85 - AND 25.67/13.85 - IntTRS 25.67/13.85 - IntTRS 25.67/13.85 - PolynomialOrderProcessor 25.67/13.85 - IntTRS 25.67/13.85 - IntTRS 25.67/13.85 25.67/13.85 Rules: 25.67/13.85 f5498_0_checkPrime_GE(x14:0, x15:0, x16:0, x17:0) -> f5498_0_checkPrime_GE'(x14:0, x15:0, x16:0, x17:0) :|: x17:0 > x16:0 && x17:0 - x16:0 * x18:0 = 0 25.67/13.85 f5498_0_checkPrime_GE'(x19:0, x20:0, x21:0, x22:0) -> f4854_0_findKthPrime_Load(x19:0, x22:0, x20:0) :|: x22:0 - x21:0 * x23:0 + x21:0 > 0 && x22:0 - x21:0 * x23:0 < x21:0 && x22:0 > x21:0 && x22:0 - x21:0 * x23:0 = 0 25.67/13.85 f5498_0_checkPrime_GE(x:0, x1:0, x2:0, x3:0) -> f5498_0_checkPrime_GE'(x:0, x1:0, x2:0, x3:0) :|: x3:0 > x2:0 && x3:0 - x2:0 * x4:0 > 0 25.67/13.85 f5498_0_checkPrime_GE'(x27:0, x28:0, x29:0, x30:0) -> f5498_0_checkPrime_GE(x27:0, x28:0, c2, x30:0) :|: c2 = x29:0 + 1 && (x30:0 - x29:0 * x32:0 + x29:0 > 0 && x30:0 - x29:0 * x32:0 < x29:0 && x30:0 > x29:0 && x30:0 - x29:0 * x32:0 > 0) 25.67/13.85 f4854_0_findKthPrime_Load(x38:0, x39:0, x40:0) -> f5498_0_checkPrime_GE(x38:0, x40:0, c3, c4) :|: c4 = x39:0 + 1 && c3 = 2 && (x40:0 < x38:0 && x39:0 > 0) 25.67/13.85 25.67/13.85 25.67/13.85 25.67/13.85 - IntTRS 25.67/13.85 - PolynomialOrderProcessor 25.67/13.85 - AND 25.67/13.85 - IntTRS 25.67/13.85 - IntTRS 25.67/13.85 - IntTRS 25.67/13.85 - RankingReductionPairProof 25.67/13.85 25.67/13.85 Rules: 25.67/13.85 f5498_0_checkPrime_GE(x14:0, x15:0, x16:0, x17:0) -> f5498_0_checkPrime_GE'(x14:0, x15:0, x16:0, x17:0) :|: x17:0 > x16:0 && x17:0 - x16:0 * x18:0 = 0 25.67/13.85 f5498_0_checkPrime_GE(x33:0, x34:0, x35:0, x36:0) -> f4854_0_findKthPrime_Load(x33:0, x36:0, c) :|: c = x34:0 + 1 && x36:0 <= x35:0 25.67/13.85 f5498_0_checkPrime_GE'(x19:0, x20:0, x21:0, x22:0) -> f4854_0_findKthPrime_Load(x19:0, x22:0, x20:0) :|: x22:0 - x21:0 * x23:0 + x21:0 > 0 && x22:0 - x21:0 * x23:0 < x21:0 && x22:0 > x21:0 && x22:0 - x21:0 * x23:0 = 0 25.67/13.85 f5498_0_checkPrime_GE(x:0, x1:0, x2:0, x3:0) -> f5498_0_checkPrime_GE'(x:0, x1:0, x2:0, x3:0) :|: x3:0 > x2:0 && x3:0 - x2:0 * x4:0 > 0 25.67/13.85 f5498_0_checkPrime_GE'(x27:0, x28:0, x29:0, x30:0) -> f5498_0_checkPrime_GE(x27:0, x28:0, c2, x30:0) :|: c2 = x29:0 + 1 && (x30:0 - x29:0 * x32:0 + x29:0 > 0 && x30:0 - x29:0 * x32:0 < x29:0 && x30:0 > x29:0 && x30:0 - x29:0 * x32:0 > 0) 25.67/13.85 25.67/13.85 Interpretation: 25.67/13.85 [ f5498_0_checkPrime_GE ] = 1 25.67/13.85 [ f5498_0_checkPrime_GE' ] = 1 25.67/13.85 [ f4854_0_findKthPrime_Load ] = 0 25.67/13.85 25.67/13.85 The following rules are decreasing: 25.67/13.85 f5498_0_checkPrime_GE(x33:0, x34:0, x35:0, x36:0) -> f4854_0_findKthPrime_Load(x33:0, x36:0, c) :|: c = x34:0 + 1 && x36:0 <= x35:0 25.67/13.85 f5498_0_checkPrime_GE'(x19:0, x20:0, x21:0, x22:0) -> f4854_0_findKthPrime_Load(x19:0, x22:0, x20:0) :|: x22:0 - x21:0 * x23:0 + x21:0 > 0 && x22:0 - x21:0 * x23:0 < x21:0 && x22:0 > x21:0 && x22:0 - x21:0 * x23:0 = 0 25.67/13.85 25.67/13.85 The following rules are bounded: 25.67/13.85 f5498_0_checkPrime_GE(x14:0, x15:0, x16:0, x17:0) -> f5498_0_checkPrime_GE'(x14:0, x15:0, x16:0, x17:0) :|: x17:0 > x16:0 && x17:0 - x16:0 * x18:0 = 0 25.67/13.85 f5498_0_checkPrime_GE(x33:0, x34:0, x35:0, x36:0) -> f4854_0_findKthPrime_Load(x33:0, x36:0, c) :|: c = x34:0 + 1 && x36:0 <= x35:0 25.67/13.85 f5498_0_checkPrime_GE'(x19:0, x20:0, x21:0, x22:0) -> f4854_0_findKthPrime_Load(x19:0, x22:0, x20:0) :|: x22:0 - x21:0 * x23:0 + x21:0 > 0 && x22:0 - x21:0 * x23:0 < x21:0 && x22:0 > x21:0 && x22:0 - x21:0 * x23:0 = 0 25.67/13.85 f5498_0_checkPrime_GE(x:0, x1:0, x2:0, x3:0) -> f5498_0_checkPrime_GE'(x:0, x1:0, x2:0, x3:0) :|: x3:0 > x2:0 && x3:0 - x2:0 * x4:0 > 0 25.67/13.85 f5498_0_checkPrime_GE'(x27:0, x28:0, x29:0, x30:0) -> f5498_0_checkPrime_GE(x27:0, x28:0, c2, x30:0) :|: c2 = x29:0 + 1 && (x30:0 - x29:0 * x32:0 + x29:0 > 0 && x30:0 - x29:0 * x32:0 < x29:0 && x30:0 > x29:0 && x30:0 - x29:0 * x32:0 > 0) 25.67/13.85 25.67/13.85 25.67/13.85 25.67/13.85 - IntTRS 25.67/13.85 - PolynomialOrderProcessor 25.67/13.85 - AND 25.67/13.85 - IntTRS 25.67/13.85 - IntTRS 25.67/13.85 - IntTRS 25.67/13.85 - RankingReductionPairProof 25.67/13.85 - IntTRS 25.67/13.85 - PolynomialOrderProcessor 25.67/13.85 25.67/13.85 Rules: 25.67/13.85 f5498_0_checkPrime_GE(x14:0, x15:0, x16:0, x17:0) -> f5498_0_checkPrime_GE'(x14:0, x15:0, x16:0, x17:0) :|: x17:0 > x16:0 && x17:0 - x16:0 * x18:0 = 0 25.67/13.85 f5498_0_checkPrime_GE(x:0, x1:0, x2:0, x3:0) -> f5498_0_checkPrime_GE'(x:0, x1:0, x2:0, x3:0) :|: x3:0 > x2:0 && x3:0 - x2:0 * x4:0 > 0 25.67/13.85 f5498_0_checkPrime_GE'(x27:0, x28:0, x29:0, x30:0) -> f5498_0_checkPrime_GE(x27:0, x28:0, c2, x30:0) :|: c2 = x29:0 + 1 && (x30:0 - x29:0 * x32:0 + x29:0 > 0 && x30:0 - x29:0 * x32:0 < x29:0 && x30:0 > x29:0 && x30:0 - x29:0 * x32:0 > 0) 25.67/13.85 25.67/13.85 Found the following polynomial interpretation: 25.67/13.85 [f5498_0_checkPrime_GE(x, x1, x2, x3)] = 1 - x2 + x3 25.67/13.85 [f5498_0_checkPrime_GE'(x4, x5, x6, x7)] = -x6 + x7 25.67/13.85 25.67/13.85 The following rules are decreasing: 25.67/13.85 f5498_0_checkPrime_GE(x14:0, x15:0, x16:0, x17:0) -> f5498_0_checkPrime_GE'(x14:0, x15:0, x16:0, x17:0) :|: x17:0 > x16:0 && x17:0 - x16:0 * x18:0 = 0 25.67/13.85 f5498_0_checkPrime_GE(x:0, x1:0, x2:0, x3:0) -> f5498_0_checkPrime_GE'(x:0, x1:0, x2:0, x3:0) :|: x3:0 > x2:0 && x3:0 - x2:0 * x4:0 > 0 25.67/13.85 The following rules are bounded: 25.67/13.85 f5498_0_checkPrime_GE(x14:0, x15:0, x16:0, x17:0) -> f5498_0_checkPrime_GE'(x14:0, x15:0, x16:0, x17:0) :|: x17:0 > x16:0 && x17:0 - x16:0 * x18:0 = 0 25.67/13.85 f5498_0_checkPrime_GE(x:0, x1:0, x2:0, x3:0) -> f5498_0_checkPrime_GE'(x:0, x1:0, x2:0, x3:0) :|: x3:0 > x2:0 && x3:0 - x2:0 * x4:0 > 0 25.67/13.85 f5498_0_checkPrime_GE'(x27:0, x28:0, x29:0, x30:0) -> f5498_0_checkPrime_GE(x27:0, x28:0, c2, x30:0) :|: c2 = x29:0 + 1 && (x30:0 - x29:0 * x32:0 + x29:0 > 0 && x30:0 - x29:0 * x32:0 < x29:0 && x30:0 > x29:0 && x30:0 - x29:0 * x32:0 > 0) 25.67/13.85 25.67/13.85 25.67/13.85 - IntTRS 25.67/13.85 - PolynomialOrderProcessor 25.67/13.85 - AND 25.67/13.85 - IntTRS 25.67/13.85 - IntTRS 25.67/13.85 - IntTRS 25.67/13.85 - RankingReductionPairProof 25.67/13.85 - IntTRS 25.67/13.85 - PolynomialOrderProcessor 25.67/13.85 - IntTRS 25.67/13.85 - PolynomialOrderProcessor 25.67/13.85 25.67/13.85 Rules: 25.67/13.85 f5498_0_checkPrime_GE'(x27:0, x28:0, x29:0, x30:0) -> f5498_0_checkPrime_GE(x27:0, x28:0, c2, x30:0) :|: c2 = x29:0 + 1 && (x30:0 - x29:0 * x32:0 + x29:0 > 0 && x30:0 - x29:0 * x32:0 < x29:0 && x30:0 > x29:0 && x30:0 - x29:0 * x32:0 > 0) 25.67/13.85 25.67/13.85 Found the following polynomial interpretation: 25.67/13.85 [f5498_0_checkPrime_GE'(x, x1, x2, x3)] = 0 25.67/13.85 [f5498_0_checkPrime_GE(x4, x5, x6, x7)] = -1 25.67/13.85 25.67/13.85 The following rules are decreasing: 25.67/13.85 f5498_0_checkPrime_GE'(x27:0, x28:0, x29:0, x30:0) -> f5498_0_checkPrime_GE(x27:0, x28:0, c2, x30:0) :|: c2 = x29:0 + 1 && (x30:0 - x29:0 * x32:0 + x29:0 > 0 && x30:0 - x29:0 * x32:0 < x29:0 && x30:0 > x29:0 && x30:0 - x29:0 * x32:0 > 0) 25.67/13.85 The following rules are bounded: 25.67/13.85 f5498_0_checkPrime_GE'(x27:0, x28:0, x29:0, x30:0) -> f5498_0_checkPrime_GE(x27:0, x28:0, c2, x30:0) :|: c2 = x29:0 + 1 && (x30:0 - x29:0 * x32:0 + x29:0 > 0 && x30:0 - x29:0 * x32:0 < x29:0 && x30:0 > x29:0 && x30:0 - x29:0 * x32:0 > 0) 25.67/13.85 25.67/13.85 25.67/13.85 25.67/13.85 ---------------------------------------- 25.67/13.85 25.67/13.85 (15) 25.67/13.85 Obligation: 25.67/13.85 Rules: 25.67/13.85 f5498_0_checkPrime_GE(x14:0, x15:0, x16:0, x17:0) -> f5498_0_checkPrime_GE'(x14:0, x15:0, x16:0, x17:0) :|: x17:0 > x16:0 && x17:0 - x16:0 * x18:0 = 0 25.67/13.85 f5498_0_checkPrime_GE'(x19:0, x20:0, x21:0, x22:0) -> f4854_0_findKthPrime_Load(x19:0, x22:0, x20:0) :|: x22:0 - x21:0 * x23:0 + x21:0 > 0 && x22:0 - x21:0 * x23:0 < x21:0 && x22:0 > x21:0 && x22:0 - x21:0 * x23:0 = 0 25.67/13.85 f5498_0_checkPrime_GE(x:0, x1:0, x2:0, x3:0) -> f5498_0_checkPrime_GE'(x:0, x1:0, x2:0, x3:0) :|: x3:0 > x2:0 && x3:0 - x2:0 * x4:0 > 0 25.67/13.85 f5498_0_checkPrime_GE'(x27:0, x28:0, x29:0, x30:0) -> f5498_0_checkPrime_GE(x27:0, x28:0, x29:0 + 1, x30:0) :|: x30:0 - x29:0 * x32:0 + x29:0 > 0 && x30:0 - x29:0 * x32:0 < x29:0 && x30:0 > x29:0 && x30:0 - x29:0 * x32:0 > 0 25.67/13.85 f4854_0_findKthPrime_Load(x38:0, x39:0, x40:0) -> f5498_0_checkPrime_GE(x38:0, x40:0, 2, x39:0 + 1) :|: x40:0 < x38:0 && x39:0 > 0 25.67/13.85 25.67/13.85 ---------------------------------------- 25.67/13.85 25.67/13.85 (16) IntTRSCompressionProof (EQUIVALENT) 25.67/13.85 Compressed rules. 25.67/13.85 ---------------------------------------- 25.67/13.85 25.67/13.85 (17) 25.67/13.85 Obligation: 25.67/13.85 Rules: 25.67/13.85 f5498_0_checkPrime_GE(x:0:0, x1:0:0, x2:0:0, x3:0:0) -> f5498_0_checkPrime_GE'(x:0:0, x1:0:0, x2:0:0, x3:0:0) :|: x3:0:0 > x2:0:0 && x3:0:0 - x2:0:0 * x4:0:0 > 0 25.67/13.85 f5498_0_checkPrime_GE(x14:0:0, x15:0:0, x16:0:0, x17:0:0) -> f5498_0_checkPrime_GE'(x14:0:0, x15:0:0, x16:0:0, x17:0:0) :|: x17:0:0 > x16:0:0 && x17:0:0 - x16:0:0 * x18:0:0 = 0 25.67/13.85 f5498_0_checkPrime_GE'(x27:0:0, x28:0:0, x29:0:0, x30:0:0) -> f5498_0_checkPrime_GE(x27:0:0, x28:0:0, x29:0:0 + 1, x30:0:0) :|: x30:0:0 > x29:0:0 && x30:0:0 - x29:0:0 * x32:0:0 > 0 && x30:0:0 - x29:0:0 * x32:0:0 < x29:0:0 && x30:0:0 - x29:0:0 * x32:0:0 + x29:0:0 > 0 25.67/13.85 f5498_0_checkPrime_GE'(x19:0:0, x20:0:0, x21:0:0, x22:0:0) -> f5498_0_checkPrime_GE(x19:0:0, x20:0:0, 2, x22:0:0 + 1) :|: x20:0:0 < x19:0:0 && x22:0:0 - x21:0:0 * x23:0:0 = 0 && x22:0:0 > 0 && x22:0:0 > x21:0:0 && x22:0:0 - x21:0:0 * x23:0:0 < x21:0:0 && x22:0:0 - x21:0:0 * x23:0:0 + x21:0:0 > 0 25.67/13.85 25.67/13.85 ---------------------------------------- 25.67/13.85 25.67/13.85 (18) 25.67/13.85 Obligation: 25.67/13.85 SCC of termination graph based on JBC Program. 25.67/13.85 SCC contains nodes from the following methods: RandomHard.getNext()I 25.67/13.85 SCC calls the following helper methods: 25.67/13.85 Performed SCC analyses: 25.67/13.85 *Used field analysis yielded the following read fields: 25.67/13.85 25.67/13.85 *Marker field analysis yielded the following relations that could be markers: 25.67/13.85 25.67/13.85 ---------------------------------------- 25.67/13.85 25.67/13.85 (19) SCCToIRSProof (SOUND) 25.67/13.85 Transformed FIGraph SCCs to intTRSs. Log: 25.67/13.85 Generated rules. Obtained 13 IRulesP rules: 25.67/13.85 f5559_0_getPowerOfKInSource_Load(EOS(STATIC_5559), i706, i707, i707) -> f5562_0_getPowerOfKInSource_IntArithmetic(EOS(STATIC_5562), i706, i707, i707, i706) :|: TRUE 25.67/13.85 f5562_0_getPowerOfKInSource_IntArithmetic(EOS(STATIC_5562), i723, i707, i707, i723) -> f5565_0_getPowerOfKInSource_IntArithmetic(EOS(STATIC_5565), i723, i707, i707, i723) :|: TRUE 25.67/13.85 f5565_0_getPowerOfKInSource_IntArithmetic(EOS(STATIC_5565), i723, i707, i707, i723) -> f5568_0_getPowerOfKInSource_NE(EOS(STATIC_5568), i723, i707, i707 % i723) :|: TRUE 25.67/13.85 f5568_0_getPowerOfKInSource_NE(EOS(STATIC_5568), i723, i707, matching1) -> f5571_0_getPowerOfKInSource_NE(EOS(STATIC_5571), i723, i707, 0) :|: TRUE && matching1 = 0 25.67/13.85 f5571_0_getPowerOfKInSource_NE(EOS(STATIC_5571), i723, i707, matching1) -> f5574_0_getPowerOfKInSource_Load(EOS(STATIC_5574), i723, i707) :|: TRUE && matching1 = 0 25.67/13.85 f5574_0_getPowerOfKInSource_Load(EOS(STATIC_5574), i723, i707) -> f5577_0_getPowerOfKInSource_Load(EOS(STATIC_5577), i723, i707) :|: TRUE 25.67/13.85 f5577_0_getPowerOfKInSource_Load(EOS(STATIC_5577), i723, i707) -> f5579_0_getPowerOfKInSource_IntArithmetic(EOS(STATIC_5579), i723, i707, i723) :|: TRUE 25.67/13.85 f5579_0_getPowerOfKInSource_IntArithmetic(EOS(STATIC_5579), i723, i707, i723) -> f5582_0_getPowerOfKInSource_Store(EOS(STATIC_5582), i723, i731) :|: i731 = i707 / i723 25.67/13.85 f5582_0_getPowerOfKInSource_Store(EOS(STATIC_5582), i723, i731) -> f5585_0_getPowerOfKInSource_Inc(EOS(STATIC_5585), i723, i731) :|: TRUE 25.67/13.85 f5585_0_getPowerOfKInSource_Inc(EOS(STATIC_5585), i723, i731) -> f5587_0_getPowerOfKInSource_JMP(EOS(STATIC_5587), i723, i731) :|: TRUE 25.67/13.85 f5587_0_getPowerOfKInSource_JMP(EOS(STATIC_5587), i723, i731) -> f5589_0_getPowerOfKInSource_Load(EOS(STATIC_5589), i723, i731) :|: TRUE 25.67/13.85 f5589_0_getPowerOfKInSource_Load(EOS(STATIC_5589), i723, i731) -> f5555_0_getPowerOfKInSource_Load(EOS(STATIC_5555), i723, i731) :|: TRUE 25.67/13.85 f5555_0_getPowerOfKInSource_Load(EOS(STATIC_5555), i706, i707) -> f5559_0_getPowerOfKInSource_Load(EOS(STATIC_5559), i706, i707, i707) :|: TRUE 25.67/13.85 Combined rules. Obtained 2 IRulesP rules: 25.67/13.85 f5559_0_getPowerOfKInSource_Load(EOS(STATIC_5559), i706:0, i707:0, i707:0) -> f5559_0_getPowerOfKInSource_Load'(EOS(STATIC_5559), i706:0, i707:0, i707:0) :|: i707:0 - i706:0 * div = 0 25.67/13.85 f5559_0_getPowerOfKInSource_Load'(EOS(STATIC_5559), i706:0, i707:0, i707:0) -> f5559_0_getPowerOfKInSource_Load(EOS(STATIC_5559), i706:0, div1, div1) :|: i707:0 - i706:0 * div = 0 && i707:0 - i706:0 * div + i706:0 > 0 && i707:0 - i706:0 * div < i706:0 && i707:0 - i706:0 * div1 < i706:0 && i707:0 - i706:0 * div1 + i706:0 > 0 25.67/13.85 Filtered constant ground arguments: 25.67/13.85 f5559_0_getPowerOfKInSource_Load(x1, x2, x3, x4) -> f5559_0_getPowerOfKInSource_Load(x2, x3, x4) 25.67/13.85 f5559_0_getPowerOfKInSource_Load'(x1, x2, x3, x4) -> f5559_0_getPowerOfKInSource_Load'(x2, x3, x4) 25.67/13.85 EOS(x1) -> EOS 25.67/13.85 Filtered duplicate arguments: 25.67/13.85 f5559_0_getPowerOfKInSource_Load(x1, x2, x3) -> f5559_0_getPowerOfKInSource_Load(x1, x3) 25.67/13.85 f5559_0_getPowerOfKInSource_Load'(x1, x2, x3) -> f5559_0_getPowerOfKInSource_Load'(x1, x3) 25.67/13.85 Finished conversion. Obtained 2 rules.P rules: 25.67/13.85 f5559_0_getPowerOfKInSource_Load(i706:0, i707:0) -> f5559_0_getPowerOfKInSource_Load'(i706:0, i707:0) :|: i707:0 - i706:0 * div = 0 25.67/13.85 f5559_0_getPowerOfKInSource_Load'(i706:0, i707:0) -> f5559_0_getPowerOfKInSource_Load(i706:0, div1) :|: i707:0 - i706:0 * div + i706:0 > 0 && i707:0 - i706:0 * div = 0 && i707:0 - i706:0 * div < i706:0 && i707:0 - i706:0 * div1 + i706:0 > 0 && i707:0 - i706:0 * div1 < i706:0 25.67/13.85 25.67/13.85 ---------------------------------------- 25.67/13.85 25.67/13.85 (20) 25.67/13.85 Obligation: 25.67/13.85 Rules: 25.67/13.85 f5559_0_getPowerOfKInSource_Load(x, x1) -> f5559_0_getPowerOfKInSource_Load'(x, x1) :|: x1 - x * x2 = 0 25.67/13.85 f5559_0_getPowerOfKInSource_Load'(x3, x4) -> f5559_0_getPowerOfKInSource_Load(x3, x5) :|: x4 - x3 * x6 + x3 > 0 && x4 - x3 * x6 = 0 && x4 - x3 * x6 < x3 && x4 - x3 * x5 + x3 > 0 && x4 - x3 * x5 < x3 25.67/13.85 25.67/13.85 ---------------------------------------- 25.67/13.85 25.67/13.85 (21) IRSFormatTransformerProof (EQUIVALENT) 25.67/13.85 Reformatted IRS to match normalized format (transformed away non-linear left-hand sides, !=, / and %). 25.67/13.85 ---------------------------------------- 25.67/13.85 25.67/13.85 (22) 25.67/13.85 Obligation: 25.67/13.85 Rules: 25.67/13.85 f5559_0_getPowerOfKInSource_Load(x, x1) -> f5559_0_getPowerOfKInSource_Load'(x, x1) :|: x1 - x * x2 = 0 25.67/13.85 f5559_0_getPowerOfKInSource_Load'(x3, x4) -> f5559_0_getPowerOfKInSource_Load(x3, x5) :|: x4 - x3 * x6 + x3 > 0 && x4 - x3 * x6 = 0 && x4 - x3 * x6 < x3 && x4 - x3 * x5 + x3 > 0 && x4 - x3 * x5 < x3 25.67/13.85 25.67/13.85 ---------------------------------------- 25.67/13.85 25.67/13.85 (23) IRSwTTerminationDigraphProof (EQUIVALENT) 25.67/13.85 Constructed termination digraph! 25.67/13.85 Nodes: 25.67/13.85 (1) f5559_0_getPowerOfKInSource_Load(x, x1) -> f5559_0_getPowerOfKInSource_Load'(x, x1) :|: x1 - x * x2 = 0 25.67/13.85 (2) f5559_0_getPowerOfKInSource_Load'(x3, x4) -> f5559_0_getPowerOfKInSource_Load(x3, x5) :|: x4 - x3 * x6 + x3 > 0 && x4 - x3 * x6 = 0 && x4 - x3 * x6 < x3 && x4 - x3 * x5 + x3 > 0 && x4 - x3 * x5 < x3 25.67/13.85 25.67/13.85 Arcs: 25.67/13.85 (1) -> (2) 25.67/13.85 (2) -> (1) 25.67/13.85 25.67/13.85 This digraph is fully evaluated! 25.67/13.85 ---------------------------------------- 25.67/13.85 25.67/13.85 (24) 25.67/13.85 Obligation: 25.67/13.85 25.67/13.85 Termination digraph: 25.67/13.85 Nodes: 25.67/13.85 (1) f5559_0_getPowerOfKInSource_Load(x, x1) -> f5559_0_getPowerOfKInSource_Load'(x, x1) :|: x1 - x * x2 = 0 25.67/13.85 (2) f5559_0_getPowerOfKInSource_Load'(x3, x4) -> f5559_0_getPowerOfKInSource_Load(x3, x5) :|: x4 - x3 * x6 + x3 > 0 && x4 - x3 * x6 = 0 && x4 - x3 * x6 < x3 && x4 - x3 * x5 + x3 > 0 && x4 - x3 * x5 < x3 25.67/13.85 25.67/13.85 Arcs: 25.67/13.85 (1) -> (2) 25.67/13.85 (2) -> (1) 25.67/13.85 25.67/13.85 This digraph is fully evaluated! 25.67/13.85 25.67/13.85 ---------------------------------------- 25.67/13.85 25.67/13.85 (25) IntTRSCompressionProof (EQUIVALENT) 25.67/13.85 Compressed rules. 25.67/13.85 ---------------------------------------- 25.67/13.85 25.67/13.85 (26) 25.67/13.85 Obligation: 25.67/13.85 Rules: 25.67/13.85 f5559_0_getPowerOfKInSource_Load(x:0, x1:0) -> f5559_0_getPowerOfKInSource_Load(x:0, x5:0) :|: x:0 > x1:0 - x:0 * x5:0 && x1:0 - x:0 * x2:0 = 0 && x1:0 - x:0 * x5:0 + x:0 > 0 && x:0 > x1:0 - x:0 * x6:0 && x1:0 - x:0 * x6:0 = 0 && x1:0 - x:0 * x6:0 + x:0 > 0 25.67/13.85 25.67/13.85 ---------------------------------------- 25.67/13.85 25.67/13.85 (27) FilterProof (EQUIVALENT) 25.67/13.85 Used the following sort dictionary for filtering: 25.67/13.85 f5559_0_getPowerOfKInSource_Load(INTEGER, INTEGER) 25.67/13.85 Replaced non-predefined constructor symbols by 0. 25.67/13.85 ---------------------------------------- 25.67/13.85 25.67/13.85 (28) 25.67/13.85 Obligation: 25.67/13.85 Rules: 25.67/13.85 f5559_0_getPowerOfKInSource_Load(x:0, x1:0) -> f5559_0_getPowerOfKInSource_Load(x:0, x5:0) :|: x:0 > x1:0 - x:0 * x5:0 && x1:0 - x:0 * x2:0 = 0 && x1:0 - x:0 * x5:0 + x:0 > 0 && x:0 > x1:0 - x:0 * x6:0 && x1:0 - x:0 * x6:0 = 0 && x1:0 - x:0 * x6:0 + x:0 > 0 25.67/13.85 25.67/13.85 ---------------------------------------- 25.67/13.85 25.67/13.85 (29) IntTRSCompressionProof (EQUIVALENT) 25.67/13.85 Compressed rules. 25.67/13.85 ---------------------------------------- 25.67/13.85 25.67/13.85 (30) 25.67/13.85 Obligation: 25.67/13.85 Rules: 25.67/13.85 f5559_0_getPowerOfKInSource_Load(x:0:0, x1:0:0) -> f5559_0_getPowerOfKInSource_Load(x:0:0, x5:0:0) :|: x1:0:0 - x:0:0 * x6:0:0 = 0 && x1:0:0 - x:0:0 * x6:0:0 + x:0:0 > 0 && x:0:0 > x1:0:0 - x:0:0 * x6:0:0 && x1:0:0 - x:0:0 * x5:0:0 + x:0:0 > 0 && x1:0:0 - x:0:0 * x2:0:0 = 0 && x:0:0 > x1:0:0 - x:0:0 * x5:0:0 25.67/13.85 25.67/13.85 ---------------------------------------- 25.67/13.85 25.67/13.85 (31) IntTRSPeriodicNontermProof (COMPLETE) 25.67/13.85 Normalized system to the following form: 25.67/13.85 f(pc, x:0:0, x1:0:0) -> f(1, x:0:0, x5:0:0) :|: pc = 1 && (x1:0:0 - x:0:0 * x6:0:0 = 0 && x1:0:0 - x:0:0 * x6:0:0 + x:0:0 > 0 && x:0:0 > x1:0:0 - x:0:0 * x6:0:0 && x1:0:0 - x:0:0 * x5:0:0 + x:0:0 > 0 && x1:0:0 - x:0:0 * x2:0:0 = 0 && x:0:0 > x1:0:0 - x:0:0 * x5:0:0) 25.67/13.85 Witness term starting non-terminating reduction: f(1, 4, 0) 25.67/13.85 ---------------------------------------- 25.67/13.85 25.67/13.85 (32) 25.67/13.85 NO 25.67/13.85 25.67/13.85 ---------------------------------------- 25.67/13.85 25.67/13.85 (33) 25.67/13.85 Obligation: 25.67/13.85 SCC of termination graph based on JBC Program. 25.67/13.85 SCC contains nodes from the following methods: RandomHard.main([Ljava/lang/String;)V 25.67/13.85 SCC calls the following helper methods: RandomHard.getNext()I, RandomHard.findKthPrime(I)I 25.67/13.85 Performed SCC analyses: 25.67/13.85 *Used field analysis yielded the following read fields: 25.67/13.85 25.67/13.85 *Marker field analysis yielded the following relations that could be markers: 25.67/13.85 25.67/13.85 ---------------------------------------- 25.67/13.85 25.67/13.85 (34) SCCToIRSProof (SOUND) 25.67/13.85 Transformed FIGraph SCCs to intTRSs. Log: 25.67/13.85 Generated rules. Obtained 15 IRulesP rules: 25.67/13.85 f3642_0_main_Load(EOS(STATIC_3642), java.lang.Object(RandomHard(EOC)), i382, i383, i383) -> f3648_0_main_GE(EOS(STATIC_3648), java.lang.Object(RandomHard(EOC)), i382, i383, i383, i382) :|: TRUE 25.67/13.85 f3648_0_main_GE(EOS(STATIC_3648), java.lang.Object(RandomHard(EOC)), i382, i383, i383, i382) -> f3656_0_main_GE(EOS(STATIC_3656), java.lang.Object(RandomHard(EOC)), i382, i383, i383, i382) :|: i383 < i382 25.67/13.85 f3656_0_main_GE(EOS(STATIC_3656), java.lang.Object(RandomHard(EOC)), i382, i383, i383, i382) -> f3668_0_main_Load(EOS(STATIC_3668), java.lang.Object(RandomHard(EOC)), i382, i383) :|: i383 < i382 25.67/13.85 f3668_0_main_Load(EOS(STATIC_3668), java.lang.Object(RandomHard(EOC)), i382, i383) -> f3676_0_main_InvokeMethod(EOS(STATIC_3676), java.lang.Object(RandomHard(EOC)), i382, i383, java.lang.Object(RandomHard(EOC))) :|: TRUE 25.67/13.85 f3676_0_main_InvokeMethod(EOS(STATIC_3676), java.lang.Object(RandomHard(EOC)), i382, i383, java.lang.Object(RandomHard(EOC))) -> f3743_0_getNext_Load(EOS(STATIC_3743), java.lang.Object(RandomHard(EOC)), java.lang.Object(RandomHard(EOC))) :|: i382 >= 1 && i24 > 1 && i381 >= 1 && i383 < i382 25.67/13.85 f3676_0_main_InvokeMethod(EOS(STATIC_3676), java.lang.Object(RandomHard(EOC)), i382, i383, java.lang.Object(RandomHard(EOC))) -> f3743_1_getNext_Load(EOS(STATIC_3743), java.lang.Object(RandomHard(EOC)), i382, i383, java.lang.Object(RandomHard(EOC))) :|: i382 >= 1 && i24 > 1 && i381 >= 1 && i383 < i382 25.67/13.85 f3743_0_getNext_Load(EOS(STATIC_3743), java.lang.Object(RandomHard(EOC)), java.lang.Object(RandomHard(EOC))) -> f5763_0_getNext_Load(EOS(STATIC_5763), java.lang.Object(RandomHard(EOC)), java.lang.Object(RandomHard(EOC))) :|: TRUE 25.67/13.85 f5591_0_getNext_Return(EOS(STATIC_5591), java.lang.Object(RandomHard(EOC)), i382, i383) -> f5592_0_getNext_Return(EOS(STATIC_5592), java.lang.Object(RandomHard(EOC)), i382, i383) :|: TRUE 25.67/13.85 f5592_0_getNext_Return(EOS(STATIC_5592), java.lang.Object(RandomHard(EOC)), i382, i383) -> f5593_0_main_StackPop(EOS(STATIC_5593), java.lang.Object(RandomHard(EOC)), i382, i383) :|: TRUE 25.67/13.85 f5593_0_main_StackPop(EOS(STATIC_5593), java.lang.Object(RandomHard(EOC)), i382, i383) -> f5595_0_main_Inc(EOS(STATIC_5595), java.lang.Object(RandomHard(EOC)), i382, i383) :|: TRUE 25.67/13.85 f5595_0_main_Inc(EOS(STATIC_5595), java.lang.Object(RandomHard(EOC)), i382, i383) -> f5597_0_main_JMP(EOS(STATIC_5597), java.lang.Object(RandomHard(EOC)), i382, i383 + 1) :|: TRUE 25.67/13.85 f5597_0_main_JMP(EOS(STATIC_5597), java.lang.Object(RandomHard(EOC)), i382, i751) -> f5599_0_main_Load(EOS(STATIC_5599), java.lang.Object(RandomHard(EOC)), i382, i751) :|: TRUE 25.67/13.85 f5599_0_main_Load(EOS(STATIC_5599), java.lang.Object(RandomHard(EOC)), i382, i751) -> f3637_0_main_Load(EOS(STATIC_3637), java.lang.Object(RandomHard(EOC)), i382, i751) :|: TRUE 25.67/13.85 f3637_0_main_Load(EOS(STATIC_3637), java.lang.Object(RandomHard(EOC)), i382, i383) -> f3642_0_main_Load(EOS(STATIC_3642), java.lang.Object(RandomHard(EOC)), i382, i383, i383) :|: TRUE 25.67/13.85 f3743_1_getNext_Load(EOS(STATIC_3743), java.lang.Object(RandomHard(EOC)), i382, i383, java.lang.Object(RandomHard(EOC))) -> f5591_0_getNext_Return(EOS(STATIC_5591), java.lang.Object(RandomHard(EOC)), i382, i383) :|: TRUE 25.67/13.85 Combined rules. Obtained 2 IRulesP rules: 25.67/13.85 f5591_0_getNext_Return(EOS(STATIC_5591), java.lang.Object(RandomHard(EOC)), i382:0, i383:0) -> f5591_0_getNext_Return(EOS(STATIC_5591), java.lang.Object(RandomHard(EOC)), i382:0, i383:0 + 1) :|: i24:0 > 1 && i382:0 > 0 && i383:0 + 1 < i382:0 && i381:0 > 0 25.67/13.85 Removed following non-SCC rules: 25.67/13.85 f5591_0_getNext_Return(EOS(STATIC_5591), java.lang.Object(RandomHard(EOC)), i382:0, i383:0) -> f5763_0_getNext_Load(EOS(STATIC_5763), java.lang.Object(RandomHard(EOC)), java.lang.Object(RandomHard(EOC))) :|: i24:0 > 1 && i382:0 > 0 && i383:0 + 1 < i382:0 && i381:0 > 0 25.67/13.85 Filtered constant ground arguments: 25.67/13.85 f5591_0_getNext_Return(x1, x2, x3, x4) -> f5591_0_getNext_Return(x3, x4) 25.67/13.85 EOS(x1) -> EOS 25.67/13.85 java.lang.Object(x1) -> java.lang.Object 25.67/13.85 RandomHard(x1) -> RandomHard 25.67/13.85 Finished conversion. Obtained 1 rules.P rules: 25.67/13.85 f5591_0_getNext_Return(i382:0, i383:0) -> f5591_0_getNext_Return(i382:0, i383:0 + 1) :|: i382:0 > 0 && i24:0 > 1 && i381:0 > 0 && i383:0 + 1 < i382:0 25.67/13.85 25.67/13.85 ---------------------------------------- 25.67/13.85 25.67/13.85 (35) 25.67/13.85 Obligation: 25.67/13.85 Rules: 25.67/13.85 f5591_0_getNext_Return(i382:0, i383:0) -> f5591_0_getNext_Return(i382:0, i383:0 + 1) :|: i382:0 > 0 && i24:0 > 1 && i381:0 > 0 && i383:0 + 1 < i382:0 25.67/13.85 25.67/13.85 ---------------------------------------- 25.67/13.85 25.67/13.85 (36) IRSFormatTransformerProof (EQUIVALENT) 25.67/13.85 Reformatted IRS to match normalized format (transformed away non-linear left-hand sides, !=, / and %). 25.67/13.85 ---------------------------------------- 25.67/13.85 25.67/13.85 (37) 25.67/13.85 Obligation: 25.67/13.85 Rules: 25.67/13.85 f5591_0_getNext_Return(i382:0, i383:0) -> f5591_0_getNext_Return(i382:0, arith) :|: i382:0 > 0 && i24:0 > 1 && i381:0 > 0 && i383:0 + 1 < i382:0 && arith = i383:0 + 1 25.67/13.85 25.67/13.85 ---------------------------------------- 25.67/13.85 25.67/13.85 (38) IRSwTTerminationDigraphProof (EQUIVALENT) 25.67/13.85 Constructed termination digraph! 25.67/13.85 Nodes: 25.67/13.85 (1) f5591_0_getNext_Return(i382:0, i383:0) -> f5591_0_getNext_Return(i382:0, arith) :|: i382:0 > 0 && i24:0 > 1 && i381:0 > 0 && i383:0 + 1 < i382:0 && arith = i383:0 + 1 25.67/13.85 25.67/13.85 Arcs: 25.67/13.85 (1) -> (1) 25.67/13.85 25.67/13.85 This digraph is fully evaluated! 25.67/13.85 ---------------------------------------- 25.67/13.85 25.67/13.85 (39) 25.67/13.85 Obligation: 25.67/13.85 25.67/13.85 Termination digraph: 25.67/13.85 Nodes: 25.67/13.85 (1) f5591_0_getNext_Return(i382:0, i383:0) -> f5591_0_getNext_Return(i382:0, arith) :|: i382:0 > 0 && i24:0 > 1 && i381:0 > 0 && i383:0 + 1 < i382:0 && arith = i383:0 + 1 25.67/13.85 25.67/13.85 Arcs: 25.67/13.85 (1) -> (1) 25.67/13.85 25.67/13.85 This digraph is fully evaluated! 25.67/13.85 25.67/13.85 ---------------------------------------- 25.67/13.85 25.67/13.85 (40) IntTRSCompressionProof (EQUIVALENT) 25.67/13.85 Compressed rules. 25.67/13.85 ---------------------------------------- 25.67/13.85 25.67/13.85 (41) 25.67/13.85 Obligation: 25.67/13.85 Rules: 25.67/13.85 f5591_0_getNext_Return(i382:0:0, i383:0:0) -> f5591_0_getNext_Return(i382:0:0, i383:0:0 + 1) :|: i381:0:0 > 0 && i383:0:0 + 1 < i382:0:0 && i24:0:0 > 1 && i382:0:0 > 0 25.67/13.85 25.67/13.85 ---------------------------------------- 25.67/13.85 25.67/13.85 (42) TempFilterProof (SOUND) 25.67/13.85 Used the following sort dictionary for filtering: 25.67/13.85 f5591_0_getNext_Return(INTEGER, INTEGER) 25.67/13.85 Replaced non-predefined constructor symbols by 0. 25.67/13.85 ---------------------------------------- 25.67/13.85 25.67/13.85 (43) 25.67/13.85 Obligation: 25.67/13.85 Rules: 25.67/13.85 f5591_0_getNext_Return(i382:0:0, i383:0:0) -> f5591_0_getNext_Return(i382:0:0, c) :|: c = i383:0:0 + 1 && (i381:0:0 > 0 && i383:0:0 + 1 < i382:0:0 && i24:0:0 > 1 && i382:0:0 > 0) 25.67/13.85 25.67/13.85 ---------------------------------------- 25.67/13.85 25.67/13.85 (44) PolynomialOrderProcessor (EQUIVALENT) 25.67/13.85 Found the following polynomial interpretation: 25.67/13.85 [f5591_0_getNext_Return(x, x1)] = x - x1 25.67/13.85 25.67/13.85 The following rules are decreasing: 25.67/13.85 f5591_0_getNext_Return(i382:0:0, i383:0:0) -> f5591_0_getNext_Return(i382:0:0, c) :|: c = i383:0:0 + 1 && (i381:0:0 > 0 && i383:0:0 + 1 < i382:0:0 && i24:0:0 > 1 && i382:0:0 > 0) 25.67/13.85 The following rules are bounded: 25.67/13.85 f5591_0_getNext_Return(i382:0:0, i383:0:0) -> f5591_0_getNext_Return(i382:0:0, c) :|: c = i383:0:0 + 1 && (i381:0:0 > 0 && i383:0:0 + 1 < i382:0:0 && i24:0:0 > 1 && i382:0:0 > 0) 25.67/13.85 25.67/13.85 ---------------------------------------- 25.67/13.85 25.67/13.85 (45) 25.67/13.85 YES 25.67/13.88 EOF