/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: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty termination of the given Bare JBC problem could be proven: (0) Bare JBC problem (1) BareJBCToJBCProof [EQUIVALENT, 97 ms] (2) JBC problem (3) JBCToGraph [EQUIVALENT, 208 ms] (4) JBCTerminationGraph (5) TerminationGraphToSCCProof [SOUND, 0 ms] (6) AND (7) JBCTerminationSCC (8) SCCToQDPProof [SOUND, 108 ms] (9) QDP (10) QDPSizeChangeProof [EQUIVALENT, 0 ms] (11) YES (12) JBCTerminationSCC (13) SCCToIRSProof [SOUND, 55 ms] (14) IRSwT (15) IRSFormatTransformerProof [EQUIVALENT, 0 ms] (16) IRSwT (17) IRSwTTerminationDigraphProof [EQUIVALENT, 0 ms] (18) IRSwT (19) IntTRSCompressionProof [EQUIVALENT, 0 ms] (20) IRSwT (21) TempFilterProof [SOUND, 14 ms] (22) IntTRS (23) PolynomialOrderProcessor [EQUIVALENT, 0 ms] (24) YES ---------------------------------------- (0) Obligation: need to prove termination of the following program: public class ListReverseAcyclicList { public static void main(String... args) { List x = List.createList(args[0].length(), null); List.reverse(x); } } class List { List n; public List(List next) { this.n = next; } public static void reverse(List x) { List y = null; while (x != null) { List z = x; x = x.n; z.n = y; y = z; } } public static List createList(int l, List end) { while (--l > 0) { end = new List(end); } return end; } public static List createCycle(int l) { List last = new List(null); List first = createList(l - 1, last); last.n = first; return first; } public static List createPanhandleList(int pl, int cl) { return createList(pl, createCycle(cl)); } } ---------------------------------------- (1) BareJBCToJBCProof (EQUIVALENT) initialized classpath ---------------------------------------- (2) Obligation: need to prove termination of the following program: public class ListReverseAcyclicList { public static void main(String... args) { List x = List.createList(args[0].length(), null); List.reverse(x); } } class List { List n; public List(List next) { this.n = next; } public static void reverse(List x) { List y = null; while (x != null) { List z = x; x = x.n; z.n = y; y = z; } } public static List createList(int l, List end) { while (--l > 0) { end = new List(end); } return end; } public static List createCycle(int l) { List last = new List(null); List first = createList(l - 1, last); last.n = first; return first; } public static List createPanhandleList(int pl, int cl) { return createList(pl, createCycle(cl)); } } ---------------------------------------- (3) JBCToGraph (EQUIVALENT) Constructed TerminationGraph. ---------------------------------------- (4) Obligation: Termination Graph based on JBC Program: ListReverseAcyclicList.main([Ljava/lang/String;)V: Graph of 147 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: ListReverseAcyclicList.main([Ljava/lang/String;)V SCC calls the following helper methods: Performed SCC analyses: *Used field analysis yielded the following read fields: *List: [n] *Marker field analysis yielded the following relations that could be markers: ---------------------------------------- (8) SCCToQDPProof (SOUND) Transformed TerminationGraph SCC to QDP. Log: Generated 16 rules for P and 0 rules for R.P rules: f653_0_reverse_NULL(EOS(STATIC_653), java.lang.Object(o206sub), java.lang.Object(List(EOC, o186)), java.lang.Object(o206sub)) -> f729_0_reverse_Load(EOS(STATIC_729), java.lang.Object(o206sub), java.lang.Object(List(EOC, o186))) :|: TRUE f729_0_reverse_Load(EOS(STATIC_729), java.lang.Object(o206sub), java.lang.Object(List(EOC, o186))) -> f737_0_reverse_Store(EOS(STATIC_737), java.lang.Object(o206sub), java.lang.Object(List(EOC, o186)), java.lang.Object(o206sub)) :|: TRUE f737_0_reverse_Store(EOS(STATIC_737), java.lang.Object(List(EOC, o217)), java.lang.Object(List(EOC, o186)), java.lang.Object(List(EOC, o217))) -> f740_0_reverse_Store(EOS(STATIC_740), java.lang.Object(List(EOC, o217)), java.lang.Object(List(EOC, o186)), java.lang.Object(List(EOC, o217))) :|: TRUE f740_0_reverse_Store(EOS(STATIC_740), java.lang.Object(List(EOC, o217)), java.lang.Object(List(EOC, o186)), java.lang.Object(List(EOC, o217))) -> f743_0_reverse_Load(EOS(STATIC_743), java.lang.Object(List(EOC, o217)), java.lang.Object(List(EOC, o186)), java.lang.Object(List(EOC, o217))) :|: TRUE f743_0_reverse_Load(EOS(STATIC_743), java.lang.Object(List(EOC, o217)), java.lang.Object(List(EOC, o186)), java.lang.Object(List(EOC, o217))) -> f744_0_reverse_FieldAccess(EOS(STATIC_744), java.lang.Object(List(EOC, o186)), java.lang.Object(List(EOC, o217)), java.lang.Object(List(EOC, o217))) :|: TRUE f744_0_reverse_FieldAccess(EOS(STATIC_744), java.lang.Object(List(EOC, o186)), java.lang.Object(List(EOC, o217)), java.lang.Object(List(EOC, o217))) -> f745_0_reverse_Store(EOS(STATIC_745), java.lang.Object(List(EOC, o186)), java.lang.Object(List(EOC, o217)), o217) :|: TRUE f745_0_reverse_Store(EOS(STATIC_745), java.lang.Object(List(EOC, o186)), java.lang.Object(List(EOC, o217)), o217) -> f746_0_reverse_Load(EOS(STATIC_746), o217, java.lang.Object(List(EOC, o186)), java.lang.Object(List(EOC, o217))) :|: TRUE f746_0_reverse_Load(EOS(STATIC_746), o217, java.lang.Object(List(EOC, o186)), java.lang.Object(List(EOC, o217))) -> f749_0_reverse_Load(EOS(STATIC_749), o217, java.lang.Object(List(EOC, o186)), java.lang.Object(List(EOC, o217)), java.lang.Object(List(EOC, o217))) :|: TRUE f749_0_reverse_Load(EOS(STATIC_749), o217, java.lang.Object(List(EOC, o186)), java.lang.Object(List(EOC, o217)), java.lang.Object(List(EOC, o217))) -> f752_0_reverse_FieldAccess(EOS(STATIC_752), o217, java.lang.Object(List(EOC, o217)), java.lang.Object(List(EOC, o217)), java.lang.Object(List(EOC, o186))) :|: TRUE f752_0_reverse_FieldAccess(EOS(STATIC_752), o217, java.lang.Object(List(EOC, o217)), java.lang.Object(List(EOC, o217)), java.lang.Object(List(EOC, o186))) -> f759_0_reverse_Load(EOS(STATIC_759), o217, java.lang.Object(List(EOC, java.lang.Object(List(EOC, o186))))) :|: TRUE f759_0_reverse_Load(EOS(STATIC_759), o217, java.lang.Object(List(EOC, java.lang.Object(List(EOC, o186))))) -> f760_0_reverse_Store(EOS(STATIC_760), o217, java.lang.Object(List(EOC, java.lang.Object(List(EOC, o186))))) :|: TRUE f760_0_reverse_Store(EOS(STATIC_760), o217, java.lang.Object(List(EOC, java.lang.Object(List(EOC, o186))))) -> f763_0_reverse_JMP(EOS(STATIC_763), o217, java.lang.Object(List(EOC, java.lang.Object(List(EOC, o186))))) :|: TRUE f763_0_reverse_JMP(EOS(STATIC_763), o217, java.lang.Object(List(EOC, java.lang.Object(List(EOC, o186))))) -> f774_0_reverse_Load(EOS(STATIC_774), o217, java.lang.Object(List(EOC, java.lang.Object(List(EOC, o186))))) :|: TRUE f774_0_reverse_Load(EOS(STATIC_774), o217, java.lang.Object(List(EOC, java.lang.Object(List(EOC, o186))))) -> f644_0_reverse_Load(EOS(STATIC_644), o217, java.lang.Object(List(EOC, java.lang.Object(List(EOC, o186))))) :|: TRUE f644_0_reverse_Load(EOS(STATIC_644), o184, java.lang.Object(List(EOC, o186))) -> f650_0_reverse_NULL(EOS(STATIC_650), o184, java.lang.Object(List(EOC, o186)), o184) :|: TRUE f650_0_reverse_NULL(EOS(STATIC_650), java.lang.Object(o206sub), java.lang.Object(List(EOC, o186)), java.lang.Object(o206sub)) -> f653_0_reverse_NULL(EOS(STATIC_653), java.lang.Object(o206sub), java.lang.Object(List(EOC, o186)), java.lang.Object(o206sub)) :|: TRUE R rules: Combined rules. Obtained 1 conditional rules for P and 0 conditional rules for R.P rules: f653_0_reverse_NULL(EOS(STATIC_653), java.lang.Object(List(EOC, java.lang.Object(o206sub:0))), java.lang.Object(List(EOC, o186:0)), java.lang.Object(List(EOC, java.lang.Object(o206sub:0)))) -> f653_0_reverse_NULL(EOS(STATIC_653), java.lang.Object(o206sub:0), java.lang.Object(List(EOC, java.lang.Object(List(EOC, o186:0)))), java.lang.Object(o206sub:0)) :|: TRUE R rules: Filtered ground terms: f653_0_reverse_NULL(x1, x2, x3, x4) -> f653_0_reverse_NULL(x2, x3, x4) EOS(x1) -> EOS List(x1, x2) -> List(x2) Filtered duplicate args: f653_0_reverse_NULL(x1, x2, x3) -> f653_0_reverse_NULL(x2, x3) Combined rules. Obtained 1 conditional rules for P and 0 conditional rules for R.P rules: F653_0_REVERSE_NULL(java.lang.Object(List(o186:0:0)), java.lang.Object(List(java.lang.Object(o206sub:0:0)))) -> F653_0_REVERSE_NULL(java.lang.Object(List(java.lang.Object(List(o186:0:0)))), java.lang.Object(o206sub:0:0)) :|: TRUE R rules: ---------------------------------------- (9) Obligation: Q DP problem: The TRS P consists of the following rules: F653_0_REVERSE_NULL(java.lang.Object(List(o186:0:0)), java.lang.Object(List(java.lang.Object(o206sub:0:0)))) -> F653_0_REVERSE_NULL(java.lang.Object(List(java.lang.Object(List(o186:0:0)))), java.lang.Object(o206sub:0:0)) R is empty. Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (10) QDPSizeChangeProof (EQUIVALENT) By using the subterm criterion [SUBTERM_CRITERION] together with the size-change analysis [AAECC05] we have proven that there are no infinite chains for this DP problem. From the DPs we obtained the following set of size-change graphs: *F653_0_REVERSE_NULL(java.lang.Object(List(o186:0:0)), java.lang.Object(List(java.lang.Object(o206sub:0:0)))) -> F653_0_REVERSE_NULL(java.lang.Object(List(java.lang.Object(List(o186:0:0)))), java.lang.Object(o206sub:0:0)) The graph contains the following edges 2 > 2 ---------------------------------------- (11) YES ---------------------------------------- (12) Obligation: SCC of termination graph based on JBC Program. SCC contains nodes from the following methods: ListReverseAcyclicList.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: ---------------------------------------- (13) SCCToIRSProof (SOUND) Transformed FIGraph SCCs to intTRSs. Log: Generated rules. Obtained 17 IRulesP rules: f447_0_createList_LE(EOS(STATIC_447), i71, i71) -> f453_0_createList_New(EOS(STATIC_453), i71) :|: i71 > 0 f453_0_createList_New(EOS(STATIC_453), i71) -> f459_0_createList_Duplicate(EOS(STATIC_459), i71) :|: TRUE f459_0_createList_Duplicate(EOS(STATIC_459), i71) -> f465_0_createList_Load(EOS(STATIC_465), i71) :|: TRUE f465_0_createList_Load(EOS(STATIC_465), i71) -> f471_0_createList_InvokeMethod(EOS(STATIC_471), i71) :|: TRUE f471_0_createList_InvokeMethod(EOS(STATIC_471), i71) -> f476_0__init__Load(EOS(STATIC_476), i71) :|: TRUE f476_0__init__Load(EOS(STATIC_476), i71) -> f479_0__init__InvokeMethod(EOS(STATIC_479), i71) :|: TRUE f479_0__init__InvokeMethod(EOS(STATIC_479), i71) -> f483_0__init__Load(EOS(STATIC_483), i71) :|: TRUE f483_0__init__Load(EOS(STATIC_483), i71) -> f487_0__init__Load(EOS(STATIC_487), i71) :|: TRUE f487_0__init__Load(EOS(STATIC_487), i71) -> f493_0__init__FieldAccess(EOS(STATIC_493), i71) :|: TRUE f493_0__init__FieldAccess(EOS(STATIC_493), i71) -> f502_0__init__Return(EOS(STATIC_502), i71) :|: TRUE f502_0__init__Return(EOS(STATIC_502), i71) -> f505_0_createList_Store(EOS(STATIC_505), i71) :|: TRUE f505_0_createList_Store(EOS(STATIC_505), i71) -> f509_0_createList_JMP(EOS(STATIC_509), i71) :|: TRUE f509_0_createList_JMP(EOS(STATIC_509), i71) -> f544_0_createList_Inc(EOS(STATIC_544), i71) :|: TRUE f544_0_createList_Inc(EOS(STATIC_544), i71) -> f430_0_createList_Inc(EOS(STATIC_430), i71) :|: TRUE f430_0_createList_Inc(EOS(STATIC_430), i62) -> f436_0_createList_Load(EOS(STATIC_436), i62 + -1) :|: TRUE f436_0_createList_Load(EOS(STATIC_436), i67) -> f442_0_createList_LE(EOS(STATIC_442), i67, i67) :|: TRUE f442_0_createList_LE(EOS(STATIC_442), i71, i71) -> f447_0_createList_LE(EOS(STATIC_447), i71, i71) :|: TRUE Combined rules. Obtained 1 IRulesP rules: f447_0_createList_LE(EOS(STATIC_447), i71:0, i71:0) -> f447_0_createList_LE(EOS(STATIC_447), i71:0 - 1, i71:0 - 1) :|: i71:0 > 0 Filtered constant ground arguments: f447_0_createList_LE(x1, x2, x3) -> f447_0_createList_LE(x2, x3) EOS(x1) -> EOS Filtered duplicate arguments: f447_0_createList_LE(x1, x2) -> f447_0_createList_LE(x2) Finished conversion. Obtained 1 rules.P rules: f447_0_createList_LE(i71:0) -> f447_0_createList_LE(i71:0 - 1) :|: i71:0 > 0 ---------------------------------------- (14) Obligation: Rules: f447_0_createList_LE(i71:0) -> f447_0_createList_LE(i71:0 - 1) :|: i71:0 > 0 ---------------------------------------- (15) IRSFormatTransformerProof (EQUIVALENT) Reformatted IRS to match normalized format (transformed away non-linear left-hand sides, !=, / and %). ---------------------------------------- (16) Obligation: Rules: f447_0_createList_LE(i71:0) -> f447_0_createList_LE(arith) :|: i71:0 > 0 && arith = i71:0 - 1 ---------------------------------------- (17) IRSwTTerminationDigraphProof (EQUIVALENT) Constructed termination digraph! Nodes: (1) f447_0_createList_LE(i71:0) -> f447_0_createList_LE(arith) :|: i71:0 > 0 && arith = i71:0 - 1 Arcs: (1) -> (1) This digraph is fully evaluated! ---------------------------------------- (18) Obligation: Termination digraph: Nodes: (1) f447_0_createList_LE(i71:0) -> f447_0_createList_LE(arith) :|: i71:0 > 0 && arith = i71:0 - 1 Arcs: (1) -> (1) This digraph is fully evaluated! ---------------------------------------- (19) IntTRSCompressionProof (EQUIVALENT) Compressed rules. ---------------------------------------- (20) Obligation: Rules: f447_0_createList_LE(i71:0:0) -> f447_0_createList_LE(i71:0:0 - 1) :|: i71:0:0 > 0 ---------------------------------------- (21) TempFilterProof (SOUND) Used the following sort dictionary for filtering: f447_0_createList_LE(INTEGER) Replaced non-predefined constructor symbols by 0. ---------------------------------------- (22) Obligation: Rules: f447_0_createList_LE(i71:0:0) -> f447_0_createList_LE(c) :|: c = i71:0:0 - 1 && i71:0:0 > 0 ---------------------------------------- (23) PolynomialOrderProcessor (EQUIVALENT) Found the following polynomial interpretation: [f447_0_createList_LE(x)] = x The following rules are decreasing: f447_0_createList_LE(i71:0:0) -> f447_0_createList_LE(c) :|: c = i71:0:0 - 1 && i71:0:0 > 0 The following rules are bounded: f447_0_createList_LE(i71:0:0) -> f447_0_createList_LE(c) :|: c = i71:0:0 - 1 && i71:0:0 > 0 ---------------------------------------- (24) YES