/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, 304 ms] (4) JBCTerminationGraph (5) TerminationGraphToSCCProof [SOUND, 0 ms] (6) AND (7) JBCTerminationSCC (8) SCCToIRSProof [SOUND, 48 ms] (9) IRSwT (10) IRSFormatTransformerProof [EQUIVALENT, 0 ms] (11) IRSwT (12) IRSwTTerminationDigraphProof [EQUIVALENT, 60 ms] (13) AND (14) IRSwT (15) IntTRSCompressionProof [EQUIVALENT, 0 ms] (16) IRSwT (17) TempFilterProof [SOUND, 11 ms] (18) IntTRS (19) RankingReductionPairProof [EQUIVALENT, 4 ms] (20) YES (21) IRSwT (22) IntTRSCompressionProof [EQUIVALENT, 0 ms] (23) IRSwT (24) TempFilterProof [SOUND, 5 ms] (25) IntTRS (26) PolynomialOrderProcessor [EQUIVALENT, 0 ms] (27) YES (28) JBCTerminationSCC (29) SCCToIRSProof [SOUND, 7 ms] (30) IRSwT (31) IRSFormatTransformerProof [EQUIVALENT, 0 ms] (32) IRSwT (33) IRSwTTerminationDigraphProof [EQUIVALENT, 19 ms] (34) IRSwT (35) IntTRSCompressionProof [EQUIVALENT, 0 ms] (36) IRSwT (37) TempFilterProof [SOUND, 10 ms] (38) IntTRS (39) PolynomialOrderProcessor [EQUIVALENT, 0 ms] (40) YES ---------------------------------------- (0) Obligation: need to prove termination of the following program: /** * This class represents a list. The function get(n) can be used to access * the n-th element. * @author Marc Brockschmidt */ public class CyclicList { /** * A reference to the next list element. */ private CyclicList next; public static void main(String[] args) { CyclicList list = CyclicList.create(args.length); list.get(args[0].length()); } /** * Create a new list element. * @param n a reference to the next element. */ public CyclicList(final CyclicList n) { this.next = n; } /** * Create a new cyclical list of a length l. * @param l some length * @return cyclical list of length max(1, l) */ public static CyclicList create(int x) { CyclicList last, current; last = current = new CyclicList(null); while (--x > 0) current = new CyclicList(current); return last.next = current; } public CyclicList get(int n) { CyclicList cur = this; while (--n > 0) { cur = cur.next; } return cur; } } ---------------------------------------- (1) BareJBCToJBCProof (EQUIVALENT) initialized classpath ---------------------------------------- (2) Obligation: need to prove termination of the following program: /** * This class represents a list. The function get(n) can be used to access * the n-th element. * @author Marc Brockschmidt */ public class CyclicList { /** * A reference to the next list element. */ private CyclicList next; public static void main(String[] args) { CyclicList list = CyclicList.create(args.length); list.get(args[0].length()); } /** * Create a new list element. * @param n a reference to the next element. */ public CyclicList(final CyclicList n) { this.next = n; } /** * Create a new cyclical list of a length l. * @param l some length * @return cyclical list of length max(1, l) */ public static CyclicList create(int x) { CyclicList last, current; last = current = new CyclicList(null); while (--x > 0) current = new CyclicList(current); return last.next = current; } public CyclicList get(int n) { CyclicList cur = this; while (--n > 0) { cur = cur.next; } return cur; } } ---------------------------------------- (3) JBCToGraph (EQUIVALENT) Constructed TerminationGraph. ---------------------------------------- (4) Obligation: Termination Graph based on JBC Program: CyclicList.main([Ljava/lang/String;)V: Graph of 131 nodes with 2 SCCs. ---------------------------------------- (5) TerminationGraphToSCCProof (SOUND) Splitted TerminationGraph to 2 SCCss. ---------------------------------------- (6) Complex Obligation (AND) ---------------------------------------- (7) Obligation: SCC of termination graph based on JBC Program. SCC contains nodes from the following methods: CyclicList.main([Ljava/lang/String;)V SCC calls the following helper methods: Performed SCC analyses: *Used field analysis yielded the following read fields: *CyclicList: [next] *Marker field analysis yielded the following relations that could be markers: ---------------------------------------- (8) SCCToIRSProof (SOUND) Transformed FIGraph SCCs to intTRSs. Log: Generated rules. Obtained 16 IRulesP rules: f811_0_get_Load(EOS(STATIC_811), i124, o29[CyclicList.next]o29) -> f816_0_get_LE(EOS(STATIC_816), i124, i124, o29[CyclicList.next]o29) :|: TRUE f816_0_get_LE(EOS(STATIC_816), i126, i126, o29[CyclicList.next]o29) -> f821_0_get_LE(EOS(STATIC_821), i126, i126, o29[CyclicList.next]o29) :|: TRUE f821_0_get_LE(EOS(STATIC_821), i126, i126, o29[CyclicList.next]o29) -> f831_0_get_Load(EOS(STATIC_831), i126, o29[CyclicList.next]o29) :|: i126 > 0 f831_0_get_Load(EOS(STATIC_831), i126, o29[CyclicList.next]o29) -> f840_0_get_FieldAccess(EOS(STATIC_840), i126, o29[CyclicList.next]o29) :|: TRUE f840_0_get_FieldAccess(EOS(STATIC_840), i126, o86[CyclicList.next]o86) -> f861_0_get_FieldAccess(EOS(STATIC_861), i126, o87[CyclicList.next]o86) :|: o87[CyclicList.next]o86 < o86[CyclicList.next]o86 && o86[CyclicList.next]o86 >= 0 f861_0_get_FieldAccess(EOS(STATIC_861), i126, o87[CyclicList.next]o86) -> f882_0_get_FieldAccess(EOS(STATIC_882), i126, o87[CyclicList.next]o86) :|: o87[CyclicList.next]o86 > 0 f861_0_get_FieldAccess(EOS(STATIC_861), i126, o87[CyclicList.next]o90) -> f883_0_get_FieldAccess(EOS(STATIC_883), i126) :|: TRUE f882_0_get_FieldAccess(EOS(STATIC_882), i126, o87[CyclicList.next]o86) -> f893_0_get_Store(EOS(STATIC_893), i126, o87[CyclicList.next]o87) :|: o87[CyclicList.next]o87 > o87[CyclicList.next]o86 && o87[CyclicList.next]o86 >= 0 f893_0_get_Store(EOS(STATIC_893), i126, o87[CyclicList.next]o87) -> f905_0_get_JMP(EOS(STATIC_905), i126, o87[CyclicList.next]o87) :|: TRUE f905_0_get_JMP(EOS(STATIC_905), i126, o87[CyclicList.next]o87) -> f913_0_get_Inc(EOS(STATIC_913), i126, o87[CyclicList.next]o87) :|: TRUE f913_0_get_Inc(EOS(STATIC_913), i126, o87[CyclicList.next]o87) -> f810_0_get_Inc(EOS(STATIC_810), i126, o87[CyclicList.next]o87) :|: TRUE f810_0_get_Inc(EOS(STATIC_810), i122, o29[CyclicList.next]o29) -> f811_0_get_Load(EOS(STATIC_811), i122 + -1, o29[CyclicList.next]o29) :|: TRUE f883_0_get_FieldAccess(EOS(STATIC_883), i126) -> f898_0_get_Store(EOS(STATIC_898), i126) :|: TRUE f898_0_get_Store(EOS(STATIC_898), i126) -> f906_0_get_JMP(EOS(STATIC_906), i126) :|: TRUE f906_0_get_JMP(EOS(STATIC_906), i126) -> f921_0_get_Inc(EOS(STATIC_921), i126) :|: TRUE f921_0_get_Inc(EOS(STATIC_921), i126) -> f810_0_get_Inc(EOS(STATIC_810), i126, o90[CyclicList.next]o90) :|: o90[CyclicList.next]o90 = 1 Combined rules. Obtained 2 IRulesP rules: f811_0_get_Load(EOS(STATIC_811), i124:0, o29[CyclicList.next]o29:0) -> f811_0_get_Load(EOS(STATIC_811), i124:0 - 1, 1) :|: i124:0 > 0 && o87[CyclicList.next]o86:0 < o29[CyclicList.next]o29:0 && o29[CyclicList.next]o29:0 > -1 f811_0_get_Load(EOS(STATIC_811), i124:0, o29[CyclicList.next]o29:0) -> f811_0_get_Load(EOS(STATIC_811), i124:0 - 1, o87[CyclicList.next]o87:0) :|: o87[CyclicList.next]o86:0 > 0 && i124:0 > 0 && o29[CyclicList.next]o29:0 > -1 && o87[CyclicList.next]o87:0 > o87[CyclicList.next]o86:0 && o87[CyclicList.next]o86:0 < o29[CyclicList.next]o29:0 Filtered constant ground arguments: f811_0_get_Load(x1, x2, x3) -> f811_0_get_Load(x2, x3) EOS(x1) -> EOS Finished conversion. Obtained 2 rules.P rules: f811_0_get_Load(i124:0, o29[CyclicList.next]o29:0) -> f811_0_get_Load(i124:0 - 1, 1) :|: o87[CyclicList.next]o86:0 < o29[CyclicList.next]o29:0 && o29[CyclicList.next]o29:0 > -1 && i124:0 > 0 f811_0_get_Load(i124:0, o29[CyclicList.next]o29:0) -> f811_0_get_Load(i124:0 - 1, o87[CyclicList.next]o87:0) :|: i124:0 > 0 && o87[CyclicList.next]o86:0 > 0 && o29[CyclicList.next]o29:0 > -1 && o87[CyclicList.next]o86:0 < o29[CyclicList.next]o29:0 && o87[CyclicList.next]o87:0 > o87[CyclicList.next]o86:0 ---------------------------------------- (9) Obligation: Rules: f811_0_get_Load(i124:0, o29[CyclicList.next]o29:0) -> f811_0_get_Load(i124:0 - 1, 1) :|: o87[CyclicList.next]o86:0 < o29[CyclicList.next]o29:0 && o29[CyclicList.next]o29:0 > -1 && i124:0 > 0 f811_0_get_Load(x, x1) -> f811_0_get_Load(x - 1, x2) :|: x > 0 && x3 > 0 && x1 > -1 && x3 < x1 && x2 > x3 ---------------------------------------- (10) IRSFormatTransformerProof (EQUIVALENT) Reformatted IRS to match normalized format (transformed away non-linear left-hand sides, !=, / and %). ---------------------------------------- (11) Obligation: Rules: f811_0_get_Load(i124:0, o29[CyclicList.next]o29:0) -> f811_0_get_Load(arith, 1) :|: o87[CyclicList.next]o86:0 < o29[CyclicList.next]o29:0 && o29[CyclicList.next]o29:0 > -1 && i124:0 > 0 && arith = i124:0 - 1 f811_0_get_Load(x4, x5) -> f811_0_get_Load(x6, x7) :|: x4 > 0 && x8 > 0 && x5 > -1 && x8 < x5 && x7 > x8 && x6 = x4 - 1 ---------------------------------------- (12) IRSwTTerminationDigraphProof (EQUIVALENT) Constructed termination digraph! Nodes: (1) f811_0_get_Load(i124:0, o29[CyclicList.next]o29:0) -> f811_0_get_Load(arith, 1) :|: o87[CyclicList.next]o86:0 < o29[CyclicList.next]o29:0 && o29[CyclicList.next]o29:0 > -1 && i124:0 > 0 && arith = i124:0 - 1 (2) f811_0_get_Load(x4, x5) -> f811_0_get_Load(x6, x7) :|: x4 > 0 && x8 > 0 && x5 > -1 && x8 < x5 && x7 > x8 && x6 = x4 - 1 Arcs: (1) -> (1) (2) -> (1), (2) This digraph is fully evaluated! ---------------------------------------- (13) Complex Obligation (AND) ---------------------------------------- (14) Obligation: Termination digraph: Nodes: (1) f811_0_get_Load(x4, x5) -> f811_0_get_Load(x6, x7) :|: x4 > 0 && x8 > 0 && x5 > -1 && x8 < x5 && x7 > x8 && x6 = x4 - 1 Arcs: (1) -> (1) This digraph is fully evaluated! ---------------------------------------- (15) IntTRSCompressionProof (EQUIVALENT) Compressed rules. ---------------------------------------- (16) Obligation: Rules: f811_0_get_Load(x4:0, x5:0) -> f811_0_get_Load(x4:0 - 1, x7:0) :|: x8:0 < x5:0 && x8:0 < x7:0 && x5:0 > -1 && x8:0 > 0 && x4:0 > 0 ---------------------------------------- (17) TempFilterProof (SOUND) Used the following sort dictionary for filtering: f811_0_get_Load(INTEGER, INTEGER) Replaced non-predefined constructor symbols by 0. ---------------------------------------- (18) Obligation: Rules: f811_0_get_Load(x4:0, x5:0) -> f811_0_get_Load(c, x7:0) :|: c = x4:0 - 1 && (x8:0 < x5:0 && x8:0 < x7:0 && x5:0 > -1 && x8:0 > 0 && x4:0 > 0) ---------------------------------------- (19) RankingReductionPairProof (EQUIVALENT) Interpretation: [ f811_0_get_Load ] = f811_0_get_Load_1 The following rules are decreasing: f811_0_get_Load(x4:0, x5:0) -> f811_0_get_Load(c, x7:0) :|: c = x4:0 - 1 && (x8:0 < x5:0 && x8:0 < x7:0 && x5:0 > -1 && x8:0 > 0 && x4:0 > 0) The following rules are bounded: f811_0_get_Load(x4:0, x5:0) -> f811_0_get_Load(c, x7:0) :|: c = x4:0 - 1 && (x8:0 < x5:0 && x8:0 < x7:0 && x5:0 > -1 && x8:0 > 0 && x4:0 > 0) ---------------------------------------- (20) YES ---------------------------------------- (21) Obligation: Termination digraph: Nodes: (1) f811_0_get_Load(i124:0, o29[CyclicList.next]o29:0) -> f811_0_get_Load(arith, 1) :|: o87[CyclicList.next]o86:0 < o29[CyclicList.next]o29:0 && o29[CyclicList.next]o29:0 > -1 && i124:0 > 0 && arith = i124:0 - 1 Arcs: (1) -> (1) This digraph is fully evaluated! ---------------------------------------- (22) IntTRSCompressionProof (EQUIVALENT) Compressed rules. ---------------------------------------- (23) Obligation: Rules: f811_0_get_Load(i124:0:0, o29[CyclicList.next]o29:0:0) -> f811_0_get_Load(i124:0:0 - 1, 1) :|: o87[CyclicList.next]o86:0:0 < o29[CyclicList.next]o29:0:0 && o29[CyclicList.next]o29:0:0 > -1 && i124:0:0 > 0 ---------------------------------------- (24) TempFilterProof (SOUND) Used the following sort dictionary for filtering: f811_0_get_Load(INTEGER, VARIABLE) Replaced non-predefined constructor symbols by 0. ---------------------------------------- (25) Obligation: Rules: f811_0_get_Load(i124:0:0, o29[CyclicList.next]o29:0:0) -> f811_0_get_Load(c, c1) :|: c1 = 1 && c = i124:0:0 - 1 && (o87[CyclicList.next]o86:0:0 < o29[CyclicList.next]o29:0:0 && o29[CyclicList.next]o29:0:0 > -1 && i124:0:0 > 0) ---------------------------------------- (26) PolynomialOrderProcessor (EQUIVALENT) Found the following polynomial interpretation: [f811_0_get_Load(x, x1)] = x The following rules are decreasing: f811_0_get_Load(i124:0:0, o29[CyclicList.next]o29:0:0) -> f811_0_get_Load(c, c1) :|: c1 = 1 && c = i124:0:0 - 1 && (o87[CyclicList.next]o86:0:0 < o29[CyclicList.next]o29:0:0 && o29[CyclicList.next]o29:0:0 > -1 && i124:0:0 > 0) The following rules are bounded: f811_0_get_Load(i124:0:0, o29[CyclicList.next]o29:0:0) -> f811_0_get_Load(c, c1) :|: c1 = 1 && c = i124:0:0 - 1 && (o87[CyclicList.next]o86:0:0 < o29[CyclicList.next]o29:0:0 && o29[CyclicList.next]o29:0:0 > -1 && i124:0:0 > 0) ---------------------------------------- (27) YES ---------------------------------------- (28) Obligation: SCC of termination graph based on JBC Program. SCC contains nodes from the following methods: CyclicList.main([Ljava/lang/String;)V SCC calls the following helper methods: Performed SCC analyses: *Used field analysis yielded the following read fields: *Marker field analysis yielded the following relations that could be markers: ---------------------------------------- (29) SCCToIRSProof (SOUND) Transformed FIGraph SCCs to intTRSs. Log: Generated rules. Obtained 17 IRulesP rules: f449_0_create_Load(EOS(STATIC_449), i69, o29[CyclicList.next]o28) -> f451_0_create_LE(EOS(STATIC_451), i69, i69, o29[CyclicList.next]o28) :|: TRUE f451_0_create_LE(EOS(STATIC_451), i71, i71, o29[CyclicList.next]o28) -> f457_0_create_LE(EOS(STATIC_457), i71, i71, o29[CyclicList.next]o28) :|: TRUE f457_0_create_LE(EOS(STATIC_457), i71, i71, o29[CyclicList.next]o28) -> f460_0_create_New(EOS(STATIC_460), i71, o29[CyclicList.next]o28) :|: i71 > 0 f460_0_create_New(EOS(STATIC_460), i71, o29[CyclicList.next]o28) -> f466_0_create_Duplicate(EOS(STATIC_466), i71, o29[CyclicList.next]o28) :|: TRUE f466_0_create_Duplicate(EOS(STATIC_466), i71, o29[CyclicList.next]o28) -> f471_0_create_Load(EOS(STATIC_471), i71, o29[CyclicList.next]o28) :|: TRUE f471_0_create_Load(EOS(STATIC_471), i71, o29[CyclicList.next]o28) -> f476_0_create_InvokeMethod(EOS(STATIC_476), i71, o29[CyclicList.next]o28) :|: TRUE f476_0_create_InvokeMethod(EOS(STATIC_476), i71, o29[CyclicList.next]o28) -> f517_0__init__Load(EOS(STATIC_517), i71, o29[CyclicList.next]o28) :|: TRUE f517_0__init__Load(EOS(STATIC_517), i71, o29[CyclicList.next]o28) -> f547_0__init__InvokeMethod(EOS(STATIC_547), i71, o29[CyclicList.next]o28) :|: TRUE f547_0__init__InvokeMethod(EOS(STATIC_547), i71, o29[CyclicList.next]o28) -> f556_0__init__Load(EOS(STATIC_556), i71, o29[CyclicList.next]o28) :|: TRUE f556_0__init__Load(EOS(STATIC_556), i71, o29[CyclicList.next]o28) -> f564_0__init__Load(EOS(STATIC_564), i71, o29[CyclicList.next]o28) :|: TRUE f564_0__init__Load(EOS(STATIC_564), i71, o29[CyclicList.next]o28) -> f573_0__init__FieldAccess(EOS(STATIC_573), i71, o29[CyclicList.next]o28) :|: TRUE f573_0__init__FieldAccess(EOS(STATIC_573), i71, o29[CyclicList.next]o28) -> f592_0__init__Return(EOS(STATIC_592), i71, o29[CyclicList.next]o28) :|: TRUE f592_0__init__Return(EOS(STATIC_592), i71, o29[CyclicList.next]o28) -> f596_0_create_Store(EOS(STATIC_596), i71, o29[CyclicList.next]o28) :|: TRUE f596_0_create_Store(EOS(STATIC_596), i71, o29[CyclicList.next]o28) -> f605_0_create_JMP(EOS(STATIC_605), i71, o29[CyclicList.next]o28) :|: TRUE f605_0_create_JMP(EOS(STATIC_605), i71, o29[CyclicList.next]o28) -> f750_0_create_Inc(EOS(STATIC_750), i71, o29[CyclicList.next]o28) :|: TRUE f750_0_create_Inc(EOS(STATIC_750), i71, o29[CyclicList.next]o28) -> f439_0_create_Inc(EOS(STATIC_439), i71, o54[CyclicList.next]o28) :|: TRUE f439_0_create_Inc(EOS(STATIC_439), i22, o29[CyclicList.next]o28) -> f449_0_create_Load(EOS(STATIC_449), i22 + -1, o29[CyclicList.next]o28) :|: TRUE Combined rules. Obtained 1 IRulesP rules: f449_0_create_Load(EOS(STATIC_449), i69:0, o29[CyclicList.next]o28:0) -> f449_0_create_Load(EOS(STATIC_449), i69:0 - 1, o54[CyclicList.next]o28:0) :|: i69:0 > 0 Filtered constant ground arguments: f449_0_create_Load(x1, x2, x3) -> f449_0_create_Load(x2, x3) EOS(x1) -> EOS Filtered unneeded arguments: f449_0_create_Load(x1, x2) -> f449_0_create_Load(x1) Finished conversion. Obtained 1 rules.P rules: f449_0_create_Load(i69:0) -> f449_0_create_Load(i69:0 - 1) :|: i69:0 > 0 ---------------------------------------- (30) Obligation: Rules: f449_0_create_Load(i69:0) -> f449_0_create_Load(i69:0 - 1) :|: i69:0 > 0 ---------------------------------------- (31) IRSFormatTransformerProof (EQUIVALENT) Reformatted IRS to match normalized format (transformed away non-linear left-hand sides, !=, / and %). ---------------------------------------- (32) Obligation: Rules: f449_0_create_Load(i69:0) -> f449_0_create_Load(arith) :|: i69:0 > 0 && arith = i69:0 - 1 ---------------------------------------- (33) IRSwTTerminationDigraphProof (EQUIVALENT) Constructed termination digraph! Nodes: (1) f449_0_create_Load(i69:0) -> f449_0_create_Load(arith) :|: i69:0 > 0 && arith = i69:0 - 1 Arcs: (1) -> (1) This digraph is fully evaluated! ---------------------------------------- (34) Obligation: Termination digraph: Nodes: (1) f449_0_create_Load(i69:0) -> f449_0_create_Load(arith) :|: i69:0 > 0 && arith = i69:0 - 1 Arcs: (1) -> (1) This digraph is fully evaluated! ---------------------------------------- (35) IntTRSCompressionProof (EQUIVALENT) Compressed rules. ---------------------------------------- (36) Obligation: Rules: f449_0_create_Load(i69:0:0) -> f449_0_create_Load(i69:0:0 - 1) :|: i69:0:0 > 0 ---------------------------------------- (37) TempFilterProof (SOUND) Used the following sort dictionary for filtering: f449_0_create_Load(INTEGER) Replaced non-predefined constructor symbols by 0. ---------------------------------------- (38) Obligation: Rules: f449_0_create_Load(i69:0:0) -> f449_0_create_Load(c) :|: c = i69:0:0 - 1 && i69:0:0 > 0 ---------------------------------------- (39) PolynomialOrderProcessor (EQUIVALENT) Found the following polynomial interpretation: [f449_0_create_Load(x)] = x The following rules are decreasing: f449_0_create_Load(i69:0:0) -> f449_0_create_Load(c) :|: c = i69:0:0 - 1 && i69:0:0 > 0 The following rules are bounded: f449_0_create_Load(i69:0:0) -> f449_0_create_Load(c) :|: c = i69:0:0 - 1 && i69:0:0 > 0 ---------------------------------------- (40) YES