7.04/2.66 YES 7.04/2.68 proof of /export/starexec/sandbox2/benchmark/theBenchmark.jar 7.04/2.68 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 7.04/2.68 7.04/2.68 7.04/2.68 termination of the given Bare JBC problem could be proven: 7.04/2.68 7.04/2.68 (0) Bare JBC problem 7.04/2.68 (1) BareJBCToJBCProof [EQUIVALENT, 96 ms] 7.04/2.68 (2) JBC problem 7.04/2.68 (3) JBCToGraph [EQUIVALENT, 335 ms] 7.04/2.68 (4) JBCTerminationGraph 7.04/2.68 (5) TerminationGraphToSCCProof [SOUND, 2 ms] 7.04/2.68 (6) JBCTerminationSCC 7.04/2.68 (7) SCCToIRSProof [SOUND, 102 ms] 7.04/2.68 (8) IRSwT 7.04/2.68 (9) IRSFormatTransformerProof [EQUIVALENT, 0 ms] 7.04/2.68 (10) IRSwT 7.04/2.68 (11) IRSwTTerminationDigraphProof [EQUIVALENT, 30 ms] 7.04/2.68 (12) IRSwT 7.04/2.68 (13) IntTRSCompressionProof [EQUIVALENT, 0 ms] 7.04/2.68 (14) IRSwT 7.04/2.68 (15) TempFilterProof [SOUND, 55 ms] 7.04/2.68 (16) IntTRS 7.04/2.68 (17) RankingReductionPairProof [EQUIVALENT, 0 ms] 7.04/2.68 (18) IntTRS 7.04/2.68 (19) RankingReductionPairProof [EQUIVALENT, 0 ms] 7.04/2.68 (20) YES 7.04/2.68 7.04/2.68 7.04/2.68 ---------------------------------------- 7.04/2.68 7.04/2.68 (0) 7.04/2.68 Obligation: 7.04/2.68 need to prove termination of the following program: 7.04/2.68 /** 7.04/2.68 * Example taken from "A Term Rewriting Approach to the Automated Termination 7.04/2.68 * Analysis of Imperative Programs" (http://www.cs.unm.edu/~spf/papers/2009-02.pdf) 7.04/2.68 * and converted to Java. 7.04/2.68 */ 7.04/2.68 7.04/2.68 public class PastaC2 { 7.04/2.68 public static void main(String[] args) { 7.04/2.68 Random.args = args; 7.04/2.68 int x = Random.random(); 7.04/2.68 7.04/2.68 while (x >= 0) { 7.04/2.68 x = x+1; 7.04/2.68 int y = 1; 7.04/2.68 while (x >= y) { 7.04/2.68 y++; 7.04/2.68 } 7.04/2.68 x = x-2; 7.04/2.68 } 7.04/2.68 } 7.04/2.68 } 7.04/2.68 7.04/2.68 7.04/2.68 public class Random { 7.04/2.68 static String[] args; 7.04/2.68 static int index = 0; 7.04/2.68 7.04/2.68 public static int random() { 7.04/2.68 String string = args[index]; 7.04/2.68 index++; 7.04/2.68 return string.length(); 7.04/2.68 } 7.04/2.68 } 7.04/2.68 7.04/2.68 7.04/2.68 7.04/2.68 ---------------------------------------- 7.04/2.68 7.04/2.68 (1) BareJBCToJBCProof (EQUIVALENT) 7.04/2.68 initialized classpath 7.04/2.68 ---------------------------------------- 7.04/2.68 7.04/2.68 (2) 7.04/2.68 Obligation: 7.04/2.68 need to prove termination of the following program: 7.04/2.68 /** 7.04/2.68 * Example taken from "A Term Rewriting Approach to the Automated Termination 7.04/2.68 * Analysis of Imperative Programs" (http://www.cs.unm.edu/~spf/papers/2009-02.pdf) 7.04/2.68 * and converted to Java. 7.04/2.68 */ 7.04/2.68 7.04/2.68 public class PastaC2 { 7.04/2.68 public static void main(String[] args) { 7.04/2.68 Random.args = args; 7.04/2.68 int x = Random.random(); 7.04/2.68 7.04/2.68 while (x >= 0) { 7.04/2.68 x = x+1; 7.04/2.68 int y = 1; 7.04/2.68 while (x >= y) { 7.04/2.68 y++; 7.04/2.68 } 7.04/2.68 x = x-2; 7.04/2.68 } 7.04/2.68 } 7.04/2.68 } 7.04/2.68 7.04/2.68 7.04/2.68 public class Random { 7.04/2.68 static String[] args; 7.04/2.68 static int index = 0; 7.04/2.68 7.04/2.68 public static int random() { 7.04/2.68 String string = args[index]; 7.04/2.68 index++; 7.04/2.68 return string.length(); 7.04/2.68 } 7.04/2.68 } 7.04/2.68 7.04/2.68 7.04/2.68 7.04/2.68 ---------------------------------------- 7.04/2.68 7.04/2.68 (3) JBCToGraph (EQUIVALENT) 7.04/2.68 Constructed TerminationGraph. 7.04/2.68 ---------------------------------------- 7.04/2.68 7.04/2.68 (4) 7.04/2.68 Obligation: 7.04/2.68 Termination Graph based on JBC Program: 7.04/2.68 PastaC2.main([Ljava/lang/String;)V: Graph of 127 nodes with 1 SCC. 7.04/2.68 7.04/2.68 7.04/2.68 7.04/2.68 7.04/2.68 7.04/2.68 ---------------------------------------- 7.04/2.68 7.04/2.68 (5) TerminationGraphToSCCProof (SOUND) 7.04/2.68 Splitted TerminationGraph to 1 SCCs. 7.04/2.68 ---------------------------------------- 7.04/2.68 7.04/2.68 (6) 7.04/2.68 Obligation: 7.04/2.68 SCC of termination graph based on JBC Program. 7.04/2.68 SCC contains nodes from the following methods: PastaC2.main([Ljava/lang/String;)V 7.04/2.68 SCC calls the following helper methods: 7.04/2.68 Performed SCC analyses: 7.04/2.68 *Used field analysis yielded the following read fields: 7.04/2.68 7.04/2.68 *Marker field analysis yielded the following relations that could be markers: 7.04/2.68 7.04/2.68 ---------------------------------------- 7.04/2.68 7.04/2.68 (7) SCCToIRSProof (SOUND) 7.04/2.68 Transformed FIGraph SCCs to intTRSs. Log: 7.04/2.68 Generated rules. Obtained 27 IRulesP rules: 7.04/2.68 f761_0_main_LT(EOS(STATIC_761), i49, i49) -> f765_0_main_LT(EOS(STATIC_765), i49, i49) :|: TRUE 7.04/2.68 f765_0_main_LT(EOS(STATIC_765), i49, i49) -> f768_0_main_Load(EOS(STATIC_768), i49) :|: i49 >= 0 7.04/2.68 f768_0_main_Load(EOS(STATIC_768), i49) -> f770_0_main_ConstantStackPush(EOS(STATIC_770), i49) :|: TRUE 7.04/2.68 f770_0_main_ConstantStackPush(EOS(STATIC_770), i49) -> f772_0_main_IntArithmetic(EOS(STATIC_772), i49, 1) :|: TRUE 7.04/2.68 f772_0_main_IntArithmetic(EOS(STATIC_772), i49, matching1) -> f774_0_main_Store(EOS(STATIC_774), i49 + 1) :|: i49 >= 0 && matching1 = 1 7.04/2.68 f774_0_main_Store(EOS(STATIC_774), i50) -> f777_0_main_ConstantStackPush(EOS(STATIC_777), i50) :|: TRUE 7.04/2.68 f777_0_main_ConstantStackPush(EOS(STATIC_777), i50) -> f779_0_main_Store(EOS(STATIC_779), i50, 1) :|: TRUE 7.04/2.68 f779_0_main_Store(EOS(STATIC_779), i50, matching1) -> f781_0_main_Load(EOS(STATIC_781), i50, 1) :|: TRUE && matching1 = 1 7.04/2.68 f781_0_main_Load(EOS(STATIC_781), i50, matching1) -> f805_0_main_Load(EOS(STATIC_805), i50, 1) :|: TRUE && matching1 = 1 7.04/2.68 f805_0_main_Load(EOS(STATIC_805), i50, i52) -> f845_0_main_Load(EOS(STATIC_845), i50, i52) :|: TRUE 7.04/2.68 f845_0_main_Load(EOS(STATIC_845), i50, i55) -> f890_0_main_Load(EOS(STATIC_890), i50, i55) :|: TRUE 7.04/2.68 f890_0_main_Load(EOS(STATIC_890), i50, i58) -> f891_0_main_Load(EOS(STATIC_891), i50, i58, i50) :|: TRUE 7.04/2.68 f891_0_main_Load(EOS(STATIC_891), i50, i58, i50) -> f892_0_main_LT(EOS(STATIC_892), i50, i58, i50, i58) :|: TRUE 7.04/2.68 f892_0_main_LT(EOS(STATIC_892), i50, i58, i50, i58) -> f902_0_main_LT(EOS(STATIC_902), i50, i58, i50, i58) :|: i50 < i58 7.04/2.68 f892_0_main_LT(EOS(STATIC_892), i50, i58, i50, i58) -> f903_0_main_LT(EOS(STATIC_903), i50, i58, i50, i58) :|: i50 >= i58 7.04/2.68 f902_0_main_LT(EOS(STATIC_902), i50, i58, i50, i58) -> f909_0_main_Load(EOS(STATIC_909), i50) :|: i50 < i58 7.04/2.68 f909_0_main_Load(EOS(STATIC_909), i50) -> f911_0_main_ConstantStackPush(EOS(STATIC_911), i50) :|: TRUE 7.04/2.68 f911_0_main_ConstantStackPush(EOS(STATIC_911), i50) -> f914_0_main_IntArithmetic(EOS(STATIC_914), i50, 2) :|: TRUE 7.04/2.68 f914_0_main_IntArithmetic(EOS(STATIC_914), i50, matching1) -> f923_0_main_Store(EOS(STATIC_923), i50 - 2) :|: i50 > 0 && matching1 = 2 7.04/2.68 f923_0_main_Store(EOS(STATIC_923), i63) -> f925_0_main_JMP(EOS(STATIC_925), i63) :|: TRUE 7.04/2.68 f925_0_main_JMP(EOS(STATIC_925), i63) -> f932_0_main_Load(EOS(STATIC_932), i63) :|: TRUE 7.04/2.68 f932_0_main_Load(EOS(STATIC_932), i63) -> f757_0_main_Load(EOS(STATIC_757), i63) :|: TRUE 7.04/2.68 f757_0_main_Load(EOS(STATIC_757), i47) -> f761_0_main_LT(EOS(STATIC_761), i47, i47) :|: TRUE 7.04/2.68 f903_0_main_LT(EOS(STATIC_903), i50, i58, i50, i58) -> f910_0_main_Inc(EOS(STATIC_910), i50, i58) :|: i50 >= i58 7.04/2.68 f910_0_main_Inc(EOS(STATIC_910), i50, i58) -> f912_0_main_JMP(EOS(STATIC_912), i50, i58 + 1) :|: TRUE 7.04/2.68 f912_0_main_JMP(EOS(STATIC_912), i50, i61) -> f921_0_main_Load(EOS(STATIC_921), i50, i61) :|: TRUE 7.04/2.68 f921_0_main_Load(EOS(STATIC_921), i50, i61) -> f890_0_main_Load(EOS(STATIC_890), i50, i61) :|: TRUE 7.04/2.68 Combined rules. Obtained 2 IRulesP rules: 7.04/2.68 f892_0_main_LT(EOS(STATIC_892), i50:0, i58:0, i50:0, i58:0) -> f892_0_main_LT(EOS(STATIC_892), i50:0 - 1, 1, i50:0 - 1, 1) :|: i50:0 > 1 && i58:0 > i50:0 7.04/2.68 f892_0_main_LT(EOS(STATIC_892), i50:0, i58:0, i50:0, i58:0) -> f892_0_main_LT(EOS(STATIC_892), i50:0, i58:0 + 1, i50:0, i58:0 + 1) :|: i58:0 <= i50:0 7.04/2.68 Filtered constant ground arguments: 7.04/2.68 f892_0_main_LT(x1, x2, x3, x4, x5) -> f892_0_main_LT(x2, x3, x4, x5) 7.04/2.68 EOS(x1) -> EOS 7.04/2.68 Filtered duplicate arguments: 7.04/2.68 f892_0_main_LT(x1, x2, x3, x4) -> f892_0_main_LT(x3, x4) 7.04/2.68 Finished conversion. Obtained 2 rules.P rules: 7.04/2.68 f892_0_main_LT(i50:0, i58:0) -> f892_0_main_LT(i50:0 - 1, 1) :|: i50:0 > 1 && i58:0 > i50:0 7.04/2.68 f892_0_main_LT(i50:0, i58:0) -> f892_0_main_LT(i50:0, i58:0 + 1) :|: i58:0 <= i50:0 7.04/2.68 7.04/2.68 ---------------------------------------- 7.04/2.68 7.04/2.68 (8) 7.04/2.68 Obligation: 7.04/2.68 Rules: 7.04/2.68 f892_0_main_LT(i50:0, i58:0) -> f892_0_main_LT(i50:0 - 1, 1) :|: i50:0 > 1 && i58:0 > i50:0 7.04/2.68 f892_0_main_LT(x, x1) -> f892_0_main_LT(x, x1 + 1) :|: x1 <= x 7.04/2.68 7.04/2.68 ---------------------------------------- 7.04/2.68 7.04/2.68 (9) IRSFormatTransformerProof (EQUIVALENT) 7.04/2.68 Reformatted IRS to match normalized format (transformed away non-linear left-hand sides, !=, / and %). 7.04/2.68 ---------------------------------------- 7.04/2.68 7.04/2.68 (10) 7.04/2.68 Obligation: 7.04/2.68 Rules: 7.04/2.68 f892_0_main_LT(i50:0, i58:0) -> f892_0_main_LT(arith, 1) :|: i50:0 > 1 && i58:0 > i50:0 && arith = i50:0 - 1 7.04/2.68 f892_0_main_LT(x2, x3) -> f892_0_main_LT(x2, x4) :|: x3 <= x2 && x4 = x3 + 1 7.04/2.68 7.04/2.68 ---------------------------------------- 7.04/2.68 7.04/2.68 (11) IRSwTTerminationDigraphProof (EQUIVALENT) 7.04/2.68 Constructed termination digraph! 7.04/2.68 Nodes: 7.04/2.68 (1) f892_0_main_LT(i50:0, i58:0) -> f892_0_main_LT(arith, 1) :|: i50:0 > 1 && i58:0 > i50:0 && arith = i50:0 - 1 7.04/2.68 (2) f892_0_main_LT(x2, x3) -> f892_0_main_LT(x2, x4) :|: x3 <= x2 && x4 = x3 + 1 7.04/2.68 7.04/2.68 Arcs: 7.04/2.68 (1) -> (2) 7.04/2.68 (2) -> (1), (2) 7.04/2.68 7.04/2.68 This digraph is fully evaluated! 7.04/2.68 ---------------------------------------- 7.04/2.68 7.04/2.68 (12) 7.04/2.68 Obligation: 7.04/2.68 7.04/2.68 Termination digraph: 7.04/2.68 Nodes: 7.04/2.68 (1) f892_0_main_LT(i50:0, i58:0) -> f892_0_main_LT(arith, 1) :|: i50:0 > 1 && i58:0 > i50:0 && arith = i50:0 - 1 7.04/2.68 (2) f892_0_main_LT(x2, x3) -> f892_0_main_LT(x2, x4) :|: x3 <= x2 && x4 = x3 + 1 7.04/2.68 7.04/2.68 Arcs: 7.04/2.68 (1) -> (2) 7.04/2.68 (2) -> (1), (2) 7.04/2.68 7.04/2.68 This digraph is fully evaluated! 7.04/2.68 7.04/2.68 ---------------------------------------- 7.04/2.68 7.04/2.68 (13) IntTRSCompressionProof (EQUIVALENT) 7.04/2.68 Compressed rules. 7.04/2.68 ---------------------------------------- 7.04/2.68 7.04/2.68 (14) 7.04/2.68 Obligation: 7.04/2.68 Rules: 7.04/2.68 f892_0_main_LT(i50:0:0, i58:0:0) -> f892_0_main_LT(i50:0:0 - 1, 1) :|: i50:0:0 > 1 && i58:0:0 > i50:0:0 7.04/2.68 f892_0_main_LT(x2:0, x3:0) -> f892_0_main_LT(x2:0, x3:0 + 1) :|: x3:0 <= x2:0 7.04/2.68 7.04/2.68 ---------------------------------------- 7.04/2.68 7.04/2.68 (15) TempFilterProof (SOUND) 7.04/2.68 Used the following sort dictionary for filtering: 7.04/2.68 f892_0_main_LT(INTEGER, VARIABLE) 7.04/2.68 Replaced non-predefined constructor symbols by 0. 7.04/2.68 ---------------------------------------- 7.04/2.68 7.04/2.68 (16) 7.04/2.68 Obligation: 7.04/2.68 Rules: 7.04/2.68 f892_0_main_LT(i50:0:0, i58:0:0) -> f892_0_main_LT(c, c1) :|: c1 = 1 && c = i50:0:0 - 1 && (i50:0:0 > 1 && i58:0:0 > i50:0:0) 7.04/2.68 f892_0_main_LT(x2:0, x3:0) -> f892_0_main_LT(x2:0, c2) :|: c2 = x3:0 + 1 && x3:0 <= x2:0 7.04/2.68 7.04/2.68 ---------------------------------------- 7.04/2.68 7.04/2.68 (17) RankingReductionPairProof (EQUIVALENT) 7.04/2.68 Interpretation: 7.04/2.68 [ f892_0_main_LT ] = f892_0_main_LT_1 7.04/2.68 7.04/2.68 The following rules are decreasing: 7.04/2.68 f892_0_main_LT(i50:0:0, i58:0:0) -> f892_0_main_LT(c, c1) :|: c1 = 1 && c = i50:0:0 - 1 && (i50:0:0 > 1 && i58:0:0 > i50:0:0) 7.04/2.68 7.04/2.68 The following rules are bounded: 7.04/2.68 f892_0_main_LT(i50:0:0, i58:0:0) -> f892_0_main_LT(c, c1) :|: c1 = 1 && c = i50:0:0 - 1 && (i50:0:0 > 1 && i58:0:0 > i50:0:0) 7.04/2.68 7.04/2.68 7.04/2.68 ---------------------------------------- 7.04/2.68 7.04/2.68 (18) 7.04/2.68 Obligation: 7.04/2.68 Rules: 7.04/2.68 f892_0_main_LT(x2:0, x3:0) -> f892_0_main_LT(x2:0, c2) :|: c2 = x3:0 + 1 && x3:0 <= x2:0 7.04/2.68 7.04/2.68 ---------------------------------------- 7.04/2.68 7.04/2.68 (19) RankingReductionPairProof (EQUIVALENT) 7.04/2.68 Interpretation: 7.04/2.68 [ f892_0_main_LT ] = -1*f892_0_main_LT_2 + f892_0_main_LT_1 7.04/2.68 7.04/2.68 The following rules are decreasing: 7.04/2.68 f892_0_main_LT(x2:0, x3:0) -> f892_0_main_LT(x2:0, c2) :|: c2 = x3:0 + 1 && x3:0 <= x2:0 7.04/2.68 7.04/2.68 The following rules are bounded: 7.04/2.68 f892_0_main_LT(x2:0, x3:0) -> f892_0_main_LT(x2:0, c2) :|: c2 = x3:0 + 1 && x3:0 <= x2:0 7.04/2.68 7.04/2.68 7.04/2.68 ---------------------------------------- 7.04/2.68 7.04/2.68 (20) 7.04/2.68 YES 7.23/2.78 EOF