/export/starexec/sandbox2/solver/bin/starexec_run_standard /export/starexec/sandbox2/benchmark/theBenchmark.pl /export/starexec/sandbox2/output/output_files -------------------------------------------------------------------------------- YES proof of /export/starexec/sandbox2/benchmark/theBenchmark.pl # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty Left Termination of the query pattern bin_tree(g) w.r.t. the given Prolog program could successfully be proven: (0) Prolog (1) PrologToDTProblemTransformerProof [SOUND, 0 ms] (2) TRIPLES (3) TriplesToPiDPProof [SOUND, 1 ms] (4) PiDP (5) DependencyGraphProof [EQUIVALENT, 0 ms] (6) PiDP (7) PiDPToQDPProof [EQUIVALENT, 0 ms] (8) QDP (9) QDPSizeChangeProof [EQUIVALENT, 0 ms] (10) YES ---------------------------------------- (0) Obligation: Clauses: bin_tree(void). bin_tree(T) :- ','(no(empty(T)), ','(left(T, L), ','(right(T, R), ','(bin_tree(L), bin_tree(R))))). left(void, void). left(tree(X1, L, X2), L). right(void, void). right(tree(X3, X4, R), R). empty(void). no(X) :- ','(X, ','(!, failure(a))). no(X5). failure(b). Query: bin_tree(g) ---------------------------------------- (1) PrologToDTProblemTransformerProof (SOUND) Built DT problem from termination graph DT10. { "root": 2, "program": { "directives": [], "clauses": [ [ "(bin_tree (void))", null ], [ "(bin_tree T)", "(',' (no (empty T)) (',' (left T L) (',' (right T R) (',' (bin_tree L) (bin_tree R)))))" ], [ "(left (void) (void))", null ], [ "(left (tree X1 L X2) L)", null ], [ "(right (void) (void))", null ], [ "(right (tree X3 X4 R) R)", null ], [ "(empty (void))", null ], [ "(no X)", "(',' X (',' (!) (failure (a))))" ], [ "(no X5)", null ], [ "(failure (b))", null ] ] }, "graph": { "nodes": { "23": { "goal": [{ "clause": 9, "scope": 5, "term": "(',' (failure (a)) (',' (left (void) X8) (',' (right (void) X9) (',' (bin_tree X8) (bin_tree X9)))))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [ "X8", "X9" ], "exprvars": [] } }, "45": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (left T9 X15) (',' (right T9 X16) (',' (bin_tree X15) (bin_tree X16))))" }], "kb": { "nonunifying": [[ "(bin_tree T9)", "(bin_tree (void))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T9"], "free": [ "X15", "X16" ], "exprvars": [] } }, "25": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "47": { "goal": [ { "clause": 2, "scope": 9, "term": "(',' (left T9 X15) (',' (right T9 X16) (',' (bin_tree X15) (bin_tree X16))))" }, { "clause": 3, "scope": 9, "term": "(',' (left T9 X15) (',' (right T9 X16) (',' (bin_tree X15) (bin_tree X16))))" } ], "kb": { "nonunifying": [[ "(bin_tree T9)", "(bin_tree (void))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T9"], "free": [ "X15", "X16" ], "exprvars": [] } }, "27": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (no (empty T3)) (',' (left T3 X15) (',' (right T3 X16) (',' (bin_tree X15) (bin_tree X16)))))" }], "kb": { "nonunifying": [[ "(bin_tree T3)", "(bin_tree (void))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T3"], "free": [ "X15", "X16" ], "exprvars": [] } }, "49": { "goal": [{ "clause": 3, "scope": 9, "term": "(',' (left T9 X15) (',' (right T9 X16) (',' (bin_tree X15) (bin_tree X16))))" }], "kb": { "nonunifying": [[ "(bin_tree T9)", "(bin_tree (void))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T9"], "free": [ "X15", "X16" ], "exprvars": [] } }, "29": { "goal": [ { "clause": 7, "scope": 6, "term": "(',' (no (empty T3)) (',' (left T3 X15) (',' (right T3 X16) (',' (bin_tree X15) (bin_tree X16)))))" }, { "clause": 8, "scope": 6, "term": "(',' (no (empty T3)) (',' (left T3 X15) (',' (right T3 X16) (',' (bin_tree X15) (bin_tree X16)))))" } ], "kb": { "nonunifying": [[ "(bin_tree T3)", "(bin_tree (void))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T3"], "free": [ "X15", "X16" ], "exprvars": [] } }, "type": "Nodes", "51": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (right (tree T16 T17 T18) X16) (',' (bin_tree T17) (bin_tree X16)))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T16", "T17", "T18" ], "free": ["X16"], "exprvars": [] } }, "53": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "75": { "goal": [{ "clause": -1, "scope": -1, "term": "(bin_tree T26)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T26"], "free": [], "exprvars": [] } }, "10": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (no (empty (void))) (',' (left (void) X8) (',' (right (void) X9) (',' (bin_tree X8) (bin_tree X9)))))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [ "X8", "X9" ], "exprvars": [] } }, "11": { "goal": [ { "clause": 7, "scope": 2, "term": "(',' (no (empty (void))) (',' (left (void) X8) (',' (right (void) X9) (',' (bin_tree X8) (bin_tree X9)))))" }, { "clause": 8, "scope": 2, "term": "(',' (no (empty (void))) (',' (left (void) X8) (',' (right (void) X9) (',' (bin_tree X8) (bin_tree X9)))))" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [ "X8", "X9" ], "exprvars": [] } }, "55": { "goal": [ { "clause": 4, "scope": 10, "term": "(',' (right (tree T16 T17 T18) X16) (',' (bin_tree T17) (bin_tree X16)))" }, { "clause": 5, "scope": 10, "term": "(',' (right (tree T16 T17 T18) X16) (',' (bin_tree T17) (bin_tree X16)))" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T16", "T17", "T18" ], "free": ["X16"], "exprvars": [] } }, "34": { "goal": [ { "clause": -1, "scope": -1, "term": "(',' (',' (call (empty T6)) (',' (!_6) (failure (a)))) (',' (left T6 X15) (',' (right T6 X16) (',' (bin_tree X15) (bin_tree X16)))))" }, { "clause": 8, "scope": 6, "term": "(',' (no (empty T6)) (',' (left T6 X15) (',' (right T6 X16) (',' (bin_tree X15) (bin_tree X16)))))" } ], "kb": { "nonunifying": [[ "(bin_tree T6)", "(bin_tree (void))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T6"], "free": [ "X15", "X16" ], "exprvars": [] } }, "78": { "goal": [{ "clause": -1, "scope": -1, "term": "(bin_tree T27)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T27"], "free": [], "exprvars": [] } }, "35": { "goal": [ { "clause": -1, "scope": -1, "term": "(',' (empty T6) (',' (',' (!_6) (failure (a))) (',' (left T6 X15) (',' (right T6 X16) (',' (bin_tree X15) (bin_tree X16))))))" }, { "clause": -1, "scope": 7, "term": null }, { "clause": 8, "scope": 6, "term": "(',' (no (empty T6)) (',' (left T6 X15) (',' (right T6 X16) (',' (bin_tree X15) (bin_tree X16)))))" } ], "kb": { "nonunifying": [[ "(bin_tree T6)", "(bin_tree (void))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T6"], "free": [ "X15", "X16" ], "exprvars": [] } }, "57": { "goal": [{ "clause": 5, "scope": 10, "term": "(',' (right (tree T16 T17 T18) X16) (',' (bin_tree T17) (bin_tree X16)))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T16", "T17", "T18" ], "free": ["X16"], "exprvars": [] } }, "14": { "goal": [ { "clause": -1, "scope": -1, "term": "(',' (',' (call (empty (void))) (',' (!_2) (failure (a)))) (',' (left (void) X8) (',' (right (void) X9) (',' (bin_tree X8) (bin_tree X9)))))" }, { "clause": 8, "scope": 2, "term": "(',' (no (empty (void))) (',' (left (void) X8) (',' (right (void) X9) (',' (bin_tree X8) (bin_tree X9)))))" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [ "X8", "X9" ], "exprvars": [] } }, "15": { "goal": [ { "clause": -1, "scope": -1, "term": "(',' (empty (void)) (',' (',' (!_2) (failure (a))) (',' (left (void) X8) (',' (right (void) X9) (',' (bin_tree X8) (bin_tree X9))))))" }, { "clause": -1, "scope": 3, "term": null }, { "clause": 8, "scope": 2, "term": "(',' (no (empty (void))) (',' (left (void) X8) (',' (right (void) X9) (',' (bin_tree X8) (bin_tree X9)))))" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [ "X8", "X9" ], "exprvars": [] } }, "59": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (bin_tree T26) (bin_tree T27))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T26", "T27" ], "free": [], "exprvars": [] } }, "39": { "goal": [ { "clause": 6, "scope": 8, "term": "(',' (empty T6) (',' (',' (!_6) (failure (a))) (',' (left T6 X15) (',' (right T6 X16) (',' (bin_tree X15) (bin_tree X16))))))" }, { "clause": -1, "scope": 8, "term": null }, { "clause": -1, "scope": 7, "term": null }, { "clause": 8, "scope": 6, "term": "(',' (no (empty T6)) (',' (left T6 X15) (',' (right T6 X16) (',' (bin_tree X15) (bin_tree X16)))))" } ], "kb": { "nonunifying": [[ "(bin_tree T6)", "(bin_tree (void))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T6"], "free": [ "X15", "X16" ], "exprvars": [] } }, "19": { "goal": [ { "clause": 6, "scope": 4, "term": "(',' (empty (void)) (',' (',' (!_2) (failure (a))) (',' (left (void) X8) (',' (right (void) X9) (',' (bin_tree X8) (bin_tree X9))))))" }, { "clause": -1, "scope": 4, "term": null }, { "clause": -1, "scope": 3, "term": null }, { "clause": 8, "scope": 2, "term": "(',' (no (empty (void))) (',' (left (void) X8) (',' (right (void) X9) (',' (bin_tree X8) (bin_tree X9)))))" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [ "X8", "X9" ], "exprvars": [] } }, "2": { "goal": [{ "clause": -1, "scope": -1, "term": "(bin_tree T1)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T1"], "free": [], "exprvars": [] } }, "4": { "goal": [ { "clause": 0, "scope": 1, "term": "(bin_tree T1)" }, { "clause": 1, "scope": 1, "term": "(bin_tree T1)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T1"], "free": [], "exprvars": [] } }, "7": { "goal": [ { "clause": -1, "scope": -1, "term": "(true)" }, { "clause": 1, "scope": 1, "term": "(bin_tree (void))" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "8": { "goal": [{ "clause": 1, "scope": 1, "term": "(bin_tree T1)" }], "kb": { "nonunifying": [[ "(bin_tree T1)", "(bin_tree (void))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T1"], "free": [], "exprvars": [] } }, "9": { "goal": [{ "clause": 1, "scope": 1, "term": "(bin_tree (void))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "40": { "goal": [ { "clause": -1, "scope": 8, "term": null }, { "clause": -1, "scope": 7, "term": null }, { "clause": 8, "scope": 6, "term": "(',' (no (empty T6)) (',' (left T6 X15) (',' (right T6 X16) (',' (bin_tree X15) (bin_tree X16)))))" } ], "kb": { "nonunifying": [[ "(bin_tree T6)", "(bin_tree (void))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T6"], "free": [ "X15", "X16" ], "exprvars": [] } }, "41": { "goal": [ { "clause": -1, "scope": 7, "term": null }, { "clause": 8, "scope": 6, "term": "(',' (no (empty T6)) (',' (left T6 X15) (',' (right T6 X16) (',' (bin_tree X15) (bin_tree X16)))))" } ], "kb": { "nonunifying": [[ "(bin_tree T6)", "(bin_tree (void))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T6"], "free": [ "X15", "X16" ], "exprvars": [] } }, "20": { "goal": [ { "clause": -1, "scope": -1, "term": "(',' (',' (!_2) (failure (a))) (',' (left (void) X8) (',' (right (void) X9) (',' (bin_tree X8) (bin_tree X9)))))" }, { "clause": -1, "scope": 4, "term": null }, { "clause": -1, "scope": 3, "term": null }, { "clause": 8, "scope": 2, "term": "(',' (no (empty (void))) (',' (left (void) X8) (',' (right (void) X9) (',' (bin_tree X8) (bin_tree X9)))))" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [ "X8", "X9" ], "exprvars": [] } }, "21": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (failure (a)) (',' (left (void) X8) (',' (right (void) X9) (',' (bin_tree X8) (bin_tree X9)))))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [ "X8", "X9" ], "exprvars": [] } }, "43": { "goal": [{ "clause": 8, "scope": 6, "term": "(',' (no (empty T6)) (',' (left T6 X15) (',' (right T6 X16) (',' (bin_tree X15) (bin_tree X16)))))" }], "kb": { "nonunifying": [[ "(bin_tree T6)", "(bin_tree (void))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T6"], "free": [ "X15", "X16" ], "exprvars": [] } } }, "edges": [ { "from": 2, "to": 4, "label": "CASE" }, { "from": 4, "to": 7, "label": "EVAL with clause\nbin_tree(void).\nand substitutionT1 -> void" }, { "from": 4, "to": 8, "label": "EVAL-BACKTRACK" }, { "from": 7, "to": 9, "label": "SUCCESS" }, { "from": 8, "to": 27, "label": "ONLY EVAL with clause\nbin_tree(X14) :- ','(no(empty(X14)), ','(left(X14, X15), ','(right(X14, X16), ','(bin_tree(X15), bin_tree(X16))))).\nand substitutionT1 -> T3,\nX14 -> T3" }, { "from": 9, "to": 10, "label": "ONLY EVAL with clause\nbin_tree(X7) :- ','(no(empty(X7)), ','(left(X7, X8), ','(right(X7, X9), ','(bin_tree(X8), bin_tree(X9))))).\nand substitutionX7 -> void" }, { "from": 10, "to": 11, "label": "CASE" }, { "from": 11, "to": 14, "label": "ONLY EVAL with clause\nno(X12) :- ','(call(X12), ','(!_2, failure(a))).\nand substitutionX12 -> empty(void)" }, { "from": 14, "to": 15, "label": "CALL" }, { "from": 15, "to": 19, "label": "CASE" }, { "from": 19, "to": 20, "label": "ONLY EVAL with clause\nempty(void).\nand substitution" }, { "from": 20, "to": 21, "label": "CUT" }, { "from": 21, "to": 23, "label": "CASE" }, { "from": 23, "to": 25, "label": "BACKTRACK\nfor clause: failure(b)because of non-unification" }, { "from": 27, "to": 29, "label": "CASE" }, { "from": 29, "to": 34, "label": "ONLY EVAL with clause\nno(X19) :- ','(call(X19), ','(!_6, failure(a))).\nand substitutionT3 -> T6,\nX19 -> empty(T6)" }, { "from": 34, "to": 35, "label": "CALL" }, { "from": 35, "to": 39, "label": "CASE" }, { "from": 39, "to": 40, "label": "BACKTRACK\nfor clause: empty(void)\nwith clash: (bin_tree(T6), bin_tree(void))" }, { "from": 40, "to": 41, "label": "FAILURE" }, { "from": 41, "to": 43, "label": "FAILURE" }, { "from": 43, "to": 45, "label": "ONLY EVAL with clause\nno(X22).\nand substitutionT6 -> T9,\nX22 -> empty(T9)" }, { "from": 45, "to": 47, "label": "CASE" }, { "from": 47, "to": 49, "label": "BACKTRACK\nfor clause: left(void, void)\nwith clash: (bin_tree(T9), bin_tree(void))" }, { "from": 49, "to": 51, "label": "EVAL with clause\nleft(tree(X29, X30, X31), X30).\nand substitutionX29 -> T16,\nX30 -> T17,\nX31 -> T18,\nT9 -> tree(T16, T17, T18),\nX15 -> T17" }, { "from": 49, "to": 53, "label": "EVAL-BACKTRACK" }, { "from": 51, "to": 55, "label": "CASE" }, { "from": 55, "to": 57, "label": "BACKTRACK\nfor clause: right(void, void)because of non-unification" }, { "from": 57, "to": 59, "label": "ONLY EVAL with clause\nright(tree(X38, X39, X40), X40).\nand substitutionT16 -> T25,\nX38 -> T25,\nT17 -> T26,\nX39 -> T26,\nT18 -> T27,\nX40 -> T27,\nX16 -> T27" }, { "from": 59, "to": 75, "label": "SPLIT 1" }, { "from": 59, "to": 78, "label": "SPLIT 2\nnew knowledge:\nT26 is ground" }, { "from": 75, "to": 2, "label": "INSTANCE with matching:\nT1 -> T26" }, { "from": 78, "to": 2, "label": "INSTANCE with matching:\nT1 -> T27" } ], "type": "Graph" } } ---------------------------------------- (2) Obligation: Triples: bin_treeA(tree(X1, X2, X3)) :- bin_treeA(X2). bin_treeA(tree(X1, X2, X3)) :- ','(bin_treecA(X2), bin_treeA(X3)). Clauses: bin_treecA(void). bin_treecA(tree(X1, X2, X3)) :- ','(bin_treecA(X2), bin_treecA(X3)). Afs: bin_treeA(x1) = bin_treeA(x1) ---------------------------------------- (3) TriplesToPiDPProof (SOUND) We use the technique of [DT09]. With regard to the inferred argument filtering the predicates were used in the following modes: bin_treeA_in_1: (b) bin_treecA_in_1: (b) Transforming TRIPLES into the following Term Rewriting System: Pi DP problem: The TRS P consists of the following rules: BIN_TREEA_IN_G(tree(X1, X2, X3)) -> U1_G(X1, X2, X3, bin_treeA_in_g(X2)) BIN_TREEA_IN_G(tree(X1, X2, X3)) -> BIN_TREEA_IN_G(X2) BIN_TREEA_IN_G(tree(X1, X2, X3)) -> U2_G(X1, X2, X3, bin_treecA_in_g(X2)) U2_G(X1, X2, X3, bin_treecA_out_g(X2)) -> U3_G(X1, X2, X3, bin_treeA_in_g(X3)) U2_G(X1, X2, X3, bin_treecA_out_g(X2)) -> BIN_TREEA_IN_G(X3) The TRS R consists of the following rules: bin_treecA_in_g(void) -> bin_treecA_out_g(void) bin_treecA_in_g(tree(X1, X2, X3)) -> U5_g(X1, X2, X3, bin_treecA_in_g(X2)) U5_g(X1, X2, X3, bin_treecA_out_g(X2)) -> U6_g(X1, X2, X3, bin_treecA_in_g(X3)) U6_g(X1, X2, X3, bin_treecA_out_g(X3)) -> bin_treecA_out_g(tree(X1, X2, X3)) Pi is empty. We have to consider all (P,R,Pi)-chains Infinitary Constructor Rewriting Termination of PiDP implies Termination of TRIPLES ---------------------------------------- (4) Obligation: Pi DP problem: The TRS P consists of the following rules: BIN_TREEA_IN_G(tree(X1, X2, X3)) -> U1_G(X1, X2, X3, bin_treeA_in_g(X2)) BIN_TREEA_IN_G(tree(X1, X2, X3)) -> BIN_TREEA_IN_G(X2) BIN_TREEA_IN_G(tree(X1, X2, X3)) -> U2_G(X1, X2, X3, bin_treecA_in_g(X2)) U2_G(X1, X2, X3, bin_treecA_out_g(X2)) -> U3_G(X1, X2, X3, bin_treeA_in_g(X3)) U2_G(X1, X2, X3, bin_treecA_out_g(X2)) -> BIN_TREEA_IN_G(X3) The TRS R consists of the following rules: bin_treecA_in_g(void) -> bin_treecA_out_g(void) bin_treecA_in_g(tree(X1, X2, X3)) -> U5_g(X1, X2, X3, bin_treecA_in_g(X2)) U5_g(X1, X2, X3, bin_treecA_out_g(X2)) -> U6_g(X1, X2, X3, bin_treecA_in_g(X3)) U6_g(X1, X2, X3, bin_treecA_out_g(X3)) -> bin_treecA_out_g(tree(X1, X2, X3)) Pi is empty. We have to consider all (P,R,Pi)-chains ---------------------------------------- (5) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LOPSTR] contains 1 SCC with 2 less nodes. ---------------------------------------- (6) Obligation: Pi DP problem: The TRS P consists of the following rules: BIN_TREEA_IN_G(tree(X1, X2, X3)) -> U2_G(X1, X2, X3, bin_treecA_in_g(X2)) U2_G(X1, X2, X3, bin_treecA_out_g(X2)) -> BIN_TREEA_IN_G(X3) BIN_TREEA_IN_G(tree(X1, X2, X3)) -> BIN_TREEA_IN_G(X2) The TRS R consists of the following rules: bin_treecA_in_g(void) -> bin_treecA_out_g(void) bin_treecA_in_g(tree(X1, X2, X3)) -> U5_g(X1, X2, X3, bin_treecA_in_g(X2)) U5_g(X1, X2, X3, bin_treecA_out_g(X2)) -> U6_g(X1, X2, X3, bin_treecA_in_g(X3)) U6_g(X1, X2, X3, bin_treecA_out_g(X3)) -> bin_treecA_out_g(tree(X1, X2, X3)) Pi is empty. We have to consider all (P,R,Pi)-chains ---------------------------------------- (7) PiDPToQDPProof (EQUIVALENT) Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. ---------------------------------------- (8) Obligation: Q DP problem: The TRS P consists of the following rules: BIN_TREEA_IN_G(tree(X1, X2, X3)) -> U2_G(X1, X2, X3, bin_treecA_in_g(X2)) U2_G(X1, X2, X3, bin_treecA_out_g(X2)) -> BIN_TREEA_IN_G(X3) BIN_TREEA_IN_G(tree(X1, X2, X3)) -> BIN_TREEA_IN_G(X2) The TRS R consists of the following rules: bin_treecA_in_g(void) -> bin_treecA_out_g(void) bin_treecA_in_g(tree(X1, X2, X3)) -> U5_g(X1, X2, X3, bin_treecA_in_g(X2)) U5_g(X1, X2, X3, bin_treecA_out_g(X2)) -> U6_g(X1, X2, X3, bin_treecA_in_g(X3)) U6_g(X1, X2, X3, bin_treecA_out_g(X3)) -> bin_treecA_out_g(tree(X1, X2, X3)) The set Q consists of the following terms: bin_treecA_in_g(x0) U5_g(x0, x1, x2, x3) U6_g(x0, x1, x2, x3) We have to consider all (P,Q,R)-chains. ---------------------------------------- (9) 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: *U2_G(X1, X2, X3, bin_treecA_out_g(X2)) -> BIN_TREEA_IN_G(X3) The graph contains the following edges 3 >= 1 *BIN_TREEA_IN_G(tree(X1, X2, X3)) -> BIN_TREEA_IN_G(X2) The graph contains the following edges 1 > 1 *BIN_TREEA_IN_G(tree(X1, X2, X3)) -> U2_G(X1, X2, X3, bin_treecA_in_g(X2)) The graph contains the following edges 1 > 1, 1 > 2, 1 > 3 ---------------------------------------- (10) YES