/export/starexec/sandbox2/solver/bin/starexec_run_standard /export/starexec/sandbox2/benchmark/theBenchmark.pl /export/starexec/sandbox2/output/output_files -------------------------------------------------------------------------------- YES proof of /export/starexec/sandbox2/benchmark/theBenchmark.pl # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty Left Termination of the query pattern mergesort(g,a) w.r.t. the given Prolog program could successfully be proven: (0) Prolog (1) PrologToTRSTransformerProof [SOUND, 35 ms] (2) QTRS (3) DependencyPairsProof [EQUIVALENT, 0 ms] (4) QDP (5) DependencyGraphProof [EQUIVALENT, 0 ms] (6) AND (7) QDP (8) UsableRulesProof [EQUIVALENT, 0 ms] (9) QDP (10) QDPSizeChangeProof [EQUIVALENT, 0 ms] (11) YES (12) QDP (13) UsableRulesProof [EQUIVALENT, 0 ms] (14) QDP (15) QDPSizeChangeProof [EQUIVALENT, 0 ms] (16) YES (17) QDP (18) QDPOrderProof [EQUIVALENT, 16 ms] (19) QDP (20) DependencyGraphProof [EQUIVALENT, 0 ms] (21) TRUE (22) QDP (23) UsableRulesProof [EQUIVALENT, 0 ms] (24) QDP (25) QDPSizeChangeProof [EQUIVALENT, 0 ms] (26) YES (27) QDP (28) QDPOrderProof [EQUIVALENT, 239 ms] (29) QDP (30) DependencyGraphProof [EQUIVALENT, 0 ms] (31) TRUE ---------------------------------------- (0) Obligation: Clauses: mergesort([], []). mergesort(.(X, []), .(X, [])). mergesort(.(X, .(Y, Xs)), Ys) :- ','(split(.(X, .(Y, Xs)), X1s, X2s), ','(mergesort(X1s, Y1s), ','(mergesort(X2s, Y2s), merge(Y1s, Y2s, Ys)))). split([], [], []). split(.(X, Xs), .(X, Ys), Zs) :- split(Xs, Zs, Ys). merge([], Xs, Xs). merge(Xs, [], Xs). merge(.(X, Xs), .(Y, Ys), .(X, Zs)) :- ','(le(X, Y), merge(Xs, .(Y, Ys), Zs)). merge(.(X, Xs), .(Y, Ys), .(Y, Zs)) :- ','(gt(X, Y), merge(.(X, Xs), Ys, Zs)). 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) PrologToTRSTransformerProof (SOUND) Transformed Prolog program to TRS. { "root": 3, "program": { "directives": [], "clauses": [ [ "(mergesort ([]) ([]))", null ], [ "(mergesort (. X ([])) (. X ([])))", null ], [ "(mergesort (. X (. Y Xs)) Ys)", "(',' (split (. X (. Y Xs)) X1s X2s) (',' (mergesort X1s Y1s) (',' (mergesort X2s Y2s) (merge Y1s Y2s Ys))))" ], [ "(split ([]) ([]) ([]))", null ], [ "(split (. X Xs) (. X Ys) Zs)", "(split Xs Zs Ys)" ], [ "(merge ([]) Xs Xs)", null ], [ "(merge Xs ([]) Xs)", null ], [ "(merge (. X Xs) (. Y Ys) (. X Zs))", "(',' (le X Y) (merge Xs (. Y Ys) Zs))" ], [ "(merge (. X Xs) (. Y Ys) (. Y Zs))", "(',' (gt X Y) (merge (. X Xs) Ys Zs))" ], [ "(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", "591": { "goal": [{ "clause": -1, "scope": -1, "term": "(mergesort T22 X25)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T22"], "free": ["X25"], "exprvars": [] } }, "196": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "592": { "goal": [{ "clause": -1, "scope": -1, "term": "(merge T44 T45 T20)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T44", "T45" ], "free": [], "exprvars": [] } }, "550": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "594": { "goal": [ { "clause": 5, "scope": 5, "term": "(merge T44 T45 T20)" }, { "clause": 6, "scope": 5, "term": "(merge T44 T45 T20)" }, { "clause": 7, "scope": 5, "term": "(merge T44 T45 T20)" }, { "clause": 8, "scope": 5, "term": "(merge T44 T45 T20)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T44", "T45" ], "free": [], "exprvars": [] } }, "551": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "750": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (gt T119 T121) (merge (. T119 T120) T122 T124))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T119", "T120", "T121", "T122" ], "free": [], "exprvars": [] } }, "597": { "goal": [{ "clause": 5, "scope": 5, "term": "(merge T44 T45 T20)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T44", "T45" ], "free": [], "exprvars": [] } }, "751": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "598": { "goal": [ { "clause": 6, "scope": 5, "term": "(merge T44 T45 T20)" }, { "clause": 7, "scope": 5, "term": "(merge T44 T45 T20)" }, { "clause": 8, "scope": 5, "term": "(merge T44 T45 T20)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T44", "T45" ], "free": [], "exprvars": [] } }, "631": { "goal": [{ "clause": -1, "scope": -1, "term": "(le T78 T80)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T78", "T80" ], "free": [], "exprvars": [] } }, "633": { "goal": [{ "clause": -1, "scope": -1, "term": "(merge T79 (. T80 T81) T83)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T79", "T80", "T81" ], "free": [], "exprvars": [] } }, "755": { "goal": [{ "clause": -1, "scope": -1, "term": "(gt T119 T121)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T119", "T121" ], "free": [], "exprvars": [] } }, "756": { "goal": [{ "clause": -1, "scope": -1, "term": "(merge (. T119 T120) T122 T124)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T119", "T120", "T122" ], "free": [], "exprvars": [] } }, "757": { "goal": [ { "clause": 9, "scope": 7, "term": "(gt T119 T121)" }, { "clause": 10, "scope": 7, "term": "(gt T119 T121)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T119", "T121" ], "free": [], "exprvars": [] } }, "758": { "goal": [{ "clause": 9, "scope": 7, "term": "(gt T119 T121)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T119", "T121" ], "free": [], "exprvars": [] } }, "638": { "goal": [ { "clause": 11, "scope": 6, "term": "(le T78 T80)" }, { "clause": 12, "scope": 6, "term": "(le T78 T80)" }, { "clause": 13, "scope": 6, "term": "(le T78 T80)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T78", "T80" ], "free": [], "exprvars": [] } }, "759": { "goal": [{ "clause": 10, "scope": 7, "term": "(gt T119 T121)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T119", "T121" ], "free": [], "exprvars": [] } }, "161": { "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": [] } }, "284": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (mergesort T21 X24) (',' (mergesort T22 X25) (merge X24 X25 T20)))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T21", "T22" ], "free": [ "X24", "X25" ], "exprvars": [] } }, "760": { "goal": [{ "clause": -1, "scope": -1, "term": "(gt T137 T138)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T137", "T138" ], "free": [], "exprvars": [] } }, "200": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "761": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "3": { "goal": [{ "clause": -1, "scope": -1, "term": "(mergesort T1 T2)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T1"], "free": [], "exprvars": [] } }, "201": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "762": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "202": { "goal": [{ "clause": 1, "scope": 1, "term": "(mergesort T1 T2)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T1"], "free": [], "exprvars": [] } }, "763": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "203": { "goal": [{ "clause": 2, "scope": 1, "term": "(mergesort T1 T2)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T1"], "free": [], "exprvars": [] } }, "764": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "600": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "644": { "goal": [{ "clause": 11, "scope": 6, "term": "(le T78 T80)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T78", "T80" ], "free": [], "exprvars": [] } }, "645": { "goal": [ { "clause": 12, "scope": 6, "term": "(le T78 T80)" }, { "clause": 13, "scope": 6, "term": "(le T78 T80)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T78", "T80" ], "free": [], "exprvars": [] } }, "602": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "207": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "208": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "604": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "209": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "606": { "goal": [{ "clause": 6, "scope": 5, "term": "(merge T44 T45 T20)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T44", "T45" ], "free": [], "exprvars": [] } }, "608": { "goal": [ { "clause": 7, "scope": 5, "term": "(merge T44 T45 T20)" }, { "clause": 8, "scope": 5, "term": "(merge T44 T45 T20)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T44", "T45" ], "free": [], "exprvars": [] } }, "650": { "goal": [{ "clause": -1, "scope": -1, "term": "(le T96 T97)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T96", "T97" ], "free": [], "exprvars": [] } }, "178": { "goal": [{ "clause": 0, "scope": 1, "term": "(mergesort T1 T2)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T1"], "free": [], "exprvars": [] } }, "651": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "212": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (split (. T16 (. T17 T18)) X22 X23) (',' (mergesort X22 X24) (',' (mergesort X23 X25) (merge X24 X25 T20))))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T16", "T17", "T18" ], "free": [ "X22", "X23", "X24", "X25" ], "exprvars": [] } }, "575": { "goal": [{ "clause": -1, "scope": -1, "term": "(split T43 X79 X78)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T43"], "free": [ "X78", "X79" ], "exprvars": [] } }, "213": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "576": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "533": { "goal": [{ "clause": -1, "scope": -1, "term": "(split T37 X61 X60)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T37"], "free": [ "X60", "X61" ], "exprvars": [] } }, "610": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "654": { "goal": [{ "clause": 12, "scope": 6, "term": "(le T78 T80)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T78", "T80" ], "free": [], "exprvars": [] } }, "655": { "goal": [{ "clause": 13, "scope": 6, "term": "(le T78 T80)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T78", "T80" ], "free": [], "exprvars": [] } }, "612": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "459": { "goal": [ { "clause": 3, "scope": 2, "term": "(split (. T16 (. T17 T18)) X22 X23)" }, { "clause": 4, "scope": 2, "term": "(split (. T16 (. T17 T18)) X22 X23)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T16", "T17", "T18" ], "free": [ "X22", "X23" ], "exprvars": [] } }, "537": { "goal": [ { "clause": 3, "scope": 4, "term": "(split T37 X61 X60)" }, { "clause": 4, "scope": 4, "term": "(split T37 X61 X60)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T37"], "free": [ "X60", "X61" ], "exprvars": [] } }, "614": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "658": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "615": { "goal": [{ "clause": 7, "scope": 5, "term": "(merge T44 T45 T20)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T44", "T45" ], "free": [], "exprvars": [] } }, "659": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "616": { "goal": [{ "clause": 8, "scope": 5, "term": "(merge T44 T45 T20)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T44", "T45" ], "free": [], "exprvars": [] } }, "739": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "181": { "goal": [ { "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": [] } }, "460": { "goal": [{ "clause": 4, "scope": 2, "term": "(split (. T16 (. T17 T18)) X22 X23)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T16", "T17", "T18" ], "free": [ "X22", "X23" ], "exprvars": [] } }, "583": { "goal": [{ "clause": -1, "scope": -1, "term": "(mergesort T21 X24)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T21"], "free": ["X24"], "exprvars": [] } }, "541": { "goal": [{ "clause": 3, "scope": 4, "term": "(split T37 X61 X60)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T37"], "free": [ "X60", "X61" ], "exprvars": [] } }, "585": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (mergesort T22 X25) (merge T44 X25 T20))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T22", "T44" ], "free": ["X25"], "exprvars": [] } }, "542": { "goal": [{ "clause": 4, "scope": 4, "term": "(split T37 X61 X60)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T37"], "free": [ "X60", "X61" ], "exprvars": [] } }, "740": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "741": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "269": { "goal": [{ "clause": -1, "scope": -1, "term": "(split (. T16 (. T17 T18)) X22 X23)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T16", "T17", "T18" ], "free": [ "X22", "X23" ], "exprvars": [] } }, "742": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "622": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (le T78 T80) (merge T79 (. T80 T81) T83))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T78", "T79", "T80", "T81" ], "free": [], "exprvars": [] } }, "548": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "625": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "505": { "goal": [{ "clause": -1, "scope": -1, "term": "(split (. T30 T31) X43 X42)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T30", "T31" ], "free": [ "X42", "X43" ], "exprvars": [] } }, "506": { "goal": [ { "clause": 3, "scope": 3, "term": "(split (. T30 T31) X43 X42)" }, { "clause": 4, "scope": 3, "term": "(split (. T30 T31) X43 X42)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T30", "T31" ], "free": [ "X42", "X43" ], "exprvars": [] } }, "509": { "goal": [{ "clause": 4, "scope": 3, "term": "(split (. T30 T31) X43 X42)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T30", "T31" ], "free": [ "X42", "X43" ], "exprvars": [] } } }, "edges": [ { "from": 3, "to": 161, "label": "CASE" }, { "from": 161, "to": 178, "label": "PARALLEL" }, { "from": 161, "to": 181, "label": "PARALLEL" }, { "from": 178, "to": 196, "label": "EVAL with clause\nmergesort([], []).\nand substitutionT1 -> [],\nT2 -> []" }, { "from": 178, "to": 200, "label": "EVAL-BACKTRACK" }, { "from": 181, "to": 202, "label": "PARALLEL" }, { "from": 181, "to": 203, "label": "PARALLEL" }, { "from": 196, "to": 201, "label": "SUCCESS" }, { "from": 202, "to": 207, "label": "EVAL with clause\nmergesort(.(X5, []), .(X5, [])).\nand substitutionX5 -> T7,\nT1 -> .(T7, []),\nT2 -> .(T7, [])" }, { "from": 202, "to": 208, "label": "EVAL-BACKTRACK" }, { "from": 203, "to": 212, "label": "EVAL with clause\nmergesort(.(X18, .(X19, X20)), X21) :- ','(split(.(X18, .(X19, X20)), X22, X23), ','(mergesort(X22, X24), ','(mergesort(X23, X25), merge(X24, X25, X21)))).\nand substitutionX18 -> T16,\nX19 -> T17,\nX20 -> T18,\nT1 -> .(T16, .(T17, T18)),\nT2 -> T20,\nX21 -> T20,\nT19 -> T20" }, { "from": 203, "to": 213, "label": "EVAL-BACKTRACK" }, { "from": 207, "to": 209, "label": "SUCCESS" }, { "from": 212, "to": 269, "label": "SPLIT 1" }, { "from": 212, "to": 284, "label": "SPLIT 2\nnew knowledge:\nT16 is ground\nT17 is ground\nT18 is ground\nT21 is ground\nT22 is ground\nreplacements:X22 -> T21,\nX23 -> T22" }, { "from": 269, "to": 459, "label": "CASE" }, { "from": 284, "to": 583, "label": "SPLIT 1" }, { "from": 284, "to": 585, "label": "SPLIT 2\nnew knowledge:\nT21 is ground\nT44 is ground\nreplacements:X24 -> T44" }, { "from": 459, "to": 460, "label": "BACKTRACK\nfor clause: split([], [], [])because of non-unification" }, { "from": 460, "to": 505, "label": "ONLY EVAL with clause\nsplit(.(X38, X39), .(X38, X40), X41) :- split(X39, X41, X40).\nand substitutionT16 -> T29,\nX38 -> T29,\nT17 -> T30,\nT18 -> T31,\nX39 -> .(T30, T31),\nX40 -> X42,\nX22 -> .(T29, X42),\nX23 -> X43,\nX41 -> X43" }, { "from": 505, "to": 506, "label": "CASE" }, { "from": 506, "to": 509, "label": "BACKTRACK\nfor clause: split([], [], [])because of non-unification" }, { "from": 509, "to": 533, "label": "ONLY EVAL with clause\nsplit(.(X56, X57), .(X56, X58), X59) :- split(X57, X59, X58).\nand substitutionT30 -> T36,\nX56 -> T36,\nT31 -> T37,\nX57 -> T37,\nX58 -> X60,\nX43 -> .(T36, X60),\nX42 -> X61,\nX59 -> X61" }, { "from": 533, "to": 537, "label": "CASE" }, { "from": 537, "to": 541, "label": "PARALLEL" }, { "from": 537, "to": 542, "label": "PARALLEL" }, { "from": 541, "to": 548, "label": "EVAL with clause\nsplit([], [], []).\nand substitutionT37 -> [],\nX61 -> [],\nX60 -> []" }, { "from": 541, "to": 550, "label": "EVAL-BACKTRACK" }, { "from": 542, "to": 575, "label": "EVAL with clause\nsplit(.(X74, X75), .(X74, X76), X77) :- split(X75, X77, X76).\nand substitutionX74 -> T42,\nX75 -> T43,\nT37 -> .(T42, T43),\nX76 -> X78,\nX61 -> .(T42, X78),\nX60 -> X79,\nX77 -> X79" }, { "from": 542, "to": 576, "label": "EVAL-BACKTRACK" }, { "from": 548, "to": 551, "label": "SUCCESS" }, { "from": 575, "to": 533, "label": "INSTANCE with matching:\nT37 -> T43\nX61 -> X79\nX60 -> X78" }, { "from": 583, "to": 3, "label": "INSTANCE with matching:\nT1 -> T21\nT2 -> X24" }, { "from": 585, "to": 591, "label": "SPLIT 1" }, { "from": 585, "to": 592, "label": "SPLIT 2\nnew knowledge:\nT22 is ground\nT45 is ground\nreplacements:X25 -> T45" }, { "from": 591, "to": 3, "label": "INSTANCE with matching:\nT1 -> T22\nT2 -> X25" }, { "from": 592, "to": 594, "label": "CASE" }, { "from": 594, "to": 597, "label": "PARALLEL" }, { "from": 594, "to": 598, "label": "PARALLEL" }, { "from": 597, "to": 600, "label": "EVAL with clause\nmerge([], X86, X86).\nand substitutionT44 -> [],\nT45 -> T52,\nX86 -> T52,\nT20 -> T52" }, { "from": 597, "to": 602, "label": "EVAL-BACKTRACK" }, { "from": 598, "to": 606, "label": "PARALLEL" }, { "from": 598, "to": 608, "label": "PARALLEL" }, { "from": 600, "to": 604, "label": "SUCCESS" }, { "from": 606, "to": 610, "label": "EVAL with clause\nmerge(X91, [], X91).\nand substitutionT44 -> T57,\nX91 -> T57,\nT45 -> [],\nT20 -> T57" }, { "from": 606, "to": 612, "label": "EVAL-BACKTRACK" }, { "from": 608, "to": 615, "label": "PARALLEL" }, { "from": 608, "to": 616, "label": "PARALLEL" }, { "from": 610, "to": 614, "label": "SUCCESS" }, { "from": 615, "to": 622, "label": "EVAL with clause\nmerge(.(X112, X113), .(X114, X115), .(X112, X116)) :- ','(le(X112, X114), merge(X113, .(X114, X115), X116)).\nand substitutionX112 -> T78,\nX113 -> T79,\nT44 -> .(T78, T79),\nX114 -> T80,\nX115 -> T81,\nT45 -> .(T80, T81),\nX116 -> T83,\nT20 -> .(T78, T83),\nT82 -> T83" }, { "from": 615, "to": 625, "label": "EVAL-BACKTRACK" }, { "from": 616, "to": 750, "label": "EVAL with clause\nmerge(.(X150, X151), .(X152, X153), .(X152, X154)) :- ','(gt(X150, X152), merge(.(X150, X151), X153, X154)).\nand substitutionX150 -> T119,\nX151 -> T120,\nT44 -> .(T119, T120),\nX152 -> T121,\nX153 -> T122,\nT45 -> .(T121, T122),\nX154 -> T124,\nT20 -> .(T121, T124),\nT123 -> T124" }, { "from": 616, "to": 751, "label": "EVAL-BACKTRACK" }, { "from": 622, "to": 631, "label": "SPLIT 1" }, { "from": 622, "to": 633, "label": "SPLIT 2\nnew knowledge:\nT78 is ground\nT80 is ground" }, { "from": 631, "to": 638, "label": "CASE" }, { "from": 633, "to": 592, "label": "INSTANCE with matching:\nT44 -> T79\nT45 -> .(T80, T81)\nT20 -> T83" }, { "from": 638, "to": 644, "label": "PARALLEL" }, { "from": 638, "to": 645, "label": "PARALLEL" }, { "from": 644, "to": 650, "label": "EVAL with clause\nle(s(X129), s(X130)) :- le(X129, X130).\nand substitutionX129 -> T96,\nT78 -> s(T96),\nX130 -> T97,\nT80 -> s(T97)" }, { "from": 644, "to": 651, "label": "EVAL-BACKTRACK" }, { "from": 645, "to": 654, "label": "PARALLEL" }, { "from": 645, "to": 655, "label": "PARALLEL" }, { "from": 650, "to": 631, "label": "INSTANCE with matching:\nT78 -> T96\nT80 -> T97" }, { "from": 654, "to": 658, "label": "EVAL with clause\nle(0, s(X137)).\nand substitutionT78 -> 0,\nX137 -> T104,\nT80 -> s(T104)" }, { "from": 654, "to": 659, "label": "EVAL-BACKTRACK" }, { "from": 655, "to": 740, "label": "EVAL with clause\nle(0, 0).\nand substitutionT78 -> 0,\nT80 -> 0" }, { "from": 655, "to": 741, "label": "EVAL-BACKTRACK" }, { "from": 658, "to": 739, "label": "SUCCESS" }, { "from": 740, "to": 742, "label": "SUCCESS" }, { "from": 750, "to": 755, "label": "SPLIT 1" }, { "from": 750, "to": 756, "label": "SPLIT 2\nnew knowledge:\nT119 is ground\nT121 is ground" }, { "from": 755, "to": 757, "label": "CASE" }, { "from": 756, "to": 592, "label": "INSTANCE with matching:\nT44 -> .(T119, T120)\nT45 -> T122\nT20 -> T124" }, { "from": 757, "to": 758, "label": "PARALLEL" }, { "from": 757, "to": 759, "label": "PARALLEL" }, { "from": 758, "to": 760, "label": "EVAL with clause\ngt(s(X167), s(X168)) :- gt(X167, X168).\nand substitutionX167 -> T137,\nT119 -> s(T137),\nX168 -> T138,\nT121 -> s(T138)" }, { "from": 758, "to": 761, "label": "EVAL-BACKTRACK" }, { "from": 759, "to": 762, "label": "EVAL with clause\ngt(s(X173), 0).\nand substitutionX173 -> T143,\nT119 -> s(T143),\nT121 -> 0" }, { "from": 759, "to": 763, "label": "EVAL-BACKTRACK" }, { "from": 760, "to": 755, "label": "INSTANCE with matching:\nT119 -> T137\nT121 -> T138" }, { "from": 762, "to": 764, "label": "SUCCESS" } ], "type": "Graph" } } ---------------------------------------- (2) Obligation: Q restricted rewrite system: The TRS R consists of the following rules: f3_in([]) -> f3_out1([]) f3_in(.(T7, [])) -> f3_out1(.(T7, [])) f3_in(.(T16, .(T17, T18))) -> U1(f212_in(T16, T17, T18), .(T16, .(T17, T18))) U1(f212_out1(X22, X23, X24, X25, T20), .(T16, .(T17, T18))) -> f3_out1(T20) f533_in([]) -> f533_out1([], []) f533_in(.(T42, T43)) -> U2(f533_in(T43), .(T42, T43)) U2(f533_out1(X79, X78), .(T42, T43)) -> f533_out1(.(T42, X78), X79) f592_in([], T52) -> f592_out1(T52) f592_in(T57, []) -> f592_out1(T57) f592_in(.(T78, T79), .(T80, T81)) -> U3(f622_in(T78, T80, T79, T81), .(T78, T79), .(T80, T81)) U3(f622_out1(T83), .(T78, T79), .(T80, T81)) -> f592_out1(.(T78, T83)) f592_in(.(T119, T120), .(T121, T122)) -> U4(f750_in(T119, T121, T120, T122), .(T119, T120), .(T121, T122)) U4(f750_out1(T124), .(T119, T120), .(T121, T122)) -> f592_out1(.(T121, T124)) f631_in(s(T96), s(T97)) -> U5(f631_in(T96, T97), s(T96), s(T97)) U5(f631_out1, s(T96), s(T97)) -> f631_out1 f631_in(0, s(T104)) -> f631_out1 f631_in(0, 0) -> f631_out1 f755_in(s(T137), s(T138)) -> U6(f755_in(T137, T138), s(T137), s(T138)) U6(f755_out1, s(T137), s(T138)) -> f755_out1 f755_in(s(T143), 0) -> f755_out1 f269_in(T29, T36, T37) -> U7(f533_in(T37), T29, T36, T37) U7(f533_out1(X61, X60), T29, T36, T37) -> f269_out1(.(T29, X61), .(T36, X60)) f212_in(T16, T17, T18) -> U8(f269_in(T16, T17, T18), T16, T17, T18) U8(f269_out1(T21, T22), T16, T17, T18) -> U9(f284_in(T21, T22), T16, T17, T18, T21, T22) U9(f284_out1(X24, X25, T20), T16, T17, T18, T21, T22) -> f212_out1(T21, T22, X24, X25, T20) f284_in(T21, T22) -> U10(f3_in(T21), T21, T22) U10(f3_out1(T44), T21, T22) -> U11(f585_in(T22, T44), T21, T22, T44) U11(f585_out1(X25, T20), T21, T22, T44) -> f284_out1(T44, X25, T20) f585_in(T22, T44) -> U12(f3_in(T22), T22, T44) U12(f3_out1(T45), T22, T44) -> U13(f592_in(T44, T45), T22, T44, T45) U13(f592_out1(T20), T22, T44, T45) -> f585_out1(T45, T20) f622_in(T78, T80, T79, T81) -> U14(f631_in(T78, T80), T78, T80, T79, T81) U14(f631_out1, T78, T80, T79, T81) -> U15(f592_in(T79, .(T80, T81)), T78, T80, T79, T81) U15(f592_out1(T83), T78, T80, T79, T81) -> f622_out1(T83) f750_in(T119, T121, T120, T122) -> U16(f755_in(T119, T121), T119, T121, T120, T122) U16(f755_out1, T119, T121, T120, T122) -> U17(f592_in(.(T119, T120), T122), T119, T121, T120, T122) U17(f592_out1(T124), T119, T121, T120, T122) -> f750_out1(T124) Q is empty. ---------------------------------------- (3) DependencyPairsProof (EQUIVALENT) Using Dependency Pairs [AG00,LPAR04] we result in the following initial DP problem. ---------------------------------------- (4) Obligation: Q DP problem: The TRS P consists of the following rules: F3_IN(.(T16, .(T17, T18))) -> U1^1(f212_in(T16, T17, T18), .(T16, .(T17, T18))) F3_IN(.(T16, .(T17, T18))) -> F212_IN(T16, T17, T18) F533_IN(.(T42, T43)) -> U2^1(f533_in(T43), .(T42, T43)) F533_IN(.(T42, T43)) -> F533_IN(T43) F592_IN(.(T78, T79), .(T80, T81)) -> U3^1(f622_in(T78, T80, T79, T81), .(T78, T79), .(T80, T81)) F592_IN(.(T78, T79), .(T80, T81)) -> F622_IN(T78, T80, T79, T81) F592_IN(.(T119, T120), .(T121, T122)) -> U4^1(f750_in(T119, T121, T120, T122), .(T119, T120), .(T121, T122)) F592_IN(.(T119, T120), .(T121, T122)) -> F750_IN(T119, T121, T120, T122) F631_IN(s(T96), s(T97)) -> U5^1(f631_in(T96, T97), s(T96), s(T97)) F631_IN(s(T96), s(T97)) -> F631_IN(T96, T97) F755_IN(s(T137), s(T138)) -> U6^1(f755_in(T137, T138), s(T137), s(T138)) F755_IN(s(T137), s(T138)) -> F755_IN(T137, T138) F269_IN(T29, T36, T37) -> U7^1(f533_in(T37), T29, T36, T37) F269_IN(T29, T36, T37) -> F533_IN(T37) F212_IN(T16, T17, T18) -> U8^1(f269_in(T16, T17, T18), T16, T17, T18) F212_IN(T16, T17, T18) -> F269_IN(T16, T17, T18) U8^1(f269_out1(T21, T22), T16, T17, T18) -> U9^1(f284_in(T21, T22), T16, T17, T18, T21, T22) U8^1(f269_out1(T21, T22), T16, T17, T18) -> F284_IN(T21, T22) F284_IN(T21, T22) -> U10^1(f3_in(T21), T21, T22) F284_IN(T21, T22) -> F3_IN(T21) U10^1(f3_out1(T44), T21, T22) -> U11^1(f585_in(T22, T44), T21, T22, T44) U10^1(f3_out1(T44), T21, T22) -> F585_IN(T22, T44) F585_IN(T22, T44) -> U12^1(f3_in(T22), T22, T44) F585_IN(T22, T44) -> F3_IN(T22) U12^1(f3_out1(T45), T22, T44) -> U13^1(f592_in(T44, T45), T22, T44, T45) U12^1(f3_out1(T45), T22, T44) -> F592_IN(T44, T45) F622_IN(T78, T80, T79, T81) -> U14^1(f631_in(T78, T80), T78, T80, T79, T81) F622_IN(T78, T80, T79, T81) -> F631_IN(T78, T80) U14^1(f631_out1, T78, T80, T79, T81) -> U15^1(f592_in(T79, .(T80, T81)), T78, T80, T79, T81) U14^1(f631_out1, T78, T80, T79, T81) -> F592_IN(T79, .(T80, T81)) F750_IN(T119, T121, T120, T122) -> U16^1(f755_in(T119, T121), T119, T121, T120, T122) F750_IN(T119, T121, T120, T122) -> F755_IN(T119, T121) U16^1(f755_out1, T119, T121, T120, T122) -> U17^1(f592_in(.(T119, T120), T122), T119, T121, T120, T122) U16^1(f755_out1, T119, T121, T120, T122) -> F592_IN(.(T119, T120), T122) The TRS R consists of the following rules: f3_in([]) -> f3_out1([]) f3_in(.(T7, [])) -> f3_out1(.(T7, [])) f3_in(.(T16, .(T17, T18))) -> U1(f212_in(T16, T17, T18), .(T16, .(T17, T18))) U1(f212_out1(X22, X23, X24, X25, T20), .(T16, .(T17, T18))) -> f3_out1(T20) f533_in([]) -> f533_out1([], []) f533_in(.(T42, T43)) -> U2(f533_in(T43), .(T42, T43)) U2(f533_out1(X79, X78), .(T42, T43)) -> f533_out1(.(T42, X78), X79) f592_in([], T52) -> f592_out1(T52) f592_in(T57, []) -> f592_out1(T57) f592_in(.(T78, T79), .(T80, T81)) -> U3(f622_in(T78, T80, T79, T81), .(T78, T79), .(T80, T81)) U3(f622_out1(T83), .(T78, T79), .(T80, T81)) -> f592_out1(.(T78, T83)) f592_in(.(T119, T120), .(T121, T122)) -> U4(f750_in(T119, T121, T120, T122), .(T119, T120), .(T121, T122)) U4(f750_out1(T124), .(T119, T120), .(T121, T122)) -> f592_out1(.(T121, T124)) f631_in(s(T96), s(T97)) -> U5(f631_in(T96, T97), s(T96), s(T97)) U5(f631_out1, s(T96), s(T97)) -> f631_out1 f631_in(0, s(T104)) -> f631_out1 f631_in(0, 0) -> f631_out1 f755_in(s(T137), s(T138)) -> U6(f755_in(T137, T138), s(T137), s(T138)) U6(f755_out1, s(T137), s(T138)) -> f755_out1 f755_in(s(T143), 0) -> f755_out1 f269_in(T29, T36, T37) -> U7(f533_in(T37), T29, T36, T37) U7(f533_out1(X61, X60), T29, T36, T37) -> f269_out1(.(T29, X61), .(T36, X60)) f212_in(T16, T17, T18) -> U8(f269_in(T16, T17, T18), T16, T17, T18) U8(f269_out1(T21, T22), T16, T17, T18) -> U9(f284_in(T21, T22), T16, T17, T18, T21, T22) U9(f284_out1(X24, X25, T20), T16, T17, T18, T21, T22) -> f212_out1(T21, T22, X24, X25, T20) f284_in(T21, T22) -> U10(f3_in(T21), T21, T22) U10(f3_out1(T44), T21, T22) -> U11(f585_in(T22, T44), T21, T22, T44) U11(f585_out1(X25, T20), T21, T22, T44) -> f284_out1(T44, X25, T20) f585_in(T22, T44) -> U12(f3_in(T22), T22, T44) U12(f3_out1(T45), T22, T44) -> U13(f592_in(T44, T45), T22, T44, T45) U13(f592_out1(T20), T22, T44, T45) -> f585_out1(T45, T20) f622_in(T78, T80, T79, T81) -> U14(f631_in(T78, T80), T78, T80, T79, T81) U14(f631_out1, T78, T80, T79, T81) -> U15(f592_in(T79, .(T80, T81)), T78, T80, T79, T81) U15(f592_out1(T83), T78, T80, T79, T81) -> f622_out1(T83) f750_in(T119, T121, T120, T122) -> U16(f755_in(T119, T121), T119, T121, T120, T122) U16(f755_out1, T119, T121, T120, T122) -> U17(f592_in(.(T119, T120), T122), T119, T121, T120, T122) U17(f592_out1(T124), T119, T121, T120, T122) -> f750_out1(T124) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (5) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 5 SCCs with 18 less nodes. ---------------------------------------- (6) Complex Obligation (AND) ---------------------------------------- (7) Obligation: Q DP problem: The TRS P consists of the following rules: F755_IN(s(T137), s(T138)) -> F755_IN(T137, T138) The TRS R consists of the following rules: f3_in([]) -> f3_out1([]) f3_in(.(T7, [])) -> f3_out1(.(T7, [])) f3_in(.(T16, .(T17, T18))) -> U1(f212_in(T16, T17, T18), .(T16, .(T17, T18))) U1(f212_out1(X22, X23, X24, X25, T20), .(T16, .(T17, T18))) -> f3_out1(T20) f533_in([]) -> f533_out1([], []) f533_in(.(T42, T43)) -> U2(f533_in(T43), .(T42, T43)) U2(f533_out1(X79, X78), .(T42, T43)) -> f533_out1(.(T42, X78), X79) f592_in([], T52) -> f592_out1(T52) f592_in(T57, []) -> f592_out1(T57) f592_in(.(T78, T79), .(T80, T81)) -> U3(f622_in(T78, T80, T79, T81), .(T78, T79), .(T80, T81)) U3(f622_out1(T83), .(T78, T79), .(T80, T81)) -> f592_out1(.(T78, T83)) f592_in(.(T119, T120), .(T121, T122)) -> U4(f750_in(T119, T121, T120, T122), .(T119, T120), .(T121, T122)) U4(f750_out1(T124), .(T119, T120), .(T121, T122)) -> f592_out1(.(T121, T124)) f631_in(s(T96), s(T97)) -> U5(f631_in(T96, T97), s(T96), s(T97)) U5(f631_out1, s(T96), s(T97)) -> f631_out1 f631_in(0, s(T104)) -> f631_out1 f631_in(0, 0) -> f631_out1 f755_in(s(T137), s(T138)) -> U6(f755_in(T137, T138), s(T137), s(T138)) U6(f755_out1, s(T137), s(T138)) -> f755_out1 f755_in(s(T143), 0) -> f755_out1 f269_in(T29, T36, T37) -> U7(f533_in(T37), T29, T36, T37) U7(f533_out1(X61, X60), T29, T36, T37) -> f269_out1(.(T29, X61), .(T36, X60)) f212_in(T16, T17, T18) -> U8(f269_in(T16, T17, T18), T16, T17, T18) U8(f269_out1(T21, T22), T16, T17, T18) -> U9(f284_in(T21, T22), T16, T17, T18, T21, T22) U9(f284_out1(X24, X25, T20), T16, T17, T18, T21, T22) -> f212_out1(T21, T22, X24, X25, T20) f284_in(T21, T22) -> U10(f3_in(T21), T21, T22) U10(f3_out1(T44), T21, T22) -> U11(f585_in(T22, T44), T21, T22, T44) U11(f585_out1(X25, T20), T21, T22, T44) -> f284_out1(T44, X25, T20) f585_in(T22, T44) -> U12(f3_in(T22), T22, T44) U12(f3_out1(T45), T22, T44) -> U13(f592_in(T44, T45), T22, T44, T45) U13(f592_out1(T20), T22, T44, T45) -> f585_out1(T45, T20) f622_in(T78, T80, T79, T81) -> U14(f631_in(T78, T80), T78, T80, T79, T81) U14(f631_out1, T78, T80, T79, T81) -> U15(f592_in(T79, .(T80, T81)), T78, T80, T79, T81) U15(f592_out1(T83), T78, T80, T79, T81) -> f622_out1(T83) f750_in(T119, T121, T120, T122) -> U16(f755_in(T119, T121), T119, T121, T120, T122) U16(f755_out1, T119, T121, T120, T122) -> U17(f592_in(.(T119, T120), T122), T119, T121, T120, T122) U17(f592_out1(T124), T119, T121, T120, T122) -> f750_out1(T124) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (8) UsableRulesProof (EQUIVALENT) We can use the usable rules and reduction pair processor [LPAR04] with the Ce-compatible extension of the polynomial order that maps every function symbol to the sum of its arguments. Then, we can delete all non-usable rules [FROCOS05] from R. ---------------------------------------- (9) Obligation: Q DP problem: The TRS P consists of the following rules: F755_IN(s(T137), s(T138)) -> F755_IN(T137, T138) R is empty. Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (10) QDPSizeChangeProof (EQUIVALENT) By using the subterm criterion [SUBTERM_CRITERION] together with the size-change analysis [AAECC05] we have proven that there are no infinite chains for this DP problem. From the DPs we obtained the following set of size-change graphs: *F755_IN(s(T137), s(T138)) -> F755_IN(T137, T138) The graph contains the following edges 1 > 1, 2 > 2 ---------------------------------------- (11) YES ---------------------------------------- (12) Obligation: Q DP problem: The TRS P consists of the following rules: F631_IN(s(T96), s(T97)) -> F631_IN(T96, T97) The TRS R consists of the following rules: f3_in([]) -> f3_out1([]) f3_in(.(T7, [])) -> f3_out1(.(T7, [])) f3_in(.(T16, .(T17, T18))) -> U1(f212_in(T16, T17, T18), .(T16, .(T17, T18))) U1(f212_out1(X22, X23, X24, X25, T20), .(T16, .(T17, T18))) -> f3_out1(T20) f533_in([]) -> f533_out1([], []) f533_in(.(T42, T43)) -> U2(f533_in(T43), .(T42, T43)) U2(f533_out1(X79, X78), .(T42, T43)) -> f533_out1(.(T42, X78), X79) f592_in([], T52) -> f592_out1(T52) f592_in(T57, []) -> f592_out1(T57) f592_in(.(T78, T79), .(T80, T81)) -> U3(f622_in(T78, T80, T79, T81), .(T78, T79), .(T80, T81)) U3(f622_out1(T83), .(T78, T79), .(T80, T81)) -> f592_out1(.(T78, T83)) f592_in(.(T119, T120), .(T121, T122)) -> U4(f750_in(T119, T121, T120, T122), .(T119, T120), .(T121, T122)) U4(f750_out1(T124), .(T119, T120), .(T121, T122)) -> f592_out1(.(T121, T124)) f631_in(s(T96), s(T97)) -> U5(f631_in(T96, T97), s(T96), s(T97)) U5(f631_out1, s(T96), s(T97)) -> f631_out1 f631_in(0, s(T104)) -> f631_out1 f631_in(0, 0) -> f631_out1 f755_in(s(T137), s(T138)) -> U6(f755_in(T137, T138), s(T137), s(T138)) U6(f755_out1, s(T137), s(T138)) -> f755_out1 f755_in(s(T143), 0) -> f755_out1 f269_in(T29, T36, T37) -> U7(f533_in(T37), T29, T36, T37) U7(f533_out1(X61, X60), T29, T36, T37) -> f269_out1(.(T29, X61), .(T36, X60)) f212_in(T16, T17, T18) -> U8(f269_in(T16, T17, T18), T16, T17, T18) U8(f269_out1(T21, T22), T16, T17, T18) -> U9(f284_in(T21, T22), T16, T17, T18, T21, T22) U9(f284_out1(X24, X25, T20), T16, T17, T18, T21, T22) -> f212_out1(T21, T22, X24, X25, T20) f284_in(T21, T22) -> U10(f3_in(T21), T21, T22) U10(f3_out1(T44), T21, T22) -> U11(f585_in(T22, T44), T21, T22, T44) U11(f585_out1(X25, T20), T21, T22, T44) -> f284_out1(T44, X25, T20) f585_in(T22, T44) -> U12(f3_in(T22), T22, T44) U12(f3_out1(T45), T22, T44) -> U13(f592_in(T44, T45), T22, T44, T45) U13(f592_out1(T20), T22, T44, T45) -> f585_out1(T45, T20) f622_in(T78, T80, T79, T81) -> U14(f631_in(T78, T80), T78, T80, T79, T81) U14(f631_out1, T78, T80, T79, T81) -> U15(f592_in(T79, .(T80, T81)), T78, T80, T79, T81) U15(f592_out1(T83), T78, T80, T79, T81) -> f622_out1(T83) f750_in(T119, T121, T120, T122) -> U16(f755_in(T119, T121), T119, T121, T120, T122) U16(f755_out1, T119, T121, T120, T122) -> U17(f592_in(.(T119, T120), T122), T119, T121, T120, T122) U17(f592_out1(T124), T119, T121, T120, T122) -> f750_out1(T124) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (13) UsableRulesProof (EQUIVALENT) We can use the usable rules and reduction pair processor [LPAR04] with the Ce-compatible extension of the polynomial order that maps every function symbol to the sum of its arguments. Then, we can delete all non-usable rules [FROCOS05] from R. ---------------------------------------- (14) Obligation: Q DP problem: The TRS P consists of the following rules: F631_IN(s(T96), s(T97)) -> F631_IN(T96, T97) R is empty. Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (15) 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: *F631_IN(s(T96), s(T97)) -> F631_IN(T96, T97) The graph contains the following edges 1 > 1, 2 > 2 ---------------------------------------- (16) YES ---------------------------------------- (17) Obligation: Q DP problem: The TRS P consists of the following rules: F592_IN(.(T78, T79), .(T80, T81)) -> F622_IN(T78, T80, T79, T81) F622_IN(T78, T80, T79, T81) -> U14^1(f631_in(T78, T80), T78, T80, T79, T81) U14^1(f631_out1, T78, T80, T79, T81) -> F592_IN(T79, .(T80, T81)) F592_IN(.(T119, T120), .(T121, T122)) -> F750_IN(T119, T121, T120, T122) F750_IN(T119, T121, T120, T122) -> U16^1(f755_in(T119, T121), T119, T121, T120, T122) U16^1(f755_out1, T119, T121, T120, T122) -> F592_IN(.(T119, T120), T122) The TRS R consists of the following rules: f3_in([]) -> f3_out1([]) f3_in(.(T7, [])) -> f3_out1(.(T7, [])) f3_in(.(T16, .(T17, T18))) -> U1(f212_in(T16, T17, T18), .(T16, .(T17, T18))) U1(f212_out1(X22, X23, X24, X25, T20), .(T16, .(T17, T18))) -> f3_out1(T20) f533_in([]) -> f533_out1([], []) f533_in(.(T42, T43)) -> U2(f533_in(T43), .(T42, T43)) U2(f533_out1(X79, X78), .(T42, T43)) -> f533_out1(.(T42, X78), X79) f592_in([], T52) -> f592_out1(T52) f592_in(T57, []) -> f592_out1(T57) f592_in(.(T78, T79), .(T80, T81)) -> U3(f622_in(T78, T80, T79, T81), .(T78, T79), .(T80, T81)) U3(f622_out1(T83), .(T78, T79), .(T80, T81)) -> f592_out1(.(T78, T83)) f592_in(.(T119, T120), .(T121, T122)) -> U4(f750_in(T119, T121, T120, T122), .(T119, T120), .(T121, T122)) U4(f750_out1(T124), .(T119, T120), .(T121, T122)) -> f592_out1(.(T121, T124)) f631_in(s(T96), s(T97)) -> U5(f631_in(T96, T97), s(T96), s(T97)) U5(f631_out1, s(T96), s(T97)) -> f631_out1 f631_in(0, s(T104)) -> f631_out1 f631_in(0, 0) -> f631_out1 f755_in(s(T137), s(T138)) -> U6(f755_in(T137, T138), s(T137), s(T138)) U6(f755_out1, s(T137), s(T138)) -> f755_out1 f755_in(s(T143), 0) -> f755_out1 f269_in(T29, T36, T37) -> U7(f533_in(T37), T29, T36, T37) U7(f533_out1(X61, X60), T29, T36, T37) -> f269_out1(.(T29, X61), .(T36, X60)) f212_in(T16, T17, T18) -> U8(f269_in(T16, T17, T18), T16, T17, T18) U8(f269_out1(T21, T22), T16, T17, T18) -> U9(f284_in(T21, T22), T16, T17, T18, T21, T22) U9(f284_out1(X24, X25, T20), T16, T17, T18, T21, T22) -> f212_out1(T21, T22, X24, X25, T20) f284_in(T21, T22) -> U10(f3_in(T21), T21, T22) U10(f3_out1(T44), T21, T22) -> U11(f585_in(T22, T44), T21, T22, T44) U11(f585_out1(X25, T20), T21, T22, T44) -> f284_out1(T44, X25, T20) f585_in(T22, T44) -> U12(f3_in(T22), T22, T44) U12(f3_out1(T45), T22, T44) -> U13(f592_in(T44, T45), T22, T44, T45) U13(f592_out1(T20), T22, T44, T45) -> f585_out1(T45, T20) f622_in(T78, T80, T79, T81) -> U14(f631_in(T78, T80), T78, T80, T79, T81) U14(f631_out1, T78, T80, T79, T81) -> U15(f592_in(T79, .(T80, T81)), T78, T80, T79, T81) U15(f592_out1(T83), T78, T80, T79, T81) -> f622_out1(T83) f750_in(T119, T121, T120, T122) -> U16(f755_in(T119, T121), T119, T121, T120, T122) U16(f755_out1, T119, T121, T120, T122) -> U17(f592_in(.(T119, T120), T122), T119, T121, T120, T122) U17(f592_out1(T124), T119, T121, T120, T122) -> f750_out1(T124) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (18) QDPOrderProof (EQUIVALENT) We use the reduction pair processor [LPAR04,JAR06]. The following pairs can be oriented strictly and are deleted. F592_IN(.(T78, T79), .(T80, T81)) -> F622_IN(T78, T80, T79, T81) F592_IN(.(T119, T120), .(T121, T122)) -> F750_IN(T119, T121, T120, T122) U16^1(f755_out1, T119, T121, T120, T122) -> F592_IN(.(T119, T120), T122) The remaining pairs can at least be oriented weakly. Used ordering: Polynomial Order [NEGPOLO,POLO] with Interpretation: POL( U14^1_5(x_1, ..., x_5) ) = x_1 + 2x_3 + 2x_4 + 2x_5 + 2 POL( f631_in_2(x_1, x_2) ) = x_1 POL( s_1(x_1) ) = 2x_1 + 2 POL( U5_3(x_1, ..., x_3) ) = 2 POL( 0 ) = 2 POL( f631_out1 ) = 2 POL( U16^1_5(x_1, ..., x_5) ) = 2x_1 + 2x_2 + 2x_4 + 2x_5 + 2 POL( f755_in_2(x_1, x_2) ) = x_2 POL( U6_3(x_1, ..., x_3) ) = max{0, 2x_1 - 2} POL( f755_out1 ) = 2 POL( F592_IN_2(x_1, x_2) ) = 2x_1 + 2x_2 POL( ._2(x_1, x_2) ) = x_1 + x_2 + 2 POL( F622_IN_4(x_1, ..., x_4) ) = x_1 + 2x_2 + 2x_3 + 2x_4 + 2 POL( F750_IN_4(x_1, ..., x_4) ) = 2x_1 + 2x_2 + 2x_3 + 2x_4 + 2 The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: f631_in(s(T96), s(T97)) -> U5(f631_in(T96, T97), s(T96), s(T97)) f631_in(0, s(T104)) -> f631_out1 f631_in(0, 0) -> f631_out1 f755_in(s(T137), s(T138)) -> U6(f755_in(T137, T138), s(T137), s(T138)) f755_in(s(T143), 0) -> f755_out1 U5(f631_out1, s(T96), s(T97)) -> f631_out1 U6(f755_out1, s(T137), s(T138)) -> f755_out1 ---------------------------------------- (19) Obligation: Q DP problem: The TRS P consists of the following rules: F622_IN(T78, T80, T79, T81) -> U14^1(f631_in(T78, T80), T78, T80, T79, T81) U14^1(f631_out1, T78, T80, T79, T81) -> F592_IN(T79, .(T80, T81)) F750_IN(T119, T121, T120, T122) -> U16^1(f755_in(T119, T121), T119, T121, T120, T122) The TRS R consists of the following rules: f3_in([]) -> f3_out1([]) f3_in(.(T7, [])) -> f3_out1(.(T7, [])) f3_in(.(T16, .(T17, T18))) -> U1(f212_in(T16, T17, T18), .(T16, .(T17, T18))) U1(f212_out1(X22, X23, X24, X25, T20), .(T16, .(T17, T18))) -> f3_out1(T20) f533_in([]) -> f533_out1([], []) f533_in(.(T42, T43)) -> U2(f533_in(T43), .(T42, T43)) U2(f533_out1(X79, X78), .(T42, T43)) -> f533_out1(.(T42, X78), X79) f592_in([], T52) -> f592_out1(T52) f592_in(T57, []) -> f592_out1(T57) f592_in(.(T78, T79), .(T80, T81)) -> U3(f622_in(T78, T80, T79, T81), .(T78, T79), .(T80, T81)) U3(f622_out1(T83), .(T78, T79), .(T80, T81)) -> f592_out1(.(T78, T83)) f592_in(.(T119, T120), .(T121, T122)) -> U4(f750_in(T119, T121, T120, T122), .(T119, T120), .(T121, T122)) U4(f750_out1(T124), .(T119, T120), .(T121, T122)) -> f592_out1(.(T121, T124)) f631_in(s(T96), s(T97)) -> U5(f631_in(T96, T97), s(T96), s(T97)) U5(f631_out1, s(T96), s(T97)) -> f631_out1 f631_in(0, s(T104)) -> f631_out1 f631_in(0, 0) -> f631_out1 f755_in(s(T137), s(T138)) -> U6(f755_in(T137, T138), s(T137), s(T138)) U6(f755_out1, s(T137), s(T138)) -> f755_out1 f755_in(s(T143), 0) -> f755_out1 f269_in(T29, T36, T37) -> U7(f533_in(T37), T29, T36, T37) U7(f533_out1(X61, X60), T29, T36, T37) -> f269_out1(.(T29, X61), .(T36, X60)) f212_in(T16, T17, T18) -> U8(f269_in(T16, T17, T18), T16, T17, T18) U8(f269_out1(T21, T22), T16, T17, T18) -> U9(f284_in(T21, T22), T16, T17, T18, T21, T22) U9(f284_out1(X24, X25, T20), T16, T17, T18, T21, T22) -> f212_out1(T21, T22, X24, X25, T20) f284_in(T21, T22) -> U10(f3_in(T21), T21, T22) U10(f3_out1(T44), T21, T22) -> U11(f585_in(T22, T44), T21, T22, T44) U11(f585_out1(X25, T20), T21, T22, T44) -> f284_out1(T44, X25, T20) f585_in(T22, T44) -> U12(f3_in(T22), T22, T44) U12(f3_out1(T45), T22, T44) -> U13(f592_in(T44, T45), T22, T44, T45) U13(f592_out1(T20), T22, T44, T45) -> f585_out1(T45, T20) f622_in(T78, T80, T79, T81) -> U14(f631_in(T78, T80), T78, T80, T79, T81) U14(f631_out1, T78, T80, T79, T81) -> U15(f592_in(T79, .(T80, T81)), T78, T80, T79, T81) U15(f592_out1(T83), T78, T80, T79, T81) -> f622_out1(T83) f750_in(T119, T121, T120, T122) -> U16(f755_in(T119, T121), T119, T121, T120, T122) U16(f755_out1, T119, T121, T120, T122) -> U17(f592_in(.(T119, T120), T122), T119, T121, T120, T122) U17(f592_out1(T124), T119, T121, T120, T122) -> f750_out1(T124) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (20) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 0 SCCs with 3 less nodes. ---------------------------------------- (21) TRUE ---------------------------------------- (22) Obligation: Q DP problem: The TRS P consists of the following rules: F533_IN(.(T42, T43)) -> F533_IN(T43) The TRS R consists of the following rules: f3_in([]) -> f3_out1([]) f3_in(.(T7, [])) -> f3_out1(.(T7, [])) f3_in(.(T16, .(T17, T18))) -> U1(f212_in(T16, T17, T18), .(T16, .(T17, T18))) U1(f212_out1(X22, X23, X24, X25, T20), .(T16, .(T17, T18))) -> f3_out1(T20) f533_in([]) -> f533_out1([], []) f533_in(.(T42, T43)) -> U2(f533_in(T43), .(T42, T43)) U2(f533_out1(X79, X78), .(T42, T43)) -> f533_out1(.(T42, X78), X79) f592_in([], T52) -> f592_out1(T52) f592_in(T57, []) -> f592_out1(T57) f592_in(.(T78, T79), .(T80, T81)) -> U3(f622_in(T78, T80, T79, T81), .(T78, T79), .(T80, T81)) U3(f622_out1(T83), .(T78, T79), .(T80, T81)) -> f592_out1(.(T78, T83)) f592_in(.(T119, T120), .(T121, T122)) -> U4(f750_in(T119, T121, T120, T122), .(T119, T120), .(T121, T122)) U4(f750_out1(T124), .(T119, T120), .(T121, T122)) -> f592_out1(.(T121, T124)) f631_in(s(T96), s(T97)) -> U5(f631_in(T96, T97), s(T96), s(T97)) U5(f631_out1, s(T96), s(T97)) -> f631_out1 f631_in(0, s(T104)) -> f631_out1 f631_in(0, 0) -> f631_out1 f755_in(s(T137), s(T138)) -> U6(f755_in(T137, T138), s(T137), s(T138)) U6(f755_out1, s(T137), s(T138)) -> f755_out1 f755_in(s(T143), 0) -> f755_out1 f269_in(T29, T36, T37) -> U7(f533_in(T37), T29, T36, T37) U7(f533_out1(X61, X60), T29, T36, T37) -> f269_out1(.(T29, X61), .(T36, X60)) f212_in(T16, T17, T18) -> U8(f269_in(T16, T17, T18), T16, T17, T18) U8(f269_out1(T21, T22), T16, T17, T18) -> U9(f284_in(T21, T22), T16, T17, T18, T21, T22) U9(f284_out1(X24, X25, T20), T16, T17, T18, T21, T22) -> f212_out1(T21, T22, X24, X25, T20) f284_in(T21, T22) -> U10(f3_in(T21), T21, T22) U10(f3_out1(T44), T21, T22) -> U11(f585_in(T22, T44), T21, T22, T44) U11(f585_out1(X25, T20), T21, T22, T44) -> f284_out1(T44, X25, T20) f585_in(T22, T44) -> U12(f3_in(T22), T22, T44) U12(f3_out1(T45), T22, T44) -> U13(f592_in(T44, T45), T22, T44, T45) U13(f592_out1(T20), T22, T44, T45) -> f585_out1(T45, T20) f622_in(T78, T80, T79, T81) -> U14(f631_in(T78, T80), T78, T80, T79, T81) U14(f631_out1, T78, T80, T79, T81) -> U15(f592_in(T79, .(T80, T81)), T78, T80, T79, T81) U15(f592_out1(T83), T78, T80, T79, T81) -> f622_out1(T83) f750_in(T119, T121, T120, T122) -> U16(f755_in(T119, T121), T119, T121, T120, T122) U16(f755_out1, T119, T121, T120, T122) -> U17(f592_in(.(T119, T120), T122), T119, T121, T120, T122) U17(f592_out1(T124), T119, T121, T120, T122) -> f750_out1(T124) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (23) UsableRulesProof (EQUIVALENT) We can use the usable rules and reduction pair processor [LPAR04] with the Ce-compatible extension of the polynomial order that maps every function symbol to the sum of its arguments. Then, we can delete all non-usable rules [FROCOS05] from R. ---------------------------------------- (24) Obligation: Q DP problem: The TRS P consists of the following rules: F533_IN(.(T42, T43)) -> F533_IN(T43) R is empty. Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (25) 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: *F533_IN(.(T42, T43)) -> F533_IN(T43) The graph contains the following edges 1 > 1 ---------------------------------------- (26) YES ---------------------------------------- (27) Obligation: Q DP problem: The TRS P consists of the following rules: F3_IN(.(T16, .(T17, T18))) -> F212_IN(T16, T17, T18) F212_IN(T16, T17, T18) -> U8^1(f269_in(T16, T17, T18), T16, T17, T18) U8^1(f269_out1(T21, T22), T16, T17, T18) -> F284_IN(T21, T22) F284_IN(T21, T22) -> U10^1(f3_in(T21), T21, T22) U10^1(f3_out1(T44), T21, T22) -> F585_IN(T22, T44) F585_IN(T22, T44) -> F3_IN(T22) F284_IN(T21, T22) -> F3_IN(T21) The TRS R consists of the following rules: f3_in([]) -> f3_out1([]) f3_in(.(T7, [])) -> f3_out1(.(T7, [])) f3_in(.(T16, .(T17, T18))) -> U1(f212_in(T16, T17, T18), .(T16, .(T17, T18))) U1(f212_out1(X22, X23, X24, X25, T20), .(T16, .(T17, T18))) -> f3_out1(T20) f533_in([]) -> f533_out1([], []) f533_in(.(T42, T43)) -> U2(f533_in(T43), .(T42, T43)) U2(f533_out1(X79, X78), .(T42, T43)) -> f533_out1(.(T42, X78), X79) f592_in([], T52) -> f592_out1(T52) f592_in(T57, []) -> f592_out1(T57) f592_in(.(T78, T79), .(T80, T81)) -> U3(f622_in(T78, T80, T79, T81), .(T78, T79), .(T80, T81)) U3(f622_out1(T83), .(T78, T79), .(T80, T81)) -> f592_out1(.(T78, T83)) f592_in(.(T119, T120), .(T121, T122)) -> U4(f750_in(T119, T121, T120, T122), .(T119, T120), .(T121, T122)) U4(f750_out1(T124), .(T119, T120), .(T121, T122)) -> f592_out1(.(T121, T124)) f631_in(s(T96), s(T97)) -> U5(f631_in(T96, T97), s(T96), s(T97)) U5(f631_out1, s(T96), s(T97)) -> f631_out1 f631_in(0, s(T104)) -> f631_out1 f631_in(0, 0) -> f631_out1 f755_in(s(T137), s(T138)) -> U6(f755_in(T137, T138), s(T137), s(T138)) U6(f755_out1, s(T137), s(T138)) -> f755_out1 f755_in(s(T143), 0) -> f755_out1 f269_in(T29, T36, T37) -> U7(f533_in(T37), T29, T36, T37) U7(f533_out1(X61, X60), T29, T36, T37) -> f269_out1(.(T29, X61), .(T36, X60)) f212_in(T16, T17, T18) -> U8(f269_in(T16, T17, T18), T16, T17, T18) U8(f269_out1(T21, T22), T16, T17, T18) -> U9(f284_in(T21, T22), T16, T17, T18, T21, T22) U9(f284_out1(X24, X25, T20), T16, T17, T18, T21, T22) -> f212_out1(T21, T22, X24, X25, T20) f284_in(T21, T22) -> U10(f3_in(T21), T21, T22) U10(f3_out1(T44), T21, T22) -> U11(f585_in(T22, T44), T21, T22, T44) U11(f585_out1(X25, T20), T21, T22, T44) -> f284_out1(T44, X25, T20) f585_in(T22, T44) -> U12(f3_in(T22), T22, T44) U12(f3_out1(T45), T22, T44) -> U13(f592_in(T44, T45), T22, T44, T45) U13(f592_out1(T20), T22, T44, T45) -> f585_out1(T45, T20) f622_in(T78, T80, T79, T81) -> U14(f631_in(T78, T80), T78, T80, T79, T81) U14(f631_out1, T78, T80, T79, T81) -> U15(f592_in(T79, .(T80, T81)), T78, T80, T79, T81) U15(f592_out1(T83), T78, T80, T79, T81) -> f622_out1(T83) f750_in(T119, T121, T120, T122) -> U16(f755_in(T119, T121), T119, T121, T120, T122) U16(f755_out1, T119, T121, T120, T122) -> U17(f592_in(.(T119, T120), T122), T119, T121, T120, T122) U17(f592_out1(T124), T119, T121, T120, T122) -> f750_out1(T124) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (28) QDPOrderProof (EQUIVALENT) We use the reduction pair processor [LPAR04,JAR06]. The following pairs can be oriented strictly and are deleted. F3_IN(.(T16, .(T17, T18))) -> F212_IN(T16, T17, T18) The remaining pairs can at least be oriented weakly. Used ordering: Polynomial Order [NEGPOLO,POLO] with Interpretation: POL( U8^1_4(x_1, ..., x_4) ) = x_1 + 2 POL( U10^1_3(x_1, ..., x_3) ) = x_3 POL( U8_4(x_1, ..., x_4) ) = 2x_2 + 2 POL( f269_in_3(x_1, ..., x_3) ) = 2x_3 POL( U7_4(x_1, ..., x_4) ) = 2x_1 POL( f533_in_1(x_1) ) = x_1 POL( f3_in_1(x_1) ) = 0 POL( [] ) = 0 POL( f3_out1_1(x_1) ) = max{0, 2x_1 - 2} POL( ._2(x_1, x_2) ) = 2x_2 + 1 POL( U1_2(x_1, x_2) ) = 2x_1 + x_2 + 1 POL( f212_in_3(x_1, ..., x_3) ) = x_1 + 2x_2 + x_3 + 2 POL( f212_out1_5(x_1, ..., x_5) ) = 2x_1 + 2x_2 + 2x_3 + 2x_4 + 1 POL( f269_out1_2(x_1, x_2) ) = max{0, x_1 + x_2 - 2} POL( U9_6(x_1, ..., x_6) ) = 2x_5 + 2 POL( f284_in_2(x_1, x_2) ) = 0 POL( f284_out1_3(x_1, ..., x_3) ) = 2x_1 + x_3 + 2 POL( U10_3(x_1, ..., x_3) ) = 2 POL( U11_4(x_1, ..., x_4) ) = max{0, 2x_4 - 2} POL( f585_in_2(x_1, x_2) ) = 2x_1 + 1 POL( f585_out1_2(x_1, x_2) ) = 2x_1 + 2x_2 + 2 POL( U12_3(x_1, ..., x_3) ) = max{0, x_2 - 2} POL( U13_4(x_1, ..., x_4) ) = max{0, x_3 + 2x_4 - 2} POL( f592_in_2(x_1, x_2) ) = 0 POL( f533_out1_2(x_1, x_2) ) = x_1 + x_2 POL( U2_2(x_1, x_2) ) = 2x_1 + 1 POL( f592_out1_1(x_1) ) = 2 POL( U3_3(x_1, ..., x_3) ) = max{0, 2x_1 - 2} POL( f622_in_4(x_1, ..., x_4) ) = 2x_2 + 2 POL( U4_3(x_1, ..., x_3) ) = 2x_1 + 2x_2 + x_3 + 1 POL( f750_in_4(x_1, ..., x_4) ) = 2x_1 + 2x_2 + 2x_3 + 2 POL( f622_out1_1(x_1) ) = 1 POL( U14_5(x_1, ..., x_5) ) = max{0, x_4 + x_5 - 2} POL( f631_in_2(x_1, x_2) ) = 0 POL( s_1(x_1) ) = 2x_1 POL( U5_3(x_1, ..., x_3) ) = max{0, x_2 - 2} POL( 0 ) = 0 POL( f631_out1 ) = 0 POL( U15_5(x_1, ..., x_5) ) = max{0, x_2 - 2} POL( f750_out1_1(x_1) ) = 0 POL( U16_5(x_1, ..., x_5) ) = max{0, x_4 + 2x_5 - 2} POL( f755_in_2(x_1, x_2) ) = 2x_1 + 2x_2 POL( U6_3(x_1, ..., x_3) ) = max{0, 2x_1 + 2x_2 + 2x_3 - 2} POL( f755_out1 ) = 2 POL( U17_5(x_1, ..., x_5) ) = max{0, 2x_3 - 2} POL( F3_IN_1(x_1) ) = x_1 POL( F212_IN_3(x_1, ..., x_3) ) = 2x_3 + 2 POL( F284_IN_2(x_1, x_2) ) = x_1 + x_2 POL( F585_IN_2(x_1, x_2) ) = x_1 The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: f269_in(T29, T36, T37) -> U7(f533_in(T37), T29, T36, T37) f533_in([]) -> f533_out1([], []) f533_in(.(T42, T43)) -> U2(f533_in(T43), .(T42, T43)) U7(f533_out1(X61, X60), T29, T36, T37) -> f269_out1(.(T29, X61), .(T36, X60)) U2(f533_out1(X79, X78), .(T42, T43)) -> f533_out1(.(T42, X78), X79) ---------------------------------------- (29) Obligation: Q DP problem: The TRS P consists of the following rules: F212_IN(T16, T17, T18) -> U8^1(f269_in(T16, T17, T18), T16, T17, T18) U8^1(f269_out1(T21, T22), T16, T17, T18) -> F284_IN(T21, T22) F284_IN(T21, T22) -> U10^1(f3_in(T21), T21, T22) U10^1(f3_out1(T44), T21, T22) -> F585_IN(T22, T44) F585_IN(T22, T44) -> F3_IN(T22) F284_IN(T21, T22) -> F3_IN(T21) The TRS R consists of the following rules: f3_in([]) -> f3_out1([]) f3_in(.(T7, [])) -> f3_out1(.(T7, [])) f3_in(.(T16, .(T17, T18))) -> U1(f212_in(T16, T17, T18), .(T16, .(T17, T18))) U1(f212_out1(X22, X23, X24, X25, T20), .(T16, .(T17, T18))) -> f3_out1(T20) f533_in([]) -> f533_out1([], []) f533_in(.(T42, T43)) -> U2(f533_in(T43), .(T42, T43)) U2(f533_out1(X79, X78), .(T42, T43)) -> f533_out1(.(T42, X78), X79) f592_in([], T52) -> f592_out1(T52) f592_in(T57, []) -> f592_out1(T57) f592_in(.(T78, T79), .(T80, T81)) -> U3(f622_in(T78, T80, T79, T81), .(T78, T79), .(T80, T81)) U3(f622_out1(T83), .(T78, T79), .(T80, T81)) -> f592_out1(.(T78, T83)) f592_in(.(T119, T120), .(T121, T122)) -> U4(f750_in(T119, T121, T120, T122), .(T119, T120), .(T121, T122)) U4(f750_out1(T124), .(T119, T120), .(T121, T122)) -> f592_out1(.(T121, T124)) f631_in(s(T96), s(T97)) -> U5(f631_in(T96, T97), s(T96), s(T97)) U5(f631_out1, s(T96), s(T97)) -> f631_out1 f631_in(0, s(T104)) -> f631_out1 f631_in(0, 0) -> f631_out1 f755_in(s(T137), s(T138)) -> U6(f755_in(T137, T138), s(T137), s(T138)) U6(f755_out1, s(T137), s(T138)) -> f755_out1 f755_in(s(T143), 0) -> f755_out1 f269_in(T29, T36, T37) -> U7(f533_in(T37), T29, T36, T37) U7(f533_out1(X61, X60), T29, T36, T37) -> f269_out1(.(T29, X61), .(T36, X60)) f212_in(T16, T17, T18) -> U8(f269_in(T16, T17, T18), T16, T17, T18) U8(f269_out1(T21, T22), T16, T17, T18) -> U9(f284_in(T21, T22), T16, T17, T18, T21, T22) U9(f284_out1(X24, X25, T20), T16, T17, T18, T21, T22) -> f212_out1(T21, T22, X24, X25, T20) f284_in(T21, T22) -> U10(f3_in(T21), T21, T22) U10(f3_out1(T44), T21, T22) -> U11(f585_in(T22, T44), T21, T22, T44) U11(f585_out1(X25, T20), T21, T22, T44) -> f284_out1(T44, X25, T20) f585_in(T22, T44) -> U12(f3_in(T22), T22, T44) U12(f3_out1(T45), T22, T44) -> U13(f592_in(T44, T45), T22, T44, T45) U13(f592_out1(T20), T22, T44, T45) -> f585_out1(T45, T20) f622_in(T78, T80, T79, T81) -> U14(f631_in(T78, T80), T78, T80, T79, T81) U14(f631_out1, T78, T80, T79, T81) -> U15(f592_in(T79, .(T80, T81)), T78, T80, T79, T81) U15(f592_out1(T83), T78, T80, T79, T81) -> f622_out1(T83) f750_in(T119, T121, T120, T122) -> U16(f755_in(T119, T121), T119, T121, T120, T122) U16(f755_out1, T119, T121, T120, T122) -> U17(f592_in(.(T119, T120), T122), T119, T121, T120, T122) U17(f592_out1(T124), T119, T121, T120, T122) -> f750_out1(T124) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (30) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 0 SCCs with 6 less nodes. ---------------------------------------- (31) TRUE