8.71/6.98 YES 8.94/7.00 proof of /export/starexec/sandbox2/benchmark/theBenchmark.jar 8.94/7.00 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 8.94/7.00 8.94/7.00 8.94/7.00 termination of the given Bare JBC problem could be proven: 8.94/7.00 8.94/7.00 (0) Bare JBC problem 8.94/7.00 (1) BareJBCToJBCProof [EQUIVALENT, 96 ms] 8.94/7.00 (2) JBC problem 8.94/7.00 (3) JBCToGraph [EQUIVALENT, 338 ms] 8.94/7.00 (4) JBCTerminationGraph 8.94/7.00 (5) TerminationGraphToSCCProof [SOUND, 0 ms] 8.94/7.00 (6) JBCTerminationSCC 8.94/7.00 (7) SCCToIRSProof [SOUND, 62 ms] 8.94/7.00 (8) IRSwT 8.94/7.00 (9) IRSFormatTransformerProof [EQUIVALENT, 0 ms] 8.94/7.00 (10) IRSwT 8.94/7.00 (11) IRSwTTerminationDigraphProof [EQUIVALENT, 0 ms] 8.94/7.00 (12) IRSwT 8.94/7.00 (13) IntTRSCompressionProof [EQUIVALENT, 0 ms] 8.94/7.00 (14) IRSwT 8.94/7.00 (15) FilterProof [EQUIVALENT, 0 ms] 8.94/7.00 (16) IntTRS 8.94/7.00 (17) IntTRSCompressionProof [EQUIVALENT, 0 ms] 8.94/7.00 (18) IntTRS 8.94/7.00 (19) PolynomialOrderProcessor [EQUIVALENT, 12 ms] 8.94/7.00 (20) YES 8.94/7.00 8.94/7.00 8.94/7.00 ---------------------------------------- 8.94/7.00 8.94/7.00 (0) 8.94/7.00 Obligation: 8.94/7.00 need to prove termination of the following program: 8.94/7.00 public class LogBuiltIn{ 8.94/7.00 public static int log(int x) { 8.94/7.00 8.94/7.00 int res = 0; 8.94/7.00 8.94/7.00 while (x > 1) { 8.94/7.00 8.94/7.00 x = x/2; 8.94/7.00 res++; 8.94/7.00 8.94/7.00 } 8.94/7.00 8.94/7.00 return res; 8.94/7.00 8.94/7.00 } 8.94/7.00 8.94/7.00 8.94/7.00 public static void main(String[] args) { 8.94/7.00 Random.args = args; 8.94/7.00 int x = Random.random(); 8.94/7.00 log(x); 8.94/7.00 } 8.94/7.00 } 8.94/7.00 8.94/7.00 8.94/7.00 8.94/7.00 public class Random { 8.94/7.00 static String[] args; 8.94/7.00 static int index = 0; 8.94/7.00 8.94/7.00 public static int random() { 8.94/7.00 String string = args[index]; 8.94/7.00 index++; 8.94/7.00 return string.length(); 8.94/7.00 } 8.94/7.00 } 8.94/7.00 8.94/7.00 8.94/7.00 8.94/7.00 ---------------------------------------- 8.94/7.00 8.94/7.00 (1) BareJBCToJBCProof (EQUIVALENT) 8.94/7.00 initialized classpath 8.94/7.00 ---------------------------------------- 8.94/7.00 8.94/7.00 (2) 8.94/7.00 Obligation: 8.94/7.00 need to prove termination of the following program: 8.94/7.00 public class LogBuiltIn{ 8.94/7.00 public static int log(int x) { 8.94/7.00 8.94/7.00 int res = 0; 8.94/7.00 8.94/7.00 while (x > 1) { 8.94/7.00 8.94/7.00 x = x/2; 8.94/7.00 res++; 8.94/7.00 8.94/7.00 } 8.94/7.00 8.94/7.00 return res; 8.94/7.00 8.94/7.00 } 8.94/7.00 8.94/7.00 8.94/7.00 public static void main(String[] args) { 8.94/7.00 Random.args = args; 8.94/7.00 int x = Random.random(); 8.94/7.00 log(x); 8.94/7.00 } 8.94/7.00 } 8.94/7.00 8.94/7.00 8.94/7.00 8.94/7.00 public class Random { 8.94/7.00 static String[] args; 8.94/7.00 static int index = 0; 8.94/7.00 8.94/7.00 public static int random() { 8.94/7.00 String string = args[index]; 8.94/7.00 index++; 8.94/7.00 return string.length(); 8.94/7.00 } 8.94/7.00 } 8.94/7.00 8.94/7.00 8.94/7.00 8.94/7.00 ---------------------------------------- 8.94/7.00 8.94/7.00 (3) JBCToGraph (EQUIVALENT) 8.94/7.00 Constructed TerminationGraph. 8.94/7.00 ---------------------------------------- 8.94/7.00 8.94/7.00 (4) 8.94/7.00 Obligation: 8.94/7.00 Termination Graph based on JBC Program: 8.94/7.00 LogBuiltIn.main([Ljava/lang/String;)V: Graph of 121 nodes with 1 SCC. 8.94/7.00 8.94/7.00 8.94/7.00 8.94/7.00 8.94/7.00 8.94/7.00 ---------------------------------------- 8.94/7.00 8.94/7.00 (5) TerminationGraphToSCCProof (SOUND) 8.94/7.00 Splitted TerminationGraph to 1 SCCs. 8.94/7.00 ---------------------------------------- 8.94/7.00 8.94/7.00 (6) 8.94/7.00 Obligation: 8.94/7.00 SCC of termination graph based on JBC Program. 8.94/7.00 SCC contains nodes from the following methods: LogBuiltIn.main([Ljava/lang/String;)V 8.94/7.00 SCC calls the following helper methods: 8.94/7.00 Performed SCC analyses: 8.94/7.00 *Used field analysis yielded the following read fields: 8.94/7.00 8.94/7.00 *Marker field analysis yielded the following relations that could be markers: 8.94/7.00 8.94/7.00 ---------------------------------------- 8.94/7.00 8.94/7.00 (7) SCCToIRSProof (SOUND) 8.94/7.00 Transformed FIGraph SCCs to intTRSs. Log: 8.94/7.00 Generated rules. Obtained 11 IRulesP rules: 8.94/7.00 f372_0_log_ConstantStackPush(EOS(STATIC_372), i60, i60) -> f373_0_log_LE(EOS(STATIC_373), i60, i60, 1) :|: TRUE 8.94/7.00 f373_0_log_LE(EOS(STATIC_373), i67, i67, matching1) -> f376_0_log_LE(EOS(STATIC_376), i67, i67, 1) :|: TRUE && matching1 = 1 8.94/7.00 f376_0_log_LE(EOS(STATIC_376), i67, i67, matching1) -> f389_0_log_Load(EOS(STATIC_389), i67) :|: i67 > 1 && matching1 = 1 8.94/7.00 f389_0_log_Load(EOS(STATIC_389), i67) -> f393_0_log_ConstantStackPush(EOS(STATIC_393), i67) :|: TRUE 8.94/7.00 f393_0_log_ConstantStackPush(EOS(STATIC_393), i67) -> f395_0_log_IntArithmetic(EOS(STATIC_395), i67, 2) :|: TRUE 8.94/7.00 f395_0_log_IntArithmetic(EOS(STATIC_395), i67, matching1) -> f399_0_log_Store(EOS(STATIC_399), i70) :|: i70 = i67 / 2 && i67 > 1 && i70 < i67 && matching1 = 2 8.94/7.00 f399_0_log_Store(EOS(STATIC_399), i70) -> f401_0_log_Inc(EOS(STATIC_401), i70) :|: TRUE 8.94/7.00 f401_0_log_Inc(EOS(STATIC_401), i70) -> f402_0_log_JMP(EOS(STATIC_402), i70) :|: TRUE 8.94/7.00 f402_0_log_JMP(EOS(STATIC_402), i70) -> f420_0_log_Load(EOS(STATIC_420), i70) :|: TRUE 8.94/7.00 f420_0_log_Load(EOS(STATIC_420), i70) -> f369_0_log_Load(EOS(STATIC_369), i70) :|: TRUE 8.94/7.00 f369_0_log_Load(EOS(STATIC_369), i60) -> f372_0_log_ConstantStackPush(EOS(STATIC_372), i60, i60) :|: TRUE 8.94/7.00 Combined rules. Obtained 2 IRulesP rules: 8.94/7.00 f372_0_log_ConstantStackPush(EOS(STATIC_372), i60:0, i60:0) -> f372_0_log_ConstantStackPush'(EOS(STATIC_372), i60:0, i60:0) :|: i60:0 > 1 && i60:0 > div 8.94/7.00 f372_0_log_ConstantStackPush'(EOS(STATIC_372), i60:0, i60:0) -> f372_0_log_ConstantStackPush(EOS(STATIC_372), div, div) :|: i60:0 > 1 && i60:0 > div && i60:0 - 2 * div < 2 && i60:0 - 2 * div > -2 8.94/7.00 Filtered constant ground arguments: 8.94/7.00 f372_0_log_ConstantStackPush(x1, x2, x3) -> f372_0_log_ConstantStackPush(x2, x3) 8.94/7.00 f372_0_log_ConstantStackPush'(x1, x2, x3) -> f372_0_log_ConstantStackPush'(x2, x3) 8.94/7.00 EOS(x1) -> EOS 8.94/7.00 Filtered duplicate arguments: 8.94/7.00 f372_0_log_ConstantStackPush(x1, x2) -> f372_0_log_ConstantStackPush(x2) 8.94/7.00 f372_0_log_ConstantStackPush'(x1, x2) -> f372_0_log_ConstantStackPush'(x2) 8.94/7.00 Finished conversion. Obtained 2 rules.P rules: 8.94/7.00 f372_0_log_ConstantStackPush(i60:0) -> f372_0_log_ConstantStackPush'(i60:0) :|: i60:0 > 1 && i60:0 > div 8.94/7.00 f372_0_log_ConstantStackPush'(i60:0) -> f372_0_log_ConstantStackPush(div) :|: i60:0 > div && i60:0 > 1 && i60:0 - 2 * div > -2 && i60:0 - 2 * div < 2 8.94/7.00 8.94/7.00 ---------------------------------------- 8.94/7.00 8.94/7.00 (8) 8.94/7.00 Obligation: 8.94/7.00 Rules: 8.94/7.00 f372_0_log_ConstantStackPush(x) -> f372_0_log_ConstantStackPush'(x) :|: x > 1 && x > x1 8.94/7.00 f372_0_log_ConstantStackPush'(x2) -> f372_0_log_ConstantStackPush(x3) :|: x2 > x3 && x2 > 1 && x2 - 2 * x3 > -2 && x2 - 2 * x3 < 2 8.94/7.00 8.94/7.00 ---------------------------------------- 8.94/7.00 8.94/7.00 (9) IRSFormatTransformerProof (EQUIVALENT) 8.94/7.00 Reformatted IRS to match normalized format (transformed away non-linear left-hand sides, !=, / and %). 8.94/7.00 ---------------------------------------- 8.94/7.00 8.94/7.00 (10) 8.94/7.00 Obligation: 8.94/7.00 Rules: 8.94/7.00 f372_0_log_ConstantStackPush(x) -> f372_0_log_ConstantStackPush'(x) :|: x > 1 && x > x1 8.94/7.00 f372_0_log_ConstantStackPush'(x2) -> f372_0_log_ConstantStackPush(x3) :|: x2 > x3 && x2 > 1 && x2 - 2 * x3 > -2 && x2 - 2 * x3 < 2 8.94/7.00 8.94/7.00 ---------------------------------------- 8.94/7.00 8.94/7.00 (11) IRSwTTerminationDigraphProof (EQUIVALENT) 8.94/7.00 Constructed termination digraph! 8.94/7.00 Nodes: 8.94/7.00 (1) f372_0_log_ConstantStackPush(x) -> f372_0_log_ConstantStackPush'(x) :|: x > 1 && x > x1 8.94/7.00 (2) f372_0_log_ConstantStackPush'(x2) -> f372_0_log_ConstantStackPush(x3) :|: x2 > x3 && x2 > 1 && x2 - 2 * x3 > -2 && x2 - 2 * x3 < 2 8.94/7.00 8.94/7.00 Arcs: 8.94/7.00 (1) -> (2) 8.94/7.00 (2) -> (1) 8.94/7.00 8.94/7.00 This digraph is fully evaluated! 8.94/7.00 ---------------------------------------- 8.94/7.00 8.94/7.00 (12) 8.94/7.00 Obligation: 8.94/7.00 8.94/7.00 Termination digraph: 8.94/7.00 Nodes: 8.94/7.00 (1) f372_0_log_ConstantStackPush(x) -> f372_0_log_ConstantStackPush'(x) :|: x > 1 && x > x1 8.94/7.00 (2) f372_0_log_ConstantStackPush'(x2) -> f372_0_log_ConstantStackPush(x3) :|: x2 > x3 && x2 > 1 && x2 - 2 * x3 > -2 && x2 - 2 * x3 < 2 8.94/7.00 8.94/7.00 Arcs: 8.94/7.00 (1) -> (2) 8.94/7.00 (2) -> (1) 8.94/7.00 8.94/7.00 This digraph is fully evaluated! 8.94/7.00 8.94/7.00 ---------------------------------------- 8.94/7.00 8.94/7.00 (13) IntTRSCompressionProof (EQUIVALENT) 8.94/7.00 Compressed rules. 8.94/7.00 ---------------------------------------- 8.94/7.00 8.94/7.00 (14) 8.94/7.00 Obligation: 8.94/7.00 Rules: 8.94/7.00 f372_0_log_ConstantStackPush(x:0) -> f372_0_log_ConstantStackPush(x3:0) :|: x:0 > x1:0 && x:0 - 2 * x3:0 < 2 && x:0 - 2 * x3:0 > -2 && x:0 > 1 && x:0 > x3:0 8.94/7.00 8.94/7.00 ---------------------------------------- 8.94/7.00 8.94/7.00 (15) FilterProof (EQUIVALENT) 8.94/7.00 Used the following sort dictionary for filtering: 8.94/7.00 f372_0_log_ConstantStackPush(INTEGER) 8.94/7.00 Replaced non-predefined constructor symbols by 0. 8.94/7.00 ---------------------------------------- 8.94/7.00 8.94/7.00 (16) 8.94/7.00 Obligation: 8.94/7.00 Rules: 8.94/7.00 f372_0_log_ConstantStackPush(x:0) -> f372_0_log_ConstantStackPush(x3:0) :|: x:0 > x1:0 && x:0 - 2 * x3:0 < 2 && x:0 - 2 * x3:0 > -2 && x:0 > 1 && x:0 > x3:0 8.94/7.00 8.94/7.00 ---------------------------------------- 8.94/7.00 8.94/7.00 (17) IntTRSCompressionProof (EQUIVALENT) 8.94/7.00 Compressed rules. 8.94/7.00 ---------------------------------------- 8.94/7.00 8.94/7.00 (18) 8.94/7.00 Obligation: 8.94/7.00 Rules: 8.94/7.00 f372_0_log_ConstantStackPush(x:0:0) -> f372_0_log_ConstantStackPush(x3:0:0) :|: x:0:0 > 1 && x:0:0 > x3:0:0 && x:0:0 - 2 * x3:0:0 > -2 && x:0:0 - 2 * x3:0:0 < 2 && x:0:0 > x1:0:0 8.94/7.00 8.94/7.00 ---------------------------------------- 8.94/7.00 8.94/7.00 (19) PolynomialOrderProcessor (EQUIVALENT) 8.94/7.00 Found the following polynomial interpretation: 8.94/7.00 [f372_0_log_ConstantStackPush(x)] = x 8.94/7.00 8.94/7.00 The following rules are decreasing: 8.94/7.00 f372_0_log_ConstantStackPush(x:0:0) -> f372_0_log_ConstantStackPush(x3:0:0) :|: x:0:0 > 1 && x:0:0 > x3:0:0 && x:0:0 - 2 * x3:0:0 > -2 && x:0:0 - 2 * x3:0:0 < 2 && x:0:0 > x1:0:0 8.94/7.00 The following rules are bounded: 8.94/7.00 f372_0_log_ConstantStackPush(x:0:0) -> f372_0_log_ConstantStackPush(x3:0:0) :|: x:0:0 > 1 && x:0:0 > x3:0:0 && x:0:0 - 2 * x3:0:0 > -2 && x:0:0 - 2 * x3:0:0 < 2 && x:0:0 > x1:0:0 8.94/7.00 8.94/7.00 ---------------------------------------- 8.94/7.00 8.94/7.00 (20) 8.94/7.00 YES 8.94/7.04 EOF