5.76/2.42 YES 5.76/2.43 proof of /export/starexec/sandbox/benchmark/theBenchmark.jar 5.76/2.43 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 5.76/2.43 5.76/2.43 5.76/2.43 termination of the given Bare JBC problem could be proven: 5.76/2.43 5.76/2.43 (0) Bare JBC problem 5.76/2.43 (1) BareJBCToJBCProof [EQUIVALENT, 95 ms] 5.76/2.43 (2) JBC problem 5.76/2.43 (3) JBCToGraph [EQUIVALENT, 296 ms] 5.76/2.43 (4) JBCTerminationGraph 5.76/2.43 (5) TerminationGraphToSCCProof [SOUND, 0 ms] 5.76/2.43 (6) JBCTerminationSCC 5.76/2.43 (7) SCCToIRSProof [SOUND, 78 ms] 5.76/2.43 (8) IRSwT 5.76/2.43 (9) IRSFormatTransformerProof [EQUIVALENT, 0 ms] 5.76/2.43 (10) IRSwT 5.76/2.43 (11) IRSwTTerminationDigraphProof [EQUIVALENT, 22 ms] 5.76/2.43 (12) IRSwT 5.76/2.43 (13) IntTRSCompressionProof [EQUIVALENT, 0 ms] 5.76/2.43 (14) IRSwT 5.76/2.43 (15) TempFilterProof [SOUND, 42 ms] 5.76/2.43 (16) IntTRS 5.76/2.43 (17) RankingReductionPairProof [EQUIVALENT, 25 ms] 5.76/2.43 (18) YES 5.76/2.43 5.76/2.43 5.76/2.43 ---------------------------------------- 5.76/2.43 5.76/2.43 (0) 5.76/2.43 Obligation: 5.76/2.43 need to prove termination of the following program: 5.76/2.43 /** 5.76/2.43 * Example taken from "A Term Rewriting Approach to the Automated Termination 5.76/2.43 * Analysis of Imperative Programs" (http://www.cs.unm.edu/~spf/papers/2009-02.pdf) 5.76/2.43 * and converted to Java. 5.76/2.43 */ 5.76/2.43 5.76/2.43 public class PastaA4 { 5.76/2.43 public static void main(String[] args) { 5.76/2.43 Random.args = args; 5.76/2.43 int x = Random.random(); 5.76/2.43 int y = Random.random(); 5.76/2.43 5.76/2.43 while (x > y) { 5.76/2.43 y++; 5.76/2.43 } 5.76/2.43 } 5.76/2.43 } 5.76/2.43 5.76/2.43 5.76/2.43 public class Random { 5.76/2.43 static String[] args; 5.76/2.43 static int index = 0; 5.76/2.43 5.76/2.43 public static int random() { 5.76/2.43 String string = args[index]; 5.76/2.43 index++; 5.76/2.43 return string.length(); 5.76/2.43 } 5.76/2.43 } 5.76/2.43 5.76/2.43 5.76/2.43 5.76/2.43 ---------------------------------------- 5.76/2.43 5.76/2.43 (1) BareJBCToJBCProof (EQUIVALENT) 5.76/2.43 initialized classpath 5.76/2.43 ---------------------------------------- 5.76/2.43 5.76/2.43 (2) 5.76/2.43 Obligation: 5.76/2.43 need to prove termination of the following program: 5.76/2.43 /** 5.76/2.43 * Example taken from "A Term Rewriting Approach to the Automated Termination 5.76/2.43 * Analysis of Imperative Programs" (http://www.cs.unm.edu/~spf/papers/2009-02.pdf) 5.76/2.43 * and converted to Java. 5.76/2.43 */ 5.76/2.43 5.76/2.43 public class PastaA4 { 5.76/2.43 public static void main(String[] args) { 5.76/2.43 Random.args = args; 5.76/2.43 int x = Random.random(); 5.76/2.43 int y = Random.random(); 5.76/2.43 5.76/2.43 while (x > y) { 5.76/2.43 y++; 5.76/2.43 } 5.76/2.43 } 5.76/2.43 } 5.76/2.43 5.76/2.43 5.76/2.43 public class Random { 5.76/2.43 static String[] args; 5.76/2.43 static int index = 0; 5.76/2.43 5.76/2.43 public static int random() { 5.76/2.43 String string = args[index]; 5.76/2.43 index++; 5.76/2.43 return string.length(); 5.76/2.43 } 5.76/2.43 } 5.76/2.43 5.76/2.43 5.76/2.43 5.76/2.43 ---------------------------------------- 5.76/2.43 5.76/2.43 (3) JBCToGraph (EQUIVALENT) 5.76/2.43 Constructed TerminationGraph. 5.76/2.43 ---------------------------------------- 5.76/2.43 5.76/2.43 (4) 5.76/2.43 Obligation: 5.76/2.43 Termination Graph based on JBC Program: 5.76/2.43 PastaA4.main([Ljava/lang/String;)V: Graph of 174 nodes with 1 SCC. 5.76/2.43 5.76/2.43 5.76/2.43 5.76/2.43 5.76/2.43 5.76/2.43 ---------------------------------------- 5.76/2.43 5.76/2.43 (5) TerminationGraphToSCCProof (SOUND) 5.76/2.43 Splitted TerminationGraph to 1 SCCs. 5.76/2.43 ---------------------------------------- 5.76/2.43 5.76/2.43 (6) 5.76/2.43 Obligation: 5.76/2.43 SCC of termination graph based on JBC Program. 5.76/2.43 SCC contains nodes from the following methods: PastaA4.main([Ljava/lang/String;)V 5.76/2.43 SCC calls the following helper methods: 5.76/2.43 Performed SCC analyses: 5.76/2.43 *Used field analysis yielded the following read fields: 5.76/2.43 5.76/2.43 *Marker field analysis yielded the following relations that could be markers: 5.76/2.43 5.76/2.43 ---------------------------------------- 5.76/2.43 5.76/2.43 (7) SCCToIRSProof (SOUND) 5.76/2.43 Transformed FIGraph SCCs to intTRSs. Log: 5.76/2.43 Generated rules. Obtained 7 IRulesP rules: 5.76/2.43 f282_0_main_Load(EOS(STATIC_282), i17, i42, i17) -> f285_0_main_LE(EOS(STATIC_285), i17, i42, i17, i42) :|: TRUE 5.76/2.43 f285_0_main_LE(EOS(STATIC_285), i17, i42, i17, i42) -> f290_0_main_LE(EOS(STATIC_290), i17, i42, i17, i42) :|: i17 > i42 5.76/2.43 f290_0_main_LE(EOS(STATIC_290), i17, i42, i17, i42) -> f298_0_main_Inc(EOS(STATIC_298), i17, i42) :|: i17 > i42 5.76/2.43 f298_0_main_Inc(EOS(STATIC_298), i17, i42) -> f307_0_main_JMP(EOS(STATIC_307), i17, i42 + 1) :|: TRUE 5.76/2.43 f307_0_main_JMP(EOS(STATIC_307), i17, i45) -> f327_0_main_Load(EOS(STATIC_327), i17, i45) :|: TRUE 5.76/2.43 f327_0_main_Load(EOS(STATIC_327), i17, i45) -> f279_0_main_Load(EOS(STATIC_279), i17, i45) :|: TRUE 5.76/2.43 f279_0_main_Load(EOS(STATIC_279), i17, i42) -> f282_0_main_Load(EOS(STATIC_282), i17, i42, i17) :|: TRUE 5.76/2.43 Combined rules. Obtained 1 IRulesP rules: 5.76/2.43 f282_0_main_Load(EOS(STATIC_282), i17:0, i42:0, i17:0) -> f282_0_main_Load(EOS(STATIC_282), i17:0, i42:0 + 1, i17:0) :|: i42:0 < i17:0 5.76/2.43 Filtered constant ground arguments: 5.76/2.43 f282_0_main_Load(x1, x2, x3, x4) -> f282_0_main_Load(x2, x3, x4) 5.76/2.43 EOS(x1) -> EOS 5.76/2.43 Filtered duplicate arguments: 5.76/2.43 f282_0_main_Load(x1, x2, x3) -> f282_0_main_Load(x2, x3) 5.76/2.43 Finished conversion. Obtained 1 rules.P rules: 5.76/2.43 f282_0_main_Load(i42:0, i17:0) -> f282_0_main_Load(i42:0 + 1, i17:0) :|: i42:0 < i17:0 5.76/2.43 5.76/2.43 ---------------------------------------- 5.76/2.43 5.76/2.43 (8) 5.76/2.43 Obligation: 5.76/2.43 Rules: 5.76/2.43 f282_0_main_Load(i42:0, i17:0) -> f282_0_main_Load(i42:0 + 1, i17:0) :|: i42:0 < i17:0 5.76/2.43 5.76/2.43 ---------------------------------------- 5.76/2.43 5.76/2.43 (9) IRSFormatTransformerProof (EQUIVALENT) 5.76/2.43 Reformatted IRS to match normalized format (transformed away non-linear left-hand sides, !=, / and %). 5.76/2.43 ---------------------------------------- 5.76/2.43 5.76/2.43 (10) 5.76/2.43 Obligation: 5.76/2.43 Rules: 5.76/2.43 f282_0_main_Load(i42:0, i17:0) -> f282_0_main_Load(arith, i17:0) :|: i42:0 < i17:0 && arith = i42:0 + 1 5.76/2.43 5.76/2.43 ---------------------------------------- 5.76/2.43 5.76/2.43 (11) IRSwTTerminationDigraphProof (EQUIVALENT) 5.76/2.43 Constructed termination digraph! 5.76/2.43 Nodes: 5.76/2.43 (1) f282_0_main_Load(i42:0, i17:0) -> f282_0_main_Load(arith, i17:0) :|: i42:0 < i17:0 && arith = i42:0 + 1 5.76/2.43 5.76/2.43 Arcs: 5.76/2.43 (1) -> (1) 5.76/2.43 5.76/2.43 This digraph is fully evaluated! 5.76/2.43 ---------------------------------------- 5.76/2.43 5.76/2.43 (12) 5.76/2.43 Obligation: 5.76/2.43 5.76/2.43 Termination digraph: 5.76/2.43 Nodes: 5.76/2.43 (1) f282_0_main_Load(i42:0, i17:0) -> f282_0_main_Load(arith, i17:0) :|: i42:0 < i17:0 && arith = i42:0 + 1 5.76/2.43 5.76/2.43 Arcs: 5.76/2.43 (1) -> (1) 5.76/2.43 5.76/2.43 This digraph is fully evaluated! 5.76/2.43 5.76/2.43 ---------------------------------------- 5.76/2.43 5.76/2.43 (13) IntTRSCompressionProof (EQUIVALENT) 5.76/2.43 Compressed rules. 5.76/2.43 ---------------------------------------- 5.76/2.43 5.76/2.43 (14) 5.76/2.43 Obligation: 5.76/2.43 Rules: 5.76/2.43 f282_0_main_Load(i42:0:0, i17:0:0) -> f282_0_main_Load(i42:0:0 + 1, i17:0:0) :|: i42:0:0 < i17:0:0 5.76/2.43 5.76/2.43 ---------------------------------------- 5.76/2.43 5.76/2.43 (15) TempFilterProof (SOUND) 5.76/2.43 Used the following sort dictionary for filtering: 5.76/2.43 f282_0_main_Load(INTEGER, INTEGER) 5.76/2.43 Replaced non-predefined constructor symbols by 0. 5.76/2.43 ---------------------------------------- 5.76/2.43 5.76/2.43 (16) 5.76/2.43 Obligation: 5.76/2.43 Rules: 5.76/2.43 f282_0_main_Load(i42:0:0, i17:0:0) -> f282_0_main_Load(c, i17:0:0) :|: c = i42:0:0 + 1 && i42:0:0 < i17:0:0 5.76/2.43 5.76/2.43 ---------------------------------------- 5.76/2.43 5.76/2.43 (17) RankingReductionPairProof (EQUIVALENT) 5.76/2.43 Interpretation: 5.76/2.43 [ f282_0_main_Load ] = -1*f282_0_main_Load_1 + f282_0_main_Load_2 5.76/2.43 5.76/2.43 The following rules are decreasing: 5.76/2.43 f282_0_main_Load(i42:0:0, i17:0:0) -> f282_0_main_Load(c, i17:0:0) :|: c = i42:0:0 + 1 && i42:0:0 < i17:0:0 5.76/2.43 5.76/2.43 The following rules are bounded: 5.76/2.43 f282_0_main_Load(i42:0:0, i17:0:0) -> f282_0_main_Load(c, i17:0:0) :|: c = i42:0:0 + 1 && i42:0:0 < i17:0:0 5.76/2.43 5.76/2.43 5.76/2.43 ---------------------------------------- 5.76/2.43 5.76/2.43 (18) 5.76/2.43 YES 5.76/2.47 EOF