/export/starexec/sandbox2/solver/bin/starexec_run_standard /export/starexec/sandbox2/benchmark/theBenchmark.jar /export/starexec/sandbox2/output/output_files -------------------------------------------------------------------------------- YES proof of /export/starexec/sandbox2/benchmark/theBenchmark.jar # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty termination of the given Bare JBC problem could be proven: (0) Bare JBC problem (1) BareJBCToJBCProof [EQUIVALENT, 96 ms] (2) JBC problem (3) JBCToGraph [EQUIVALENT, 335 ms] (4) JBCTerminationGraph (5) TerminationGraphToSCCProof [SOUND, 0 ms] (6) JBCTerminationSCC (7) SCCToIRSProof [SOUND, 123 ms] (8) IRSwT (9) IRSFormatTransformerProof [EQUIVALENT, 0 ms] (10) IRSwT (11) IRSwTTerminationDigraphProof [EQUIVALENT, 13 ms] (12) IRSwT (13) IntTRSCompressionProof [EQUIVALENT, 0 ms] (14) IRSwT (15) TempFilterProof [SOUND, 52 ms] (16) IntTRS (17) PolynomialOrderProcessor [EQUIVALENT, 18 ms] (18) YES ---------------------------------------- (0) Obligation: need to prove termination of the following program: /** * Java can do infinite data objects, too. * Here we take the first n elements from an * ascending infinite list of integer numbers. * * @author Carsten Fuhs */ public class Take { public static int[] take(int n, MyIterator f) { int[] result = new int[n]; for (int i = 0; i < n; ++i) { if (f.hasNext()) { result[i] = f.next(); } else { break; } } return result; } public static void main(String args[]) { int start = args[0].length(); int howMany = args[1].length(); From f = new From(start); int[] firstHowMany = take(howMany, f); } } interface MyIterator { boolean hasNext(); int next(); } class From implements MyIterator { private int current; public From(int start) { this.current = start; } public boolean hasNext() { return true; } public int next() { return current++; } } ---------------------------------------- (1) BareJBCToJBCProof (EQUIVALENT) initialized classpath ---------------------------------------- (2) Obligation: need to prove termination of the following program: /** * Java can do infinite data objects, too. * Here we take the first n elements from an * ascending infinite list of integer numbers. * * @author Carsten Fuhs */ public class Take { public static int[] take(int n, MyIterator f) { int[] result = new int[n]; for (int i = 0; i < n; ++i) { if (f.hasNext()) { result[i] = f.next(); } else { break; } } return result; } public static void main(String args[]) { int start = args[0].length(); int howMany = args[1].length(); From f = new From(start); int[] firstHowMany = take(howMany, f); } } interface MyIterator { boolean hasNext(); int next(); } class From implements MyIterator { private int current; public From(int start) { this.current = start; } public boolean hasNext() { return true; } public int next() { return current++; } } ---------------------------------------- (3) JBCToGraph (EQUIVALENT) Constructed TerminationGraph. ---------------------------------------- (4) Obligation: Termination Graph based on JBC Program: Take.main([Ljava/lang/String;)V: Graph of 194 nodes with 1 SCC. ---------------------------------------- (5) TerminationGraphToSCCProof (SOUND) Splitted TerminationGraph to 1 SCCs. ---------------------------------------- (6) Obligation: SCC of termination graph based on JBC Program. SCC contains nodes from the following methods: Take.main([Ljava/lang/String;)V SCC calls the following helper methods: Performed SCC analyses: *Used field analysis yielded the following read fields: *From: [current] *Marker field analysis yielded the following relations that could be markers: ---------------------------------------- (7) SCCToIRSProof (SOUND) Transformed FIGraph SCCs to intTRSs. Log: Generated rules. Obtained 26 IRulesP rules: f710_0_take_Load(EOS(STATIC_710), i79, java.lang.Object(From(EOC, i80)), java.lang.Object(ARRAY(i79)), i81, i81) -> f713_0_take_GE(EOS(STATIC_713), i79, java.lang.Object(From(EOC, i80)), java.lang.Object(ARRAY(i79)), i81, i81, i79) :|: TRUE f713_0_take_GE(EOS(STATIC_713), i79, java.lang.Object(From(EOC, i80)), java.lang.Object(ARRAY(i79)), i81, i81, i79) -> f738_0_take_GE(EOS(STATIC_738), i79, java.lang.Object(From(EOC, i80)), java.lang.Object(ARRAY(i79)), i81, i81, i79) :|: i81 < i79 f738_0_take_GE(EOS(STATIC_738), i79, java.lang.Object(From(EOC, i80)), java.lang.Object(ARRAY(i79)), i81, i81, i79) -> f763_0_take_Load(EOS(STATIC_763), i79, java.lang.Object(From(EOC, i80)), java.lang.Object(ARRAY(i79)), i81) :|: i81 < i79 f763_0_take_Load(EOS(STATIC_763), i79, java.lang.Object(From(EOC, i80)), java.lang.Object(ARRAY(i79)), i81) -> f768_0_take_InvokeMethod(EOS(STATIC_768), i79, java.lang.Object(From(EOC, i80)), java.lang.Object(ARRAY(i79)), i81, java.lang.Object(From(EOC, i80))) :|: TRUE f768_0_take_InvokeMethod(EOS(STATIC_768), i79, java.lang.Object(From(EOC, i80)), java.lang.Object(ARRAY(i79)), i81, java.lang.Object(From(EOC, i80))) -> f771_0_hasNext_ConstantStackPush(EOS(STATIC_771), i79, java.lang.Object(From(EOC, i80)), java.lang.Object(ARRAY(i79)), i81) :|: TRUE f771_0_hasNext_ConstantStackPush(EOS(STATIC_771), i79, java.lang.Object(From(EOC, i80)), java.lang.Object(ARRAY(i79)), i81) -> f774_0_hasNext_Return(EOS(STATIC_774), i79, java.lang.Object(From(EOC, i80)), java.lang.Object(ARRAY(i79)), i81, 1) :|: TRUE f774_0_hasNext_Return(EOS(STATIC_774), i79, java.lang.Object(From(EOC, i80)), java.lang.Object(ARRAY(i79)), i81, matching1) -> f777_0_take_EQ(EOS(STATIC_777), i79, java.lang.Object(From(EOC, i80)), java.lang.Object(ARRAY(i79)), i81, 1) :|: TRUE && matching1 = 1 f777_0_take_EQ(EOS(STATIC_777), i79, java.lang.Object(From(EOC, i80)), java.lang.Object(ARRAY(i79)), i81, matching1) -> f778_0_take_Load(EOS(STATIC_778), i79, java.lang.Object(From(EOC, i80)), java.lang.Object(ARRAY(i79)), i81) :|: 1 > 0 && matching1 = 1 f778_0_take_Load(EOS(STATIC_778), i79, java.lang.Object(From(EOC, i80)), java.lang.Object(ARRAY(i79)), i81) -> f779_0_take_Load(EOS(STATIC_779), i79, java.lang.Object(From(EOC, i80)), java.lang.Object(ARRAY(i79)), i81, java.lang.Object(ARRAY(i79))) :|: TRUE f779_0_take_Load(EOS(STATIC_779), i79, java.lang.Object(From(EOC, i80)), java.lang.Object(ARRAY(i79)), i81, java.lang.Object(ARRAY(i79))) -> f780_0_take_Load(EOS(STATIC_780), i79, java.lang.Object(From(EOC, i80)), java.lang.Object(ARRAY(i79)), i81, java.lang.Object(ARRAY(i79)), i81) :|: TRUE f780_0_take_Load(EOS(STATIC_780), i79, java.lang.Object(From(EOC, i80)), java.lang.Object(ARRAY(i79)), i81, java.lang.Object(ARRAY(i79)), i81) -> f782_0_take_InvokeMethod(EOS(STATIC_782), i79, java.lang.Object(From(EOC, i80)), java.lang.Object(ARRAY(i79)), i81, java.lang.Object(ARRAY(i79)), i81, java.lang.Object(From(EOC, i80))) :|: TRUE f782_0_take_InvokeMethod(EOS(STATIC_782), i79, java.lang.Object(From(EOC, i80)), java.lang.Object(ARRAY(i79)), i81, java.lang.Object(ARRAY(i79)), i81, java.lang.Object(From(EOC, i80))) -> f783_0_next_Load(EOS(STATIC_783), i79, java.lang.Object(From(EOC, i80)), java.lang.Object(ARRAY(i79)), i81, java.lang.Object(ARRAY(i79)), i81, java.lang.Object(From(EOC, i80))) :|: TRUE f783_0_next_Load(EOS(STATIC_783), i79, java.lang.Object(From(EOC, i80)), java.lang.Object(ARRAY(i79)), i81, java.lang.Object(ARRAY(i79)), i81, java.lang.Object(From(EOC, i80))) -> f784_0_next_Duplicate(EOS(STATIC_784), i79, java.lang.Object(From(EOC, i80)), java.lang.Object(ARRAY(i79)), i81, java.lang.Object(ARRAY(i79)), i81, java.lang.Object(From(EOC, i80))) :|: TRUE f784_0_next_Duplicate(EOS(STATIC_784), i79, java.lang.Object(From(EOC, i80)), java.lang.Object(ARRAY(i79)), i81, java.lang.Object(ARRAY(i79)), i81, java.lang.Object(From(EOC, i80))) -> f785_0_next_FieldAccess(EOS(STATIC_785), i79, java.lang.Object(From(EOC, i80)), java.lang.Object(ARRAY(i79)), i81, java.lang.Object(ARRAY(i79)), i81, java.lang.Object(From(EOC, i80)), java.lang.Object(From(EOC, i80))) :|: TRUE f785_0_next_FieldAccess(EOS(STATIC_785), i79, java.lang.Object(From(EOC, i80)), java.lang.Object(ARRAY(i79)), i81, java.lang.Object(ARRAY(i79)), i81, java.lang.Object(From(EOC, i80)), java.lang.Object(From(EOC, i80))) -> f786_0_next_Duplicate(EOS(STATIC_786), i79, java.lang.Object(From(EOC, i80)), java.lang.Object(ARRAY(i79)), i81, java.lang.Object(ARRAY(i79)), i81, java.lang.Object(From(EOC, i80)), i80) :|: TRUE f786_0_next_Duplicate(EOS(STATIC_786), i79, java.lang.Object(From(EOC, i80)), java.lang.Object(ARRAY(i79)), i81, java.lang.Object(ARRAY(i79)), i81, java.lang.Object(From(EOC, i80)), i80) -> f787_0_next_ConstantStackPush(EOS(STATIC_787), i79, java.lang.Object(From(EOC, i80)), java.lang.Object(ARRAY(i79)), i81, java.lang.Object(ARRAY(i79)), i81, i80, java.lang.Object(From(EOC, i80)), i80) :|: TRUE f787_0_next_ConstantStackPush(EOS(STATIC_787), i79, java.lang.Object(From(EOC, i80)), java.lang.Object(ARRAY(i79)), i81, java.lang.Object(ARRAY(i79)), i81, i80, java.lang.Object(From(EOC, i80)), i80) -> f788_0_next_IntArithmetic(EOS(STATIC_788), i79, java.lang.Object(From(EOC, i80)), java.lang.Object(ARRAY(i79)), i81, java.lang.Object(ARRAY(i79)), i81, i80, java.lang.Object(From(EOC, i80)), i80, 1) :|: TRUE f788_0_next_IntArithmetic(EOS(STATIC_788), i79, java.lang.Object(From(EOC, i80)), java.lang.Object(ARRAY(i79)), i81, java.lang.Object(ARRAY(i79)), i81, i80, java.lang.Object(From(EOC, i80)), i80, matching1) -> f789_0_next_FieldAccess(EOS(STATIC_789), i79, java.lang.Object(From(EOC, i80)), java.lang.Object(ARRAY(i79)), i81, java.lang.Object(ARRAY(i79)), i81, i80, java.lang.Object(From(EOC, i80)), i80 + 1) :|: i80 >= 0 && matching1 = 1 f789_0_next_FieldAccess(EOS(STATIC_789), i79, java.lang.Object(From(EOC, i80)), java.lang.Object(ARRAY(i79)), i81, java.lang.Object(ARRAY(i79)), i81, i80, java.lang.Object(From(EOC, i80)), i96) -> f790_0_next_Return(EOS(STATIC_790), i79, java.lang.Object(From(EOC, i96)), java.lang.Object(ARRAY(i79)), i81, java.lang.Object(ARRAY(i79)), i81, i80) :|: TRUE f790_0_next_Return(EOS(STATIC_790), i79, java.lang.Object(From(EOC, i96)), java.lang.Object(ARRAY(i79)), i81, java.lang.Object(ARRAY(i79)), i81, i80) -> f791_0_take_ArrayAccess(EOS(STATIC_791), i79, java.lang.Object(From(EOC, i96)), java.lang.Object(ARRAY(i79)), i81, java.lang.Object(ARRAY(i79)), i81, i80) :|: TRUE f791_0_take_ArrayAccess(EOS(STATIC_791), i79, java.lang.Object(From(EOC, i96)), java.lang.Object(ARRAY(i79)), i81, java.lang.Object(ARRAY(i79)), i81, i80) -> f792_0_take_ArrayAccess(EOS(STATIC_792), i79, java.lang.Object(From(EOC, i96)), java.lang.Object(ARRAY(i79)), i81, java.lang.Object(ARRAY(i79)), i81, i80) :|: TRUE f792_0_take_ArrayAccess(EOS(STATIC_792), i79, java.lang.Object(From(EOC, i96)), java.lang.Object(ARRAY(i79)), i81, java.lang.Object(ARRAY(i79)), i81, i80) -> f794_0_take_Inc(EOS(STATIC_794), i79, java.lang.Object(From(EOC, i96)), java.lang.Object(ARRAY(i79)), i81) :|: i81 < i79 f794_0_take_Inc(EOS(STATIC_794), i79, java.lang.Object(From(EOC, i96)), java.lang.Object(ARRAY(i79)), i81) -> f796_0_take_JMP(EOS(STATIC_796), i79, java.lang.Object(From(EOC, i96)), java.lang.Object(ARRAY(i79)), i81 + 1) :|: TRUE f796_0_take_JMP(EOS(STATIC_796), i79, java.lang.Object(From(EOC, i96)), java.lang.Object(ARRAY(i79)), i97) -> f819_0_take_Load(EOS(STATIC_819), i79, java.lang.Object(From(EOC, i96)), java.lang.Object(ARRAY(i79)), i97) :|: TRUE f819_0_take_Load(EOS(STATIC_819), i79, java.lang.Object(From(EOC, i96)), java.lang.Object(ARRAY(i79)), i97) -> f704_0_take_Load(EOS(STATIC_704), i79, java.lang.Object(From(EOC, i96)), java.lang.Object(ARRAY(i79)), i97) :|: TRUE f704_0_take_Load(EOS(STATIC_704), i79, java.lang.Object(From(EOC, i80)), java.lang.Object(ARRAY(i79)), i81) -> f710_0_take_Load(EOS(STATIC_710), i79, java.lang.Object(From(EOC, i80)), java.lang.Object(ARRAY(i79)), i81, i81) :|: TRUE Combined rules. Obtained 1 IRulesP rules: f710_0_take_Load(EOS(STATIC_710), i79:0, java.lang.Object(From(EOC, i80:0)), java.lang.Object(ARRAY(i79:0)), i81:0, i81:0) -> f710_0_take_Load(EOS(STATIC_710), i79:0, java.lang.Object(From(EOC, i80:0 + 1)), java.lang.Object(ARRAY(i79:0)), i81:0 + 1, i81:0 + 1) :|: i81:0 < i79:0 && i80:0 > -1 Filtered constant ground arguments: f710_0_take_Load(x1, x2, x3, x4, x5, x6) -> f710_0_take_Load(x2, x3, x4, x5, x6) EOS(x1) -> EOS From(x1, x2) -> From(x2) Filtered duplicate arguments: f710_0_take_Load(x1, x2, x3, x4, x5) -> f710_0_take_Load(x1, x2, x3, x5) Finished conversion. Obtained 1 rules.P rules: f710_0_take_Load(i79:0, java.lang.Object(From(i80:0)), java.lang.Object(ARRAY(i79:0)), i81:0, i80:0, i79:0) -> f710_0_take_Load(i79:0, java.lang.Object(From(i80:0 + 1)), java.lang.Object(ARRAY(i79:0)), i81:0 + 1, i80:0 + 1, i79:0) :|: i81:0 < i79:0 && i80:0 > -1 ---------------------------------------- (8) Obligation: Rules: f710_0_take_Load(i79:0, java.lang.Object(From(i80:0)), java.lang.Object(ARRAY(i79:0)), i81:0, i80:0, i79:0) -> f710_0_take_Load(i79:0, java.lang.Object(From(i80:0 + 1)), java.lang.Object(ARRAY(i79:0)), i81:0 + 1, i80:0 + 1, i79:0) :|: i81:0 < i79:0 && i80:0 > -1 ---------------------------------------- (9) IRSFormatTransformerProof (EQUIVALENT) Reformatted IRS to match normalized format (transformed away non-linear left-hand sides, !=, / and %). ---------------------------------------- (10) Obligation: Rules: f710_0_take_Load(i79:0, java.lang.Object(From(i80:0)), java.lang.Object(ARRAY(i79:0)), i81:0, i80:0, i79:0) -> f710_0_take_Load(i79:0, java.lang.Object(From(arith1)), java.lang.Object(ARRAY(i79:0)), arith, arith1, i79:0) :|: i81:0 < i79:0 && i80:0 > -1 && arith = i81:0 + 1 && arith1 = i80:0 + 1 && arith1 = i80:0 + 1 ---------------------------------------- (11) IRSwTTerminationDigraphProof (EQUIVALENT) Constructed termination digraph! Nodes: (1) f710_0_take_Load(i79:0, java.lang.Object(From(i80:0)), java.lang.Object(ARRAY(i79:0)), i81:0, i80:0, i79:0) -> f710_0_take_Load(i79:0, java.lang.Object(From(arith1)), java.lang.Object(ARRAY(i79:0)), arith, arith1, i79:0) :|: i81:0 < i79:0 && i80:0 > -1 && arith = i81:0 + 1 && arith1 = i80:0 + 1 && arith1 = i80:0 + 1 Arcs: (1) -> (1) This digraph is fully evaluated! ---------------------------------------- (12) Obligation: Termination digraph: Nodes: (1) f710_0_take_Load(i79:0, java.lang.Object(From(i80:0)), java.lang.Object(ARRAY(i79:0)), i81:0, i80:0, i79:0) -> f710_0_take_Load(i79:0, java.lang.Object(From(arith1)), java.lang.Object(ARRAY(i79:0)), arith, arith1, i79:0) :|: i81:0 < i79:0 && i80:0 > -1 && arith = i81:0 + 1 && arith1 = i80:0 + 1 && arith1 = i80:0 + 1 Arcs: (1) -> (1) This digraph is fully evaluated! ---------------------------------------- (13) IntTRSCompressionProof (EQUIVALENT) Compressed rules. ---------------------------------------- (14) Obligation: Rules: f710_0_take_Load(i79:0:0, java.lang.Object(From(i80:0:0)), java.lang.Object(ARRAY(i79:0:0)), i81:0:0, i80:0:0, i79:0:0) -> f710_0_take_Load(i79:0:0, java.lang.Object(From(i80:0:0 + 1)), java.lang.Object(ARRAY(i79:0:0)), i81:0:0 + 1, i80:0:0 + 1, i79:0:0) :|: i81:0:0 < i79:0:0 && i80:0:0 > -1 ---------------------------------------- (15) TempFilterProof (SOUND) Used the following sort dictionary for filtering: f710_0_take_Load(INTEGER, VARIABLE, VARIABLE, INTEGER, INTEGER, INTEGER) java.lang.Object(VARIABLE) From(INTEGER) ARRAY(INTEGER) Replaced non-predefined constructor symbols by 0. ---------------------------------------- (16) Obligation: Rules: f710_0_take_Load(i79:0:0, c, c1, i81:0:0, i80:0:0, i79:0:0) -> f710_0_take_Load(i79:0:0, c2, c3, c4, c5, i79:0:0) :|: c5 = i80:0:0 + 1 && (c4 = i81:0:0 + 1 && (c3 = 0 && (c2 = 0 && (c1 = 0 && c = 0)))) && (i81:0:0 < i79:0:0 && i80:0:0 > -1) ---------------------------------------- (17) PolynomialOrderProcessor (EQUIVALENT) Found the following polynomial interpretation: [f710_0_take_Load(x, x1, x2, x3, x4, x5)] = x + c1*x1 + c2*x2 - x3 The following rules are decreasing: f710_0_take_Load(i79:0:0, c, c1, i81:0:0, i80:0:0, i79:0:0) -> f710_0_take_Load(i79:0:0, c2, c3, c4, c5, i79:0:0) :|: c5 = i80:0:0 + 1 && (c4 = i81:0:0 + 1 && (c3 = 0 && (c2 = 0 && (c1 = 0 && c = 0)))) && (i81:0:0 < i79:0:0 && i80:0:0 > -1) The following rules are bounded: f710_0_take_Load(i79:0:0, c, c1, i81:0:0, i80:0:0, i79:0:0) -> f710_0_take_Load(i79:0:0, c2, c3, c4, c5, i79:0:0) :|: c5 = i80:0:0 + 1 && (c4 = i81:0:0 + 1 && (c3 = 0 && (c2 = 0 && (c1 = 0 && c = 0)))) && (i81:0:0 < i79:0:0 && i80:0:0 > -1) ---------------------------------------- (18) YES