7.78/2.96 YES 7.78/2.97 proof of /export/starexec/sandbox2/benchmark/theBenchmark.jar 7.78/2.97 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 7.78/2.97 7.78/2.97 7.78/2.97 termination of the given Bare JBC problem could be proven: 7.78/2.97 7.78/2.97 (0) Bare JBC problem 7.78/2.97 (1) BareJBCToJBCProof [EQUIVALENT, 96 ms] 7.78/2.97 (2) JBC problem 7.78/2.97 (3) JBCToGraph [EQUIVALENT, 264 ms] 7.78/2.97 (4) JBCTerminationGraph 7.78/2.97 (5) TerminationGraphToSCCProof [SOUND, 0 ms] 7.78/2.97 (6) JBCTerminationSCC 7.78/2.97 (7) SCCToIRSProof [SOUND, 28 ms] 7.78/2.97 (8) IRSwT 7.78/2.97 (9) IRSFormatTransformerProof [EQUIVALENT, 0 ms] 7.78/2.97 (10) IRSwT 7.78/2.97 (11) IRSwTTerminationDigraphProof [EQUIVALENT, 42 ms] 7.78/2.97 (12) IRSwT 7.78/2.97 (13) IntTRSCompressionProof [EQUIVALENT, 0 ms] 7.78/2.97 (14) IRSwT 7.78/2.97 (15) TempFilterProof [SOUND, 28 ms] 7.78/2.97 (16) IntTRS 7.78/2.97 (17) RankingReductionPairProof [EQUIVALENT, 0 ms] 7.78/2.97 (18) YES 7.78/2.97 7.78/2.97 7.78/2.97 ---------------------------------------- 7.78/2.97 7.78/2.97 (0) 7.78/2.97 Obligation: 7.78/2.97 need to prove termination of the following program: 7.78/2.97 /** 7.78/2.97 * Example taken from "A Term Rewriting Approach to the Automated Termination 7.78/2.97 * Analysis of Imperative Programs" (http://www.cs.unm.edu/~spf/papers/2009-02.pdf) 7.78/2.97 * and converted to Java. 7.78/2.97 */ 7.78/2.97 7.78/2.97 public class PastaC7 { 7.78/2.97 public static void main(String[] args) { 7.78/2.97 Random.args = args; 7.78/2.97 int i = Random.random(); 7.78/2.97 int j = Random.random(); 7.78/2.97 int k = Random.random(); 7.78/2.97 7.78/2.97 while (i <= 100 && j <= k) { 7.78/2.97 int t = i; 7.78/2.97 i = j; 7.78/2.97 j = i + 1; 7.78/2.97 k--; 7.78/2.97 } 7.78/2.97 } 7.78/2.97 } 7.78/2.97 7.78/2.97 7.78/2.97 public class Random { 7.78/2.97 static String[] args; 7.78/2.97 static int index = 0; 7.78/2.97 7.78/2.97 public static int random() { 7.78/2.97 String string = args[index]; 7.78/2.97 index++; 7.78/2.97 return string.length(); 7.78/2.97 } 7.78/2.97 } 7.78/2.97 7.78/2.97 7.78/2.97 7.78/2.97 ---------------------------------------- 7.78/2.97 7.78/2.97 (1) BareJBCToJBCProof (EQUIVALENT) 7.78/2.97 initialized classpath 7.78/2.97 ---------------------------------------- 7.78/2.97 7.78/2.97 (2) 7.78/2.97 Obligation: 7.78/2.97 need to prove termination of the following program: 7.78/2.97 /** 7.78/2.97 * Example taken from "A Term Rewriting Approach to the Automated Termination 7.78/2.97 * Analysis of Imperative Programs" (http://www.cs.unm.edu/~spf/papers/2009-02.pdf) 7.78/2.97 * and converted to Java. 7.78/2.97 */ 7.78/2.97 7.78/2.97 public class PastaC7 { 7.78/2.97 public static void main(String[] args) { 7.78/2.97 Random.args = args; 7.78/2.97 int i = Random.random(); 7.78/2.97 int j = Random.random(); 7.78/2.97 int k = Random.random(); 7.78/2.97 7.78/2.97 while (i <= 100 && j <= k) { 7.78/2.97 int t = i; 7.78/2.97 i = j; 7.78/2.97 j = i + 1; 7.78/2.97 k--; 7.78/2.97 } 7.78/2.97 } 7.78/2.97 } 7.78/2.97 7.78/2.97 7.78/2.97 public class Random { 7.78/2.97 static String[] args; 7.78/2.97 static int index = 0; 7.78/2.97 7.78/2.97 public static int random() { 7.78/2.97 String string = args[index]; 7.78/2.97 index++; 7.78/2.97 return string.length(); 7.78/2.97 } 7.78/2.97 } 7.78/2.97 7.78/2.97 7.78/2.97 7.78/2.97 ---------------------------------------- 7.78/2.97 7.78/2.97 (3) JBCToGraph (EQUIVALENT) 7.78/2.97 Constructed TerminationGraph. 7.78/2.97 ---------------------------------------- 7.78/2.97 7.78/2.97 (4) 7.78/2.97 Obligation: 7.78/2.97 Termination Graph based on JBC Program: 7.78/2.97 PastaC7.main([Ljava/lang/String;)V: Graph of 256 nodes with 1 SCC. 7.78/2.97 7.78/2.97 7.78/2.97 7.78/2.97 7.78/2.97 7.78/2.97 ---------------------------------------- 7.78/2.97 7.78/2.97 (5) TerminationGraphToSCCProof (SOUND) 7.78/2.97 Splitted TerminationGraph to 1 SCCs. 7.78/2.97 ---------------------------------------- 7.78/2.97 7.78/2.97 (6) 7.78/2.97 Obligation: 7.78/2.97 SCC of termination graph based on JBC Program. 7.78/2.97 SCC contains nodes from the following methods: PastaC7.main([Ljava/lang/String;)V 7.78/2.97 SCC calls the following helper methods: 7.78/2.97 Performed SCC analyses: 7.78/2.97 *Used field analysis yielded the following read fields: 7.78/2.97 7.78/2.97 *Marker field analysis yielded the following relations that could be markers: 7.78/2.97 7.78/2.97 ---------------------------------------- 7.78/2.97 7.78/2.97 (7) SCCToIRSProof (SOUND) 7.78/2.97 Transformed FIGraph SCCs to intTRSs. Log: 7.78/2.97 Generated rules. Obtained 19 IRulesP rules: 7.78/2.97 f539_0_main_ConstantStackPush(EOS(STATIC_539), i87, i88, i89, i87) -> f540_0_main_GT(EOS(STATIC_540), i87, i88, i89, i87, 100) :|: TRUE 7.78/2.97 f540_0_main_GT(EOS(STATIC_540), i96, i88, i89, i96, matching1) -> f541_0_main_GT(EOS(STATIC_541), i96, i88, i89, i96, 100) :|: TRUE && matching1 = 100 7.78/2.97 f541_0_main_GT(EOS(STATIC_541), i96, i88, i89, i96, matching1) -> f545_0_main_Load(EOS(STATIC_545), i96, i88, i89) :|: i96 <= 100 && matching1 = 100 7.78/2.97 f545_0_main_Load(EOS(STATIC_545), i96, i88, i89) -> f547_0_main_Load(EOS(STATIC_547), i96, i88, i89, i88) :|: TRUE 7.78/2.97 f547_0_main_Load(EOS(STATIC_547), i96, i88, i89, i88) -> f549_0_main_GT(EOS(STATIC_549), i96, i88, i89, i88, i89) :|: TRUE 7.78/2.97 f549_0_main_GT(EOS(STATIC_549), i96, i88, i89, i88, i89) -> f555_0_main_GT(EOS(STATIC_555), i96, i88, i89, i88, i89) :|: i88 <= i89 7.78/2.97 f555_0_main_GT(EOS(STATIC_555), i96, i88, i89, i88, i89) -> f558_0_main_Load(EOS(STATIC_558), i96, i88, i89) :|: i88 <= i89 7.78/2.97 f558_0_main_Load(EOS(STATIC_558), i96, i88, i89) -> f559_0_main_Store(EOS(STATIC_559), i88, i89, i96) :|: TRUE 7.78/2.97 f559_0_main_Store(EOS(STATIC_559), i88, i89, i96) -> f560_0_main_Load(EOS(STATIC_560), i88, i89) :|: TRUE 7.78/2.97 f560_0_main_Load(EOS(STATIC_560), i88, i89) -> f561_0_main_Store(EOS(STATIC_561), i89, i88) :|: TRUE 7.78/2.97 f561_0_main_Store(EOS(STATIC_561), i89, i88) -> f562_0_main_Load(EOS(STATIC_562), i88, i89) :|: TRUE 7.78/2.97 f562_0_main_Load(EOS(STATIC_562), i88, i89) -> f563_0_main_ConstantStackPush(EOS(STATIC_563), i88, i89, i88) :|: TRUE 7.78/2.97 f563_0_main_ConstantStackPush(EOS(STATIC_563), i88, i89, i88) -> f566_0_main_IntArithmetic(EOS(STATIC_566), i88, i89, i88, 1) :|: TRUE 7.78/2.97 f566_0_main_IntArithmetic(EOS(STATIC_566), i88, i89, i88, matching1) -> f567_0_main_Store(EOS(STATIC_567), i88, i89, i88 + 1) :|: i88 >= 0 && matching1 = 1 7.78/2.97 f567_0_main_Store(EOS(STATIC_567), i88, i89, i101) -> f568_0_main_Inc(EOS(STATIC_568), i88, i101, i89) :|: TRUE 7.78/2.97 f568_0_main_Inc(EOS(STATIC_568), i88, i101, i89) -> f569_0_main_JMP(EOS(STATIC_569), i88, i101, i89 + -1) :|: TRUE 7.78/2.97 f569_0_main_JMP(EOS(STATIC_569), i88, i101, i102) -> f587_0_main_Load(EOS(STATIC_587), i88, i101, i102) :|: TRUE 7.78/2.97 f587_0_main_Load(EOS(STATIC_587), i88, i101, i102) -> f534_0_main_Load(EOS(STATIC_534), i88, i101, i102) :|: TRUE 7.78/2.97 f534_0_main_Load(EOS(STATIC_534), i87, i88, i89) -> f539_0_main_ConstantStackPush(EOS(STATIC_539), i87, i88, i89, i87) :|: TRUE 7.78/2.97 Combined rules. Obtained 1 IRulesP rules: 7.78/2.97 f539_0_main_ConstantStackPush(EOS(STATIC_539), i87:0, i88:0, i89:0, i87:0) -> f539_0_main_ConstantStackPush(EOS(STATIC_539), i88:0, i88:0 + 1, i89:0 - 1, i88:0) :|: i87:0 < 101 && i89:0 >= i88:0 && i88:0 > -1 7.78/2.97 Filtered constant ground arguments: 7.78/2.97 f539_0_main_ConstantStackPush(x1, x2, x3, x4, x5) -> f539_0_main_ConstantStackPush(x2, x3, x4, x5) 7.78/2.97 EOS(x1) -> EOS 7.78/2.97 Filtered duplicate arguments: 7.78/2.97 f539_0_main_ConstantStackPush(x1, x2, x3, x4) -> f539_0_main_ConstantStackPush(x2, x3, x4) 7.78/2.97 Finished conversion. Obtained 1 rules.P rules: 7.78/2.97 f539_0_main_ConstantStackPush(i88:0, i89:0, i87:0) -> f539_0_main_ConstantStackPush(i88:0 + 1, i89:0 - 1, i88:0) :|: i89:0 >= i88:0 && i88:0 > -1 && i87:0 < 101 7.78/2.97 7.78/2.97 ---------------------------------------- 7.78/2.97 7.78/2.97 (8) 7.78/2.97 Obligation: 7.78/2.97 Rules: 7.78/2.97 f539_0_main_ConstantStackPush(i88:0, i89:0, i87:0) -> f539_0_main_ConstantStackPush(i88:0 + 1, i89:0 - 1, i88:0) :|: i89:0 >= i88:0 && i88:0 > -1 && i87:0 < 101 7.78/2.97 7.78/2.97 ---------------------------------------- 7.78/2.97 7.78/2.97 (9) IRSFormatTransformerProof (EQUIVALENT) 7.78/2.97 Reformatted IRS to match normalized format (transformed away non-linear left-hand sides, !=, / and %). 7.78/2.97 ---------------------------------------- 7.78/2.97 7.78/2.97 (10) 7.78/2.97 Obligation: 7.78/2.97 Rules: 7.78/2.97 f539_0_main_ConstantStackPush(i88:0, i89:0, i87:0) -> f539_0_main_ConstantStackPush(arith, arith1, i88:0) :|: i89:0 >= i88:0 && i88:0 > -1 && i87:0 < 101 && arith = i88:0 + 1 && arith1 = i89:0 - 1 7.78/2.97 7.78/2.97 ---------------------------------------- 7.78/2.97 7.78/2.97 (11) IRSwTTerminationDigraphProof (EQUIVALENT) 7.78/2.97 Constructed termination digraph! 7.78/2.97 Nodes: 7.78/2.97 (1) f539_0_main_ConstantStackPush(i88:0, i89:0, i87:0) -> f539_0_main_ConstantStackPush(arith, arith1, i88:0) :|: i89:0 >= i88:0 && i88:0 > -1 && i87:0 < 101 && arith = i88:0 + 1 && arith1 = i89:0 - 1 7.78/2.97 7.78/2.97 Arcs: 7.78/2.97 (1) -> (1) 7.78/2.97 7.78/2.97 This digraph is fully evaluated! 7.78/2.97 ---------------------------------------- 7.78/2.97 7.78/2.97 (12) 7.78/2.97 Obligation: 7.78/2.97 7.78/2.97 Termination digraph: 7.78/2.97 Nodes: 7.78/2.97 (1) f539_0_main_ConstantStackPush(i88:0, i89:0, i87:0) -> f539_0_main_ConstantStackPush(arith, arith1, i88:0) :|: i89:0 >= i88:0 && i88:0 > -1 && i87:0 < 101 && arith = i88:0 + 1 && arith1 = i89:0 - 1 7.78/2.97 7.78/2.97 Arcs: 7.78/2.97 (1) -> (1) 7.78/2.97 7.78/2.97 This digraph is fully evaluated! 7.78/2.97 7.78/2.97 ---------------------------------------- 7.78/2.97 7.78/2.97 (13) IntTRSCompressionProof (EQUIVALENT) 7.78/2.97 Compressed rules. 7.78/2.97 ---------------------------------------- 7.78/2.97 7.78/2.97 (14) 7.78/2.97 Obligation: 7.78/2.97 Rules: 7.78/2.97 f539_0_main_ConstantStackPush(i88:0:0, i89:0:0, i87:0:0) -> f539_0_main_ConstantStackPush(i88:0:0 + 1, i89:0:0 - 1, i88:0:0) :|: i89:0:0 >= i88:0:0 && i88:0:0 > -1 && i87:0:0 < 101 7.78/2.97 7.78/2.97 ---------------------------------------- 7.78/2.97 7.78/2.97 (15) TempFilterProof (SOUND) 7.78/2.97 Used the following sort dictionary for filtering: 7.78/2.97 f539_0_main_ConstantStackPush(INTEGER, INTEGER, INTEGER) 7.78/2.97 Replaced non-predefined constructor symbols by 0. 7.78/2.97 ---------------------------------------- 7.78/2.97 7.78/2.97 (16) 7.78/2.97 Obligation: 7.78/2.97 Rules: 7.78/2.97 f539_0_main_ConstantStackPush(i88:0:0, i89:0:0, i87:0:0) -> f539_0_main_ConstantStackPush(c, c1, i88:0:0) :|: c1 = i89:0:0 - 1 && c = i88:0:0 + 1 && (i89:0:0 >= i88:0:0 && i88:0:0 > -1 && i87:0:0 < 101) 7.78/2.97 7.78/2.97 ---------------------------------------- 7.78/2.97 7.78/2.97 (17) RankingReductionPairProof (EQUIVALENT) 7.78/2.97 Interpretation: 7.78/2.97 [ f539_0_main_ConstantStackPush ] = f539_0_main_ConstantStackPush_2 7.78/2.97 7.78/2.97 The following rules are decreasing: 7.78/2.97 f539_0_main_ConstantStackPush(i88:0:0, i89:0:0, i87:0:0) -> f539_0_main_ConstantStackPush(c, c1, i88:0:0) :|: c1 = i89:0:0 - 1 && c = i88:0:0 + 1 && (i89:0:0 >= i88:0:0 && i88:0:0 > -1 && i87:0:0 < 101) 7.78/2.97 7.78/2.97 The following rules are bounded: 7.78/2.97 f539_0_main_ConstantStackPush(i88:0:0, i89:0:0, i87:0:0) -> f539_0_main_ConstantStackPush(c, c1, i88:0:0) :|: c1 = i89:0:0 - 1 && c = i88:0:0 + 1 && (i89:0:0 >= i88:0:0 && i88:0:0 > -1 && i87:0:0 < 101) 7.78/2.97 7.78/2.97 7.78/2.97 ---------------------------------------- 7.78/2.97 7.78/2.97 (18) 7.78/2.97 YES 7.78/3.02 EOF