13.27/4.49 MAYBE 13.27/4.51 proof of /export/starexec/sandbox/benchmark/theBenchmark.jar 13.27/4.51 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 13.27/4.51 13.27/4.51 13.27/4.51 termination of the given Bare JBC problem could not be shown: 13.27/4.51 13.27/4.51 (0) Bare JBC problem 13.27/4.51 (1) BareJBCToJBCProof [EQUIVALENT, 96 ms] 13.27/4.51 (2) JBC problem 13.27/4.51 (3) JBCToGraph [EQUIVALENT, 870 ms] 13.27/4.51 (4) JBCTerminationGraph 13.27/4.51 (5) TerminationGraphToSCCProof [SOUND, 0 ms] 13.27/4.51 (6) AND 13.27/4.51 (7) JBCTerminationSCC 13.27/4.51 (8) SCCToIRSProof [SOUND, 29 ms] 13.27/4.51 (9) IRSwT 13.27/4.51 (10) IRSFormatTransformerProof [EQUIVALENT, 0 ms] 13.27/4.51 (11) IRSwT 13.27/4.51 (12) IRSwTTerminationDigraphProof [EQUIVALENT, 19 ms] 13.27/4.51 (13) IRSwT 13.27/4.51 (14) IntTRSCompressionProof [EQUIVALENT, 0 ms] 13.27/4.51 (15) IRSwT 13.27/4.51 (16) TempFilterProof [SOUND, 30 ms] 13.27/4.51 (17) IntTRS 13.27/4.51 (18) RankingReductionPairProof [EQUIVALENT, 0 ms] 13.27/4.51 (19) YES 13.27/4.51 (20) JBCTerminationSCC 13.27/4.51 (21) SCCToIRSProof [SOUND, 75 ms] 13.27/4.51 (22) IRSwT 13.27/4.51 (23) IRSFormatTransformerProof [EQUIVALENT, 0 ms] 13.27/4.51 (24) IRSwT 13.27/4.51 (25) IRSwTTerminationDigraphProof [EQUIVALENT, 54 ms] 13.27/4.51 (26) IRSwT 13.27/4.51 (27) IntTRSCompressionProof [EQUIVALENT, 0 ms] 13.27/4.51 (28) IRSwT 13.27/4.51 (29) FilterProof [EQUIVALENT, 0 ms] 13.27/4.51 (30) IntTRS 13.27/4.51 (31) IntTRSCompressionProof [EQUIVALENT, 0 ms] 13.27/4.51 (32) IntTRS 13.27/4.51 (33) IntTRSPeriodicNontermProof [COMPLETE, 11 ms] 13.27/4.51 (34) NO 13.27/4.51 (35) JBCTerminationSCC 13.27/4.51 (36) SCCToIRSProof [SOUND, 70 ms] 13.27/4.51 (37) IRSwT 13.27/4.51 (38) IRSFormatTransformerProof [EQUIVALENT, 0 ms] 13.27/4.51 (39) IRSwT 13.27/4.51 (40) IRSwTTerminationDigraphProof [EQUIVALENT, 86 ms] 13.27/4.51 (41) IRSwT 13.27/4.51 (42) IntTRSCompressionProof [EQUIVALENT, 0 ms] 13.27/4.51 (43) IRSwT 13.27/4.51 (44) FilterProof [EQUIVALENT, 0 ms] 13.27/4.51 (45) IntTRS 13.27/4.51 (46) IntTRSCompressionProof [EQUIVALENT, 0 ms] 13.27/4.51 (47) IntTRS 13.27/4.51 (48) IntTRSPeriodicNontermProof [COMPLETE, 11 ms] 13.27/4.51 (49) NO 13.27/4.51 13.27/4.51 13.27/4.51 ---------------------------------------- 13.27/4.51 13.27/4.51 (0) 13.27/4.51 Obligation: 13.27/4.51 need to prove termination of the following program: 13.27/4.51 /** 13.27/4.51 * Parts of the below code have been adapted from 13.27/4.51 * 13.27/4.51 * http://www0.cs.ucl.ac.uk/staff/p.ohearn/Talks/SAStalk.pdf 13.27/4.51 * 13.27/4.51 * Based on the motivating example of the paper 13.27/4.51 * 13.27/4.51 * Automatic termination proofs for programs with shape-shifting heaps 13.27/4.51 * Josh Berdine, Byron Cook, Dino Distefano, and Peter W. O’Hearn 13.27/4.51 * In Proc. CAV'06, LNCS 4144, pp. 386 - 400, 2006. 13.27/4.51 */ 13.27/4.51 public class Kernel93 { 13.27/4.51 /** 13.27/4.51 * A reference to the next list element. 13.27/4.51 */ 13.27/4.51 private Kernel93 next; 13.27/4.51 13.27/4.51 public static void main(String[] args) { 13.27/4.51 int random1 = args[0].length(); 13.27/4.51 int random2 = args[1].length(); 13.27/4.51 13.27/4.51 //slide68(random1, random2); 13.27/4.51 //slide88(random1, random2); 13.27/4.51 slide93(random1, random2); 13.27/4.51 //slide95(random1, random2); 13.27/4.51 } 13.27/4.51 13.27/4.51 /** 13.27/4.51 * Create a new list element. 13.27/4.51 * @param n a reference to the next element. 13.27/4.51 */ 13.27/4.51 public Kernel93(final Kernel93 n) { 13.27/4.51 this.next = n; 13.27/4.51 } 13.27/4.51 13.27/4.51 /** 13.27/4.51 * Create a new cyclical list of a length x. 13.27/4.51 * @param x some length 13.27/4.51 * @return cyclical list of length max(1, x) 13.27/4.51 */ 13.27/4.51 public static Kernel93 create(int x) { 13.27/4.51 Kernel93 last, current; 13.27/4.51 last = current = new Kernel93(null); 13.27/4.51 while (--x > 0) 13.27/4.51 current = new Kernel93(current); 13.27/4.51 return last.next = current; 13.27/4.51 } 13.27/4.51 13.27/4.51 /** 13.27/4.51 * Check if the last bit of x is > 0. 13.27/4.51 */ 13.27/4.51 private static boolean check(int x) { 13.27/4.51 return x % 2 > 0; 13.27/4.51 } 13.27/4.51 13.27/4.51 public static void slide68(int random1, int random2) { 13.27/4.51 Kernel93 h = create(random1); 13.27/4.51 Kernel93 p = h; 13.27/4.51 Kernel93 c = p.next; 13.27/4.51 while (c != h) { 13.27/4.51 Kernel93 o = c; 13.27/4.51 c = c.next; 13.27/4.51 if (check(random2)) { // nondet() 13.27/4.51 p.next = c; 13.27/4.51 //dispose(o); 13.27/4.51 o = null; 13.27/4.51 // Java's garbage collector will notice that the object 13.27/4.51 // previously referenced by o is not referenced any more 13.27/4.51 // and will release it (of course, in the next loop iteration 13.27/4.51 // this would happen anyway); obviously, this does not have 13.27/4.51 // quite the impact of a proper "dispose" operation, which 13.27/4.51 // also renders all other pointer invalid that happen to point 13.27/4.51 // to the same address 13.27/4.51 } else { 13.27/4.51 p = o; 13.27/4.51 } 13.27/4.51 13.27/4.51 // get a fresh random bit to the end of random2 13.27/4.51 random2 = random2 / 2; 13.27/4.51 } 13.27/4.51 } 13.27/4.51 13.27/4.51 public static void slide88(int random1, int random2) { 13.27/4.51 Kernel93 h = create(random1); 13.27/4.51 Kernel93 p = h; 13.27/4.51 Kernel93 c = p.next; 13.27/4.51 while (c != h) { 13.27/4.51 Kernel93 o = c; 13.27/4.51 //c = c.next; 13.27/4.51 if (check(random2)) { // nondet() 13.27/4.51 Kernel93 e = o.next; 13.27/4.51 p.next = e; 13.27/4.51 //dispose(o); 13.27/4.51 o = null; 13.27/4.51 // Java's garbage collector will notice that the object 13.27/4.51 // previously referenced by o is not referenced any more 13.27/4.51 // and will release it 13.27/4.51 c = o; 13.27/4.51 // for a faithful translation of the original C code, 13.27/4.51 // let c point to whatever o points to -- the interesting 13.27/4.51 // aspect is that dereferencing this memory location 13.27/4.51 // henceforth is a very bad idea (in C, obviously, this would 13.27/4.51 // not necessarily lead to a clean exception at runtime) 13.27/4.51 } else { 13.27/4.51 p = o; 13.27/4.51 } 13.27/4.51 c = c.next; 13.27/4.51 13.27/4.51 // get a fresh random bit to the end of random2 13.27/4.51 random2 = random2 / 2; 13.27/4.51 } 13.27/4.51 } 13.27/4.51 13.27/4.51 /** 13.27/4.51 * Non-terminating. 13.27/4.51 */ 13.27/4.51 public static void slide93(int random1, int random2) { 13.27/4.51 Kernel93 h = create(random1); 13.27/4.51 Kernel93 p = h; 13.27/4.51 Kernel93 c = p.next; 13.27/4.51 while (c != h) { 13.27/4.51 Kernel93 o = c; 13.27/4.51 //c = c.next; 13.27/4.51 13.27/4.51 if (check(random2)) { // nondet() 13.27/4.51 Kernel93 e = o.next; 13.27/4.51 p.next = e; 13.27/4.51 o.next = o; 13.27/4.51 } else { 13.27/4.51 p = o; 13.27/4.51 } 13.27/4.51 c = c.next; 13.27/4.51 13.27/4.51 // get a fresh random bit to the end of random2 13.27/4.51 random2 = random2 / 2; 13.27/4.51 } 13.27/4.51 } 13.27/4.51 13.27/4.51 public static void slide95(int random1, int random2) { 13.27/4.51 Kernel93 h = create(random1); 13.27/4.51 Kernel93 p = h; 13.27/4.51 Kernel93 c = p.next; 13.27/4.51 while (c != h) { 13.27/4.51 Kernel93 o = c; 13.27/4.51 c = c.next; 13.27/4.51 13.27/4.51 if (check(random2)) { // nondet() 13.27/4.51 Kernel93 e = o.next; 13.27/4.51 p.next = e; 13.27/4.51 o.next = o; 13.27/4.51 } else { 13.27/4.51 p = o; 13.27/4.51 } 13.27/4.51 13.27/4.51 // get a fresh random bit to the end of random2 13.27/4.51 random2 = random2 / 2; 13.27/4.51 } 13.27/4.51 } 13.27/4.51 13.27/4.51 } 13.27/4.51 13.27/4.51 13.27/4.51 13.27/4.51 ---------------------------------------- 13.27/4.51 13.27/4.51 (1) BareJBCToJBCProof (EQUIVALENT) 13.27/4.51 initialized classpath 13.27/4.51 ---------------------------------------- 13.27/4.51 13.27/4.51 (2) 13.27/4.51 Obligation: 13.27/4.51 need to prove termination of the following program: 13.27/4.51 /** 13.27/4.51 * Parts of the below code have been adapted from 13.27/4.51 * 13.27/4.51 * http://www0.cs.ucl.ac.uk/staff/p.ohearn/Talks/SAStalk.pdf 13.27/4.51 * 13.27/4.51 * Based on the motivating example of the paper 13.27/4.51 * 13.27/4.51 * Automatic termination proofs for programs with shape-shifting heaps 13.27/4.51 * Josh Berdine, Byron Cook, Dino Distefano, and Peter W. O’Hearn 13.27/4.51 * In Proc. CAV'06, LNCS 4144, pp. 386 - 400, 2006. 13.27/4.51 */ 13.27/4.51 public class Kernel93 { 13.27/4.51 /** 13.27/4.51 * A reference to the next list element. 13.27/4.51 */ 13.27/4.51 private Kernel93 next; 13.27/4.51 13.27/4.51 public static void main(String[] args) { 13.27/4.51 int random1 = args[0].length(); 13.27/4.51 int random2 = args[1].length(); 13.27/4.51 13.27/4.51 //slide68(random1, random2); 13.27/4.51 //slide88(random1, random2); 13.27/4.51 slide93(random1, random2); 13.27/4.51 //slide95(random1, random2); 13.27/4.51 } 13.27/4.51 13.27/4.51 /** 13.27/4.51 * Create a new list element. 13.27/4.51 * @param n a reference to the next element. 13.27/4.51 */ 13.27/4.51 public Kernel93(final Kernel93 n) { 13.27/4.51 this.next = n; 13.27/4.51 } 13.27/4.51 13.27/4.51 /** 13.27/4.51 * Create a new cyclical list of a length x. 13.27/4.51 * @param x some length 13.27/4.51 * @return cyclical list of length max(1, x) 13.27/4.51 */ 13.27/4.51 public static Kernel93 create(int x) { 13.27/4.51 Kernel93 last, current; 13.27/4.51 last = current = new Kernel93(null); 13.27/4.51 while (--x > 0) 13.27/4.51 current = new Kernel93(current); 13.27/4.51 return last.next = current; 13.27/4.51 } 13.27/4.51 13.27/4.51 /** 13.27/4.51 * Check if the last bit of x is > 0. 13.27/4.51 */ 13.27/4.51 private static boolean check(int x) { 13.27/4.51 return x % 2 > 0; 13.27/4.51 } 13.27/4.51 13.27/4.51 public static void slide68(int random1, int random2) { 13.27/4.51 Kernel93 h = create(random1); 13.27/4.51 Kernel93 p = h; 13.27/4.51 Kernel93 c = p.next; 13.27/4.51 while (c != h) { 13.27/4.51 Kernel93 o = c; 13.27/4.51 c = c.next; 13.27/4.51 if (check(random2)) { // nondet() 13.27/4.51 p.next = c; 13.27/4.51 //dispose(o); 13.27/4.51 o = null; 13.27/4.51 // Java's garbage collector will notice that the object 13.27/4.51 // previously referenced by o is not referenced any more 13.27/4.51 // and will release it (of course, in the next loop iteration 13.27/4.51 // this would happen anyway); obviously, this does not have 13.27/4.51 // quite the impact of a proper "dispose" operation, which 13.27/4.51 // also renders all other pointer invalid that happen to point 13.27/4.51 // to the same address 13.27/4.51 } else { 13.27/4.51 p = o; 13.27/4.51 } 13.27/4.51 13.27/4.51 // get a fresh random bit to the end of random2 13.27/4.51 random2 = random2 / 2; 13.27/4.51 } 13.27/4.51 } 13.27/4.51 13.27/4.51 public static void slide88(int random1, int random2) { 13.27/4.51 Kernel93 h = create(random1); 13.27/4.51 Kernel93 p = h; 13.27/4.51 Kernel93 c = p.next; 13.27/4.51 while (c != h) { 13.27/4.51 Kernel93 o = c; 13.27/4.51 //c = c.next; 13.27/4.51 if (check(random2)) { // nondet() 13.27/4.51 Kernel93 e = o.next; 13.27/4.51 p.next = e; 13.27/4.51 //dispose(o); 13.27/4.51 o = null; 13.27/4.51 // Java's garbage collector will notice that the object 13.27/4.51 // previously referenced by o is not referenced any more 13.27/4.51 // and will release it 13.27/4.51 c = o; 13.27/4.51 // for a faithful translation of the original C code, 13.27/4.51 // let c point to whatever o points to -- the interesting 13.27/4.51 // aspect is that dereferencing this memory location 13.27/4.51 // henceforth is a very bad idea (in C, obviously, this would 13.27/4.51 // not necessarily lead to a clean exception at runtime) 13.27/4.51 } else { 13.27/4.51 p = o; 13.27/4.51 } 13.27/4.51 c = c.next; 13.27/4.51 13.27/4.51 // get a fresh random bit to the end of random2 13.27/4.51 random2 = random2 / 2; 13.27/4.51 } 13.27/4.51 } 13.27/4.51 13.27/4.51 /** 13.27/4.51 * Non-terminating. 13.27/4.51 */ 13.27/4.51 public static void slide93(int random1, int random2) { 13.27/4.51 Kernel93 h = create(random1); 13.27/4.51 Kernel93 p = h; 13.27/4.51 Kernel93 c = p.next; 13.27/4.51 while (c != h) { 13.27/4.51 Kernel93 o = c; 13.27/4.51 //c = c.next; 13.27/4.51 13.27/4.51 if (check(random2)) { // nondet() 13.27/4.51 Kernel93 e = o.next; 13.27/4.51 p.next = e; 13.27/4.51 o.next = o; 13.27/4.51 } else { 13.27/4.51 p = o; 13.27/4.51 } 13.27/4.51 c = c.next; 13.27/4.51 13.27/4.51 // get a fresh random bit to the end of random2 13.27/4.51 random2 = random2 / 2; 13.27/4.51 } 13.27/4.51 } 13.27/4.51 13.27/4.51 public static void slide95(int random1, int random2) { 13.27/4.51 Kernel93 h = create(random1); 13.27/4.51 Kernel93 p = h; 13.27/4.51 Kernel93 c = p.next; 13.27/4.51 while (c != h) { 13.27/4.51 Kernel93 o = c; 13.27/4.51 c = c.next; 13.27/4.51 13.27/4.51 if (check(random2)) { // nondet() 13.27/4.51 Kernel93 e = o.next; 13.27/4.51 p.next = e; 13.27/4.51 o.next = o; 13.27/4.51 } else { 13.27/4.51 p = o; 13.27/4.51 } 13.27/4.51 13.27/4.51 // get a fresh random bit to the end of random2 13.27/4.51 random2 = random2 / 2; 13.27/4.51 } 13.27/4.51 } 13.27/4.51 13.27/4.51 } 13.27/4.51 13.27/4.51 13.27/4.51 13.27/4.51 ---------------------------------------- 13.27/4.51 13.27/4.51 (3) JBCToGraph (EQUIVALENT) 13.27/4.51 Constructed TerminationGraph. 13.27/4.51 ---------------------------------------- 13.27/4.51 13.27/4.51 (4) 13.27/4.51 Obligation: 13.27/4.51 Termination Graph based on JBC Program: 13.27/4.51 Kernel93.main([Ljava/lang/String;)V: Graph of 297 nodes with 2 SCCs. 13.27/4.51 13.27/4.51 13.27/4.51 13.27/4.51 Kernel93.create(I)LKernel93;: Graph of 42 nodes with 1 SCC. 13.27/4.51 13.27/4.51 13.27/4.51 13.27/4.51 13.27/4.51 13.27/4.51 ---------------------------------------- 13.27/4.51 13.27/4.51 (5) TerminationGraphToSCCProof (SOUND) 13.27/4.51 Splitted TerminationGraph to 3 SCCss. 13.27/4.51 ---------------------------------------- 13.27/4.51 13.27/4.51 (6) 13.27/4.51 Complex Obligation (AND) 13.27/4.51 13.27/4.51 ---------------------------------------- 13.27/4.51 13.27/4.51 (7) 13.27/4.51 Obligation: 13.27/4.51 SCC of termination graph based on JBC Program. 13.27/4.51 SCC contains nodes from the following methods: Kernel93.create(I)LKernel93; 13.27/4.51 SCC calls the following helper methods: 13.27/4.51 Performed SCC analyses: 13.27/4.51 *Used field analysis yielded the following read fields: 13.27/4.51 13.27/4.51 *Marker field analysis yielded the following relations that could be markers: 13.27/4.51 13.27/4.51 ---------------------------------------- 13.27/4.51 13.27/4.51 (8) SCCToIRSProof (SOUND) 13.27/4.51 Transformed FIGraph SCCs to intTRSs. Log: 13.27/4.51 Generated rules. Obtained 17 IRulesP rules: 13.27/4.51 f820_0_create_Load(EOS(STATIC_820), i80, o74[Kernel93.next]o73) -> f826_0_create_LE(EOS(STATIC_826), i80, i80, o74[Kernel93.next]o73) :|: TRUE 13.27/4.51 f826_0_create_LE(EOS(STATIC_826), i82, i82, o74[Kernel93.next]o73) -> f834_0_create_LE(EOS(STATIC_834), i82, i82, o74[Kernel93.next]o73) :|: TRUE 13.27/4.51 f834_0_create_LE(EOS(STATIC_834), i82, i82, o74[Kernel93.next]o73) -> f840_0_create_New(EOS(STATIC_840), i82, o74[Kernel93.next]o73) :|: i82 > 0 13.27/4.51 f840_0_create_New(EOS(STATIC_840), i82, o74[Kernel93.next]o73) -> f846_0_create_Duplicate(EOS(STATIC_846), i82, o74[Kernel93.next]o73) :|: TRUE 13.27/4.51 f846_0_create_Duplicate(EOS(STATIC_846), i82, o74[Kernel93.next]o73) -> f854_0_create_Load(EOS(STATIC_854), i82, o74[Kernel93.next]o73) :|: TRUE 13.27/4.51 f854_0_create_Load(EOS(STATIC_854), i82, o74[Kernel93.next]o73) -> f859_0_create_InvokeMethod(EOS(STATIC_859), i82, o74[Kernel93.next]o73) :|: TRUE 13.27/4.51 f859_0_create_InvokeMethod(EOS(STATIC_859), i82, o74[Kernel93.next]o73) -> f866_0__init__Load(EOS(STATIC_866), i82, o74[Kernel93.next]o73) :|: TRUE 13.27/4.51 f866_0__init__Load(EOS(STATIC_866), i82, o74[Kernel93.next]o73) -> f894_0__init__InvokeMethod(EOS(STATIC_894), i82, o74[Kernel93.next]o73) :|: TRUE 13.27/4.51 f894_0__init__InvokeMethod(EOS(STATIC_894), i82, o74[Kernel93.next]o73) -> f915_0__init__Load(EOS(STATIC_915), i82, o74[Kernel93.next]o73) :|: TRUE 13.27/4.51 f915_0__init__Load(EOS(STATIC_915), i82, o74[Kernel93.next]o73) -> f947_0__init__Load(EOS(STATIC_947), i82, o74[Kernel93.next]o73) :|: TRUE 13.27/4.51 f947_0__init__Load(EOS(STATIC_947), i82, o74[Kernel93.next]o73) -> f953_0__init__FieldAccess(EOS(STATIC_953), i82, o74[Kernel93.next]o73) :|: TRUE 13.27/4.51 f953_0__init__FieldAccess(EOS(STATIC_953), i82, o74[Kernel93.next]o73) -> f960_0__init__Return(EOS(STATIC_960), i82, o74[Kernel93.next]o73) :|: TRUE 13.27/4.51 f960_0__init__Return(EOS(STATIC_960), i82, o74[Kernel93.next]o73) -> f965_0_create_Store(EOS(STATIC_965), i82, o74[Kernel93.next]o73) :|: TRUE 13.27/4.51 f965_0_create_Store(EOS(STATIC_965), i82, o74[Kernel93.next]o73) -> f970_0_create_JMP(EOS(STATIC_970), i82, o74[Kernel93.next]o73) :|: TRUE 13.27/4.51 f970_0_create_JMP(EOS(STATIC_970), i82, o74[Kernel93.next]o73) -> f1043_0_create_Inc(EOS(STATIC_1043), i82, o74[Kernel93.next]o73) :|: TRUE 13.27/4.51 f1043_0_create_Inc(EOS(STATIC_1043), i82, o74[Kernel93.next]o73) -> f808_0_create_Inc(EOS(STATIC_808), i82, o81[Kernel93.next]o73) :|: TRUE 13.27/4.51 f808_0_create_Inc(EOS(STATIC_808), i55, o74[Kernel93.next]o73) -> f820_0_create_Load(EOS(STATIC_820), i55 + -1, o74[Kernel93.next]o73) :|: TRUE 13.27/4.51 Combined rules. Obtained 1 IRulesP rules: 13.27/4.51 f820_0_create_Load(EOS(STATIC_820), i80:0, o74[Kernel93.next]o73:0) -> f820_0_create_Load(EOS(STATIC_820), i80:0 - 1, o81[Kernel93.next]o73:0) :|: i80:0 > 0 13.27/4.51 Filtered constant ground arguments: 13.27/4.51 f820_0_create_Load(x1, x2, x3) -> f820_0_create_Load(x2, x3) 13.27/4.51 EOS(x1) -> EOS 13.27/4.51 Filtered unneeded arguments: 13.27/4.51 f820_0_create_Load(x1, x2) -> f820_0_create_Load(x1) 13.27/4.51 Finished conversion. Obtained 1 rules.P rules: 13.27/4.51 f820_0_create_Load(i80:0) -> f820_0_create_Load(i80:0 - 1) :|: i80:0 > 0 13.27/4.51 13.27/4.51 ---------------------------------------- 13.27/4.51 13.27/4.51 (9) 13.27/4.51 Obligation: 13.27/4.51 Rules: 13.27/4.51 f820_0_create_Load(i80:0) -> f820_0_create_Load(i80:0 - 1) :|: i80:0 > 0 13.27/4.51 13.27/4.51 ---------------------------------------- 13.27/4.51 13.27/4.51 (10) IRSFormatTransformerProof (EQUIVALENT) 13.27/4.51 Reformatted IRS to match normalized format (transformed away non-linear left-hand sides, !=, / and %). 13.27/4.51 ---------------------------------------- 13.27/4.51 13.27/4.51 (11) 13.27/4.51 Obligation: 13.27/4.51 Rules: 13.27/4.51 f820_0_create_Load(i80:0) -> f820_0_create_Load(arith) :|: i80:0 > 0 && arith = i80:0 - 1 13.27/4.51 13.27/4.51 ---------------------------------------- 13.27/4.51 13.27/4.51 (12) IRSwTTerminationDigraphProof (EQUIVALENT) 13.27/4.51 Constructed termination digraph! 13.27/4.51 Nodes: 13.27/4.51 (1) f820_0_create_Load(i80:0) -> f820_0_create_Load(arith) :|: i80:0 > 0 && arith = i80:0 - 1 13.27/4.51 13.27/4.51 Arcs: 13.27/4.51 (1) -> (1) 13.27/4.51 13.27/4.51 This digraph is fully evaluated! 13.27/4.51 ---------------------------------------- 13.27/4.51 13.27/4.51 (13) 13.27/4.51 Obligation: 13.27/4.51 13.27/4.51 Termination digraph: 13.27/4.51 Nodes: 13.27/4.51 (1) f820_0_create_Load(i80:0) -> f820_0_create_Load(arith) :|: i80:0 > 0 && arith = i80:0 - 1 13.27/4.51 13.27/4.51 Arcs: 13.27/4.51 (1) -> (1) 13.27/4.51 13.27/4.51 This digraph is fully evaluated! 13.27/4.51 13.27/4.51 ---------------------------------------- 13.27/4.51 13.27/4.51 (14) IntTRSCompressionProof (EQUIVALENT) 13.27/4.51 Compressed rules. 13.27/4.51 ---------------------------------------- 13.27/4.51 13.27/4.51 (15) 13.27/4.51 Obligation: 13.27/4.51 Rules: 13.27/4.51 f820_0_create_Load(i80:0:0) -> f820_0_create_Load(i80:0:0 - 1) :|: i80:0:0 > 0 13.27/4.51 13.27/4.51 ---------------------------------------- 13.27/4.51 13.27/4.51 (16) TempFilterProof (SOUND) 13.27/4.51 Used the following sort dictionary for filtering: 13.27/4.51 f820_0_create_Load(INTEGER) 13.27/4.51 Replaced non-predefined constructor symbols by 0. 13.27/4.51 ---------------------------------------- 13.27/4.51 13.27/4.51 (17) 13.27/4.51 Obligation: 13.27/4.51 Rules: 13.27/4.51 f820_0_create_Load(i80:0:0) -> f820_0_create_Load(c) :|: c = i80:0:0 - 1 && i80:0:0 > 0 13.27/4.51 13.27/4.51 ---------------------------------------- 13.27/4.51 13.27/4.51 (18) RankingReductionPairProof (EQUIVALENT) 13.27/4.51 Interpretation: 13.27/4.51 [ f820_0_create_Load ] = f820_0_create_Load_1 13.27/4.51 13.27/4.51 The following rules are decreasing: 13.27/4.51 f820_0_create_Load(i80:0:0) -> f820_0_create_Load(c) :|: c = i80:0:0 - 1 && i80:0:0 > 0 13.27/4.51 13.27/4.51 The following rules are bounded: 13.27/4.51 f820_0_create_Load(i80:0:0) -> f820_0_create_Load(c) :|: c = i80:0:0 - 1 && i80:0:0 > 0 13.27/4.51 13.27/4.51 13.27/4.51 ---------------------------------------- 13.27/4.51 13.27/4.51 (19) 13.27/4.51 YES 13.27/4.51 13.27/4.51 ---------------------------------------- 13.27/4.51 13.27/4.51 (20) 13.27/4.51 Obligation: 13.27/4.51 SCC of termination graph based on JBC Program. 13.27/4.51 SCC contains nodes from the following methods: Kernel93.main([Ljava/lang/String;)V 13.27/4.51 SCC calls the following helper methods: 13.27/4.51 Performed SCC analyses: 13.27/4.51 *Used field analysis yielded the following read fields: 13.27/4.51 *Kernel93: [next] 13.27/4.51 *Marker field analysis yielded the following relations that could be markers: 13.27/4.51 13.27/4.51 ---------------------------------------- 13.27/4.51 13.27/4.51 (21) SCCToIRSProof (SOUND) 13.27/4.51 Transformed FIGraph SCCs to intTRSs. Log: 13.27/4.51 Generated rules. Obtained 77 IRulesP rules: 13.27/4.51 f4717_0_slide93_EQ(EOS(STATIC_4717), i519) -> f4722_0_slide93_Load(EOS(STATIC_4722), i519) :|: TRUE 13.27/4.51 f4722_0_slide93_Load(EOS(STATIC_4722), i519) -> f4728_0_slide93_Store(EOS(STATIC_4728), i519) :|: TRUE 13.27/4.51 f4728_0_slide93_Store(EOS(STATIC_4728), i519) -> f4732_0_slide93_Load(EOS(STATIC_4732), i519) :|: TRUE 13.27/4.51 f4732_0_slide93_Load(EOS(STATIC_4732), i519) -> f4734_0_slide93_InvokeMethod(EOS(STATIC_4734), i519, i519) :|: TRUE 13.27/4.51 f4734_0_slide93_InvokeMethod(EOS(STATIC_4734), i519, i519) -> f4736_0_check_Load(EOS(STATIC_4736), i519, i519) :|: TRUE 13.27/4.51 f4736_0_check_Load(EOS(STATIC_4736), i519, i519) -> f4740_0_check_ConstantStackPush(EOS(STATIC_4740), i519, i519) :|: TRUE 13.27/4.51 f4740_0_check_ConstantStackPush(EOS(STATIC_4740), i519, i519) -> f4744_0_check_IntArithmetic(EOS(STATIC_4744), i519, i519, 2) :|: TRUE 13.27/4.51 f4744_0_check_IntArithmetic(EOS(STATIC_4744), i519, i519, matching1) -> f4755_0_check_LE(EOS(STATIC_4755), i519, i519 % 2) :|: TRUE && matching1 = 2 13.27/4.51 f4755_0_check_LE(EOS(STATIC_4755), i519, matching1) -> f4759_0_check_LE(EOS(STATIC_4759), i519, 0) :|: TRUE && matching1 = 0 13.27/4.51 f4755_0_check_LE(EOS(STATIC_4755), i519, matching1) -> f4760_0_check_LE(EOS(STATIC_4760), i519, 1) :|: TRUE && matching1 = 1 13.27/4.51 f4759_0_check_LE(EOS(STATIC_4759), i519, matching1) -> f4764_0_check_ConstantStackPush(EOS(STATIC_4764), i519) :|: 0 <= 0 && matching1 = 0 13.27/4.51 f4764_0_check_ConstantStackPush(EOS(STATIC_4764), i519) -> f4774_0_check_Return(EOS(STATIC_4774), i519, 0) :|: TRUE 13.27/4.51 f4774_0_check_Return(EOS(STATIC_4774), i519, matching1) -> f4782_0_slide93_EQ(EOS(STATIC_4782), i519, 0) :|: TRUE && matching1 = 0 13.27/4.51 f4782_0_slide93_EQ(EOS(STATIC_4782), i519, matching1) -> f4790_0_slide93_Load(EOS(STATIC_4790), i519) :|: TRUE && matching1 = 0 13.27/4.51 f4790_0_slide93_Load(EOS(STATIC_4790), i519) -> f4799_0_slide93_Store(EOS(STATIC_4799), i519) :|: TRUE 13.27/4.51 f4799_0_slide93_Store(EOS(STATIC_4799), i519) -> f4812_0_slide93_Load(EOS(STATIC_4812), i519) :|: TRUE 13.27/4.51 f4812_0_slide93_Load(EOS(STATIC_4812), i519) -> f4825_0_slide93_FieldAccess(EOS(STATIC_4825), i519) :|: TRUE 13.27/4.51 f4825_0_slide93_FieldAccess(EOS(STATIC_4825), i519) -> f4873_0_slide93_Store(EOS(STATIC_4873), i519) :|: TRUE 13.27/4.51 f4873_0_slide93_Store(EOS(STATIC_4873), i519) -> f4885_0_slide93_Load(EOS(STATIC_4885), i519) :|: TRUE 13.27/4.51 f4885_0_slide93_Load(EOS(STATIC_4885), i519) -> f4893_0_slide93_ConstantStackPush(EOS(STATIC_4893), i519) :|: TRUE 13.27/4.51 f4893_0_slide93_ConstantStackPush(EOS(STATIC_4893), i519) -> f4915_0_slide93_IntArithmetic(EOS(STATIC_4915), i519, 2) :|: TRUE 13.27/4.51 f4915_0_slide93_IntArithmetic(EOS(STATIC_4915), i519, matching1) -> f4927_0_slide93_Store(EOS(STATIC_4927), i605) :|: i605 = i519 / 2 && i605 <= i519 && matching1 = 2 13.27/4.51 f4927_0_slide93_Store(EOS(STATIC_4927), i605) -> f4946_0_slide93_JMP(EOS(STATIC_4946), i605) :|: TRUE 13.27/4.51 f4946_0_slide93_JMP(EOS(STATIC_4946), i605) -> f4952_0_slide93_Load(EOS(STATIC_4952), i605) :|: TRUE 13.27/4.51 f4952_0_slide93_Load(EOS(STATIC_4952), i605) -> f4636_0_slide93_Load(EOS(STATIC_4636), i605) :|: TRUE 13.27/4.51 f4636_0_slide93_Load(EOS(STATIC_4636), i519) -> f4682_0_slide93_Load(EOS(STATIC_4682), i519) :|: TRUE 13.27/4.51 f4682_0_slide93_Load(EOS(STATIC_4682), i519) -> f4700_0_slide93_EQ(EOS(STATIC_4700), i519) :|: TRUE 13.27/4.51 f4700_0_slide93_EQ(EOS(STATIC_4700), i519) -> f4717_0_slide93_EQ(EOS(STATIC_4717), i519) :|: TRUE 13.27/4.51 f4760_0_check_LE(EOS(STATIC_4760), i519, matching1) -> f4768_0_check_ConstantStackPush(EOS(STATIC_4768), i519) :|: 1 > 0 && matching1 = 1 13.27/4.51 f4768_0_check_ConstantStackPush(EOS(STATIC_4768), i519) -> f4778_0_check_JMP(EOS(STATIC_4778), i519, 1) :|: TRUE 13.27/4.51 f4778_0_check_JMP(EOS(STATIC_4778), i519, matching1) -> f4787_0_check_Return(EOS(STATIC_4787), i519, 1) :|: TRUE && matching1 = 1 13.27/4.51 f4787_0_check_Return(EOS(STATIC_4787), i519, matching1) -> f4796_0_slide93_EQ(EOS(STATIC_4796), i519, 1) :|: TRUE && matching1 = 1 13.27/4.51 f4796_0_slide93_EQ(EOS(STATIC_4796), i519, matching1) -> f4803_0_slide93_Load(EOS(STATIC_4803), i519) :|: 1 > 0 && matching1 = 1 13.27/4.51 f4803_0_slide93_Load(EOS(STATIC_4803), i519) -> f4814_0_slide93_FieldAccess(EOS(STATIC_4814), i519) :|: TRUE 13.27/4.51 f4814_0_slide93_FieldAccess(EOS(STATIC_4814), i519) -> f4844_0_slide93_Store(EOS(STATIC_4844), i519) :|: TRUE 13.27/4.51 f4844_0_slide93_Store(EOS(STATIC_4844), i519) -> f4879_0_slide93_Load(EOS(STATIC_4879), i519) :|: TRUE 13.27/4.51 f4879_0_slide93_Load(EOS(STATIC_4879), i519) -> f4889_0_slide93_Load(EOS(STATIC_4889), i519) :|: TRUE 13.27/4.51 f4889_0_slide93_Load(EOS(STATIC_4889), i519) -> f4909_0_slide93_FieldAccess(EOS(STATIC_4909), i519) :|: TRUE 13.27/4.51 f4909_0_slide93_FieldAccess(EOS(STATIC_4909), i519) -> f4920_0_slide93_FieldAccess(EOS(STATIC_4920), i519) :|: TRUE 13.27/4.51 f4920_0_slide93_FieldAccess(EOS(STATIC_4920), i519) -> f4938_0_slide93_FieldAccess(EOS(STATIC_4938), i519) :|: TRUE 13.27/4.51 f4920_0_slide93_FieldAccess(EOS(STATIC_4920), i519) -> f4940_0_slide93_FieldAccess(EOS(STATIC_4940), i519) :|: TRUE 13.27/4.51 f4938_0_slide93_FieldAccess(EOS(STATIC_4938), i519) -> f4949_0_slide93_FieldAccess(EOS(STATIC_4949), i519) :|: TRUE 13.27/4.51 f4938_0_slide93_FieldAccess(EOS(STATIC_4938), i519) -> f4950_0_slide93_FieldAccess(EOS(STATIC_4950), i519) :|: TRUE 13.27/4.51 f4949_0_slide93_FieldAccess(EOS(STATIC_4949), i519) -> f4953_0_slide93_Load(EOS(STATIC_4953), i519) :|: TRUE 13.27/4.51 f4953_0_slide93_Load(EOS(STATIC_4953), i519) -> f4956_0_slide93_Load(EOS(STATIC_4956), i519) :|: TRUE 13.27/4.51 f4956_0_slide93_Load(EOS(STATIC_4956), i519) -> f4959_0_slide93_FieldAccess(EOS(STATIC_4959), i519) :|: TRUE 13.27/4.51 f4959_0_slide93_FieldAccess(EOS(STATIC_4959), i519) -> f4962_0_slide93_JMP(EOS(STATIC_4962), i519) :|: TRUE 13.27/4.51 f4962_0_slide93_JMP(EOS(STATIC_4962), i519) -> f4965_0_slide93_Load(EOS(STATIC_4965), i519) :|: TRUE 13.27/4.51 f4965_0_slide93_Load(EOS(STATIC_4965), i519) -> f4992_0_slide93_FieldAccess(EOS(STATIC_4992), i519) :|: TRUE 13.27/4.51 f4992_0_slide93_FieldAccess(EOS(STATIC_4992), i519) -> f5008_0_slide93_Store(EOS(STATIC_5008), i519) :|: TRUE 13.27/4.51 f5008_0_slide93_Store(EOS(STATIC_5008), i519) -> f5026_0_slide93_Load(EOS(STATIC_5026), i519) :|: TRUE 13.27/4.51 f5026_0_slide93_Load(EOS(STATIC_5026), i519) -> f5040_0_slide93_ConstantStackPush(EOS(STATIC_5040), i519) :|: TRUE 13.27/4.51 f5040_0_slide93_ConstantStackPush(EOS(STATIC_5040), i519) -> f5051_0_slide93_IntArithmetic(EOS(STATIC_5051), i519, 2) :|: TRUE 13.27/4.51 f5051_0_slide93_IntArithmetic(EOS(STATIC_5051), i519, matching1) -> f5065_0_slide93_Store(EOS(STATIC_5065), i668) :|: i668 = i519 / 2 && i668 <= i519 && matching1 = 2 13.27/4.51 f5065_0_slide93_Store(EOS(STATIC_5065), i668) -> f5070_0_slide93_JMP(EOS(STATIC_5070), i668) :|: TRUE 13.27/4.51 f5070_0_slide93_JMP(EOS(STATIC_5070), i668) -> f5087_0_slide93_Load(EOS(STATIC_5087), i668) :|: TRUE 13.27/4.51 f5087_0_slide93_Load(EOS(STATIC_5087), i668) -> f4636_0_slide93_Load(EOS(STATIC_4636), i668) :|: TRUE 13.27/4.51 f4950_0_slide93_FieldAccess(EOS(STATIC_4950), i519) -> f4954_0_slide93_Load(EOS(STATIC_4954), i519) :|: TRUE 13.27/4.51 f4954_0_slide93_Load(EOS(STATIC_4954), i519) -> f4957_0_slide93_Load(EOS(STATIC_4957), i519) :|: TRUE 13.27/4.51 f4957_0_slide93_Load(EOS(STATIC_4957), i519) -> f4960_0_slide93_FieldAccess(EOS(STATIC_4960), i519) :|: TRUE 13.27/4.51 f4960_0_slide93_FieldAccess(EOS(STATIC_4960), i519) -> f4963_0_slide93_JMP(EOS(STATIC_4963), i519) :|: TRUE 13.27/4.51 f4963_0_slide93_JMP(EOS(STATIC_4963), i519) -> f4974_0_slide93_Load(EOS(STATIC_4974), i519) :|: TRUE 13.27/4.51 f4974_0_slide93_Load(EOS(STATIC_4974), i519) -> f4812_0_slide93_Load(EOS(STATIC_4812), i519) :|: TRUE 13.27/4.51 f4940_0_slide93_FieldAccess(EOS(STATIC_4940), i519) -> f4951_0_slide93_Load(EOS(STATIC_4951), i519) :|: TRUE 13.27/4.51 f4951_0_slide93_Load(EOS(STATIC_4951), i519) -> f4955_0_slide93_Load(EOS(STATIC_4955), i519) :|: TRUE 13.27/4.51 f4955_0_slide93_Load(EOS(STATIC_4955), i519) -> f4958_0_slide93_FieldAccess(EOS(STATIC_4958), i519) :|: TRUE 13.27/4.51 f4958_0_slide93_FieldAccess(EOS(STATIC_4958), i519) -> f4961_0_slide93_JMP(EOS(STATIC_4961), i519) :|: TRUE 13.27/4.51 f4961_0_slide93_JMP(EOS(STATIC_4961), i519) -> f4964_0_slide93_Load(EOS(STATIC_4964), i519) :|: TRUE 13.27/4.51 f4964_0_slide93_Load(EOS(STATIC_4964), i519) -> f4982_0_slide93_FieldAccess(EOS(STATIC_4982), i519) :|: TRUE 13.27/4.51 f4982_0_slide93_FieldAccess(EOS(STATIC_4982), i519) -> f4998_0_slide93_Store(EOS(STATIC_4998), i519) :|: TRUE 13.27/4.51 f4998_0_slide93_Store(EOS(STATIC_4998), i519) -> f5012_0_slide93_Load(EOS(STATIC_5012), i519) :|: TRUE 13.27/4.51 f5012_0_slide93_Load(EOS(STATIC_5012), i519) -> f5031_0_slide93_ConstantStackPush(EOS(STATIC_5031), i519) :|: TRUE 13.27/4.51 f5031_0_slide93_ConstantStackPush(EOS(STATIC_5031), i519) -> f5044_0_slide93_IntArithmetic(EOS(STATIC_5044), i519, 2) :|: TRUE 13.27/4.51 f5044_0_slide93_IntArithmetic(EOS(STATIC_5044), i519, matching1) -> f5056_0_slide93_Store(EOS(STATIC_5056), i667) :|: i667 = i519 / 2 && i667 <= i519 && matching1 = 2 13.27/4.51 f5056_0_slide93_Store(EOS(STATIC_5056), i667) -> f5069_0_slide93_JMP(EOS(STATIC_5069), i667) :|: TRUE 13.27/4.51 f5069_0_slide93_JMP(EOS(STATIC_5069), i667) -> f5076_0_slide93_Load(EOS(STATIC_5076), i667) :|: TRUE 13.27/4.51 f5076_0_slide93_Load(EOS(STATIC_5076), i667) -> f4636_0_slide93_Load(EOS(STATIC_4636), i667) :|: TRUE 13.27/4.51 Combined rules. Obtained 4 IRulesP rules: 13.27/4.51 f4717_0_slide93_EQ(EOS(STATIC_4717), i519:0) -> f4717_0_slide93_EQ'(EOS(STATIC_4717), i519:0) :|: i519:0 >= div1 && i519:0 - 2 * div = 1 13.27/4.51 f4717_0_slide93_EQ'(EOS(STATIC_4717), i519:0) -> f4717_0_slide93_EQ(EOS(STATIC_4717), div1) :|: i519:0 - 2 * div = 1 && i519:0 >= div1 && i519:0 - 2 * div > -2 && i519:0 - 2 * div < 2 && i519:0 - 2 * div1 < 2 && i519:0 - 2 * div1 > -2 13.27/4.51 f4717_0_slide93_EQ(EOS(STATIC_4717), i519:0) -> f4717_0_slide93_EQ'(EOS(STATIC_4717), i519:0) :|: i519:0 >= div1 && i519:0 - 2 * div = 0 13.27/4.51 f4717_0_slide93_EQ'(EOS(STATIC_4717), i519:0) -> f4717_0_slide93_EQ(EOS(STATIC_4717), div1) :|: i519:0 - 2 * div = 0 && i519:0 >= div1 && i519:0 - 2 * div > -2 && i519:0 - 2 * div < 2 && i519:0 - 2 * div1 < 2 && i519:0 - 2 * div1 > -2 13.27/4.51 Filtered constant ground arguments: 13.27/4.51 f4717_0_slide93_EQ(x1, x2) -> f4717_0_slide93_EQ(x2) 13.27/4.51 f4717_0_slide93_EQ'(x1, x2) -> f4717_0_slide93_EQ'(x2) 13.27/4.51 EOS(x1) -> EOS 13.27/4.51 Finished conversion. Obtained 4 rules.P rules: 13.27/4.51 f4717_0_slide93_EQ(i519:0) -> f4717_0_slide93_EQ'(i519:0) :|: i519:0 >= div1 && i519:0 - 2 * div = 1 13.27/4.51 f4717_0_slide93_EQ'(i519:0) -> f4717_0_slide93_EQ(div1) :|: i519:0 >= div1 && i519:0 - 2 * div = 1 && i519:0 - 2 * div > -2 && i519:0 - 2 * div < 2 && i519:0 - 2 * div1 > -2 && i519:0 - 2 * div1 < 2 13.27/4.51 f4717_0_slide93_EQ(i519:0) -> f4717_0_slide93_EQ'(i519:0) :|: i519:0 >= div1 && i519:0 - 2 * div = 0 13.27/4.51 f4717_0_slide93_EQ'(i519:0) -> f4717_0_slide93_EQ(div1) :|: i519:0 >= div1 && i519:0 - 2 * div = 0 && i519:0 - 2 * div > -2 && i519:0 - 2 * div < 2 && i519:0 - 2 * div1 > -2 && i519:0 - 2 * div1 < 2 13.27/4.51 13.27/4.51 ---------------------------------------- 13.27/4.51 13.27/4.51 (22) 13.27/4.51 Obligation: 13.27/4.51 Rules: 13.27/4.51 f4717_0_slide93_EQ(x) -> f4717_0_slide93_EQ'(x) :|: x >= x1 && x - 2 * x2 = 1 13.27/4.51 f4717_0_slide93_EQ'(x3) -> f4717_0_slide93_EQ(x4) :|: x3 >= x4 && x3 - 2 * x5 = 1 && x3 - 2 * x5 > -2 && x3 - 2 * x5 < 2 && x3 - 2 * x4 > -2 && x3 - 2 * x4 < 2 13.27/4.51 f4717_0_slide93_EQ(x6) -> f4717_0_slide93_EQ'(x6) :|: x6 >= x7 && x6 - 2 * x8 = 0 13.27/4.51 f4717_0_slide93_EQ'(x9) -> f4717_0_slide93_EQ(x10) :|: x9 >= x10 && x9 - 2 * x11 = 0 && x9 - 2 * x11 > -2 && x9 - 2 * x11 < 2 && x9 - 2 * x10 > -2 && x9 - 2 * x10 < 2 13.27/4.51 13.27/4.51 ---------------------------------------- 13.27/4.51 13.27/4.51 (23) IRSFormatTransformerProof (EQUIVALENT) 13.27/4.51 Reformatted IRS to match normalized format (transformed away non-linear left-hand sides, !=, / and %). 13.27/4.51 ---------------------------------------- 13.27/4.51 13.27/4.51 (24) 13.27/4.51 Obligation: 13.27/4.51 Rules: 13.27/4.51 f4717_0_slide93_EQ(x) -> f4717_0_slide93_EQ'(x) :|: x >= x1 && x - 2 * x2 = 1 13.27/4.51 f4717_0_slide93_EQ'(x3) -> f4717_0_slide93_EQ(x4) :|: x3 >= x4 && x3 - 2 * x5 = 1 && x3 - 2 * x5 > -2 && x3 - 2 * x5 < 2 && x3 - 2 * x4 > -2 && x3 - 2 * x4 < 2 13.27/4.51 f4717_0_slide93_EQ(x6) -> f4717_0_slide93_EQ'(x6) :|: x6 >= x7 && x6 - 2 * x8 = 0 13.27/4.51 f4717_0_slide93_EQ'(x9) -> f4717_0_slide93_EQ(x10) :|: x9 >= x10 && x9 - 2 * x11 = 0 && x9 - 2 * x11 > -2 && x9 - 2 * x11 < 2 && x9 - 2 * x10 > -2 && x9 - 2 * x10 < 2 13.27/4.51 13.27/4.51 ---------------------------------------- 13.27/4.51 13.27/4.51 (25) IRSwTTerminationDigraphProof (EQUIVALENT) 13.27/4.51 Constructed termination digraph! 13.27/4.51 Nodes: 13.27/4.51 (1) f4717_0_slide93_EQ(x) -> f4717_0_slide93_EQ'(x) :|: x >= x1 && x - 2 * x2 = 1 13.27/4.51 (2) f4717_0_slide93_EQ'(x3) -> f4717_0_slide93_EQ(x4) :|: x3 >= x4 && x3 - 2 * x5 = 1 && x3 - 2 * x5 > -2 && x3 - 2 * x5 < 2 && x3 - 2 * x4 > -2 && x3 - 2 * x4 < 2 13.27/4.51 (3) f4717_0_slide93_EQ(x6) -> f4717_0_slide93_EQ'(x6) :|: x6 >= x7 && x6 - 2 * x8 = 0 13.27/4.51 (4) f4717_0_slide93_EQ'(x9) -> f4717_0_slide93_EQ(x10) :|: x9 >= x10 && x9 - 2 * x11 = 0 && x9 - 2 * x11 > -2 && x9 - 2 * x11 < 2 && x9 - 2 * x10 > -2 && x9 - 2 * x10 < 2 13.27/4.51 13.27/4.51 Arcs: 13.27/4.51 (1) -> (2) 13.27/4.51 (2) -> (1), (3) 13.27/4.51 (3) -> (4) 13.27/4.51 (4) -> (1), (3) 13.27/4.51 13.27/4.51 This digraph is fully evaluated! 13.27/4.51 ---------------------------------------- 13.27/4.51 13.27/4.51 (26) 13.27/4.51 Obligation: 13.27/4.51 13.27/4.51 Termination digraph: 13.27/4.51 Nodes: 13.27/4.51 (1) f4717_0_slide93_EQ(x) -> f4717_0_slide93_EQ'(x) :|: x >= x1 && x - 2 * x2 = 1 13.27/4.51 (2) f4717_0_slide93_EQ'(x9) -> f4717_0_slide93_EQ(x10) :|: x9 >= x10 && x9 - 2 * x11 = 0 && x9 - 2 * x11 > -2 && x9 - 2 * x11 < 2 && x9 - 2 * x10 > -2 && x9 - 2 * x10 < 2 13.27/4.51 (3) f4717_0_slide93_EQ(x6) -> f4717_0_slide93_EQ'(x6) :|: x6 >= x7 && x6 - 2 * x8 = 0 13.27/4.51 (4) f4717_0_slide93_EQ'(x3) -> f4717_0_slide93_EQ(x4) :|: x3 >= x4 && x3 - 2 * x5 = 1 && x3 - 2 * x5 > -2 && x3 - 2 * x5 < 2 && x3 - 2 * x4 > -2 && x3 - 2 * x4 < 2 13.27/4.51 13.27/4.51 Arcs: 13.27/4.51 (1) -> (4) 13.27/4.51 (2) -> (1), (3) 13.27/4.51 (3) -> (2) 13.27/4.51 (4) -> (1), (3) 13.27/4.51 13.27/4.51 This digraph is fully evaluated! 13.27/4.51 13.27/4.51 ---------------------------------------- 13.27/4.51 13.27/4.51 (27) IntTRSCompressionProof (EQUIVALENT) 13.27/4.51 Compressed rules. 13.27/4.51 ---------------------------------------- 13.27/4.51 13.27/4.51 (28) 13.27/4.51 Obligation: 13.27/4.51 Rules: 13.27/4.51 f4717_0_slide93_EQ(x:0) -> f4717_0_slide93_EQ'(x:0) :|: x:0 >= x1:0 && x:0 - 2 * x2:0 = 1 13.27/4.51 f4717_0_slide93_EQ'(x9:0) -> f4717_0_slide93_EQ(x10:0) :|: x9:0 - 2 * x10:0 > -2 && x9:0 - 2 * x10:0 < 2 && x9:0 - 2 * x11:0 < 2 && x9:0 - 2 * x11:0 > -2 && x9:0 - 2 * x11:0 = 0 && x9:0 >= x10:0 13.27/4.51 f4717_0_slide93_EQ'(x3:0) -> f4717_0_slide93_EQ(x4:0) :|: x3:0 - 2 * x4:0 > -2 && x3:0 - 2 * x4:0 < 2 && x3:0 - 2 * x5:0 < 2 && x3:0 - 2 * x5:0 > -2 && x3:0 - 2 * x5:0 = 1 && x4:0 <= x3:0 13.27/4.51 f4717_0_slide93_EQ(x6:0) -> f4717_0_slide93_EQ'(x6:0) :|: x7:0 <= x6:0 && x6:0 - 2 * x8:0 = 0 13.27/4.51 13.27/4.51 ---------------------------------------- 13.27/4.51 13.27/4.51 (29) FilterProof (EQUIVALENT) 13.27/4.51 Used the following sort dictionary for filtering: 13.27/4.51 f4717_0_slide93_EQ(INTEGER) 13.27/4.51 f4717_0_slide93_EQ'(INTEGER) 13.27/4.51 Replaced non-predefined constructor symbols by 0. 13.27/4.51 ---------------------------------------- 13.27/4.51 13.27/4.51 (30) 13.27/4.51 Obligation: 13.27/4.51 Rules: 13.27/4.51 f4717_0_slide93_EQ(x:0) -> f4717_0_slide93_EQ'(x:0) :|: x:0 >= x1:0 && x:0 - 2 * x2:0 = 1 13.27/4.51 f4717_0_slide93_EQ'(x9:0) -> f4717_0_slide93_EQ(x10:0) :|: x9:0 - 2 * x10:0 > -2 && x9:0 - 2 * x10:0 < 2 && x9:0 - 2 * x11:0 < 2 && x9:0 - 2 * x11:0 > -2 && x9:0 - 2 * x11:0 = 0 && x9:0 >= x10:0 13.27/4.51 f4717_0_slide93_EQ'(x3:0) -> f4717_0_slide93_EQ(x4:0) :|: x3:0 - 2 * x4:0 > -2 && x3:0 - 2 * x4:0 < 2 && x3:0 - 2 * x5:0 < 2 && x3:0 - 2 * x5:0 > -2 && x3:0 - 2 * x5:0 = 1 && x4:0 <= x3:0 13.27/4.51 f4717_0_slide93_EQ(x6:0) -> f4717_0_slide93_EQ'(x6:0) :|: x7:0 <= x6:0 && x6:0 - 2 * x8:0 = 0 13.27/4.51 13.27/4.51 ---------------------------------------- 13.27/4.51 13.27/4.51 (31) IntTRSCompressionProof (EQUIVALENT) 13.27/4.51 Compressed rules. 13.27/4.51 ---------------------------------------- 13.27/4.51 13.27/4.51 (32) 13.27/4.51 Obligation: 13.27/4.51 Rules: 13.27/4.51 f4717_0_slide93_EQ(x6:0:0) -> f4717_0_slide93_EQ'(x6:0:0) :|: x7:0:0 <= x6:0:0 && x6:0:0 - 2 * x8:0:0 = 0 13.27/4.51 f4717_0_slide93_EQ(x:0:0) -> f4717_0_slide93_EQ'(x:0:0) :|: x:0:0 >= x1:0:0 && x:0:0 - 2 * x2:0:0 = 1 13.27/4.51 f4717_0_slide93_EQ'(x3:0:0) -> f4717_0_slide93_EQ(x4:0:0) :|: x3:0:0 - 2 * x5:0:0 = 1 && x4:0:0 <= x3:0:0 && x3:0:0 - 2 * x5:0:0 > -2 && x3:0:0 - 2 * x5:0:0 < 2 && x3:0:0 - 2 * x4:0:0 < 2 && x3:0:0 - 2 * x4:0:0 > -2 13.27/4.51 f4717_0_slide93_EQ'(x9:0:0) -> f4717_0_slide93_EQ(x10:0:0) :|: x9:0:0 - 2 * x11:0:0 = 0 && x9:0:0 >= x10:0:0 && x9:0:0 - 2 * x11:0:0 > -2 && x9:0:0 - 2 * x11:0:0 < 2 && x9:0:0 - 2 * x10:0:0 < 2 && x9:0:0 - 2 * x10:0:0 > -2 13.27/4.51 13.27/4.51 ---------------------------------------- 13.27/4.51 13.27/4.51 (33) IntTRSPeriodicNontermProof (COMPLETE) 13.27/4.51 Normalized system to the following form: 13.27/4.51 f(pc, x6:0:0) -> f(2, x6:0:0) :|: pc = 1 && (x7:0:0 <= x6:0:0 && x6:0:0 - 2 * x8:0:0 = 0) 13.27/4.51 f(pc, x:0:0) -> f(2, x:0:0) :|: pc = 1 && (x:0:0 >= x1:0:0 && x:0:0 - 2 * x2:0:0 = 1) 13.27/4.51 f(pc, x3:0:0) -> f(1, x4:0:0) :|: pc = 2 && (x3:0:0 - 2 * x5:0:0 = 1 && x4:0:0 <= x3:0:0 && x3:0:0 - 2 * x5:0:0 > -2 && x3:0:0 - 2 * x5:0:0 < 2 && x3:0:0 - 2 * x4:0:0 < 2 && x3:0:0 - 2 * x4:0:0 > -2) 13.27/4.51 f(pc, x9:0:0) -> f(1, x10:0:0) :|: pc = 2 && (x9:0:0 - 2 * x11:0:0 = 0 && x9:0:0 >= x10:0:0 && x9:0:0 - 2 * x11:0:0 > -2 && x9:0:0 - 2 * x11:0:0 < 2 && x9:0:0 - 2 * x10:0:0 < 2 && x9:0:0 - 2 * x10:0:0 > -2) 13.27/4.51 Witness term starting non-terminating reduction: f(2, 0) 13.27/4.51 ---------------------------------------- 13.27/4.51 13.27/4.51 (34) 13.27/4.51 NO 13.27/4.51 13.27/4.51 ---------------------------------------- 13.27/4.51 13.27/4.51 (35) 13.27/4.51 Obligation: 13.27/4.51 SCC of termination graph based on JBC Program. 13.27/4.51 SCC contains nodes from the following methods: Kernel93.main([Ljava/lang/String;)V 13.27/4.51 SCC calls the following helper methods: 13.27/4.51 Performed SCC analyses: 13.27/4.51 *Used field analysis yielded the following read fields: 13.27/4.51 *Kernel93: [next] 13.27/4.51 *Marker field analysis yielded the following relations that could be markers: 13.27/4.51 13.27/4.51 ---------------------------------------- 13.27/4.51 13.27/4.51 (36) SCCToIRSProof (SOUND) 13.27/4.51 Transformed FIGraph SCCs to intTRSs. Log: 13.27/4.51 Generated rules. Obtained 57 IRulesP rules: 13.27/4.51 f4072_0_slide93_EQ(EOS(STATIC_4072), i370, o1537[Kernel93.next]o1537) -> f4079_0_slide93_Load(EOS(STATIC_4079), i370, o1537[Kernel93.next]o1537) :|: TRUE 13.27/4.51 f4079_0_slide93_Load(EOS(STATIC_4079), i370, o1537[Kernel93.next]o1537) -> f4095_0_slide93_Store(EOS(STATIC_4095), i370, o1537[Kernel93.next]o1537) :|: TRUE 13.27/4.51 f4095_0_slide93_Store(EOS(STATIC_4095), i370, o1537[Kernel93.next]o1537) -> f4107_0_slide93_Load(EOS(STATIC_4107), i370, o1537[Kernel93.next]o1537) :|: TRUE 13.27/4.51 f4107_0_slide93_Load(EOS(STATIC_4107), i370, o1537[Kernel93.next]o1537) -> f4120_0_slide93_InvokeMethod(EOS(STATIC_4120), i370, i370, o1537[Kernel93.next]o1537) :|: TRUE 13.27/4.51 f4120_0_slide93_InvokeMethod(EOS(STATIC_4120), i370, i370, o1537[Kernel93.next]o1537) -> f4127_0_check_Load(EOS(STATIC_4127), i370, i370, o1537[Kernel93.next]o1537) :|: TRUE 13.27/4.51 f4127_0_check_Load(EOS(STATIC_4127), i370, i370, o1537[Kernel93.next]o1537) -> f4145_0_check_ConstantStackPush(EOS(STATIC_4145), i370, i370, o1537[Kernel93.next]o1537) :|: TRUE 13.27/4.51 f4145_0_check_ConstantStackPush(EOS(STATIC_4145), i370, i370, o1537[Kernel93.next]o1537) -> f4152_0_check_IntArithmetic(EOS(STATIC_4152), i370, i370, 2, o1537[Kernel93.next]o1537) :|: TRUE 13.27/4.51 f4152_0_check_IntArithmetic(EOS(STATIC_4152), i370, i370, matching1, o1537[Kernel93.next]o1537) -> f4160_0_check_LE(EOS(STATIC_4160), i370, i370 % 2, o1537[Kernel93.next]o1537) :|: TRUE && matching1 = 2 13.27/4.51 f4160_0_check_LE(EOS(STATIC_4160), i370, matching1, o1537[Kernel93.next]o1537) -> f4163_0_check_LE(EOS(STATIC_4163), i370, 0, o1537[Kernel93.next]o1537) :|: TRUE && matching1 = 0 13.27/4.51 f4160_0_check_LE(EOS(STATIC_4160), i370, matching1, o1537[Kernel93.next]o1537) -> f4164_0_check_LE(EOS(STATIC_4164), i370, 1, o1537[Kernel93.next]o1537) :|: TRUE && matching1 = 1 13.27/4.51 f4163_0_check_LE(EOS(STATIC_4163), i370, matching1, o1537[Kernel93.next]o1537) -> f4167_0_check_ConstantStackPush(EOS(STATIC_4167), i370, o1537[Kernel93.next]o1537) :|: 0 <= 0 && matching1 = 0 13.27/4.51 f4167_0_check_ConstantStackPush(EOS(STATIC_4167), i370, o1537[Kernel93.next]o1537) -> f4171_0_check_Return(EOS(STATIC_4171), i370, 0, o1537[Kernel93.next]o1537) :|: TRUE 13.27/4.51 f4171_0_check_Return(EOS(STATIC_4171), i370, matching1, o1537[Kernel93.next]o1537) -> f4180_0_slide93_EQ(EOS(STATIC_4180), i370, 0, o1537[Kernel93.next]o1537) :|: TRUE && matching1 = 0 13.27/4.51 f4180_0_slide93_EQ(EOS(STATIC_4180), i370, matching1, o1537[Kernel93.next]o1537) -> f4209_0_slide93_Load(EOS(STATIC_4209), i370, o1537[Kernel93.next]o1537) :|: TRUE && matching1 = 0 13.27/4.51 f4209_0_slide93_Load(EOS(STATIC_4209), i370, o1537[Kernel93.next]o1537) -> f4235_0_slide93_Store(EOS(STATIC_4235), i370, o1537[Kernel93.next]o1537) :|: TRUE 13.27/4.51 f4235_0_slide93_Store(EOS(STATIC_4235), i370, o1537[Kernel93.next]o1537) -> f4243_0_slide93_Load(EOS(STATIC_4243), i370, o1537[Kernel93.next]o1537) :|: TRUE 13.27/4.51 f4243_0_slide93_Load(EOS(STATIC_4243), i370, o1537[Kernel93.next]o1537) -> f4256_0_slide93_FieldAccess(EOS(STATIC_4256), i370, o1537[Kernel93.next]o1537) :|: TRUE 13.27/4.51 f4256_0_slide93_FieldAccess(EOS(STATIC_4256), i370, o1726[Kernel93.next]o1726) -> f4258_0_slide93_FieldAccess(EOS(STATIC_4258), i370, o1727[Kernel93.next]o1726) :|: o1727[Kernel93.next]o1726 < o1726[Kernel93.next]o1726 && o1726[Kernel93.next]o1726 >= 0 13.27/4.51 f4258_0_slide93_FieldAccess(EOS(STATIC_4258), i370, o1727[Kernel93.next]o1726) -> f4261_0_slide93_FieldAccess(EOS(STATIC_4261), i370, o1727[Kernel93.next]o1726) :|: o1727[Kernel93.next]o1726 > 0 13.27/4.51 f4261_0_slide93_FieldAccess(EOS(STATIC_4261), i370, o1727[Kernel93.next]o1726) -> f4265_0_slide93_Store(EOS(STATIC_4265), i370, o1727[Kernel93.next]o1726) :|: TRUE 13.27/4.51 f4265_0_slide93_Store(EOS(STATIC_4265), i370, o1727[Kernel93.next]o1726) -> f4269_0_slide93_Load(EOS(STATIC_4269), i370, o1727[Kernel93.next]o1726) :|: TRUE 13.27/4.51 f4269_0_slide93_Load(EOS(STATIC_4269), i370, o1727[Kernel93.next]o1726) -> f4285_0_slide93_ConstantStackPush(EOS(STATIC_4285), i370, o1727[Kernel93.next]o1726) :|: TRUE 13.27/4.51 f4285_0_slide93_ConstantStackPush(EOS(STATIC_4285), i370, o1727[Kernel93.next]o1726) -> f4345_0_slide93_IntArithmetic(EOS(STATIC_4345), i370, 2, o1727[Kernel93.next]o1726) :|: TRUE 13.27/4.51 f4345_0_slide93_IntArithmetic(EOS(STATIC_4345), i370, matching1, o1727[Kernel93.next]o1726) -> f4351_0_slide93_Store(EOS(STATIC_4351), i442, o1727[Kernel93.next]o1726) :|: i442 = i370 / 2 && i442 <= i370 && matching1 = 2 13.27/4.51 f4351_0_slide93_Store(EOS(STATIC_4351), i442, o1727[Kernel93.next]o1726) -> f4410_0_slide93_JMP(EOS(STATIC_4410), i442, o1727[Kernel93.next]o1726) :|: TRUE 13.27/4.51 f4410_0_slide93_JMP(EOS(STATIC_4410), i442, o1727[Kernel93.next]o1726) -> f4427_0_slide93_Load(EOS(STATIC_4427), i442, o1727[Kernel93.next]o1726) :|: TRUE 13.27/4.51 f4427_0_slide93_Load(EOS(STATIC_4427), i442, o1727[Kernel93.next]o1726) -> f4022_0_slide93_Load(EOS(STATIC_4022), i442, o1727[Kernel93.next]o1727) :|: TRUE 13.27/4.51 f4022_0_slide93_Load(EOS(STATIC_4022), i370, o1537[Kernel93.next]o1537) -> f4039_0_slide93_Load(EOS(STATIC_4039), i370, o1537[Kernel93.next]o1537) :|: TRUE 13.27/4.51 f4039_0_slide93_Load(EOS(STATIC_4039), i370, o1537[Kernel93.next]o1537) -> f4064_0_slide93_EQ(EOS(STATIC_4064), i370, o1537[Kernel93.next]o1537) :|: TRUE 13.27/4.51 f4064_0_slide93_EQ(EOS(STATIC_4064), i370, o1537[Kernel93.next]o1537) -> f4072_0_slide93_EQ(EOS(STATIC_4072), i370, o1537[Kernel93.next]o1537) :|: o1537[Kernel93.next]o1537 > 0 13.27/4.51 f4164_0_check_LE(EOS(STATIC_4164), i370, matching1, o1537[Kernel93.next]o1537) -> f4168_0_check_ConstantStackPush(EOS(STATIC_4168), i370, o1537[Kernel93.next]o1537) :|: 1 > 0 && matching1 = 1 13.27/4.51 f4168_0_check_ConstantStackPush(EOS(STATIC_4168), i370, o1537[Kernel93.next]o1537) -> f4172_0_check_JMP(EOS(STATIC_4172), i370, 1, o1537[Kernel93.next]o1537) :|: TRUE 13.27/4.51 f4172_0_check_JMP(EOS(STATIC_4172), i370, matching1, o1537[Kernel93.next]o1537) -> f4187_0_check_Return(EOS(STATIC_4187), i370, 1, o1537[Kernel93.next]o1537) :|: TRUE && matching1 = 1 13.27/4.51 f4187_0_check_Return(EOS(STATIC_4187), i370, matching1, o1537[Kernel93.next]o1537) -> f4213_0_slide93_EQ(EOS(STATIC_4213), i370, 1, o1537[Kernel93.next]o1537) :|: TRUE && matching1 = 1 13.27/4.51 f4213_0_slide93_EQ(EOS(STATIC_4213), i370, matching1, o1537[Kernel93.next]o1537) -> f4240_0_slide93_Load(EOS(STATIC_4240), i370, o1537[Kernel93.next]o1537) :|: 1 > 0 && matching1 = 1 13.27/4.51 f4240_0_slide93_Load(EOS(STATIC_4240), i370, o1537[Kernel93.next]o1537) -> f4255_0_slide93_FieldAccess(EOS(STATIC_4255), i370, o1537[Kernel93.next]o1537) :|: TRUE 13.27/4.51 f4255_0_slide93_FieldAccess(EOS(STATIC_4255), i370, o1724[Kernel93.next]o1724) -> f4257_0_slide93_FieldAccess(EOS(STATIC_4257), i370, o1725[Kernel93.next]o1724) :|: o1725[Kernel93.next]o1724 < o1724[Kernel93.next]o1724 && o1724[Kernel93.next]o1724 >= 0 13.27/4.51 f4257_0_slide93_FieldAccess(EOS(STATIC_4257), i370, o1725[Kernel93.next]o1724) -> f4259_0_slide93_FieldAccess(EOS(STATIC_4259), i370, o1725[Kernel93.next]o1724) :|: o1725[Kernel93.next]o1724 > 0 13.27/4.51 f4259_0_slide93_FieldAccess(EOS(STATIC_4259), i370, o1725[Kernel93.next]o1724) -> f4263_0_slide93_Store(EOS(STATIC_4263), i370, o1725[Kernel93.next]o1724) :|: TRUE 13.27/4.51 f4263_0_slide93_Store(EOS(STATIC_4263), i370, o1725[Kernel93.next]o1724) -> f4267_0_slide93_Load(EOS(STATIC_4267), i370, o1725[Kernel93.next]o1724) :|: TRUE 13.27/4.51 f4267_0_slide93_Load(EOS(STATIC_4267), i370, o1725[Kernel93.next]o1724) -> f4276_0_slide93_Load(EOS(STATIC_4276), i370, o1725[Kernel93.next]o1724) :|: TRUE 13.27/4.51 f4276_0_slide93_Load(EOS(STATIC_4276), i370, o1725[Kernel93.next]o1724) -> f4315_0_slide93_FieldAccess(EOS(STATIC_4315), i370, o1725[Kernel93.next]o1724) :|: TRUE 13.27/4.51 f4315_0_slide93_FieldAccess(EOS(STATIC_4315), i370, o1725[Kernel93.next]o1724) -> f4347_0_slide93_FieldAccess(EOS(STATIC_4347), i370, o1725[Kernel93.next]o1724) :|: TRUE 13.27/4.51 f4347_0_slide93_FieldAccess(EOS(STATIC_4347), i370, o1725[Kernel93.next]o1724) -> f4357_0_slide93_Load(EOS(STATIC_4357), i370) :|: TRUE 13.27/4.51 f4357_0_slide93_Load(EOS(STATIC_4357), i370) -> f4412_0_slide93_Load(EOS(STATIC_4412), i370) :|: TRUE 13.27/4.51 f4412_0_slide93_Load(EOS(STATIC_4412), i370) -> f4430_0_slide93_FieldAccess(EOS(STATIC_4430), i370) :|: TRUE 13.27/4.51 f4430_0_slide93_FieldAccess(EOS(STATIC_4430), i370) -> f4458_0_slide93_JMP(EOS(STATIC_4458), i370) :|: TRUE 13.27/4.51 f4458_0_slide93_JMP(EOS(STATIC_4458), i370) -> f4499_0_slide93_Load(EOS(STATIC_4499), i370) :|: TRUE 13.27/4.51 f4499_0_slide93_Load(EOS(STATIC_4499), i370) -> f4517_0_slide93_FieldAccess(EOS(STATIC_4517), i370) :|: TRUE 13.27/4.51 f4517_0_slide93_FieldAccess(EOS(STATIC_4517), i370) -> f4523_0_slide93_Store(EOS(STATIC_4523), i370) :|: TRUE 13.27/4.51 f4523_0_slide93_Store(EOS(STATIC_4523), i370) -> f4528_0_slide93_Load(EOS(STATIC_4528), i370) :|: TRUE 13.27/4.51 f4528_0_slide93_Load(EOS(STATIC_4528), i370) -> f4536_0_slide93_ConstantStackPush(EOS(STATIC_4536), i370) :|: TRUE 13.27/4.51 f4536_0_slide93_ConstantStackPush(EOS(STATIC_4536), i370) -> f4565_0_slide93_IntArithmetic(EOS(STATIC_4565), i370, 2) :|: TRUE 13.27/4.51 f4565_0_slide93_IntArithmetic(EOS(STATIC_4565), i370, matching1) -> f4590_0_slide93_Store(EOS(STATIC_4590), i490) :|: i490 = i370 / 2 && i490 <= i370 && matching1 = 2 13.27/4.51 f4590_0_slide93_Store(EOS(STATIC_4590), i490) -> f4618_0_slide93_JMP(EOS(STATIC_4618), i490) :|: TRUE 13.27/4.51 f4618_0_slide93_JMP(EOS(STATIC_4618), i490) -> f4634_0_slide93_Load(EOS(STATIC_4634), i490) :|: TRUE 13.27/4.51 f4634_0_slide93_Load(EOS(STATIC_4634), i490) -> f4022_0_slide93_Load(EOS(STATIC_4022), i490, o1724[Kernel93.next]o1724) :|: o1724[Kernel93.next]o1724 = 1 13.27/4.51 Combined rules. Obtained 4 IRulesP rules: 13.27/4.51 f4072_0_slide93_EQ(EOS(STATIC_4072), i370:0, o1537[Kernel93.next]o1537:0) -> f4072_0_slide93_EQ'(EOS(STATIC_4072), i370:0, o1537[Kernel93.next]o1537:0) :|: i370:0 - 2 * div = 1 && o1537[Kernel93.next]o1537:0 > -1 && o1725[Kernel93.next]o1724:0 < o1537[Kernel93.next]o1537:0 && i370:0 >= div1 && o1725[Kernel93.next]o1724:0 > 0 13.27/4.51 f4072_0_slide93_EQ'(EOS(STATIC_4072), i370:0, o1537[Kernel93.next]o1537:0) -> f4072_0_slide93_EQ(EOS(STATIC_4072), div1, 1) :|: i370:0 - 2 * div = 1 && o1537[Kernel93.next]o1537:0 > -1 && o1725[Kernel93.next]o1724:0 < o1537[Kernel93.next]o1537:0 && o1725[Kernel93.next]o1724:0 > 0 && i370:0 >= div1 && i370:0 - 2 * div > -2 && i370:0 - 2 * div < 2 && i370:0 - 2 * div1 < 2 && i370:0 - 2 * div1 > -2 13.27/4.51 f4072_0_slide93_EQ(EOS(STATIC_4072), i370:0, o1537[Kernel93.next]o1537:0) -> f4072_0_slide93_EQ'(EOS(STATIC_4072), i370:0, o1537[Kernel93.next]o1537:0) :|: i370:0 - 2 * div = 0 && o1537[Kernel93.next]o1537:0 > -1 && o1727[Kernel93.next]o1726:0 < o1537[Kernel93.next]o1537:0 && o1727[Kernel93.next]o1726:0 > 0 && o1727[Kernel93.next]o1727:0 > 0 && i370:0 >= div1 13.27/4.51 f4072_0_slide93_EQ'(EOS(STATIC_4072), i370:0, o1537[Kernel93.next]o1537:0) -> f4072_0_slide93_EQ(EOS(STATIC_4072), div1, o1727[Kernel93.next]o1727:0) :|: i370:0 - 2 * div = 0 && o1537[Kernel93.next]o1537:0 > -1 && o1727[Kernel93.next]o1726:0 < o1537[Kernel93.next]o1537:0 && o1727[Kernel93.next]o1726:0 > 0 && i370:0 >= div1 && o1727[Kernel93.next]o1727:0 > 0 && i370:0 - 2 * div > -2 && i370:0 - 2 * div < 2 && i370:0 - 2 * div1 < 2 && i370:0 - 2 * div1 > -2 13.27/4.51 Filtered constant ground arguments: 13.27/4.51 f4072_0_slide93_EQ(x1, x2, x3) -> f4072_0_slide93_EQ(x2, x3) 13.27/4.51 f4072_0_slide93_EQ'(x1, x2, x3) -> f4072_0_slide93_EQ'(x2, x3) 13.27/4.51 EOS(x1) -> EOS 13.27/4.51 Finished conversion. Obtained 4 rules.P rules: 13.27/4.51 f4072_0_slide93_EQ(i370:0, o1537[Kernel93.next]o1537:0) -> f4072_0_slide93_EQ'(i370:0, o1537[Kernel93.next]o1537:0) :|: o1537[Kernel93.next]o1537:0 > -1 && i370:0 - 2 * div = 1 && o1725[Kernel93.next]o1724:0 < o1537[Kernel93.next]o1537:0 && o1725[Kernel93.next]o1724:0 > 0 && i370:0 >= div1 13.27/4.51 f4072_0_slide93_EQ'(i370:0, o1537[Kernel93.next]o1537:0) -> f4072_0_slide93_EQ(div1, 1) :|: o1537[Kernel93.next]o1537:0 > -1 && i370:0 - 2 * div = 1 && o1725[Kernel93.next]o1724:0 < o1537[Kernel93.next]o1537:0 && o1725[Kernel93.next]o1724:0 > 0 && i370:0 >= div1 && i370:0 - 2 * div > -2 && i370:0 - 2 * div < 2 && i370:0 - 2 * div1 > -2 && i370:0 - 2 * div1 < 2 13.27/4.51 f4072_0_slide93_EQ(i370:0, o1537[Kernel93.next]o1537:0) -> f4072_0_slide93_EQ'(i370:0, o1537[Kernel93.next]o1537:0) :|: o1537[Kernel93.next]o1537:0 > -1 && i370:0 - 2 * div = 0 && o1727[Kernel93.next]o1726:0 < o1537[Kernel93.next]o1537:0 && o1727[Kernel93.next]o1726:0 > 0 && i370:0 >= div1 && o1727[Kernel93.next]o1727:0 > 0 13.27/4.51 f4072_0_slide93_EQ'(i370:0, o1537[Kernel93.next]o1537:0) -> f4072_0_slide93_EQ(div1, o1727[Kernel93.next]o1727:0) :|: o1537[Kernel93.next]o1537:0 > -1 && i370:0 - 2 * div = 0 && o1727[Kernel93.next]o1726:0 < o1537[Kernel93.next]o1537:0 && o1727[Kernel93.next]o1726:0 > 0 && i370:0 >= div1 && o1727[Kernel93.next]o1727:0 > 0 && i370:0 - 2 * div > -2 && i370:0 - 2 * div < 2 && i370:0 - 2 * div1 > -2 && i370:0 - 2 * div1 < 2 13.27/4.51 13.27/4.51 ---------------------------------------- 13.27/4.51 13.27/4.51 (37) 13.27/4.51 Obligation: 13.27/4.51 Rules: 13.27/4.51 f4072_0_slide93_EQ(x, x1) -> f4072_0_slide93_EQ'(x, x1) :|: x1 > -1 && x - 2 * x2 = 1 && x3 < x1 && x3 > 0 && x >= x4 13.27/4.51 f4072_0_slide93_EQ'(x5, x6) -> f4072_0_slide93_EQ(x7, 1) :|: x6 > -1 && x5 - 2 * x8 = 1 && x9 < x6 && x9 > 0 && x5 >= x7 && x5 - 2 * x8 > -2 && x5 - 2 * x8 < 2 && x5 - 2 * x7 > -2 && x5 - 2 * x7 < 2 13.27/4.51 f4072_0_slide93_EQ(x10, x11) -> f4072_0_slide93_EQ'(x10, x11) :|: x11 > -1 && x10 - 2 * x12 = 0 && x13 < x11 && x13 > 0 && x10 >= x14 && x15 > 0 13.27/4.51 f4072_0_slide93_EQ'(x16, x17) -> f4072_0_slide93_EQ(x18, x19) :|: x17 > -1 && x16 - 2 * x20 = 0 && x21 < x17 && x21 > 0 && x16 >= x18 && x19 > 0 && x16 - 2 * x20 > -2 && x16 - 2 * x20 < 2 && x16 - 2 * x18 > -2 && x16 - 2 * x18 < 2 13.27/4.51 13.27/4.51 ---------------------------------------- 13.27/4.51 13.27/4.51 (38) IRSFormatTransformerProof (EQUIVALENT) 13.27/4.51 Reformatted IRS to match normalized format (transformed away non-linear left-hand sides, !=, / and %). 13.27/4.51 ---------------------------------------- 13.27/4.51 13.27/4.51 (39) 13.27/4.51 Obligation: 13.27/4.51 Rules: 13.27/4.51 f4072_0_slide93_EQ(x, x1) -> f4072_0_slide93_EQ'(x, x1) :|: x1 > -1 && x - 2 * x2 = 1 && x3 < x1 && x3 > 0 && x >= x4 13.27/4.51 f4072_0_slide93_EQ'(x5, x6) -> f4072_0_slide93_EQ(x7, 1) :|: x6 > -1 && x5 - 2 * x8 = 1 && x9 < x6 && x9 > 0 && x5 >= x7 && x5 - 2 * x8 > -2 && x5 - 2 * x8 < 2 && x5 - 2 * x7 > -2 && x5 - 2 * x7 < 2 13.27/4.51 f4072_0_slide93_EQ(x10, x11) -> f4072_0_slide93_EQ'(x10, x11) :|: x11 > -1 && x10 - 2 * x12 = 0 && x13 < x11 && x13 > 0 && x10 >= x14 && x15 > 0 13.27/4.51 f4072_0_slide93_EQ'(x16, x17) -> f4072_0_slide93_EQ(x18, x19) :|: x17 > -1 && x16 - 2 * x20 = 0 && x21 < x17 && x21 > 0 && x16 >= x18 && x19 > 0 && x16 - 2 * x20 > -2 && x16 - 2 * x20 < 2 && x16 - 2 * x18 > -2 && x16 - 2 * x18 < 2 13.27/4.51 13.27/4.51 ---------------------------------------- 13.27/4.51 13.27/4.51 (40) IRSwTTerminationDigraphProof (EQUIVALENT) 13.27/4.51 Constructed termination digraph! 13.27/4.51 Nodes: 13.27/4.51 (1) f4072_0_slide93_EQ(x, x1) -> f4072_0_slide93_EQ'(x, x1) :|: x1 > -1 && x - 2 * x2 = 1 && x3 < x1 && x3 > 0 && x >= x4 13.27/4.51 (2) f4072_0_slide93_EQ'(x5, x6) -> f4072_0_slide93_EQ(x7, 1) :|: x6 > -1 && x5 - 2 * x8 = 1 && x9 < x6 && x9 > 0 && x5 >= x7 && x5 - 2 * x8 > -2 && x5 - 2 * x8 < 2 && x5 - 2 * x7 > -2 && x5 - 2 * x7 < 2 13.27/4.51 (3) f4072_0_slide93_EQ(x10, x11) -> f4072_0_slide93_EQ'(x10, x11) :|: x11 > -1 && x10 - 2 * x12 = 0 && x13 < x11 && x13 > 0 && x10 >= x14 && x15 > 0 13.27/4.51 (4) f4072_0_slide93_EQ'(x16, x17) -> f4072_0_slide93_EQ(x18, x19) :|: x17 > -1 && x16 - 2 * x20 = 0 && x21 < x17 && x21 > 0 && x16 >= x18 && x19 > 0 && x16 - 2 * x20 > -2 && x16 - 2 * x20 < 2 && x16 - 2 * x18 > -2 && x16 - 2 * x18 < 2 13.27/4.51 13.27/4.51 Arcs: 13.27/4.51 (1) -> (2) 13.27/4.51 (3) -> (4) 13.27/4.51 (4) -> (1), (3) 13.27/4.51 13.27/4.51 This digraph is fully evaluated! 13.27/4.51 ---------------------------------------- 13.27/4.51 13.27/4.51 (41) 13.27/4.51 Obligation: 13.27/4.51 13.27/4.51 Termination digraph: 13.27/4.51 Nodes: 13.27/4.51 (1) f4072_0_slide93_EQ(x10, x11) -> f4072_0_slide93_EQ'(x10, x11) :|: x11 > -1 && x10 - 2 * x12 = 0 && x13 < x11 && x13 > 0 && x10 >= x14 && x15 > 0 13.27/4.51 (2) f4072_0_slide93_EQ'(x16, x17) -> f4072_0_slide93_EQ(x18, x19) :|: x17 > -1 && x16 - 2 * x20 = 0 && x21 < x17 && x21 > 0 && x16 >= x18 && x19 > 0 && x16 - 2 * x20 > -2 && x16 - 2 * x20 < 2 && x16 - 2 * x18 > -2 && x16 - 2 * x18 < 2 13.27/4.51 13.27/4.51 Arcs: 13.27/4.51 (1) -> (2) 13.27/4.51 (2) -> (1) 13.27/4.51 13.27/4.51 This digraph is fully evaluated! 13.27/4.51 13.27/4.51 ---------------------------------------- 13.27/4.51 13.27/4.51 (42) IntTRSCompressionProof (EQUIVALENT) 13.27/4.51 Compressed rules. 13.27/4.51 ---------------------------------------- 13.27/4.51 13.27/4.51 (43) 13.27/4.51 Obligation: 13.27/4.51 Rules: 13.27/4.51 f4072_0_slide93_EQ(x10:0, x11:0) -> f4072_0_slide93_EQ(x18:0, x19:0) :|: x10:0 - 2 * x18:0 < 2 && x15:0 > 0 && x14:0 <= x10:0 && x10:0 - 2 * x18:0 > -2 && x13:0 > 0 && x10:0 - 2 * x20:0 < 2 && x13:0 < x11:0 && x10:0 - 2 * x20:0 > -2 && x10:0 - 2 * x12:0 = 0 && x19:0 > 0 && x18:0 <= x10:0 && x21:0 > 0 && x21:0 < x11:0 && x10:0 - 2 * x20:0 = 0 && x11:0 > -1 13.27/4.51 13.27/4.51 ---------------------------------------- 13.27/4.51 13.27/4.51 (44) FilterProof (EQUIVALENT) 13.27/4.51 Used the following sort dictionary for filtering: 13.27/4.51 f4072_0_slide93_EQ(INTEGER, INTEGER) 13.27/4.51 Replaced non-predefined constructor symbols by 0. 13.27/4.51 ---------------------------------------- 13.27/4.51 13.27/4.51 (45) 13.27/4.51 Obligation: 13.27/4.51 Rules: 13.27/4.51 f4072_0_slide93_EQ(x10:0, x11:0) -> f4072_0_slide93_EQ(x18:0, x19:0) :|: x10:0 - 2 * x18:0 < 2 && x15:0 > 0 && x14:0 <= x10:0 && x10:0 - 2 * x18:0 > -2 && x13:0 > 0 && x10:0 - 2 * x20:0 < 2 && x13:0 < x11:0 && x10:0 - 2 * x20:0 > -2 && x10:0 - 2 * x12:0 = 0 && x19:0 > 0 && x18:0 <= x10:0 && x21:0 > 0 && x21:0 < x11:0 && x10:0 - 2 * x20:0 = 0 && x11:0 > -1 13.27/4.51 13.27/4.51 ---------------------------------------- 13.27/4.51 13.27/4.51 (46) IntTRSCompressionProof (EQUIVALENT) 13.27/4.51 Compressed rules. 13.27/4.51 ---------------------------------------- 13.27/4.51 13.27/4.51 (47) 13.27/4.51 Obligation: 13.27/4.51 Rules: 13.27/4.51 f4072_0_slide93_EQ(x10:0:0, x11:0:0) -> f4072_0_slide93_EQ(x18:0:0, x19:0:0) :|: x10:0:0 - 2 * x20:0:0 = 0 && x11:0:0 > -1 && x21:0:0 < x11:0:0 && x21:0:0 > 0 && x18:0:0 <= x10:0:0 && x19:0:0 > 0 && x10:0:0 - 2 * x12:0:0 = 0 && x10:0:0 - 2 * x20:0:0 > -2 && x13:0:0 < x11:0:0 && x10:0:0 - 2 * x20:0:0 < 2 && x13:0:0 > 0 && x10:0:0 - 2 * x18:0:0 > -2 && x14:0:0 <= x10:0:0 && x15:0:0 > 0 && x10:0:0 - 2 * x18:0:0 < 2 13.27/4.51 13.27/4.51 ---------------------------------------- 13.27/4.51 13.27/4.51 (48) IntTRSPeriodicNontermProof (COMPLETE) 13.27/4.51 Normalized system to the following form: 13.27/4.51 f(pc, x10:0:0, x11:0:0) -> f(1, x18:0:0, x19:0:0) :|: pc = 1 && (x10:0:0 - 2 * x20:0:0 = 0 && x11:0:0 > -1 && x21:0:0 < x11:0:0 && x21:0:0 > 0 && x18:0:0 <= x10:0:0 && x19:0:0 > 0 && x10:0:0 - 2 * x12:0:0 = 0 && x10:0:0 - 2 * x20:0:0 > -2 && x13:0:0 < x11:0:0 && x10:0:0 - 2 * x20:0:0 < 2 && x13:0:0 > 0 && x10:0:0 - 2 * x18:0:0 > -2 && x14:0:0 <= x10:0:0 && x15:0:0 > 0 && x10:0:0 - 2 * x18:0:0 < 2) 13.27/4.51 Witness term starting non-terminating reduction: f(1, 0, 15) 13.27/4.51 ---------------------------------------- 13.27/4.51 13.27/4.51 (49) 13.27/4.51 NO 13.52/4.55 EOF