/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 mergesort(g,a) w.r.t. the given Prolog program could successfully be proven: (0) Prolog (1) PrologToDTProblemTransformerProof [SOUND, 50 ms] (2) TRIPLES (3) TriplesToPiDPProof [SOUND, 3 ms] (4) PiDP (5) DependencyGraphProof [EQUIVALENT, 0 ms] (6) AND (7) PiDP (8) UsableRulesProof [EQUIVALENT, 0 ms] (9) PiDP (10) PiDPToQDPProof [EQUIVALENT, 0 ms] (11) QDP (12) QDPSizeChangeProof [EQUIVALENT, 0 ms] (13) YES (14) PiDP (15) UsableRulesProof [EQUIVALENT, 0 ms] (16) PiDP (17) PiDPToQDPProof [EQUIVALENT, 0 ms] (18) QDP (19) QDPSizeChangeProof [EQUIVALENT, 0 ms] (20) YES (21) PiDP (22) UsableRulesProof [EQUIVALENT, 0 ms] (23) PiDP (24) PiDPToQDPProof [SOUND, 0 ms] (25) QDP (26) MRRProof [EQUIVALENT, 19 ms] (27) QDP (28) MRRProof [EQUIVALENT, 24 ms] (29) QDP (30) DependencyGraphProof [EQUIVALENT, 0 ms] (31) QDP (32) UsableRulesProof [EQUIVALENT, 0 ms] (33) QDP (34) QReductionProof [EQUIVALENT, 0 ms] (35) QDP (36) QDPSizeChangeProof [EQUIVALENT, 0 ms] (37) YES (38) PiDP (39) UsableRulesProof [EQUIVALENT, 0 ms] (40) PiDP (41) PiDPToQDPProof [SOUND, 0 ms] (42) QDP (43) QDPSizeChangeProof [EQUIVALENT, 0 ms] (44) YES (45) PiDP (46) UsableRulesProof [EQUIVALENT, 0 ms] (47) PiDP (48) PiDPToQDPProof [SOUND, 0 ms] (49) QDP (50) QDPOrderProof [EQUIVALENT, 919 ms] (51) QDP (52) PisEmptyProof [EQUIVALENT, 0 ms] (53) YES ---------------------------------------- (0) Obligation: Clauses: mergesort([], []). mergesort(.(X, []), .(X, [])). mergesort(.(X, .(Y, L1)), L2) :- ','(split2(.(X, .(Y, L1)), L3, L4), ','(mergesort(L3, L5), ','(mergesort(L4, L6), merge(L5, L6, L2)))). split(L1, L2, L3) :- split0(L1, L2, L3). split(L1, L2, L3) :- split1(L1, L2, L3). split(L1, L2, L3) :- split2(L1, L2, L3). split0([], [], []). split1(.(X, []), .(X, []), []). split2(.(X, .(Y, L1)), .(X, L2), .(Y, L3)) :- split(L1, L2, L3). merge([], L1, L1). merge(L1, [], L1). merge(.(X, L1), .(Y, L2), .(X, L3)) :- ','(le(X, Y), merge(L1, .(Y, L2), L3)). merge(.(X, L1), .(Y, L2), .(Y, L3)) :- ','(gt(X, Y), merge(.(X, L1), L2, L3)). gt(s(X), s(Y)) :- gt(X, Y). gt(s(X), 0). le(s(X), s(Y)) :- le(X, Y). le(0, s(Y)). le(0, 0). Query: mergesort(g,a) ---------------------------------------- (1) PrologToDTProblemTransformerProof (SOUND) Built DT problem from termination graph DT10. { "root": 2, "program": { "directives": [], "clauses": [ [ "(mergesort ([]) ([]))", null ], [ "(mergesort (. X ([])) (. X ([])))", null ], [ "(mergesort (. X (. Y L1)) L2)", "(',' (split2 (. X (. Y L1)) L3 L4) (',' (mergesort L3 L5) (',' (mergesort L4 L6) (merge L5 L6 L2))))" ], [ "(split L1 L2 L3)", "(split0 L1 L2 L3)" ], [ "(split L1 L2 L3)", "(split1 L1 L2 L3)" ], [ "(split L1 L2 L3)", "(split2 L1 L2 L3)" ], [ "(split0 ([]) ([]) ([]))", null ], [ "(split1 (. X ([])) (. X ([])) ([]))", null ], [ "(split2 (. X (. Y L1)) (. X L2) (. Y L3))", "(split L1 L2 L3)" ], [ "(merge ([]) L1 L1)", null ], [ "(merge L1 ([]) L1)", null ], [ "(merge (. X L1) (. Y L2) (. X L3))", "(',' (le X Y) (merge L1 (. Y L2) L3))" ], [ "(merge (. X L1) (. Y L2) (. Y L3))", "(',' (gt X Y) (merge (. X L1) L2 L3))" ], [ "(gt (s X) (s Y))", "(gt X Y)" ], [ "(gt (s X) (0))", null ], [ "(le (s X) (s Y))", "(le X Y)" ], [ "(le (0) (s Y))", null ], [ "(le (0) (0))", null ] ] }, "graph": { "nodes": { "type": "Nodes", "150": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "151": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "152": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "196": { "goal": [{ "clause": -1, "scope": -1, "term": "(split T59 X161 X162)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T59"], "free": [ "X161", "X162" ], "exprvars": [] } }, "153": { "goal": [{ "clause": -1, "scope": -1, "term": "(split2 T47 X133 X134)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T47"], "free": [ "X133", "X134" ], "exprvars": [] } }, "154": { "goal": [{ "clause": 8, "scope": 6, "term": "(split2 T47 X133 X134)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T47"], "free": [ "X133", "X134" ], "exprvars": [] } }, "510": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "511": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "830": { "goal": [ { "clause": 15, "scope": 8, "term": "(le T95 T97)" }, { "clause": 16, "scope": 8, "term": "(le T95 T97)" }, { "clause": 17, "scope": 8, "term": "(le T95 T97)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T95", "T97" ], "free": [], "exprvars": [] } }, "237": { "goal": [{ "clause": -1, "scope": -1, "term": "(mergesort (. T22 T26) X22)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T22", "T26" ], "free": ["X22"], "exprvars": [] } }, "238": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (mergesort (. T23 T27) X23) (merge T61 X23 T14))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T23", "T27", "T61" ], "free": ["X23"], "exprvars": [] } }, "832": { "goal": [{ "clause": 15, "scope": 8, "term": "(le T95 T97)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T95", "T97" ], "free": [], "exprvars": [] } }, "559": { "goal": [{ "clause": 11, "scope": 7, "term": "(merge T61 T62 T14)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T61", "T62" ], "free": [], "exprvars": [] } }, "834": { "goal": [ { "clause": 16, "scope": 8, "term": "(le T95 T97)" }, { "clause": 17, "scope": 8, "term": "(le T95 T97)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T95", "T97" ], "free": [], "exprvars": [] } }, "835": { "goal": [{ "clause": -1, "scope": -1, "term": "(le T113 T114)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T113", "T114" ], "free": [], "exprvars": [] } }, "836": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "13": { "goal": [ { "clause": -1, "scope": -1, "term": "(true)" }, { "clause": 1, "scope": 1, "term": "(mergesort ([]) T2)" }, { "clause": 2, "scope": 1, "term": "(mergesort ([]) T2)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "15": { "goal": [ { "clause": 1, "scope": 1, "term": "(mergesort T1 T2)" }, { "clause": 2, "scope": 1, "term": "(mergesort T1 T2)" } ], "kb": { "nonunifying": [[ "(mergesort T1 T2)", "(mergesort ([]) ([]))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T1"], "free": [], "exprvars": [] } }, "16": { "goal": [ { "clause": 1, "scope": 1, "term": "(mergesort ([]) T2)" }, { "clause": 2, "scope": 1, "term": "(mergesort ([]) T2)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "17": { "goal": [{ "clause": 2, "scope": 1, "term": "(mergesort ([]) T2)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "482": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "560": { "goal": [{ "clause": 12, "scope": 7, "term": "(merge T61 T62 T14)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T61", "T62" ], "free": [], "exprvars": [] } }, "2": { "goal": [{ "clause": -1, "scope": -1, "term": "(mergesort T1 T2)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T1"], "free": [], "exprvars": [] } }, "486": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "488": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "5": { "goal": [ { "clause": 0, "scope": 1, "term": "(mergesort T1 T2)" }, { "clause": 1, "scope": 1, "term": "(mergesort T1 T2)" }, { "clause": 2, "scope": 1, "term": "(mergesort T1 T2)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T1"], "free": [], "exprvars": [] } }, "445": { "goal": [{ "clause": 9, "scope": 7, "term": "(merge T61 T62 T14)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T61", "T62" ], "free": [], "exprvars": [] } }, "566": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (le T95 T97) (merge T96 (. T97 T98) T100))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T95", "T96", "T97", "T98" ], "free": [], "exprvars": [] } }, "447": { "goal": [ { "clause": 10, "scope": 7, "term": "(merge T61 T62 T14)" }, { "clause": 11, "scope": 7, "term": "(merge T61 T62 T14)" }, { "clause": 12, "scope": 7, "term": "(merge T61 T62 T14)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T61", "T62" ], "free": [], "exprvars": [] } }, "129": { "goal": [{ "clause": -1, "scope": -1, "term": "(split T24 X48 X49)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T24"], "free": [ "X48", "X49" ], "exprvars": [] } }, "569": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "888": { "goal": [{ "clause": -1, "scope": -1, "term": "(gt T154 T155)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T154", "T155" ], "free": [], "exprvars": [] } }, "207": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "889": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "848": { "goal": [{ "clause": 16, "scope": 8, "term": "(le T95 T97)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T95", "T97" ], "free": [], "exprvars": [] } }, "849": { "goal": [{ "clause": 17, "scope": 8, "term": "(le T95 T97)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T95", "T97" ], "free": [], "exprvars": [] } }, "20": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "24": { "goal": [ { "clause": -1, "scope": -1, "term": "(true)" }, { "clause": 2, "scope": 1, "term": "(mergesort (. T4 ([])) T2)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T4"], "free": [], "exprvars": [] } }, "26": { "goal": [{ "clause": 2, "scope": 1, "term": "(mergesort T1 T2)" }], "kb": { "nonunifying": [ [ "(mergesort T1 T2)", "(mergesort ([]) ([]))" ], [ "(mergesort T1 T2)", "(mergesort (. X7 ([])) (. X7 ([])))" ] ], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T1"], "free": ["X7"], "exprvars": [] } }, "28": { "goal": [{ "clause": 2, "scope": 1, "term": "(mergesort (. T4 ([])) T2)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T4"], "free": [], "exprvars": [] } }, "130": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (mergesort (. T22 T26) X22) (',' (mergesort (. T23 T27) X23) (merge X22 X23 T14)))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T22", "T23", "T26", "T27" ], "free": [ "X22", "X23" ], "exprvars": [] } }, "890": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "132": { "goal": [ { "clause": 3, "scope": 3, "term": "(split T24 X48 X49)" }, { "clause": 4, "scope": 3, "term": "(split T24 X48 X49)" }, { "clause": 5, "scope": 3, "term": "(split T24 X48 X49)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T24"], "free": [ "X48", "X49" ], "exprvars": [] } }, "891": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "892": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "136": { "goal": [{ "clause": 3, "scope": 3, "term": "(split T24 X48 X49)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T24"], "free": [ "X48", "X49" ], "exprvars": [] } }, "851": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "137": { "goal": [ { "clause": 4, "scope": 3, "term": "(split T24 X48 X49)" }, { "clause": 5, "scope": 3, "term": "(split T24 X48 X49)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T24"], "free": [ "X48", "X49" ], "exprvars": [] } }, "852": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "853": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "338": { "goal": [{ "clause": -1, "scope": -1, "term": "(mergesort (. T23 T27) X23)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T23", "T27" ], "free": ["X23"], "exprvars": [] } }, "415": { "goal": [ { "clause": 9, "scope": 7, "term": "(merge T61 T62 T14)" }, { "clause": 10, "scope": 7, "term": "(merge T61 T62 T14)" }, { "clause": 11, "scope": 7, "term": "(merge T61 T62 T14)" }, { "clause": 12, "scope": 7, "term": "(merge T61 T62 T14)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T61", "T62" ], "free": [], "exprvars": [] } }, "856": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "857": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "858": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "859": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (gt T136 T138) (merge (. T136 T137) T139 T141))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T136", "T137", "T138", "T139" ], "free": [], "exprvars": [] } }, "30": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "38": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (split2 (. T10 (. T11 T12)) X20 X21) (',' (mergesort X20 X22) (',' (mergesort X21 X23) (merge X22 X23 T14))))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T10", "T11", "T12" ], "free": [ "X20", "X21", "X22", "X23" ], "exprvars": [] } }, "39": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "141": { "goal": [{ "clause": -1, "scope": -1, "term": "(split0 T33 X83 X84)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T33"], "free": [ "X83", "X84" ], "exprvars": [] } }, "142": { "goal": [{ "clause": 6, "scope": 4, "term": "(split0 T33 X83 X84)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T33"], "free": [ "X83", "X84" ], "exprvars": [] } }, "340": { "goal": [{ "clause": -1, "scope": -1, "term": "(merge T61 T62 T14)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T61", "T62" ], "free": [], "exprvars": [] } }, "143": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "144": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "145": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "860": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "146": { "goal": [{ "clause": 4, "scope": 3, "term": "(split T24 X48 X49)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T24"], "free": [ "X48", "X49" ], "exprvars": [] } }, "861": { "goal": [{ "clause": -1, "scope": -1, "term": "(gt T136 T138)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T136", "T138" ], "free": [], "exprvars": [] } }, "147": { "goal": [{ "clause": 5, "scope": 3, "term": "(split T24 X48 X49)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T24"], "free": [ "X48", "X49" ], "exprvars": [] } }, "862": { "goal": [{ "clause": -1, "scope": -1, "term": "(merge (. T136 T137) T139 T141)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T136", "T137", "T139" ], "free": [], "exprvars": [] } }, "148": { "goal": [{ "clause": -1, "scope": -1, "term": "(split1 T38 X108 X109)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T38"], "free": [ "X108", "X109" ], "exprvars": [] } }, "863": { "goal": [ { "clause": 13, "scope": 9, "term": "(gt T136 T138)" }, { "clause": 14, "scope": 9, "term": "(gt T136 T138)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T136", "T138" ], "free": [], "exprvars": [] } }, "149": { "goal": [{ "clause": 7, "scope": 5, "term": "(split1 T38 X108 X109)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T38"], "free": [ "X108", "X109" ], "exprvars": [] } }, "865": { "goal": [{ "clause": 13, "scope": 9, "term": "(gt T136 T138)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T136", "T138" ], "free": [], "exprvars": [] } }, "866": { "goal": [{ "clause": 14, "scope": 9, "term": "(gt T136 T138)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T136", "T138" ], "free": [], "exprvars": [] } }, "506": { "goal": [{ "clause": 10, "scope": 7, "term": "(merge T61 T62 T14)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T61", "T62" ], "free": [], "exprvars": [] } }, "40": { "goal": [{ "clause": 8, "scope": 2, "term": "(',' (split2 (. T10 (. T11 T12)) X20 X21) (',' (mergesort X20 X22) (',' (mergesort X21 X23) (merge X22 X23 T14))))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T10", "T11", "T12" ], "free": [ "X20", "X21", "X22", "X23" ], "exprvars": [] } }, "508": { "goal": [ { "clause": 11, "scope": 7, "term": "(merge T61 T62 T14)" }, { "clause": 12, "scope": 7, "term": "(merge T61 T62 T14)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T61", "T62" ], "free": [], "exprvars": [] } }, "827": { "goal": [{ "clause": -1, "scope": -1, "term": "(le T95 T97)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T95", "T97" ], "free": [], "exprvars": [] } }, "509": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "828": { "goal": [{ "clause": -1, "scope": -1, "term": "(merge T96 (. T97 T98) T100)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T96", "T97", "T98" ], "free": [], "exprvars": [] } }, "43": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (split T24 X48 X49) (',' (mergesort (. T22 X48) X22) (',' (mergesort (. T23 X49) X23) (merge X22 X23 T14))))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T22", "T23", "T24" ], "free": [ "X22", "X23", "X48", "X49" ], "exprvars": [] } } }, "edges": [ { "from": 2, "to": 5, "label": "CASE" }, { "from": 5, "to": 13, "label": "EVAL with clause\nmergesort([], []).\nand substitutionT1 -> [],\nT2 -> []" }, { "from": 5, "to": 15, "label": "EVAL-BACKTRACK" }, { "from": 13, "to": 16, "label": "SUCCESS" }, { "from": 15, "to": 24, "label": "EVAL with clause\nmergesort(.(X7, []), .(X7, [])).\nand substitutionX7 -> T4,\nT1 -> .(T4, []),\nT2 -> .(T4, [])" }, { "from": 15, "to": 26, "label": "EVAL-BACKTRACK" }, { "from": 16, "to": 17, "label": "BACKTRACK\nfor clause: mergesort(.(X, []), .(X, []))because of non-unification" }, { "from": 17, "to": 20, "label": "BACKTRACK\nfor clause: mergesort(.(X, .(Y, L1)), L2) :- ','(split2(.(X, .(Y, L1)), L3, L4), ','(mergesort(L3, L5), ','(mergesort(L4, L6), merge(L5, L6, L2))))because of non-unification" }, { "from": 24, "to": 28, "label": "SUCCESS" }, { "from": 26, "to": 38, "label": "EVAL with clause\nmergesort(.(X16, .(X17, X18)), X19) :- ','(split2(.(X16, .(X17, X18)), X20, X21), ','(mergesort(X20, X22), ','(mergesort(X21, X23), merge(X22, X23, X19)))).\nand substitutionX16 -> T10,\nX17 -> T11,\nX18 -> T12,\nT1 -> .(T10, .(T11, T12)),\nT2 -> T14,\nX19 -> T14,\nT13 -> T14" }, { "from": 26, "to": 39, "label": "EVAL-BACKTRACK" }, { "from": 28, "to": 30, "label": "BACKTRACK\nfor clause: mergesort(.(X, .(Y, L1)), L2) :- ','(split2(.(X, .(Y, L1)), L3, L4), ','(mergesort(L3, L5), ','(mergesort(L4, L6), merge(L5, L6, L2))))because of non-unification" }, { "from": 38, "to": 40, "label": "CASE" }, { "from": 40, "to": 43, "label": "ONLY EVAL with clause\nsplit2(.(X43, .(X44, X45)), .(X43, X46), .(X44, X47)) :- split(X45, X46, X47).\nand substitutionT10 -> T22,\nX43 -> T22,\nT11 -> T23,\nX44 -> T23,\nT12 -> T24,\nX45 -> T24,\nX46 -> X48,\nX20 -> .(T22, X48),\nX47 -> X49,\nX21 -> .(T23, X49)" }, { "from": 43, "to": 129, "label": "SPLIT 1" }, { "from": 43, "to": 130, "label": "SPLIT 2\nnew knowledge:\nT24 is ground\nT26 is ground\nT27 is ground\nreplacements:X48 -> T26,\nX49 -> T27" }, { "from": 129, "to": 132, "label": "CASE" }, { "from": 130, "to": 237, "label": "SPLIT 1" }, { "from": 130, "to": 238, "label": "SPLIT 2\nnew knowledge:\nT22 is ground\nT26 is ground\nT61 is ground\nreplacements:X22 -> T61" }, { "from": 132, "to": 136, "label": "PARALLEL" }, { "from": 132, "to": 137, "label": "PARALLEL" }, { "from": 136, "to": 141, "label": "ONLY EVAL with clause\nsplit(X80, X81, X82) :- split0(X80, X81, X82).\nand substitutionT24 -> T33,\nX80 -> T33,\nX48 -> X83,\nX81 -> X83,\nX49 -> X84,\nX82 -> X84" }, { "from": 137, "to": 146, "label": "PARALLEL" }, { "from": 137, "to": 147, "label": "PARALLEL" }, { "from": 141, "to": 142, "label": "CASE" }, { "from": 142, "to": 143, "label": "EVAL with clause\nsplit0([], [], []).\nand substitutionT33 -> [],\nX83 -> [],\nX84 -> []" }, { "from": 142, "to": 144, "label": "EVAL-BACKTRACK" }, { "from": 143, "to": 145, "label": "SUCCESS" }, { "from": 146, "to": 148, "label": "ONLY EVAL with clause\nsplit(X105, X106, X107) :- split1(X105, X106, X107).\nand substitutionT24 -> T38,\nX105 -> T38,\nX48 -> X108,\nX106 -> X108,\nX49 -> X109,\nX107 -> X109" }, { "from": 147, "to": 153, "label": "ONLY EVAL with clause\nsplit(X130, X131, X132) :- split2(X130, X131, X132).\nand substitutionT24 -> T47,\nX130 -> T47,\nX48 -> X133,\nX131 -> X133,\nX49 -> X134,\nX132 -> X134" }, { "from": 148, "to": 149, "label": "CASE" }, { "from": 149, "to": 150, "label": "EVAL with clause\nsplit1(.(X112, []), .(X112, []), []).\nand substitutionX112 -> T41,\nT38 -> .(T41, []),\nX108 -> .(T41, []),\nX109 -> []" }, { "from": 149, "to": 151, "label": "EVAL-BACKTRACK" }, { "from": 150, "to": 152, "label": "SUCCESS" }, { "from": 153, "to": 154, "label": "CASE" }, { "from": 154, "to": 196, "label": "EVAL with clause\nsplit2(.(X156, .(X157, X158)), .(X156, X159), .(X157, X160)) :- split(X158, X159, X160).\nand substitutionX156 -> T57,\nX157 -> T58,\nX158 -> T59,\nT47 -> .(T57, .(T58, T59)),\nX159 -> X161,\nX133 -> .(T57, X161),\nX160 -> X162,\nX134 -> .(T58, X162)" }, { "from": 154, "to": 207, "label": "EVAL-BACKTRACK" }, { "from": 196, "to": 129, "label": "INSTANCE with matching:\nT24 -> T59\nX48 -> X161\nX49 -> X162" }, { "from": 237, "to": 2, "label": "INSTANCE with matching:\nT1 -> .(T22, T26)\nT2 -> X22" }, { "from": 238, "to": 338, "label": "SPLIT 1" }, { "from": 238, "to": 340, "label": "SPLIT 2\nnew knowledge:\nT23 is ground\nT27 is ground\nT62 is ground\nreplacements:X23 -> T62" }, { "from": 338, "to": 2, "label": "INSTANCE with matching:\nT1 -> .(T23, T27)\nT2 -> X23" }, { "from": 340, "to": 415, "label": "CASE" }, { "from": 415, "to": 445, "label": "PARALLEL" }, { "from": 415, "to": 447, "label": "PARALLEL" }, { "from": 445, "to": 482, "label": "EVAL with clause\nmerge([], X174, X174).\nand substitutionT61 -> [],\nT62 -> T69,\nX174 -> T69,\nT14 -> T69" }, { "from": 445, "to": 486, "label": "EVAL-BACKTRACK" }, { "from": 447, "to": 506, "label": "PARALLEL" }, { "from": 447, "to": 508, "label": "PARALLEL" }, { "from": 482, "to": 488, "label": "SUCCESS" }, { "from": 506, "to": 509, "label": "EVAL with clause\nmerge(X179, [], X179).\nand substitutionT61 -> T74,\nX179 -> T74,\nT62 -> [],\nT14 -> T74" }, { "from": 506, "to": 510, "label": "EVAL-BACKTRACK" }, { "from": 508, "to": 559, "label": "PARALLEL" }, { "from": 508, "to": 560, "label": "PARALLEL" }, { "from": 509, "to": 511, "label": "SUCCESS" }, { "from": 559, "to": 566, "label": "EVAL with clause\nmerge(.(X200, X201), .(X202, X203), .(X200, X204)) :- ','(le(X200, X202), merge(X201, .(X202, X203), X204)).\nand substitutionX200 -> T95,\nX201 -> T96,\nT61 -> .(T95, T96),\nX202 -> T97,\nX203 -> T98,\nT62 -> .(T97, T98),\nX204 -> T100,\nT14 -> .(T95, T100),\nT99 -> T100" }, { "from": 559, "to": 569, "label": "EVAL-BACKTRACK" }, { "from": 560, "to": 859, "label": "EVAL with clause\nmerge(.(X238, X239), .(X240, X241), .(X240, X242)) :- ','(gt(X238, X240), merge(.(X238, X239), X241, X242)).\nand substitutionX238 -> T136,\nX239 -> T137,\nT61 -> .(T136, T137),\nX240 -> T138,\nX241 -> T139,\nT62 -> .(T138, T139),\nX242 -> T141,\nT14 -> .(T138, T141),\nT140 -> T141" }, { "from": 560, "to": 860, "label": "EVAL-BACKTRACK" }, { "from": 566, "to": 827, "label": "SPLIT 1" }, { "from": 566, "to": 828, "label": "SPLIT 2\nnew knowledge:\nT95 is ground\nT97 is ground" }, { "from": 827, "to": 830, "label": "CASE" }, { "from": 828, "to": 340, "label": "INSTANCE with matching:\nT61 -> T96\nT62 -> .(T97, T98)\nT14 -> T100" }, { "from": 830, "to": 832, "label": "PARALLEL" }, { "from": 830, "to": 834, "label": "PARALLEL" }, { "from": 832, "to": 835, "label": "EVAL with clause\nle(s(X217), s(X218)) :- le(X217, X218).\nand substitutionX217 -> T113,\nT95 -> s(T113),\nX218 -> T114,\nT97 -> s(T114)" }, { "from": 832, "to": 836, "label": "EVAL-BACKTRACK" }, { "from": 834, "to": 848, "label": "PARALLEL" }, { "from": 834, "to": 849, "label": "PARALLEL" }, { "from": 835, "to": 827, "label": "INSTANCE with matching:\nT95 -> T113\nT97 -> T114" }, { "from": 848, "to": 851, "label": "EVAL with clause\nle(0, s(X225)).\nand substitutionT95 -> 0,\nX225 -> T121,\nT97 -> s(T121)" }, { "from": 848, "to": 852, "label": "EVAL-BACKTRACK" }, { "from": 849, "to": 856, "label": "EVAL with clause\nle(0, 0).\nand substitutionT95 -> 0,\nT97 -> 0" }, { "from": 849, "to": 857, "label": "EVAL-BACKTRACK" }, { "from": 851, "to": 853, "label": "SUCCESS" }, { "from": 856, "to": 858, "label": "SUCCESS" }, { "from": 859, "to": 861, "label": "SPLIT 1" }, { "from": 859, "to": 862, "label": "SPLIT 2\nnew knowledge:\nT136 is ground\nT138 is ground" }, { "from": 861, "to": 863, "label": "CASE" }, { "from": 862, "to": 340, "label": "INSTANCE with matching:\nT61 -> .(T136, T137)\nT62 -> T139\nT14 -> T141" }, { "from": 863, "to": 865, "label": "PARALLEL" }, { "from": 863, "to": 866, "label": "PARALLEL" }, { "from": 865, "to": 888, "label": "EVAL with clause\ngt(s(X255), s(X256)) :- gt(X255, X256).\nand substitutionX255 -> T154,\nT136 -> s(T154),\nX256 -> T155,\nT138 -> s(T155)" }, { "from": 865, "to": 889, "label": "EVAL-BACKTRACK" }, { "from": 866, "to": 890, "label": "EVAL with clause\ngt(s(X261), 0).\nand substitutionX261 -> T160,\nT136 -> s(T160),\nT138 -> 0" }, { "from": 866, "to": 891, "label": "EVAL-BACKTRACK" }, { "from": 888, "to": 861, "label": "INSTANCE with matching:\nT136 -> T154\nT138 -> T155" }, { "from": 890, "to": 892, "label": "SUCCESS" } ], "type": "Graph" } } ---------------------------------------- (2) Obligation: Triples: splitA(.(X1, .(X2, X3)), .(X1, X4), .(X2, X5)) :- splitA(X3, X4, X5). mergeC(.(X1, X2), .(X3, X4), .(X1, X5)) :- leD(X1, X3). mergeC(.(X1, X2), .(X3, X4), .(X1, X5)) :- ','(lecD(X1, X3), mergeC(X2, .(X3, X4), X5)). mergeC(.(X1, X2), .(X3, X4), .(X3, X5)) :- gtE(X1, X3). mergeC(.(X1, X2), .(X3, X4), .(X3, X5)) :- ','(gtcE(X1, X3), mergeC(.(X1, X2), X4, X5)). leD(s(X1), s(X2)) :- leD(X1, X2). gtE(s(X1), s(X2)) :- gtE(X1, X2). mergesortB(.(X1, .(X2, X3)), X4) :- splitA(X3, X5, X6). mergesortB(.(X1, .(X2, X3)), X4) :- ','(splitcA(X3, X5, X6), mergesortB(.(X1, X5), X7)). mergesortB(.(X1, .(X2, X3)), X4) :- ','(splitcA(X3, X5, X6), ','(mergesortcB(.(X1, X5), X7), mergesortB(.(X2, X6), X8))). mergesortB(.(X1, .(X2, X3)), X4) :- ','(splitcA(X3, X5, X6), ','(mergesortcB(.(X1, X5), X7), ','(mergesortcB(.(X2, X6), X8), mergeC(X7, X8, X4)))). Clauses: splitcA([], [], []). splitcA(.(X1, []), .(X1, []), []). splitcA(.(X1, .(X2, X3)), .(X1, X4), .(X2, X5)) :- splitcA(X3, X4, X5). mergesortcB([], []). mergesortcB(.(X1, []), .(X1, [])). mergesortcB(.(X1, .(X2, X3)), X4) :- ','(splitcA(X3, X5, X6), ','(mergesortcB(.(X1, X5), X7), ','(mergesortcB(.(X2, X6), X8), mergecC(X7, X8, X4)))). mergecC([], X1, X1). mergecC(X1, [], X1). mergecC(.(X1, X2), .(X3, X4), .(X1, X5)) :- ','(lecD(X1, X3), mergecC(X2, .(X3, X4), X5)). mergecC(.(X1, X2), .(X3, X4), .(X3, X5)) :- ','(gtcE(X1, X3), mergecC(.(X1, X2), X4, X5)). lecD(s(X1), s(X2)) :- lecD(X1, X2). lecD(0, s(X1)). lecD(0, 0). gtcE(s(X1), s(X2)) :- gtcE(X1, X2). gtcE(s(X1), 0). Afs: mergesortB(x1, x2) = mergesortB(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: mergesortB_in_2: (b,f) splitA_in_3: (b,f,f) splitcA_in_3: (b,f,f) mergesortcB_in_2: (b,f) mergecC_in_3: (b,b,f) lecD_in_2: (b,b) gtcE_in_2: (b,b) mergeC_in_3: (b,b,f) leD_in_2: (b,b) gtE_in_2: (b,b) Transforming TRIPLES into the following Term Rewriting System: Pi DP problem: The TRS P consists of the following rules: MERGESORTB_IN_GA(.(X1, .(X2, X3)), X4) -> U10_GA(X1, X2, X3, X4, splitA_in_gaa(X3, X5, X6)) MERGESORTB_IN_GA(.(X1, .(X2, X3)), X4) -> SPLITA_IN_GAA(X3, X5, X6) SPLITA_IN_GAA(.(X1, .(X2, X3)), .(X1, X4), .(X2, X5)) -> U1_GAA(X1, X2, X3, X4, X5, splitA_in_gaa(X3, X4, X5)) SPLITA_IN_GAA(.(X1, .(X2, X3)), .(X1, X4), .(X2, X5)) -> SPLITA_IN_GAA(X3, X4, X5) MERGESORTB_IN_GA(.(X1, .(X2, X3)), X4) -> U11_GA(X1, X2, X3, X4, splitcA_in_gaa(X3, X5, X6)) U11_GA(X1, X2, X3, X4, splitcA_out_gaa(X3, X5, X6)) -> U12_GA(X1, X2, X3, X4, mergesortB_in_ga(.(X1, X5), X7)) U11_GA(X1, X2, X3, X4, splitcA_out_gaa(X3, X5, X6)) -> MERGESORTB_IN_GA(.(X1, X5), X7) U11_GA(X1, X2, X3, X4, splitcA_out_gaa(X3, X5, X6)) -> U13_GA(X1, X2, X3, X4, X6, mergesortcB_in_ga(.(X1, X5), X7)) U13_GA(X1, X2, X3, X4, X6, mergesortcB_out_ga(.(X1, X5), X7)) -> U14_GA(X1, X2, X3, X4, mergesortB_in_ga(.(X2, X6), X8)) U13_GA(X1, X2, X3, X4, X6, mergesortcB_out_ga(.(X1, X5), X7)) -> MERGESORTB_IN_GA(.(X2, X6), X8) U13_GA(X1, X2, X3, X4, X6, mergesortcB_out_ga(.(X1, X5), X7)) -> U15_GA(X1, X2, X3, X4, X7, mergesortcB_in_ga(.(X2, X6), X8)) U15_GA(X1, X2, X3, X4, X7, mergesortcB_out_ga(.(X2, X6), X8)) -> U16_GA(X1, X2, X3, X4, mergeC_in_gga(X7, X8, X4)) U15_GA(X1, X2, X3, X4, X7, mergesortcB_out_ga(.(X2, X6), X8)) -> MERGEC_IN_GGA(X7, X8, X4) MERGEC_IN_GGA(.(X1, X2), .(X3, X4), .(X1, X5)) -> U2_GGA(X1, X2, X3, X4, X5, leD_in_gg(X1, X3)) MERGEC_IN_GGA(.(X1, X2), .(X3, X4), .(X1, X5)) -> LED_IN_GG(X1, X3) LED_IN_GG(s(X1), s(X2)) -> U8_GG(X1, X2, leD_in_gg(X1, X2)) LED_IN_GG(s(X1), s(X2)) -> LED_IN_GG(X1, X2) MERGEC_IN_GGA(.(X1, X2), .(X3, X4), .(X1, X5)) -> U3_GGA(X1, X2, X3, X4, X5, lecD_in_gg(X1, X3)) U3_GGA(X1, X2, X3, X4, X5, lecD_out_gg(X1, X3)) -> U4_GGA(X1, X2, X3, X4, X5, mergeC_in_gga(X2, .(X3, X4), X5)) U3_GGA(X1, X2, X3, X4, X5, lecD_out_gg(X1, X3)) -> MERGEC_IN_GGA(X2, .(X3, X4), X5) MERGEC_IN_GGA(.(X1, X2), .(X3, X4), .(X3, X5)) -> U5_GGA(X1, X2, X3, X4, X5, gtE_in_gg(X1, X3)) MERGEC_IN_GGA(.(X1, X2), .(X3, X4), .(X3, X5)) -> GTE_IN_GG(X1, X3) GTE_IN_GG(s(X1), s(X2)) -> U9_GG(X1, X2, gtE_in_gg(X1, X2)) GTE_IN_GG(s(X1), s(X2)) -> GTE_IN_GG(X1, X2) MERGEC_IN_GGA(.(X1, X2), .(X3, X4), .(X3, X5)) -> U6_GGA(X1, X2, X3, X4, X5, gtcE_in_gg(X1, X3)) U6_GGA(X1, X2, X3, X4, X5, gtcE_out_gg(X1, X3)) -> U7_GGA(X1, X2, X3, X4, X5, mergeC_in_gga(.(X1, X2), X4, X5)) U6_GGA(X1, X2, X3, X4, X5, gtcE_out_gg(X1, X3)) -> MERGEC_IN_GGA(.(X1, X2), X4, X5) The TRS R consists of the following rules: splitcA_in_gaa([], [], []) -> splitcA_out_gaa([], [], []) splitcA_in_gaa(.(X1, []), .(X1, []), []) -> splitcA_out_gaa(.(X1, []), .(X1, []), []) splitcA_in_gaa(.(X1, .(X2, X3)), .(X1, X4), .(X2, X5)) -> U18_gaa(X1, X2, X3, X4, X5, splitcA_in_gaa(X3, X4, X5)) U18_gaa(X1, X2, X3, X4, X5, splitcA_out_gaa(X3, X4, X5)) -> splitcA_out_gaa(.(X1, .(X2, X3)), .(X1, X4), .(X2, X5)) mergesortcB_in_ga([], []) -> mergesortcB_out_ga([], []) mergesortcB_in_ga(.(X1, []), .(X1, [])) -> mergesortcB_out_ga(.(X1, []), .(X1, [])) mergesortcB_in_ga(.(X1, .(X2, X3)), X4) -> U19_ga(X1, X2, X3, X4, splitcA_in_gaa(X3, X5, X6)) U19_ga(X1, X2, X3, X4, splitcA_out_gaa(X3, X5, X6)) -> U20_ga(X1, X2, X3, X4, X6, mergesortcB_in_ga(.(X1, X5), X7)) U20_ga(X1, X2, X3, X4, X6, mergesortcB_out_ga(.(X1, X5), X7)) -> U21_ga(X1, X2, X3, X4, X7, mergesortcB_in_ga(.(X2, X6), X8)) U21_ga(X1, X2, X3, X4, X7, mergesortcB_out_ga(.(X2, X6), X8)) -> U22_ga(X1, X2, X3, X4, mergecC_in_gga(X7, X8, X4)) mergecC_in_gga([], X1, X1) -> mergecC_out_gga([], X1, X1) mergecC_in_gga(X1, [], X1) -> mergecC_out_gga(X1, [], X1) mergecC_in_gga(.(X1, X2), .(X3, X4), .(X1, X5)) -> U23_gga(X1, X2, X3, X4, X5, lecD_in_gg(X1, X3)) lecD_in_gg(s(X1), s(X2)) -> U27_gg(X1, X2, lecD_in_gg(X1, X2)) lecD_in_gg(0, s(X1)) -> lecD_out_gg(0, s(X1)) lecD_in_gg(0, 0) -> lecD_out_gg(0, 0) U27_gg(X1, X2, lecD_out_gg(X1, X2)) -> lecD_out_gg(s(X1), s(X2)) U23_gga(X1, X2, X3, X4, X5, lecD_out_gg(X1, X3)) -> U24_gga(X1, X2, X3, X4, X5, mergecC_in_gga(X2, .(X3, X4), X5)) mergecC_in_gga(.(X1, X2), .(X3, X4), .(X3, X5)) -> U25_gga(X1, X2, X3, X4, X5, gtcE_in_gg(X1, X3)) gtcE_in_gg(s(X1), s(X2)) -> U28_gg(X1, X2, gtcE_in_gg(X1, X2)) gtcE_in_gg(s(X1), 0) -> gtcE_out_gg(s(X1), 0) U28_gg(X1, X2, gtcE_out_gg(X1, X2)) -> gtcE_out_gg(s(X1), s(X2)) U25_gga(X1, X2, X3, X4, X5, gtcE_out_gg(X1, X3)) -> U26_gga(X1, X2, X3, X4, X5, mergecC_in_gga(.(X1, X2), X4, X5)) U26_gga(X1, X2, X3, X4, X5, mergecC_out_gga(.(X1, X2), X4, X5)) -> mergecC_out_gga(.(X1, X2), .(X3, X4), .(X3, X5)) U24_gga(X1, X2, X3, X4, X5, mergecC_out_gga(X2, .(X3, X4), X5)) -> mergecC_out_gga(.(X1, X2), .(X3, X4), .(X1, X5)) U22_ga(X1, X2, X3, X4, mergecC_out_gga(X7, X8, X4)) -> mergesortcB_out_ga(.(X1, .(X2, X3)), X4) The argument filtering Pi contains the following mapping: mergesortB_in_ga(x1, x2) = mergesortB_in_ga(x1) .(x1, x2) = .(x1, x2) splitA_in_gaa(x1, x2, x3) = splitA_in_gaa(x1) splitcA_in_gaa(x1, x2, x3) = splitcA_in_gaa(x1) [] = [] splitcA_out_gaa(x1, x2, x3) = splitcA_out_gaa(x1, x2, x3) U18_gaa(x1, x2, x3, x4, x5, x6) = U18_gaa(x1, x2, x3, x6) mergesortcB_in_ga(x1, x2) = mergesortcB_in_ga(x1) mergesortcB_out_ga(x1, x2) = mergesortcB_out_ga(x1, x2) U19_ga(x1, x2, x3, x4, x5) = U19_ga(x1, x2, x3, x5) U20_ga(x1, x2, x3, x4, x5, x6) = U20_ga(x1, x2, x3, x5, x6) U21_ga(x1, x2, x3, x4, x5, x6) = U21_ga(x1, x2, x3, x5, x6) U22_ga(x1, x2, x3, x4, x5) = U22_ga(x1, x2, x3, x5) mergecC_in_gga(x1, x2, x3) = mergecC_in_gga(x1, x2) mergecC_out_gga(x1, x2, x3) = mergecC_out_gga(x1, x2, x3) U23_gga(x1, x2, x3, x4, x5, x6) = U23_gga(x1, x2, x3, x4, x6) lecD_in_gg(x1, x2) = lecD_in_gg(x1, x2) s(x1) = s(x1) U27_gg(x1, x2, x3) = U27_gg(x1, x2, x3) 0 = 0 lecD_out_gg(x1, x2) = lecD_out_gg(x1, x2) U24_gga(x1, x2, x3, x4, x5, x6) = U24_gga(x1, x2, x3, x4, x6) U25_gga(x1, x2, x3, x4, x5, x6) = U25_gga(x1, x2, x3, x4, x6) gtcE_in_gg(x1, x2) = gtcE_in_gg(x1, x2) U28_gg(x1, x2, x3) = U28_gg(x1, x2, x3) gtcE_out_gg(x1, x2) = gtcE_out_gg(x1, x2) U26_gga(x1, x2, x3, x4, x5, x6) = U26_gga(x1, x2, x3, x4, x6) mergeC_in_gga(x1, x2, x3) = mergeC_in_gga(x1, x2) leD_in_gg(x1, x2) = leD_in_gg(x1, x2) gtE_in_gg(x1, x2) = gtE_in_gg(x1, x2) MERGESORTB_IN_GA(x1, x2) = MERGESORTB_IN_GA(x1) U10_GA(x1, x2, x3, x4, x5) = U10_GA(x1, x2, x3, x5) SPLITA_IN_GAA(x1, x2, x3) = SPLITA_IN_GAA(x1) U1_GAA(x1, x2, x3, x4, x5, x6) = U1_GAA(x1, x2, x3, x6) U11_GA(x1, x2, x3, x4, x5) = U11_GA(x1, x2, x3, x5) U12_GA(x1, x2, x3, x4, x5) = U12_GA(x1, x2, x3, x5) U13_GA(x1, x2, x3, x4, x5, x6) = U13_GA(x1, x2, x3, x5, x6) U14_GA(x1, x2, x3, x4, x5) = U14_GA(x1, x2, x3, x5) U15_GA(x1, x2, x3, x4, x5, x6) = U15_GA(x1, x2, x3, x5, x6) U16_GA(x1, x2, x3, x4, x5) = U16_GA(x1, x2, x3, x5) MERGEC_IN_GGA(x1, x2, x3) = MERGEC_IN_GGA(x1, x2) U2_GGA(x1, x2, x3, x4, x5, x6) = U2_GGA(x1, x2, x3, x4, x6) LED_IN_GG(x1, x2) = LED_IN_GG(x1, x2) U8_GG(x1, x2, x3) = U8_GG(x1, x2, x3) U3_GGA(x1, x2, x3, x4, x5, x6) = U3_GGA(x1, x2, x3, x4, x6) U4_GGA(x1, x2, x3, x4, x5, x6) = U4_GGA(x1, x2, x3, x4, x6) U5_GGA(x1, x2, x3, x4, x5, x6) = U5_GGA(x1, x2, x3, x4, x6) GTE_IN_GG(x1, x2) = GTE_IN_GG(x1, x2) U9_GG(x1, x2, x3) = U9_GG(x1, x2, x3) U6_GGA(x1, x2, x3, x4, x5, x6) = U6_GGA(x1, x2, x3, x4, x6) U7_GGA(x1, x2, x3, x4, x5, x6) = U7_GGA(x1, x2, x3, x4, x6) 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: MERGESORTB_IN_GA(.(X1, .(X2, X3)), X4) -> U10_GA(X1, X2, X3, X4, splitA_in_gaa(X3, X5, X6)) MERGESORTB_IN_GA(.(X1, .(X2, X3)), X4) -> SPLITA_IN_GAA(X3, X5, X6) SPLITA_IN_GAA(.(X1, .(X2, X3)), .(X1, X4), .(X2, X5)) -> U1_GAA(X1, X2, X3, X4, X5, splitA_in_gaa(X3, X4, X5)) SPLITA_IN_GAA(.(X1, .(X2, X3)), .(X1, X4), .(X2, X5)) -> SPLITA_IN_GAA(X3, X4, X5) MERGESORTB_IN_GA(.(X1, .(X2, X3)), X4) -> U11_GA(X1, X2, X3, X4, splitcA_in_gaa(X3, X5, X6)) U11_GA(X1, X2, X3, X4, splitcA_out_gaa(X3, X5, X6)) -> U12_GA(X1, X2, X3, X4, mergesortB_in_ga(.(X1, X5), X7)) U11_GA(X1, X2, X3, X4, splitcA_out_gaa(X3, X5, X6)) -> MERGESORTB_IN_GA(.(X1, X5), X7) U11_GA(X1, X2, X3, X4, splitcA_out_gaa(X3, X5, X6)) -> U13_GA(X1, X2, X3, X4, X6, mergesortcB_in_ga(.(X1, X5), X7)) U13_GA(X1, X2, X3, X4, X6, mergesortcB_out_ga(.(X1, X5), X7)) -> U14_GA(X1, X2, X3, X4, mergesortB_in_ga(.(X2, X6), X8)) U13_GA(X1, X2, X3, X4, X6, mergesortcB_out_ga(.(X1, X5), X7)) -> MERGESORTB_IN_GA(.(X2, X6), X8) U13_GA(X1, X2, X3, X4, X6, mergesortcB_out_ga(.(X1, X5), X7)) -> U15_GA(X1, X2, X3, X4, X7, mergesortcB_in_ga(.(X2, X6), X8)) U15_GA(X1, X2, X3, X4, X7, mergesortcB_out_ga(.(X2, X6), X8)) -> U16_GA(X1, X2, X3, X4, mergeC_in_gga(X7, X8, X4)) U15_GA(X1, X2, X3, X4, X7, mergesortcB_out_ga(.(X2, X6), X8)) -> MERGEC_IN_GGA(X7, X8, X4) MERGEC_IN_GGA(.(X1, X2), .(X3, X4), .(X1, X5)) -> U2_GGA(X1, X2, X3, X4, X5, leD_in_gg(X1, X3)) MERGEC_IN_GGA(.(X1, X2), .(X3, X4), .(X1, X5)) -> LED_IN_GG(X1, X3) LED_IN_GG(s(X1), s(X2)) -> U8_GG(X1, X2, leD_in_gg(X1, X2)) LED_IN_GG(s(X1), s(X2)) -> LED_IN_GG(X1, X2) MERGEC_IN_GGA(.(X1, X2), .(X3, X4), .(X1, X5)) -> U3_GGA(X1, X2, X3, X4, X5, lecD_in_gg(X1, X3)) U3_GGA(X1, X2, X3, X4, X5, lecD_out_gg(X1, X3)) -> U4_GGA(X1, X2, X3, X4, X5, mergeC_in_gga(X2, .(X3, X4), X5)) U3_GGA(X1, X2, X3, X4, X5, lecD_out_gg(X1, X3)) -> MERGEC_IN_GGA(X2, .(X3, X4), X5) MERGEC_IN_GGA(.(X1, X2), .(X3, X4), .(X3, X5)) -> U5_GGA(X1, X2, X3, X4, X5, gtE_in_gg(X1, X3)) MERGEC_IN_GGA(.(X1, X2), .(X3, X4), .(X3, X5)) -> GTE_IN_GG(X1, X3) GTE_IN_GG(s(X1), s(X2)) -> U9_GG(X1, X2, gtE_in_gg(X1, X2)) GTE_IN_GG(s(X1), s(X2)) -> GTE_IN_GG(X1, X2) MERGEC_IN_GGA(.(X1, X2), .(X3, X4), .(X3, X5)) -> U6_GGA(X1, X2, X3, X4, X5, gtcE_in_gg(X1, X3)) U6_GGA(X1, X2, X3, X4, X5, gtcE_out_gg(X1, X3)) -> U7_GGA(X1, X2, X3, X4, X5, mergeC_in_gga(.(X1, X2), X4, X5)) U6_GGA(X1, X2, X3, X4, X5, gtcE_out_gg(X1, X3)) -> MERGEC_IN_GGA(.(X1, X2), X4, X5) The TRS R consists of the following rules: splitcA_in_gaa([], [], []) -> splitcA_out_gaa([], [], []) splitcA_in_gaa(.(X1, []), .(X1, []), []) -> splitcA_out_gaa(.(X1, []), .(X1, []), []) splitcA_in_gaa(.(X1, .(X2, X3)), .(X1, X4), .(X2, X5)) -> U18_gaa(X1, X2, X3, X4, X5, splitcA_in_gaa(X3, X4, X5)) U18_gaa(X1, X2, X3, X4, X5, splitcA_out_gaa(X3, X4, X5)) -> splitcA_out_gaa(.(X1, .(X2, X3)), .(X1, X4), .(X2, X5)) mergesortcB_in_ga([], []) -> mergesortcB_out_ga([], []) mergesortcB_in_ga(.(X1, []), .(X1, [])) -> mergesortcB_out_ga(.(X1, []), .(X1, [])) mergesortcB_in_ga(.(X1, .(X2, X3)), X4) -> U19_ga(X1, X2, X3, X4, splitcA_in_gaa(X3, X5, X6)) U19_ga(X1, X2, X3, X4, splitcA_out_gaa(X3, X5, X6)) -> U20_ga(X1, X2, X3, X4, X6, mergesortcB_in_ga(.(X1, X5), X7)) U20_ga(X1, X2, X3, X4, X6, mergesortcB_out_ga(.(X1, X5), X7)) -> U21_ga(X1, X2, X3, X4, X7, mergesortcB_in_ga(.(X2, X6), X8)) U21_ga(X1, X2, X3, X4, X7, mergesortcB_out_ga(.(X2, X6), X8)) -> U22_ga(X1, X2, X3, X4, mergecC_in_gga(X7, X8, X4)) mergecC_in_gga([], X1, X1) -> mergecC_out_gga([], X1, X1) mergecC_in_gga(X1, [], X1) -> mergecC_out_gga(X1, [], X1) mergecC_in_gga(.(X1, X2), .(X3, X4), .(X1, X5)) -> U23_gga(X1, X2, X3, X4, X5, lecD_in_gg(X1, X3)) lecD_in_gg(s(X1), s(X2)) -> U27_gg(X1, X2, lecD_in_gg(X1, X2)) lecD_in_gg(0, s(X1)) -> lecD_out_gg(0, s(X1)) lecD_in_gg(0, 0) -> lecD_out_gg(0, 0) U27_gg(X1, X2, lecD_out_gg(X1, X2)) -> lecD_out_gg(s(X1), s(X2)) U23_gga(X1, X2, X3, X4, X5, lecD_out_gg(X1, X3)) -> U24_gga(X1, X2, X3, X4, X5, mergecC_in_gga(X2, .(X3, X4), X5)) mergecC_in_gga(.(X1, X2), .(X3, X4), .(X3, X5)) -> U25_gga(X1, X2, X3, X4, X5, gtcE_in_gg(X1, X3)) gtcE_in_gg(s(X1), s(X2)) -> U28_gg(X1, X2, gtcE_in_gg(X1, X2)) gtcE_in_gg(s(X1), 0) -> gtcE_out_gg(s(X1), 0) U28_gg(X1, X2, gtcE_out_gg(X1, X2)) -> gtcE_out_gg(s(X1), s(X2)) U25_gga(X1, X2, X3, X4, X5, gtcE_out_gg(X1, X3)) -> U26_gga(X1, X2, X3, X4, X5, mergecC_in_gga(.(X1, X2), X4, X5)) U26_gga(X1, X2, X3, X4, X5, mergecC_out_gga(.(X1, X2), X4, X5)) -> mergecC_out_gga(.(X1, X2), .(X3, X4), .(X3, X5)) U24_gga(X1, X2, X3, X4, X5, mergecC_out_gga(X2, .(X3, X4), X5)) -> mergecC_out_gga(.(X1, X2), .(X3, X4), .(X1, X5)) U22_ga(X1, X2, X3, X4, mergecC_out_gga(X7, X8, X4)) -> mergesortcB_out_ga(.(X1, .(X2, X3)), X4) The argument filtering Pi contains the following mapping: mergesortB_in_ga(x1, x2) = mergesortB_in_ga(x1) .(x1, x2) = .(x1, x2) splitA_in_gaa(x1, x2, x3) = splitA_in_gaa(x1) splitcA_in_gaa(x1, x2, x3) = splitcA_in_gaa(x1) [] = [] splitcA_out_gaa(x1, x2, x3) = splitcA_out_gaa(x1, x2, x3) U18_gaa(x1, x2, x3, x4, x5, x6) = U18_gaa(x1, x2, x3, x6) mergesortcB_in_ga(x1, x2) = mergesortcB_in_ga(x1) mergesortcB_out_ga(x1, x2) = mergesortcB_out_ga(x1, x2) U19_ga(x1, x2, x3, x4, x5) = U19_ga(x1, x2, x3, x5) U20_ga(x1, x2, x3, x4, x5, x6) = U20_ga(x1, x2, x3, x5, x6) U21_ga(x1, x2, x3, x4, x5, x6) = U21_ga(x1, x2, x3, x5, x6) U22_ga(x1, x2, x3, x4, x5) = U22_ga(x1, x2, x3, x5) mergecC_in_gga(x1, x2, x3) = mergecC_in_gga(x1, x2) mergecC_out_gga(x1, x2, x3) = mergecC_out_gga(x1, x2, x3) U23_gga(x1, x2, x3, x4, x5, x6) = U23_gga(x1, x2, x3, x4, x6) lecD_in_gg(x1, x2) = lecD_in_gg(x1, x2) s(x1) = s(x1) U27_gg(x1, x2, x3) = U27_gg(x1, x2, x3) 0 = 0 lecD_out_gg(x1, x2) = lecD_out_gg(x1, x2) U24_gga(x1, x2, x3, x4, x5, x6) = U24_gga(x1, x2, x3, x4, x6) U25_gga(x1, x2, x3, x4, x5, x6) = U25_gga(x1, x2, x3, x4, x6) gtcE_in_gg(x1, x2) = gtcE_in_gg(x1, x2) U28_gg(x1, x2, x3) = U28_gg(x1, x2, x3) gtcE_out_gg(x1, x2) = gtcE_out_gg(x1, x2) U26_gga(x1, x2, x3, x4, x5, x6) = U26_gga(x1, x2, x3, x4, x6) mergeC_in_gga(x1, x2, x3) = mergeC_in_gga(x1, x2) leD_in_gg(x1, x2) = leD_in_gg(x1, x2) gtE_in_gg(x1, x2) = gtE_in_gg(x1, x2) MERGESORTB_IN_GA(x1, x2) = MERGESORTB_IN_GA(x1) U10_GA(x1, x2, x3, x4, x5) = U10_GA(x1, x2, x3, x5) SPLITA_IN_GAA(x1, x2, x3) = SPLITA_IN_GAA(x1) U1_GAA(x1, x2, x3, x4, x5, x6) = U1_GAA(x1, x2, x3, x6) U11_GA(x1, x2, x3, x4, x5) = U11_GA(x1, x2, x3, x5) U12_GA(x1, x2, x3, x4, x5) = U12_GA(x1, x2, x3, x5) U13_GA(x1, x2, x3, x4, x5, x6) = U13_GA(x1, x2, x3, x5, x6) U14_GA(x1, x2, x3, x4, x5) = U14_GA(x1, x2, x3, x5) U15_GA(x1, x2, x3, x4, x5, x6) = U15_GA(x1, x2, x3, x5, x6) U16_GA(x1, x2, x3, x4, x5) = U16_GA(x1, x2, x3, x5) MERGEC_IN_GGA(x1, x2, x3) = MERGEC_IN_GGA(x1, x2) U2_GGA(x1, x2, x3, x4, x5, x6) = U2_GGA(x1, x2, x3, x4, x6) LED_IN_GG(x1, x2) = LED_IN_GG(x1, x2) U8_GG(x1, x2, x3) = U8_GG(x1, x2, x3) U3_GGA(x1, x2, x3, x4, x5, x6) = U3_GGA(x1, x2, x3, x4, x6) U4_GGA(x1, x2, x3, x4, x5, x6) = U4_GGA(x1, x2, x3, x4, x6) U5_GGA(x1, x2, x3, x4, x5, x6) = U5_GGA(x1, x2, x3, x4, x6) GTE_IN_GG(x1, x2) = GTE_IN_GG(x1, x2) U9_GG(x1, x2, x3) = U9_GG(x1, x2, x3) U6_GGA(x1, x2, x3, x4, x5, x6) = U6_GGA(x1, x2, x3, x4, x6) U7_GGA(x1, x2, x3, x4, x5, x6) = U7_GGA(x1, x2, x3, x4, x6) We have to consider all (P,R,Pi)-chains ---------------------------------------- (5) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LOPSTR] contains 5 SCCs with 16 less nodes. ---------------------------------------- (6) Complex Obligation (AND) ---------------------------------------- (7) Obligation: Pi DP problem: The TRS P consists of the following rules: GTE_IN_GG(s(X1), s(X2)) -> GTE_IN_GG(X1, X2) The TRS R consists of the following rules: splitcA_in_gaa([], [], []) -> splitcA_out_gaa([], [], []) splitcA_in_gaa(.(X1, []), .(X1, []), []) -> splitcA_out_gaa(.(X1, []), .(X1, []), []) splitcA_in_gaa(.(X1, .(X2, X3)), .(X1, X4), .(X2, X5)) -> U18_gaa(X1, X2, X3, X4, X5, splitcA_in_gaa(X3, X4, X5)) U18_gaa(X1, X2, X3, X4, X5, splitcA_out_gaa(X3, X4, X5)) -> splitcA_out_gaa(.(X1, .(X2, X3)), .(X1, X4), .(X2, X5)) mergesortcB_in_ga([], []) -> mergesortcB_out_ga([], []) mergesortcB_in_ga(.(X1, []), .(X1, [])) -> mergesortcB_out_ga(.(X1, []), .(X1, [])) mergesortcB_in_ga(.(X1, .(X2, X3)), X4) -> U19_ga(X1, X2, X3, X4, splitcA_in_gaa(X3, X5, X6)) U19_ga(X1, X2, X3, X4, splitcA_out_gaa(X3, X5, X6)) -> U20_ga(X1, X2, X3, X4, X6, mergesortcB_in_ga(.(X1, X5), X7)) U20_ga(X1, X2, X3, X4, X6, mergesortcB_out_ga(.(X1, X5), X7)) -> U21_ga(X1, X2, X3, X4, X7, mergesortcB_in_ga(.(X2, X6), X8)) U21_ga(X1, X2, X3, X4, X7, mergesortcB_out_ga(.(X2, X6), X8)) -> U22_ga(X1, X2, X3, X4, mergecC_in_gga(X7, X8, X4)) mergecC_in_gga([], X1, X1) -> mergecC_out_gga([], X1, X1) mergecC_in_gga(X1, [], X1) -> mergecC_out_gga(X1, [], X1) mergecC_in_gga(.(X1, X2), .(X3, X4), .(X1, X5)) -> U23_gga(X1, X2, X3, X4, X5, lecD_in_gg(X1, X3)) lecD_in_gg(s(X1), s(X2)) -> U27_gg(X1, X2, lecD_in_gg(X1, X2)) lecD_in_gg(0, s(X1)) -> lecD_out_gg(0, s(X1)) lecD_in_gg(0, 0) -> lecD_out_gg(0, 0) U27_gg(X1, X2, lecD_out_gg(X1, X2)) -> lecD_out_gg(s(X1), s(X2)) U23_gga(X1, X2, X3, X4, X5, lecD_out_gg(X1, X3)) -> U24_gga(X1, X2, X3, X4, X5, mergecC_in_gga(X2, .(X3, X4), X5)) mergecC_in_gga(.(X1, X2), .(X3, X4), .(X3, X5)) -> U25_gga(X1, X2, X3, X4, X5, gtcE_in_gg(X1, X3)) gtcE_in_gg(s(X1), s(X2)) -> U28_gg(X1, X2, gtcE_in_gg(X1, X2)) gtcE_in_gg(s(X1), 0) -> gtcE_out_gg(s(X1), 0) U28_gg(X1, X2, gtcE_out_gg(X1, X2)) -> gtcE_out_gg(s(X1), s(X2)) U25_gga(X1, X2, X3, X4, X5, gtcE_out_gg(X1, X3)) -> U26_gga(X1, X2, X3, X4, X5, mergecC_in_gga(.(X1, X2), X4, X5)) U26_gga(X1, X2, X3, X4, X5, mergecC_out_gga(.(X1, X2), X4, X5)) -> mergecC_out_gga(.(X1, X2), .(X3, X4), .(X3, X5)) U24_gga(X1, X2, X3, X4, X5, mergecC_out_gga(X2, .(X3, X4), X5)) -> mergecC_out_gga(.(X1, X2), .(X3, X4), .(X1, X5)) U22_ga(X1, X2, X3, X4, mergecC_out_gga(X7, X8, X4)) -> mergesortcB_out_ga(.(X1, .(X2, X3)), X4) The argument filtering Pi contains the following mapping: .(x1, x2) = .(x1, x2) splitcA_in_gaa(x1, x2, x3) = splitcA_in_gaa(x1) [] = [] splitcA_out_gaa(x1, x2, x3) = splitcA_out_gaa(x1, x2, x3) U18_gaa(x1, x2, x3, x4, x5, x6) = U18_gaa(x1, x2, x3, x6) mergesortcB_in_ga(x1, x2) = mergesortcB_in_ga(x1) mergesortcB_out_ga(x1, x2) = mergesortcB_out_ga(x1, x2) U19_ga(x1, x2, x3, x4, x5) = U19_ga(x1, x2, x3, x5) U20_ga(x1, x2, x3, x4, x5, x6) = U20_ga(x1, x2, x3, x5, x6) U21_ga(x1, x2, x3, x4, x5, x6) = U21_ga(x1, x2, x3, x5, x6) U22_ga(x1, x2, x3, x4, x5) = U22_ga(x1, x2, x3, x5) mergecC_in_gga(x1, x2, x3) = mergecC_in_gga(x1, x2) mergecC_out_gga(x1, x2, x3) = mergecC_out_gga(x1, x2, x3) U23_gga(x1, x2, x3, x4, x5, x6) = U23_gga(x1, x2, x3, x4, x6) lecD_in_gg(x1, x2) = lecD_in_gg(x1, x2) s(x1) = s(x1) U27_gg(x1, x2, x3) = U27_gg(x1, x2, x3) 0 = 0 lecD_out_gg(x1, x2) = lecD_out_gg(x1, x2) U24_gga(x1, x2, x3, x4, x5, x6) = U24_gga(x1, x2, x3, x4, x6) U25_gga(x1, x2, x3, x4, x5, x6) = U25_gga(x1, x2, x3, x4, x6) gtcE_in_gg(x1, x2) = gtcE_in_gg(x1, x2) U28_gg(x1, x2, x3) = U28_gg(x1, x2, x3) gtcE_out_gg(x1, x2) = gtcE_out_gg(x1, x2) U26_gga(x1, x2, x3, x4, x5, x6) = U26_gga(x1, x2, x3, x4, x6) GTE_IN_GG(x1, x2) = GTE_IN_GG(x1, x2) We have to consider all (P,R,Pi)-chains ---------------------------------------- (8) UsableRulesProof (EQUIVALENT) For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. ---------------------------------------- (9) Obligation: Pi DP problem: The TRS P consists of the following rules: GTE_IN_GG(s(X1), s(X2)) -> GTE_IN_GG(X1, X2) R is empty. Pi is empty. We have to consider all (P,R,Pi)-chains ---------------------------------------- (10) PiDPToQDPProof (EQUIVALENT) Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. ---------------------------------------- (11) Obligation: Q DP problem: The TRS P consists of the following rules: GTE_IN_GG(s(X1), s(X2)) -> GTE_IN_GG(X1, X2) R is empty. Q is empty. We have to consider all (P,Q,R)-chains. ---------------------------------------- (12) 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: *GTE_IN_GG(s(X1), s(X2)) -> GTE_IN_GG(X1, X2) The graph contains the following edges 1 > 1, 2 > 2 ---------------------------------------- (13) YES ---------------------------------------- (14) Obligation: Pi DP problem: The TRS P consists of the following rules: LED_IN_GG(s(X1), s(X2)) -> LED_IN_GG(X1, X2) The TRS R consists of the following rules: splitcA_in_gaa([], [], []) -> splitcA_out_gaa([], [], []) splitcA_in_gaa(.(X1, []), .(X1, []), []) -> splitcA_out_gaa(.(X1, []), .(X1, []), []) splitcA_in_gaa(.(X1, .(X2, X3)), .(X1, X4), .(X2, X5)) -> U18_gaa(X1, X2, X3, X4, X5, splitcA_in_gaa(X3, X4, X5)) U18_gaa(X1, X2, X3, X4, X5, splitcA_out_gaa(X3, X4, X5)) -> splitcA_out_gaa(.(X1, .(X2, X3)), .(X1, X4), .(X2, X5)) mergesortcB_in_ga([], []) -> mergesortcB_out_ga([], []) mergesortcB_in_ga(.(X1, []), .(X1, [])) -> mergesortcB_out_ga(.(X1, []), .(X1, [])) mergesortcB_in_ga(.(X1, .(X2, X3)), X4) -> U19_ga(X1, X2, X3, X4, splitcA_in_gaa(X3, X5, X6)) U19_ga(X1, X2, X3, X4, splitcA_out_gaa(X3, X5, X6)) -> U20_ga(X1, X2, X3, X4, X6, mergesortcB_in_ga(.(X1, X5), X7)) U20_ga(X1, X2, X3, X4, X6, mergesortcB_out_ga(.(X1, X5), X7)) -> U21_ga(X1, X2, X3, X4, X7, mergesortcB_in_ga(.(X2, X6), X8)) U21_ga(X1, X2, X3, X4, X7, mergesortcB_out_ga(.(X2, X6), X8)) -> U22_ga(X1, X2, X3, X4, mergecC_in_gga(X7, X8, X4)) mergecC_in_gga([], X1, X1) -> mergecC_out_gga([], X1, X1) mergecC_in_gga(X1, [], X1) -> mergecC_out_gga(X1, [], X1) mergecC_in_gga(.(X1, X2), .(X3, X4), .(X1, X5)) -> U23_gga(X1, X2, X3, X4, X5, lecD_in_gg(X1, X3)) lecD_in_gg(s(X1), s(X2)) -> U27_gg(X1, X2, lecD_in_gg(X1, X2)) lecD_in_gg(0, s(X1)) -> lecD_out_gg(0, s(X1)) lecD_in_gg(0, 0) -> lecD_out_gg(0, 0) U27_gg(X1, X2, lecD_out_gg(X1, X2)) -> lecD_out_gg(s(X1), s(X2)) U23_gga(X1, X2, X3, X4, X5, lecD_out_gg(X1, X3)) -> U24_gga(X1, X2, X3, X4, X5, mergecC_in_gga(X2, .(X3, X4), X5)) mergecC_in_gga(.(X1, X2), .(X3, X4), .(X3, X5)) -> U25_gga(X1, X2, X3, X4, X5, gtcE_in_gg(X1, X3)) gtcE_in_gg(s(X1), s(X2)) -> U28_gg(X1, X2, gtcE_in_gg(X1, X2)) gtcE_in_gg(s(X1), 0) -> gtcE_out_gg(s(X1), 0) U28_gg(X1, X2, gtcE_out_gg(X1, X2)) -> gtcE_out_gg(s(X1), s(X2)) U25_gga(X1, X2, X3, X4, X5, gtcE_out_gg(X1, X3)) -> U26_gga(X1, X2, X3, X4, X5, mergecC_in_gga(.(X1, X2), X4, X5)) U26_gga(X1, X2, X3, X4, X5, mergecC_out_gga(.(X1, X2), X4, X5)) -> mergecC_out_gga(.(X1, X2), .(X3, X4), .(X3, X5)) U24_gga(X1, X2, X3, X4, X5, mergecC_out_gga(X2, .(X3, X4), X5)) -> mergecC_out_gga(.(X1, X2), .(X3, X4), .(X1, X5)) U22_ga(X1, X2, X3, X4, mergecC_out_gga(X7, X8, X4)) -> mergesortcB_out_ga(.(X1, .(X2, X3)), X4) The argument filtering Pi contains the following mapping: .(x1, x2) = .(x1, x2) splitcA_in_gaa(x1, x2, x3) = splitcA_in_gaa(x1) [] = [] splitcA_out_gaa(x1, x2, x3) = splitcA_out_gaa(x1, x2, x3) U18_gaa(x1, x2, x3, x4, x5, x6) = U18_gaa(x1, x2, x3, x6) mergesortcB_in_ga(x1, x2) = mergesortcB_in_ga(x1) mergesortcB_out_ga(x1, x2) = mergesortcB_out_ga(x1, x2) U19_ga(x1, x2, x3, x4, x5) = U19_ga(x1, x2, x3, x5) U20_ga(x1, x2, x3, x4, x5, x6) = U20_ga(x1, x2, x3, x5, x6) U21_ga(x1, x2, x3, x4, x5, x6) = U21_ga(x1, x2, x3, x5, x6) U22_ga(x1, x2, x3, x4, x5) = U22_ga(x1, x2, x3, x5) mergecC_in_gga(x1, x2, x3) = mergecC_in_gga(x1, x2) mergecC_out_gga(x1, x2, x3) = mergecC_out_gga(x1, x2, x3) U23_gga(x1, x2, x3, x4, x5, x6) = U23_gga(x1, x2, x3, x4, x6) lecD_in_gg(x1, x2) = lecD_in_gg(x1, x2) s(x1) = s(x1) U27_gg(x1, x2, x3) = U27_gg(x1, x2, x3) 0 = 0 lecD_out_gg(x1, x2) = lecD_out_gg(x1, x2) U24_gga(x1, x2, x3, x4, x5, x6) = U24_gga(x1, x2, x3, x4, x6) U25_gga(x1, x2, x3, x4, x5, x6) = U25_gga(x1, x2, x3, x4, x6) gtcE_in_gg(x1, x2) = gtcE_in_gg(x1, x2) U28_gg(x1, x2, x3) = U28_gg(x1, x2, x3) gtcE_out_gg(x1, x2) = gtcE_out_gg(x1, x2) U26_gga(x1, x2, x3, x4, x5, x6) = U26_gga(x1, x2, x3, x4, x6) LED_IN_GG(x1, x2) = LED_IN_GG(x1, x2) We have to consider all (P,R,Pi)-chains ---------------------------------------- (15) UsableRulesProof (EQUIVALENT) For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. ---------------------------------------- (16) Obligation: Pi DP problem: The TRS P consists of the following rules: LED_IN_GG(s(X1), s(X2)) -> LED_IN_GG(X1, X2) R is empty. Pi is empty. We have to consider all (P,R,Pi)-chains ---------------------------------------- (17) PiDPToQDPProof (EQUIVALENT) Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. ---------------------------------------- (18) Obligation: Q DP problem: The TRS P consists of the following rules: LED_IN_GG(s(X1), s(X2)) -> LED_IN_GG(X1, X2) R is empty. Q is empty. We have to consider all (P,Q,R)-chains. ---------------------------------------- (19) 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: *LED_IN_GG(s(X1), s(X2)) -> LED_IN_GG(X1, X2) The graph contains the following edges 1 > 1, 2 > 2 ---------------------------------------- (20) YES ---------------------------------------- (21) Obligation: Pi DP problem: The TRS P consists of the following rules: MERGEC_IN_GGA(.(X1, X2), .(X3, X4), .(X1, X5)) -> U3_GGA(X1, X2, X3, X4, X5, lecD_in_gg(X1, X3)) U3_GGA(X1, X2, X3, X4, X5, lecD_out_gg(X1, X3)) -> MERGEC_IN_GGA(X2, .(X3, X4), X5) MERGEC_IN_GGA(.(X1, X2), .(X3, X4), .(X3, X5)) -> U6_GGA(X1, X2, X3, X4, X5, gtcE_in_gg(X1, X3)) U6_GGA(X1, X2, X3, X4, X5, gtcE_out_gg(X1, X3)) -> MERGEC_IN_GGA(.(X1, X2), X4, X5) The TRS R consists of the following rules: splitcA_in_gaa([], [], []) -> splitcA_out_gaa([], [], []) splitcA_in_gaa(.(X1, []), .(X1, []), []) -> splitcA_out_gaa(.(X1, []), .(X1, []), []) splitcA_in_gaa(.(X1, .(X2, X3)), .(X1, X4), .(X2, X5)) -> U18_gaa(X1, X2, X3, X4, X5, splitcA_in_gaa(X3, X4, X5)) U18_gaa(X1, X2, X3, X4, X5, splitcA_out_gaa(X3, X4, X5)) -> splitcA_out_gaa(.(X1, .(X2, X3)), .(X1, X4), .(X2, X5)) mergesortcB_in_ga([], []) -> mergesortcB_out_ga([], []) mergesortcB_in_ga(.(X1, []), .(X1, [])) -> mergesortcB_out_ga(.(X1, []), .(X1, [])) mergesortcB_in_ga(.(X1, .(X2, X3)), X4) -> U19_ga(X1, X2, X3, X4, splitcA_in_gaa(X3, X5, X6)) U19_ga(X1, X2, X3, X4, splitcA_out_gaa(X3, X5, X6)) -> U20_ga(X1, X2, X3, X4, X6, mergesortcB_in_ga(.(X1, X5), X7)) U20_ga(X1, X2, X3, X4, X6, mergesortcB_out_ga(.(X1, X5), X7)) -> U21_ga(X1, X2, X3, X4, X7, mergesortcB_in_ga(.(X2, X6), X8)) U21_ga(X1, X2, X3, X4, X7, mergesortcB_out_ga(.(X2, X6), X8)) -> U22_ga(X1, X2, X3, X4, mergecC_in_gga(X7, X8, X4)) mergecC_in_gga([], X1, X1) -> mergecC_out_gga([], X1, X1) mergecC_in_gga(X1, [], X1) -> mergecC_out_gga(X1, [], X1) mergecC_in_gga(.(X1, X2), .(X3, X4), .(X1, X5)) -> U23_gga(X1, X2, X3, X4, X5, lecD_in_gg(X1, X3)) lecD_in_gg(s(X1), s(X2)) -> U27_gg(X1, X2, lecD_in_gg(X1, X2)) lecD_in_gg(0, s(X1)) -> lecD_out_gg(0, s(X1)) lecD_in_gg(0, 0) -> lecD_out_gg(0, 0) U27_gg(X1, X2, lecD_out_gg(X1, X2)) -> lecD_out_gg(s(X1), s(X2)) U23_gga(X1, X2, X3, X4, X5, lecD_out_gg(X1, X3)) -> U24_gga(X1, X2, X3, X4, X5, mergecC_in_gga(X2, .(X3, X4), X5)) mergecC_in_gga(.(X1, X2), .(X3, X4), .(X3, X5)) -> U25_gga(X1, X2, X3, X4, X5, gtcE_in_gg(X1, X3)) gtcE_in_gg(s(X1), s(X2)) -> U28_gg(X1, X2, gtcE_in_gg(X1, X2)) gtcE_in_gg(s(X1), 0) -> gtcE_out_gg(s(X1), 0) U28_gg(X1, X2, gtcE_out_gg(X1, X2)) -> gtcE_out_gg(s(X1), s(X2)) U25_gga(X1, X2, X3, X4, X5, gtcE_out_gg(X1, X3)) -> U26_gga(X1, X2, X3, X4, X5, mergecC_in_gga(.(X1, X2), X4, X5)) U26_gga(X1, X2, X3, X4, X5, mergecC_out_gga(.(X1, X2), X4, X5)) -> mergecC_out_gga(.(X1, X2), .(X3, X4), .(X3, X5)) U24_gga(X1, X2, X3, X4, X5, mergecC_out_gga(X2, .(X3, X4), X5)) -> mergecC_out_gga(.(X1, X2), .(X3, X4), .(X1, X5)) U22_ga(X1, X2, X3, X4, mergecC_out_gga(X7, X8, X4)) -> mergesortcB_out_ga(.(X1, .(X2, X3)), X4) The argument filtering Pi contains the following mapping: .(x1, x2) = .(x1, x2) splitcA_in_gaa(x1, x2, x3) = splitcA_in_gaa(x1) [] = [] splitcA_out_gaa(x1, x2, x3) = splitcA_out_gaa(x1, x2, x3) U18_gaa(x1, x2, x3, x4, x5, x6) = U18_gaa(x1, x2, x3, x6) mergesortcB_in_ga(x1, x2) = mergesortcB_in_ga(x1) mergesortcB_out_ga(x1, x2) = mergesortcB_out_ga(x1, x2) U19_ga(x1, x2, x3, x4, x5) = U19_ga(x1, x2, x3, x5) U20_ga(x1, x2, x3, x4, x5, x6) = U20_ga(x1, x2, x3, x5, x6) U21_ga(x1, x2, x3, x4, x5, x6) = U21_ga(x1, x2, x3, x5, x6) U22_ga(x1, x2, x3, x4, x5) = U22_ga(x1, x2, x3, x5) mergecC_in_gga(x1, x2, x3) = mergecC_in_gga(x1, x2) mergecC_out_gga(x1, x2, x3) = mergecC_out_gga(x1, x2, x3) U23_gga(x1, x2, x3, x4, x5, x6) = U23_gga(x1, x2, x3, x4, x6) lecD_in_gg(x1, x2) = lecD_in_gg(x1, x2) s(x1) = s(x1) U27_gg(x1, x2, x3) = U27_gg(x1, x2, x3) 0 = 0 lecD_out_gg(x1, x2) = lecD_out_gg(x1, x2) U24_gga(x1, x2, x3, x4, x5, x6) = U24_gga(x1, x2, x3, x4, x6) U25_gga(x1, x2, x3, x4, x5, x6) = U25_gga(x1, x2, x3, x4, x6) gtcE_in_gg(x1, x2) = gtcE_in_gg(x1, x2) U28_gg(x1, x2, x3) = U28_gg(x1, x2, x3) gtcE_out_gg(x1, x2) = gtcE_out_gg(x1, x2) U26_gga(x1, x2, x3, x4, x5, x6) = U26_gga(x1, x2, x3, x4, x6) MERGEC_IN_GGA(x1, x2, x3) = MERGEC_IN_GGA(x1, x2) U3_GGA(x1, x2, x3, x4, x5, x6) = U3_GGA(x1, x2, x3, x4, x6) U6_GGA(x1, x2, x3, x4, x5, x6) = U6_GGA(x1, x2, x3, x4, x6) We have to consider all (P,R,Pi)-chains ---------------------------------------- (22) UsableRulesProof (EQUIVALENT) For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. ---------------------------------------- (23) Obligation: Pi DP problem: The TRS P consists of the following rules: MERGEC_IN_GGA(.(X1, X2), .(X3, X4), .(X1, X5)) -> U3_GGA(X1, X2, X3, X4, X5, lecD_in_gg(X1, X3)) U3_GGA(X1, X2, X3, X4, X5, lecD_out_gg(X1, X3)) -> MERGEC_IN_GGA(X2, .(X3, X4), X5) MERGEC_IN_GGA(.(X1, X2), .(X3, X4), .(X3, X5)) -> U6_GGA(X1, X2, X3, X4, X5, gtcE_in_gg(X1, X3)) U6_GGA(X1, X2, X3, X4, X5, gtcE_out_gg(X1, X3)) -> MERGEC_IN_GGA(.(X1, X2), X4, X5) The TRS R consists of the following rules: lecD_in_gg(s(X1), s(X2)) -> U27_gg(X1, X2, lecD_in_gg(X1, X2)) lecD_in_gg(0, s(X1)) -> lecD_out_gg(0, s(X1)) lecD_in_gg(0, 0) -> lecD_out_gg(0, 0) gtcE_in_gg(s(X1), s(X2)) -> U28_gg(X1, X2, gtcE_in_gg(X1, X2)) gtcE_in_gg(s(X1), 0) -> gtcE_out_gg(s(X1), 0) U27_gg(X1, X2, lecD_out_gg(X1, X2)) -> lecD_out_gg(s(X1), s(X2)) U28_gg(X1, X2, gtcE_out_gg(X1, X2)) -> gtcE_out_gg(s(X1), s(X2)) The argument filtering Pi contains the following mapping: .(x1, x2) = .(x1, x2) lecD_in_gg(x1, x2) = lecD_in_gg(x1, x2) s(x1) = s(x1) U27_gg(x1, x2, x3) = U27_gg(x1, x2, x3) 0 = 0 lecD_out_gg(x1, x2) = lecD_out_gg(x1, x2) gtcE_in_gg(x1, x2) = gtcE_in_gg(x1, x2) U28_gg(x1, x2, x3) = U28_gg(x1, x2, x3) gtcE_out_gg(x1, x2) = gtcE_out_gg(x1, x2) MERGEC_IN_GGA(x1, x2, x3) = MERGEC_IN_GGA(x1, x2) U3_GGA(x1, x2, x3, x4, x5, x6) = U3_GGA(x1, x2, x3, x4, x6) U6_GGA(x1, x2, x3, x4, x5, x6) = U6_GGA(x1, x2, x3, x4, x6) We have to consider all (P,R,Pi)-chains ---------------------------------------- (24) PiDPToQDPProof (SOUND) Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. ---------------------------------------- (25) Obligation: Q DP problem: The TRS P consists of the following rules: MERGEC_IN_GGA(.(X1, X2), .(X3, X4)) -> U3_GGA(X1, X2, X3, X4, lecD_in_gg(X1, X3)) U3_GGA(X1, X2, X3, X4, lecD_out_gg(X1, X3)) -> MERGEC_IN_GGA(X2, .(X3, X4)) MERGEC_IN_GGA(.(X1, X2), .(X3, X4)) -> U6_GGA(X1, X2, X3, X4, gtcE_in_gg(X1, X3)) U6_GGA(X1, X2, X3, X4, gtcE_out_gg(X1, X3)) -> MERGEC_IN_GGA(.(X1, X2), X4) The TRS R consists of the following rules: lecD_in_gg(s(X1), s(X2)) -> U27_gg(X1, X2, lecD_in_gg(X1, X2)) lecD_in_gg(0, s(X1)) -> lecD_out_gg(0, s(X1)) lecD_in_gg(0, 0) -> lecD_out_gg(0, 0) gtcE_in_gg(s(X1), s(X2)) -> U28_gg(X1, X2, gtcE_in_gg(X1, X2)) gtcE_in_gg(s(X1), 0) -> gtcE_out_gg(s(X1), 0) U27_gg(X1, X2, lecD_out_gg(X1, X2)) -> lecD_out_gg(s(X1), s(X2)) U28_gg(X1, X2, gtcE_out_gg(X1, X2)) -> gtcE_out_gg(s(X1), s(X2)) The set Q consists of the following terms: lecD_in_gg(x0, x1) gtcE_in_gg(x0, x1) U27_gg(x0, x1, x2) U28_gg(x0, x1, x2) We have to consider all (P,Q,R)-chains. ---------------------------------------- (26) 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 rules of the TRS R: lecD_in_gg(0, s(X1)) -> lecD_out_gg(0, s(X1)) lecD_in_gg(0, 0) -> lecD_out_gg(0, 0) Used ordering: Polynomial interpretation [POLO]: POL(.(x_1, x_2)) = 2*x_1 + x_2 POL(0) = 1 POL(MERGEC_IN_GGA(x_1, x_2)) = 2*x_1 + 2*x_2 POL(U27_gg(x_1, x_2, x_3)) = x_1 + 2*x_2 + x_3 POL(U28_gg(x_1, x_2, x_3)) = x_1 + x_2 + x_3 POL(U3_GGA(x_1, x_2, x_3, x_4, x_5)) = x_1 + 2*x_2 + 2*x_3 + 2*x_4 + x_5 POL(U6_GGA(x_1, x_2, x_3, x_4, x_5)) = 2*x_1 + 2*x_2 + x_3 + 2*x_4 + 2*x_5 POL(gtcE_in_gg(x_1, x_2)) = x_1 + x_2 POL(gtcE_out_gg(x_1, x_2)) = x_1 + x_2 POL(lecD_in_gg(x_1, x_2)) = 2*x_1 + 2*x_2 POL(lecD_out_gg(x_1, x_2)) = x_1 + 2*x_2 POL(s(x_1)) = 2*x_1 ---------------------------------------- (27) Obligation: Q DP problem: The TRS P consists of the following rules: MERGEC_IN_GGA(.(X1, X2), .(X3, X4)) -> U3_GGA(X1, X2, X3, X4, lecD_in_gg(X1, X3)) U3_GGA(X1, X2, X3, X4, lecD_out_gg(X1, X3)) -> MERGEC_IN_GGA(X2, .(X3, X4)) MERGEC_IN_GGA(.(X1, X2), .(X3, X4)) -> U6_GGA(X1, X2, X3, X4, gtcE_in_gg(X1, X3)) U6_GGA(X1, X2, X3, X4, gtcE_out_gg(X1, X3)) -> MERGEC_IN_GGA(.(X1, X2), X4) The TRS R consists of the following rules: lecD_in_gg(s(X1), s(X2)) -> U27_gg(X1, X2, lecD_in_gg(X1, X2)) gtcE_in_gg(s(X1), s(X2)) -> U28_gg(X1, X2, gtcE_in_gg(X1, X2)) gtcE_in_gg(s(X1), 0) -> gtcE_out_gg(s(X1), 0) U27_gg(X1, X2, lecD_out_gg(X1, X2)) -> lecD_out_gg(s(X1), s(X2)) U28_gg(X1, X2, gtcE_out_gg(X1, X2)) -> gtcE_out_gg(s(X1), s(X2)) The set Q consists of the following terms: lecD_in_gg(x0, x1) gtcE_in_gg(x0, x1) U27_gg(x0, x1, x2) U28_gg(x0, x1, x2) We have to consider all (P,Q,R)-chains. ---------------------------------------- (28) 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: U3_GGA(X1, X2, X3, X4, lecD_out_gg(X1, X3)) -> MERGEC_IN_GGA(X2, .(X3, X4)) Used ordering: Polynomial interpretation [POLO]: POL(.(x_1, x_2)) = 2*x_1 + x_2 POL(0) = 0 POL(MERGEC_IN_GGA(x_1, x_2)) = 1 + 2*x_1 + 2*x_2 POL(U27_gg(x_1, x_2, x_3)) = x_1 + 2*x_2 + x_3 POL(U28_gg(x_1, x_2, x_3)) = x_1 + x_2 + x_3 POL(U3_GGA(x_1, x_2, x_3, x_4, x_5)) = 1 + x_1 + 2*x_2 + 2*x_3 + 2*x_4 + x_5 POL(U6_GGA(x_1, x_2, x_3, x_4, x_5)) = 1 + 2*x_1 + 2*x_2 + x_3 + 2*x_4 + 2*x_5 POL(gtcE_in_gg(x_1, x_2)) = x_1 + x_2 POL(gtcE_out_gg(x_1, x_2)) = x_1 + x_2 POL(lecD_in_gg(x_1, x_2)) = 2*x_1 + 2*x_2 POL(lecD_out_gg(x_1, x_2)) = 1 + x_1 + 2*x_2 POL(s(x_1)) = 2*x_1 ---------------------------------------- (29) Obligation: Q DP problem: The TRS P consists of the following rules: MERGEC_IN_GGA(.(X1, X2), .(X3, X4)) -> U3_GGA(X1, X2, X3, X4, lecD_in_gg(X1, X3)) MERGEC_IN_GGA(.(X1, X2), .(X3, X4)) -> U6_GGA(X1, X2, X3, X4, gtcE_in_gg(X1, X3)) U6_GGA(X1, X2, X3, X4, gtcE_out_gg(X1, X3)) -> MERGEC_IN_GGA(.(X1, X2), X4) The TRS R consists of the following rules: lecD_in_gg(s(X1), s(X2)) -> U27_gg(X1, X2, lecD_in_gg(X1, X2)) gtcE_in_gg(s(X1), s(X2)) -> U28_gg(X1, X2, gtcE_in_gg(X1, X2)) gtcE_in_gg(s(X1), 0) -> gtcE_out_gg(s(X1), 0) U27_gg(X1, X2, lecD_out_gg(X1, X2)) -> lecD_out_gg(s(X1), s(X2)) U28_gg(X1, X2, gtcE_out_gg(X1, X2)) -> gtcE_out_gg(s(X1), s(X2)) The set Q consists of the following terms: lecD_in_gg(x0, x1) gtcE_in_gg(x0, x1) U27_gg(x0, x1, x2) U28_gg(x0, x1, x2) We have to consider all (P,Q,R)-chains. ---------------------------------------- (30) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 1 less node. ---------------------------------------- (31) Obligation: Q DP problem: The TRS P consists of the following rules: MERGEC_IN_GGA(.(X1, X2), .(X3, X4)) -> U6_GGA(X1, X2, X3, X4, gtcE_in_gg(X1, X3)) U6_GGA(X1, X2, X3, X4, gtcE_out_gg(X1, X3)) -> MERGEC_IN_GGA(.(X1, X2), X4) The TRS R consists of the following rules: lecD_in_gg(s(X1), s(X2)) -> U27_gg(X1, X2, lecD_in_gg(X1, X2)) gtcE_in_gg(s(X1), s(X2)) -> U28_gg(X1, X2, gtcE_in_gg(X1, X2)) gtcE_in_gg(s(X1), 0) -> gtcE_out_gg(s(X1), 0) U27_gg(X1, X2, lecD_out_gg(X1, X2)) -> lecD_out_gg(s(X1), s(X2)) U28_gg(X1, X2, gtcE_out_gg(X1, X2)) -> gtcE_out_gg(s(X1), s(X2)) The set Q consists of the following terms: lecD_in_gg(x0, x1) gtcE_in_gg(x0, x1) U27_gg(x0, x1, x2) U28_gg(x0, x1, x2) We have to consider all (P,Q,R)-chains. ---------------------------------------- (32) UsableRulesProof (EQUIVALENT) As all Q-normal forms are R-normal forms we are in the innermost case. Hence, by the usable rules processor [LPAR04] we can delete all non-usable rules [FROCOS05] from R. ---------------------------------------- (33) Obligation: Q DP problem: The TRS P consists of the following rules: MERGEC_IN_GGA(.(X1, X2), .(X3, X4)) -> U6_GGA(X1, X2, X3, X4, gtcE_in_gg(X1, X3)) U6_GGA(X1, X2, X3, X4, gtcE_out_gg(X1, X3)) -> MERGEC_IN_GGA(.(X1, X2), X4) The TRS R consists of the following rules: gtcE_in_gg(s(X1), s(X2)) -> U28_gg(X1, X2, gtcE_in_gg(X1, X2)) gtcE_in_gg(s(X1), 0) -> gtcE_out_gg(s(X1), 0) U28_gg(X1, X2, gtcE_out_gg(X1, X2)) -> gtcE_out_gg(s(X1), s(X2)) The set Q consists of the following terms: lecD_in_gg(x0, x1) gtcE_in_gg(x0, x1) U27_gg(x0, x1, x2) U28_gg(x0, x1, x2) We have to consider all (P,Q,R)-chains. ---------------------------------------- (34) QReductionProof (EQUIVALENT) We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. lecD_in_gg(x0, x1) U27_gg(x0, x1, x2) ---------------------------------------- (35) Obligation: Q DP problem: The TRS P consists of the following rules: MERGEC_IN_GGA(.(X1, X2), .(X3, X4)) -> U6_GGA(X1, X2, X3, X4, gtcE_in_gg(X1, X3)) U6_GGA(X1, X2, X3, X4, gtcE_out_gg(X1, X3)) -> MERGEC_IN_GGA(.(X1, X2), X4) The TRS R consists of the following rules: gtcE_in_gg(s(X1), s(X2)) -> U28_gg(X1, X2, gtcE_in_gg(X1, X2)) gtcE_in_gg(s(X1), 0) -> gtcE_out_gg(s(X1), 0) U28_gg(X1, X2, gtcE_out_gg(X1, X2)) -> gtcE_out_gg(s(X1), s(X2)) The set Q consists of the following terms: gtcE_in_gg(x0, x1) U28_gg(x0, x1, x2) We have to consider all (P,Q,R)-chains. ---------------------------------------- (36) 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: *U6_GGA(X1, X2, X3, X4, gtcE_out_gg(X1, X3)) -> MERGEC_IN_GGA(.(X1, X2), X4) The graph contains the following edges 4 >= 2 *MERGEC_IN_GGA(.(X1, X2), .(X3, X4)) -> U6_GGA(X1, X2, X3, X4, gtcE_in_gg(X1, X3)) The graph contains the following edges 1 > 1, 1 > 2, 2 > 3, 2 > 4 ---------------------------------------- (37) YES ---------------------------------------- (38) Obligation: Pi DP problem: The TRS P consists of the following rules: SPLITA_IN_GAA(.(X1, .(X2, X3)), .(X1, X4), .(X2, X5)) -> SPLITA_IN_GAA(X3, X4, X5) The TRS R consists of the following rules: splitcA_in_gaa([], [], []) -> splitcA_out_gaa([], [], []) splitcA_in_gaa(.(X1, []), .(X1, []), []) -> splitcA_out_gaa(.(X1, []), .(X1, []), []) splitcA_in_gaa(.(X1, .(X2, X3)), .(X1, X4), .(X2, X5)) -> U18_gaa(X1, X2, X3, X4, X5, splitcA_in_gaa(X3, X4, X5)) U18_gaa(X1, X2, X3, X4, X5, splitcA_out_gaa(X3, X4, X5)) -> splitcA_out_gaa(.(X1, .(X2, X3)), .(X1, X4), .(X2, X5)) mergesortcB_in_ga([], []) -> mergesortcB_out_ga([], []) mergesortcB_in_ga(.(X1, []), .(X1, [])) -> mergesortcB_out_ga(.(X1, []), .(X1, [])) mergesortcB_in_ga(.(X1, .(X2, X3)), X4) -> U19_ga(X1, X2, X3, X4, splitcA_in_gaa(X3, X5, X6)) U19_ga(X1, X2, X3, X4, splitcA_out_gaa(X3, X5, X6)) -> U20_ga(X1, X2, X3, X4, X6, mergesortcB_in_ga(.(X1, X5), X7)) U20_ga(X1, X2, X3, X4, X6, mergesortcB_out_ga(.(X1, X5), X7)) -> U21_ga(X1, X2, X3, X4, X7, mergesortcB_in_ga(.(X2, X6), X8)) U21_ga(X1, X2, X3, X4, X7, mergesortcB_out_ga(.(X2, X6), X8)) -> U22_ga(X1, X2, X3, X4, mergecC_in_gga(X7, X8, X4)) mergecC_in_gga([], X1, X1) -> mergecC_out_gga([], X1, X1) mergecC_in_gga(X1, [], X1) -> mergecC_out_gga(X1, [], X1) mergecC_in_gga(.(X1, X2), .(X3, X4), .(X1, X5)) -> U23_gga(X1, X2, X3, X4, X5, lecD_in_gg(X1, X3)) lecD_in_gg(s(X1), s(X2)) -> U27_gg(X1, X2, lecD_in_gg(X1, X2)) lecD_in_gg(0, s(X1)) -> lecD_out_gg(0, s(X1)) lecD_in_gg(0, 0) -> lecD_out_gg(0, 0) U27_gg(X1, X2, lecD_out_gg(X1, X2)) -> lecD_out_gg(s(X1), s(X2)) U23_gga(X1, X2, X3, X4, X5, lecD_out_gg(X1, X3)) -> U24_gga(X1, X2, X3, X4, X5, mergecC_in_gga(X2, .(X3, X4), X5)) mergecC_in_gga(.(X1, X2), .(X3, X4), .(X3, X5)) -> U25_gga(X1, X2, X3, X4, X5, gtcE_in_gg(X1, X3)) gtcE_in_gg(s(X1), s(X2)) -> U28_gg(X1, X2, gtcE_in_gg(X1, X2)) gtcE_in_gg(s(X1), 0) -> gtcE_out_gg(s(X1), 0) U28_gg(X1, X2, gtcE_out_gg(X1, X2)) -> gtcE_out_gg(s(X1), s(X2)) U25_gga(X1, X2, X3, X4, X5, gtcE_out_gg(X1, X3)) -> U26_gga(X1, X2, X3, X4, X5, mergecC_in_gga(.(X1, X2), X4, X5)) U26_gga(X1, X2, X3, X4, X5, mergecC_out_gga(.(X1, X2), X4, X5)) -> mergecC_out_gga(.(X1, X2), .(X3, X4), .(X3, X5)) U24_gga(X1, X2, X3, X4, X5, mergecC_out_gga(X2, .(X3, X4), X5)) -> mergecC_out_gga(.(X1, X2), .(X3, X4), .(X1, X5)) U22_ga(X1, X2, X3, X4, mergecC_out_gga(X7, X8, X4)) -> mergesortcB_out_ga(.(X1, .(X2, X3)), X4) The argument filtering Pi contains the following mapping: .(x1, x2) = .(x1, x2) splitcA_in_gaa(x1, x2, x3) = splitcA_in_gaa(x1) [] = [] splitcA_out_gaa(x1, x2, x3) = splitcA_out_gaa(x1, x2, x3) U18_gaa(x1, x2, x3, x4, x5, x6) = U18_gaa(x1, x2, x3, x6) mergesortcB_in_ga(x1, x2) = mergesortcB_in_ga(x1) mergesortcB_out_ga(x1, x2) = mergesortcB_out_ga(x1, x2) U19_ga(x1, x2, x3, x4, x5) = U19_ga(x1, x2, x3, x5) U20_ga(x1, x2, x3, x4, x5, x6) = U20_ga(x1, x2, x3, x5, x6) U21_ga(x1, x2, x3, x4, x5, x6) = U21_ga(x1, x2, x3, x5, x6) U22_ga(x1, x2, x3, x4, x5) = U22_ga(x1, x2, x3, x5) mergecC_in_gga(x1, x2, x3) = mergecC_in_gga(x1, x2) mergecC_out_gga(x1, x2, x3) = mergecC_out_gga(x1, x2, x3) U23_gga(x1, x2, x3, x4, x5, x6) = U23_gga(x1, x2, x3, x4, x6) lecD_in_gg(x1, x2) = lecD_in_gg(x1, x2) s(x1) = s(x1) U27_gg(x1, x2, x3) = U27_gg(x1, x2, x3) 0 = 0 lecD_out_gg(x1, x2) = lecD_out_gg(x1, x2) U24_gga(x1, x2, x3, x4, x5, x6) = U24_gga(x1, x2, x3, x4, x6) U25_gga(x1, x2, x3, x4, x5, x6) = U25_gga(x1, x2, x3, x4, x6) gtcE_in_gg(x1, x2) = gtcE_in_gg(x1, x2) U28_gg(x1, x2, x3) = U28_gg(x1, x2, x3) gtcE_out_gg(x1, x2) = gtcE_out_gg(x1, x2) U26_gga(x1, x2, x3, x4, x5, x6) = U26_gga(x1, x2, x3, x4, x6) SPLITA_IN_GAA(x1, x2, x3) = SPLITA_IN_GAA(x1) We have to consider all (P,R,Pi)-chains ---------------------------------------- (39) UsableRulesProof (EQUIVALENT) For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. ---------------------------------------- (40) Obligation: Pi DP problem: The TRS P consists of the following rules: SPLITA_IN_GAA(.(X1, .(X2, X3)), .(X1, X4), .(X2, X5)) -> SPLITA_IN_GAA(X3, X4, X5) R is empty. The argument filtering Pi contains the following mapping: .(x1, x2) = .(x1, x2) SPLITA_IN_GAA(x1, x2, x3) = SPLITA_IN_GAA(x1) We have to consider all (P,R,Pi)-chains ---------------------------------------- (41) PiDPToQDPProof (SOUND) Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. ---------------------------------------- (42) Obligation: Q DP problem: The TRS P consists of the following rules: SPLITA_IN_GAA(.(X1, .(X2, X3))) -> SPLITA_IN_GAA(X3) R is empty. Q is empty. We have to consider all (P,Q,R)-chains. ---------------------------------------- (43) 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: *SPLITA_IN_GAA(.(X1, .(X2, X3))) -> SPLITA_IN_GAA(X3) The graph contains the following edges 1 > 1 ---------------------------------------- (44) YES ---------------------------------------- (45) Obligation: Pi DP problem: The TRS P consists of the following rules: MERGESORTB_IN_GA(.(X1, .(X2, X3)), X4) -> U11_GA(X1, X2, X3, X4, splitcA_in_gaa(X3, X5, X6)) U11_GA(X1, X2, X3, X4, splitcA_out_gaa(X3, X5, X6)) -> MERGESORTB_IN_GA(.(X1, X5), X7) U11_GA(X1, X2, X3, X4, splitcA_out_gaa(X3, X5, X6)) -> U13_GA(X1, X2, X3, X4, X6, mergesortcB_in_ga(.(X1, X5), X7)) U13_GA(X1, X2, X3, X4, X6, mergesortcB_out_ga(.(X1, X5), X7)) -> MERGESORTB_IN_GA(.(X2, X6), X8) The TRS R consists of the following rules: splitcA_in_gaa([], [], []) -> splitcA_out_gaa([], [], []) splitcA_in_gaa(.(X1, []), .(X1, []), []) -> splitcA_out_gaa(.(X1, []), .(X1, []), []) splitcA_in_gaa(.(X1, .(X2, X3)), .(X1, X4), .(X2, X5)) -> U18_gaa(X1, X2, X3, X4, X5, splitcA_in_gaa(X3, X4, X5)) U18_gaa(X1, X2, X3, X4, X5, splitcA_out_gaa(X3, X4, X5)) -> splitcA_out_gaa(.(X1, .(X2, X3)), .(X1, X4), .(X2, X5)) mergesortcB_in_ga([], []) -> mergesortcB_out_ga([], []) mergesortcB_in_ga(.(X1, []), .(X1, [])) -> mergesortcB_out_ga(.(X1, []), .(X1, [])) mergesortcB_in_ga(.(X1, .(X2, X3)), X4) -> U19_ga(X1, X2, X3, X4, splitcA_in_gaa(X3, X5, X6)) U19_ga(X1, X2, X3, X4, splitcA_out_gaa(X3, X5, X6)) -> U20_ga(X1, X2, X3, X4, X6, mergesortcB_in_ga(.(X1, X5), X7)) U20_ga(X1, X2, X3, X4, X6, mergesortcB_out_ga(.(X1, X5), X7)) -> U21_ga(X1, X2, X3, X4, X7, mergesortcB_in_ga(.(X2, X6), X8)) U21_ga(X1, X2, X3, X4, X7, mergesortcB_out_ga(.(X2, X6), X8)) -> U22_ga(X1, X2, X3, X4, mergecC_in_gga(X7, X8, X4)) mergecC_in_gga([], X1, X1) -> mergecC_out_gga([], X1, X1) mergecC_in_gga(X1, [], X1) -> mergecC_out_gga(X1, [], X1) mergecC_in_gga(.(X1, X2), .(X3, X4), .(X1, X5)) -> U23_gga(X1, X2, X3, X4, X5, lecD_in_gg(X1, X3)) lecD_in_gg(s(X1), s(X2)) -> U27_gg(X1, X2, lecD_in_gg(X1, X2)) lecD_in_gg(0, s(X1)) -> lecD_out_gg(0, s(X1)) lecD_in_gg(0, 0) -> lecD_out_gg(0, 0) U27_gg(X1, X2, lecD_out_gg(X1, X2)) -> lecD_out_gg(s(X1), s(X2)) U23_gga(X1, X2, X3, X4, X5, lecD_out_gg(X1, X3)) -> U24_gga(X1, X2, X3, X4, X5, mergecC_in_gga(X2, .(X3, X4), X5)) mergecC_in_gga(.(X1, X2), .(X3, X4), .(X3, X5)) -> U25_gga(X1, X2, X3, X4, X5, gtcE_in_gg(X1, X3)) gtcE_in_gg(s(X1), s(X2)) -> U28_gg(X1, X2, gtcE_in_gg(X1, X2)) gtcE_in_gg(s(X1), 0) -> gtcE_out_gg(s(X1), 0) U28_gg(X1, X2, gtcE_out_gg(X1, X2)) -> gtcE_out_gg(s(X1), s(X2)) U25_gga(X1, X2, X3, X4, X5, gtcE_out_gg(X1, X3)) -> U26_gga(X1, X2, X3, X4, X5, mergecC_in_gga(.(X1, X2), X4, X5)) U26_gga(X1, X2, X3, X4, X5, mergecC_out_gga(.(X1, X2), X4, X5)) -> mergecC_out_gga(.(X1, X2), .(X3, X4), .(X3, X5)) U24_gga(X1, X2, X3, X4, X5, mergecC_out_gga(X2, .(X3, X4), X5)) -> mergecC_out_gga(.(X1, X2), .(X3, X4), .(X1, X5)) U22_ga(X1, X2, X3, X4, mergecC_out_gga(X7, X8, X4)) -> mergesortcB_out_ga(.(X1, .(X2, X3)), X4) The argument filtering Pi contains the following mapping: .(x1, x2) = .(x1, x2) splitcA_in_gaa(x1, x2, x3) = splitcA_in_gaa(x1) [] = [] splitcA_out_gaa(x1, x2, x3) = splitcA_out_gaa(x1, x2, x3) U18_gaa(x1, x2, x3, x4, x5, x6) = U18_gaa(x1, x2, x3, x6) mergesortcB_in_ga(x1, x2) = mergesortcB_in_ga(x1) mergesortcB_out_ga(x1, x2) = mergesortcB_out_ga(x1, x2) U19_ga(x1, x2, x3, x4, x5) = U19_ga(x1, x2, x3, x5) U20_ga(x1, x2, x3, x4, x5, x6) = U20_ga(x1, x2, x3, x5, x6) U21_ga(x1, x2, x3, x4, x5, x6) = U21_ga(x1, x2, x3, x5, x6) U22_ga(x1, x2, x3, x4, x5) = U22_ga(x1, x2, x3, x5) mergecC_in_gga(x1, x2, x3) = mergecC_in_gga(x1, x2) mergecC_out_gga(x1, x2, x3) = mergecC_out_gga(x1, x2, x3) U23_gga(x1, x2, x3, x4, x5, x6) = U23_gga(x1, x2, x3, x4, x6) lecD_in_gg(x1, x2) = lecD_in_gg(x1, x2) s(x1) = s(x1) U27_gg(x1, x2, x3) = U27_gg(x1, x2, x3) 0 = 0 lecD_out_gg(x1, x2) = lecD_out_gg(x1, x2) U24_gga(x1, x2, x3, x4, x5, x6) = U24_gga(x1, x2, x3, x4, x6) U25_gga(x1, x2, x3, x4, x5, x6) = U25_gga(x1, x2, x3, x4, x6) gtcE_in_gg(x1, x2) = gtcE_in_gg(x1, x2) U28_gg(x1, x2, x3) = U28_gg(x1, x2, x3) gtcE_out_gg(x1, x2) = gtcE_out_gg(x1, x2) U26_gga(x1, x2, x3, x4, x5, x6) = U26_gga(x1, x2, x3, x4, x6) MERGESORTB_IN_GA(x1, x2) = MERGESORTB_IN_GA(x1) U11_GA(x1, x2, x3, x4, x5) = U11_GA(x1, x2, x3, x5) U13_GA(x1, x2, x3, x4, x5, x6) = U13_GA(x1, x2, x3, x5, x6) We have to consider all (P,R,Pi)-chains ---------------------------------------- (46) UsableRulesProof (EQUIVALENT) For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. ---------------------------------------- (47) Obligation: Pi DP problem: The TRS P consists of the following rules: MERGESORTB_IN_GA(.(X1, .(X2, X3)), X4) -> U11_GA(X1, X2, X3, X4, splitcA_in_gaa(X3, X5, X6)) U11_GA(X1, X2, X3, X4, splitcA_out_gaa(X3, X5, X6)) -> MERGESORTB_IN_GA(.(X1, X5), X7) U11_GA(X1, X2, X3, X4, splitcA_out_gaa(X3, X5, X6)) -> U13_GA(X1, X2, X3, X4, X6, mergesortcB_in_ga(.(X1, X5), X7)) U13_GA(X1, X2, X3, X4, X6, mergesortcB_out_ga(.(X1, X5), X7)) -> MERGESORTB_IN_GA(.(X2, X6), X8) The TRS R consists of the following rules: splitcA_in_gaa([], [], []) -> splitcA_out_gaa([], [], []) splitcA_in_gaa(.(X1, []), .(X1, []), []) -> splitcA_out_gaa(.(X1, []), .(X1, []), []) splitcA_in_gaa(.(X1, .(X2, X3)), .(X1, X4), .(X2, X5)) -> U18_gaa(X1, X2, X3, X4, X5, splitcA_in_gaa(X3, X4, X5)) mergesortcB_in_ga(.(X1, []), .(X1, [])) -> mergesortcB_out_ga(.(X1, []), .(X1, [])) mergesortcB_in_ga(.(X1, .(X2, X3)), X4) -> U19_ga(X1, X2, X3, X4, splitcA_in_gaa(X3, X5, X6)) U18_gaa(X1, X2, X3, X4, X5, splitcA_out_gaa(X3, X4, X5)) -> splitcA_out_gaa(.(X1, .(X2, X3)), .(X1, X4), .(X2, X5)) U19_ga(X1, X2, X3, X4, splitcA_out_gaa(X3, X5, X6)) -> U20_ga(X1, X2, X3, X4, X6, mergesortcB_in_ga(.(X1, X5), X7)) U20_ga(X1, X2, X3, X4, X6, mergesortcB_out_ga(.(X1, X5), X7)) -> U21_ga(X1, X2, X3, X4, X7, mergesortcB_in_ga(.(X2, X6), X8)) U21_ga(X1, X2, X3, X4, X7, mergesortcB_out_ga(.(X2, X6), X8)) -> U22_ga(X1, X2, X3, X4, mergecC_in_gga(X7, X8, X4)) U22_ga(X1, X2, X3, X4, mergecC_out_gga(X7, X8, X4)) -> mergesortcB_out_ga(.(X1, .(X2, X3)), X4) mergecC_in_gga([], X1, X1) -> mergecC_out_gga([], X1, X1) mergecC_in_gga(X1, [], X1) -> mergecC_out_gga(X1, [], X1) mergecC_in_gga(.(X1, X2), .(X3, X4), .(X1, X5)) -> U23_gga(X1, X2, X3, X4, X5, lecD_in_gg(X1, X3)) mergecC_in_gga(.(X1, X2), .(X3, X4), .(X3, X5)) -> U25_gga(X1, X2, X3, X4, X5, gtcE_in_gg(X1, X3)) U23_gga(X1, X2, X3, X4, X5, lecD_out_gg(X1, X3)) -> U24_gga(X1, X2, X3, X4, X5, mergecC_in_gga(X2, .(X3, X4), X5)) U25_gga(X1, X2, X3, X4, X5, gtcE_out_gg(X1, X3)) -> U26_gga(X1, X2, X3, X4, X5, mergecC_in_gga(.(X1, X2), X4, X5)) lecD_in_gg(s(X1), s(X2)) -> U27_gg(X1, X2, lecD_in_gg(X1, X2)) lecD_in_gg(0, s(X1)) -> lecD_out_gg(0, s(X1)) lecD_in_gg(0, 0) -> lecD_out_gg(0, 0) U24_gga(X1, X2, X3, X4, X5, mergecC_out_gga(X2, .(X3, X4), X5)) -> mergecC_out_gga(.(X1, X2), .(X3, X4), .(X1, X5)) gtcE_in_gg(s(X1), s(X2)) -> U28_gg(X1, X2, gtcE_in_gg(X1, X2)) gtcE_in_gg(s(X1), 0) -> gtcE_out_gg(s(X1), 0) U26_gga(X1, X2, X3, X4, X5, mergecC_out_gga(.(X1, X2), X4, X5)) -> mergecC_out_gga(.(X1, X2), .(X3, X4), .(X3, X5)) U27_gg(X1, X2, lecD_out_gg(X1, X2)) -> lecD_out_gg(s(X1), s(X2)) U28_gg(X1, X2, gtcE_out_gg(X1, X2)) -> gtcE_out_gg(s(X1), s(X2)) The argument filtering Pi contains the following mapping: .(x1, x2) = .(x1, x2) splitcA_in_gaa(x1, x2, x3) = splitcA_in_gaa(x1) [] = [] splitcA_out_gaa(x1, x2, x3) = splitcA_out_gaa(x1, x2, x3) U18_gaa(x1, x2, x3, x4, x5, x6) = U18_gaa(x1, x2, x3, x6) mergesortcB_in_ga(x1, x2) = mergesortcB_in_ga(x1) mergesortcB_out_ga(x1, x2) = mergesortcB_out_ga(x1, x2) U19_ga(x1, x2, x3, x4, x5) = U19_ga(x1, x2, x3, x5) U20_ga(x1, x2, x3, x4, x5, x6) = U20_ga(x1, x2, x3, x5, x6) U21_ga(x1, x2, x3, x4, x5, x6) = U21_ga(x1, x2, x3, x5, x6) U22_ga(x1, x2, x3, x4, x5) = U22_ga(x1, x2, x3, x5) mergecC_in_gga(x1, x2, x3) = mergecC_in_gga(x1, x2) mergecC_out_gga(x1, x2, x3) = mergecC_out_gga(x1, x2, x3) U23_gga(x1, x2, x3, x4, x5, x6) = U23_gga(x1, x2, x3, x4, x6) lecD_in_gg(x1, x2) = lecD_in_gg(x1, x2) s(x1) = s(x1) U27_gg(x1, x2, x3) = U27_gg(x1, x2, x3) 0 = 0 lecD_out_gg(x1, x2) = lecD_out_gg(x1, x2) U24_gga(x1, x2, x3, x4, x5, x6) = U24_gga(x1, x2, x3, x4, x6) U25_gga(x1, x2, x3, x4, x5, x6) = U25_gga(x1, x2, x3, x4, x6) gtcE_in_gg(x1, x2) = gtcE_in_gg(x1, x2) U28_gg(x1, x2, x3) = U28_gg(x1, x2, x3) gtcE_out_gg(x1, x2) = gtcE_out_gg(x1, x2) U26_gga(x1, x2, x3, x4, x5, x6) = U26_gga(x1, x2, x3, x4, x6) MERGESORTB_IN_GA(x1, x2) = MERGESORTB_IN_GA(x1) U11_GA(x1, x2, x3, x4, x5) = U11_GA(x1, x2, x3, x5) U13_GA(x1, x2, x3, x4, x5, x6) = U13_GA(x1, x2, x3, x5, x6) We have to consider all (P,R,Pi)-chains ---------------------------------------- (48) PiDPToQDPProof (SOUND) Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. ---------------------------------------- (49) Obligation: Q DP problem: The TRS P consists of the following rules: MERGESORTB_IN_GA(.(X1, .(X2, X3))) -> U11_GA(X1, X2, X3, splitcA_in_gaa(X3)) U11_GA(X1, X2, X3, splitcA_out_gaa(X3, X5, X6)) -> MERGESORTB_IN_GA(.(X1, X5)) U11_GA(X1, X2, X3, splitcA_out_gaa(X3, X5, X6)) -> U13_GA(X1, X2, X3, X6, mergesortcB_in_ga(.(X1, X5))) U13_GA(X1, X2, X3, X6, mergesortcB_out_ga(.(X1, X5), X7)) -> MERGESORTB_IN_GA(.(X2, X6)) The TRS R consists of the following rules: splitcA_in_gaa([]) -> splitcA_out_gaa([], [], []) splitcA_in_gaa(.(X1, [])) -> splitcA_out_gaa(.(X1, []), .(X1, []), []) splitcA_in_gaa(.(X1, .(X2, X3))) -> U18_gaa(X1, X2, X3, splitcA_in_gaa(X3)) mergesortcB_in_ga(.(X1, [])) -> mergesortcB_out_ga(.(X1, []), .(X1, [])) mergesortcB_in_ga(.(X1, .(X2, X3))) -> U19_ga(X1, X2, X3, splitcA_in_gaa(X3)) U18_gaa(X1, X2, X3, splitcA_out_gaa(X3, X4, X5)) -> splitcA_out_gaa(.(X1, .(X2, X3)), .(X1, X4), .(X2, X5)) U19_ga(X1, X2, X3, splitcA_out_gaa(X3, X5, X6)) -> U20_ga(X1, X2, X3, X6, mergesortcB_in_ga(.(X1, X5))) U20_ga(X1, X2, X3, X6, mergesortcB_out_ga(.(X1, X5), X7)) -> U21_ga(X1, X2, X3, X7, mergesortcB_in_ga(.(X2, X6))) U21_ga(X1, X2, X3, X7, mergesortcB_out_ga(.(X2, X6), X8)) -> U22_ga(X1, X2, X3, mergecC_in_gga(X7, X8)) U22_ga(X1, X2, X3, mergecC_out_gga(X7, X8, X4)) -> mergesortcB_out_ga(.(X1, .(X2, X3)), X4) mergecC_in_gga([], X1) -> mergecC_out_gga([], X1, X1) mergecC_in_gga(X1, []) -> mergecC_out_gga(X1, [], X1) mergecC_in_gga(.(X1, X2), .(X3, X4)) -> U23_gga(X1, X2, X3, X4, lecD_in_gg(X1, X3)) mergecC_in_gga(.(X1, X2), .(X3, X4)) -> U25_gga(X1, X2, X3, X4, gtcE_in_gg(X1, X3)) U23_gga(X1, X2, X3, X4, lecD_out_gg(X1, X3)) -> U24_gga(X1, X2, X3, X4, mergecC_in_gga(X2, .(X3, X4))) U25_gga(X1, X2, X3, X4, gtcE_out_gg(X1, X3)) -> U26_gga(X1, X2, X3, X4, mergecC_in_gga(.(X1, X2), X4)) lecD_in_gg(s(X1), s(X2)) -> U27_gg(X1, X2, lecD_in_gg(X1, X2)) lecD_in_gg(0, s(X1)) -> lecD_out_gg(0, s(X1)) lecD_in_gg(0, 0) -> lecD_out_gg(0, 0) U24_gga(X1, X2, X3, X4, mergecC_out_gga(X2, .(X3, X4), X5)) -> mergecC_out_gga(.(X1, X2), .(X3, X4), .(X1, X5)) gtcE_in_gg(s(X1), s(X2)) -> U28_gg(X1, X2, gtcE_in_gg(X1, X2)) gtcE_in_gg(s(X1), 0) -> gtcE_out_gg(s(X1), 0) U26_gga(X1, X2, X3, X4, mergecC_out_gga(.(X1, X2), X4, X5)) -> mergecC_out_gga(.(X1, X2), .(X3, X4), .(X3, X5)) U27_gg(X1, X2, lecD_out_gg(X1, X2)) -> lecD_out_gg(s(X1), s(X2)) U28_gg(X1, X2, gtcE_out_gg(X1, X2)) -> gtcE_out_gg(s(X1), s(X2)) The set Q consists of the following terms: splitcA_in_gaa(x0) mergesortcB_in_ga(x0) U18_gaa(x0, x1, x2, x3) U19_ga(x0, x1, x2, x3) U20_ga(x0, x1, x2, x3, x4) U21_ga(x0, x1, x2, x3, x4) U22_ga(x0, x1, x2, x3) mergecC_in_gga(x0, x1) U23_gga(x0, x1, x2, x3, x4) U25_gga(x0, x1, x2, x3, x4) lecD_in_gg(x0, x1) U24_gga(x0, x1, x2, x3, x4) gtcE_in_gg(x0, x1) U26_gga(x0, x1, x2, x3, x4) U27_gg(x0, x1, x2) U28_gg(x0, x1, x2) We have to consider all (P,Q,R)-chains. ---------------------------------------- (50) QDPOrderProof (EQUIVALENT) We use the reduction pair processor [LPAR04,JAR06]. The following pairs can be oriented strictly and are deleted. MERGESORTB_IN_GA(.(X1, .(X2, X3))) -> U11_GA(X1, X2, X3, splitcA_in_gaa(X3)) U11_GA(X1, X2, X3, splitcA_out_gaa(X3, X5, X6)) -> MERGESORTB_IN_GA(.(X1, X5)) U11_GA(X1, X2, X3, splitcA_out_gaa(X3, X5, X6)) -> U13_GA(X1, X2, X3, X6, mergesortcB_in_ga(.(X1, X5))) U13_GA(X1, X2, X3, X6, mergesortcB_out_ga(.(X1, X5), X7)) -> MERGESORTB_IN_GA(.(X2, X6)) The remaining pairs can at least be oriented weakly. Used ordering: Combined order from the following AFS and order. MERGESORTB_IN_GA(x1) = MERGESORTB_IN_GA(x1) .(x1, x2) = .(x2) U11_GA(x1, x2, x3, x4) = U11_GA(x4) splitcA_in_gaa(x1) = splitcA_in_gaa(x1) splitcA_out_gaa(x1, x2, x3) = splitcA_out_gaa(x2, x3) U13_GA(x1, x2, x3, x4, x5) = U13_GA(x4, x5) mergesortcB_in_ga(x1) = mergesortcB_in_ga mergesortcB_out_ga(x1, x2) = mergesortcB_out_ga [] = [] U18_gaa(x1, x2, x3, x4) = U18_gaa(x3, x4) U19_ga(x1, x2, x3, x4) = U19_ga U20_ga(x1, x2, x3, x4, x5) = x5 U21_ga(x1, x2, x3, x4, x5) = x5 U22_ga(x1, x2, x3, x4) = U22_ga mergecC_in_gga(x1, x2) = mergecC_in_gga mergecC_out_gga(x1, x2, x3) = mergecC_out_gga(x1, x2) U23_gga(x1, x2, x3, x4, x5) = U23_gga(x2, x3, x4) lecD_in_gg(x1, x2) = lecD_in_gg U25_gga(x1, x2, x3, x4, x5) = U25_gga gtcE_in_gg(x1, x2) = gtcE_in_gg s(x1) = s(x1) U27_gg(x1, x2, x3) = U27_gg 0 = 0 lecD_out_gg(x1, x2) = lecD_out_gg(x1, x2) U24_gga(x1, x2, x3, x4, x5) = U24_gga(x5) U28_gg(x1, x2, x3) = U28_gg(x1, x2) gtcE_out_gg(x1, x2) = x2 U26_gga(x1, x2, x3, x4, x5) = U26_gga(x1, x2, x3, x4, x5) Recursive path order with status [RPO]. Quasi-Precedence: [._1, U11_GA_1, U13_GA_2, mergesortcB_in_ga, mergesortcB_out_ga, U18_gaa_2, U19_ga, U22_ga] > MERGESORTB_IN_GA_1 > splitcA_in_gaa_1 > [[], mergecC_out_gga_2] > splitcA_out_gaa_2 [._1, U11_GA_1, U13_GA_2, mergesortcB_in_ga, mergesortcB_out_ga, U18_gaa_2, U19_ga, U22_ga] > U23_gga_3 > [mergecC_in_gga, U25_gga] [._1, U11_GA_1, U13_GA_2, mergesortcB_in_ga, mergesortcB_out_ga, U18_gaa_2, U19_ga, U22_ga] > U23_gga_3 > U24_gga_1 [._1, U11_GA_1, U13_GA_2, mergesortcB_in_ga, mergesortcB_out_ga, U18_gaa_2, U19_ga, U22_ga] > [lecD_in_gg, gtcE_in_gg, 0, U28_gg_2] > lecD_out_gg_2 [s_1, U27_gg] > [lecD_in_gg, gtcE_in_gg, 0, U28_gg_2] > lecD_out_gg_2 U26_gga_5 > [[], mergecC_out_gga_2] > splitcA_out_gaa_2 Status: MERGESORTB_IN_GA_1: multiset status ._1: [1] U11_GA_1: [1] splitcA_in_gaa_1: multiset status splitcA_out_gaa_2: multiset status U13_GA_2: [1,2] mergesortcB_in_ga: [] mergesortcB_out_ga: [] []: multiset status U18_gaa_2: [2,1] U19_ga: [] U22_ga: [] mergecC_in_gga: [] mergecC_out_gga_2: multiset status U23_gga_3: multiset status lecD_in_gg: multiset status U25_gga: multiset status gtcE_in_gg: [] s_1: multiset status U27_gg: [] 0: multiset status lecD_out_gg_2: multiset status U24_gga_1: multiset status U28_gg_2: multiset status U26_gga_5: multiset status The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: splitcA_in_gaa([]) -> splitcA_out_gaa([], [], []) splitcA_in_gaa(.(X1, [])) -> splitcA_out_gaa(.(X1, []), .(X1, []), []) splitcA_in_gaa(.(X1, .(X2, X3))) -> U18_gaa(X1, X2, X3, splitcA_in_gaa(X3)) mergesortcB_in_ga(.(X1, [])) -> mergesortcB_out_ga(.(X1, []), .(X1, [])) mergesortcB_in_ga(.(X1, .(X2, X3))) -> U19_ga(X1, X2, X3, splitcA_in_gaa(X3)) U19_ga(X1, X2, X3, splitcA_out_gaa(X3, X5, X6)) -> U20_ga(X1, X2, X3, X6, mergesortcB_in_ga(.(X1, X5))) U20_ga(X1, X2, X3, X6, mergesortcB_out_ga(.(X1, X5), X7)) -> U21_ga(X1, X2, X3, X7, mergesortcB_in_ga(.(X2, X6))) U21_ga(X1, X2, X3, X7, mergesortcB_out_ga(.(X2, X6), X8)) -> U22_ga(X1, X2, X3, mergecC_in_gga(X7, X8)) U18_gaa(X1, X2, X3, splitcA_out_gaa(X3, X4, X5)) -> splitcA_out_gaa(.(X1, .(X2, X3)), .(X1, X4), .(X2, X5)) U22_ga(X1, X2, X3, mergecC_out_gga(X7, X8, X4)) -> mergesortcB_out_ga(.(X1, .(X2, X3)), X4) ---------------------------------------- (51) Obligation: Q DP problem: P is empty. The TRS R consists of the following rules: splitcA_in_gaa([]) -> splitcA_out_gaa([], [], []) splitcA_in_gaa(.(X1, [])) -> splitcA_out_gaa(.(X1, []), .(X1, []), []) splitcA_in_gaa(.(X1, .(X2, X3))) -> U18_gaa(X1, X2, X3, splitcA_in_gaa(X3)) mergesortcB_in_ga(.(X1, [])) -> mergesortcB_out_ga(.(X1, []), .(X1, [])) mergesortcB_in_ga(.(X1, .(X2, X3))) -> U19_ga(X1, X2, X3, splitcA_in_gaa(X3)) U18_gaa(X1, X2, X3, splitcA_out_gaa(X3, X4, X5)) -> splitcA_out_gaa(.(X1, .(X2, X3)), .(X1, X4), .(X2, X5)) U19_ga(X1, X2, X3, splitcA_out_gaa(X3, X5, X6)) -> U20_ga(X1, X2, X3, X6, mergesortcB_in_ga(.(X1, X5))) U20_ga(X1, X2, X3, X6, mergesortcB_out_ga(.(X1, X5), X7)) -> U21_ga(X1, X2, X3, X7, mergesortcB_in_ga(.(X2, X6))) U21_ga(X1, X2, X3, X7, mergesortcB_out_ga(.(X2, X6), X8)) -> U22_ga(X1, X2, X3, mergecC_in_gga(X7, X8)) U22_ga(X1, X2, X3, mergecC_out_gga(X7, X8, X4)) -> mergesortcB_out_ga(.(X1, .(X2, X3)), X4) mergecC_in_gga([], X1) -> mergecC_out_gga([], X1, X1) mergecC_in_gga(X1, []) -> mergecC_out_gga(X1, [], X1) mergecC_in_gga(.(X1, X2), .(X3, X4)) -> U23_gga(X1, X2, X3, X4, lecD_in_gg(X1, X3)) mergecC_in_gga(.(X1, X2), .(X3, X4)) -> U25_gga(X1, X2, X3, X4, gtcE_in_gg(X1, X3)) U23_gga(X1, X2, X3, X4, lecD_out_gg(X1, X3)) -> U24_gga(X1, X2, X3, X4, mergecC_in_gga(X2, .(X3, X4))) U25_gga(X1, X2, X3, X4, gtcE_out_gg(X1, X3)) -> U26_gga(X1, X2, X3, X4, mergecC_in_gga(.(X1, X2), X4)) lecD_in_gg(s(X1), s(X2)) -> U27_gg(X1, X2, lecD_in_gg(X1, X2)) lecD_in_gg(0, s(X1)) -> lecD_out_gg(0, s(X1)) lecD_in_gg(0, 0) -> lecD_out_gg(0, 0) U24_gga(X1, X2, X3, X4, mergecC_out_gga(X2, .(X3, X4), X5)) -> mergecC_out_gga(.(X1, X2), .(X3, X4), .(X1, X5)) gtcE_in_gg(s(X1), s(X2)) -> U28_gg(X1, X2, gtcE_in_gg(X1, X2)) gtcE_in_gg(s(X1), 0) -> gtcE_out_gg(s(X1), 0) U26_gga(X1, X2, X3, X4, mergecC_out_gga(.(X1, X2), X4, X5)) -> mergecC_out_gga(.(X1, X2), .(X3, X4), .(X3, X5)) U27_gg(X1, X2, lecD_out_gg(X1, X2)) -> lecD_out_gg(s(X1), s(X2)) U28_gg(X1, X2, gtcE_out_gg(X1, X2)) -> gtcE_out_gg(s(X1), s(X2)) The set Q consists of the following terms: splitcA_in_gaa(x0) mergesortcB_in_ga(x0) U18_gaa(x0, x1, x2, x3) U19_ga(x0, x1, x2, x3) U20_ga(x0, x1, x2, x3, x4) U21_ga(x0, x1, x2, x3, x4) U22_ga(x0, x1, x2, x3) mergecC_in_gga(x0, x1) U23_gga(x0, x1, x2, x3, x4) U25_gga(x0, x1, x2, x3, x4) lecD_in_gg(x0, x1) U24_gga(x0, x1, x2, x3, x4) gtcE_in_gg(x0, x1) U26_gga(x0, x1, x2, x3, x4) U27_gg(x0, x1, x2) U28_gg(x0, x1, x2) We have to consider all (P,Q,R)-chains. ---------------------------------------- (52) PisEmptyProof (EQUIVALENT) The TRS P is empty. Hence, there is no (P,Q,R) chain. ---------------------------------------- (53) YES