/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: 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, 633 ms] (4) JBCTerminationGraph (5) TerminationGraphToSCCProof [SOUND, 0 ms] (6) AND (7) JBCTerminationSCC (8) SCCToIRSProof [SOUND, 98 ms] (9) IRSwT (10) IRSFormatTransformerProof [EQUIVALENT, 0 ms] (11) IRSwT (12) IRSwTTerminationDigraphProof [EQUIVALENT, 0 ms] (13) IRSwT (14) IntTRSCompressionProof [EQUIVALENT, 0 ms] (15) IRSwT (16) TempFilterProof [SOUND, 36 ms] (17) IntTRS (18) RankingReductionPairProof [EQUIVALENT, 0 ms] (19) YES (20) JBCTerminationSCC (21) SCCToIRSProof [SOUND, 121 ms] (22) IRSwT (23) IRSFormatTransformerProof [EQUIVALENT, 0 ms] (24) IRSwT (25) IRSwTTerminationDigraphProof [EQUIVALENT, 31 ms] (26) IRSwT (27) IntTRSCompressionProof [EQUIVALENT, 0 ms] (28) IRSwT (29) TempFilterProof [SOUND, 353 ms] (30) IRSwT (31) IRSwTTerminationDigraphProof [EQUIVALENT, 0 ms] (32) IRSwT (33) IntTRSUnneededArgumentFilterProof [EQUIVALENT, 0 ms] (34) IRSwT (35) IRSwTOrderProof [EQUIVALENT, 0 ms] (36) YES ---------------------------------------- (0) Obligation: need to prove termination of the following program: public class Convert{ // adapted from [Giesl, 95] // converts a number to decimal notation public static void main(String[] args) { Random.args = args; IntList l = IntList.createIntList(); int b = Random.random(); int res = 0; while (l != null) { if (l.value <= 0) { l = l.next; if (l != null) res = res * b; } else { l.value--; res++; } } } } class IntList { int value; IntList next; public IntList(int value, IntList next) { this.value = value; this.next = next; } public static IntList createIntList() { int i = Random.random(); IntList l = null; while (i > 0) { l = new IntList(Random.random(), l); i--; } return l; } } public class Random { static String[] args; static int index = 0; public static int random() { String string = args[index]; index++; return string.length(); } } ---------------------------------------- (1) BareJBCToJBCProof (EQUIVALENT) initialized classpath ---------------------------------------- (2) Obligation: need to prove termination of the following program: public class Convert{ // adapted from [Giesl, 95] // converts a number to decimal notation public static void main(String[] args) { Random.args = args; IntList l = IntList.createIntList(); int b = Random.random(); int res = 0; while (l != null) { if (l.value <= 0) { l = l.next; if (l != null) res = res * b; } else { l.value--; res++; } } } } class IntList { int value; IntList next; public IntList(int value, IntList next) { this.value = value; this.next = next; } public static IntList createIntList() { int i = Random.random(); IntList l = null; while (i > 0) { l = new IntList(Random.random(), l); i--; } return l; } } public class Random { static String[] args; static int index = 0; public static int random() { String string = args[index]; index++; return string.length(); } } ---------------------------------------- (3) JBCToGraph (EQUIVALENT) Constructed TerminationGraph. ---------------------------------------- (4) Obligation: Termination Graph based on JBC Program: Convert.main([Ljava/lang/String;)V: Graph of 136 nodes with 1 SCC. IntList.createIntList()LIntList;: Graph of 277 nodes with 1 SCC. ---------------------------------------- (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: IntList.createIntList()LIntList; SCC calls the following helper methods: Performed SCC analyses: *Used field analysis yielded the following read fields: *java.lang.String: [count] *Marker field analysis yielded the following relations that could be markers: ---------------------------------------- (8) SCCToIRSProof (SOUND) Transformed FIGraph SCCs to intTRSs. Log: Generated rules. Obtained 39 IRulesP rules: f3055_0_createIntList_LE(EOS(STATIC_3055(java.lang.Object(ARRAY(i6)))), i490, i490) -> f3084_0_createIntList_LE(EOS(STATIC_3084(java.lang.Object(ARRAY(i6)))), i490, i490) :|: TRUE f3084_0_createIntList_LE(EOS(STATIC_3084(java.lang.Object(ARRAY(i6)))), i490, i490) -> f3099_0_createIntList_New(EOS(STATIC_3099(java.lang.Object(ARRAY(i6)))), i490) :|: i490 > 0 f3099_0_createIntList_New(EOS(STATIC_3099(java.lang.Object(ARRAY(i6)))), i490) -> f3110_0_createIntList_Duplicate(EOS(STATIC_3110(java.lang.Object(ARRAY(i6)))), i490) :|: TRUE f3110_0_createIntList_Duplicate(EOS(STATIC_3110(java.lang.Object(ARRAY(i6)))), i490) -> f3131_0_createIntList_InvokeMethod(EOS(STATIC_3131(java.lang.Object(ARRAY(i6)))), i490) :|: TRUE f3131_0_createIntList_InvokeMethod(EOS(STATIC_3131(java.lang.Object(ARRAY(i6)))), i490) -> f3164_0_random_FieldAccess(EOS(STATIC_3164(java.lang.Object(ARRAY(i6)))), i490) :|: TRUE f3164_0_random_FieldAccess(EOS(STATIC_3164(java.lang.Object(ARRAY(i6)))), i490) -> f3333_0_random_FieldAccess(EOS(STATIC_3333(java.lang.Object(ARRAY(i6)))), i490, java.lang.Object(ARRAY(i6))) :|: TRUE f3333_0_random_FieldAccess(EOS(STATIC_3333(java.lang.Object(ARRAY(i6)))), i490, java.lang.Object(ARRAY(i6))) -> f3347_0_random_ArrayAccess(EOS(STATIC_3347(java.lang.Object(ARRAY(i6)))), i490, java.lang.Object(ARRAY(i6))) :|: TRUE f3347_0_random_ArrayAccess(EOS(STATIC_3347(java.lang.Object(ARRAY(i6)))), i490, java.lang.Object(ARRAY(i6))) -> f3353_0_random_ArrayAccess(EOS(STATIC_3353(java.lang.Object(ARRAY(i6)))), i490, java.lang.Object(ARRAY(i6))) :|: TRUE f3353_0_random_ArrayAccess(EOS(STATIC_3353(java.lang.Object(ARRAY(i6)))), i490, java.lang.Object(ARRAY(i6))) -> f3363_0_random_Store(EOS(STATIC_3363(java.lang.Object(ARRAY(i6)))), i490, o272) :|: TRUE f3363_0_random_Store(EOS(STATIC_3363(java.lang.Object(ARRAY(i6)))), i490, o272) -> f3371_0_random_FieldAccess(EOS(STATIC_3371(java.lang.Object(ARRAY(i6)))), i490, o272) :|: TRUE f3371_0_random_FieldAccess(EOS(STATIC_3371(java.lang.Object(ARRAY(i6)))), i490, o272) -> f3381_0_random_ConstantStackPush(EOS(STATIC_3381(java.lang.Object(ARRAY(i6)))), i490, o272) :|: TRUE f3381_0_random_ConstantStackPush(EOS(STATIC_3381(java.lang.Object(ARRAY(i6)))), i490, o272) -> f3390_0_random_IntArithmetic(EOS(STATIC_3390(java.lang.Object(ARRAY(i6)))), i490, o272) :|: TRUE f3390_0_random_IntArithmetic(EOS(STATIC_3390(java.lang.Object(ARRAY(i6)))), i490, o272) -> f3399_0_random_FieldAccess(EOS(STATIC_3399(java.lang.Object(ARRAY(i6)))), i490, o272) :|: TRUE f3399_0_random_FieldAccess(EOS(STATIC_3399(java.lang.Object(ARRAY(i6)))), i490, o272) -> f3406_0_random_Load(EOS(STATIC_3406(java.lang.Object(ARRAY(i6)))), i490, o272) :|: TRUE f3406_0_random_Load(EOS(STATIC_3406(java.lang.Object(ARRAY(i6)))), i490, o272) -> f3422_0_random_InvokeMethod(EOS(STATIC_3422(java.lang.Object(ARRAY(i6)))), i490, o272) :|: TRUE f3422_0_random_InvokeMethod(EOS(STATIC_3422(java.lang.Object(ARRAY(i6)))), i490, java.lang.Object(o278sub)) -> f3432_0_random_InvokeMethod(EOS(STATIC_3432(java.lang.Object(ARRAY(i6)))), i490, java.lang.Object(o278sub)) :|: TRUE f3432_0_random_InvokeMethod(EOS(STATIC_3432(java.lang.Object(ARRAY(i6)))), i490, java.lang.Object(o279sub)) -> f3441_0_random_InvokeMethod(EOS(STATIC_3441(java.lang.Object(ARRAY(i6)))), i490, java.lang.Object(o279sub)) :|: TRUE f3441_0_random_InvokeMethod(EOS(STATIC_3441(java.lang.Object(ARRAY(i6)))), i490, java.lang.Object(o279sub)) -> f3456_0_length_Load(EOS(STATIC_3456(java.lang.Object(ARRAY(i6)))), i490, java.lang.Object(o279sub)) :|: TRUE f3456_0_length_Load(EOS(STATIC_3456(java.lang.Object(ARRAY(i6)))), i490, java.lang.Object(o279sub)) -> f3489_0_length_FieldAccess(EOS(STATIC_3489(java.lang.Object(ARRAY(i6)))), i490, java.lang.Object(o279sub)) :|: TRUE f3489_0_length_FieldAccess(EOS(STATIC_3489(java.lang.Object(ARRAY(i6)))), i490, java.lang.Object(java.lang.String(EOC, i567))) -> f3505_0_length_FieldAccess(EOS(STATIC_3505(java.lang.Object(ARRAY(i6)))), i490, java.lang.Object(java.lang.String(EOC, i567))) :|: TRUE f3505_0_length_FieldAccess(EOS(STATIC_3505(java.lang.Object(ARRAY(i6)))), i490, java.lang.Object(java.lang.String(EOC, i567))) -> f3618_0_length_Return(EOS(STATIC_3618(java.lang.Object(ARRAY(i6)))), i490) :|: TRUE f3618_0_length_Return(EOS(STATIC_3618(java.lang.Object(ARRAY(i6)))), i490) -> f3632_0_random_Return(EOS(STATIC_3632(java.lang.Object(ARRAY(i6)))), i490) :|: TRUE f3632_0_random_Return(EOS(STATIC_3632(java.lang.Object(ARRAY(i6)))), i490) -> f3649_0_createIntList_Load(EOS(STATIC_3649(java.lang.Object(ARRAY(i6)))), i490) :|: TRUE f3649_0_createIntList_Load(EOS(STATIC_3649(java.lang.Object(ARRAY(i6)))), i490) -> f3660_0_createIntList_InvokeMethod(EOS(STATIC_3660(java.lang.Object(ARRAY(i6)))), i490) :|: TRUE f3660_0_createIntList_InvokeMethod(EOS(STATIC_3660(java.lang.Object(ARRAY(i6)))), i490) -> f3673_0__init__Load(EOS(STATIC_3673(java.lang.Object(ARRAY(i6)))), i490) :|: TRUE f3673_0__init__Load(EOS(STATIC_3673(java.lang.Object(ARRAY(i6)))), i490) -> f3705_0__init__InvokeMethod(EOS(STATIC_3705(java.lang.Object(ARRAY(i6)))), i490) :|: TRUE f3705_0__init__InvokeMethod(EOS(STATIC_3705(java.lang.Object(ARRAY(i6)))), i490) -> f3720_0__init__Load(EOS(STATIC_3720(java.lang.Object(ARRAY(i6)))), i490) :|: TRUE f3720_0__init__Load(EOS(STATIC_3720(java.lang.Object(ARRAY(i6)))), i490) -> f3740_0__init__Load(EOS(STATIC_3740(java.lang.Object(ARRAY(i6)))), i490) :|: TRUE f3740_0__init__Load(EOS(STATIC_3740(java.lang.Object(ARRAY(i6)))), i490) -> f3758_0__init__FieldAccess(EOS(STATIC_3758(java.lang.Object(ARRAY(i6)))), i490) :|: TRUE f3758_0__init__FieldAccess(EOS(STATIC_3758(java.lang.Object(ARRAY(i6)))), i490) -> f3774_0__init__Load(EOS(STATIC_3774(java.lang.Object(ARRAY(i6)))), i490) :|: TRUE f3774_0__init__Load(EOS(STATIC_3774(java.lang.Object(ARRAY(i6)))), i490) -> f3800_0__init__Load(EOS(STATIC_3800(java.lang.Object(ARRAY(i6)))), i490) :|: TRUE f3800_0__init__Load(EOS(STATIC_3800(java.lang.Object(ARRAY(i6)))), i490) -> f3819_0__init__FieldAccess(EOS(STATIC_3819(java.lang.Object(ARRAY(i6)))), i490) :|: TRUE f3819_0__init__FieldAccess(EOS(STATIC_3819(java.lang.Object(ARRAY(i6)))), i490) -> f3844_0__init__Return(EOS(STATIC_3844(java.lang.Object(ARRAY(i6)))), i490) :|: TRUE f3844_0__init__Return(EOS(STATIC_3844(java.lang.Object(ARRAY(i6)))), i490) -> f3867_0_createIntList_Store(EOS(STATIC_3867(java.lang.Object(ARRAY(i6)))), i490) :|: TRUE f3867_0_createIntList_Store(EOS(STATIC_3867(java.lang.Object(ARRAY(i6)))), i490) -> f3888_0_createIntList_Inc(EOS(STATIC_3888(java.lang.Object(ARRAY(i6)))), i490) :|: TRUE f3888_0_createIntList_Inc(EOS(STATIC_3888(java.lang.Object(ARRAY(i6)))), i490) -> f4096_0_createIntList_JMP(EOS(STATIC_4096(java.lang.Object(ARRAY(i6)))), i490 + -1) :|: TRUE f4096_0_createIntList_JMP(EOS(STATIC_4096(java.lang.Object(ARRAY(i6)))), i645) -> f4141_0_createIntList_Load(EOS(STATIC_4141(java.lang.Object(ARRAY(i6)))), i645) :|: TRUE f4141_0_createIntList_Load(EOS(STATIC_4141(java.lang.Object(ARRAY(i6)))), i645) -> f3001_0_createIntList_Load(EOS(STATIC_3001(java.lang.Object(ARRAY(i6)))), i645) :|: TRUE f3001_0_createIntList_Load(EOS(STATIC_3001(java.lang.Object(ARRAY(i6)))), i449) -> f3055_0_createIntList_LE(EOS(STATIC_3055(java.lang.Object(ARRAY(i6)))), i449, i449) :|: TRUE Combined rules. Obtained 1 IRulesP rules: f3055_0_createIntList_LE(EOS(STATIC_3055(java.lang.Object(ARRAY(i6:0)))), i490:0, i490:0) -> f3055_0_createIntList_LE(EOS(STATIC_3055(java.lang.Object(ARRAY(i6:0)))), i490:0 - 1, i490:0 - 1) :|: i490:0 > 0 Filtered duplicate arguments: f3055_0_createIntList_LE(x1, x2, x3) -> f3055_0_createIntList_LE(x1, x3) Filtered unneeded arguments: f3055_0_createIntList_LE(x1, x2) -> f3055_0_createIntList_LE(x2) Finished conversion. Obtained 1 rules.P rules: f3055_0_createIntList_LE(i490:0) -> f3055_0_createIntList_LE(i490:0 - 1) :|: i490:0 > 0 ---------------------------------------- (9) Obligation: Rules: f3055_0_createIntList_LE(i490:0) -> f3055_0_createIntList_LE(i490:0 - 1) :|: i490:0 > 0 ---------------------------------------- (10) IRSFormatTransformerProof (EQUIVALENT) Reformatted IRS to match normalized format (transformed away non-linear left-hand sides, !=, / and %). ---------------------------------------- (11) Obligation: Rules: f3055_0_createIntList_LE(i490:0) -> f3055_0_createIntList_LE(arith) :|: i490:0 > 0 && arith = i490:0 - 1 ---------------------------------------- (12) IRSwTTerminationDigraphProof (EQUIVALENT) Constructed termination digraph! Nodes: (1) f3055_0_createIntList_LE(i490:0) -> f3055_0_createIntList_LE(arith) :|: i490:0 > 0 && arith = i490:0 - 1 Arcs: (1) -> (1) This digraph is fully evaluated! ---------------------------------------- (13) Obligation: Termination digraph: Nodes: (1) f3055_0_createIntList_LE(i490:0) -> f3055_0_createIntList_LE(arith) :|: i490:0 > 0 && arith = i490:0 - 1 Arcs: (1) -> (1) This digraph is fully evaluated! ---------------------------------------- (14) IntTRSCompressionProof (EQUIVALENT) Compressed rules. ---------------------------------------- (15) Obligation: Rules: f3055_0_createIntList_LE(i490:0:0) -> f3055_0_createIntList_LE(i490:0:0 - 1) :|: i490:0:0 > 0 ---------------------------------------- (16) TempFilterProof (SOUND) Used the following sort dictionary for filtering: f3055_0_createIntList_LE(INTEGER) Replaced non-predefined constructor symbols by 0. ---------------------------------------- (17) Obligation: Rules: f3055_0_createIntList_LE(i490:0:0) -> f3055_0_createIntList_LE(c) :|: c = i490:0:0 - 1 && i490:0:0 > 0 ---------------------------------------- (18) RankingReductionPairProof (EQUIVALENT) Interpretation: [ f3055_0_createIntList_LE ] = f3055_0_createIntList_LE_1 The following rules are decreasing: f3055_0_createIntList_LE(i490:0:0) -> f3055_0_createIntList_LE(c) :|: c = i490:0:0 - 1 && i490:0:0 > 0 The following rules are bounded: f3055_0_createIntList_LE(i490:0:0) -> f3055_0_createIntList_LE(c) :|: c = i490:0:0 - 1 && i490:0:0 > 0 ---------------------------------------- (19) YES ---------------------------------------- (20) Obligation: SCC of termination graph based on JBC Program. SCC contains nodes from the following methods: Convert.main([Ljava/lang/String;)V SCC calls the following helper methods: Performed SCC analyses: *Used field analysis yielded the following read fields: *IntList: [value, next] *Marker field analysis yielded the following relations that could be markers: ---------------------------------------- (21) SCCToIRSProof (SOUND) Transformed FIGraph SCCs to intTRSs. Log: Generated rules. Obtained 31 IRulesP rules: f4129_0_main_NULL(EOS(STATIC_4129), java.lang.Object(o332sub), java.lang.Object(o332sub)) -> f4162_0_main_NULL(EOS(STATIC_4162), java.lang.Object(o332sub), java.lang.Object(o332sub)) :|: TRUE f4162_0_main_NULL(EOS(STATIC_4162), java.lang.Object(o332sub), java.lang.Object(o332sub)) -> f4169_0_main_Load(EOS(STATIC_4169), java.lang.Object(o332sub)) :|: TRUE f4169_0_main_Load(EOS(STATIC_4169), java.lang.Object(o332sub)) -> f4174_0_main_FieldAccess(EOS(STATIC_4174), java.lang.Object(o332sub), java.lang.Object(o332sub)) :|: TRUE f4174_0_main_FieldAccess(EOS(STATIC_4174), java.lang.Object(IntList(EOC, i668, o338)), java.lang.Object(IntList(EOC, i668, o338))) -> f4202_0_main_FieldAccess(EOS(STATIC_4202), java.lang.Object(IntList(EOC, i668, o338)), java.lang.Object(IntList(EOC, i668, o338))) :|: TRUE f4202_0_main_FieldAccess(EOS(STATIC_4202), java.lang.Object(IntList(EOC, i668, o338)), java.lang.Object(IntList(EOC, i668, o338))) -> f4212_0_main_GT(EOS(STATIC_4212), java.lang.Object(IntList(EOC, i668, o338)), i668) :|: TRUE f4212_0_main_GT(EOS(STATIC_4212), java.lang.Object(IntList(EOC, i673, o338)), i673) -> f4214_0_main_GT(EOS(STATIC_4214), java.lang.Object(IntList(EOC, i673, o338)), i673) :|: TRUE f4212_0_main_GT(EOS(STATIC_4212), java.lang.Object(IntList(EOC, i674, o338)), i674) -> f4215_0_main_GT(EOS(STATIC_4215), java.lang.Object(IntList(EOC, i674, o338)), i674) :|: TRUE f4214_0_main_GT(EOS(STATIC_4214), java.lang.Object(IntList(EOC, i673, o338)), i673) -> f4217_0_main_Load(EOS(STATIC_4217), java.lang.Object(IntList(EOC, i673, o338))) :|: i673 <= 0 f4217_0_main_Load(EOS(STATIC_4217), java.lang.Object(IntList(EOC, i673, o338))) -> f4221_0_main_FieldAccess(EOS(STATIC_4221), java.lang.Object(IntList(EOC, i673, o338))) :|: TRUE f4221_0_main_FieldAccess(EOS(STATIC_4221), java.lang.Object(IntList(EOC, i673, o338))) -> f4225_0_main_Store(EOS(STATIC_4225), o338) :|: TRUE f4225_0_main_Store(EOS(STATIC_4225), o338) -> f4229_0_main_Load(EOS(STATIC_4229), o338) :|: TRUE f4229_0_main_Load(EOS(STATIC_4229), o338) -> f4233_0_main_NULL(EOS(STATIC_4233), o338, o338) :|: TRUE f4233_0_main_NULL(EOS(STATIC_4233), java.lang.Object(o341sub), java.lang.Object(o341sub)) -> f4238_0_main_NULL(EOS(STATIC_4238), java.lang.Object(o341sub), java.lang.Object(o341sub)) :|: TRUE f4238_0_main_NULL(EOS(STATIC_4238), java.lang.Object(o341sub), java.lang.Object(o341sub)) -> f4244_0_main_Load(EOS(STATIC_4244), java.lang.Object(o341sub)) :|: TRUE f4244_0_main_Load(EOS(STATIC_4244), java.lang.Object(o341sub)) -> f4255_0_main_Load(EOS(STATIC_4255), java.lang.Object(o341sub)) :|: TRUE f4255_0_main_Load(EOS(STATIC_4255), java.lang.Object(o341sub)) -> f4263_0_main_IntArithmetic(EOS(STATIC_4263), java.lang.Object(o341sub)) :|: TRUE f4263_0_main_IntArithmetic(EOS(STATIC_4263), java.lang.Object(o341sub)) -> f4286_0_main_Store(EOS(STATIC_4286), java.lang.Object(o341sub)) :|: TRUE f4286_0_main_Store(EOS(STATIC_4286), java.lang.Object(o341sub)) -> f4288_0_main_JMP(EOS(STATIC_4288), java.lang.Object(o341sub)) :|: TRUE f4288_0_main_JMP(EOS(STATIC_4288), java.lang.Object(o341sub)) -> f4299_0_main_Load(EOS(STATIC_4299), java.lang.Object(o341sub)) :|: TRUE f4299_0_main_Load(EOS(STATIC_4299), java.lang.Object(o341sub)) -> f4088_0_main_Load(EOS(STATIC_4088), java.lang.Object(o341sub)) :|: TRUE f4088_0_main_Load(EOS(STATIC_4088), o319) -> f4129_0_main_NULL(EOS(STATIC_4129), o319, o319) :|: TRUE f4215_0_main_GT(EOS(STATIC_4215), java.lang.Object(IntList(EOC, i674, o338)), i674) -> f4218_0_main_Load(EOS(STATIC_4218), java.lang.Object(IntList(EOC, i674, o338))) :|: i674 > 0 f4218_0_main_Load(EOS(STATIC_4218), java.lang.Object(IntList(EOC, i674, o338))) -> f4222_0_main_Duplicate(EOS(STATIC_4222), java.lang.Object(IntList(EOC, i674, o338)), java.lang.Object(IntList(EOC, i674, o338))) :|: TRUE f4222_0_main_Duplicate(EOS(STATIC_4222), java.lang.Object(IntList(EOC, i674, o338)), java.lang.Object(IntList(EOC, i674, o338))) -> f4227_0_main_FieldAccess(EOS(STATIC_4227), java.lang.Object(IntList(EOC, i674, o338)), java.lang.Object(IntList(EOC, i674, o338)), java.lang.Object(IntList(EOC, i674, o338))) :|: TRUE f4227_0_main_FieldAccess(EOS(STATIC_4227), java.lang.Object(IntList(EOC, i674, o338)), java.lang.Object(IntList(EOC, i674, o338)), java.lang.Object(IntList(EOC, i674, o338))) -> f4231_0_main_ConstantStackPush(EOS(STATIC_4231), java.lang.Object(IntList(EOC, i674, o338)), java.lang.Object(IntList(EOC, i674, o338)), i674) :|: TRUE f4231_0_main_ConstantStackPush(EOS(STATIC_4231), java.lang.Object(IntList(EOC, i674, o338)), java.lang.Object(IntList(EOC, i674, o338)), i674) -> f4235_0_main_IntArithmetic(EOS(STATIC_4235), java.lang.Object(IntList(EOC, i674, o338)), java.lang.Object(IntList(EOC, i674, o338)), i674, 1) :|: TRUE f4235_0_main_IntArithmetic(EOS(STATIC_4235), java.lang.Object(IntList(EOC, i674, o338)), java.lang.Object(IntList(EOC, i674, o338)), i674, matching1) -> f4241_0_main_FieldAccess(EOS(STATIC_4241), java.lang.Object(IntList(EOC, i674, o338)), java.lang.Object(IntList(EOC, i674, o338)), i674 - 1) :|: i674 > 0 && matching1 = 1 f4241_0_main_FieldAccess(EOS(STATIC_4241), java.lang.Object(IntList(EOC, i674, o338)), java.lang.Object(IntList(EOC, i674, o338)), i680) -> f4253_0_main_Inc(EOS(STATIC_4253), java.lang.Object(IntList(EOC, i680, o338))) :|: TRUE f4253_0_main_Inc(EOS(STATIC_4253), java.lang.Object(IntList(EOC, i680, o338))) -> f4261_0_main_JMP(EOS(STATIC_4261), java.lang.Object(IntList(EOC, i680, o338))) :|: TRUE f4261_0_main_JMP(EOS(STATIC_4261), java.lang.Object(IntList(EOC, i680, o338))) -> f4284_0_main_Load(EOS(STATIC_4284), java.lang.Object(IntList(EOC, i680, o338))) :|: TRUE f4284_0_main_Load(EOS(STATIC_4284), java.lang.Object(IntList(EOC, i680, o338))) -> f4088_0_main_Load(EOS(STATIC_4088), java.lang.Object(IntList(EOC, i680, o338))) :|: TRUE Combined rules. Obtained 2 IRulesP rules: f4129_0_main_NULL(EOS(STATIC_4129), java.lang.Object(IntList(EOC, i668:0, java.lang.Object(o341sub:0))), java.lang.Object(IntList(EOC, i668:0, java.lang.Object(o341sub:0)))) -> f4129_0_main_NULL(EOS(STATIC_4129), java.lang.Object(o341sub:0), java.lang.Object(o341sub:0)) :|: i668:0 < 1 f4129_0_main_NULL(EOS(STATIC_4129), java.lang.Object(IntList(EOC, i668:0, o338:0)), java.lang.Object(IntList(EOC, i668:0, o338:0))) -> f4129_0_main_NULL(EOS(STATIC_4129), java.lang.Object(IntList(EOC, i668:0 - 1, o338:0)), java.lang.Object(IntList(EOC, i668:0 - 1, o338:0))) :|: i668:0 > 0 Filtered constant ground arguments: f4129_0_main_NULL(x1, x2, x3) -> f4129_0_main_NULL(x2, x3) EOS(x1) -> EOS IntList(x1, x2, x3) -> IntList(x2, x3) Filtered duplicate arguments: f4129_0_main_NULL(x1, x2) -> f4129_0_main_NULL(x2) Finished conversion. Obtained 2 rules.P rules: f4129_0_main_NULL(java.lang.Object(IntList(i668:0, java.lang.Object(o341sub:0)))) -> f4129_0_main_NULL(java.lang.Object(o341sub:0)) :|: i668:0 < 1 f4129_0_main_NULL(java.lang.Object(IntList(i668:0, o338:0))) -> f4129_0_main_NULL(java.lang.Object(IntList(i668:0 - 1, o338:0))) :|: i668:0 > 0 ---------------------------------------- (22) Obligation: Rules: f4129_0_main_NULL(java.lang.Object(IntList(i668:0, java.lang.Object(o341sub:0)))) -> f4129_0_main_NULL(java.lang.Object(o341sub:0)) :|: i668:0 < 1 f4129_0_main_NULL(java.lang.Object(IntList(x, x1))) -> f4129_0_main_NULL(java.lang.Object(IntList(x - 1, x1))) :|: x > 0 ---------------------------------------- (23) IRSFormatTransformerProof (EQUIVALENT) Reformatted IRS to match normalized format (transformed away non-linear left-hand sides, !=, / and %). ---------------------------------------- (24) Obligation: Rules: f4129_0_main_NULL(java.lang.Object(IntList(i668:0, java.lang.Object(o341sub:0)))) -> f4129_0_main_NULL(java.lang.Object(o341sub:0)) :|: i668:0 < 1 f4129_0_main_NULL(java.lang.Object(IntList(x, x1))) -> f4129_0_main_NULL(java.lang.Object(IntList(arith, x1))) :|: x > 0 && arith = x - 1 ---------------------------------------- (25) IRSwTTerminationDigraphProof (EQUIVALENT) Constructed termination digraph! Nodes: (1) f4129_0_main_NULL(java.lang.Object(IntList(i668:0, java.lang.Object(o341sub:0)))) -> f4129_0_main_NULL(java.lang.Object(o341sub:0)) :|: i668:0 < 1 (2) f4129_0_main_NULL(java.lang.Object(IntList(x, x1))) -> f4129_0_main_NULL(java.lang.Object(IntList(arith, x1))) :|: x > 0 && arith = x - 1 Arcs: (1) -> (1), (2) (2) -> (1), (2) This digraph is fully evaluated! ---------------------------------------- (26) Obligation: Termination digraph: Nodes: (1) f4129_0_main_NULL(java.lang.Object(IntList(i668:0, java.lang.Object(o341sub:0)))) -> f4129_0_main_NULL(java.lang.Object(o341sub:0)) :|: i668:0 < 1 (2) f4129_0_main_NULL(java.lang.Object(IntList(x, x1))) -> f4129_0_main_NULL(java.lang.Object(IntList(arith, x1))) :|: x > 0 && arith = x - 1 Arcs: (1) -> (1), (2) (2) -> (1), (2) This digraph is fully evaluated! ---------------------------------------- (27) IntTRSCompressionProof (EQUIVALENT) Compressed rules. ---------------------------------------- (28) Obligation: Rules: f4129_0_main_NULL(java.lang.Object(IntList(i668:0:0, java.lang.Object(o341sub:0:0)))) -> f4129_0_main_NULL(java.lang.Object(o341sub:0:0)) :|: i668:0:0 < 1 f4129_0_main_NULL(java.lang.Object(IntList(x:0, x1:0))) -> f4129_0_main_NULL(java.lang.Object(IntList(x:0 - 1, x1:0))) :|: x:0 > 0 ---------------------------------------- (29) TempFilterProof (SOUND) Used the following sort dictionary for filtering: f4129_0_main_NULL(VARIABLE) java.lang.Object(VARIABLE) IntList(INTEGER, VARIABLE) Removed predefined arithmetic.The following proof was generated: # AProVE Commit ID: 794c25de1cacf0d048858bcd21c9a779e1221865 marcel 20200619 unpublished dirty Termination of the given IRSwT could not be shown: - IRSwT - IRSwTToQDPProof Rules: f4129_0_main_NULL(java.lang.Object(IntList(java.lang.Object(o341sub:0:0)))) -> f4129_0_main_NULL(java.lang.Object(o341sub:0:0)) f4129_0_main_NULL(java.lang.Object(IntList(x1:0))) -> f4129_0_main_NULL(java.lang.Object(IntList(x1:0))) Removed the integers and created a QDP-Problem. - IRSwT - IRSwTToQDPProof - QDP - MRRProof Q DP problem: The TRS P consists of the following rules: f4129_0_main_NULL(java.lang.Object(IntList(java.lang.Object(o341sub:0:0)))) -> f4129_0_main_NULL(java.lang.Object(o341sub:0:0)) f4129_0_main_NULL(java.lang.Object(IntList(x1:0))) -> f4129_0_main_NULL(java.lang.Object(IntList(x1:0))) R is empty. Q is empty. We have to consider all (P,Q,R)-chains. By using the rule removal processor [LPAR04] with the following ordering, at least one Dependency Pair or term rewrite system rule of this QDP problem can be strictly oriented. Strictly oriented dependency pairs: f4129_0_main_NULL(java.lang.Object(IntList(java.lang.Object(o341sub:0:0)))) -> f4129_0_main_NULL(java.lang.Object(o341sub:0:0)) Used ordering: Knuth-Bendix order [KBO] with precedence:IntList_1 > java.lang.Object_1 > f4129_0_main_NULL_1 and weight map: f4129_0_main_NULL_1=1 java.lang.Object_1=1 IntList_1=1 The variable weight is 1 - IRSwT - IRSwTToQDPProof - QDP - MRRProof - QDP Q DP problem: The TRS P consists of the following rules: f4129_0_main_NULL(java.lang.Object(IntList(x1:0))) -> f4129_0_main_NULL(java.lang.Object(IntList(x1:0))) R is empty. Q is empty. We have to consider all (P,Q,R)-chains. ---------------------------------------- (30) Obligation: Rules: f4129_0_main_NULL(java.lang.Object(IntList(x:0, x1:0))) -> f4129_0_main_NULL(java.lang.Object(IntList(x:0 - 1, x1:0))) :|: x:0 > 0 ---------------------------------------- (31) IRSwTTerminationDigraphProof (EQUIVALENT) Constructed termination digraph! Nodes: (1) f4129_0_main_NULL(java.lang.Object(IntList(x:0, x1:0))) -> f4129_0_main_NULL(java.lang.Object(IntList(x:0 - 1, x1:0))) :|: x:0 > 0 Arcs: (1) -> (1) This digraph is fully evaluated! ---------------------------------------- (32) Obligation: Termination digraph: Nodes: (1) f4129_0_main_NULL(java.lang.Object(IntList(x:0, x1:0))) -> f4129_0_main_NULL(java.lang.Object(IntList(x:0 - 1, x1:0))) :|: x:0 > 0 Arcs: (1) -> (1) This digraph is fully evaluated! ---------------------------------------- (33) IntTRSUnneededArgumentFilterProof (EQUIVALENT) Some arguments are removed because they cannot influence termination. We removed arguments according to the following replacements: IntList(x1, x2) -> IntList(x1) ---------------------------------------- (34) Obligation: Rules: f4129_0_main_NULL(java.lang.Object(IntList(x:0))) -> f4129_0_main_NULL(java.lang.Object(IntList(x:0 - 1))) :|: x:0 > 0 ---------------------------------------- (35) IRSwTOrderProof (EQUIVALENT) [f4129_0_main_NULL(x)] = -9 + 1*x [java.lang.Object(x1)] = 0 + 3*x1 [IntList(x2)] = 0 + 3*x2 The following rules are decreasing: f4129_0_main_NULL(java.lang.Object(IntList(x:0))) -> f4129_0_main_NULL(java.lang.Object(IntList(x:0 - 1))) :|: x:0 > 0 The following rules are bounded: f4129_0_main_NULL(java.lang.Object(IntList(x:0))) -> f4129_0_main_NULL(java.lang.Object(IntList(x:0 - 1))) :|: x:0 > 0 ---------------------------------------- (36) YES