YES proof of /export/starexec/sandbox/benchmark/theBenchmark.pl # AProVE Commit ID: 794c25de1cacf0d048858bcd21c9a779e1221865 marcel 20200619 unpublished dirty Left Termination of the query pattern flat(g,a) w.r.t. the given Prolog program could successfully be proven: (0) Prolog (1) PrologToDTProblemTransformerProof [SOUND, 0 ms] (2) TRIPLES (3) TriplesToPiDPProof [SOUND, 4 ms] (4) PiDP (5) DependencyGraphProof [EQUIVALENT, 0 ms] (6) PiDP (7) PiDPToQDPProof [SOUND, 0 ms] (8) QDP (9) UsableRulesReductionPairsProof [EQUIVALENT, 12 ms] (10) QDP (11) MRRProof [EQUIVALENT, 0 ms] (12) QDP (13) PisEmptyProof [EQUIVALENT, 0 ms] (14) YES ---------------------------------------- (0) Obligation: Clauses: right(tree(X, XS1, XS2), XS2). flat(niltree, nil). flat(tree(X, niltree, XS), cons(X, YS)) :- ','(right(tree(X, niltree, XS), ZS), flat(ZS, YS)). flat(tree(X, tree(Y, YS1, YS2), XS), ZS) :- flat(tree(Y, YS1, tree(X, YS2, XS)), ZS). Query: flat(g,a) ---------------------------------------- (1) PrologToDTProblemTransformerProof (SOUND) Built DT problem from termination graph DT10. { "root": 2, "program": { "directives": [], "clauses": [ [ "(right (tree X XS1 XS2) XS2)", null ], [ "(flat (niltree) (nil))", null ], [ "(flat (tree X (niltree) XS) (cons X YS))", "(',' (right (tree X (niltree) XS) ZS) (flat ZS YS))" ], [ "(flat (tree X (tree Y YS1 YS2) XS) ZS)", "(flat (tree Y YS1 (tree X YS2 XS)) ZS)" ] ] }, "graph": { "nodes": { "type": "Nodes", "197": { "goal": [ { "clause": -1, "scope": -1, "term": "(',' (right (tree T6 (niltree) T7) X16) (flat X16 T9))" }, { "clause": 3, "scope": 1, "term": "(flat (tree T6 (niltree) T7) T2)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T6", "T7" ], "free": ["X16"], "exprvars": [] } }, "230": { "goal": [{ "clause": -1, "scope": -1, "term": "(flat (tree T69 T70 T71) T59)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T69", "T70", "T71" ], "free": [], "exprvars": [] } }, "110": { "goal": [{ "clause": 3, "scope": 1, "term": "(flat (niltree) T2)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "198": { "goal": [{ "clause": 3, "scope": 1, "term": "(flat T1 T2)" }], "kb": { "nonunifying": [ [ "(flat T1 T2)", "(flat (niltree) (nil))" ], [ "(flat T1 T2)", "(flat (tree X13 (niltree) X14) (cons X13 X15))" ] ], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T1"], "free": [ "X13", "X14", "X15" ], "exprvars": [] } }, "231": { "goal": [{ "clause": -1, "scope": -1, "term": "(flat (tree T89 T90 (tree T88 T91 (tree T92 T93 T94))) T96)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T88", "T89", "T90", "T91", "T92", "T93", "T94" ], "free": [], "exprvars": [] } }, "111": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "210": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "232": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "211": { "goal": [ { "clause": 1, "scope": 3, "term": "(flat (tree T28 T29 (tree T27 T30 T31)) T33)" }, { "clause": 2, "scope": 3, "term": "(flat (tree T28 T29 (tree T27 T30 T31)) T33)" }, { "clause": 3, "scope": 3, "term": "(flat (tree T28 T29 (tree T27 T30 T31)) T33)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T27", "T28", "T29", "T30", "T31" ], "free": [], "exprvars": [] } }, "212": { "goal": [ { "clause": 2, "scope": 3, "term": "(flat (tree T28 T29 (tree T27 T30 T31)) T33)" }, { "clause": 3, "scope": 3, "term": "(flat (tree T28 T29 (tree T27 T30 T31)) T33)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T27", "T28", "T29", "T30", "T31" ], "free": [], "exprvars": [] } }, "2": { "goal": [{ "clause": -1, "scope": -1, "term": "(flat T1 T2)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T1"], "free": [], "exprvars": [] } }, "203": { "goal": [ { "clause": 0, "scope": 2, "term": "(',' (right (tree T6 (niltree) T7) X16) (flat X16 T9))" }, { "clause": -1, "scope": 2, "term": null }, { "clause": 3, "scope": 1, "term": "(flat (tree T6 (niltree) T7) T2)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T6", "T7" ], "free": ["X16"], "exprvars": [] } }, "225": { "goal": [{ "clause": 2, "scope": 3, "term": "(flat (tree T28 T29 (tree T27 T30 T31)) T33)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T27", "T28", "T29", "T30", "T31" ], "free": [], "exprvars": [] } }, "204": { "goal": [{ "clause": 0, "scope": 2, "term": "(',' (right (tree T6 (niltree) T7) X16) (flat X16 T9))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T6", "T7" ], "free": ["X16"], "exprvars": [] } }, "226": { "goal": [{ "clause": 3, "scope": 3, "term": "(flat (tree T28 T29 (tree T27 T30 T31)) T33)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T27", "T28", "T29", "T30", "T31" ], "free": [], "exprvars": [] } }, "7": { "goal": [ { "clause": 1, "scope": 1, "term": "(flat T1 T2)" }, { "clause": 2, "scope": 1, "term": "(flat T1 T2)" }, { "clause": 3, "scope": 1, "term": "(flat T1 T2)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T1"], "free": [], "exprvars": [] } }, "205": { "goal": [ { "clause": -1, "scope": 2, "term": null }, { "clause": 3, "scope": 1, "term": "(flat (tree T6 (niltree) T7) T2)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T6", "T7" ], "free": [], "exprvars": [] } }, "227": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (right (tree T54 (niltree) (tree T55 T56 T57)) X67) (flat X67 T59))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T54", "T55", "T56", "T57" ], "free": ["X67"], "exprvars": [] } }, "107": { "goal": [ { "clause": -1, "scope": -1, "term": "(true)" }, { "clause": 2, "scope": 1, "term": "(flat (niltree) T2)" }, { "clause": 3, "scope": 1, "term": "(flat (niltree) T2)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "206": { "goal": [{ "clause": -1, "scope": -1, "term": "(flat T19 T9)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T19"], "free": [], "exprvars": [] } }, "228": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "108": { "goal": [ { "clause": 2, "scope": 1, "term": "(flat T1 T2)" }, { "clause": 3, "scope": 1, "term": "(flat T1 T2)" } ], "kb": { "nonunifying": [[ "(flat T1 T2)", "(flat (niltree) (nil))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T1"], "free": [], "exprvars": [] } }, "207": { "goal": [{ "clause": 3, "scope": 1, "term": "(flat (tree T6 (niltree) T7) T2)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T6", "T7" ], "free": [], "exprvars": [] } }, "229": { "goal": [{ "clause": 0, "scope": 4, "term": "(',' (right (tree T54 (niltree) (tree T55 T56 T57)) X67) (flat X67 T59))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T54", "T55", "T56", "T57" ], "free": ["X67"], "exprvars": [] } }, "109": { "goal": [ { "clause": 2, "scope": 1, "term": "(flat (niltree) T2)" }, { "clause": 3, "scope": 1, "term": "(flat (niltree) T2)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "208": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "209": { "goal": [{ "clause": -1, "scope": -1, "term": "(flat (tree T28 T29 (tree T27 T30 T31)) T33)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T27", "T28", "T29", "T30", "T31" ], "free": [], "exprvars": [] } } }, "edges": [ { "from": 2, "to": 7, "label": "CASE" }, { "from": 7, "to": 107, "label": "EVAL with clause\nflat(niltree, nil).\nand substitutionT1 -> niltree,\nT2 -> nil" }, { "from": 7, "to": 108, "label": "EVAL-BACKTRACK" }, { "from": 107, "to": 109, "label": "SUCCESS" }, { "from": 108, "to": 197, "label": "EVAL with clause\nflat(tree(X13, niltree, X14), cons(X13, X15)) :- ','(right(tree(X13, niltree, X14), X16), flat(X16, X15)).\nand substitutionX13 -> T6,\nX14 -> T7,\nT1 -> tree(T6, niltree, T7),\nX15 -> T9,\nT2 -> cons(T6, T9),\nT8 -> T9" }, { "from": 108, "to": 198, "label": "EVAL-BACKTRACK" }, { "from": 109, "to": 110, "label": "BACKTRACK\nfor clause: flat(tree(X, niltree, XS), cons(X, YS)) :- ','(right(tree(X, niltree, XS), ZS), flat(ZS, YS))because of non-unification" }, { "from": 110, "to": 111, "label": "BACKTRACK\nfor clause: flat(tree(X, tree(Y, YS1, YS2), XS), ZS) :- flat(tree(Y, YS1, tree(X, YS2, XS)), ZS)because of non-unification" }, { "from": 197, "to": 203, "label": "CASE" }, { "from": 198, "to": 209, "label": "EVAL with clause\nflat(tree(X44, tree(X45, X46, X47), X48), X49) :- flat(tree(X45, X46, tree(X44, X47, X48)), X49).\nand substitutionX44 -> T27,\nX45 -> T28,\nX46 -> T29,\nX47 -> T30,\nX48 -> T31,\nT1 -> tree(T27, tree(T28, T29, T30), T31),\nT2 -> T33,\nX49 -> T33,\nT32 -> T33" }, { "from": 198, "to": 210, "label": "EVAL-BACKTRACK" }, { "from": 203, "to": 204, "label": "PARALLEL" }, { "from": 203, "to": 205, "label": "PARALLEL" }, { "from": 204, "to": 206, "label": "ONLY EVAL with clause\nright(tree(X29, X30, X31), X31).\nand substitutionT6 -> T18,\nX29 -> T18,\nX30 -> niltree,\nT7 -> T19,\nX31 -> T19,\nX16 -> T19" }, { "from": 205, "to": 207, "label": "FAILURE" }, { "from": 206, "to": 2, "label": "INSTANCE with matching:\nT1 -> T19\nT2 -> T9" }, { "from": 207, "to": 208, "label": "BACKTRACK\nfor clause: flat(tree(X, tree(Y, YS1, YS2), XS), ZS) :- flat(tree(Y, YS1, tree(X, YS2, XS)), ZS)because of non-unification" }, { "from": 209, "to": 211, "label": "CASE" }, { "from": 211, "to": 212, "label": "BACKTRACK\nfor clause: flat(niltree, nil)because of non-unification" }, { "from": 212, "to": 225, "label": "PARALLEL" }, { "from": 212, "to": 226, "label": "PARALLEL" }, { "from": 225, "to": 227, "label": "EVAL with clause\nflat(tree(X64, niltree, X65), cons(X64, X66)) :- ','(right(tree(X64, niltree, X65), X67), flat(X67, X66)).\nand substitutionT28 -> T54,\nX64 -> T54,\nT29 -> niltree,\nT27 -> T55,\nT30 -> T56,\nT31 -> T57,\nX65 -> tree(T55, T56, T57),\nX66 -> T59,\nT33 -> cons(T54, T59),\nT58 -> T59" }, { "from": 225, "to": 228, "label": "EVAL-BACKTRACK" }, { "from": 226, "to": 231, "label": "EVAL with clause\nflat(tree(X89, tree(X90, X91, X92), X93), X94) :- flat(tree(X90, X91, tree(X89, X92, X93)), X94).\nand substitutionT28 -> T88,\nX89 -> T88,\nX90 -> T89,\nX91 -> T90,\nX92 -> T91,\nT29 -> tree(T89, T90, T91),\nT27 -> T92,\nT30 -> T93,\nT31 -> T94,\nX93 -> tree(T92, T93, T94),\nT33 -> T96,\nX94 -> T96,\nT95 -> T96" }, { "from": 226, "to": 232, "label": "EVAL-BACKTRACK" }, { "from": 227, "to": 229, "label": "CASE" }, { "from": 229, "to": 230, "label": "ONLY EVAL with clause\nright(tree(X74, X75, X76), X76).\nand substitutionT54 -> T68,\nX74 -> T68,\nX75 -> niltree,\nT55 -> T69,\nT56 -> T70,\nT57 -> T71,\nX76 -> tree(T69, T70, T71),\nX67 -> tree(T69, T70, T71)" }, { "from": 230, "to": 2, "label": "INSTANCE with matching:\nT1 -> tree(T69, T70, T71)\nT2 -> T59" }, { "from": 231, "to": 2, "label": "INSTANCE with matching:\nT1 -> tree(T89, T90, tree(T88, T91, tree(T92, T93, T94)))\nT2 -> T96" } ], "type": "Graph" } } ---------------------------------------- (2) Obligation: Triples: flatA(tree(X1, niltree, X2), cons(X1, X3)) :- flatA(X2, X3). flatA(tree(X1, tree(X2, niltree, X3), X4), cons(X2, X5)) :- flatA(tree(X1, X3, X4), X5). flatA(tree(X1, tree(X2, tree(X3, X4, X5), X6), X7), X8) :- flatA(tree(X3, X4, tree(X2, X5, tree(X1, X6, X7))), X8). Clauses: flatcA(niltree, nil). flatcA(tree(X1, niltree, X2), cons(X1, X3)) :- flatcA(X2, X3). flatcA(tree(X1, tree(X2, niltree, X3), X4), cons(X2, X5)) :- flatcA(tree(X1, X3, X4), X5). flatcA(tree(X1, tree(X2, tree(X3, X4, X5), X6), X7), X8) :- flatcA(tree(X3, X4, tree(X2, X5, tree(X1, X6, X7))), X8). Afs: flatA(x1, x2) = flatA(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: flatA_in_2: (b,f) Transforming TRIPLES into the following Term Rewriting System: Pi DP problem: The TRS P consists of the following rules: FLATA_IN_GA(tree(X1, niltree, X2), cons(X1, X3)) -> U1_GA(X1, X2, X3, flatA_in_ga(X2, X3)) FLATA_IN_GA(tree(X1, niltree, X2), cons(X1, X3)) -> FLATA_IN_GA(X2, X3) FLATA_IN_GA(tree(X1, tree(X2, niltree, X3), X4), cons(X2, X5)) -> U2_GA(X1, X2, X3, X4, X5, flatA_in_ga(tree(X1, X3, X4), X5)) FLATA_IN_GA(tree(X1, tree(X2, niltree, X3), X4), cons(X2, X5)) -> FLATA_IN_GA(tree(X1, X3, X4), X5) FLATA_IN_GA(tree(X1, tree(X2, tree(X3, X4, X5), X6), X7), X8) -> U3_GA(X1, X2, X3, X4, X5, X6, X7, X8, flatA_in_ga(tree(X3, X4, tree(X2, X5, tree(X1, X6, X7))), X8)) FLATA_IN_GA(tree(X1, tree(X2, tree(X3, X4, X5), X6), X7), X8) -> FLATA_IN_GA(tree(X3, X4, tree(X2, X5, tree(X1, X6, X7))), X8) R is empty. The argument filtering Pi contains the following mapping: flatA_in_ga(x1, x2) = flatA_in_ga(x1) tree(x1, x2, x3) = tree(x1, x2, x3) niltree = niltree cons(x1, x2) = cons(x1, x2) FLATA_IN_GA(x1, x2) = FLATA_IN_GA(x1) U1_GA(x1, x2, x3, x4) = U1_GA(x1, x2, x4) U2_GA(x1, x2, x3, x4, x5, x6) = U2_GA(x1, x2, x3, x4, x6) U3_GA(x1, x2, x3, x4, x5, x6, x7, x8, x9) = U3_GA(x1, x2, x3, x4, x5, x6, x7, x9) 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: FLATA_IN_GA(tree(X1, niltree, X2), cons(X1, X3)) -> U1_GA(X1, X2, X3, flatA_in_ga(X2, X3)) FLATA_IN_GA(tree(X1, niltree, X2), cons(X1, X3)) -> FLATA_IN_GA(X2, X3) FLATA_IN_GA(tree(X1, tree(X2, niltree, X3), X4), cons(X2, X5)) -> U2_GA(X1, X2, X3, X4, X5, flatA_in_ga(tree(X1, X3, X4), X5)) FLATA_IN_GA(tree(X1, tree(X2, niltree, X3), X4), cons(X2, X5)) -> FLATA_IN_GA(tree(X1, X3, X4), X5) FLATA_IN_GA(tree(X1, tree(X2, tree(X3, X4, X5), X6), X7), X8) -> U3_GA(X1, X2, X3, X4, X5, X6, X7, X8, flatA_in_ga(tree(X3, X4, tree(X2, X5, tree(X1, X6, X7))), X8)) FLATA_IN_GA(tree(X1, tree(X2, tree(X3, X4, X5), X6), X7), X8) -> FLATA_IN_GA(tree(X3, X4, tree(X2, X5, tree(X1, X6, X7))), X8) R is empty. The argument filtering Pi contains the following mapping: flatA_in_ga(x1, x2) = flatA_in_ga(x1) tree(x1, x2, x3) = tree(x1, x2, x3) niltree = niltree cons(x1, x2) = cons(x1, x2) FLATA_IN_GA(x1, x2) = FLATA_IN_GA(x1) U1_GA(x1, x2, x3, x4) = U1_GA(x1, x2, x4) U2_GA(x1, x2, x3, x4, x5, x6) = U2_GA(x1, x2, x3, x4, x6) U3_GA(x1, x2, x3, x4, x5, x6, x7, x8, x9) = U3_GA(x1, x2, x3, x4, x5, x6, x7, x9) We have to consider all (P,R,Pi)-chains ---------------------------------------- (5) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LOPSTR] contains 1 SCC with 3 less nodes. ---------------------------------------- (6) Obligation: Pi DP problem: The TRS P consists of the following rules: FLATA_IN_GA(tree(X1, tree(X2, niltree, X3), X4), cons(X2, X5)) -> FLATA_IN_GA(tree(X1, X3, X4), X5) FLATA_IN_GA(tree(X1, niltree, X2), cons(X1, X3)) -> FLATA_IN_GA(X2, X3) FLATA_IN_GA(tree(X1, tree(X2, tree(X3, X4, X5), X6), X7), X8) -> FLATA_IN_GA(tree(X3, X4, tree(X2, X5, tree(X1, X6, X7))), X8) R is empty. The argument filtering Pi contains the following mapping: tree(x1, x2, x3) = tree(x1, x2, x3) niltree = niltree cons(x1, x2) = cons(x1, x2) FLATA_IN_GA(x1, x2) = FLATA_IN_GA(x1) 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: FLATA_IN_GA(tree(X1, tree(X2, niltree, X3), X4)) -> FLATA_IN_GA(tree(X1, X3, X4)) FLATA_IN_GA(tree(X1, niltree, X2)) -> FLATA_IN_GA(X2) FLATA_IN_GA(tree(X1, tree(X2, tree(X3, X4, X5), X6), X7)) -> FLATA_IN_GA(tree(X3, X4, tree(X2, X5, tree(X1, X6, X7)))) R is empty. Q is empty. We have to consider all (P,Q,R)-chains. ---------------------------------------- (9) UsableRulesReductionPairsProof (EQUIVALENT) By using the usable rules with reduction pair processor [LPAR04] with a polynomial ordering [POLO], all dependency pairs and the corresponding usable rules [FROCOS05] can be oriented non-strictly. All non-usable rules are removed, and those dependency pairs and usable rules that have been oriented strictly or contain non-usable symbols in their left-hand side are removed as well. The following dependency pairs can be deleted: FLATA_IN_GA(tree(X1, tree(X2, niltree, X3), X4)) -> FLATA_IN_GA(tree(X1, X3, X4)) FLATA_IN_GA(tree(X1, niltree, X2)) -> FLATA_IN_GA(X2) No rules are removed from R. Used ordering: POLO with Polynomial interpretation [POLO]: POL(FLATA_IN_GA(x_1)) = 2*x_1 POL(niltree) = 0 POL(tree(x_1, x_2, x_3)) = 2*x_1 + x_2 + x_3 ---------------------------------------- (10) Obligation: Q DP problem: The TRS P consists of the following rules: FLATA_IN_GA(tree(X1, tree(X2, tree(X3, X4, X5), X6), X7)) -> FLATA_IN_GA(tree(X3, X4, tree(X2, X5, tree(X1, X6, X7)))) R is empty. Q is empty. We have to consider all (P,Q,R)-chains. ---------------------------------------- (11) 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: FLATA_IN_GA(tree(X1, tree(X2, tree(X3, X4, X5), X6), X7)) -> FLATA_IN_GA(tree(X3, X4, tree(X2, X5, tree(X1, X6, X7)))) Used ordering: Polynomial interpretation [POLO]: POL(FLATA_IN_GA(x_1)) = 2*x_1 POL(tree(x_1, x_2, x_3)) = 2 + 2*x_1 + 2*x_2 + x_3 ---------------------------------------- (12) Obligation: Q DP problem: P is empty. R is empty. Q is empty. We have to consider all (P,Q,R)-chains. ---------------------------------------- (13) PisEmptyProof (EQUIVALENT) The TRS P is empty. Hence, there is no (P,Q,R) chain. ---------------------------------------- (14) YES