/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, 966 ms] (4) JBCTerminationGraph (5) TerminationGraphToSCCProof [SOUND, 0 ms] (6) AND (7) JBCTerminationSCC (8) SCCToQDPProof [SOUND, 191 ms] (9) QDP (10) QDPSizeChangeProof [EQUIVALENT, 0 ms] (11) YES (12) JBCTerminationSCC (13) SCCToIRSProof [SOUND, 97 ms] (14) IRSwT (15) IRSFormatTransformerProof [EQUIVALENT, 0 ms] (16) IRSwT (17) IRSwTTerminationDigraphProof [EQUIVALENT, 30 ms] (18) IRSwT (19) IntTRSCompressionProof [EQUIVALENT, 0 ms] (20) IRSwT (21) TempFilterProof [SOUND, 32 ms] (22) IntTRS (23) RankingReductionPairProof [EQUIVALENT, 1 ms] (24) YES ---------------------------------------- (0) Obligation: need to prove termination of the following program: public class BTreeR { private BTreeR left, right; public BTreeR(int height) { if (height > 1) { this.left = new BTreeR(height - 1); this.right = new BTreeR(height - 1); } } public int height() { if (left == null && right == null) return 1; else if (left == null) return 1 + right.height(); else return 1 + left.height(); } public static void main(String[] args) { Random.args = args; BTreeR bt = new BTreeR(Random.random()*Random.random()+10); bt.height(); } } public class Random { static String[] args; static int index = 0; public static int random() { if (index >= args.length) return 0; 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 BTreeR { private BTreeR left, right; public BTreeR(int height) { if (height > 1) { this.left = new BTreeR(height - 1); this.right = new BTreeR(height - 1); } } public int height() { if (left == null && right == null) return 1; else if (left == null) return 1 + right.height(); else return 1 + left.height(); } public static void main(String[] args) { Random.args = args; BTreeR bt = new BTreeR(Random.random()*Random.random()+10); bt.height(); } } public class Random { static String[] args; static int index = 0; public static int random() { if (index >= args.length) return 0; String string = args[index]; index++; return string.length(); } } ---------------------------------------- (3) JBCToGraph (EQUIVALENT) Constructed TerminationGraph. ---------------------------------------- (4) Obligation: Termination Graph based on JBC Program: BTreeR.main([Ljava/lang/String;)V: Graph of 283 nodes with 0 SCCs. BTreeR.(I)V: Graph of 40 nodes with 0 SCCs. BTreeR.height()I: Graph of 52 nodes with 0 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: BTreeR.height()I SCC calls the following helper methods: BTreeR.height()I Performed SCC analyses: *Used field analysis yielded the following read fields: *BTreeR: [left, right] *Marker field analysis yielded the following relations that could be markers: ---------------------------------------- (8) SCCToQDPProof (SOUND) Transformed TerminationGraph SCC to QDP. Log: Generated 29 rules for P and 54 rules for R.P rules: f1472_0_height_FieldAccess(EOS(STATIC_1472), java.lang.Object(BTreeR(EOC, o497, o498)), java.lang.Object(BTreeR(EOC, o497, o498))) -> f1477_0_height_FieldAccess(EOS(STATIC_1477), java.lang.Object(BTreeR(EOC, o497, o498)), java.lang.Object(BTreeR(EOC, o497, o498))) :|: TRUE f1477_0_height_FieldAccess(EOS(STATIC_1477), java.lang.Object(BTreeR(EOC, o497, o498)), java.lang.Object(BTreeR(EOC, o497, o498))) -> f1482_0_height_NONNULL(EOS(STATIC_1482), java.lang.Object(BTreeR(EOC, o497, o498)), o497) :|: TRUE f1482_0_height_NONNULL(EOS(STATIC_1482), java.lang.Object(BTreeR(EOC, java.lang.Object(o517sub), o498)), java.lang.Object(o517sub)) -> f1487_0_height_NONNULL(EOS(STATIC_1487), java.lang.Object(BTreeR(EOC, java.lang.Object(o517sub), o498)), java.lang.Object(o517sub)) :|: TRUE f1482_0_height_NONNULL(EOS(STATIC_1482), java.lang.Object(BTreeR(EOC, NULL, o498)), NULL) -> f1488_0_height_NONNULL(EOS(STATIC_1488), java.lang.Object(BTreeR(EOC, NULL, o498)), NULL) :|: TRUE f1487_0_height_NONNULL(EOS(STATIC_1487), java.lang.Object(BTreeR(EOC, java.lang.Object(o517sub), o498)), java.lang.Object(o517sub)) -> f1491_0_height_Load(EOS(STATIC_1491), java.lang.Object(BTreeR(EOC, java.lang.Object(o517sub), o498))) :|: TRUE f1491_0_height_Load(EOS(STATIC_1491), java.lang.Object(BTreeR(EOC, java.lang.Object(o517sub), o498))) -> f1497_0_height_FieldAccess(EOS(STATIC_1497), java.lang.Object(BTreeR(EOC, java.lang.Object(o517sub), o498)), java.lang.Object(BTreeR(EOC, java.lang.Object(o517sub), o498))) :|: TRUE f1497_0_height_FieldAccess(EOS(STATIC_1497), java.lang.Object(BTreeR(EOC, java.lang.Object(o517sub), o498)), java.lang.Object(BTreeR(EOC, java.lang.Object(o517sub), o498))) -> f1500_0_height_NONNULL(EOS(STATIC_1500), java.lang.Object(BTreeR(EOC, java.lang.Object(o517sub), o498)), java.lang.Object(o517sub)) :|: TRUE f1500_0_height_NONNULL(EOS(STATIC_1500), java.lang.Object(BTreeR(EOC, java.lang.Object(o517sub), o498)), java.lang.Object(o517sub)) -> f1502_0_height_ConstantStackPush(EOS(STATIC_1502), java.lang.Object(BTreeR(EOC, java.lang.Object(o517sub), o498))) :|: TRUE f1502_0_height_ConstantStackPush(EOS(STATIC_1502), java.lang.Object(BTreeR(EOC, java.lang.Object(o517sub), o498))) -> f1505_0_height_Load(EOS(STATIC_1505), java.lang.Object(BTreeR(EOC, java.lang.Object(o517sub), o498))) :|: TRUE f1505_0_height_Load(EOS(STATIC_1505), java.lang.Object(BTreeR(EOC, java.lang.Object(o517sub), o498))) -> f1508_0_height_FieldAccess(EOS(STATIC_1508), java.lang.Object(BTreeR(EOC, java.lang.Object(o517sub), o498))) :|: TRUE f1508_0_height_FieldAccess(EOS(STATIC_1508), java.lang.Object(BTreeR(EOC, java.lang.Object(o517sub), o498))) -> f1512_0_height_InvokeMethod(EOS(STATIC_1512), java.lang.Object(o517sub)) :|: TRUE f1512_0_height_InvokeMethod(EOS(STATIC_1512), java.lang.Object(o517sub)) -> f1516_1_height_InvokeMethod(f1516_0_height_Load(EOS(STATIC_1516), java.lang.Object(o517sub))) :|: TRUE f1516_0_height_Load(EOS(STATIC_1516), java.lang.Object(o517sub)) -> f1525_0_height_Load(EOS(STATIC_1525), java.lang.Object(o517sub)) :|: TRUE f1525_0_height_Load(EOS(STATIC_1525), java.lang.Object(o517sub)) -> f1467_0_height_Load(EOS(STATIC_1467), java.lang.Object(o517sub)) :|: TRUE f1467_0_height_Load(EOS(STATIC_1467), java.lang.Object(o494sub)) -> f1472_0_height_FieldAccess(EOS(STATIC_1472), java.lang.Object(o494sub), java.lang.Object(o494sub)) :|: TRUE f1488_0_height_NONNULL(EOS(STATIC_1488), java.lang.Object(BTreeR(EOC, NULL, o498)), NULL) -> f1492_0_height_Load(EOS(STATIC_1492), java.lang.Object(BTreeR(EOC, NULL, o498))) :|: TRUE f1492_0_height_Load(EOS(STATIC_1492), java.lang.Object(BTreeR(EOC, NULL, o498))) -> f1498_0_height_FieldAccess(EOS(STATIC_1498), java.lang.Object(BTreeR(EOC, NULL, o498)), java.lang.Object(BTreeR(EOC, NULL, o498))) :|: TRUE f1498_0_height_FieldAccess(EOS(STATIC_1498), java.lang.Object(BTreeR(EOC, NULL, o498)), java.lang.Object(BTreeR(EOC, NULL, o498))) -> f1501_0_height_NONNULL(EOS(STATIC_1501), java.lang.Object(BTreeR(EOC, NULL, o498)), o498) :|: TRUE f1501_0_height_NONNULL(EOS(STATIC_1501), java.lang.Object(BTreeR(EOC, NULL, java.lang.Object(o536sub))), java.lang.Object(o536sub)) -> f1503_0_height_NONNULL(EOS(STATIC_1503), java.lang.Object(BTreeR(EOC, NULL, java.lang.Object(o536sub))), java.lang.Object(o536sub)) :|: TRUE f1503_0_height_NONNULL(EOS(STATIC_1503), java.lang.Object(BTreeR(EOC, NULL, java.lang.Object(o536sub))), java.lang.Object(o536sub)) -> f1506_0_height_Load(EOS(STATIC_1506), java.lang.Object(BTreeR(EOC, NULL, java.lang.Object(o536sub)))) :|: TRUE f1506_0_height_Load(EOS(STATIC_1506), java.lang.Object(BTreeR(EOC, NULL, java.lang.Object(o536sub)))) -> f1509_0_height_FieldAccess(EOS(STATIC_1509), java.lang.Object(BTreeR(EOC, NULL, java.lang.Object(o536sub))), java.lang.Object(BTreeR(EOC, NULL, java.lang.Object(o536sub)))) :|: TRUE f1509_0_height_FieldAccess(EOS(STATIC_1509), java.lang.Object(BTreeR(EOC, NULL, java.lang.Object(o536sub))), java.lang.Object(BTreeR(EOC, NULL, java.lang.Object(o536sub)))) -> f1513_0_height_NONNULL(EOS(STATIC_1513), java.lang.Object(BTreeR(EOC, NULL, java.lang.Object(o536sub))), NULL) :|: TRUE f1513_0_height_NONNULL(EOS(STATIC_1513), java.lang.Object(BTreeR(EOC, NULL, java.lang.Object(o536sub))), NULL) -> f1517_0_height_ConstantStackPush(EOS(STATIC_1517), java.lang.Object(BTreeR(EOC, NULL, java.lang.Object(o536sub)))) :|: TRUE f1517_0_height_ConstantStackPush(EOS(STATIC_1517), java.lang.Object(BTreeR(EOC, NULL, java.lang.Object(o536sub)))) -> f1526_0_height_Load(EOS(STATIC_1526), java.lang.Object(BTreeR(EOC, NULL, java.lang.Object(o536sub)))) :|: TRUE f1526_0_height_Load(EOS(STATIC_1526), java.lang.Object(BTreeR(EOC, NULL, java.lang.Object(o536sub)))) -> f1531_0_height_FieldAccess(EOS(STATIC_1531), java.lang.Object(BTreeR(EOC, NULL, java.lang.Object(o536sub)))) :|: TRUE f1531_0_height_FieldAccess(EOS(STATIC_1531), java.lang.Object(BTreeR(EOC, NULL, java.lang.Object(o536sub)))) -> f1539_0_height_InvokeMethod(EOS(STATIC_1539), java.lang.Object(o536sub)) :|: TRUE f1539_0_height_InvokeMethod(EOS(STATIC_1539), java.lang.Object(o536sub)) -> f1554_1_height_InvokeMethod(f1554_0_height_Load(EOS(STATIC_1554), java.lang.Object(o536sub))) :|: TRUE f1554_0_height_Load(EOS(STATIC_1554), java.lang.Object(o536sub)) -> f1560_0_height_Load(EOS(STATIC_1560), java.lang.Object(o536sub)) :|: TRUE f1560_0_height_Load(EOS(STATIC_1560), java.lang.Object(o536sub)) -> f1467_0_height_Load(EOS(STATIC_1467), java.lang.Object(o536sub)) :|: TRUE R rules: f1467_0_height_Load(EOS(STATIC_1467), java.lang.Object(o494sub)) -> f1472_0_height_FieldAccess(EOS(STATIC_1472), java.lang.Object(o494sub), java.lang.Object(o494sub)) :|: TRUE f1472_0_height_FieldAccess(EOS(STATIC_1472), java.lang.Object(BTreeR(EOC, o497, o498)), java.lang.Object(BTreeR(EOC, o497, o498))) -> f1477_0_height_FieldAccess(EOS(STATIC_1477), java.lang.Object(BTreeR(EOC, o497, o498)), java.lang.Object(BTreeR(EOC, o497, o498))) :|: TRUE f1477_0_height_FieldAccess(EOS(STATIC_1477), java.lang.Object(BTreeR(EOC, o497, o498)), java.lang.Object(BTreeR(EOC, o497, o498))) -> f1482_0_height_NONNULL(EOS(STATIC_1482), java.lang.Object(BTreeR(EOC, o497, o498)), o497) :|: TRUE f1482_0_height_NONNULL(EOS(STATIC_1482), java.lang.Object(BTreeR(EOC, java.lang.Object(o517sub), o498)), java.lang.Object(o517sub)) -> f1487_0_height_NONNULL(EOS(STATIC_1487), java.lang.Object(BTreeR(EOC, java.lang.Object(o517sub), o498)), java.lang.Object(o517sub)) :|: TRUE f1482_0_height_NONNULL(EOS(STATIC_1482), java.lang.Object(BTreeR(EOC, NULL, o498)), NULL) -> f1488_0_height_NONNULL(EOS(STATIC_1488), java.lang.Object(BTreeR(EOC, NULL, o498)), NULL) :|: TRUE f1487_0_height_NONNULL(EOS(STATIC_1487), java.lang.Object(BTreeR(EOC, java.lang.Object(o517sub), o498)), java.lang.Object(o517sub)) -> f1491_0_height_Load(EOS(STATIC_1491), java.lang.Object(BTreeR(EOC, java.lang.Object(o517sub), o498))) :|: TRUE f1488_0_height_NONNULL(EOS(STATIC_1488), java.lang.Object(BTreeR(EOC, NULL, o498)), NULL) -> f1492_0_height_Load(EOS(STATIC_1492), java.lang.Object(BTreeR(EOC, NULL, o498))) :|: TRUE f1491_0_height_Load(EOS(STATIC_1491), java.lang.Object(BTreeR(EOC, java.lang.Object(o517sub), o498))) -> f1497_0_height_FieldAccess(EOS(STATIC_1497), java.lang.Object(BTreeR(EOC, java.lang.Object(o517sub), o498)), java.lang.Object(BTreeR(EOC, java.lang.Object(o517sub), o498))) :|: TRUE f1492_0_height_Load(EOS(STATIC_1492), java.lang.Object(BTreeR(EOC, NULL, o498))) -> f1498_0_height_FieldAccess(EOS(STATIC_1498), java.lang.Object(BTreeR(EOC, NULL, o498)), java.lang.Object(BTreeR(EOC, NULL, o498))) :|: TRUE f1497_0_height_FieldAccess(EOS(STATIC_1497), java.lang.Object(BTreeR(EOC, java.lang.Object(o517sub), o498)), java.lang.Object(BTreeR(EOC, java.lang.Object(o517sub), o498))) -> f1500_0_height_NONNULL(EOS(STATIC_1500), java.lang.Object(BTreeR(EOC, java.lang.Object(o517sub), o498)), java.lang.Object(o517sub)) :|: TRUE f1498_0_height_FieldAccess(EOS(STATIC_1498), java.lang.Object(BTreeR(EOC, NULL, o498)), java.lang.Object(BTreeR(EOC, NULL, o498))) -> f1501_0_height_NONNULL(EOS(STATIC_1501), java.lang.Object(BTreeR(EOC, NULL, o498)), o498) :|: TRUE f1500_0_height_NONNULL(EOS(STATIC_1500), java.lang.Object(BTreeR(EOC, java.lang.Object(o517sub), o498)), java.lang.Object(o517sub)) -> f1502_0_height_ConstantStackPush(EOS(STATIC_1502), java.lang.Object(BTreeR(EOC, java.lang.Object(o517sub), o498))) :|: TRUE f1501_0_height_NONNULL(EOS(STATIC_1501), java.lang.Object(BTreeR(EOC, NULL, java.lang.Object(o536sub))), java.lang.Object(o536sub)) -> f1503_0_height_NONNULL(EOS(STATIC_1503), java.lang.Object(BTreeR(EOC, NULL, java.lang.Object(o536sub))), java.lang.Object(o536sub)) :|: TRUE f1501_0_height_NONNULL(EOS(STATIC_1501), java.lang.Object(BTreeR(EOC, NULL, NULL)), NULL) -> f1504_0_height_NONNULL(EOS(STATIC_1504), java.lang.Object(BTreeR(EOC, NULL, NULL)), NULL) :|: TRUE f1502_0_height_ConstantStackPush(EOS(STATIC_1502), java.lang.Object(BTreeR(EOC, java.lang.Object(o517sub), o498))) -> f1505_0_height_Load(EOS(STATIC_1505), java.lang.Object(BTreeR(EOC, java.lang.Object(o517sub), o498))) :|: TRUE f1503_0_height_NONNULL(EOS(STATIC_1503), java.lang.Object(BTreeR(EOC, NULL, java.lang.Object(o536sub))), java.lang.Object(o536sub)) -> f1506_0_height_Load(EOS(STATIC_1506), java.lang.Object(BTreeR(EOC, NULL, java.lang.Object(o536sub)))) :|: TRUE f1504_0_height_NONNULL(EOS(STATIC_1504), java.lang.Object(BTreeR(EOC, NULL, NULL)), NULL) -> f1507_0_height_ConstantStackPush(EOS(STATIC_1507)) :|: TRUE f1505_0_height_Load(EOS(STATIC_1505), java.lang.Object(BTreeR(EOC, java.lang.Object(o517sub), o498))) -> f1508_0_height_FieldAccess(EOS(STATIC_1508), java.lang.Object(BTreeR(EOC, java.lang.Object(o517sub), o498))) :|: TRUE f1506_0_height_Load(EOS(STATIC_1506), java.lang.Object(BTreeR(EOC, NULL, java.lang.Object(o536sub)))) -> f1509_0_height_FieldAccess(EOS(STATIC_1509), java.lang.Object(BTreeR(EOC, NULL, java.lang.Object(o536sub))), java.lang.Object(BTreeR(EOC, NULL, java.lang.Object(o536sub)))) :|: TRUE f1507_0_height_ConstantStackPush(EOS(STATIC_1507)) -> f1510_0_height_Return(EOS(STATIC_1510)) :|: TRUE f1508_0_height_FieldAccess(EOS(STATIC_1508), java.lang.Object(BTreeR(EOC, java.lang.Object(o517sub), o498))) -> f1512_0_height_InvokeMethod(EOS(STATIC_1512), java.lang.Object(o517sub)) :|: TRUE f1509_0_height_FieldAccess(EOS(STATIC_1509), java.lang.Object(BTreeR(EOC, NULL, java.lang.Object(o536sub))), java.lang.Object(BTreeR(EOC, NULL, java.lang.Object(o536sub)))) -> f1513_0_height_NONNULL(EOS(STATIC_1513), java.lang.Object(BTreeR(EOC, NULL, java.lang.Object(o536sub))), NULL) :|: TRUE f1512_0_height_InvokeMethod(EOS(STATIC_1512), java.lang.Object(o517sub)) -> f1516_1_height_InvokeMethod(f1516_0_height_Load(EOS(STATIC_1516), java.lang.Object(o517sub))) :|: TRUE f1513_0_height_NONNULL(EOS(STATIC_1513), java.lang.Object(BTreeR(EOC, NULL, java.lang.Object(o536sub))), NULL) -> f1517_0_height_ConstantStackPush(EOS(STATIC_1517), java.lang.Object(BTreeR(EOC, NULL, java.lang.Object(o536sub)))) :|: TRUE f1516_0_height_Load(EOS(STATIC_1516), java.lang.Object(o517sub)) -> f1525_0_height_Load(EOS(STATIC_1525), java.lang.Object(o517sub)) :|: TRUE f1517_0_height_ConstantStackPush(EOS(STATIC_1517), java.lang.Object(BTreeR(EOC, NULL, java.lang.Object(o536sub)))) -> f1526_0_height_Load(EOS(STATIC_1526), java.lang.Object(BTreeR(EOC, NULL, java.lang.Object(o536sub)))) :|: TRUE f1526_0_height_Load(EOS(STATIC_1526), java.lang.Object(BTreeR(EOC, NULL, java.lang.Object(o536sub)))) -> f1531_0_height_FieldAccess(EOS(STATIC_1531), java.lang.Object(BTreeR(EOC, NULL, java.lang.Object(o536sub)))) :|: TRUE f1531_0_height_FieldAccess(EOS(STATIC_1531), java.lang.Object(BTreeR(EOC, NULL, java.lang.Object(o536sub)))) -> f1539_0_height_InvokeMethod(EOS(STATIC_1539), java.lang.Object(o536sub)) :|: TRUE f1539_0_height_InvokeMethod(EOS(STATIC_1539), java.lang.Object(o536sub)) -> f1554_1_height_InvokeMethod(f1554_0_height_Load(EOS(STATIC_1554), java.lang.Object(o536sub))) :|: TRUE f1554_0_height_Load(EOS(STATIC_1554), java.lang.Object(o536sub)) -> f1560_0_height_Load(EOS(STATIC_1560), java.lang.Object(o536sub)) :|: TRUE f1559_0_height_Return(EOS(STATIC_1559)) -> f1562_0_height_IntArithmetic(EOS(STATIC_1562)) :|: TRUE f1562_0_height_IntArithmetic(EOS(STATIC_1562)) -> f1743_0_height_IntArithmetic(EOS(STATIC_1743)) :|: TRUE f1593_0_height_Return(EOS(STATIC_1593)) -> f1601_0_height_IntArithmetic(EOS(STATIC_1601)) :|: TRUE f1601_0_height_IntArithmetic(EOS(STATIC_1601)) -> f1744_0_height_IntArithmetic(EOS(STATIC_1744)) :|: TRUE f1723_0_height_Return(EOS(STATIC_1723)) -> f1743_0_height_IntArithmetic(EOS(STATIC_1743)) :|: TRUE f1725_0_height_Return(EOS(STATIC_1725)) -> f1744_0_height_IntArithmetic(EOS(STATIC_1744)) :|: TRUE f1733_0_height_Return(EOS(STATIC_1733)) -> f1748_0_height_IntArithmetic(EOS(STATIC_1748)) :|: TRUE f1735_0_height_Return(EOS(STATIC_1735)) -> f1749_0_height_IntArithmetic(EOS(STATIC_1749)) :|: TRUE f1743_0_height_IntArithmetic(EOS(STATIC_1743)) -> f1754_0_height_Return(EOS(STATIC_1754)) :|: TRUE f1744_0_height_IntArithmetic(EOS(STATIC_1744)) -> f1755_0_height_Return(EOS(STATIC_1755)) :|: TRUE f1748_0_height_IntArithmetic(EOS(STATIC_1748)) -> f1743_0_height_IntArithmetic(EOS(STATIC_1743)) :|: TRUE f1749_0_height_IntArithmetic(EOS(STATIC_1749)) -> f1744_0_height_IntArithmetic(EOS(STATIC_1744)) :|: TRUE f1771_0_height_Return(EOS(STATIC_1771)) -> f1723_0_height_Return(EOS(STATIC_1723)) :|: TRUE f1772_0_height_Return(EOS(STATIC_1772)) -> f1725_0_height_Return(EOS(STATIC_1725)) :|: TRUE f1776_0_height_Return(EOS(STATIC_1776)) -> f1733_0_height_Return(EOS(STATIC_1733)) :|: TRUE f1777_0_height_Return(EOS(STATIC_1777)) -> f1735_0_height_Return(EOS(STATIC_1735)) :|: TRUE f1525_0_height_Load(EOS(STATIC_1525), java.lang.Object(o517sub)) -> f1467_0_height_Load(EOS(STATIC_1467), java.lang.Object(o517sub)) :|: TRUE f1560_0_height_Load(EOS(STATIC_1560), java.lang.Object(o536sub)) -> f1467_0_height_Load(EOS(STATIC_1467), java.lang.Object(o536sub)) :|: TRUE f1516_1_height_InvokeMethod(f1510_0_height_Return(EOS(STATIC_1510))) -> f1559_0_height_Return(EOS(STATIC_1559)) :|: TRUE f1516_1_height_InvokeMethod(f1754_0_height_Return(EOS(STATIC_1754))) -> f1771_0_height_Return(EOS(STATIC_1771)) :|: TRUE f1516_1_height_InvokeMethod(f1755_0_height_Return(EOS(STATIC_1755))) -> f1776_0_height_Return(EOS(STATIC_1776)) :|: TRUE f1554_1_height_InvokeMethod(f1510_0_height_Return(EOS(STATIC_1510))) -> f1593_0_height_Return(EOS(STATIC_1593)) :|: TRUE f1554_1_height_InvokeMethod(f1754_0_height_Return(EOS(STATIC_1754))) -> f1772_0_height_Return(EOS(STATIC_1772)) :|: TRUE f1554_1_height_InvokeMethod(f1755_0_height_Return(EOS(STATIC_1755))) -> f1777_0_height_Return(EOS(STATIC_1777)) :|: TRUE Combined rules. Obtained 2 conditional rules for P and 9 conditional rules for R.P rules: f1472_0_height_FieldAccess(EOS(STATIC_1472), java.lang.Object(BTreeR(EOC, java.lang.Object(o517sub:0), o498:0)), java.lang.Object(BTreeR(EOC, java.lang.Object(o517sub:0), o498:0))) -> f1516_1_height_InvokeMethod(f1472_0_height_FieldAccess(EOS(STATIC_1472), java.lang.Object(o517sub:0), java.lang.Object(o517sub:0))) :|: TRUE f1472_0_height_FieldAccess(EOS(STATIC_1472), java.lang.Object(BTreeR(EOC, NULL, java.lang.Object(o536sub:0))), java.lang.Object(BTreeR(EOC, NULL, java.lang.Object(o536sub:0)))) -> f1554_1_height_InvokeMethod(f1472_0_height_FieldAccess(EOS(STATIC_1472), java.lang.Object(o536sub:0), java.lang.Object(o536sub:0))) :|: TRUE R rules: f1554_1_height_InvokeMethod(f1755_0_height_Return(EOS(STATIC_1755))) -> f1755_0_height_Return(EOS(STATIC_1755)) :|: TRUE f1554_1_height_InvokeMethod(f1510_0_height_Return(EOS(STATIC_1510))) -> f1755_0_height_Return(EOS(STATIC_1755)) :|: TRUE f1516_1_height_InvokeMethod(f1510_0_height_Return(EOS(STATIC_1510))) -> f1754_0_height_Return(EOS(STATIC_1754)) :|: TRUE f1472_0_height_FieldAccess(EOS(STATIC_1472), java.lang.Object(BTreeR(EOC, NULL, java.lang.Object(o536sub:0))), java.lang.Object(BTreeR(EOC, NULL, java.lang.Object(o536sub:0)))) -> f1554_1_height_InvokeMethod(f1472_0_height_FieldAccess(EOS(STATIC_1472), java.lang.Object(o536sub:0), java.lang.Object(o536sub:0))) :|: TRUE f1516_1_height_InvokeMethod(f1754_0_height_Return(EOS(STATIC_1754))) -> f1754_0_height_Return(EOS(STATIC_1754)) :|: TRUE f1472_0_height_FieldAccess(EOS(STATIC_1472), java.lang.Object(BTreeR(EOC, NULL, NULL)), java.lang.Object(BTreeR(EOC, NULL, NULL))) -> f1510_0_height_Return(EOS(STATIC_1510)) :|: TRUE f1516_1_height_InvokeMethod(f1755_0_height_Return(EOS(STATIC_1755))) -> f1754_0_height_Return(EOS(STATIC_1754)) :|: TRUE f1472_0_height_FieldAccess(EOS(STATIC_1472), java.lang.Object(BTreeR(EOC, java.lang.Object(o517sub:0), o498:0)), java.lang.Object(BTreeR(EOC, java.lang.Object(o517sub:0), o498:0))) -> f1516_1_height_InvokeMethod(f1472_0_height_FieldAccess(EOS(STATIC_1472), java.lang.Object(o517sub:0), java.lang.Object(o517sub:0))) :|: TRUE f1554_1_height_InvokeMethod(f1754_0_height_Return(EOS(STATIC_1754))) -> f1755_0_height_Return(EOS(STATIC_1755)) :|: TRUE Filtered ground terms: f1472_0_height_FieldAccess(x1, x2, x3) -> f1472_0_height_FieldAccess(x2, x3) BTreeR(x1, x2, x3) -> BTreeR(x2, x3) f1755_0_height_Return(x1) -> f1755_0_height_Return f1754_0_height_Return(x1) -> f1754_0_height_Return f1510_0_height_Return(x1) -> f1510_0_height_Return Filtered duplicate args: f1472_0_height_FieldAccess(x1, x2) -> f1472_0_height_FieldAccess(x2) Combined rules. Obtained 2 conditional rules for P and 0 conditional rules for R.P rules: F1472_0_HEIGHT_FIELDACCESS(java.lang.Object(BTreeR(NULL, java.lang.Object(o536sub:0:0)))) -> F1472_0_HEIGHT_FIELDACCESS(java.lang.Object(o536sub:0:0)) :|: TRUE F1472_0_HEIGHT_FIELDACCESS(java.lang.Object(BTreeR(java.lang.Object(o517sub:0:0), o498:0:0))) -> F1472_0_HEIGHT_FIELDACCESS(java.lang.Object(o517sub:0:0)) :|: TRUE R rules: ---------------------------------------- (9) Obligation: Q DP problem: The TRS P consists of the following rules: F1472_0_HEIGHT_FIELDACCESS(java.lang.Object(BTreeR(NULL, java.lang.Object(o536sub:0:0)))) -> F1472_0_HEIGHT_FIELDACCESS(java.lang.Object(o536sub:0:0)) F1472_0_HEIGHT_FIELDACCESS(java.lang.Object(BTreeR(java.lang.Object(o517sub:0:0), o498:0:0))) -> F1472_0_HEIGHT_FIELDACCESS(java.lang.Object(o517sub: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: *F1472_0_HEIGHT_FIELDACCESS(java.lang.Object(BTreeR(NULL, java.lang.Object(o536sub:0:0)))) -> F1472_0_HEIGHT_FIELDACCESS(java.lang.Object(o536sub:0:0)) The graph contains the following edges 1 > 1 *F1472_0_HEIGHT_FIELDACCESS(java.lang.Object(BTreeR(java.lang.Object(o517sub:0:0), o498:0:0))) -> F1472_0_HEIGHT_FIELDACCESS(java.lang.Object(o517sub:0:0)) The graph contains the following edges 1 > 1 ---------------------------------------- (11) YES ---------------------------------------- (12) Obligation: SCC of termination graph based on JBC Program. SCC contains nodes from the following methods: BTreeR.(I)V SCC calls the following helper methods: BTreeR.(I)V 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 34 IRulesP rules: f728_0__init__InvokeMethod(EOS(STATIC_728), i82, i83) -> f732_0__init__Load(EOS(STATIC_732), i82, i83) :|: TRUE f732_0__init__Load(EOS(STATIC_732), i82, i83) -> f737_0__init__ConstantStackPush(EOS(STATIC_737), i82, i83, i83) :|: TRUE f737_0__init__ConstantStackPush(EOS(STATIC_737), i82, i83, i83) -> f742_0__init__LE(EOS(STATIC_742), i82, i83, i83, 1) :|: TRUE f742_0__init__LE(EOS(STATIC_742), i82, i86, i86, matching1) -> f752_0__init__LE(EOS(STATIC_752), i82, i86, i86, 1) :|: TRUE && matching1 = 1 f752_0__init__LE(EOS(STATIC_752), i82, i86, i86, matching1) -> f766_0__init__Load(EOS(STATIC_766), i82, i86) :|: i86 > 1 && matching1 = 1 f766_0__init__Load(EOS(STATIC_766), i82, i86) -> f769_0__init__New(EOS(STATIC_769), i82, i86) :|: TRUE f769_0__init__New(EOS(STATIC_769), i82, i86) -> f771_0__init__Duplicate(EOS(STATIC_771), i82, i86) :|: TRUE f771_0__init__Duplicate(EOS(STATIC_771), i82, i86) -> f786_0__init__Load(EOS(STATIC_786), i82, i86) :|: TRUE f786_0__init__Load(EOS(STATIC_786), i82, i86) -> f797_0__init__ConstantStackPush(EOS(STATIC_797), i82, i86, i86) :|: TRUE f797_0__init__ConstantStackPush(EOS(STATIC_797), i82, i86, i86) -> f801_0__init__IntArithmetic(EOS(STATIC_801), i82, i86, i86, 1) :|: TRUE f801_0__init__IntArithmetic(EOS(STATIC_801), i82, i86, i86, matching1) -> f805_0__init__InvokeMethod(EOS(STATIC_805), i82, i86, i86 - 1) :|: i86 > 0 && matching1 = 1 f805_0__init__InvokeMethod(EOS(STATIC_805), i82, i86, i102) -> f811_0__init__Load(EOS(STATIC_811), i102, i102) :|: i102 >= 1 && i86 > 1 && i102 < i86 f805_0__init__InvokeMethod(EOS(STATIC_805), i82, i86, i102) -> f811_1__init__Load(EOS(STATIC_811), i82, i86, i102) :|: i102 >= 1 && i86 > 1 && i102 < i86 f811_0__init__Load(EOS(STATIC_811), i102, i102) -> f815_0__init__Load(EOS(STATIC_815), i102, i102) :|: TRUE f815_0__init__Load(EOS(STATIC_815), i102, i102) -> f721_0__init__Load(EOS(STATIC_721), i102, i102) :|: TRUE f721_0__init__Load(EOS(STATIC_721), i82, i83) -> f728_0__init__InvokeMethod(EOS(STATIC_728), i82, i83) :|: TRUE f1027_0__init__Return(EOS(STATIC_1027), i82, i86) -> f1228_0__init__Return(EOS(STATIC_1228), i82, i86) :|: TRUE f1228_0__init__Return(EOS(STATIC_1228), i82, i86) -> f1435_0__init__Return(EOS(STATIC_1435), i82, i86) :|: TRUE f1435_0__init__Return(EOS(STATIC_1435), i82, i86) -> f1592_0__init__Return(EOS(STATIC_1592), i82, i86) :|: TRUE f1592_0__init__Return(EOS(STATIC_1592), i82, i86) -> f1599_0__init__FieldAccess(EOS(STATIC_1599), i82, i86) :|: TRUE f1599_0__init__FieldAccess(EOS(STATIC_1599), i82, i86) -> f1606_0__init__Load(EOS(STATIC_1606), i82, i86) :|: TRUE f1606_0__init__Load(EOS(STATIC_1606), i82, i86) -> f1613_0__init__New(EOS(STATIC_1613), i82, i86) :|: TRUE f1613_0__init__New(EOS(STATIC_1613), i82, i86) -> f1620_0__init__Duplicate(EOS(STATIC_1620), i82, i86) :|: TRUE f1620_0__init__Duplicate(EOS(STATIC_1620), i82, i86) -> f1625_0__init__Load(EOS(STATIC_1625), i82, i86) :|: TRUE f1625_0__init__Load(EOS(STATIC_1625), i82, i86) -> f1636_0__init__ConstantStackPush(EOS(STATIC_1636), i82, i86) :|: TRUE f1636_0__init__ConstantStackPush(EOS(STATIC_1636), i82, i86) -> f1646_0__init__IntArithmetic(EOS(STATIC_1646), i82, i86, 1) :|: TRUE f1646_0__init__IntArithmetic(EOS(STATIC_1646), i82, i86, matching1) -> f1651_0__init__InvokeMethod(EOS(STATIC_1651), i82, i86 - 1) :|: i86 > 0 && matching1 = 1 f1651_0__init__InvokeMethod(EOS(STATIC_1651), i82, i538) -> f1666_0__init__Load(EOS(STATIC_1666), i538, i538) :|: i538 >= 1 f1651_0__init__InvokeMethod(EOS(STATIC_1651), i82, i538) -> f1666_1__init__Load(EOS(STATIC_1666), i82, i538) :|: i538 >= 1 f1666_0__init__Load(EOS(STATIC_1666), i538, i538) -> f1676_0__init__Load(EOS(STATIC_1676), i538, i538) :|: TRUE f1676_0__init__Load(EOS(STATIC_1676), i538, i538) -> f721_0__init__Load(EOS(STATIC_721), i538, i538) :|: TRUE f1795_0__init__Return(EOS(STATIC_1795), i82, i86) -> f1592_0__init__Return(EOS(STATIC_1592), i82, i86) :|: TRUE f811_1__init__Load(EOS(STATIC_811), i82, i86, i102) -> f1027_0__init__Return(EOS(STATIC_1027), i82, i86) :|: TRUE f811_1__init__Load(EOS(STATIC_811), i82, i86, i102) -> f1795_0__init__Return(EOS(STATIC_1795), i82, i86) :|: TRUE Combined rules. Obtained 4 IRulesP rules: f728_0__init__InvokeMethod(EOS(STATIC_728), i82:0, i83:0) -> f728_0__init__InvokeMethod(EOS(STATIC_728), i83:0 - 1, i83:0 - 1) :|: i83:0 > 1 && i83:0 - 1 < i83:0 f728_0__init__InvokeMethod(EOS(STATIC_728), i82:0, i83:0) -> f1651_0__init__InvokeMethod(EOS(STATIC_1651), i82:0, i83:0 - 1) :|: i83:0 > 1 && i83:0 - 1 < i83:0 f1651_0__init__InvokeMethod(EOS(STATIC_1651), i82:0, i538:0) -> f728_0__init__InvokeMethod(EOS(STATIC_728), i538:0, i538:0) :|: i538:0 > 0 Removed following non-SCC rules: f1651_0__init__InvokeMethod(EOS(STATIC_1651), i82:0, i538:0) -> f1666_1__init__Load(EOS(STATIC_1666), i82:0, i538:0) :|: i538:0 > 0 Filtered constant ground arguments: f728_0__init__InvokeMethod(x1, x2, x3) -> f728_0__init__InvokeMethod(x2, x3) f1651_0__init__InvokeMethod(x1, x2, x3) -> f1651_0__init__InvokeMethod(x2, x3) Filtered unneeded arguments: f728_0__init__InvokeMethod(x1, x2) -> f728_0__init__InvokeMethod(x2) f1651_0__init__InvokeMethod(x1, x2) -> f1651_0__init__InvokeMethod(x2) Finished conversion. Obtained 3 rules.P rules: f728_0__init__InvokeMethod(i83:0) -> f728_0__init__InvokeMethod(i83:0 - 1) :|: i83:0 > 1 && i83:0 - 1 < i83:0 f728_0__init__InvokeMethod(i83:0) -> f1651_0__init__InvokeMethod(i83:0 - 1) :|: i83:0 > 1 && i83:0 - 1 < i83:0 f1651_0__init__InvokeMethod(i538:0) -> f728_0__init__InvokeMethod(i538:0) :|: i538:0 > 0 ---------------------------------------- (14) Obligation: Rules: f728_0__init__InvokeMethod(i83:0) -> f728_0__init__InvokeMethod(i83:0 - 1) :|: i83:0 > 1 && i83:0 - 1 < i83:0 f728_0__init__InvokeMethod(x) -> f1651_0__init__InvokeMethod(x - 1) :|: x > 1 && x - 1 < x f1651_0__init__InvokeMethod(i538:0) -> f728_0__init__InvokeMethod(i538:0) :|: i538:0 > 0 ---------------------------------------- (15) IRSFormatTransformerProof (EQUIVALENT) Reformatted IRS to match normalized format (transformed away non-linear left-hand sides, !=, / and %). ---------------------------------------- (16) Obligation: Rules: f728_0__init__InvokeMethod(i83:0) -> f728_0__init__InvokeMethod(arith) :|: i83:0 > 1 && i83:0 - 1 < i83:0 && arith = i83:0 - 1 f728_0__init__InvokeMethod(x1) -> f1651_0__init__InvokeMethod(x2) :|: x1 > 1 && x1 - 1 < x1 && x2 = x1 - 1 f1651_0__init__InvokeMethod(i538:0) -> f728_0__init__InvokeMethod(i538:0) :|: i538:0 > 0 ---------------------------------------- (17) IRSwTTerminationDigraphProof (EQUIVALENT) Constructed termination digraph! Nodes: (1) f728_0__init__InvokeMethod(i83:0) -> f728_0__init__InvokeMethod(arith) :|: i83:0 > 1 && i83:0 - 1 < i83:0 && arith = i83:0 - 1 (2) f728_0__init__InvokeMethod(x1) -> f1651_0__init__InvokeMethod(x2) :|: x1 > 1 && x1 - 1 < x1 && x2 = x1 - 1 (3) f1651_0__init__InvokeMethod(i538:0) -> f728_0__init__InvokeMethod(i538:0) :|: i538:0 > 0 Arcs: (1) -> (1), (2) (2) -> (3) (3) -> (1), (2) This digraph is fully evaluated! ---------------------------------------- (18) Obligation: Termination digraph: Nodes: (1) f728_0__init__InvokeMethod(i83:0) -> f728_0__init__InvokeMethod(arith) :|: i83:0 > 1 && i83:0 - 1 < i83:0 && arith = i83:0 - 1 (2) f1651_0__init__InvokeMethod(i538:0) -> f728_0__init__InvokeMethod(i538:0) :|: i538:0 > 0 (3) f728_0__init__InvokeMethod(x1) -> f1651_0__init__InvokeMethod(x2) :|: x1 > 1 && x1 - 1 < x1 && x2 = x1 - 1 Arcs: (1) -> (1), (3) (2) -> (1), (3) (3) -> (2) This digraph is fully evaluated! ---------------------------------------- (19) IntTRSCompressionProof (EQUIVALENT) Compressed rules. ---------------------------------------- (20) Obligation: Rules: f728_0__init__InvokeMethod(x1:0) -> f728_0__init__InvokeMethod(x1:0 - 1) :|: x1:0 - 1 < x1:0 && x1:0 > 1 f728_0__init__InvokeMethod(i83:0:0) -> f728_0__init__InvokeMethod(i83:0:0 - 1) :|: i83:0:0 > 1 && i83:0:0 - 1 < i83:0:0 ---------------------------------------- (21) TempFilterProof (SOUND) Used the following sort dictionary for filtering: f728_0__init__InvokeMethod(INTEGER) Replaced non-predefined constructor symbols by 0. ---------------------------------------- (22) Obligation: Rules: f728_0__init__InvokeMethod(x1:0) -> f728_0__init__InvokeMethod(c) :|: c = x1:0 - 1 && (x1:0 - 1 < x1:0 && x1:0 > 1) f728_0__init__InvokeMethod(i83:0:0) -> f728_0__init__InvokeMethod(c1) :|: c1 = i83:0:0 - 1 && (i83:0:0 > 1 && i83:0:0 - 1 < i83:0:0) ---------------------------------------- (23) RankingReductionPairProof (EQUIVALENT) Interpretation: [ f728_0__init__InvokeMethod ] = f728_0__init__InvokeMethod_1 The following rules are decreasing: f728_0__init__InvokeMethod(x1:0) -> f728_0__init__InvokeMethod(c) :|: c = x1:0 - 1 && (x1:0 - 1 < x1:0 && x1:0 > 1) f728_0__init__InvokeMethod(i83:0:0) -> f728_0__init__InvokeMethod(c1) :|: c1 = i83:0:0 - 1 && (i83:0:0 > 1 && i83:0:0 - 1 < i83:0:0) The following rules are bounded: f728_0__init__InvokeMethod(x1:0) -> f728_0__init__InvokeMethod(c) :|: c = x1:0 - 1 && (x1:0 - 1 < x1:0 && x1:0 > 1) f728_0__init__InvokeMethod(i83:0:0) -> f728_0__init__InvokeMethod(c1) :|: c1 = i83:0:0 - 1 && (i83:0:0 > 1 && i83:0:0 - 1 < i83:0:0) ---------------------------------------- (24) YES