9.97/3.54 YES 9.97/3.57 proof of /export/starexec/sandbox/benchmark/theBenchmark.jar 9.97/3.57 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 9.97/3.57 9.97/3.57 9.97/3.57 termination of the given Bare JBC problem could be proven: 9.97/3.57 9.97/3.57 (0) Bare JBC problem 9.97/3.57 (1) BareJBCToJBCProof [EQUIVALENT, 96 ms] 9.97/3.57 (2) JBC problem 9.97/3.57 (3) JBCToGraph [EQUIVALENT, 364 ms] 9.97/3.57 (4) JBCTerminationGraph 9.97/3.57 (5) TerminationGraphToSCCProof [SOUND, 0 ms] 9.97/3.57 (6) JBCTerminationSCC 9.97/3.57 (7) SCCToIRSProof [SOUND, 103 ms] 9.97/3.57 (8) IRSwT 9.97/3.57 (9) IRSFormatTransformerProof [EQUIVALENT, 0 ms] 9.97/3.57 (10) IRSwT 9.97/3.57 (11) IRSwTTerminationDigraphProof [EQUIVALENT, 65 ms] 9.97/3.57 (12) AND 9.97/3.57 (13) IRSwT 9.97/3.57 (14) IntTRSCompressionProof [EQUIVALENT, 0 ms] 9.97/3.57 (15) IRSwT 9.97/3.57 (16) TempFilterProof [SOUND, 41 ms] 9.97/3.57 (17) IntTRS 9.97/3.57 (18) PolynomialOrderProcessor [EQUIVALENT, 14 ms] 9.97/3.57 (19) YES 9.97/3.57 (20) IRSwT 9.97/3.57 (21) IntTRSCompressionProof [EQUIVALENT, 0 ms] 9.97/3.57 (22) IRSwT 9.97/3.57 (23) TempFilterProof [SOUND, 24 ms] 9.97/3.57 (24) IntTRS 9.97/3.57 (25) RankingReductionPairProof [EQUIVALENT, 2 ms] 9.97/3.57 (26) IntTRS 9.97/3.57 (27) PolynomialOrderProcessor [EQUIVALENT, 0 ms] 9.97/3.57 (28) YES 9.97/3.57 9.97/3.57 9.97/3.57 ---------------------------------------- 9.97/3.57 9.97/3.57 (0) 9.97/3.57 Obligation: 9.97/3.57 need to prove termination of the following program: 9.97/3.57 /** 9.97/3.57 * Example taken from "A Term Rewriting Approach to the Automated Termination 9.97/3.57 * Analysis of Imperative Programs" (http://www.cs.unm.edu/~spf/papers/2009-02.pdf) 9.97/3.57 * and converted to Java. 9.97/3.57 */ 9.97/3.57 9.97/3.57 public class PastaB11 { 9.97/3.57 public static void main(String[] args) { 9.97/3.57 Random.args = args; 9.97/3.57 int x = Random.random(); 9.97/3.57 int y = Random.random(); 9.97/3.57 9.97/3.57 while (x + y > 0) { 9.97/3.57 if (x > y) { 9.97/3.57 x--; 9.97/3.57 } else if (x == y) { 9.97/3.57 x--; 9.97/3.57 } else { 9.97/3.57 y--; 9.97/3.57 } 9.97/3.57 } 9.97/3.57 } 9.97/3.57 } 9.97/3.57 9.97/3.57 9.97/3.57 public class Random { 9.97/3.57 static String[] args; 9.97/3.57 static int index = 0; 9.97/3.57 9.97/3.57 public static int random() { 9.97/3.57 String string = args[index]; 9.97/3.57 index++; 9.97/3.57 return string.length(); 9.97/3.57 } 9.97/3.57 } 9.97/3.57 9.97/3.57 9.97/3.57 9.97/3.57 ---------------------------------------- 9.97/3.57 9.97/3.57 (1) BareJBCToJBCProof (EQUIVALENT) 9.97/3.57 initialized classpath 9.97/3.57 ---------------------------------------- 9.97/3.57 9.97/3.57 (2) 9.97/3.57 Obligation: 9.97/3.57 need to prove termination of the following program: 9.97/3.57 /** 9.97/3.57 * Example taken from "A Term Rewriting Approach to the Automated Termination 9.97/3.57 * Analysis of Imperative Programs" (http://www.cs.unm.edu/~spf/papers/2009-02.pdf) 9.97/3.57 * and converted to Java. 9.97/3.57 */ 9.97/3.57 9.97/3.57 public class PastaB11 { 9.97/3.57 public static void main(String[] args) { 9.97/3.57 Random.args = args; 9.97/3.57 int x = Random.random(); 9.97/3.57 int y = Random.random(); 9.97/3.57 9.97/3.57 while (x + y > 0) { 9.97/3.57 if (x > y) { 9.97/3.57 x--; 9.97/3.57 } else if (x == y) { 9.97/3.57 x--; 9.97/3.57 } else { 9.97/3.57 y--; 9.97/3.57 } 9.97/3.57 } 9.97/3.57 } 9.97/3.57 } 9.97/3.57 9.97/3.57 9.97/3.57 public class Random { 9.97/3.57 static String[] args; 9.97/3.57 static int index = 0; 9.97/3.57 9.97/3.57 public static int random() { 9.97/3.57 String string = args[index]; 9.97/3.57 index++; 9.97/3.57 return string.length(); 9.97/3.57 } 9.97/3.57 } 9.97/3.57 9.97/3.57 9.97/3.57 9.97/3.57 ---------------------------------------- 9.97/3.57 9.97/3.57 (3) JBCToGraph (EQUIVALENT) 9.97/3.57 Constructed TerminationGraph. 9.97/3.57 ---------------------------------------- 9.97/3.57 9.97/3.57 (4) 9.97/3.57 Obligation: 9.97/3.57 Termination Graph based on JBC Program: 9.97/3.57 PastaB11.main([Ljava/lang/String;)V: Graph of 197 nodes with 1 SCC. 9.97/3.57 9.97/3.57 9.97/3.57 9.97/3.57 9.97/3.57 9.97/3.57 ---------------------------------------- 9.97/3.57 9.97/3.57 (5) TerminationGraphToSCCProof (SOUND) 9.97/3.57 Splitted TerminationGraph to 1 SCCs. 9.97/3.57 ---------------------------------------- 9.97/3.57 9.97/3.57 (6) 9.97/3.57 Obligation: 9.97/3.57 SCC of termination graph based on JBC Program. 9.97/3.57 SCC contains nodes from the following methods: PastaB11.main([Ljava/lang/String;)V 9.97/3.57 SCC calls the following helper methods: 9.97/3.57 Performed SCC analyses: 9.97/3.57 *Used field analysis yielded the following read fields: 9.97/3.57 9.97/3.57 *Marker field analysis yielded the following relations that could be markers: 9.97/3.57 9.97/3.57 ---------------------------------------- 9.97/3.57 9.97/3.57 (7) SCCToIRSProof (SOUND) 9.97/3.57 Transformed FIGraph SCCs to intTRSs. Log: 9.97/3.57 Generated rules. Obtained 26 IRulesP rules: 9.97/3.57 f881_0_main_Load(EOS(STATIC_881), i176, i157, i176) -> f882_0_main_IntArithmetic(EOS(STATIC_882), i176, i157, i176, i157) :|: TRUE 9.97/3.57 f882_0_main_IntArithmetic(EOS(STATIC_882), i176, i157, i176, i157) -> f883_0_main_LE(EOS(STATIC_883), i176, i157, i176 + i157) :|: TRUE 9.97/3.57 f883_0_main_LE(EOS(STATIC_883), i176, i157, i184) -> f885_0_main_LE(EOS(STATIC_885), i176, i157, i184) :|: TRUE 9.97/3.57 f885_0_main_LE(EOS(STATIC_885), i176, i157, i184) -> f887_0_main_Load(EOS(STATIC_887), i176, i157) :|: i184 > 0 9.97/3.57 f887_0_main_Load(EOS(STATIC_887), i176, i157) -> f890_0_main_Load(EOS(STATIC_890), i176, i157, i176) :|: TRUE 9.97/3.57 f890_0_main_Load(EOS(STATIC_890), i176, i157, i176) -> f891_0_main_LE(EOS(STATIC_891), i176, i157, i176, i157) :|: TRUE 9.97/3.57 f891_0_main_LE(EOS(STATIC_891), i176, i157, i176, i157) -> f892_0_main_LE(EOS(STATIC_892), i176, i157, i176, i157) :|: i176 <= i157 9.97/3.57 f891_0_main_LE(EOS(STATIC_891), i176, i157, i176, i157) -> f893_0_main_LE(EOS(STATIC_893), i176, i157, i176, i157) :|: i176 > i157 9.97/3.57 f892_0_main_LE(EOS(STATIC_892), i176, i157, i176, i157) -> f900_0_main_Load(EOS(STATIC_900), i176, i157) :|: i176 <= i157 9.97/3.57 f900_0_main_Load(EOS(STATIC_900), i176, i157) -> f909_0_main_Load(EOS(STATIC_909), i176, i157, i176) :|: TRUE 9.97/3.57 f909_0_main_Load(EOS(STATIC_909), i176, i157, i176) -> f914_0_main_NE(EOS(STATIC_914), i176, i157, i176, i157) :|: TRUE 9.97/3.57 f914_0_main_NE(EOS(STATIC_914), i176, i157, i176, i157) -> f936_0_main_NE(EOS(STATIC_936), i176, i157, i176, i157) :|: !(i176 = i157) 9.97/3.57 f914_0_main_NE(EOS(STATIC_914), i157, i157, i157, i157) -> f937_0_main_NE(EOS(STATIC_937), i157, i157, i157, i157) :|: i176 = i157 9.97/3.57 f936_0_main_NE(EOS(STATIC_936), i176, i157, i176, i157) -> f944_0_main_Inc(EOS(STATIC_944), i176, i157) :|: i176 < i157 9.97/3.57 f944_0_main_Inc(EOS(STATIC_944), i176, i157) -> f952_0_main_JMP(EOS(STATIC_952), i176, i157 + -1) :|: TRUE 9.97/3.57 f952_0_main_JMP(EOS(STATIC_952), i176, i197) -> f957_0_main_Load(EOS(STATIC_957), i176, i197) :|: TRUE 9.97/3.57 f957_0_main_Load(EOS(STATIC_957), i176, i197) -> f880_0_main_Load(EOS(STATIC_880), i176, i197) :|: TRUE 9.97/3.57 f880_0_main_Load(EOS(STATIC_880), i176, i157) -> f881_0_main_Load(EOS(STATIC_881), i176, i157, i176) :|: TRUE 9.97/3.57 f937_0_main_NE(EOS(STATIC_937), i157, i157, i157, i157) -> f949_0_main_Inc(EOS(STATIC_949), i157, i157) :|: TRUE 9.97/3.57 f949_0_main_Inc(EOS(STATIC_949), i157, i157) -> f954_0_main_JMP(EOS(STATIC_954), i157 + -1, i157) :|: TRUE 9.97/3.57 f954_0_main_JMP(EOS(STATIC_954), i198, i157) -> f974_0_main_Load(EOS(STATIC_974), i198, i157) :|: TRUE 9.97/3.57 f974_0_main_Load(EOS(STATIC_974), i198, i157) -> f880_0_main_Load(EOS(STATIC_880), i198, i157) :|: TRUE 9.97/3.57 f893_0_main_LE(EOS(STATIC_893), i176, i157, i176, i157) -> f907_0_main_Inc(EOS(STATIC_907), i176, i157) :|: i176 > i157 9.97/3.57 f907_0_main_Inc(EOS(STATIC_907), i176, i157) -> f912_0_main_JMP(EOS(STATIC_912), i176 + -1, i157) :|: TRUE 9.97/3.57 f912_0_main_JMP(EOS(STATIC_912), i185, i157) -> f917_0_main_Load(EOS(STATIC_917), i185, i157) :|: TRUE 9.97/3.57 f917_0_main_Load(EOS(STATIC_917), i185, i157) -> f880_0_main_Load(EOS(STATIC_880), i185, i157) :|: TRUE 9.97/3.57 Combined rules. Obtained 3 IRulesP rules: 9.97/3.57 f881_0_main_Load(EOS(STATIC_881), i176:0, i157:0, i176:0) -> f881_0_main_Load(EOS(STATIC_881), i176:0, i157:0 - 1, i176:0) :|: i176:0 < i157:0 && i176:0 + i157:0 > 0 9.97/3.57 f881_0_main_Load(EOS(STATIC_881), i176:0, i176:0, i176:0) -> f881_0_main_Load(EOS(STATIC_881), i176:0 - 1, i176:0, i176:0 - 1) :|: i176:0 + i176:0 > 0 9.97/3.57 f881_0_main_Load(EOS(STATIC_881), i176:0, i157:0, i176:0) -> f881_0_main_Load(EOS(STATIC_881), i176:0 - 1, i157:0, i176:0 - 1) :|: i176:0 + i157:0 > 0 && i176:0 > i157:0 9.97/3.57 Filtered constant ground arguments: 9.97/3.57 f881_0_main_Load(x1, x2, x3, x4) -> f881_0_main_Load(x2, x3, x4) 9.97/3.57 EOS(x1) -> EOS 9.97/3.57 Filtered duplicate arguments: 9.97/3.57 f881_0_main_Load(x1, x2, x3) -> f881_0_main_Load(x2, x3) 9.97/3.57 Finished conversion. Obtained 3 rules.P rules: 9.97/3.57 f881_0_main_Load(i157:0, i176:0) -> f881_0_main_Load(i157:0 - 1, i176:0) :|: i176:0 < i157:0 && i176:0 + i157:0 > 0 9.97/3.57 f881_0_main_Load(i176:0, i176:0) -> f881_0_main_Load(i176:0, i176:0 - 1) :|: i176:0 + i176:0 > 0 9.97/3.57 f881_0_main_Load(i157:0, i176:0) -> f881_0_main_Load(i157:0, i176:0 - 1) :|: i176:0 + i157:0 > 0 && i176:0 > i157:0 9.97/3.57 9.97/3.57 ---------------------------------------- 9.97/3.57 9.97/3.57 (8) 9.97/3.57 Obligation: 9.97/3.57 Rules: 9.97/3.57 f881_0_main_Load(i157:0, i176:0) -> f881_0_main_Load(i157:0 - 1, i176:0) :|: i176:0 < i157:0 && i176:0 + i157:0 > 0 9.97/3.57 f881_0_main_Load(x, x) -> f881_0_main_Load(x, x - 1) :|: x + x > 0 9.97/3.57 f881_0_main_Load(x1, x2) -> f881_0_main_Load(x1, x2 - 1) :|: x2 + x1 > 0 && x2 > x1 9.97/3.57 9.97/3.57 ---------------------------------------- 9.97/3.57 9.97/3.57 (9) IRSFormatTransformerProof (EQUIVALENT) 9.97/3.57 Reformatted IRS to match normalized format (transformed away non-linear left-hand sides, !=, / and %). 9.97/3.57 ---------------------------------------- 9.97/3.57 9.97/3.57 (10) 9.97/3.57 Obligation: 9.97/3.57 Rules: 9.97/3.57 f881_0_main_Load(i157:0, i176:0) -> f881_0_main_Load(arith, i176:0) :|: i176:0 < i157:0 && i176:0 + i157:0 > 0 && arith = i157:0 - 1 9.97/3.57 f881_0_main_Load(x3, x3) -> f881_0_main_Load(x3, x4) :|: x3 + x3 > 0 && x4 = x3 - 1 9.97/3.57 f881_0_main_Load(x5, x6) -> f881_0_main_Load(x5, x7) :|: x6 + x5 > 0 && x6 > x5 && x7 = x6 - 1 9.97/3.57 9.97/3.57 ---------------------------------------- 9.97/3.57 9.97/3.57 (11) IRSwTTerminationDigraphProof (EQUIVALENT) 9.97/3.57 Constructed termination digraph! 9.97/3.57 Nodes: 9.97/3.57 (1) f881_0_main_Load(i157:0, i176:0) -> f881_0_main_Load(arith, i176:0) :|: i176:0 < i157:0 && i176:0 + i157:0 > 0 && arith = i157:0 - 1 9.97/3.57 (2) f881_0_main_Load(x3, x3) -> f881_0_main_Load(x3, x4) :|: x3 + x3 > 0 && x4 = x3 - 1 9.97/3.57 (3) f881_0_main_Load(x5, x6) -> f881_0_main_Load(x5, x7) :|: x6 + x5 > 0 && x6 > x5 && x7 = x6 - 1 9.97/3.57 9.97/3.57 Arcs: 9.97/3.57 (1) -> (1), (2) 9.97/3.57 (2) -> (1) 9.97/3.57 (3) -> (2), (3) 9.97/3.57 9.97/3.57 This digraph is fully evaluated! 9.97/3.57 ---------------------------------------- 9.97/3.57 9.97/3.57 (12) 9.97/3.57 Complex Obligation (AND) 9.97/3.57 9.97/3.57 ---------------------------------------- 9.97/3.57 9.97/3.57 (13) 9.97/3.57 Obligation: 9.97/3.57 9.97/3.57 Termination digraph: 9.97/3.57 Nodes: 9.97/3.57 (1) f881_0_main_Load(x5, x6) -> f881_0_main_Load(x5, x7) :|: x6 + x5 > 0 && x6 > x5 && x7 = x6 - 1 9.97/3.57 9.97/3.57 Arcs: 9.97/3.57 (1) -> (1) 9.97/3.57 9.97/3.57 This digraph is fully evaluated! 9.97/3.57 9.97/3.57 ---------------------------------------- 9.97/3.57 9.97/3.57 (14) IntTRSCompressionProof (EQUIVALENT) 9.97/3.57 Compressed rules. 9.97/3.57 ---------------------------------------- 9.97/3.57 9.97/3.57 (15) 9.97/3.57 Obligation: 9.97/3.57 Rules: 9.97/3.57 f881_0_main_Load(x5:0, x6:0) -> f881_0_main_Load(x5:0, x6:0 - 1) :|: x6:0 + x5:0 > 0 && x6:0 > x5:0 9.97/3.57 9.97/3.57 ---------------------------------------- 9.97/3.57 9.97/3.57 (16) TempFilterProof (SOUND) 9.97/3.57 Used the following sort dictionary for filtering: 9.97/3.57 f881_0_main_Load(INTEGER, INTEGER) 9.97/3.57 Replaced non-predefined constructor symbols by 0. 9.97/3.57 ---------------------------------------- 9.97/3.57 9.97/3.57 (17) 9.97/3.57 Obligation: 9.97/3.57 Rules: 9.97/3.57 f881_0_main_Load(x5:0, x6:0) -> f881_0_main_Load(x5:0, c) :|: c = x6:0 - 1 && (x6:0 + x5:0 > 0 && x6:0 > x5:0) 9.97/3.57 9.97/3.57 ---------------------------------------- 9.97/3.57 9.97/3.57 (18) PolynomialOrderProcessor (EQUIVALENT) 9.97/3.57 Found the following polynomial interpretation: 9.97/3.57 [f881_0_main_Load(x, x1)] = -x + x1 9.97/3.57 9.97/3.57 The following rules are decreasing: 9.97/3.57 f881_0_main_Load(x5:0, x6:0) -> f881_0_main_Load(x5:0, c) :|: c = x6:0 - 1 && (x6:0 + x5:0 > 0 && x6:0 > x5:0) 9.97/3.57 The following rules are bounded: 9.97/3.57 f881_0_main_Load(x5:0, x6:0) -> f881_0_main_Load(x5:0, c) :|: c = x6:0 - 1 && (x6:0 + x5:0 > 0 && x6:0 > x5:0) 9.97/3.57 9.97/3.57 ---------------------------------------- 9.97/3.57 9.97/3.57 (19) 9.97/3.57 YES 9.97/3.57 9.97/3.57 ---------------------------------------- 9.97/3.57 9.97/3.57 (20) 9.97/3.57 Obligation: 9.97/3.57 9.97/3.57 Termination digraph: 9.97/3.57 Nodes: 9.97/3.57 (1) f881_0_main_Load(i157:0, i176:0) -> f881_0_main_Load(arith, i176:0) :|: i176:0 < i157:0 && i176:0 + i157:0 > 0 && arith = i157:0 - 1 9.97/3.57 (2) f881_0_main_Load(x3, x3) -> f881_0_main_Load(x3, x4) :|: x3 + x3 > 0 && x4 = x3 - 1 9.97/3.57 9.97/3.57 Arcs: 9.97/3.57 (1) -> (1), (2) 9.97/3.57 (2) -> (1) 9.97/3.57 9.97/3.57 This digraph is fully evaluated! 9.97/3.57 9.97/3.57 ---------------------------------------- 9.97/3.57 9.97/3.57 (21) IntTRSCompressionProof (EQUIVALENT) 9.97/3.57 Compressed rules. 9.97/3.57 ---------------------------------------- 9.97/3.57 9.97/3.57 (22) 9.97/3.57 Obligation: 9.97/3.57 Rules: 9.97/3.57 f881_0_main_Load(x3:0, x3:0) -> f881_0_main_Load(x3:0, x3:0 - 1) :|: x3:0 + x3:0 > 0 9.97/3.57 f881_0_main_Load(i157:0:0, i176:0:0) -> f881_0_main_Load(i157:0:0 - 1, i176:0:0) :|: i176:0:0 < i157:0:0 && i176:0:0 + i157:0:0 > 0 9.97/3.57 9.97/3.57 ---------------------------------------- 9.97/3.57 9.97/3.57 (23) TempFilterProof (SOUND) 9.97/3.57 Used the following sort dictionary for filtering: 9.97/3.57 f881_0_main_Load(INTEGER, INTEGER) 9.97/3.57 Replaced non-predefined constructor symbols by 0. 9.97/3.57 ---------------------------------------- 9.97/3.57 9.97/3.57 (24) 9.97/3.57 Obligation: 9.97/3.57 Rules: 9.97/3.57 f881_0_main_Load(x3:0, x3:0) -> f881_0_main_Load(x3:0, c) :|: c = x3:0 - 1 && x3:0 + x3:0 > 0 9.97/3.57 f881_0_main_Load(i157:0:0, i176:0:0) -> f881_0_main_Load(c1, i176:0:0) :|: c1 = i157:0:0 - 1 && (i176:0:0 < i157:0:0 && i176:0:0 + i157:0:0 > 0) 9.97/3.57 9.97/3.57 ---------------------------------------- 9.97/3.57 9.97/3.57 (25) RankingReductionPairProof (EQUIVALENT) 9.97/3.57 Interpretation: 9.97/3.57 [ f881_0_main_Load ] = f881_0_main_Load_2 9.97/3.57 9.97/3.57 The following rules are decreasing: 9.97/3.57 f881_0_main_Load(x3:0, x3:0) -> f881_0_main_Load(x3:0, c) :|: c = x3:0 - 1 && x3:0 + x3:0 > 0 9.97/3.57 9.97/3.57 The following rules are bounded: 9.97/3.57 f881_0_main_Load(x3:0, x3:0) -> f881_0_main_Load(x3:0, c) :|: c = x3:0 - 1 && x3:0 + x3:0 > 0 9.97/3.57 9.97/3.57 9.97/3.57 ---------------------------------------- 9.97/3.57 9.97/3.57 (26) 9.97/3.57 Obligation: 9.97/3.57 Rules: 9.97/3.57 f881_0_main_Load(i157:0:0, i176:0:0) -> f881_0_main_Load(c1, i176:0:0) :|: c1 = i157:0:0 - 1 && (i176:0:0 < i157:0:0 && i176:0:0 + i157:0:0 > 0) 9.97/3.57 9.97/3.57 ---------------------------------------- 9.97/3.57 9.97/3.57 (27) PolynomialOrderProcessor (EQUIVALENT) 9.97/3.57 Found the following polynomial interpretation: 9.97/3.57 [f881_0_main_Load(x, x1)] = x + x1 9.97/3.57 9.97/3.57 The following rules are decreasing: 9.97/3.57 f881_0_main_Load(i157:0:0, i176:0:0) -> f881_0_main_Load(c1, i176:0:0) :|: c1 = i157:0:0 - 1 && (i176:0:0 < i157:0:0 && i176:0:0 + i157:0:0 > 0) 9.97/3.57 The following rules are bounded: 9.97/3.57 f881_0_main_Load(i157:0:0, i176:0:0) -> f881_0_main_Load(c1, i176:0:0) :|: c1 = i157:0:0 - 1 && (i176:0:0 < i157:0:0 && i176:0:0 + i157:0:0 > 0) 9.97/3.58 9.97/3.58 ---------------------------------------- 9.97/3.58 9.97/3.58 (28) 9.97/3.58 YES 9.97/3.60 EOF