8.11/3.92 YES 8.45/4.03 proof of /export/starexec/sandbox/benchmark/theBenchmark.jar 8.45/4.03 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 8.45/4.03 8.45/4.03 8.45/4.03 termination of the given Bare JBC problem could be proven: 8.45/4.03 8.45/4.03 (0) Bare JBC problem 8.45/4.03 (1) BareJBCToJBCProof [EQUIVALENT, 96 ms] 8.45/4.03 (2) JBC problem 8.45/4.03 (3) JBCToGraph [EQUIVALENT, 338 ms] 8.45/4.03 (4) JBCTerminationGraph 8.45/4.03 (5) TerminationGraphToSCCProof [SOUND, 0 ms] 8.45/4.03 (6) JBCTerminationSCC 8.45/4.03 (7) SCCToIRSProof [SOUND, 64 ms] 8.45/4.03 (8) IRSwT 8.45/4.03 (9) IRSFormatTransformerProof [EQUIVALENT, 0 ms] 8.45/4.03 (10) IRSwT 8.45/4.03 (11) IRSwTTerminationDigraphProof [EQUIVALENT, 50 ms] 8.45/4.03 (12) IRSwT 8.45/4.03 (13) IntTRSCompressionProof [EQUIVALENT, 0 ms] 8.45/4.03 (14) IRSwT 8.45/4.03 (15) TempFilterProof [SOUND, 67 ms] 8.45/4.03 (16) IntTRS 8.45/4.03 (17) PolynomialOrderProcessor [EQUIVALENT, 15 ms] 8.45/4.03 (18) IntTRS 8.45/4.03 (19) RankingReductionPairProof [EQUIVALENT, 0 ms] 8.45/4.03 (20) YES 8.45/4.03 8.45/4.03 8.45/4.03 ---------------------------------------- 8.45/4.03 8.45/4.03 (0) 8.45/4.03 Obligation: 8.45/4.03 need to prove termination of the following program: 8.45/4.03 public class Mod { 8.45/4.03 public static void main(String[] args) { 8.45/4.03 int x = args[0].length(); 8.45/4.03 int y = args[1].length(); 8.45/4.03 mod(x, y); 8.45/4.03 } 8.45/4.03 public static int mod(int x, int y) { 8.45/4.03 8.45/4.03 while (x >= y && y > 0) { 8.45/4.03 x = minus(x,y); 8.45/4.03 8.45/4.03 } 8.45/4.03 return x; 8.45/4.03 } 8.45/4.03 8.45/4.03 public static int minus(int x, int y) { 8.45/4.03 while (y != 0) { 8.45/4.03 if (y > 0) { 8.45/4.03 y--; 8.45/4.03 x--; 8.45/4.03 } else { 8.45/4.03 y++; 8.45/4.03 x++; 8.45/4.03 } 8.45/4.03 } 8.45/4.03 return x; 8.45/4.03 } 8.45/4.03 8.45/4.03 } 8.45/4.03 8.45/4.03 8.45/4.03 8.45/4.03 ---------------------------------------- 8.45/4.03 8.45/4.03 (1) BareJBCToJBCProof (EQUIVALENT) 8.45/4.03 initialized classpath 8.45/4.03 ---------------------------------------- 8.45/4.03 8.45/4.03 (2) 8.45/4.03 Obligation: 8.45/4.03 need to prove termination of the following program: 8.45/4.03 public class Mod { 8.45/4.03 public static void main(String[] args) { 8.45/4.03 int x = args[0].length(); 8.45/4.03 int y = args[1].length(); 8.45/4.03 mod(x, y); 8.45/4.03 } 8.45/4.03 public static int mod(int x, int y) { 8.45/4.03 8.45/4.03 while (x >= y && y > 0) { 8.45/4.03 x = minus(x,y); 8.45/4.03 8.45/4.03 } 8.45/4.03 return x; 8.45/4.03 } 8.45/4.03 8.45/4.03 public static int minus(int x, int y) { 8.45/4.03 while (y != 0) { 8.45/4.03 if (y > 0) { 8.45/4.03 y--; 8.45/4.03 x--; 8.45/4.03 } else { 8.45/4.03 y++; 8.45/4.03 x++; 8.45/4.03 } 8.45/4.03 } 8.45/4.03 return x; 8.45/4.03 } 8.45/4.03 8.45/4.03 } 8.45/4.03 8.45/4.03 8.45/4.03 8.45/4.03 ---------------------------------------- 8.45/4.03 8.45/4.03 (3) JBCToGraph (EQUIVALENT) 8.45/4.03 Constructed TerminationGraph. 8.45/4.03 ---------------------------------------- 8.45/4.03 8.45/4.03 (4) 8.45/4.03 Obligation: 8.45/4.03 Termination Graph based on JBC Program: 8.45/4.03 Mod.main([Ljava/lang/String;)V: Graph of 152 nodes with 1 SCC. 8.45/4.03 8.45/4.03 8.45/4.03 8.45/4.03 8.45/4.03 8.45/4.03 ---------------------------------------- 8.45/4.03 8.45/4.03 (5) TerminationGraphToSCCProof (SOUND) 8.45/4.03 Splitted TerminationGraph to 1 SCCs. 8.45/4.03 ---------------------------------------- 8.45/4.03 8.45/4.03 (6) 8.45/4.03 Obligation: 8.45/4.03 SCC of termination graph based on JBC Program. 8.45/4.03 SCC contains nodes from the following methods: Mod.main([Ljava/lang/String;)V 8.45/4.03 SCC calls the following helper methods: 8.45/4.03 Performed SCC analyses: 8.45/4.03 *Used field analysis yielded the following read fields: 8.45/4.03 8.45/4.03 *Marker field analysis yielded the following relations that could be markers: 8.45/4.03 8.45/4.03 ---------------------------------------- 8.45/4.03 8.45/4.03 (7) SCCToIRSProof (SOUND) 8.45/4.03 Transformed FIGraph SCCs to intTRSs. Log: 8.45/4.03 Generated rules. Obtained 27 IRulesP rules: 8.45/4.03 f195_0_mod_Load(EOS(STATIC_195), i13, i30, i13) -> f198_0_mod_LT(EOS(STATIC_198), i13, i30, i13, i30) :|: TRUE 8.45/4.03 f198_0_mod_LT(EOS(STATIC_198), i13, i30, i13, i30) -> f204_0_mod_LT(EOS(STATIC_204), i13, i30, i13, i30) :|: i13 >= i30 8.45/4.03 f204_0_mod_LT(EOS(STATIC_204), i13, i30, i13, i30) -> f212_0_mod_Load(EOS(STATIC_212), i13, i30) :|: i13 >= i30 8.45/4.03 f212_0_mod_Load(EOS(STATIC_212), i13, i30) -> f223_0_mod_LE(EOS(STATIC_223), i13, i30, i30) :|: TRUE 8.45/4.03 f223_0_mod_LE(EOS(STATIC_223), i36, i35, i35) -> f239_0_mod_LE(EOS(STATIC_239), i36, i35, i35) :|: TRUE 8.45/4.03 f239_0_mod_LE(EOS(STATIC_239), i36, i35, i35) -> f265_0_mod_Load(EOS(STATIC_265), i36, i35) :|: i35 > 0 8.45/4.03 f265_0_mod_Load(EOS(STATIC_265), i36, i35) -> f269_0_mod_Load(EOS(STATIC_269), i35, i36) :|: TRUE 8.45/4.03 f269_0_mod_Load(EOS(STATIC_269), i35, i36) -> f274_0_mod_InvokeMethod(EOS(STATIC_274), i35, i36, i35) :|: TRUE 8.45/4.03 f274_0_mod_InvokeMethod(EOS(STATIC_274), i35, i36, i35) -> f279_0_minus_Load(EOS(STATIC_279), i35, i36, i35) :|: TRUE 8.45/4.03 f279_0_minus_Load(EOS(STATIC_279), i35, i36, i35) -> f350_0_minus_Load(EOS(STATIC_350), i35, i36, i35) :|: TRUE 8.45/4.03 f350_0_minus_Load(EOS(STATIC_350), i35, i48, i49) -> f355_0_minus_EQ(EOS(STATIC_355), i35, i48, i49, i49) :|: TRUE 8.45/4.03 f355_0_minus_EQ(EOS(STATIC_355), i35, i57, i56, i56) -> f358_0_minus_EQ(EOS(STATIC_358), i35, i57, i56, i56) :|: TRUE 8.45/4.03 f355_0_minus_EQ(EOS(STATIC_355), i35, i48, matching1, matching2) -> f360_0_minus_EQ(EOS(STATIC_360), i35, i48, 0, 0) :|: TRUE && matching1 = 0 && matching2 = 0 8.45/4.03 f358_0_minus_EQ(EOS(STATIC_358), i35, i57, i56, i56) -> f362_0_minus_Load(EOS(STATIC_362), i35, i57, i56) :|: i56 > 0 8.45/4.03 f362_0_minus_Load(EOS(STATIC_362), i35, i57, i56) -> f366_0_minus_LE(EOS(STATIC_366), i35, i57, i56, i56) :|: TRUE 8.45/4.03 f366_0_minus_LE(EOS(STATIC_366), i35, i57, i56, i56) -> f371_0_minus_Inc(EOS(STATIC_371), i35, i57, i56) :|: i56 > 0 8.45/4.03 f371_0_minus_Inc(EOS(STATIC_371), i35, i57, i56) -> f375_0_minus_Inc(EOS(STATIC_375), i35, i57, i56 + -1) :|: TRUE 8.45/4.03 f375_0_minus_Inc(EOS(STATIC_375), i35, i57, i61) -> f384_0_minus_JMP(EOS(STATIC_384), i35, i57 + -1, i61) :|: TRUE 8.45/4.03 f384_0_minus_JMP(EOS(STATIC_384), i35, i62, i61) -> f406_0_minus_Load(EOS(STATIC_406), i35, i62, i61) :|: TRUE 8.45/4.03 f406_0_minus_Load(EOS(STATIC_406), i35, i62, i61) -> f350_0_minus_Load(EOS(STATIC_350), i35, i62, i61) :|: TRUE 8.45/4.03 f360_0_minus_EQ(EOS(STATIC_360), i35, i48, matching1, matching2) -> f364_0_minus_Load(EOS(STATIC_364), i35, i48) :|: TRUE && matching1 = 0 && matching2 = 0 8.45/4.03 f364_0_minus_Load(EOS(STATIC_364), i35, i48) -> f368_0_minus_Return(EOS(STATIC_368), i35, i48) :|: TRUE 8.45/4.03 f368_0_minus_Return(EOS(STATIC_368), i35, i48) -> f373_0_mod_Store(EOS(STATIC_373), i35, i48) :|: TRUE 8.45/4.03 f373_0_mod_Store(EOS(STATIC_373), i35, i48) -> f378_0_mod_JMP(EOS(STATIC_378), i48, i35) :|: TRUE 8.45/4.03 f378_0_mod_JMP(EOS(STATIC_378), i48, i35) -> f394_0_mod_Load(EOS(STATIC_394), i48, i35) :|: TRUE 8.45/4.03 f394_0_mod_Load(EOS(STATIC_394), i48, i35) -> f189_0_mod_Load(EOS(STATIC_189), i48, i35) :|: TRUE 8.45/4.03 f189_0_mod_Load(EOS(STATIC_189), i13, i30) -> f195_0_mod_Load(EOS(STATIC_195), i13, i30, i13) :|: TRUE 8.45/4.03 Combined rules. Obtained 2 IRulesP rules: 8.45/4.03 f355_0_minus_EQ(EOS(STATIC_355), i35:0, i57:0, i56:0, i56:0) -> f355_0_minus_EQ(EOS(STATIC_355), i35:0, i57:0 - 1, i56:0 - 1, i56:0 - 1) :|: i56:0 > 0 8.45/4.03 f355_0_minus_EQ(EOS(STATIC_355), i35:0, i48:0, 0, 0) -> f355_0_minus_EQ(EOS(STATIC_355), i35:0, i48:0, i35:0, i35:0) :|: i48:0 >= i35:0 && i35:0 > 0 8.45/4.03 Filtered constant ground arguments: 8.45/4.03 f355_0_minus_EQ(x1, x2, x3, x4, x5) -> f355_0_minus_EQ(x2, x3, x4, x5) 8.45/4.03 EOS(x1) -> EOS 8.45/4.03 Filtered duplicate arguments: 8.45/4.03 f355_0_minus_EQ(x1, x2, x3, x4) -> f355_0_minus_EQ(x1, x2, x4) 8.45/4.03 Finished conversion. Obtained 2 rules.P rules: 8.45/4.03 f355_0_minus_EQ(i35:0, i57:0, i56:0) -> f355_0_minus_EQ(i35:0, i57:0 - 1, i56:0 - 1) :|: i56:0 > 0 8.45/4.03 f355_0_minus_EQ(i35:0, i48:0, cons_0) -> f355_0_minus_EQ(i35:0, i48:0, i35:0) :|: i48:0 >= i35:0 && i35:0 > 0 && cons_0 = 0 8.45/4.03 8.45/4.03 ---------------------------------------- 8.45/4.03 8.45/4.03 (8) 8.45/4.03 Obligation: 8.45/4.03 Rules: 8.45/4.03 f355_0_minus_EQ(i35:0, i57:0, i56:0) -> f355_0_minus_EQ(i35:0, i57:0 - 1, i56:0 - 1) :|: i56:0 > 0 8.45/4.03 f355_0_minus_EQ(x, x1, x2) -> f355_0_minus_EQ(x, x1, x) :|: x1 >= x && x > 0 && x2 = 0 8.45/4.03 8.45/4.03 ---------------------------------------- 8.45/4.03 8.45/4.03 (9) IRSFormatTransformerProof (EQUIVALENT) 8.45/4.03 Reformatted IRS to match normalized format (transformed away non-linear left-hand sides, !=, / and %). 8.45/4.03 ---------------------------------------- 8.45/4.03 8.45/4.03 (10) 8.45/4.03 Obligation: 8.45/4.03 Rules: 8.45/4.03 f355_0_minus_EQ(i35:0, i57:0, i56:0) -> f355_0_minus_EQ(i35:0, arith, arith1) :|: i56:0 > 0 && arith = i57:0 - 1 && arith1 = i56:0 - 1 8.45/4.03 f355_0_minus_EQ(x, x1, x2) -> f355_0_minus_EQ(x, x1, x) :|: x1 >= x && x > 0 && x2 = 0 8.45/4.03 8.45/4.03 ---------------------------------------- 8.45/4.03 8.45/4.03 (11) IRSwTTerminationDigraphProof (EQUIVALENT) 8.45/4.03 Constructed termination digraph! 8.45/4.03 Nodes: 8.45/4.03 (1) f355_0_minus_EQ(i35:0, i57:0, i56:0) -> f355_0_minus_EQ(i35:0, arith, arith1) :|: i56:0 > 0 && arith = i57:0 - 1 && arith1 = i56:0 - 1 8.45/4.03 (2) f355_0_minus_EQ(x, x1, x2) -> f355_0_minus_EQ(x, x1, x) :|: x1 >= x && x > 0 && x2 = 0 8.45/4.03 8.45/4.03 Arcs: 8.45/4.03 (1) -> (1), (2) 8.45/4.03 (2) -> (1) 8.45/4.03 8.45/4.03 This digraph is fully evaluated! 8.45/4.03 ---------------------------------------- 8.45/4.03 8.45/4.03 (12) 8.45/4.03 Obligation: 8.45/4.03 8.45/4.03 Termination digraph: 8.45/4.03 Nodes: 8.45/4.03 (1) f355_0_minus_EQ(i35:0, i57:0, i56:0) -> f355_0_minus_EQ(i35:0, arith, arith1) :|: i56:0 > 0 && arith = i57:0 - 1 && arith1 = i56:0 - 1 8.45/4.03 (2) f355_0_minus_EQ(x, x1, x2) -> f355_0_minus_EQ(x, x1, x) :|: x1 >= x && x > 0 && x2 = 0 8.45/4.03 8.45/4.03 Arcs: 8.45/4.03 (1) -> (1), (2) 8.45/4.03 (2) -> (1) 8.45/4.03 8.45/4.03 This digraph is fully evaluated! 8.45/4.03 8.45/4.03 ---------------------------------------- 8.45/4.03 8.45/4.03 (13) IntTRSCompressionProof (EQUIVALENT) 8.45/4.03 Compressed rules. 8.45/4.03 ---------------------------------------- 8.45/4.03 8.45/4.03 (14) 8.45/4.03 Obligation: 8.45/4.03 Rules: 8.45/4.03 f355_0_minus_EQ(i35:0:0, i57:0:0, i56:0:0) -> f355_0_minus_EQ(i35:0:0, i57:0:0 - 1, i56:0:0 - 1) :|: i56:0:0 > 0 8.45/4.03 f355_0_minus_EQ(x:0, x1:0, cons_0) -> f355_0_minus_EQ(x:0, x1:0, x:0) :|: x:0 <= x1:0 && x:0 > 0 && cons_0 = 0 8.45/4.03 8.45/4.03 ---------------------------------------- 8.45/4.03 8.45/4.03 (15) TempFilterProof (SOUND) 8.45/4.03 Used the following sort dictionary for filtering: 8.45/4.03 f355_0_minus_EQ(VARIABLE, VARIABLE, INTEGER) 8.45/4.03 Replaced non-predefined constructor symbols by 0. 8.45/4.03 ---------------------------------------- 8.45/4.03 8.45/4.03 (16) 8.45/4.03 Obligation: 8.45/4.03 Rules: 8.45/4.03 f355_0_minus_EQ(i35:0:0, i57:0:0, i56:0:0) -> f355_0_minus_EQ(i35:0:0, c, c1) :|: c1 = i56:0:0 - 1 && c = i57:0:0 - 1 && i56:0:0 > 0 8.45/4.03 f355_0_minus_EQ(x:0, x1:0, c2) -> f355_0_minus_EQ(x:0, x1:0, x:0) :|: c2 = 0 && (x:0 <= x1:0 && x:0 > 0 && cons_0 = 0) 8.45/4.03 8.45/4.03 ---------------------------------------- 8.45/4.03 8.45/4.03 (17) PolynomialOrderProcessor (EQUIVALENT) 8.45/4.03 Found the following polynomial interpretation: 8.45/4.03 [f355_0_minus_EQ(x, x1, x2)] = x + x1 - x2 8.45/4.03 8.45/4.03 The following rules are decreasing: 8.45/4.03 f355_0_minus_EQ(x:0, x1:0, c2) -> f355_0_minus_EQ(x:0, x1:0, x:0) :|: c2 = 0 && (x:0 <= x1:0 && x:0 > 0 && cons_0 = 0) 8.45/4.03 The following rules are bounded: 8.45/4.03 f355_0_minus_EQ(x:0, x1:0, c2) -> f355_0_minus_EQ(x:0, x1:0, x:0) :|: c2 = 0 && (x:0 <= x1:0 && x:0 > 0 && cons_0 = 0) 8.45/4.03 8.45/4.03 ---------------------------------------- 8.45/4.03 8.45/4.03 (18) 8.45/4.03 Obligation: 8.45/4.03 Rules: 8.45/4.03 f355_0_minus_EQ(i35:0:0, i57:0:0, i56:0:0) -> f355_0_minus_EQ(i35:0:0, c, c1) :|: c1 = i56:0:0 - 1 && c = i57:0:0 - 1 && i56:0:0 > 0 8.45/4.03 8.45/4.03 ---------------------------------------- 8.45/4.03 8.45/4.03 (19) RankingReductionPairProof (EQUIVALENT) 8.45/4.03 Interpretation: 8.45/4.03 [ f355_0_minus_EQ ] = f355_0_minus_EQ_3 8.45/4.03 8.45/4.03 The following rules are decreasing: 8.45/4.03 f355_0_minus_EQ(i35:0:0, i57:0:0, i56:0:0) -> f355_0_minus_EQ(i35:0:0, c, c1) :|: c1 = i56:0:0 - 1 && c = i57:0:0 - 1 && i56:0:0 > 0 8.45/4.03 8.45/4.03 The following rules are bounded: 8.45/4.03 f355_0_minus_EQ(i35:0:0, i57:0:0, i56:0:0) -> f355_0_minus_EQ(i35:0:0, c, c1) :|: c1 = i56:0:0 - 1 && c = i57:0:0 - 1 && i56:0:0 > 0 8.45/4.03 8.45/4.03 8.45/4.03 ---------------------------------------- 8.45/4.03 8.45/4.03 (20) 8.45/4.03 YES 8.45/4.09 EOF