8.70/3.30 YES 8.70/3.31 proof of /export/starexec/sandbox/benchmark/theBenchmark.jar 8.70/3.31 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 8.70/3.31 8.70/3.31 8.70/3.31 termination of the given Bare JBC problem could be proven: 8.70/3.31 8.70/3.31 (0) Bare JBC problem 8.70/3.31 (1) BareJBCToJBCProof [EQUIVALENT, 94 ms] 8.70/3.31 (2) JBC problem 8.70/3.31 (3) JBCToGraph [EQUIVALENT, 176 ms] 8.70/3.31 (4) JBCTerminationGraph 8.70/3.31 (5) TerminationGraphToSCCProof [SOUND, 0 ms] 8.70/3.31 (6) JBCTerminationSCC 8.70/3.31 (7) SCCToIRSProof [SOUND, 146 ms] 8.70/3.31 (8) IRSwT 8.70/3.31 (9) IRSFormatTransformerProof [EQUIVALENT, 0 ms] 8.70/3.31 (10) IRSwT 8.70/3.31 (11) IRSwTTerminationDigraphProof [EQUIVALENT, 0 ms] 8.70/3.31 (12) TRUE 8.70/3.31 8.70/3.31 8.70/3.31 ---------------------------------------- 8.70/3.31 8.70/3.31 (0) 8.70/3.31 Obligation: 8.70/3.31 need to prove termination of the following program: 8.70/3.31 public class StupidArray { 8.70/3.31 public static void main(String[] args) { 8.70/3.31 int i = 0; 8.70/3.31 while (true) { 8.70/3.31 i = args.length + 1; 8.70/3.31 args[i] = new String(); 8.70/3.31 } 8.70/3.31 } 8.70/3.31 } 8.70/3.31 8.70/3.31 8.70/3.31 8.70/3.31 8.70/3.31 ---------------------------------------- 8.70/3.31 8.70/3.31 (1) BareJBCToJBCProof (EQUIVALENT) 8.70/3.31 initialized classpath 8.70/3.31 ---------------------------------------- 8.70/3.31 8.70/3.31 (2) 8.70/3.31 Obligation: 8.70/3.31 need to prove termination of the following program: 8.70/3.31 public class StupidArray { 8.70/3.31 public static void main(String[] args) { 8.70/3.31 int i = 0; 8.70/3.31 while (true) { 8.70/3.31 i = args.length + 1; 8.70/3.31 args[i] = new String(); 8.70/3.31 } 8.70/3.31 } 8.70/3.31 } 8.70/3.31 8.70/3.31 8.70/3.31 8.70/3.31 8.70/3.31 ---------------------------------------- 8.70/3.31 8.70/3.31 (3) JBCToGraph (EQUIVALENT) 8.70/3.31 Constructed TerminationGraph. 8.70/3.31 ---------------------------------------- 8.70/3.31 8.70/3.31 (4) 8.70/3.31 Obligation: 8.70/3.31 Termination Graph based on JBC Program: 8.70/3.31 StupidArray.main([Ljava/lang/String;)V: Graph of 56 nodes with 1 SCC. 8.70/3.31 8.70/3.31 8.70/3.31 8.70/3.31 8.70/3.31 8.70/3.31 ---------------------------------------- 8.70/3.31 8.70/3.31 (5) TerminationGraphToSCCProof (SOUND) 8.70/3.31 Splitted TerminationGraph to 1 SCCs. 8.70/3.31 ---------------------------------------- 8.70/3.31 8.70/3.31 (6) 8.70/3.31 Obligation: 8.70/3.31 SCC of termination graph based on JBC Program. 8.70/3.31 SCC contains nodes from the following methods: StupidArray.main([Ljava/lang/String;)V 8.70/3.31 SCC calls the following helper methods: 8.70/3.31 Performed SCC analyses: 8.70/3.31 *Used field analysis yielded the following read fields: 8.70/3.31 8.70/3.31 *Marker field analysis yielded the following relations that could be markers: 8.70/3.31 8.70/3.31 ---------------------------------------- 8.70/3.31 8.70/3.31 (7) SCCToIRSProof (SOUND) 8.70/3.31 Transformed FIGraph SCCs to intTRSs. Log: 8.70/3.31 Generated rules. Obtained 29 IRulesP rules: 8.70/3.31 f100_0_main_ArrayLength(EOS(STATIC_100), java.lang.Object(ARRAY(i6)), java.lang.Object(ARRAY(i6)), java.lang.Object(ARRAY(i6))) -> f101_0_main_ArrayLength(EOS(STATIC_101), java.lang.Object(ARRAY(i6)), java.lang.Object(ARRAY(i6)), java.lang.Object(ARRAY(i6))) :|: i6 >= 0 8.70/3.31 f101_0_main_ArrayLength(EOS(STATIC_101), java.lang.Object(ARRAY(i6)), java.lang.Object(ARRAY(i6)), java.lang.Object(ARRAY(i6))) -> f102_0_main_ConstantStackPush(EOS(STATIC_102), java.lang.Object(ARRAY(i6)), java.lang.Object(ARRAY(i6)), i6) :|: i6 >= 0 8.70/3.31 f102_0_main_ConstantStackPush(EOS(STATIC_102), java.lang.Object(ARRAY(i6)), java.lang.Object(ARRAY(i6)), i6) -> f104_0_main_IntArithmetic(EOS(STATIC_104), java.lang.Object(ARRAY(i6)), java.lang.Object(ARRAY(i6)), i6, 1) :|: TRUE 8.70/3.31 f104_0_main_IntArithmetic(EOS(STATIC_104), java.lang.Object(ARRAY(i6)), java.lang.Object(ARRAY(i6)), i6, matching1) -> f107_0_main_Store(EOS(STATIC_107), java.lang.Object(ARRAY(i6)), java.lang.Object(ARRAY(i6)), i6 + 1) :|: i6 >= 0 && matching1 = 1 8.70/3.31 f107_0_main_Store(EOS(STATIC_107), java.lang.Object(ARRAY(i6)), java.lang.Object(ARRAY(i6)), i7) -> f109_0_main_Load(EOS(STATIC_109), java.lang.Object(ARRAY(i6)), java.lang.Object(ARRAY(i6)), i7) :|: TRUE 8.70/3.31 f109_0_main_Load(EOS(STATIC_109), java.lang.Object(ARRAY(i6)), java.lang.Object(ARRAY(i6)), i7) -> f111_0_main_Load(EOS(STATIC_111), java.lang.Object(ARRAY(i6)), java.lang.Object(ARRAY(i6)), i7, java.lang.Object(ARRAY(i6))) :|: TRUE 8.70/3.31 f111_0_main_Load(EOS(STATIC_111), java.lang.Object(ARRAY(i6)), java.lang.Object(ARRAY(i6)), i7, java.lang.Object(ARRAY(i6))) -> f113_0_main_New(EOS(STATIC_113), java.lang.Object(ARRAY(i6)), java.lang.Object(ARRAY(i6)), java.lang.Object(ARRAY(i6)), i7) :|: TRUE 8.70/3.31 f113_0_main_New(EOS(STATIC_113), java.lang.Object(ARRAY(i6)), java.lang.Object(ARRAY(i6)), java.lang.Object(ARRAY(i6)), i7) -> f115_0_main_Duplicate(EOS(STATIC_115), java.lang.Object(ARRAY(i6)), java.lang.Object(ARRAY(i6)), java.lang.Object(ARRAY(i6)), i7, java.lang.Object(java.lang.String(EOC))) :|: TRUE 8.70/3.31 f115_0_main_Duplicate(EOS(STATIC_115), java.lang.Object(ARRAY(i6)), java.lang.Object(ARRAY(i6)), java.lang.Object(ARRAY(i6)), i7, java.lang.Object(java.lang.String(EOC))) -> f116_0_main_InvokeMethod(EOS(STATIC_116), java.lang.Object(ARRAY(i6)), java.lang.Object(ARRAY(i6)), java.lang.Object(ARRAY(i6)), i7, java.lang.Object(java.lang.String(EOC)), java.lang.Object(java.lang.String(EOC))) :|: TRUE 8.70/3.31 f116_0_main_InvokeMethod(EOS(STATIC_116), java.lang.Object(ARRAY(i6)), java.lang.Object(ARRAY(i6)), java.lang.Object(ARRAY(i6)), i7, java.lang.Object(java.lang.String(EOC)), java.lang.Object(java.lang.String(EOC))) -> f117_0__init__Load(EOS(STATIC_117), java.lang.Object(ARRAY(i6)), java.lang.Object(ARRAY(i6)), java.lang.Object(ARRAY(i6)), i7, java.lang.Object(java.lang.String(EOC)), java.lang.Object(java.lang.String(EOC))) :|: TRUE 8.70/3.31 f117_0__init__Load(EOS(STATIC_117), java.lang.Object(ARRAY(i6)), java.lang.Object(ARRAY(i6)), java.lang.Object(ARRAY(i6)), i7, java.lang.Object(java.lang.String(EOC)), java.lang.Object(java.lang.String(EOC))) -> f120_0__init__InvokeMethod(EOS(STATIC_120), java.lang.Object(ARRAY(i6)), java.lang.Object(ARRAY(i6)), java.lang.Object(ARRAY(i6)), i7, java.lang.Object(java.lang.String(EOC)), java.lang.Object(java.lang.String(EOC)), java.lang.Object(java.lang.String(EOC))) :|: TRUE 8.70/3.31 f120_0__init__InvokeMethod(EOS(STATIC_120), java.lang.Object(ARRAY(i6)), java.lang.Object(ARRAY(i6)), java.lang.Object(ARRAY(i6)), i7, java.lang.Object(java.lang.String(EOC)), java.lang.Object(java.lang.String(EOC)), java.lang.Object(java.lang.String(EOC))) -> f123_0__init__Load(EOS(STATIC_123), java.lang.Object(ARRAY(i6)), java.lang.Object(ARRAY(i6)), java.lang.Object(ARRAY(i6)), i7, java.lang.Object(java.lang.String(EOC)), java.lang.Object(java.lang.String(EOC))) :|: TRUE 8.70/3.31 f123_0__init__Load(EOS(STATIC_123), java.lang.Object(ARRAY(i6)), java.lang.Object(ARRAY(i6)), java.lang.Object(ARRAY(i6)), i7, java.lang.Object(java.lang.String(EOC)), java.lang.Object(java.lang.String(EOC))) -> f126_0__init__ConstantStackPush(EOS(STATIC_126), java.lang.Object(ARRAY(i6)), java.lang.Object(ARRAY(i6)), java.lang.Object(ARRAY(i6)), i7, java.lang.Object(java.lang.String(EOC)), java.lang.Object(java.lang.String(EOC)), java.lang.Object(java.lang.String(EOC))) :|: TRUE 8.70/3.31 f126_0__init__ConstantStackPush(EOS(STATIC_126), java.lang.Object(ARRAY(i6)), java.lang.Object(ARRAY(i6)), java.lang.Object(ARRAY(i6)), i7, java.lang.Object(java.lang.String(EOC)), java.lang.Object(java.lang.String(EOC)), java.lang.Object(java.lang.String(EOC))) -> f128_0__init__FieldAccess(EOS(STATIC_128), java.lang.Object(ARRAY(i6)), java.lang.Object(ARRAY(i6)), java.lang.Object(ARRAY(i6)), i7, java.lang.Object(java.lang.String(EOC)), java.lang.Object(java.lang.String(EOC)), java.lang.Object(java.lang.String(EOC)), 0) :|: TRUE 8.70/3.31 f128_0__init__FieldAccess(EOS(STATIC_128), java.lang.Object(ARRAY(i6)), java.lang.Object(ARRAY(i6)), java.lang.Object(ARRAY(i6)), i7, java.lang.Object(java.lang.String(EOC)), java.lang.Object(java.lang.String(EOC)), java.lang.Object(java.lang.String(EOC)), matching1) -> f129_0__init__Load(EOS(STATIC_129), java.lang.Object(ARRAY(i6)), java.lang.Object(ARRAY(i6)), java.lang.Object(ARRAY(i6)), i7, java.lang.Object(java.lang.String(EOC)), java.lang.Object(java.lang.String(EOC))) :|: TRUE && matching1 = 0 8.70/3.31 f129_0__init__Load(EOS(STATIC_129), java.lang.Object(ARRAY(i6)), java.lang.Object(ARRAY(i6)), java.lang.Object(ARRAY(i6)), i7, java.lang.Object(java.lang.String(EOC)), java.lang.Object(java.lang.String(EOC))) -> f130_0__init__ConstantStackPush(EOS(STATIC_130), java.lang.Object(ARRAY(i6)), java.lang.Object(ARRAY(i6)), java.lang.Object(ARRAY(i6)), i7, java.lang.Object(java.lang.String(EOC)), java.lang.Object(java.lang.String(EOC)), java.lang.Object(java.lang.String(EOC))) :|: TRUE 8.70/3.31 f130_0__init__ConstantStackPush(EOS(STATIC_130), java.lang.Object(ARRAY(i6)), java.lang.Object(ARRAY(i6)), java.lang.Object(ARRAY(i6)), i7, java.lang.Object(java.lang.String(EOC)), java.lang.Object(java.lang.String(EOC)), java.lang.Object(java.lang.String(EOC))) -> f132_0__init__FieldAccess(EOS(STATIC_132), java.lang.Object(ARRAY(i6)), java.lang.Object(ARRAY(i6)), java.lang.Object(ARRAY(i6)), i7, java.lang.Object(java.lang.String(EOC)), java.lang.Object(java.lang.String(EOC)), java.lang.Object(java.lang.String(EOC)), 0) :|: TRUE 8.70/3.31 f132_0__init__FieldAccess(EOS(STATIC_132), java.lang.Object(ARRAY(i6)), java.lang.Object(ARRAY(i6)), java.lang.Object(ARRAY(i6)), i7, java.lang.Object(java.lang.String(EOC)), java.lang.Object(java.lang.String(EOC)), java.lang.Object(java.lang.String(EOC)), matching1) -> f134_0__init__Load(EOS(STATIC_134), java.lang.Object(ARRAY(i6)), java.lang.Object(ARRAY(i6)), java.lang.Object(ARRAY(i6)), i7, java.lang.Object(java.lang.String(EOC)), java.lang.Object(java.lang.String(EOC))) :|: TRUE && matching1 = 0 8.70/3.31 f134_0__init__Load(EOS(STATIC_134), java.lang.Object(ARRAY(i6)), java.lang.Object(ARRAY(i6)), java.lang.Object(ARRAY(i6)), i7, java.lang.Object(java.lang.String(EOC)), java.lang.Object(java.lang.String(EOC))) -> f135_0__init__ConstantStackPush(EOS(STATIC_135), java.lang.Object(ARRAY(i6)), java.lang.Object(ARRAY(i6)), java.lang.Object(ARRAY(i6)), i7, java.lang.Object(java.lang.String(EOC)), java.lang.Object(java.lang.String(EOC))) :|: TRUE 8.70/3.31 f135_0__init__ConstantStackPush(EOS(STATIC_135), java.lang.Object(ARRAY(i6)), java.lang.Object(ARRAY(i6)), java.lang.Object(ARRAY(i6)), i7, java.lang.Object(java.lang.String(EOC)), java.lang.Object(java.lang.String(EOC))) -> f138_0__init__ArrayCreate(EOS(STATIC_138), java.lang.Object(ARRAY(i6)), java.lang.Object(ARRAY(i6)), java.lang.Object(ARRAY(i6)), i7, java.lang.Object(java.lang.String(EOC)), java.lang.Object(java.lang.String(EOC)), 0) :|: TRUE 8.70/3.31 f138_0__init__ArrayCreate(EOS(STATIC_138), java.lang.Object(ARRAY(i6)), java.lang.Object(ARRAY(i6)), java.lang.Object(ARRAY(i6)), i7, java.lang.Object(java.lang.String(EOC)), java.lang.Object(java.lang.String(EOC)), matching1) -> f140_0__init__FieldAccess(EOS(STATIC_140), java.lang.Object(ARRAY(i6)), java.lang.Object(ARRAY(i6)), java.lang.Object(ARRAY(i6)), i7, java.lang.Object(java.lang.String(EOC)), java.lang.Object(java.lang.String(EOC)), java.lang.Object(ARRAY(0))) :|: TRUE && matching1 = 0 8.70/3.31 f140_0__init__FieldAccess(EOS(STATIC_140), java.lang.Object(ARRAY(i6)), java.lang.Object(ARRAY(i6)), java.lang.Object(ARRAY(i6)), i7, java.lang.Object(java.lang.String(EOC)), java.lang.Object(java.lang.String(EOC)), java.lang.Object(ARRAY(matching1))) -> f146_0__init__Return(EOS(STATIC_146), java.lang.Object(ARRAY(i6)), java.lang.Object(ARRAY(i6)), java.lang.Object(ARRAY(i6)), i7, java.lang.Object(java.lang.String(EOC))) :|: TRUE && matching1 = 0 8.70/3.31 f146_0__init__Return(EOS(STATIC_146), java.lang.Object(ARRAY(i6)), java.lang.Object(ARRAY(i6)), java.lang.Object(ARRAY(i6)), i7, java.lang.Object(java.lang.String(EOC))) -> f148_0_main_ArrayAccess(EOS(STATIC_148), java.lang.Object(ARRAY(i6)), java.lang.Object(ARRAY(i6)), java.lang.Object(ARRAY(i6)), i7, java.lang.Object(java.lang.String(EOC))) :|: TRUE 8.70/3.31 f148_0_main_ArrayAccess(EOS(STATIC_148), java.lang.Object(ARRAY(i6)), java.lang.Object(ARRAY(i6)), java.lang.Object(ARRAY(i6)), i7, java.lang.Object(java.lang.String(EOC))) -> f151_0_main_ArrayAccess(EOS(STATIC_151), java.lang.Object(ARRAY(i6)), java.lang.Object(ARRAY(i6)), java.lang.Object(ARRAY(i6)), i7, java.lang.Object(java.lang.String(EOC))) :|: TRUE 8.70/3.31 f151_0_main_ArrayAccess(EOS(STATIC_151), java.lang.Object(ARRAY(i6)), java.lang.Object(ARRAY(i6)), java.lang.Object(ARRAY(i6)), i7, java.lang.Object(java.lang.String(EOC))) -> f154_0_main_ArrayAccess(EOS(STATIC_154), java.lang.Object(ARRAY(i6)), java.lang.Object(ARRAY(i6)), java.lang.Object(ARRAY(i6)), i7, java.lang.Object(java.lang.String(EOC))) :|: TRUE 8.70/3.31 f154_0_main_ArrayAccess(EOS(STATIC_154), java.lang.Object(ARRAY(i6)), java.lang.Object(ARRAY(i6)), java.lang.Object(ARRAY(i6)), i7, java.lang.Object(java.lang.String(EOC))) -> f160_0_main_JMP(EOS(STATIC_160), java.lang.Object(ARRAY(i6)), java.lang.Object(ARRAY(i6))) :|: i7 < i6 8.70/3.31 f160_0_main_JMP(EOS(STATIC_160), java.lang.Object(ARRAY(i6)), java.lang.Object(ARRAY(i6))) -> f176_0_main_Load(EOS(STATIC_176), java.lang.Object(ARRAY(i6)), java.lang.Object(ARRAY(i6))) :|: TRUE 8.70/3.31 f176_0_main_Load(EOS(STATIC_176), java.lang.Object(ARRAY(i6)), java.lang.Object(ARRAY(i6))) -> f95_0_main_Load(EOS(STATIC_95), java.lang.Object(ARRAY(i6)), java.lang.Object(ARRAY(i6))) :|: TRUE 8.70/3.31 f95_0_main_Load(EOS(STATIC_95), java.lang.Object(o8sub), java.lang.Object(o8sub)) -> f100_0_main_ArrayLength(EOS(STATIC_100), java.lang.Object(o8sub), java.lang.Object(o8sub), java.lang.Object(o8sub)) :|: TRUE 8.70/3.31 Combined rules. Obtained 1 IRulesP rules: 8.70/3.31 f100_0_main_ArrayLength(EOS(STATIC_100), java.lang.Object(ARRAY(i6:0)), java.lang.Object(ARRAY(i6:0)), java.lang.Object(ARRAY(i6:0))) -> f100_0_main_ArrayLength(EOS(STATIC_100), java.lang.Object(ARRAY(i6:0)), java.lang.Object(ARRAY(i6:0)), java.lang.Object(ARRAY(i6:0))) :|: i6:0 > -1 && i6:0 + 1 < i6:0 8.70/3.31 Filtered constant ground arguments: 8.70/3.31 f100_0_main_ArrayLength(x1, x2, x3, x4) -> f100_0_main_ArrayLength(x2, x3, x4) 8.70/3.31 EOS(x1) -> EOS 8.70/3.31 Filtered duplicate arguments: 8.70/3.31 f100_0_main_ArrayLength(x1, x2, x3) -> f100_0_main_ArrayLength(x3) 8.70/3.31 Finished conversion. Obtained 1 rules.P rules: 8.70/3.31 f100_0_main_ArrayLength(java.lang.Object(ARRAY(i6:0)), i6:0) -> f100_0_main_ArrayLength(java.lang.Object(ARRAY(i6:0)), i6:0) :|: i6:0 > -1 && i6:0 + 1 < i6:0 8.70/3.31 8.70/3.31 ---------------------------------------- 8.70/3.31 8.70/3.31 (8) 8.70/3.31 Obligation: 8.70/3.31 Rules: 8.70/3.31 f100_0_main_ArrayLength(java.lang.Object(ARRAY(i6:0)), i6:0) -> f100_0_main_ArrayLength(java.lang.Object(ARRAY(i6:0)), i6:0) :|: i6:0 > -1 && i6:0 + 1 < i6:0 8.70/3.31 8.70/3.31 ---------------------------------------- 8.70/3.31 8.70/3.31 (9) IRSFormatTransformerProof (EQUIVALENT) 8.70/3.31 Reformatted IRS to match normalized format (transformed away non-linear left-hand sides, !=, / and %). 8.70/3.31 ---------------------------------------- 8.70/3.31 8.70/3.31 (10) 8.70/3.31 Obligation: 8.70/3.31 Rules: 8.70/3.31 f100_0_main_ArrayLength(java.lang.Object(ARRAY(i6:0)), i6:0) -> f100_0_main_ArrayLength(java.lang.Object(ARRAY(i6:0)), i6:0) :|: i6:0 > -1 && i6:0 + 1 < i6:0 8.70/3.31 8.70/3.31 ---------------------------------------- 8.70/3.31 8.70/3.31 (11) IRSwTTerminationDigraphProof (EQUIVALENT) 8.70/3.31 Constructed termination digraph! 8.70/3.31 Nodes: 8.70/3.31 (1) f100_0_main_ArrayLength(java.lang.Object(ARRAY(i6:0)), i6:0) -> f100_0_main_ArrayLength(java.lang.Object(ARRAY(i6:0)), i6:0) :|: i6:0 > -1 && i6:0 + 1 < i6:0 8.70/3.31 8.70/3.31 No arcs! 8.70/3.31 8.70/3.31 This digraph is fully evaluated! 8.70/3.31 ---------------------------------------- 8.70/3.31 8.70/3.31 (12) 8.70/3.31 TRUE 8.85/3.40 EOF