5.83/2.52 YES 5.83/2.53 proof of /export/starexec/sandbox/benchmark/theBenchmark.jar 5.83/2.53 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 5.83/2.53 5.83/2.53 5.83/2.53 termination of the given Bare JBC problem could be proven: 5.83/2.53 5.83/2.53 (0) Bare JBC problem 5.83/2.53 (1) BareJBCToJBCProof [EQUIVALENT, 96 ms] 5.83/2.53 (2) JBC problem 5.83/2.53 (3) JBCToGraph [EQUIVALENT, 288 ms] 5.83/2.53 (4) JBCTerminationGraph 5.83/2.53 (5) TerminationGraphToSCCProof [SOUND, 0 ms] 5.83/2.53 (6) JBCTerminationSCC 5.83/2.53 (7) SCCToIRSProof [SOUND, 40 ms] 5.83/2.53 (8) IRSwT 5.83/2.53 (9) IRSFormatTransformerProof [EQUIVALENT, 0 ms] 5.83/2.53 (10) IRSwT 5.83/2.53 (11) IRSwTTerminationDigraphProof [EQUIVALENT, 16 ms] 5.83/2.53 (12) IRSwT 5.83/2.53 (13) IntTRSCompressionProof [EQUIVALENT, 0 ms] 5.83/2.53 (14) IRSwT 5.83/2.53 (15) TempFilterProof [SOUND, 16 ms] 5.83/2.53 (16) IntTRS 5.83/2.53 (17) PolynomialOrderProcessor [EQUIVALENT, 0 ms] 5.83/2.53 (18) YES 5.83/2.53 5.83/2.53 5.83/2.53 ---------------------------------------- 5.83/2.53 5.83/2.53 (0) 5.83/2.53 Obligation: 5.83/2.53 need to prove termination of the following program: 5.83/2.53 /** 5.83/2.53 * Example taken from "A Term Rewriting Approach to the Automated Termination 5.83/2.53 * Analysis of Imperative Programs" (http://www.cs.unm.edu/~spf/papers/2009-02.pdf) 5.83/2.53 * and converted to Java. 5.83/2.53 */ 5.83/2.53 5.83/2.53 public class PastaA5 { 5.83/2.53 public static void main(String[] args) { 5.83/2.53 Random.args = args; 5.83/2.53 int x = Random.random(); 5.83/2.53 int y = Random.random(); 5.83/2.53 5.83/2.53 while (x >= y + 1) { 5.83/2.53 y++; 5.83/2.53 } 5.83/2.53 } 5.83/2.53 } 5.83/2.53 5.83/2.53 5.83/2.53 public class Random { 5.83/2.53 static String[] args; 5.83/2.53 static int index = 0; 5.83/2.53 5.83/2.53 public static int random() { 5.83/2.53 String string = args[index]; 5.83/2.53 index++; 5.83/2.53 return string.length(); 5.83/2.53 } 5.83/2.53 } 5.83/2.53 5.83/2.53 5.83/2.53 5.83/2.53 ---------------------------------------- 5.83/2.53 5.83/2.53 (1) BareJBCToJBCProof (EQUIVALENT) 5.83/2.53 initialized classpath 5.83/2.53 ---------------------------------------- 5.83/2.53 5.83/2.53 (2) 5.83/2.53 Obligation: 5.83/2.53 need to prove termination of the following program: 5.83/2.53 /** 5.83/2.53 * Example taken from "A Term Rewriting Approach to the Automated Termination 5.83/2.53 * Analysis of Imperative Programs" (http://www.cs.unm.edu/~spf/papers/2009-02.pdf) 5.83/2.53 * and converted to Java. 5.83/2.53 */ 5.83/2.53 5.83/2.53 public class PastaA5 { 5.83/2.53 public static void main(String[] args) { 5.83/2.53 Random.args = args; 5.83/2.53 int x = Random.random(); 5.83/2.53 int y = Random.random(); 5.83/2.53 5.83/2.53 while (x >= y + 1) { 5.83/2.53 y++; 5.83/2.53 } 5.83/2.53 } 5.83/2.53 } 5.83/2.53 5.83/2.53 5.83/2.53 public class Random { 5.83/2.53 static String[] args; 5.83/2.53 static int index = 0; 5.83/2.53 5.83/2.53 public static int random() { 5.83/2.53 String string = args[index]; 5.83/2.53 index++; 5.83/2.53 return string.length(); 5.83/2.53 } 5.83/2.53 } 5.83/2.53 5.83/2.53 5.83/2.53 5.83/2.53 ---------------------------------------- 5.83/2.53 5.83/2.53 (3) JBCToGraph (EQUIVALENT) 5.83/2.53 Constructed TerminationGraph. 5.83/2.53 ---------------------------------------- 5.83/2.53 5.83/2.53 (4) 5.83/2.53 Obligation: 5.83/2.53 Termination Graph based on JBC Program: 5.83/2.53 PastaA5.main([Ljava/lang/String;)V: Graph of 176 nodes with 1 SCC. 5.83/2.53 5.83/2.53 5.83/2.53 5.83/2.53 5.83/2.53 5.83/2.53 ---------------------------------------- 5.83/2.53 5.83/2.53 (5) TerminationGraphToSCCProof (SOUND) 5.83/2.53 Splitted TerminationGraph to 1 SCCs. 5.83/2.53 ---------------------------------------- 5.83/2.53 5.83/2.53 (6) 5.83/2.53 Obligation: 5.83/2.53 SCC of termination graph based on JBC Program. 5.83/2.53 SCC contains nodes from the following methods: PastaA5.main([Ljava/lang/String;)V 5.83/2.53 SCC calls the following helper methods: 5.83/2.53 Performed SCC analyses: 5.83/2.53 *Used field analysis yielded the following read fields: 5.83/2.53 5.83/2.53 *Marker field analysis yielded the following relations that could be markers: 5.83/2.53 5.83/2.53 ---------------------------------------- 5.83/2.53 5.83/2.53 (7) SCCToIRSProof (SOUND) 5.83/2.53 Transformed FIGraph SCCs to intTRSs. Log: 5.83/2.53 Generated rules. Obtained 9 IRulesP rules: 5.83/2.53 f288_0_main_Load(EOS(STATIC_288), i19, i43, i19) -> f291_0_main_ConstantStackPush(EOS(STATIC_291), i19, i43, i19, i43) :|: TRUE 5.83/2.53 f291_0_main_ConstantStackPush(EOS(STATIC_291), i19, i43, i19, i43) -> f293_0_main_IntArithmetic(EOS(STATIC_293), i19, i43, i19, i43, 1) :|: TRUE 5.83/2.53 f293_0_main_IntArithmetic(EOS(STATIC_293), i19, i43, i19, i43, matching1) -> f296_0_main_LT(EOS(STATIC_296), i19, i43, i19, i43 + 1) :|: i43 >= 0 && matching1 = 1 5.83/2.53 f296_0_main_LT(EOS(STATIC_296), i19, i43, i19, i45) -> f302_0_main_LT(EOS(STATIC_302), i19, i43, i19, i45) :|: i19 >= i45 5.83/2.53 f302_0_main_LT(EOS(STATIC_302), i19, i43, i19, i45) -> f313_0_main_Inc(EOS(STATIC_313), i19, i43) :|: i19 >= i45 5.83/2.53 f313_0_main_Inc(EOS(STATIC_313), i19, i43) -> f318_0_main_JMP(EOS(STATIC_318), i19, i43 + 1) :|: TRUE 5.83/2.53 f318_0_main_JMP(EOS(STATIC_318), i19, i47) -> f338_0_main_Load(EOS(STATIC_338), i19, i47) :|: TRUE 5.83/2.53 f338_0_main_Load(EOS(STATIC_338), i19, i47) -> f285_0_main_Load(EOS(STATIC_285), i19, i47) :|: TRUE 5.83/2.53 f285_0_main_Load(EOS(STATIC_285), i19, i43) -> f288_0_main_Load(EOS(STATIC_288), i19, i43, i19) :|: TRUE 5.83/2.53 Combined rules. Obtained 1 IRulesP rules: 5.83/2.53 f288_0_main_Load(EOS(STATIC_288), i19:0, i43:0, i19:0) -> f288_0_main_Load(EOS(STATIC_288), i19:0, i43:0 + 1, i19:0) :|: i43:0 > -1 && i43:0 + 1 <= i19:0 5.83/2.53 Filtered constant ground arguments: 5.83/2.53 f288_0_main_Load(x1, x2, x3, x4) -> f288_0_main_Load(x2, x3, x4) 5.83/2.53 EOS(x1) -> EOS 5.83/2.53 Filtered duplicate arguments: 5.83/2.53 f288_0_main_Load(x1, x2, x3) -> f288_0_main_Load(x2, x3) 5.83/2.53 Finished conversion. Obtained 1 rules.P rules: 5.83/2.53 f288_0_main_Load(i43:0, i19:0) -> f288_0_main_Load(i43:0 + 1, i19:0) :|: i43:0 > -1 && i43:0 + 1 <= i19:0 5.83/2.53 5.83/2.53 ---------------------------------------- 5.83/2.53 5.83/2.53 (8) 5.83/2.53 Obligation: 5.83/2.53 Rules: 5.83/2.53 f288_0_main_Load(i43:0, i19:0) -> f288_0_main_Load(i43:0 + 1, i19:0) :|: i43:0 > -1 && i43:0 + 1 <= i19:0 5.83/2.53 5.83/2.53 ---------------------------------------- 5.83/2.53 5.83/2.53 (9) IRSFormatTransformerProof (EQUIVALENT) 5.83/2.53 Reformatted IRS to match normalized format (transformed away non-linear left-hand sides, !=, / and %). 5.83/2.53 ---------------------------------------- 5.83/2.53 5.83/2.53 (10) 5.83/2.53 Obligation: 5.83/2.53 Rules: 5.83/2.53 f288_0_main_Load(i43:0, i19:0) -> f288_0_main_Load(arith, i19:0) :|: i43:0 > -1 && i43:0 + 1 <= i19:0 && arith = i43:0 + 1 5.83/2.53 5.83/2.53 ---------------------------------------- 5.83/2.53 5.83/2.53 (11) IRSwTTerminationDigraphProof (EQUIVALENT) 5.83/2.53 Constructed termination digraph! 5.83/2.53 Nodes: 5.83/2.53 (1) f288_0_main_Load(i43:0, i19:0) -> f288_0_main_Load(arith, i19:0) :|: i43:0 > -1 && i43:0 + 1 <= i19:0 && arith = i43:0 + 1 5.83/2.53 5.83/2.53 Arcs: 5.83/2.53 (1) -> (1) 5.83/2.53 5.83/2.53 This digraph is fully evaluated! 5.83/2.53 ---------------------------------------- 5.83/2.53 5.83/2.53 (12) 5.83/2.53 Obligation: 5.83/2.53 5.83/2.53 Termination digraph: 5.83/2.53 Nodes: 5.83/2.53 (1) f288_0_main_Load(i43:0, i19:0) -> f288_0_main_Load(arith, i19:0) :|: i43:0 > -1 && i43:0 + 1 <= i19:0 && arith = i43:0 + 1 5.83/2.53 5.83/2.53 Arcs: 5.83/2.53 (1) -> (1) 5.83/2.53 5.83/2.53 This digraph is fully evaluated! 5.83/2.53 5.83/2.53 ---------------------------------------- 5.83/2.53 5.83/2.53 (13) IntTRSCompressionProof (EQUIVALENT) 5.83/2.53 Compressed rules. 5.83/2.53 ---------------------------------------- 5.83/2.53 5.83/2.53 (14) 5.83/2.53 Obligation: 5.83/2.53 Rules: 5.83/2.53 f288_0_main_Load(i43:0:0, i19:0:0) -> f288_0_main_Load(i43:0:0 + 1, i19:0:0) :|: i43:0:0 > -1 && i43:0:0 + 1 <= i19:0:0 5.83/2.53 5.83/2.53 ---------------------------------------- 5.83/2.53 5.83/2.53 (15) TempFilterProof (SOUND) 5.83/2.53 Used the following sort dictionary for filtering: 5.83/2.53 f288_0_main_Load(INTEGER, INTEGER) 5.83/2.53 Replaced non-predefined constructor symbols by 0. 5.83/2.53 ---------------------------------------- 5.83/2.53 5.83/2.53 (16) 5.83/2.53 Obligation: 5.83/2.53 Rules: 5.83/2.53 f288_0_main_Load(i43:0:0, i19:0:0) -> f288_0_main_Load(c, i19:0:0) :|: c = i43:0:0 + 1 && (i43:0:0 > -1 && i43:0:0 + 1 <= i19:0:0) 5.83/2.53 5.83/2.53 ---------------------------------------- 5.83/2.53 5.83/2.53 (17) PolynomialOrderProcessor (EQUIVALENT) 5.83/2.53 Found the following polynomial interpretation: 5.83/2.53 [f288_0_main_Load(x, x1)] = -x + x1 5.83/2.53 5.83/2.53 The following rules are decreasing: 5.83/2.53 f288_0_main_Load(i43:0:0, i19:0:0) -> f288_0_main_Load(c, i19:0:0) :|: c = i43:0:0 + 1 && (i43:0:0 > -1 && i43:0:0 + 1 <= i19:0:0) 5.83/2.53 The following rules are bounded: 5.83/2.53 f288_0_main_Load(i43:0:0, i19:0:0) -> f288_0_main_Load(c, i19:0:0) :|: c = i43:0:0 + 1 && (i43:0:0 > -1 && i43:0:0 + 1 <= i19:0:0) 5.83/2.53 5.83/2.53 ---------------------------------------- 5.83/2.53 5.83/2.53 (18) 5.83/2.53 YES 6.02/2.58 EOF