/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: 794c25de1cacf0d048858bcd21c9a779e1221865 marcel 20200619 unpublished dirty Left Termination of the query pattern hbal_tree(g,a) w.r.t. the given Prolog program could successfully be proven: (0) Prolog (1) PrologToDTProblemTransformerProof [SOUND, 49 ms] (2) TRIPLES (3) TriplesToPiDPProof [SOUND, 0 ms] (4) PiDP (5) DependencyGraphProof [EQUIVALENT, 0 ms] (6) PiDP (7) PiDPToQDPProof [SOUND, 0 ms] (8) QDP (9) MRRProof [EQUIVALENT, 61 ms] (10) QDP (11) PisEmptyProof [EQUIVALENT, 0 ms] (12) YES ---------------------------------------- (0) Obligation: Clauses: hbal_tree(zero, nil). hbal_tree(s(zero), t(x, nil, nil)). hbal_tree(s(s(X)), t(x, L, R)) :- ','(distr(s(X), X, DL, DR), ','(hbal_tree(DL, L), hbal_tree(DR, R))). distr(D1, X1, D1, D1). distr(D1, D2, D1, D2). distr(D1, D2, D2, D1). Query: hbal_tree(g,a) ---------------------------------------- (1) PrologToDTProblemTransformerProof (SOUND) Built DT problem from termination graph DT10. { "root": 1, "program": { "directives": [], "clauses": [ [ "(hbal_tree (zero) (nil))", null ], [ "(hbal_tree (s (zero)) (t (x) (nil) (nil)))", null ], [ "(hbal_tree (s (s X)) (t (x) L R))", "(',' (distr (s X) X DL DR) (',' (hbal_tree DL L) (hbal_tree DR R)))" ], [ "(distr D1 X1 D1 D1)", null ], [ "(distr D1 D2 D1 D2)", null ], [ "(distr D1 D2 D2 D1)", null ] ] }, "graph": { "nodes": { "66": { "goal": [ { "clause": 3, "scope": 2, "term": "(',' (distr (s T6) T6 X14 X15) (',' (hbal_tree X14 T9) (hbal_tree X15 T10)))" }, { "clause": 4, "scope": 2, "term": "(',' (distr (s T6) T6 X14 X15) (',' (hbal_tree X14 T9) (hbal_tree X15 T10)))" }, { "clause": 5, "scope": 2, "term": "(',' (distr (s T6) T6 X14 X15) (',' (hbal_tree X14 T9) (hbal_tree X15 T10)))" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T6"], "free": [ "X14", "X15" ], "exprvars": [] } }, "67": { "goal": [{ "clause": 3, "scope": 2, "term": "(',' (distr (s T6) T6 X14 X15) (',' (hbal_tree X14 T9) (hbal_tree X15 T10)))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T6"], "free": [ "X14", "X15" ], "exprvars": [] } }, "68": { "goal": [ { "clause": 4, "scope": 2, "term": "(',' (distr (s T6) T6 X14 X15) (',' (hbal_tree X14 T9) (hbal_tree X15 T10)))" }, { "clause": 5, "scope": 2, "term": "(',' (distr (s T6) T6 X14 X15) (',' (hbal_tree X14 T9) (hbal_tree X15 T10)))" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T6"], "free": [ "X14", "X15" ], "exprvars": [] } }, "25": { "goal": [{ "clause": 2, "scope": 1, "term": "(hbal_tree T1 T2)" }], "kb": { "nonunifying": [ [ "(hbal_tree T1 T2)", "(hbal_tree (zero) (nil))" ], [ "(hbal_tree T1 T2)", "(hbal_tree (s (zero)) (t (x) (nil) (nil)))" ] ], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T1"], "free": [], "exprvars": [] } }, "69": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (hbal_tree (s T15) T9) (hbal_tree (s T15) T10))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T15"], "free": [], "exprvars": [] } }, "26": { "goal": [{ "clause": 2, "scope": 1, "term": "(hbal_tree (s (zero)) T2)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "27": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "type": "Nodes", "11": { "goal": [ { "clause": -1, "scope": -1, "term": "(true)" }, { "clause": 1, "scope": 1, "term": "(hbal_tree (zero) T2)" }, { "clause": 2, "scope": 1, "term": "(hbal_tree (zero) T2)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "12": { "goal": [ { "clause": 1, "scope": 1, "term": "(hbal_tree T1 T2)" }, { "clause": 2, "scope": 1, "term": "(hbal_tree T1 T2)" } ], "kb": { "nonunifying": [[ "(hbal_tree T1 T2)", "(hbal_tree (zero) (nil))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T1"], "free": [], "exprvars": [] } }, "14": { "goal": [ { "clause": 1, "scope": 1, "term": "(hbal_tree (zero) T2)" }, { "clause": 2, "scope": 1, "term": "(hbal_tree (zero) T2)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "17": { "goal": [{ "clause": 2, "scope": 1, "term": "(hbal_tree (zero) T2)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "19": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "260": { "goal": [{ "clause": -1, "scope": -1, "term": "(hbal_tree (s T21) T9)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T21"], "free": [], "exprvars": [] } }, "261": { "goal": [{ "clause": -1, "scope": -1, "term": "(hbal_tree T21 T22)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T21"], "free": [], "exprvars": [] } }, "262": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (hbal_tree T25 T9) (hbal_tree (s T25) T10))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T25"], "free": [], "exprvars": [] } }, "241": { "goal": [{ "clause": 4, "scope": 2, "term": "(',' (distr (s T6) T6 X14 X15) (',' (hbal_tree X14 T9) (hbal_tree X15 T10)))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T6"], "free": [ "X14", "X15" ], "exprvars": [] } }, "263": { "goal": [{ "clause": -1, "scope": -1, "term": "(hbal_tree T25 T9)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T25"], "free": [], "exprvars": [] } }, "242": { "goal": [{ "clause": 5, "scope": 2, "term": "(',' (distr (s T6) T6 X14 X15) (',' (hbal_tree X14 T9) (hbal_tree X15 T10)))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T6"], "free": [ "X14", "X15" ], "exprvars": [] } }, "264": { "goal": [{ "clause": -1, "scope": -1, "term": "(hbal_tree (s T25) T26)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T25"], "free": [], "exprvars": [] } }, "1": { "goal": [{ "clause": -1, "scope": -1, "term": "(hbal_tree T1 T2)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T1"], "free": [], "exprvars": [] } }, "243": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (hbal_tree (s T21) T9) (hbal_tree T21 T10))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T21"], "free": [], "exprvars": [] } }, "6": { "goal": [ { "clause": 0, "scope": 1, "term": "(hbal_tree T1 T2)" }, { "clause": 1, "scope": 1, "term": "(hbal_tree T1 T2)" }, { "clause": 2, "scope": 1, "term": "(hbal_tree T1 T2)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T1"], "free": [], "exprvars": [] } }, "208": { "goal": [{ "clause": -1, "scope": -1, "term": "(hbal_tree (s T15) T9)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T15"], "free": [], "exprvars": [] } }, "209": { "goal": [{ "clause": -1, "scope": -1, "term": "(hbal_tree (s T15) T16)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T15"], "free": [], "exprvars": [] } }, "64": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (distr (s T6) T6 X14 X15) (',' (hbal_tree X14 T9) (hbal_tree X15 T10)))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T6"], "free": [ "X14", "X15" ], "exprvars": [] } }, "21": { "goal": [ { "clause": -1, "scope": -1, "term": "(true)" }, { "clause": 2, "scope": 1, "term": "(hbal_tree (s (zero)) T2)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "65": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } } }, "edges": [ { "from": 1, "to": 6, "label": "CASE" }, { "from": 6, "to": 11, "label": "EVAL with clause\nhbal_tree(zero, nil).\nand substitutionT1 -> zero,\nT2 -> nil" }, { "from": 6, "to": 12, "label": "EVAL-BACKTRACK" }, { "from": 11, "to": 14, "label": "SUCCESS" }, { "from": 12, "to": 21, "label": "EVAL with clause\nhbal_tree(s(zero), t(x, nil, nil)).\nand substitutionT1 -> s(zero),\nT2 -> t(x, nil, nil)" }, { "from": 12, "to": 25, "label": "EVAL-BACKTRACK" }, { "from": 14, "to": 17, "label": "BACKTRACK\nfor clause: hbal_tree(s(zero), t(x, nil, nil))because of non-unification" }, { "from": 17, "to": 19, "label": "BACKTRACK\nfor clause: hbal_tree(s(s(X)), t(x, L, R)) :- ','(distr(s(X), X, DL, DR), ','(hbal_tree(DL, L), hbal_tree(DR, R)))because of non-unification" }, { "from": 21, "to": 26, "label": "SUCCESS" }, { "from": 25, "to": 64, "label": "EVAL with clause\nhbal_tree(s(s(X11)), t(x, X12, X13)) :- ','(distr(s(X11), X11, X14, X15), ','(hbal_tree(X14, X12), hbal_tree(X15, X13))).\nand substitutionX11 -> T6,\nT1 -> s(s(T6)),\nX12 -> T9,\nX13 -> T10,\nT2 -> t(x, T9, T10),\nT7 -> T9,\nT8 -> T10" }, { "from": 25, "to": 65, "label": "EVAL-BACKTRACK" }, { "from": 26, "to": 27, "label": "BACKTRACK\nfor clause: hbal_tree(s(s(X)), t(x, L, R)) :- ','(distr(s(X), X, DL, DR), ','(hbal_tree(DL, L), hbal_tree(DR, R)))because of non-unification" }, { "from": 64, "to": 66, "label": "CASE" }, { "from": 66, "to": 67, "label": "PARALLEL" }, { "from": 66, "to": 68, "label": "PARALLEL" }, { "from": 67, "to": 69, "label": "ONLY EVAL with clause\ndistr(X24, X25, X24, X24).\nand substitutionT6 -> T15,\nX24 -> s(T15),\nX25 -> T15,\nX14 -> s(T15),\nX15 -> s(T15)" }, { "from": 68, "to": 241, "label": "PARALLEL" }, { "from": 68, "to": 242, "label": "PARALLEL" }, { "from": 69, "to": 208, "label": "SPLIT 1" }, { "from": 69, "to": 209, "label": "SPLIT 2\nnew knowledge:\nT15 is ground\nT9 is ground\nreplacements:T10 -> T16" }, { "from": 208, "to": 1, "label": "INSTANCE with matching:\nT1 -> s(T15)\nT2 -> T9" }, { "from": 209, "to": 1, "label": "INSTANCE with matching:\nT1 -> s(T15)\nT2 -> T16" }, { "from": 241, "to": 243, "label": "ONLY EVAL with clause\ndistr(X34, X35, X34, X35).\nand substitutionT6 -> T21,\nX34 -> s(T21),\nX35 -> T21,\nX14 -> s(T21),\nX15 -> T21" }, { "from": 242, "to": 262, "label": "ONLY EVAL with clause\ndistr(X40, X41, X41, X40).\nand substitutionT6 -> T25,\nX40 -> s(T25),\nX41 -> T25,\nX14 -> T25,\nX15 -> s(T25)" }, { "from": 243, "to": 260, "label": "SPLIT 1" }, { "from": 243, "to": 261, "label": "SPLIT 2\nnew knowledge:\nT21 is ground\nT9 is ground\nreplacements:T10 -> T22" }, { "from": 260, "to": 1, "label": "INSTANCE with matching:\nT1 -> s(T21)\nT2 -> T9" }, { "from": 261, "to": 1, "label": "INSTANCE with matching:\nT1 -> T21\nT2 -> T22" }, { "from": 262, "to": 263, "label": "SPLIT 1" }, { "from": 262, "to": 264, "label": "SPLIT 2\nnew knowledge:\nT25 is ground\nT9 is ground\nreplacements:T10 -> T26" }, { "from": 263, "to": 1, "label": "INSTANCE with matching:\nT1 -> T25\nT2 -> T9" }, { "from": 264, "to": 1, "label": "INSTANCE with matching:\nT1 -> s(T25)\nT2 -> T26" } ], "type": "Graph" } } ---------------------------------------- (2) Obligation: Triples: hbal_treeA(s(s(X1)), t(x, X2, X3)) :- hbal_treeA(s(X1), X2). hbal_treeA(s(s(X1)), t(x, X2, X3)) :- ','(hbal_treecA(s(X1), X2), hbal_treeA(s(X1), X3)). hbal_treeA(s(s(X1)), t(x, X2, X3)) :- hbal_treeA(s(X1), X2). hbal_treeA(s(s(X1)), t(x, X2, X3)) :- ','(hbal_treecA(s(X1), X2), hbal_treeA(X1, X3)). hbal_treeA(s(s(X1)), t(x, X2, X3)) :- hbal_treeA(X1, X2). hbal_treeA(s(s(X1)), t(x, X2, X3)) :- ','(hbal_treecA(X1, X2), hbal_treeA(s(X1), X3)). Clauses: hbal_treecA(zero, nil). hbal_treecA(s(zero), t(x, nil, nil)). hbal_treecA(s(s(X1)), t(x, X2, X3)) :- ','(hbal_treecA(s(X1), X2), hbal_treecA(s(X1), X3)). hbal_treecA(s(s(X1)), t(x, X2, X3)) :- ','(hbal_treecA(s(X1), X2), hbal_treecA(X1, X3)). hbal_treecA(s(s(X1)), t(x, X2, X3)) :- ','(hbal_treecA(X1, X2), hbal_treecA(s(X1), X3)). Afs: hbal_treeA(x1, x2) = hbal_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: hbal_treeA_in_2: (b,f) hbal_treecA_in_2: (b,f) Transforming TRIPLES into the following Term Rewriting System: Pi DP problem: The TRS P consists of the following rules: HBAL_TREEA_IN_GA(s(s(X1)), t(x, X2, X3)) -> U1_GA(X1, X2, X3, hbal_treeA_in_ga(s(X1), X2)) HBAL_TREEA_IN_GA(s(s(X1)), t(x, X2, X3)) -> HBAL_TREEA_IN_GA(s(X1), X2) HBAL_TREEA_IN_GA(s(s(X1)), t(x, X2, X3)) -> U2_GA(X1, X2, X3, hbal_treecA_in_ga(s(X1), X2)) U2_GA(X1, X2, X3, hbal_treecA_out_ga(s(X1), X2)) -> U3_GA(X1, X2, X3, hbal_treeA_in_ga(s(X1), X3)) U2_GA(X1, X2, X3, hbal_treecA_out_ga(s(X1), X2)) -> HBAL_TREEA_IN_GA(s(X1), X3) HBAL_TREEA_IN_GA(s(s(X1)), t(x, X2, X3)) -> U5_GA(X1, X2, X3, hbal_treeA_in_ga(X1, X2)) HBAL_TREEA_IN_GA(s(s(X1)), t(x, X2, X3)) -> HBAL_TREEA_IN_GA(X1, X2) HBAL_TREEA_IN_GA(s(s(X1)), t(x, X2, X3)) -> U6_GA(X1, X2, X3, hbal_treecA_in_ga(X1, X2)) U6_GA(X1, X2, X3, hbal_treecA_out_ga(X1, X2)) -> U7_GA(X1, X2, X3, hbal_treeA_in_ga(s(X1), X3)) U6_GA(X1, X2, X3, hbal_treecA_out_ga(X1, X2)) -> HBAL_TREEA_IN_GA(s(X1), X3) U2_GA(X1, X2, X3, hbal_treecA_out_ga(s(X1), X2)) -> U4_GA(X1, X2, X3, hbal_treeA_in_ga(X1, X3)) U2_GA(X1, X2, X3, hbal_treecA_out_ga(s(X1), X2)) -> HBAL_TREEA_IN_GA(X1, X3) The TRS R consists of the following rules: hbal_treecA_in_ga(zero, nil) -> hbal_treecA_out_ga(zero, nil) hbal_treecA_in_ga(s(zero), t(x, nil, nil)) -> hbal_treecA_out_ga(s(zero), t(x, nil, nil)) hbal_treecA_in_ga(s(s(X1)), t(x, X2, X3)) -> U9_ga(X1, X2, X3, hbal_treecA_in_ga(s(X1), X2)) hbal_treecA_in_ga(s(s(X1)), t(x, X2, X3)) -> U12_ga(X1, X2, X3, hbal_treecA_in_ga(X1, X2)) U12_ga(X1, X2, X3, hbal_treecA_out_ga(X1, X2)) -> U13_ga(X1, X2, X3, hbal_treecA_in_ga(s(X1), X3)) U13_ga(X1, X2, X3, hbal_treecA_out_ga(s(X1), X3)) -> hbal_treecA_out_ga(s(s(X1)), t(x, X2, X3)) U9_ga(X1, X2, X3, hbal_treecA_out_ga(s(X1), X2)) -> U10_ga(X1, X2, X3, hbal_treecA_in_ga(s(X1), X3)) U10_ga(X1, X2, X3, hbal_treecA_out_ga(s(X1), X3)) -> hbal_treecA_out_ga(s(s(X1)), t(x, X2, X3)) U9_ga(X1, X2, X3, hbal_treecA_out_ga(s(X1), X2)) -> U11_ga(X1, X2, X3, hbal_treecA_in_ga(X1, X3)) U11_ga(X1, X2, X3, hbal_treecA_out_ga(X1, X3)) -> hbal_treecA_out_ga(s(s(X1)), t(x, X2, X3)) The argument filtering Pi contains the following mapping: hbal_treeA_in_ga(x1, x2) = hbal_treeA_in_ga(x1) s(x1) = s(x1) hbal_treecA_in_ga(x1, x2) = hbal_treecA_in_ga(x1) zero = zero hbal_treecA_out_ga(x1, x2) = hbal_treecA_out_ga(x1, x2) U9_ga(x1, x2, x3, x4) = U9_ga(x1, x4) U12_ga(x1, x2, x3, x4) = U12_ga(x1, x4) U13_ga(x1, x2, x3, x4) = U13_ga(x1, x2, x4) U10_ga(x1, x2, x3, x4) = U10_ga(x1, x2, x4) U11_ga(x1, x2, x3, x4) = U11_ga(x1, x2, x4) t(x1, x2, x3) = t(x1, x2, x3) x = x HBAL_TREEA_IN_GA(x1, x2) = HBAL_TREEA_IN_GA(x1) U1_GA(x1, x2, x3, x4) = U1_GA(x1, x4) U2_GA(x1, x2, x3, x4) = U2_GA(x1, x4) U3_GA(x1, x2, x3, x4) = U3_GA(x1, x4) U5_GA(x1, x2, x3, x4) = U5_GA(x1, x4) U6_GA(x1, x2, x3, x4) = U6_GA(x1, x4) U7_GA(x1, x2, x3, x4) = U7_GA(x1, x4) U4_GA(x1, x2, x3, x4) = U4_GA(x1, x4) 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: HBAL_TREEA_IN_GA(s(s(X1)), t(x, X2, X3)) -> U1_GA(X1, X2, X3, hbal_treeA_in_ga(s(X1), X2)) HBAL_TREEA_IN_GA(s(s(X1)), t(x, X2, X3)) -> HBAL_TREEA_IN_GA(s(X1), X2) HBAL_TREEA_IN_GA(s(s(X1)), t(x, X2, X3)) -> U2_GA(X1, X2, X3, hbal_treecA_in_ga(s(X1), X2)) U2_GA(X1, X2, X3, hbal_treecA_out_ga(s(X1), X2)) -> U3_GA(X1, X2, X3, hbal_treeA_in_ga(s(X1), X3)) U2_GA(X1, X2, X3, hbal_treecA_out_ga(s(X1), X2)) -> HBAL_TREEA_IN_GA(s(X1), X3) HBAL_TREEA_IN_GA(s(s(X1)), t(x, X2, X3)) -> U5_GA(X1, X2, X3, hbal_treeA_in_ga(X1, X2)) HBAL_TREEA_IN_GA(s(s(X1)), t(x, X2, X3)) -> HBAL_TREEA_IN_GA(X1, X2) HBAL_TREEA_IN_GA(s(s(X1)), t(x, X2, X3)) -> U6_GA(X1, X2, X3, hbal_treecA_in_ga(X1, X2)) U6_GA(X1, X2, X3, hbal_treecA_out_ga(X1, X2)) -> U7_GA(X1, X2, X3, hbal_treeA_in_ga(s(X1), X3)) U6_GA(X1, X2, X3, hbal_treecA_out_ga(X1, X2)) -> HBAL_TREEA_IN_GA(s(X1), X3) U2_GA(X1, X2, X3, hbal_treecA_out_ga(s(X1), X2)) -> U4_GA(X1, X2, X3, hbal_treeA_in_ga(X1, X3)) U2_GA(X1, X2, X3, hbal_treecA_out_ga(s(X1), X2)) -> HBAL_TREEA_IN_GA(X1, X3) The TRS R consists of the following rules: hbal_treecA_in_ga(zero, nil) -> hbal_treecA_out_ga(zero, nil) hbal_treecA_in_ga(s(zero), t(x, nil, nil)) -> hbal_treecA_out_ga(s(zero), t(x, nil, nil)) hbal_treecA_in_ga(s(s(X1)), t(x, X2, X3)) -> U9_ga(X1, X2, X3, hbal_treecA_in_ga(s(X1), X2)) hbal_treecA_in_ga(s(s(X1)), t(x, X2, X3)) -> U12_ga(X1, X2, X3, hbal_treecA_in_ga(X1, X2)) U12_ga(X1, X2, X3, hbal_treecA_out_ga(X1, X2)) -> U13_ga(X1, X2, X3, hbal_treecA_in_ga(s(X1), X3)) U13_ga(X1, X2, X3, hbal_treecA_out_ga(s(X1), X3)) -> hbal_treecA_out_ga(s(s(X1)), t(x, X2, X3)) U9_ga(X1, X2, X3, hbal_treecA_out_ga(s(X1), X2)) -> U10_ga(X1, X2, X3, hbal_treecA_in_ga(s(X1), X3)) U10_ga(X1, X2, X3, hbal_treecA_out_ga(s(X1), X3)) -> hbal_treecA_out_ga(s(s(X1)), t(x, X2, X3)) U9_ga(X1, X2, X3, hbal_treecA_out_ga(s(X1), X2)) -> U11_ga(X1, X2, X3, hbal_treecA_in_ga(X1, X3)) U11_ga(X1, X2, X3, hbal_treecA_out_ga(X1, X3)) -> hbal_treecA_out_ga(s(s(X1)), t(x, X2, X3)) The argument filtering Pi contains the following mapping: hbal_treeA_in_ga(x1, x2) = hbal_treeA_in_ga(x1) s(x1) = s(x1) hbal_treecA_in_ga(x1, x2) = hbal_treecA_in_ga(x1) zero = zero hbal_treecA_out_ga(x1, x2) = hbal_treecA_out_ga(x1, x2) U9_ga(x1, x2, x3, x4) = U9_ga(x1, x4) U12_ga(x1, x2, x3, x4) = U12_ga(x1, x4) U13_ga(x1, x2, x3, x4) = U13_ga(x1, x2, x4) U10_ga(x1, x2, x3, x4) = U10_ga(x1, x2, x4) U11_ga(x1, x2, x3, x4) = U11_ga(x1, x2, x4) t(x1, x2, x3) = t(x1, x2, x3) x = x HBAL_TREEA_IN_GA(x1, x2) = HBAL_TREEA_IN_GA(x1) U1_GA(x1, x2, x3, x4) = U1_GA(x1, x4) U2_GA(x1, x2, x3, x4) = U2_GA(x1, x4) U3_GA(x1, x2, x3, x4) = U3_GA(x1, x4) U5_GA(x1, x2, x3, x4) = U5_GA(x1, x4) U6_GA(x1, x2, x3, x4) = U6_GA(x1, x4) U7_GA(x1, x2, x3, x4) = U7_GA(x1, x4) U4_GA(x1, x2, x3, x4) = U4_GA(x1, x4) We have to consider all (P,R,Pi)-chains ---------------------------------------- (5) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LOPSTR] contains 1 SCC with 5 less nodes. ---------------------------------------- (6) Obligation: Pi DP problem: The TRS P consists of the following rules: HBAL_TREEA_IN_GA(s(s(X1)), t(x, X2, X3)) -> U2_GA(X1, X2, X3, hbal_treecA_in_ga(s(X1), X2)) U2_GA(X1, X2, X3, hbal_treecA_out_ga(s(X1), X2)) -> HBAL_TREEA_IN_GA(s(X1), X3) HBAL_TREEA_IN_GA(s(s(X1)), t(x, X2, X3)) -> HBAL_TREEA_IN_GA(s(X1), X2) HBAL_TREEA_IN_GA(s(s(X1)), t(x, X2, X3)) -> HBAL_TREEA_IN_GA(X1, X2) HBAL_TREEA_IN_GA(s(s(X1)), t(x, X2, X3)) -> U6_GA(X1, X2, X3, hbal_treecA_in_ga(X1, X2)) U6_GA(X1, X2, X3, hbal_treecA_out_ga(X1, X2)) -> HBAL_TREEA_IN_GA(s(X1), X3) U2_GA(X1, X2, X3, hbal_treecA_out_ga(s(X1), X2)) -> HBAL_TREEA_IN_GA(X1, X3) The TRS R consists of the following rules: hbal_treecA_in_ga(zero, nil) -> hbal_treecA_out_ga(zero, nil) hbal_treecA_in_ga(s(zero), t(x, nil, nil)) -> hbal_treecA_out_ga(s(zero), t(x, nil, nil)) hbal_treecA_in_ga(s(s(X1)), t(x, X2, X3)) -> U9_ga(X1, X2, X3, hbal_treecA_in_ga(s(X1), X2)) hbal_treecA_in_ga(s(s(X1)), t(x, X2, X3)) -> U12_ga(X1, X2, X3, hbal_treecA_in_ga(X1, X2)) U12_ga(X1, X2, X3, hbal_treecA_out_ga(X1, X2)) -> U13_ga(X1, X2, X3, hbal_treecA_in_ga(s(X1), X3)) U13_ga(X1, X2, X3, hbal_treecA_out_ga(s(X1), X3)) -> hbal_treecA_out_ga(s(s(X1)), t(x, X2, X3)) U9_ga(X1, X2, X3, hbal_treecA_out_ga(s(X1), X2)) -> U10_ga(X1, X2, X3, hbal_treecA_in_ga(s(X1), X3)) U10_ga(X1, X2, X3, hbal_treecA_out_ga(s(X1), X3)) -> hbal_treecA_out_ga(s(s(X1)), t(x, X2, X3)) U9_ga(X1, X2, X3, hbal_treecA_out_ga(s(X1), X2)) -> U11_ga(X1, X2, X3, hbal_treecA_in_ga(X1, X3)) U11_ga(X1, X2, X3, hbal_treecA_out_ga(X1, X3)) -> hbal_treecA_out_ga(s(s(X1)), t(x, X2, X3)) The argument filtering Pi contains the following mapping: s(x1) = s(x1) hbal_treecA_in_ga(x1, x2) = hbal_treecA_in_ga(x1) zero = zero hbal_treecA_out_ga(x1, x2) = hbal_treecA_out_ga(x1, x2) U9_ga(x1, x2, x3, x4) = U9_ga(x1, x4) U12_ga(x1, x2, x3, x4) = U12_ga(x1, x4) U13_ga(x1, x2, x3, x4) = U13_ga(x1, x2, x4) U10_ga(x1, x2, x3, x4) = U10_ga(x1, x2, x4) U11_ga(x1, x2, x3, x4) = U11_ga(x1, x2, x4) t(x1, x2, x3) = t(x1, x2, x3) x = x HBAL_TREEA_IN_GA(x1, x2) = HBAL_TREEA_IN_GA(x1) U2_GA(x1, x2, x3, x4) = U2_GA(x1, x4) U6_GA(x1, x2, x3, x4) = U6_GA(x1, x4) We have to consider all (P,R,Pi)-chains ---------------------------------------- (7) PiDPToQDPProof (SOUND) 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: HBAL_TREEA_IN_GA(s(s(X1))) -> U2_GA(X1, hbal_treecA_in_ga(s(X1))) U2_GA(X1, hbal_treecA_out_ga(s(X1), X2)) -> HBAL_TREEA_IN_GA(s(X1)) HBAL_TREEA_IN_GA(s(s(X1))) -> HBAL_TREEA_IN_GA(s(X1)) HBAL_TREEA_IN_GA(s(s(X1))) -> HBAL_TREEA_IN_GA(X1) HBAL_TREEA_IN_GA(s(s(X1))) -> U6_GA(X1, hbal_treecA_in_ga(X1)) U6_GA(X1, hbal_treecA_out_ga(X1, X2)) -> HBAL_TREEA_IN_GA(s(X1)) U2_GA(X1, hbal_treecA_out_ga(s(X1), X2)) -> HBAL_TREEA_IN_GA(X1) The TRS R consists of the following rules: hbal_treecA_in_ga(zero) -> hbal_treecA_out_ga(zero, nil) hbal_treecA_in_ga(s(zero)) -> hbal_treecA_out_ga(s(zero), t(x, nil, nil)) hbal_treecA_in_ga(s(s(X1))) -> U9_ga(X1, hbal_treecA_in_ga(s(X1))) hbal_treecA_in_ga(s(s(X1))) -> U12_ga(X1, hbal_treecA_in_ga(X1)) U12_ga(X1, hbal_treecA_out_ga(X1, X2)) -> U13_ga(X1, X2, hbal_treecA_in_ga(s(X1))) U13_ga(X1, X2, hbal_treecA_out_ga(s(X1), X3)) -> hbal_treecA_out_ga(s(s(X1)), t(x, X2, X3)) U9_ga(X1, hbal_treecA_out_ga(s(X1), X2)) -> U10_ga(X1, X2, hbal_treecA_in_ga(s(X1))) U10_ga(X1, X2, hbal_treecA_out_ga(s(X1), X3)) -> hbal_treecA_out_ga(s(s(X1)), t(x, X2, X3)) U9_ga(X1, hbal_treecA_out_ga(s(X1), X2)) -> U11_ga(X1, X2, hbal_treecA_in_ga(X1)) U11_ga(X1, X2, hbal_treecA_out_ga(X1, X3)) -> hbal_treecA_out_ga(s(s(X1)), t(x, X2, X3)) The set Q consists of the following terms: hbal_treecA_in_ga(x0) U12_ga(x0, x1) U13_ga(x0, x1, x2) U9_ga(x0, x1) U10_ga(x0, x1, x2) U11_ga(x0, x1, x2) We have to consider all (P,Q,R)-chains. ---------------------------------------- (9) MRRProof (EQUIVALENT) 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: HBAL_TREEA_IN_GA(s(s(X1))) -> U2_GA(X1, hbal_treecA_in_ga(s(X1))) U2_GA(X1, hbal_treecA_out_ga(s(X1), X2)) -> HBAL_TREEA_IN_GA(s(X1)) HBAL_TREEA_IN_GA(s(s(X1))) -> HBAL_TREEA_IN_GA(s(X1)) HBAL_TREEA_IN_GA(s(s(X1))) -> HBAL_TREEA_IN_GA(X1) HBAL_TREEA_IN_GA(s(s(X1))) -> U6_GA(X1, hbal_treecA_in_ga(X1)) U6_GA(X1, hbal_treecA_out_ga(X1, X2)) -> HBAL_TREEA_IN_GA(s(X1)) U2_GA(X1, hbal_treecA_out_ga(s(X1), X2)) -> HBAL_TREEA_IN_GA(X1) Used ordering: Polynomial interpretation [POLO]: POL(HBAL_TREEA_IN_GA(x_1)) = 1 + x_1 POL(U10_ga(x_1, x_2, x_3)) = 2 + 2*x_1 + 2*x_2 + x_3 POL(U11_ga(x_1, x_2, x_3)) = 1 + 2*x_1 + 2*x_2 + 2*x_3 POL(U12_ga(x_1, x_2)) = 1 + 2*x_1 + 2*x_2 POL(U13_ga(x_1, x_2, x_3)) = 2 + 2*x_1 + 2*x_2 + x_3 POL(U2_GA(x_1, x_2)) = 2*x_1 + x_2 POL(U6_GA(x_1, x_2)) = 1 + 2*x_1 + x_2 POL(U9_ga(x_1, x_2)) = 2 + 2*x_1 + x_2 POL(hbal_treecA_in_ga(x_1)) = 2 + x_1 POL(hbal_treecA_out_ga(x_1, x_2)) = 2 + x_1 + 2*x_2 POL(nil) = 0 POL(s(x_1)) = 1 + 2*x_1 POL(t(x_1, x_2, x_3)) = 2*x_1 + x_2 + x_3 POL(x) = 0 POL(zero) = 0 ---------------------------------------- (10) Obligation: Q DP problem: P is empty. The TRS R consists of the following rules: hbal_treecA_in_ga(zero) -> hbal_treecA_out_ga(zero, nil) hbal_treecA_in_ga(s(zero)) -> hbal_treecA_out_ga(s(zero), t(x, nil, nil)) hbal_treecA_in_ga(s(s(X1))) -> U9_ga(X1, hbal_treecA_in_ga(s(X1))) hbal_treecA_in_ga(s(s(X1))) -> U12_ga(X1, hbal_treecA_in_ga(X1)) U12_ga(X1, hbal_treecA_out_ga(X1, X2)) -> U13_ga(X1, X2, hbal_treecA_in_ga(s(X1))) U13_ga(X1, X2, hbal_treecA_out_ga(s(X1), X3)) -> hbal_treecA_out_ga(s(s(X1)), t(x, X2, X3)) U9_ga(X1, hbal_treecA_out_ga(s(X1), X2)) -> U10_ga(X1, X2, hbal_treecA_in_ga(s(X1))) U10_ga(X1, X2, hbal_treecA_out_ga(s(X1), X3)) -> hbal_treecA_out_ga(s(s(X1)), t(x, X2, X3)) U9_ga(X1, hbal_treecA_out_ga(s(X1), X2)) -> U11_ga(X1, X2, hbal_treecA_in_ga(X1)) U11_ga(X1, X2, hbal_treecA_out_ga(X1, X3)) -> hbal_treecA_out_ga(s(s(X1)), t(x, X2, X3)) The set Q consists of the following terms: hbal_treecA_in_ga(x0) U12_ga(x0, x1) U13_ga(x0, x1, x2) U9_ga(x0, x1) U10_ga(x0, x1, x2) U11_ga(x0, x1, x2) We have to consider all (P,Q,R)-chains. ---------------------------------------- (11) PisEmptyProof (EQUIVALENT) The TRS P is empty. Hence, there is no (P,Q,R) chain. ---------------------------------------- (12) YES