/export/starexec/sandbox/solver/bin/starexec_run_standard /export/starexec/sandbox/benchmark/theBenchmark.jar /export/starexec/sandbox/output/output_files -------------------------------------------------------------------------------- YES proof of /export/starexec/sandbox/benchmark/theBenchmark.jar # AProVE Commit ID: 794c25de1cacf0d048858bcd21c9a779e1221865 marcel 20200619 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, 336 ms] (4) JBCTerminationGraph (5) TerminationGraphToSCCProof [SOUND, 0 ms] (6) JBCTerminationSCC (7) SCCToIRSProof [SOUND, 94 ms] (8) IRSwT (9) IRSFormatTransformerProof [EQUIVALENT, 0 ms] (10) IRSwT (11) IRSwTTerminationDigraphProof [EQUIVALENT, 6 ms] (12) IRSwT (13) IntTRSCompressionProof [EQUIVALENT, 0 ms] (14) IRSwT (15) TempFilterProof [SOUND, 47 ms] (16) IntTRS (17) PolynomialOrderProcessor [EQUIVALENT, 8 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: f712_0_take_Load(EOS(STATIC_712), i80, java.lang.Object(From(EOC, i81)), java.lang.Object(ARRAY(i80)), i82, i82) -> f714_0_take_GE(EOS(STATIC_714), i80, java.lang.Object(From(EOC, i81)), java.lang.Object(ARRAY(i80)), i82, i82, i80) :|: TRUE f714_0_take_GE(EOS(STATIC_714), i80, java.lang.Object(From(EOC, i81)), java.lang.Object(ARRAY(i80)), i82, i82, i80) -> f732_0_take_GE(EOS(STATIC_732), i80, java.lang.Object(From(EOC, i81)), java.lang.Object(ARRAY(i80)), i82, i82, i80) :|: i82 < i80 f732_0_take_GE(EOS(STATIC_732), i80, java.lang.Object(From(EOC, i81)), java.lang.Object(ARRAY(i80)), i82, i82, i80) -> f739_0_take_Load(EOS(STATIC_739), i80, java.lang.Object(From(EOC, i81)), java.lang.Object(ARRAY(i80)), i82) :|: i82 < i80 f739_0_take_Load(EOS(STATIC_739), i80, java.lang.Object(From(EOC, i81)), java.lang.Object(ARRAY(i80)), i82) -> f742_0_take_InvokeMethod(EOS(STATIC_742), i80, java.lang.Object(From(EOC, i81)), java.lang.Object(ARRAY(i80)), i82, java.lang.Object(From(EOC, i81))) :|: TRUE f742_0_take_InvokeMethod(EOS(STATIC_742), i80, java.lang.Object(From(EOC, i81)), java.lang.Object(ARRAY(i80)), i82, java.lang.Object(From(EOC, i81))) -> f746_0_hasNext_ConstantStackPush(EOS(STATIC_746), i80, java.lang.Object(From(EOC, i81)), java.lang.Object(ARRAY(i80)), i82) :|: TRUE f746_0_hasNext_ConstantStackPush(EOS(STATIC_746), i80, java.lang.Object(From(EOC, i81)), java.lang.Object(ARRAY(i80)), i82) -> f752_0_hasNext_Return(EOS(STATIC_752), i80, java.lang.Object(From(EOC, i81)), java.lang.Object(ARRAY(i80)), i82, 1) :|: TRUE f752_0_hasNext_Return(EOS(STATIC_752), i80, java.lang.Object(From(EOC, i81)), java.lang.Object(ARRAY(i80)), i82, matching1) -> f755_0_take_EQ(EOS(STATIC_755), i80, java.lang.Object(From(EOC, i81)), java.lang.Object(ARRAY(i80)), i82, 1) :|: TRUE && matching1 = 1 f755_0_take_EQ(EOS(STATIC_755), i80, java.lang.Object(From(EOC, i81)), java.lang.Object(ARRAY(i80)), i82, matching1) -> f757_0_take_Load(EOS(STATIC_757), i80, java.lang.Object(From(EOC, i81)), java.lang.Object(ARRAY(i80)), i82) :|: 1 > 0 && matching1 = 1 f757_0_take_Load(EOS(STATIC_757), i80, java.lang.Object(From(EOC, i81)), java.lang.Object(ARRAY(i80)), i82) -> f759_0_take_Load(EOS(STATIC_759), i80, java.lang.Object(From(EOC, i81)), java.lang.Object(ARRAY(i80)), i82, java.lang.Object(ARRAY(i80))) :|: TRUE f759_0_take_Load(EOS(STATIC_759), i80, java.lang.Object(From(EOC, i81)), java.lang.Object(ARRAY(i80)), i82, java.lang.Object(ARRAY(i80))) -> f762_0_take_Load(EOS(STATIC_762), i80, java.lang.Object(From(EOC, i81)), java.lang.Object(ARRAY(i80)), i82, java.lang.Object(ARRAY(i80)), i82) :|: TRUE f762_0_take_Load(EOS(STATIC_762), i80, java.lang.Object(From(EOC, i81)), java.lang.Object(ARRAY(i80)), i82, java.lang.Object(ARRAY(i80)), i82) -> f764_0_take_InvokeMethod(EOS(STATIC_764), i80, java.lang.Object(From(EOC, i81)), java.lang.Object(ARRAY(i80)), i82, java.lang.Object(ARRAY(i80)), i82, java.lang.Object(From(EOC, i81))) :|: TRUE f764_0_take_InvokeMethod(EOS(STATIC_764), i80, java.lang.Object(From(EOC, i81)), java.lang.Object(ARRAY(i80)), i82, java.lang.Object(ARRAY(i80)), i82, java.lang.Object(From(EOC, i81))) -> f766_0_next_Load(EOS(STATIC_766), i80, java.lang.Object(From(EOC, i81)), java.lang.Object(ARRAY(i80)), i82, java.lang.Object(ARRAY(i80)), i82, java.lang.Object(From(EOC, i81))) :|: TRUE f766_0_next_Load(EOS(STATIC_766), i80, java.lang.Object(From(EOC, i81)), java.lang.Object(ARRAY(i80)), i82, java.lang.Object(ARRAY(i80)), i82, java.lang.Object(From(EOC, i81))) -> f769_0_next_Duplicate(EOS(STATIC_769), i80, java.lang.Object(From(EOC, i81)), java.lang.Object(ARRAY(i80)), i82, java.lang.Object(ARRAY(i80)), i82, java.lang.Object(From(EOC, i81))) :|: TRUE f769_0_next_Duplicate(EOS(STATIC_769), i80, java.lang.Object(From(EOC, i81)), java.lang.Object(ARRAY(i80)), i82, java.lang.Object(ARRAY(i80)), i82, java.lang.Object(From(EOC, i81))) -> f771_0_next_FieldAccess(EOS(STATIC_771), i80, java.lang.Object(From(EOC, i81)), java.lang.Object(ARRAY(i80)), i82, java.lang.Object(ARRAY(i80)), i82, java.lang.Object(From(EOC, i81)), java.lang.Object(From(EOC, i81))) :|: TRUE f771_0_next_FieldAccess(EOS(STATIC_771), i80, java.lang.Object(From(EOC, i81)), java.lang.Object(ARRAY(i80)), i82, java.lang.Object(ARRAY(i80)), i82, java.lang.Object(From(EOC, i81)), java.lang.Object(From(EOC, i81))) -> f773_0_next_Duplicate(EOS(STATIC_773), i80, java.lang.Object(From(EOC, i81)), java.lang.Object(ARRAY(i80)), i82, java.lang.Object(ARRAY(i80)), i82, java.lang.Object(From(EOC, i81)), i81) :|: TRUE f773_0_next_Duplicate(EOS(STATIC_773), i80, java.lang.Object(From(EOC, i81)), java.lang.Object(ARRAY(i80)), i82, java.lang.Object(ARRAY(i80)), i82, java.lang.Object(From(EOC, i81)), i81) -> f776_0_next_ConstantStackPush(EOS(STATIC_776), i80, java.lang.Object(From(EOC, i81)), java.lang.Object(ARRAY(i80)), i82, java.lang.Object(ARRAY(i80)), i82, i81, java.lang.Object(From(EOC, i81)), i81) :|: TRUE f776_0_next_ConstantStackPush(EOS(STATIC_776), i80, java.lang.Object(From(EOC, i81)), java.lang.Object(ARRAY(i80)), i82, java.lang.Object(ARRAY(i80)), i82, i81, java.lang.Object(From(EOC, i81)), i81) -> f778_0_next_IntArithmetic(EOS(STATIC_778), i80, java.lang.Object(From(EOC, i81)), java.lang.Object(ARRAY(i80)), i82, java.lang.Object(ARRAY(i80)), i82, i81, java.lang.Object(From(EOC, i81)), i81, 1) :|: TRUE f778_0_next_IntArithmetic(EOS(STATIC_778), i80, java.lang.Object(From(EOC, i81)), java.lang.Object(ARRAY(i80)), i82, java.lang.Object(ARRAY(i80)), i82, i81, java.lang.Object(From(EOC, i81)), i81, matching1) -> f779_0_next_FieldAccess(EOS(STATIC_779), i80, java.lang.Object(From(EOC, i81)), java.lang.Object(ARRAY(i80)), i82, java.lang.Object(ARRAY(i80)), i82, i81, java.lang.Object(From(EOC, i81)), i81 + 1) :|: i81 >= 0 && matching1 = 1 f779_0_next_FieldAccess(EOS(STATIC_779), i80, java.lang.Object(From(EOC, i81)), java.lang.Object(ARRAY(i80)), i82, java.lang.Object(ARRAY(i80)), i82, i81, java.lang.Object(From(EOC, i81)), i95) -> f782_0_next_Return(EOS(STATIC_782), i80, java.lang.Object(From(EOC, i95)), java.lang.Object(ARRAY(i80)), i82, java.lang.Object(ARRAY(i80)), i82, i81) :|: TRUE f782_0_next_Return(EOS(STATIC_782), i80, java.lang.Object(From(EOC, i95)), java.lang.Object(ARRAY(i80)), i82, java.lang.Object(ARRAY(i80)), i82, i81) -> f784_0_take_ArrayAccess(EOS(STATIC_784), i80, java.lang.Object(From(EOC, i95)), java.lang.Object(ARRAY(i80)), i82, java.lang.Object(ARRAY(i80)), i82, i81) :|: TRUE f784_0_take_ArrayAccess(EOS(STATIC_784), i80, java.lang.Object(From(EOC, i95)), java.lang.Object(ARRAY(i80)), i82, java.lang.Object(ARRAY(i80)), i82, i81) -> f787_0_take_ArrayAccess(EOS(STATIC_787), i80, java.lang.Object(From(EOC, i95)), java.lang.Object(ARRAY(i80)), i82, java.lang.Object(ARRAY(i80)), i82, i81) :|: TRUE f787_0_take_ArrayAccess(EOS(STATIC_787), i80, java.lang.Object(From(EOC, i95)), java.lang.Object(ARRAY(i80)), i82, java.lang.Object(ARRAY(i80)), i82, i81) -> f791_0_take_Inc(EOS(STATIC_791), i80, java.lang.Object(From(EOC, i95)), java.lang.Object(ARRAY(i80)), i82) :|: i82 < i80 f791_0_take_Inc(EOS(STATIC_791), i80, java.lang.Object(From(EOC, i95)), java.lang.Object(ARRAY(i80)), i82) -> f793_0_take_JMP(EOS(STATIC_793), i80, java.lang.Object(From(EOC, i95)), java.lang.Object(ARRAY(i80)), i82 + 1) :|: TRUE f793_0_take_JMP(EOS(STATIC_793), i80, java.lang.Object(From(EOC, i95)), java.lang.Object(ARRAY(i80)), i96) -> f856_0_take_Load(EOS(STATIC_856), i80, java.lang.Object(From(EOC, i95)), java.lang.Object(ARRAY(i80)), i96) :|: TRUE f856_0_take_Load(EOS(STATIC_856), i80, java.lang.Object(From(EOC, i95)), java.lang.Object(ARRAY(i80)), i96) -> f708_0_take_Load(EOS(STATIC_708), i80, java.lang.Object(From(EOC, i95)), java.lang.Object(ARRAY(i80)), i96) :|: TRUE f708_0_take_Load(EOS(STATIC_708), i80, java.lang.Object(From(EOC, i81)), java.lang.Object(ARRAY(i80)), i82) -> f712_0_take_Load(EOS(STATIC_712), i80, java.lang.Object(From(EOC, i81)), java.lang.Object(ARRAY(i80)), i82, i82) :|: TRUE Combined rules. Obtained 1 IRulesP rules: f712_0_take_Load(EOS(STATIC_712), i80:0, java.lang.Object(From(EOC, i81:0)), java.lang.Object(ARRAY(i80:0)), i82:0, i82:0) -> f712_0_take_Load(EOS(STATIC_712), i80:0, java.lang.Object(From(EOC, i81:0 + 1)), java.lang.Object(ARRAY(i80:0)), i82:0 + 1, i82:0 + 1) :|: i82:0 < i80:0 && i81:0 > -1 Filtered constant ground arguments: f712_0_take_Load(x1, x2, x3, x4, x5, x6) -> f712_0_take_Load(x2, x3, x4, x5, x6) EOS(x1) -> EOS From(x1, x2) -> From(x2) Filtered duplicate arguments: f712_0_take_Load(x1, x2, x3, x4, x5) -> f712_0_take_Load(x1, x2, x3, x5) Finished conversion. Obtained 1 rules.P rules: f712_0_take_Load(i80:0, java.lang.Object(From(i81:0)), java.lang.Object(ARRAY(i80:0)), i82:0, i81:0, i80:0) -> f712_0_take_Load(i80:0, java.lang.Object(From(i81:0 + 1)), java.lang.Object(ARRAY(i80:0)), i82:0 + 1, i81:0 + 1, i80:0) :|: i82:0 < i80:0 && i81:0 > -1 ---------------------------------------- (8) Obligation: Rules: f712_0_take_Load(i80:0, java.lang.Object(From(i81:0)), java.lang.Object(ARRAY(i80:0)), i82:0, i81:0, i80:0) -> f712_0_take_Load(i80:0, java.lang.Object(From(i81:0 + 1)), java.lang.Object(ARRAY(i80:0)), i82:0 + 1, i81:0 + 1, i80:0) :|: i82:0 < i80:0 && i81:0 > -1 ---------------------------------------- (9) IRSFormatTransformerProof (EQUIVALENT) Reformatted IRS to match normalized format (transformed away non-linear left-hand sides, !=, / and %). ---------------------------------------- (10) Obligation: Rules: f712_0_take_Load(i80:0, java.lang.Object(From(i81:0)), java.lang.Object(ARRAY(i80:0)), i82:0, i81:0, i80:0) -> f712_0_take_Load(i80:0, java.lang.Object(From(arith1)), java.lang.Object(ARRAY(i80:0)), arith, arith1, i80:0) :|: i82:0 < i80:0 && i81:0 > -1 && arith = i82:0 + 1 && arith1 = i81:0 + 1 && arith1 = i81:0 + 1 ---------------------------------------- (11) IRSwTTerminationDigraphProof (EQUIVALENT) Constructed termination digraph! Nodes: (1) f712_0_take_Load(i80:0, java.lang.Object(From(i81:0)), java.lang.Object(ARRAY(i80:0)), i82:0, i81:0, i80:0) -> f712_0_take_Load(i80:0, java.lang.Object(From(arith1)), java.lang.Object(ARRAY(i80:0)), arith, arith1, i80:0) :|: i82:0 < i80:0 && i81:0 > -1 && arith = i82:0 + 1 && arith1 = i81:0 + 1 && arith1 = i81:0 + 1 Arcs: (1) -> (1) This digraph is fully evaluated! ---------------------------------------- (12) Obligation: Termination digraph: Nodes: (1) f712_0_take_Load(i80:0, java.lang.Object(From(i81:0)), java.lang.Object(ARRAY(i80:0)), i82:0, i81:0, i80:0) -> f712_0_take_Load(i80:0, java.lang.Object(From(arith1)), java.lang.Object(ARRAY(i80:0)), arith, arith1, i80:0) :|: i82:0 < i80:0 && i81:0 > -1 && arith = i82:0 + 1 && arith1 = i81:0 + 1 && arith1 = i81:0 + 1 Arcs: (1) -> (1) This digraph is fully evaluated! ---------------------------------------- (13) IntTRSCompressionProof (EQUIVALENT) Compressed rules. ---------------------------------------- (14) Obligation: Rules: f712_0_take_Load(i80:0:0, java.lang.Object(From(i81:0:0)), java.lang.Object(ARRAY(i80:0:0)), i82:0:0, i81:0:0, i80:0:0) -> f712_0_take_Load(i80:0:0, java.lang.Object(From(i81:0:0 + 1)), java.lang.Object(ARRAY(i80:0:0)), i82:0:0 + 1, i81:0:0 + 1, i80:0:0) :|: i82:0:0 < i80:0:0 && i81:0:0 > -1 ---------------------------------------- (15) TempFilterProof (SOUND) Used the following sort dictionary for filtering: f712_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: f712_0_take_Load(i80:0:0, c, c1, i82:0:0, i81:0:0, i80:0:0) -> f712_0_take_Load(i80:0:0, c2, c3, c4, c5, i80:0:0) :|: c5 = i81:0:0 + 1 && (c4 = i82:0:0 + 1 && (c3 = 0 && (c2 = 0 && (c1 = 0 && c = 0)))) && (i82:0:0 < i80:0:0 && i81:0:0 > -1) ---------------------------------------- (17) PolynomialOrderProcessor (EQUIVALENT) Found the following polynomial interpretation: [f712_0_take_Load(x, x1, x2, x3, x4, x5)] = x + c1*x1 + c2*x2 - x3 The following rules are decreasing: f712_0_take_Load(i80:0:0, c, c1, i82:0:0, i81:0:0, i80:0:0) -> f712_0_take_Load(i80:0:0, c2, c3, c4, c5, i80:0:0) :|: c5 = i81:0:0 + 1 && (c4 = i82:0:0 + 1 && (c3 = 0 && (c2 = 0 && (c1 = 0 && c = 0)))) && (i82:0:0 < i80:0:0 && i81:0:0 > -1) The following rules are bounded: f712_0_take_Load(i80:0:0, c, c1, i82:0:0, i81:0:0, i80:0:0) -> f712_0_take_Load(i80:0:0, c2, c3, c4, c5, i80:0:0) :|: c5 = i81:0:0 + 1 && (c4 = i82:0:0 + 1 && (c3 = 0 && (c2 = 0 && (c1 = 0 && c = 0)))) && (i82:0:0 < i80:0:0 && i81:0:0 > -1) ---------------------------------------- (18) YES