8.00/3.11 YES 8.00/3.11 proof of /export/starexec/sandbox/benchmark/theBenchmark.jar 8.00/3.11 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 8.00/3.11 8.00/3.11 8.00/3.11 termination of the given Bare JBC problem could be proven: 8.00/3.11 8.00/3.11 (0) Bare JBC problem 8.00/3.11 (1) BareJBCToJBCProof [EQUIVALENT, 96 ms] 8.00/3.11 (2) JBC problem 8.00/3.11 (3) JBCToGraph [EQUIVALENT, 329 ms] 8.00/3.11 (4) JBCTerminationGraph 8.00/3.11 (5) TerminationGraphToSCCProof [SOUND, 0 ms] 8.00/3.11 (6) JBCTerminationSCC 8.00/3.11 (7) SCCToIRSProof [SOUND, 14 ms] 8.00/3.11 (8) IRSwT 8.00/3.11 (9) IRSFormatTransformerProof [EQUIVALENT, 0 ms] 8.00/3.11 (10) IRSwT 8.00/3.11 (11) IRSwTTerminationDigraphProof [EQUIVALENT, 0 ms] 8.00/3.11 (12) IRSwT 8.00/3.11 (13) IntTRSCompressionProof [EQUIVALENT, 0 ms] 8.00/3.11 (14) IRSwT 8.00/3.11 (15) TempFilterProof [SOUND, 18 ms] 8.00/3.11 (16) IntTRS 8.00/3.11 (17) PolynomialOrderProcessor [EQUIVALENT, 0 ms] 8.00/3.11 (18) YES 8.00/3.11 8.00/3.11 8.00/3.11 ---------------------------------------- 8.00/3.11 8.00/3.11 (0) 8.00/3.11 Obligation: 8.00/3.11 need to prove termination of the following program: 8.00/3.11 /** 8.00/3.11 * Example taken from "A Term Rewriting Approach to the Automated Termination 8.00/3.11 * Analysis of Imperative Programs" (http://www.cs.unm.edu/~spf/papers/2009-02.pdf) 8.00/3.11 * and converted to Java. 8.00/3.11 */ 8.00/3.11 8.00/3.11 public class PastaA7 { 8.00/3.11 public static void main(String[] args) { 8.00/3.11 Random.args = args; 8.00/3.11 int x = Random.random(); 8.00/3.11 int y = Random.random(); 8.00/3.11 int z = Random.random(); 8.00/3.11 8.00/3.11 while (x > y && x > z) { 8.00/3.11 y++; 8.00/3.11 z++; 8.00/3.11 } 8.00/3.11 } 8.00/3.11 } 8.00/3.11 8.00/3.11 8.00/3.11 public class Random { 8.00/3.11 static String[] args; 8.00/3.11 static int index = 0; 8.00/3.11 8.00/3.11 public static int random() { 8.00/3.11 String string = args[index]; 8.00/3.11 index++; 8.00/3.11 return string.length(); 8.00/3.11 } 8.00/3.11 } 8.00/3.11 8.00/3.11 8.00/3.11 8.00/3.11 ---------------------------------------- 8.00/3.11 8.00/3.11 (1) BareJBCToJBCProof (EQUIVALENT) 8.00/3.11 initialized classpath 8.00/3.11 ---------------------------------------- 8.00/3.11 8.00/3.11 (2) 8.00/3.11 Obligation: 8.00/3.11 need to prove termination of the following program: 8.00/3.11 /** 8.00/3.11 * Example taken from "A Term Rewriting Approach to the Automated Termination 8.00/3.11 * Analysis of Imperative Programs" (http://www.cs.unm.edu/~spf/papers/2009-02.pdf) 8.00/3.11 * and converted to Java. 8.00/3.11 */ 8.00/3.11 8.00/3.11 public class PastaA7 { 8.00/3.11 public static void main(String[] args) { 8.00/3.11 Random.args = args; 8.00/3.11 int x = Random.random(); 8.00/3.11 int y = Random.random(); 8.00/3.11 int z = Random.random(); 8.00/3.11 8.00/3.11 while (x > y && x > z) { 8.00/3.11 y++; 8.00/3.11 z++; 8.00/3.11 } 8.00/3.11 } 8.00/3.11 } 8.00/3.11 8.00/3.11 8.00/3.11 public class Random { 8.00/3.11 static String[] args; 8.00/3.11 static int index = 0; 8.00/3.11 8.00/3.11 public static int random() { 8.00/3.11 String string = args[index]; 8.00/3.11 index++; 8.00/3.11 return string.length(); 8.00/3.11 } 8.00/3.11 } 8.00/3.11 8.00/3.11 8.00/3.11 8.00/3.11 ---------------------------------------- 8.00/3.11 8.00/3.11 (3) JBCToGraph (EQUIVALENT) 8.00/3.11 Constructed TerminationGraph. 8.00/3.11 ---------------------------------------- 8.00/3.11 8.00/3.11 (4) 8.00/3.11 Obligation: 8.00/3.11 Termination Graph based on JBC Program: 8.00/3.11 PastaA7.main([Ljava/lang/String;)V: Graph of 248 nodes with 1 SCC. 8.00/3.11 8.00/3.11 8.00/3.11 8.00/3.11 8.00/3.11 8.00/3.11 ---------------------------------------- 8.00/3.11 8.00/3.11 (5) TerminationGraphToSCCProof (SOUND) 8.00/3.11 Splitted TerminationGraph to 1 SCCs. 8.00/3.11 ---------------------------------------- 8.00/3.11 8.00/3.11 (6) 8.00/3.11 Obligation: 8.00/3.11 SCC of termination graph based on JBC Program. 8.00/3.11 SCC contains nodes from the following methods: PastaA7.main([Ljava/lang/String;)V 8.00/3.11 SCC calls the following helper methods: 8.00/3.11 Performed SCC analyses: 8.00/3.11 *Used field analysis yielded the following read fields: 8.00/3.11 8.00/3.11 *Marker field analysis yielded the following relations that could be markers: 8.00/3.11 8.00/3.11 ---------------------------------------- 8.00/3.11 8.00/3.11 (7) SCCToIRSProof (SOUND) 8.00/3.11 Transformed FIGraph SCCs to intTRSs. Log: 8.00/3.11 Generated rules. Obtained 12 IRulesP rules: 8.00/3.11 f416_0_main_Load(EOS(STATIC_416), i19, i48, i71, i19) -> f419_0_main_LE(EOS(STATIC_419), i19, i48, i71, i19, i48) :|: TRUE 8.00/3.11 f419_0_main_LE(EOS(STATIC_419), i19, i48, i71, i19, i48) -> f423_0_main_LE(EOS(STATIC_423), i19, i48, i71, i19, i48) :|: i19 > i48 8.00/3.11 f423_0_main_LE(EOS(STATIC_423), i19, i48, i71, i19, i48) -> f445_0_main_Load(EOS(STATIC_445), i19, i48, i71) :|: i19 > i48 8.00/3.11 f445_0_main_Load(EOS(STATIC_445), i19, i48, i71) -> f450_0_main_Load(EOS(STATIC_450), i19, i48, i71, i19) :|: TRUE 8.00/3.11 f450_0_main_Load(EOS(STATIC_450), i19, i48, i71, i19) -> f456_0_main_LE(EOS(STATIC_456), i19, i48, i71, i19, i71) :|: TRUE 8.00/3.11 f456_0_main_LE(EOS(STATIC_456), i19, i48, i71, i19, i71) -> f475_0_main_LE(EOS(STATIC_475), i19, i48, i71, i19, i71) :|: i19 > i71 8.00/3.11 f475_0_main_LE(EOS(STATIC_475), i19, i48, i71, i19, i71) -> f489_0_main_Inc(EOS(STATIC_489), i19, i48, i71) :|: i19 > i71 8.00/3.11 f489_0_main_Inc(EOS(STATIC_489), i19, i48, i71) -> f494_0_main_Inc(EOS(STATIC_494), i19, i48 + 1, i71) :|: TRUE 8.00/3.11 f494_0_main_Inc(EOS(STATIC_494), i19, i75, i71) -> f498_0_main_JMP(EOS(STATIC_498), i19, i75, i71 + 1) :|: TRUE 8.00/3.11 f498_0_main_JMP(EOS(STATIC_498), i19, i75, i76) -> f515_0_main_Load(EOS(STATIC_515), i19, i75, i76) :|: TRUE 8.00/3.11 f515_0_main_Load(EOS(STATIC_515), i19, i75, i76) -> f413_0_main_Load(EOS(STATIC_413), i19, i75, i76) :|: TRUE 8.00/3.11 f413_0_main_Load(EOS(STATIC_413), i19, i48, i71) -> f416_0_main_Load(EOS(STATIC_416), i19, i48, i71, i19) :|: TRUE 8.00/3.11 Combined rules. Obtained 1 IRulesP rules: 8.00/3.11 f416_0_main_Load(EOS(STATIC_416), i19:0, i48:0, i71:0, i19:0) -> f416_0_main_Load(EOS(STATIC_416), i19:0, i48:0 + 1, i71:0 + 1, i19:0) :|: i48:0 < i19:0 && i71:0 < i19:0 8.00/3.11 Filtered constant ground arguments: 8.00/3.11 f416_0_main_Load(x1, x2, x3, x4, x5) -> f416_0_main_Load(x2, x3, x4, x5) 8.00/3.11 EOS(x1) -> EOS 8.00/3.11 Filtered duplicate arguments: 8.00/3.11 f416_0_main_Load(x1, x2, x3, x4) -> f416_0_main_Load(x2, x3, x4) 8.00/3.11 Finished conversion. Obtained 1 rules.P rules: 8.00/3.11 f416_0_main_Load(i48:0, i71:0, i19:0) -> f416_0_main_Load(i48:0 + 1, i71:0 + 1, i19:0) :|: i48:0 < i19:0 && i71:0 < i19:0 8.00/3.11 8.00/3.11 ---------------------------------------- 8.00/3.11 8.00/3.11 (8) 8.00/3.11 Obligation: 8.00/3.11 Rules: 8.00/3.11 f416_0_main_Load(i48:0, i71:0, i19:0) -> f416_0_main_Load(i48:0 + 1, i71:0 + 1, i19:0) :|: i48:0 < i19:0 && i71:0 < i19:0 8.00/3.11 8.00/3.11 ---------------------------------------- 8.00/3.11 8.00/3.11 (9) IRSFormatTransformerProof (EQUIVALENT) 8.00/3.11 Reformatted IRS to match normalized format (transformed away non-linear left-hand sides, !=, / and %). 8.00/3.11 ---------------------------------------- 8.00/3.11 8.00/3.11 (10) 8.00/3.11 Obligation: 8.00/3.11 Rules: 8.00/3.11 f416_0_main_Load(i48:0, i71:0, i19:0) -> f416_0_main_Load(arith, arith1, i19:0) :|: i48:0 < i19:0 && i71:0 < i19:0 && arith = i48:0 + 1 && arith1 = i71:0 + 1 8.00/3.11 8.00/3.11 ---------------------------------------- 8.00/3.11 8.00/3.11 (11) IRSwTTerminationDigraphProof (EQUIVALENT) 8.00/3.11 Constructed termination digraph! 8.00/3.11 Nodes: 8.00/3.11 (1) f416_0_main_Load(i48:0, i71:0, i19:0) -> f416_0_main_Load(arith, arith1, i19:0) :|: i48:0 < i19:0 && i71:0 < i19:0 && arith = i48:0 + 1 && arith1 = i71:0 + 1 8.00/3.11 8.00/3.11 Arcs: 8.00/3.11 (1) -> (1) 8.00/3.11 8.00/3.11 This digraph is fully evaluated! 8.00/3.11 ---------------------------------------- 8.00/3.11 8.00/3.11 (12) 8.00/3.11 Obligation: 8.00/3.11 8.00/3.11 Termination digraph: 8.00/3.11 Nodes: 8.00/3.11 (1) f416_0_main_Load(i48:0, i71:0, i19:0) -> f416_0_main_Load(arith, arith1, i19:0) :|: i48:0 < i19:0 && i71:0 < i19:0 && arith = i48:0 + 1 && arith1 = i71:0 + 1 8.00/3.11 8.00/3.11 Arcs: 8.00/3.11 (1) -> (1) 8.00/3.11 8.00/3.11 This digraph is fully evaluated! 8.00/3.11 8.00/3.11 ---------------------------------------- 8.00/3.11 8.00/3.11 (13) IntTRSCompressionProof (EQUIVALENT) 8.00/3.11 Compressed rules. 8.00/3.11 ---------------------------------------- 8.00/3.11 8.00/3.11 (14) 8.00/3.11 Obligation: 8.00/3.11 Rules: 8.00/3.11 f416_0_main_Load(i48:0:0, i71:0:0, i19:0:0) -> f416_0_main_Load(i48:0:0 + 1, i71:0:0 + 1, i19:0:0) :|: i48:0:0 < i19:0:0 && i71:0:0 < i19:0:0 8.00/3.11 8.00/3.11 ---------------------------------------- 8.00/3.11 8.00/3.11 (15) TempFilterProof (SOUND) 8.00/3.11 Used the following sort dictionary for filtering: 8.00/3.11 f416_0_main_Load(INTEGER, INTEGER, INTEGER) 8.00/3.11 Replaced non-predefined constructor symbols by 0. 8.00/3.11 ---------------------------------------- 8.00/3.11 8.00/3.11 (16) 8.00/3.11 Obligation: 8.00/3.11 Rules: 8.00/3.11 f416_0_main_Load(i48:0:0, i71:0:0, i19:0:0) -> f416_0_main_Load(c, c1, i19:0:0) :|: c1 = i71:0:0 + 1 && c = i48:0:0 + 1 && (i48:0:0 < i19:0:0 && i71:0:0 < i19:0:0) 8.00/3.11 8.00/3.11 ---------------------------------------- 8.00/3.11 8.00/3.11 (17) PolynomialOrderProcessor (EQUIVALENT) 8.00/3.11 Found the following polynomial interpretation: 8.00/3.11 [f416_0_main_Load(x, x1, x2)] = -x1 + x2 8.00/3.11 8.00/3.11 The following rules are decreasing: 8.00/3.11 f416_0_main_Load(i48:0:0, i71:0:0, i19:0:0) -> f416_0_main_Load(c, c1, i19:0:0) :|: c1 = i71:0:0 + 1 && c = i48:0:0 + 1 && (i48:0:0 < i19:0:0 && i71:0:0 < i19:0:0) 8.00/3.11 The following rules are bounded: 8.00/3.11 f416_0_main_Load(i48:0:0, i71:0:0, i19:0:0) -> f416_0_main_Load(c, c1, i19:0:0) :|: c1 = i71:0:0 + 1 && c = i48:0:0 + 1 && (i48:0:0 < i19:0:0 && i71:0:0 < i19:0:0) 8.00/3.11 8.00/3.11 ---------------------------------------- 8.00/3.11 8.00/3.11 (18) 8.00/3.11 YES 8.11/3.16 EOF