/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,a) w.r.t. the given Prolog program could successfully be proven: (0) Prolog (1) PrologToTRSTransformerProof [SOUND, 95 ms] (2) QTRS (3) DependencyPairsProof [EQUIVALENT, 6 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) QDPSizeChangeProof [EQUIVALENT, 0 ms] (19) YES (20) QDP (21) UsableRulesProof [EQUIVALENT, 0 ms] (22) QDP (23) QDPSizeChangeProof [EQUIVALENT, 0 ms] (24) YES (25) QDP (26) QDPOrderProof [EQUIVALENT, 67 ms] (27) QDP (28) DependencyGraphProof [EQUIVALENT, 0 ms] (29) TRUE ---------------------------------------- (0) Obligation: Clauses: mergesort([], [], Ls). mergesort(.(X, []), .(X, []), Ls). mergesort(.(X, .(Y, Xs)), Ys, .(H, Ls)) :- ','(split(.(X, .(Y, Xs)), X1s, X2s, .(H, Ls)), ','(mergesort(X1s, Y1s, Ls), ','(mergesort(X2s, Y2s, Ls), merge(Y1s, Y2s, Ys, .(H, Ls))))). split([], [], [], Ls). split(.(X, Xs), .(X, Ys), Zs, .(H, Ls)) :- split(Xs, Zs, Ys, Ls). merge([], Xs, Xs, Ls). merge(Xs, [], Xs, Ls). merge(.(X, Xs), .(Y, Ys), .(X, Zs), .(H, Ls)) :- ','(le(X, Y), merge(Xs, .(Y, Ys), Zs, Ls)). merge(.(X, Xs), .(Y, Ys), .(Y, Zs), .(H, Ls)) :- ','(gt(X, Y), merge(.(X, Xs), Ys, Zs, Ls)). gt(s(X), s(Y)) :- gt(X, Y). gt(s(0), 0). le(s(X), s(Y)) :- le(X, Y). le(0, s(0)). le(0, 0). Query: mergesort(g,a,a) ---------------------------------------- (1) PrologToTRSTransformerProof (SOUND) Transformed Prolog program to TRS. { "root": 1, "program": { "directives": [], "clauses": [ [ "(mergesort ([]) ([]) Ls)", null ], [ "(mergesort (. X ([])) (. X ([])) Ls)", null ], [ "(mergesort (. X (. Y Xs)) Ys (. H Ls))", "(',' (split (. X (. Y Xs)) X1s X2s (. H Ls)) (',' (mergesort X1s Y1s Ls) (',' (mergesort X2s Y2s Ls) (merge Y1s Y2s Ys (. H Ls)))))" ], [ "(split ([]) ([]) ([]) Ls)", null ], [ "(split (. X Xs) (. X Ys) Zs (. H Ls))", "(split Xs Zs Ys Ls)" ], [ "(merge ([]) Xs Xs Ls)", null ], [ "(merge Xs ([]) Xs Ls)", null ], [ "(merge (. X Xs) (. Y Ys) (. X Zs) (. H Ls))", "(',' (le X Y) (merge Xs (. Y Ys) Zs Ls))" ], [ "(merge (. X Xs) (. Y Ys) (. Y Zs) (. H Ls))", "(',' (gt X Y) (merge (. X Xs) Ys Zs Ls))" ], [ "(gt (s X) (s Y))", "(gt X Y)" ], [ "(gt (s (0)) (0))", null ], [ "(le (s X) (s Y))", "(le X Y)" ], [ "(le (0) (s (0)))", null ], [ "(le (0) (0))", null ] ] }, "graph": { "nodes": { "907": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "908": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "909": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "type": "Nodes", "596": { "goal": [ { "clause": 3, "scope": 2, "term": "(split (. T31 (. T32 T33)) X38 X39 (. T37 T38))" }, { "clause": 4, "scope": 2, "term": "(split (. T31 (. T32 T33)) X38 X39 (. T37 T38))" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T31", "T32", "T33" ], "free": [ "X38", "X39" ], "exprvars": [] } }, "750": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "630": { "goal": [{ "clause": -1, "scope": -1, "term": "(split (. T57 T58) X72 X71 T61)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T57", "T58" ], "free": [ "X71", "X72" ], "exprvars": [] } }, "751": { "goal": [{ "clause": 6, "scope": 5, "term": "(merge T99 T107 T108 (. T109 T110))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T99", "T107" ], "free": [], "exprvars": [] } }, "598": { "goal": [{ "clause": 4, "scope": 2, "term": "(split (. T31 (. T32 T33)) X38 X39 (. T37 T38))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T31", "T32", "T33" ], "free": [ "X38", "X39" ], "exprvars": [] } }, "752": { "goal": [ { "clause": 7, "scope": 5, "term": "(merge T99 T107 T108 (. T109 T110))" }, { "clause": 8, "scope": 5, "term": "(merge T99 T107 T108 (. T109 T110))" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T99", "T107" ], "free": [], "exprvars": [] } }, "755": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "756": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "910": { "goal": [ { "clause": 5, "scope": 9, "term": "(merge (. T277 T278) T280 T284 T285)" }, { "clause": 6, "scope": 9, "term": "(merge (. T277 T278) T280 T284 T285)" }, { "clause": 7, "scope": 9, "term": "(merge (. T277 T278) T280 T284 T285)" }, { "clause": 8, "scope": 9, "term": "(merge (. T277 T278) T280 T284 T285)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T277", "T278", "T280" ], "free": [], "exprvars": [] } }, "757": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "911": { "goal": [ { "clause": 6, "scope": 9, "term": "(merge (. T277 T278) T280 T284 T285)" }, { "clause": 7, "scope": 9, "term": "(merge (. T277 T278) T280 T284 T285)" }, { "clause": 8, "scope": 9, "term": "(merge (. T277 T278) T280 T284 T285)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T277", "T278", "T280" ], "free": [], "exprvars": [] } }, "758": { "goal": [{ "clause": 7, "scope": 5, "term": "(merge T99 T107 T108 (. T109 T110))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T99", "T107" ], "free": [], "exprvars": [] } }, "912": { "goal": [{ "clause": 6, "scope": 9, "term": "(merge (. T277 T278) T280 T284 T285)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T277", "T278", "T280" ], "free": [], "exprvars": [] } }, "638": { "goal": [ { "clause": 3, "scope": 3, "term": "(split (. T57 T58) X72 X71 T61)" }, { "clause": 4, "scope": 3, "term": "(split (. T57 T58) X72 X71 T61)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T57", "T58" ], "free": [ "X71", "X72" ], "exprvars": [] } }, "759": { "goal": [{ "clause": 8, "scope": 5, "term": "(merge T99 T107 T108 (. T109 T110))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T99", "T107" ], "free": [], "exprvars": [] } }, "913": { "goal": [ { "clause": 7, "scope": 9, "term": "(merge (. T277 T278) T280 T284 T285)" }, { "clause": 8, "scope": 9, "term": "(merge (. T277 T278) T280 T284 T285)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T277", "T278", "T280" ], "free": [], "exprvars": [] } }, "914": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "915": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "917": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "919": { "goal": [{ "clause": 7, "scope": 9, "term": "(merge (. T277 T278) T280 T284 T285)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T277", "T278", "T280" ], "free": [], "exprvars": [] } }, "1": { "goal": [{ "clause": -1, "scope": -1, "term": "(mergesort T1 T2 T3)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T1"], "free": [], "exprvars": [] } }, "640": { "goal": [{ "clause": 4, "scope": 3, "term": "(split (. T57 T58) X72 X71 T61)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T57", "T58" ], "free": [ "X71", "X72" ], "exprvars": [] } }, "3": { "goal": [ { "clause": 0, "scope": 1, "term": "(mergesort T1 T2 T3)" }, { "clause": 1, "scope": 1, "term": "(mergesort T1 T2 T3)" }, { "clause": 2, "scope": 1, "term": "(mergesort T1 T2 T3)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T1"], "free": [], "exprvars": [] } }, "4": { "goal": [{ "clause": 0, "scope": 1, "term": "(mergesort T1 T2 T3)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T1"], "free": [], "exprvars": [] } }, "5": { "goal": [ { "clause": 1, "scope": 1, "term": "(mergesort T1 T2 T3)" }, { "clause": 2, "scope": 1, "term": "(mergesort T1 T2 T3)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T1"], "free": [], "exprvars": [] } }, "645": { "goal": [{ "clause": -1, "scope": -1, "term": "(split T71 X99 X98 T74)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T71"], "free": [ "X98", "X99" ], "exprvars": [] } }, "920": { "goal": [{ "clause": 8, "scope": 9, "term": "(merge (. T277 T278) T280 T284 T285)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T277", "T278", "T280" ], "free": [], "exprvars": [] } }, "921": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (le T345 T347) (merge T346 (. T347 T348) T352 T353))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T345", "T346", "T347", "T348" ], "free": [], "exprvars": [] } }, "647": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "922": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "648": { "goal": [ { "clause": 3, "scope": 4, "term": "(split T71 X99 X98 T74)" }, { "clause": 4, "scope": 4, "term": "(split T71 X99 X98 T74)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T71"], "free": [ "X98", "X99" ], "exprvars": [] } }, "923": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (gt T370 T372) (merge (. T370 T371) T373 T377 T378))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T370", "T371", "T372", "T373" ], "free": [], "exprvars": [] } }, "649": { "goal": [{ "clause": 3, "scope": 4, "term": "(split T71 X99 X98 T74)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T71"], "free": [ "X98", "X99" ], "exprvars": [] } }, "803": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "924": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "804": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "805": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "806": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "807": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "808": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "650": { "goal": [{ "clause": 4, "scope": 4, "term": "(split T71 X99 X98 T74)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T71"], "free": [ "X98", "X99" ], "exprvars": [] } }, "651": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "652": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "653": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "896": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (gt T277 T279) (merge (. T277 T278) T280 T284 T285))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T277", "T278", "T279", "T280" ], "free": [], "exprvars": [] } }, "897": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "898": { "goal": [{ "clause": -1, "scope": -1, "term": "(gt T277 T279)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T277", "T279" ], "free": [], "exprvars": [] } }, "899": { "goal": [{ "clause": -1, "scope": -1, "term": "(merge (. T277 T278) T280 T284 T285)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T277", "T278", "T280" ], "free": [], "exprvars": [] } }, "932": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (gt T395 T397) (merge (. T395 T396) T398 T402 T403))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T395", "T396", "T397", "T398" ], "free": [], "exprvars": [] } }, "933": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "813": { "goal": [ { "clause": 5, "scope": 7, "term": "(merge T178 (. T179 T180) T184 T185)" }, { "clause": 6, "scope": 7, "term": "(merge T178 (. T179 T180) T184 T185)" }, { "clause": 7, "scope": 7, "term": "(merge T178 (. T179 T180) T184 T185)" }, { "clause": 8, "scope": 7, "term": "(merge T178 (. T179 T180) T184 T185)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T178", "T179", "T180" ], "free": [], "exprvars": [] } }, "814": { "goal": [{ "clause": 5, "scope": 7, "term": "(merge T178 (. T179 T180) T184 T185)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T178", "T179", "T180" ], "free": [], "exprvars": [] } }, "815": { "goal": [ { "clause": 6, "scope": 7, "term": "(merge T178 (. T179 T180) T184 T185)" }, { "clause": 7, "scope": 7, "term": "(merge T178 (. T179 T180) T184 T185)" }, { "clause": 8, "scope": 7, "term": "(merge T178 (. T179 T180) T184 T185)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T178", "T179", "T180" ], "free": [], "exprvars": [] } }, "818": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "819": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "37": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "38": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "39": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "782": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (le T177 T179) (merge T178 (. T179 T180) T184 T185))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T177", "T178", "T179", "T180" ], "free": [], "exprvars": [] } }, "783": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "787": { "goal": [{ "clause": -1, "scope": -1, "term": "(le T177 T179)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T177", "T179" ], "free": [], "exprvars": [] } }, "820": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "788": { "goal": [{ "clause": -1, "scope": -1, "term": "(merge T178 (. T179 T180) T184 T185)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T178", "T179", "T180" ], "free": [], "exprvars": [] } }, "825": { "goal": [ { "clause": 7, "scope": 7, "term": "(merge T178 (. T179 T180) T184 T185)" }, { "clause": 8, "scope": 7, "term": "(merge T178 (. T179 T180) T184 T185)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T178", "T179", "T180" ], "free": [], "exprvars": [] } }, "40": { "goal": [{ "clause": 1, "scope": 1, "term": "(mergesort T1 T2 T3)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T1"], "free": [], "exprvars": [] } }, "41": { "goal": [{ "clause": 2, "scope": 1, "term": "(mergesort T1 T2 T3)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T1"], "free": [], "exprvars": [] } }, "42": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "43": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "44": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "791": { "goal": [ { "clause": 11, "scope": 6, "term": "(le T177 T179)" }, { "clause": 12, "scope": 6, "term": "(le T177 T179)" }, { "clause": 13, "scope": 6, "term": "(le T177 T179)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T177", "T179" ], "free": [], "exprvars": [] } }, "792": { "goal": [{ "clause": 11, "scope": 6, "term": "(le T177 T179)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T177", "T179" ], "free": [], "exprvars": [] } }, "793": { "goal": [ { "clause": 12, "scope": 6, "term": "(le T177 T179)" }, { "clause": 13, "scope": 6, "term": "(le T177 T179)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T177", "T179" ], "free": [], "exprvars": [] } }, "794": { "goal": [{ "clause": -1, "scope": -1, "term": "(le T198 T199)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T198", "T199" ], "free": [], "exprvars": [] } }, "795": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "675": { "goal": [{ "clause": -1, "scope": -1, "term": "(split T91 X130 X129 T94)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T91"], "free": [ "X129", "X130" ], "exprvars": [] } }, "798": { "goal": [{ "clause": 12, "scope": 6, "term": "(le T177 T179)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T177", "T179" ], "free": [], "exprvars": [] } }, "799": { "goal": [{ "clause": 13, "scope": 6, "term": "(le T177 T179)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T177", "T179" ], "free": [], "exprvars": [] } }, "835": { "goal": [{ "clause": 7, "scope": 7, "term": "(merge T178 (. T179 T180) T184 T185)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T178", "T179", "T180" ], "free": [], "exprvars": [] } }, "836": { "goal": [{ "clause": 8, "scope": 7, "term": "(merge T178 (. T179 T180) T184 T185)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T178", "T179", "T180" ], "free": [], "exprvars": [] } }, "687": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "455": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (split (. T31 (. T32 T33)) X38 X39 (. T37 T38)) (',' (mergesort X38 X40 T38) (',' (mergesort X39 X41 T38) (merge X40 X41 T39 (. T37 T38)))))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T31", "T32", "T33" ], "free": [ "X38", "X39", "X40", "X41" ], "exprvars": [] } }, "730": { "goal": [{ "clause": -1, "scope": -1, "term": "(mergesort T40 X40 T42)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T40"], "free": ["X40"], "exprvars": [] } }, "731": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (mergesort T41 X41 T100) (merge T99 X41 T101 (. T102 T100)))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T41", "T99" ], "free": ["X41"], "exprvars": [] } }, "457": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "735": { "goal": [{ "clause": -1, "scope": -1, "term": "(mergesort T41 X41 T100)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T41"], "free": ["X41"], "exprvars": [] } }, "737": { "goal": [{ "clause": -1, "scope": -1, "term": "(merge T99 T107 T108 (. T109 T110))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T99", "T107" ], "free": [], "exprvars": [] } }, "466": { "goal": [{ "clause": -1, "scope": -1, "term": "(split (. T31 (. T32 T33)) X38 X39 (. T37 T38))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T31", "T32", "T33" ], "free": [ "X38", "X39" ], "exprvars": [] } }, "467": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (mergesort T40 X40 T42) (',' (mergesort T41 X41 T42) (merge X40 X41 T43 (. T44 T42))))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T40", "T41" ], "free": [ "X40", "X41" ], "exprvars": [] } }, "742": { "goal": [ { "clause": 5, "scope": 5, "term": "(merge T99 T107 T108 (. T109 T110))" }, { "clause": 6, "scope": 5, "term": "(merge T99 T107 T108 (. T109 T110))" }, { "clause": 7, "scope": 5, "term": "(merge T99 T107 T108 (. T109 T110))" }, { "clause": 8, "scope": 5, "term": "(merge T99 T107 T108 (. T109 T110))" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T99", "T107" ], "free": [], "exprvars": [] } }, "743": { "goal": [{ "clause": 5, "scope": 5, "term": "(merge T99 T107 T108 (. T109 T110))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T99", "T107" ], "free": [], "exprvars": [] } }, "744": { "goal": [ { "clause": 6, "scope": 5, "term": "(merge T99 T107 T108 (. T109 T110))" }, { "clause": 7, "scope": 5, "term": "(merge T99 T107 T108 (. T109 T110))" }, { "clause": 8, "scope": 5, "term": "(merge T99 T107 T108 (. T109 T110))" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T99", "T107" ], "free": [], "exprvars": [] } }, "865": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (le T252 T254) (merge T253 (. T254 T255) T259 T260))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T252", "T253", "T254", "T255" ], "free": [], "exprvars": [] } }, "866": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "900": { "goal": [ { "clause": 9, "scope": 8, "term": "(gt T277 T279)" }, { "clause": 10, "scope": 8, "term": "(gt T277 T279)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T277", "T279" ], "free": [], "exprvars": [] } }, "901": { "goal": [{ "clause": 9, "scope": 8, "term": "(gt T277 T279)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T277", "T279" ], "free": [], "exprvars": [] } }, "748": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "902": { "goal": [{ "clause": 10, "scope": 8, "term": "(gt T277 T279)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T277", "T279" ], "free": [], "exprvars": [] } }, "749": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "903": { "goal": [{ "clause": -1, "scope": -1, "term": "(gt T298 T299)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T298", "T299" ], "free": [], "exprvars": [] } }, "904": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } } }, "edges": [ { "from": 1, "to": 3, "label": "CASE" }, { "from": 3, "to": 4, "label": "PARALLEL" }, { "from": 3, "to": 5, "label": "PARALLEL" }, { "from": 4, "to": 37, "label": "EVAL with clause\nmergesort([], [], X5).\nand substitutionT1 -> [],\nT2 -> [],\nT3 -> T8,\nX5 -> T8" }, { "from": 4, "to": 38, "label": "EVAL-BACKTRACK" }, { "from": 5, "to": 40, "label": "PARALLEL" }, { "from": 5, "to": 41, "label": "PARALLEL" }, { "from": 37, "to": 39, "label": "SUCCESS" }, { "from": 40, "to": 42, "label": "EVAL with clause\nmergesort(.(X14, []), .(X14, []), X15).\nand substitutionX14 -> T17,\nT1 -> .(T17, []),\nT2 -> .(T17, []),\nT3 -> T18,\nX15 -> T18" }, { "from": 40, "to": 43, "label": "EVAL-BACKTRACK" }, { "from": 41, "to": 455, "label": "EVAL with clause\nmergesort(.(X32, .(X33, X34)), X35, .(X36, X37)) :- ','(split(.(X32, .(X33, X34)), X38, X39, .(X36, X37)), ','(mergesort(X38, X40, X37), ','(mergesort(X39, X41, X37), merge(X40, X41, X35, .(X36, X37))))).\nand substitutionX32 -> T31,\nX33 -> T32,\nX34 -> T33,\nT1 -> .(T31, .(T32, T33)),\nT2 -> T39,\nX35 -> T39,\nX36 -> T37,\nX37 -> T38,\nT3 -> .(T37, T38),\nT35 -> T37,\nT36 -> T38,\nT34 -> T39" }, { "from": 41, "to": 457, "label": "EVAL-BACKTRACK" }, { "from": 42, "to": 44, "label": "SUCCESS" }, { "from": 455, "to": 466, "label": "SPLIT 1" }, { "from": 455, "to": 467, "label": "SPLIT 2\nnew knowledge:\nT31 is ground\nT32 is ground\nT33 is ground\nT40 is ground\nT41 is ground\nreplacements:X38 -> T40,\nX39 -> T41,\nT38 -> T42,\nT39 -> T43,\nT37 -> T44" }, { "from": 466, "to": 596, "label": "CASE" }, { "from": 467, "to": 730, "label": "SPLIT 1" }, { "from": 467, "to": 731, "label": "SPLIT 2\nnew knowledge:\nT40 is ground\nT99 is ground\nreplacements:X40 -> T99,\nT42 -> T100,\nT43 -> T101,\nT44 -> T102" }, { "from": 596, "to": 598, "label": "BACKTRACK\nfor clause: split([], [], [], Ls)because of non-unification" }, { "from": 598, "to": 630, "label": "ONLY EVAL with clause\nsplit(.(X65, X66), .(X65, X67), X68, .(X69, X70)) :- split(X66, X68, X67, X70).\nand substitutionT31 -> T56,\nX65 -> T56,\nT32 -> T57,\nT33 -> T58,\nX66 -> .(T57, T58),\nX67 -> X71,\nX38 -> .(T56, X71),\nX39 -> X72,\nX68 -> X72,\nT37 -> T59,\nX69 -> T59,\nT38 -> T61,\nX70 -> T61,\nT60 -> T61" }, { "from": 630, "to": 638, "label": "CASE" }, { "from": 638, "to": 640, "label": "BACKTRACK\nfor clause: split([], [], [], Ls)because of non-unification" }, { "from": 640, "to": 645, "label": "EVAL with clause\nsplit(.(X92, X93), .(X92, X94), X95, .(X96, X97)) :- split(X93, X95, X94, X97).\nand substitutionT57 -> T70,\nX92 -> T70,\nT58 -> T71,\nX93 -> T71,\nX94 -> X98,\nX72 -> .(T70, X98),\nX71 -> X99,\nX95 -> X99,\nX96 -> T72,\nX97 -> T74,\nT61 -> .(T72, T74),\nT73 -> T74" }, { "from": 640, "to": 647, "label": "EVAL-BACKTRACK" }, { "from": 645, "to": 648, "label": "CASE" }, { "from": 648, "to": 649, "label": "PARALLEL" }, { "from": 648, "to": 650, "label": "PARALLEL" }, { "from": 649, "to": 651, "label": "EVAL with clause\nsplit([], [], [], X106).\nand substitutionT71 -> [],\nX99 -> [],\nX98 -> [],\nT74 -> T81,\nX106 -> T81" }, { "from": 649, "to": 652, "label": "EVAL-BACKTRACK" }, { "from": 650, "to": 675, "label": "EVAL with clause\nsplit(.(X123, X124), .(X123, X125), X126, .(X127, X128)) :- split(X124, X126, X125, X128).\nand substitutionX123 -> T90,\nX124 -> T91,\nT71 -> .(T90, T91),\nX125 -> X129,\nX99 -> .(T90, X129),\nX98 -> X130,\nX126 -> X130,\nX127 -> T92,\nX128 -> T94,\nT74 -> .(T92, T94),\nT93 -> T94" }, { "from": 650, "to": 687, "label": "EVAL-BACKTRACK" }, { "from": 651, "to": 653, "label": "SUCCESS" }, { "from": 675, "to": 645, "label": "INSTANCE with matching:\nT71 -> T91\nX99 -> X130\nX98 -> X129\nT74 -> T94" }, { "from": 730, "to": 1, "label": "INSTANCE with matching:\nT1 -> T40\nT2 -> X40\nT3 -> T42" }, { "from": 731, "to": 735, "label": "SPLIT 1" }, { "from": 731, "to": 737, "label": "SPLIT 2\nnew knowledge:\nT41 is ground\nT107 is ground\nreplacements:X41 -> T107,\nT101 -> T108,\nT102 -> T109,\nT100 -> T110" }, { "from": 735, "to": 1, "label": "INSTANCE with matching:\nT1 -> T41\nT2 -> X41\nT3 -> T100" }, { "from": 737, "to": 742, "label": "CASE" }, { "from": 742, "to": 743, "label": "PARALLEL" }, { "from": 742, "to": 744, "label": "PARALLEL" }, { "from": 743, "to": 748, "label": "EVAL with clause\nmerge([], X153, X153, X154).\nand substitutionT99 -> [],\nT107 -> T131,\nX153 -> T131,\nT108 -> T131,\nT109 -> T132,\nT110 -> T133,\nX154 -> .(T132, T133)" }, { "from": 743, "to": 749, "label": "EVAL-BACKTRACK" }, { "from": 744, "to": 751, "label": "PARALLEL" }, { "from": 744, "to": 752, "label": "PARALLEL" }, { "from": 748, "to": 750, "label": "SUCCESS" }, { "from": 751, "to": 755, "label": "EVAL with clause\nmerge(X163, [], X163, X164).\nand substitutionT99 -> T146,\nX163 -> T146,\nT107 -> [],\nT108 -> T146,\nT109 -> T147,\nT110 -> T148,\nX164 -> .(T147, T148)" }, { "from": 751, "to": 756, "label": "EVAL-BACKTRACK" }, { "from": 752, "to": 758, "label": "PARALLEL" }, { "from": 752, "to": 759, "label": "PARALLEL" }, { "from": 755, "to": 757, "label": "SUCCESS" }, { "from": 758, "to": 782, "label": "EVAL with clause\nmerge(.(X193, X194), .(X195, X196), .(X193, X197), .(X198, X199)) :- ','(le(X193, X195), merge(X194, .(X195, X196), X197, X199)).\nand substitutionX193 -> T177,\nX194 -> T178,\nT99 -> .(T177, T178),\nX195 -> T179,\nX196 -> T180,\nT107 -> .(T179, T180),\nX197 -> T184,\nT108 -> .(T177, T184),\nT109 -> T182,\nX198 -> T182,\nT110 -> T185,\nX199 -> T185,\nT181 -> T184,\nT183 -> T185" }, { "from": 758, "to": 783, "label": "EVAL-BACKTRACK" }, { "from": 759, "to": 932, "label": "EVAL with clause\nmerge(.(X396, X397), .(X398, X399), .(X398, X400), .(X401, X402)) :- ','(gt(X396, X398), merge(.(X396, X397), X399, X400, X402)).\nand substitutionX396 -> T395,\nX397 -> T396,\nT99 -> .(T395, T396),\nX398 -> T397,\nX399 -> T398,\nT107 -> .(T397, T398),\nX400 -> T402,\nT108 -> .(T397, T402),\nT109 -> T400,\nX401 -> T400,\nT110 -> T403,\nX402 -> T403,\nT399 -> T402,\nT401 -> T403" }, { "from": 759, "to": 933, "label": "EVAL-BACKTRACK" }, { "from": 782, "to": 787, "label": "SPLIT 1" }, { "from": 782, "to": 788, "label": "SPLIT 2\nnew knowledge:\nT177 is ground\nT179 is ground" }, { "from": 787, "to": 791, "label": "CASE" }, { "from": 788, "to": 813, "label": "CASE" }, { "from": 791, "to": 792, "label": "PARALLEL" }, { "from": 791, "to": 793, "label": "PARALLEL" }, { "from": 792, "to": 794, "label": "EVAL with clause\nle(s(X212), s(X213)) :- le(X212, X213).\nand substitutionX212 -> T198,\nT177 -> s(T198),\nX213 -> T199,\nT179 -> s(T199)" }, { "from": 792, "to": 795, "label": "EVAL-BACKTRACK" }, { "from": 793, "to": 798, "label": "PARALLEL" }, { "from": 793, "to": 799, "label": "PARALLEL" }, { "from": 794, "to": 787, "label": "INSTANCE with matching:\nT177 -> T198\nT179 -> T199" }, { "from": 798, "to": 803, "label": "EVAL with clause\nle(0, s(0)).\nand substitutionT177 -> 0,\nT179 -> s(0)" }, { "from": 798, "to": 804, "label": "EVAL-BACKTRACK" }, { "from": 799, "to": 806, "label": "EVAL with clause\nle(0, 0).\nand substitutionT177 -> 0,\nT179 -> 0" }, { "from": 799, "to": 807, "label": "EVAL-BACKTRACK" }, { "from": 803, "to": 805, "label": "SUCCESS" }, { "from": 806, "to": 808, "label": "SUCCESS" }, { "from": 813, "to": 814, "label": "PARALLEL" }, { "from": 813, "to": 815, "label": "PARALLEL" }, { "from": 814, "to": 818, "label": "EVAL with clause\nmerge([], X228, X228, X229).\nand substitutionT178 -> [],\nT179 -> T220,\nT180 -> T221,\nX228 -> .(T220, T221),\nT184 -> .(T220, T221),\nT185 -> T222,\nX229 -> T222" }, { "from": 814, "to": 819, "label": "EVAL-BACKTRACK" }, { "from": 815, "to": 825, "label": "BACKTRACK\nfor clause: merge(Xs, [], Xs, Ls)because of non-unification" }, { "from": 818, "to": 820, "label": "SUCCESS" }, { "from": 825, "to": 835, "label": "PARALLEL" }, { "from": 825, "to": 836, "label": "PARALLEL" }, { "from": 835, "to": 865, "label": "EVAL with clause\nmerge(.(X260, X261), .(X262, X263), .(X260, X264), .(X265, X266)) :- ','(le(X260, X262), merge(X261, .(X262, X263), X264, X266)).\nand substitutionX260 -> T252,\nX261 -> T253,\nT178 -> .(T252, T253),\nT179 -> T254,\nX262 -> T254,\nT180 -> T255,\nX263 -> T255,\nX264 -> T259,\nT184 -> .(T252, T259),\nX265 -> T257,\nX266 -> T260,\nT185 -> .(T257, T260),\nT256 -> T259,\nT258 -> T260" }, { "from": 835, "to": 866, "label": "EVAL-BACKTRACK" }, { "from": 836, "to": 896, "label": "EVAL with clause\nmerge(.(X283, X284), .(X285, X286), .(X285, X287), .(X288, X289)) :- ','(gt(X283, X285), merge(.(X283, X284), X286, X287, X289)).\nand substitutionX283 -> T277,\nX284 -> T278,\nT178 -> .(T277, T278),\nT179 -> T279,\nX285 -> T279,\nT180 -> T280,\nX286 -> T280,\nX287 -> T284,\nT184 -> .(T279, T284),\nX288 -> T282,\nX289 -> T285,\nT185 -> .(T282, T285),\nT281 -> T284,\nT283 -> T285" }, { "from": 836, "to": 897, "label": "EVAL-BACKTRACK" }, { "from": 865, "to": 782, "label": "INSTANCE with matching:\nT177 -> T252\nT179 -> T254\nT178 -> T253\nT180 -> T255\nT184 -> T259\nT185 -> T260" }, { "from": 896, "to": 898, "label": "SPLIT 1" }, { "from": 896, "to": 899, "label": "SPLIT 2\nnew knowledge:\nT277 is ground\nT279 is ground" }, { "from": 898, "to": 900, "label": "CASE" }, { "from": 899, "to": 910, "label": "CASE" }, { "from": 900, "to": 901, "label": "PARALLEL" }, { "from": 900, "to": 902, "label": "PARALLEL" }, { "from": 901, "to": 903, "label": "EVAL with clause\ngt(s(X302), s(X303)) :- gt(X302, X303).\nand substitutionX302 -> T298,\nT277 -> s(T298),\nX303 -> T299,\nT279 -> s(T299)" }, { "from": 901, "to": 904, "label": "EVAL-BACKTRACK" }, { "from": 902, "to": 907, "label": "EVAL with clause\ngt(s(0), 0).\nand substitutionT277 -> s(0),\nT279 -> 0" }, { "from": 902, "to": 908, "label": "EVAL-BACKTRACK" }, { "from": 903, "to": 898, "label": "INSTANCE with matching:\nT277 -> T298\nT279 -> T299" }, { "from": 907, "to": 909, "label": "SUCCESS" }, { "from": 910, "to": 911, "label": "BACKTRACK\nfor clause: merge([], Xs, Xs, Ls)because of non-unification" }, { "from": 911, "to": 912, "label": "PARALLEL" }, { "from": 911, "to": 913, "label": "PARALLEL" }, { "from": 912, "to": 914, "label": "EVAL with clause\nmerge(X320, [], X320, X321).\nand substitutionT277 -> T314,\nT278 -> T315,\nX320 -> .(T314, T315),\nT280 -> [],\nT284 -> .(T314, T315),\nT285 -> T316,\nX321 -> T316" }, { "from": 912, "to": 915, "label": "EVAL-BACKTRACK" }, { "from": 913, "to": 919, "label": "PARALLEL" }, { "from": 913, "to": 920, "label": "PARALLEL" }, { "from": 914, "to": 917, "label": "SUCCESS" }, { "from": 919, "to": 921, "label": "EVAL with clause\nmerge(.(X350, X351), .(X352, X353), .(X350, X354), .(X355, X356)) :- ','(le(X350, X352), merge(X351, .(X352, X353), X354, X356)).\nand substitutionT277 -> T345,\nX350 -> T345,\nT278 -> T346,\nX351 -> T346,\nX352 -> T347,\nX353 -> T348,\nT280 -> .(T347, T348),\nX354 -> T352,\nT284 -> .(T345, T352),\nX355 -> T350,\nX356 -> T353,\nT285 -> .(T350, T353),\nT349 -> T352,\nT351 -> T353" }, { "from": 919, "to": 922, "label": "EVAL-BACKTRACK" }, { "from": 920, "to": 923, "label": "EVAL with clause\nmerge(.(X373, X374), .(X375, X376), .(X375, X377), .(X378, X379)) :- ','(gt(X373, X375), merge(.(X373, X374), X376, X377, X379)).\nand substitutionT277 -> T370,\nX373 -> T370,\nT278 -> T371,\nX374 -> T371,\nX375 -> T372,\nX376 -> T373,\nT280 -> .(T372, T373),\nX377 -> T377,\nT284 -> .(T372, T377),\nX378 -> T375,\nX379 -> T378,\nT285 -> .(T375, T378),\nT374 -> T377,\nT376 -> T378" }, { "from": 920, "to": 924, "label": "EVAL-BACKTRACK" }, { "from": 921, "to": 782, "label": "INSTANCE with matching:\nT177 -> T345\nT179 -> T347\nT178 -> T346\nT180 -> T348\nT184 -> T352\nT185 -> T353" }, { "from": 923, "to": 896, "label": "INSTANCE with matching:\nT277 -> T370\nT279 -> T372\nT278 -> T371\nT280 -> T373\nT284 -> T377\nT285 -> T378" }, { "from": 932, "to": 896, "label": "INSTANCE with matching:\nT277 -> T395\nT279 -> T397\nT278 -> T396\nT280 -> T398\nT284 -> T402\nT285 -> T403" } ], "type": "Graph" } } ---------------------------------------- (2) Obligation: Q restricted rewrite system: The TRS R consists of the following rules: f1_in([]) -> f1_out1([]) f1_in(.(T17, [])) -> f1_out1(.(T17, [])) f1_in(.(T31, .(T32, T33))) -> U1(f455_in(T31, T32, T33), .(T31, .(T32, T33))) U1(f455_out1(X38, X39, X40, X41, T39), .(T31, .(T32, T33))) -> f1_out1(T39) f645_in([]) -> f645_out1([], []) f645_in(.(T90, T91)) -> U2(f645_in(T91), .(T90, T91)) U2(f645_out1(X130, X129), .(T90, T91)) -> f645_out1(.(T90, X129), X130) f787_in(s(T198), s(T199)) -> U3(f787_in(T198, T199), s(T198), s(T199)) U3(f787_out1, s(T198), s(T199)) -> f787_out1 f787_in(0, s(0)) -> f787_out1 f787_in(0, 0) -> f787_out1 f898_in(s(T298), s(T299)) -> U4(f898_in(T298, T299), s(T298), s(T299)) U4(f898_out1, s(T298), s(T299)) -> f898_out1 f898_in(s(0), 0) -> f898_out1 f466_in(T56, T70, T71) -> U5(f645_in(T71), T56, T70, T71) U5(f645_out1(X99, X98), T56, T70, T71) -> f466_out1(.(T56, X99), .(T70, X98)) f737_in([], T131) -> f737_out1(T131) f737_in(T146, []) -> f737_out1(T146) f737_in(.(T177, T178), .(T179, T180)) -> U6(f782_in(T177, T179, T178, T180), .(T177, T178), .(T179, T180)) U6(f782_out1(T184), .(T177, T178), .(T179, T180)) -> f737_out1(.(T177, T184)) f737_in(.(T395, T396), .(T397, T398)) -> U7(f896_in(T395, T397, T396, T398), .(T395, T396), .(T397, T398)) U7(f896_out1(T402), .(T395, T396), .(T397, T398)) -> f737_out1(.(T397, T402)) f788_in([], T220, T221) -> f788_out1(.(T220, T221)) f788_in(.(T252, T253), T254, T255) -> U8(f782_in(T252, T254, T253, T255), .(T252, T253), T254, T255) U8(f782_out1(T259), .(T252, T253), T254, T255) -> f788_out1(.(T252, T259)) f788_in(.(T277, T278), T279, T280) -> U9(f896_in(T277, T279, T278, T280), .(T277, T278), T279, T280) U9(f896_out1(T284), .(T277, T278), T279, T280) -> f788_out1(.(T279, T284)) f899_in(T314, T315, []) -> f899_out1(.(T314, T315)) f899_in(T345, T346, .(T347, T348)) -> U10(f782_in(T345, T347, T346, T348), T345, T346, .(T347, T348)) U10(f782_out1(T352), T345, T346, .(T347, T348)) -> f899_out1(.(T345, T352)) f899_in(T370, T371, .(T372, T373)) -> U11(f896_in(T370, T372, T371, T373), T370, T371, .(T372, T373)) U11(f896_out1(T377), T370, T371, .(T372, T373)) -> f899_out1(.(T372, T377)) f455_in(T31, T32, T33) -> U12(f466_in(T31, T32, T33), T31, T32, T33) U12(f466_out1(T40, T41), T31, T32, T33) -> U13(f467_in(T40, T41), T31, T32, T33, T40, T41) U13(f467_out1(X40, X41, T43), T31, T32, T33, T40, T41) -> f455_out1(T40, T41, X40, X41, T43) f467_in(T40, T41) -> U14(f1_in(T40), T40, T41) U14(f1_out1(T99), T40, T41) -> U15(f731_in(T41, T99), T40, T41, T99) U15(f731_out1(X41, T101), T40, T41, T99) -> f467_out1(T99, X41, T101) f731_in(T41, T99) -> U16(f1_in(T41), T41, T99) U16(f1_out1(T107), T41, T99) -> U17(f737_in(T99, T107), T41, T99, T107) U17(f737_out1(T108), T41, T99, T107) -> f731_out1(T107, T108) f782_in(T177, T179, T178, T180) -> U18(f787_in(T177, T179), T177, T179, T178, T180) U18(f787_out1, T177, T179, T178, T180) -> U19(f788_in(T178, T179, T180), T177, T179, T178, T180) U19(f788_out1(T184), T177, T179, T178, T180) -> f782_out1(T184) f896_in(T277, T279, T278, T280) -> U20(f898_in(T277, T279), T277, T279, T278, T280) U20(f898_out1, T277, T279, T278, T280) -> U21(f899_in(T277, T278, T280), T277, T279, T278, T280) U21(f899_out1(T284), T277, T279, T278, T280) -> f896_out1(T284) 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: F1_IN(.(T31, .(T32, T33))) -> U1^1(f455_in(T31, T32, T33), .(T31, .(T32, T33))) F1_IN(.(T31, .(T32, T33))) -> F455_IN(T31, T32, T33) F645_IN(.(T90, T91)) -> U2^1(f645_in(T91), .(T90, T91)) F645_IN(.(T90, T91)) -> F645_IN(T91) F787_IN(s(T198), s(T199)) -> U3^1(f787_in(T198, T199), s(T198), s(T199)) F787_IN(s(T198), s(T199)) -> F787_IN(T198, T199) F898_IN(s(T298), s(T299)) -> U4^1(f898_in(T298, T299), s(T298), s(T299)) F898_IN(s(T298), s(T299)) -> F898_IN(T298, T299) F466_IN(T56, T70, T71) -> U5^1(f645_in(T71), T56, T70, T71) F466_IN(T56, T70, T71) -> F645_IN(T71) F737_IN(.(T177, T178), .(T179, T180)) -> U6^1(f782_in(T177, T179, T178, T180), .(T177, T178), .(T179, T180)) F737_IN(.(T177, T178), .(T179, T180)) -> F782_IN(T177, T179, T178, T180) F737_IN(.(T395, T396), .(T397, T398)) -> U7^1(f896_in(T395, T397, T396, T398), .(T395, T396), .(T397, T398)) F737_IN(.(T395, T396), .(T397, T398)) -> F896_IN(T395, T397, T396, T398) F788_IN(.(T252, T253), T254, T255) -> U8^1(f782_in(T252, T254, T253, T255), .(T252, T253), T254, T255) F788_IN(.(T252, T253), T254, T255) -> F782_IN(T252, T254, T253, T255) F788_IN(.(T277, T278), T279, T280) -> U9^1(f896_in(T277, T279, T278, T280), .(T277, T278), T279, T280) F788_IN(.(T277, T278), T279, T280) -> F896_IN(T277, T279, T278, T280) F899_IN(T345, T346, .(T347, T348)) -> U10^1(f782_in(T345, T347, T346, T348), T345, T346, .(T347, T348)) F899_IN(T345, T346, .(T347, T348)) -> F782_IN(T345, T347, T346, T348) F899_IN(T370, T371, .(T372, T373)) -> U11^1(f896_in(T370, T372, T371, T373), T370, T371, .(T372, T373)) F899_IN(T370, T371, .(T372, T373)) -> F896_IN(T370, T372, T371, T373) F455_IN(T31, T32, T33) -> U12^1(f466_in(T31, T32, T33), T31, T32, T33) F455_IN(T31, T32, T33) -> F466_IN(T31, T32, T33) U12^1(f466_out1(T40, T41), T31, T32, T33) -> U13^1(f467_in(T40, T41), T31, T32, T33, T40, T41) U12^1(f466_out1(T40, T41), T31, T32, T33) -> F467_IN(T40, T41) F467_IN(T40, T41) -> U14^1(f1_in(T40), T40, T41) F467_IN(T40, T41) -> F1_IN(T40) U14^1(f1_out1(T99), T40, T41) -> U15^1(f731_in(T41, T99), T40, T41, T99) U14^1(f1_out1(T99), T40, T41) -> F731_IN(T41, T99) F731_IN(T41, T99) -> U16^1(f1_in(T41), T41, T99) F731_IN(T41, T99) -> F1_IN(T41) U16^1(f1_out1(T107), T41, T99) -> U17^1(f737_in(T99, T107), T41, T99, T107) U16^1(f1_out1(T107), T41, T99) -> F737_IN(T99, T107) F782_IN(T177, T179, T178, T180) -> U18^1(f787_in(T177, T179), T177, T179, T178, T180) F782_IN(T177, T179, T178, T180) -> F787_IN(T177, T179) U18^1(f787_out1, T177, T179, T178, T180) -> U19^1(f788_in(T178, T179, T180), T177, T179, T178, T180) U18^1(f787_out1, T177, T179, T178, T180) -> F788_IN(T178, T179, T180) F896_IN(T277, T279, T278, T280) -> U20^1(f898_in(T277, T279), T277, T279, T278, T280) F896_IN(T277, T279, T278, T280) -> F898_IN(T277, T279) U20^1(f898_out1, T277, T279, T278, T280) -> U21^1(f899_in(T277, T278, T280), T277, T279, T278, T280) U20^1(f898_out1, T277, T279, T278, T280) -> F899_IN(T277, T278, T280) The TRS R consists of the following rules: f1_in([]) -> f1_out1([]) f1_in(.(T17, [])) -> f1_out1(.(T17, [])) f1_in(.(T31, .(T32, T33))) -> U1(f455_in(T31, T32, T33), .(T31, .(T32, T33))) U1(f455_out1(X38, X39, X40, X41, T39), .(T31, .(T32, T33))) -> f1_out1(T39) f645_in([]) -> f645_out1([], []) f645_in(.(T90, T91)) -> U2(f645_in(T91), .(T90, T91)) U2(f645_out1(X130, X129), .(T90, T91)) -> f645_out1(.(T90, X129), X130) f787_in(s(T198), s(T199)) -> U3(f787_in(T198, T199), s(T198), s(T199)) U3(f787_out1, s(T198), s(T199)) -> f787_out1 f787_in(0, s(0)) -> f787_out1 f787_in(0, 0) -> f787_out1 f898_in(s(T298), s(T299)) -> U4(f898_in(T298, T299), s(T298), s(T299)) U4(f898_out1, s(T298), s(T299)) -> f898_out1 f898_in(s(0), 0) -> f898_out1 f466_in(T56, T70, T71) -> U5(f645_in(T71), T56, T70, T71) U5(f645_out1(X99, X98), T56, T70, T71) -> f466_out1(.(T56, X99), .(T70, X98)) f737_in([], T131) -> f737_out1(T131) f737_in(T146, []) -> f737_out1(T146) f737_in(.(T177, T178), .(T179, T180)) -> U6(f782_in(T177, T179, T178, T180), .(T177, T178), .(T179, T180)) U6(f782_out1(T184), .(T177, T178), .(T179, T180)) -> f737_out1(.(T177, T184)) f737_in(.(T395, T396), .(T397, T398)) -> U7(f896_in(T395, T397, T396, T398), .(T395, T396), .(T397, T398)) U7(f896_out1(T402), .(T395, T396), .(T397, T398)) -> f737_out1(.(T397, T402)) f788_in([], T220, T221) -> f788_out1(.(T220, T221)) f788_in(.(T252, T253), T254, T255) -> U8(f782_in(T252, T254, T253, T255), .(T252, T253), T254, T255) U8(f782_out1(T259), .(T252, T253), T254, T255) -> f788_out1(.(T252, T259)) f788_in(.(T277, T278), T279, T280) -> U9(f896_in(T277, T279, T278, T280), .(T277, T278), T279, T280) U9(f896_out1(T284), .(T277, T278), T279, T280) -> f788_out1(.(T279, T284)) f899_in(T314, T315, []) -> f899_out1(.(T314, T315)) f899_in(T345, T346, .(T347, T348)) -> U10(f782_in(T345, T347, T346, T348), T345, T346, .(T347, T348)) U10(f782_out1(T352), T345, T346, .(T347, T348)) -> f899_out1(.(T345, T352)) f899_in(T370, T371, .(T372, T373)) -> U11(f896_in(T370, T372, T371, T373), T370, T371, .(T372, T373)) U11(f896_out1(T377), T370, T371, .(T372, T373)) -> f899_out1(.(T372, T377)) f455_in(T31, T32, T33) -> U12(f466_in(T31, T32, T33), T31, T32, T33) U12(f466_out1(T40, T41), T31, T32, T33) -> U13(f467_in(T40, T41), T31, T32, T33, T40, T41) U13(f467_out1(X40, X41, T43), T31, T32, T33, T40, T41) -> f455_out1(T40, T41, X40, X41, T43) f467_in(T40, T41) -> U14(f1_in(T40), T40, T41) U14(f1_out1(T99), T40, T41) -> U15(f731_in(T41, T99), T40, T41, T99) U15(f731_out1(X41, T101), T40, T41, T99) -> f467_out1(T99, X41, T101) f731_in(T41, T99) -> U16(f1_in(T41), T41, T99) U16(f1_out1(T107), T41, T99) -> U17(f737_in(T99, T107), T41, T99, T107) U17(f737_out1(T108), T41, T99, T107) -> f731_out1(T107, T108) f782_in(T177, T179, T178, T180) -> U18(f787_in(T177, T179), T177, T179, T178, T180) U18(f787_out1, T177, T179, T178, T180) -> U19(f788_in(T178, T179, T180), T177, T179, T178, T180) U19(f788_out1(T184), T177, T179, T178, T180) -> f782_out1(T184) f896_in(T277, T279, T278, T280) -> U20(f898_in(T277, T279), T277, T279, T278, T280) U20(f898_out1, T277, T279, T278, T280) -> U21(f899_in(T277, T278, T280), T277, T279, T278, T280) U21(f899_out1(T284), T277, T279, T278, T280) -> f896_out1(T284) 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 24 less nodes. ---------------------------------------- (6) Complex Obligation (AND) ---------------------------------------- (7) Obligation: Q DP problem: The TRS P consists of the following rules: F898_IN(s(T298), s(T299)) -> F898_IN(T298, T299) The TRS R consists of the following rules: f1_in([]) -> f1_out1([]) f1_in(.(T17, [])) -> f1_out1(.(T17, [])) f1_in(.(T31, .(T32, T33))) -> U1(f455_in(T31, T32, T33), .(T31, .(T32, T33))) U1(f455_out1(X38, X39, X40, X41, T39), .(T31, .(T32, T33))) -> f1_out1(T39) f645_in([]) -> f645_out1([], []) f645_in(.(T90, T91)) -> U2(f645_in(T91), .(T90, T91)) U2(f645_out1(X130, X129), .(T90, T91)) -> f645_out1(.(T90, X129), X130) f787_in(s(T198), s(T199)) -> U3(f787_in(T198, T199), s(T198), s(T199)) U3(f787_out1, s(T198), s(T199)) -> f787_out1 f787_in(0, s(0)) -> f787_out1 f787_in(0, 0) -> f787_out1 f898_in(s(T298), s(T299)) -> U4(f898_in(T298, T299), s(T298), s(T299)) U4(f898_out1, s(T298), s(T299)) -> f898_out1 f898_in(s(0), 0) -> f898_out1 f466_in(T56, T70, T71) -> U5(f645_in(T71), T56, T70, T71) U5(f645_out1(X99, X98), T56, T70, T71) -> f466_out1(.(T56, X99), .(T70, X98)) f737_in([], T131) -> f737_out1(T131) f737_in(T146, []) -> f737_out1(T146) f737_in(.(T177, T178), .(T179, T180)) -> U6(f782_in(T177, T179, T178, T180), .(T177, T178), .(T179, T180)) U6(f782_out1(T184), .(T177, T178), .(T179, T180)) -> f737_out1(.(T177, T184)) f737_in(.(T395, T396), .(T397, T398)) -> U7(f896_in(T395, T397, T396, T398), .(T395, T396), .(T397, T398)) U7(f896_out1(T402), .(T395, T396), .(T397, T398)) -> f737_out1(.(T397, T402)) f788_in([], T220, T221) -> f788_out1(.(T220, T221)) f788_in(.(T252, T253), T254, T255) -> U8(f782_in(T252, T254, T253, T255), .(T252, T253), T254, T255) U8(f782_out1(T259), .(T252, T253), T254, T255) -> f788_out1(.(T252, T259)) f788_in(.(T277, T278), T279, T280) -> U9(f896_in(T277, T279, T278, T280), .(T277, T278), T279, T280) U9(f896_out1(T284), .(T277, T278), T279, T280) -> f788_out1(.(T279, T284)) f899_in(T314, T315, []) -> f899_out1(.(T314, T315)) f899_in(T345, T346, .(T347, T348)) -> U10(f782_in(T345, T347, T346, T348), T345, T346, .(T347, T348)) U10(f782_out1(T352), T345, T346, .(T347, T348)) -> f899_out1(.(T345, T352)) f899_in(T370, T371, .(T372, T373)) -> U11(f896_in(T370, T372, T371, T373), T370, T371, .(T372, T373)) U11(f896_out1(T377), T370, T371, .(T372, T373)) -> f899_out1(.(T372, T377)) f455_in(T31, T32, T33) -> U12(f466_in(T31, T32, T33), T31, T32, T33) U12(f466_out1(T40, T41), T31, T32, T33) -> U13(f467_in(T40, T41), T31, T32, T33, T40, T41) U13(f467_out1(X40, X41, T43), T31, T32, T33, T40, T41) -> f455_out1(T40, T41, X40, X41, T43) f467_in(T40, T41) -> U14(f1_in(T40), T40, T41) U14(f1_out1(T99), T40, T41) -> U15(f731_in(T41, T99), T40, T41, T99) U15(f731_out1(X41, T101), T40, T41, T99) -> f467_out1(T99, X41, T101) f731_in(T41, T99) -> U16(f1_in(T41), T41, T99) U16(f1_out1(T107), T41, T99) -> U17(f737_in(T99, T107), T41, T99, T107) U17(f737_out1(T108), T41, T99, T107) -> f731_out1(T107, T108) f782_in(T177, T179, T178, T180) -> U18(f787_in(T177, T179), T177, T179, T178, T180) U18(f787_out1, T177, T179, T178, T180) -> U19(f788_in(T178, T179, T180), T177, T179, T178, T180) U19(f788_out1(T184), T177, T179, T178, T180) -> f782_out1(T184) f896_in(T277, T279, T278, T280) -> U20(f898_in(T277, T279), T277, T279, T278, T280) U20(f898_out1, T277, T279, T278, T280) -> U21(f899_in(T277, T278, T280), T277, T279, T278, T280) U21(f899_out1(T284), T277, T279, T278, T280) -> f896_out1(T284) 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: F898_IN(s(T298), s(T299)) -> F898_IN(T298, T299) 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: *F898_IN(s(T298), s(T299)) -> F898_IN(T298, T299) 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: F787_IN(s(T198), s(T199)) -> F787_IN(T198, T199) The TRS R consists of the following rules: f1_in([]) -> f1_out1([]) f1_in(.(T17, [])) -> f1_out1(.(T17, [])) f1_in(.(T31, .(T32, T33))) -> U1(f455_in(T31, T32, T33), .(T31, .(T32, T33))) U1(f455_out1(X38, X39, X40, X41, T39), .(T31, .(T32, T33))) -> f1_out1(T39) f645_in([]) -> f645_out1([], []) f645_in(.(T90, T91)) -> U2(f645_in(T91), .(T90, T91)) U2(f645_out1(X130, X129), .(T90, T91)) -> f645_out1(.(T90, X129), X130) f787_in(s(T198), s(T199)) -> U3(f787_in(T198, T199), s(T198), s(T199)) U3(f787_out1, s(T198), s(T199)) -> f787_out1 f787_in(0, s(0)) -> f787_out1 f787_in(0, 0) -> f787_out1 f898_in(s(T298), s(T299)) -> U4(f898_in(T298, T299), s(T298), s(T299)) U4(f898_out1, s(T298), s(T299)) -> f898_out1 f898_in(s(0), 0) -> f898_out1 f466_in(T56, T70, T71) -> U5(f645_in(T71), T56, T70, T71) U5(f645_out1(X99, X98), T56, T70, T71) -> f466_out1(.(T56, X99), .(T70, X98)) f737_in([], T131) -> f737_out1(T131) f737_in(T146, []) -> f737_out1(T146) f737_in(.(T177, T178), .(T179, T180)) -> U6(f782_in(T177, T179, T178, T180), .(T177, T178), .(T179, T180)) U6(f782_out1(T184), .(T177, T178), .(T179, T180)) -> f737_out1(.(T177, T184)) f737_in(.(T395, T396), .(T397, T398)) -> U7(f896_in(T395, T397, T396, T398), .(T395, T396), .(T397, T398)) U7(f896_out1(T402), .(T395, T396), .(T397, T398)) -> f737_out1(.(T397, T402)) f788_in([], T220, T221) -> f788_out1(.(T220, T221)) f788_in(.(T252, T253), T254, T255) -> U8(f782_in(T252, T254, T253, T255), .(T252, T253), T254, T255) U8(f782_out1(T259), .(T252, T253), T254, T255) -> f788_out1(.(T252, T259)) f788_in(.(T277, T278), T279, T280) -> U9(f896_in(T277, T279, T278, T280), .(T277, T278), T279, T280) U9(f896_out1(T284), .(T277, T278), T279, T280) -> f788_out1(.(T279, T284)) f899_in(T314, T315, []) -> f899_out1(.(T314, T315)) f899_in(T345, T346, .(T347, T348)) -> U10(f782_in(T345, T347, T346, T348), T345, T346, .(T347, T348)) U10(f782_out1(T352), T345, T346, .(T347, T348)) -> f899_out1(.(T345, T352)) f899_in(T370, T371, .(T372, T373)) -> U11(f896_in(T370, T372, T371, T373), T370, T371, .(T372, T373)) U11(f896_out1(T377), T370, T371, .(T372, T373)) -> f899_out1(.(T372, T377)) f455_in(T31, T32, T33) -> U12(f466_in(T31, T32, T33), T31, T32, T33) U12(f466_out1(T40, T41), T31, T32, T33) -> U13(f467_in(T40, T41), T31, T32, T33, T40, T41) U13(f467_out1(X40, X41, T43), T31, T32, T33, T40, T41) -> f455_out1(T40, T41, X40, X41, T43) f467_in(T40, T41) -> U14(f1_in(T40), T40, T41) U14(f1_out1(T99), T40, T41) -> U15(f731_in(T41, T99), T40, T41, T99) U15(f731_out1(X41, T101), T40, T41, T99) -> f467_out1(T99, X41, T101) f731_in(T41, T99) -> U16(f1_in(T41), T41, T99) U16(f1_out1(T107), T41, T99) -> U17(f737_in(T99, T107), T41, T99, T107) U17(f737_out1(T108), T41, T99, T107) -> f731_out1(T107, T108) f782_in(T177, T179, T178, T180) -> U18(f787_in(T177, T179), T177, T179, T178, T180) U18(f787_out1, T177, T179, T178, T180) -> U19(f788_in(T178, T179, T180), T177, T179, T178, T180) U19(f788_out1(T184), T177, T179, T178, T180) -> f782_out1(T184) f896_in(T277, T279, T278, T280) -> U20(f898_in(T277, T279), T277, T279, T278, T280) U20(f898_out1, T277, T279, T278, T280) -> U21(f899_in(T277, T278, T280), T277, T279, T278, T280) U21(f899_out1(T284), T277, T279, T278, T280) -> f896_out1(T284) 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: F787_IN(s(T198), s(T199)) -> F787_IN(T198, T199) 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: *F787_IN(s(T198), s(T199)) -> F787_IN(T198, T199) 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: F782_IN(T177, T179, T178, T180) -> U18^1(f787_in(T177, T179), T177, T179, T178, T180) U18^1(f787_out1, T177, T179, T178, T180) -> F788_IN(T178, T179, T180) F788_IN(.(T252, T253), T254, T255) -> F782_IN(T252, T254, T253, T255) F788_IN(.(T277, T278), T279, T280) -> F896_IN(T277, T279, T278, T280) F896_IN(T277, T279, T278, T280) -> U20^1(f898_in(T277, T279), T277, T279, T278, T280) U20^1(f898_out1, T277, T279, T278, T280) -> F899_IN(T277, T278, T280) F899_IN(T345, T346, .(T347, T348)) -> F782_IN(T345, T347, T346, T348) F899_IN(T370, T371, .(T372, T373)) -> F896_IN(T370, T372, T371, T373) The TRS R consists of the following rules: f1_in([]) -> f1_out1([]) f1_in(.(T17, [])) -> f1_out1(.(T17, [])) f1_in(.(T31, .(T32, T33))) -> U1(f455_in(T31, T32, T33), .(T31, .(T32, T33))) U1(f455_out1(X38, X39, X40, X41, T39), .(T31, .(T32, T33))) -> f1_out1(T39) f645_in([]) -> f645_out1([], []) f645_in(.(T90, T91)) -> U2(f645_in(T91), .(T90, T91)) U2(f645_out1(X130, X129), .(T90, T91)) -> f645_out1(.(T90, X129), X130) f787_in(s(T198), s(T199)) -> U3(f787_in(T198, T199), s(T198), s(T199)) U3(f787_out1, s(T198), s(T199)) -> f787_out1 f787_in(0, s(0)) -> f787_out1 f787_in(0, 0) -> f787_out1 f898_in(s(T298), s(T299)) -> U4(f898_in(T298, T299), s(T298), s(T299)) U4(f898_out1, s(T298), s(T299)) -> f898_out1 f898_in(s(0), 0) -> f898_out1 f466_in(T56, T70, T71) -> U5(f645_in(T71), T56, T70, T71) U5(f645_out1(X99, X98), T56, T70, T71) -> f466_out1(.(T56, X99), .(T70, X98)) f737_in([], T131) -> f737_out1(T131) f737_in(T146, []) -> f737_out1(T146) f737_in(.(T177, T178), .(T179, T180)) -> U6(f782_in(T177, T179, T178, T180), .(T177, T178), .(T179, T180)) U6(f782_out1(T184), .(T177, T178), .(T179, T180)) -> f737_out1(.(T177, T184)) f737_in(.(T395, T396), .(T397, T398)) -> U7(f896_in(T395, T397, T396, T398), .(T395, T396), .(T397, T398)) U7(f896_out1(T402), .(T395, T396), .(T397, T398)) -> f737_out1(.(T397, T402)) f788_in([], T220, T221) -> f788_out1(.(T220, T221)) f788_in(.(T252, T253), T254, T255) -> U8(f782_in(T252, T254, T253, T255), .(T252, T253), T254, T255) U8(f782_out1(T259), .(T252, T253), T254, T255) -> f788_out1(.(T252, T259)) f788_in(.(T277, T278), T279, T280) -> U9(f896_in(T277, T279, T278, T280), .(T277, T278), T279, T280) U9(f896_out1(T284), .(T277, T278), T279, T280) -> f788_out1(.(T279, T284)) f899_in(T314, T315, []) -> f899_out1(.(T314, T315)) f899_in(T345, T346, .(T347, T348)) -> U10(f782_in(T345, T347, T346, T348), T345, T346, .(T347, T348)) U10(f782_out1(T352), T345, T346, .(T347, T348)) -> f899_out1(.(T345, T352)) f899_in(T370, T371, .(T372, T373)) -> U11(f896_in(T370, T372, T371, T373), T370, T371, .(T372, T373)) U11(f896_out1(T377), T370, T371, .(T372, T373)) -> f899_out1(.(T372, T377)) f455_in(T31, T32, T33) -> U12(f466_in(T31, T32, T33), T31, T32, T33) U12(f466_out1(T40, T41), T31, T32, T33) -> U13(f467_in(T40, T41), T31, T32, T33, T40, T41) U13(f467_out1(X40, X41, T43), T31, T32, T33, T40, T41) -> f455_out1(T40, T41, X40, X41, T43) f467_in(T40, T41) -> U14(f1_in(T40), T40, T41) U14(f1_out1(T99), T40, T41) -> U15(f731_in(T41, T99), T40, T41, T99) U15(f731_out1(X41, T101), T40, T41, T99) -> f467_out1(T99, X41, T101) f731_in(T41, T99) -> U16(f1_in(T41), T41, T99) U16(f1_out1(T107), T41, T99) -> U17(f737_in(T99, T107), T41, T99, T107) U17(f737_out1(T108), T41, T99, T107) -> f731_out1(T107, T108) f782_in(T177, T179, T178, T180) -> U18(f787_in(T177, T179), T177, T179, T178, T180) U18(f787_out1, T177, T179, T178, T180) -> U19(f788_in(T178, T179, T180), T177, T179, T178, T180) U19(f788_out1(T184), T177, T179, T178, T180) -> f782_out1(T184) f896_in(T277, T279, T278, T280) -> U20(f898_in(T277, T279), T277, T279, T278, T280) U20(f898_out1, T277, T279, T278, T280) -> U21(f899_in(T277, T278, T280), T277, T279, T278, T280) U21(f899_out1(T284), T277, T279, T278, T280) -> f896_out1(T284) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (18) 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: *U18^1(f787_out1, T177, T179, T178, T180) -> F788_IN(T178, T179, T180) The graph contains the following edges 4 >= 1, 3 >= 2, 5 >= 3 *F788_IN(.(T252, T253), T254, T255) -> F782_IN(T252, T254, T253, T255) The graph contains the following edges 1 > 1, 2 >= 2, 1 > 3, 3 >= 4 *F899_IN(T345, T346, .(T347, T348)) -> F782_IN(T345, T347, T346, T348) The graph contains the following edges 1 >= 1, 3 > 2, 2 >= 3, 3 > 4 *F788_IN(.(T277, T278), T279, T280) -> F896_IN(T277, T279, T278, T280) The graph contains the following edges 1 > 1, 2 >= 2, 1 > 3, 3 >= 4 *F782_IN(T177, T179, T178, T180) -> U18^1(f787_in(T177, T179), T177, T179, T178, T180) The graph contains the following edges 1 >= 2, 2 >= 3, 3 >= 4, 4 >= 5 *F896_IN(T277, T279, T278, T280) -> U20^1(f898_in(T277, T279), T277, T279, T278, T280) The graph contains the following edges 1 >= 2, 2 >= 3, 3 >= 4, 4 >= 5 *U20^1(f898_out1, T277, T279, T278, T280) -> F899_IN(T277, T278, T280) The graph contains the following edges 2 >= 1, 4 >= 2, 5 >= 3 *F899_IN(T370, T371, .(T372, T373)) -> F896_IN(T370, T372, T371, T373) The graph contains the following edges 1 >= 1, 3 > 2, 2 >= 3, 3 > 4 ---------------------------------------- (19) YES ---------------------------------------- (20) Obligation: Q DP problem: The TRS P consists of the following rules: F645_IN(.(T90, T91)) -> F645_IN(T91) The TRS R consists of the following rules: f1_in([]) -> f1_out1([]) f1_in(.(T17, [])) -> f1_out1(.(T17, [])) f1_in(.(T31, .(T32, T33))) -> U1(f455_in(T31, T32, T33), .(T31, .(T32, T33))) U1(f455_out1(X38, X39, X40, X41, T39), .(T31, .(T32, T33))) -> f1_out1(T39) f645_in([]) -> f645_out1([], []) f645_in(.(T90, T91)) -> U2(f645_in(T91), .(T90, T91)) U2(f645_out1(X130, X129), .(T90, T91)) -> f645_out1(.(T90, X129), X130) f787_in(s(T198), s(T199)) -> U3(f787_in(T198, T199), s(T198), s(T199)) U3(f787_out1, s(T198), s(T199)) -> f787_out1 f787_in(0, s(0)) -> f787_out1 f787_in(0, 0) -> f787_out1 f898_in(s(T298), s(T299)) -> U4(f898_in(T298, T299), s(T298), s(T299)) U4(f898_out1, s(T298), s(T299)) -> f898_out1 f898_in(s(0), 0) -> f898_out1 f466_in(T56, T70, T71) -> U5(f645_in(T71), T56, T70, T71) U5(f645_out1(X99, X98), T56, T70, T71) -> f466_out1(.(T56, X99), .(T70, X98)) f737_in([], T131) -> f737_out1(T131) f737_in(T146, []) -> f737_out1(T146) f737_in(.(T177, T178), .(T179, T180)) -> U6(f782_in(T177, T179, T178, T180), .(T177, T178), .(T179, T180)) U6(f782_out1(T184), .(T177, T178), .(T179, T180)) -> f737_out1(.(T177, T184)) f737_in(.(T395, T396), .(T397, T398)) -> U7(f896_in(T395, T397, T396, T398), .(T395, T396), .(T397, T398)) U7(f896_out1(T402), .(T395, T396), .(T397, T398)) -> f737_out1(.(T397, T402)) f788_in([], T220, T221) -> f788_out1(.(T220, T221)) f788_in(.(T252, T253), T254, T255) -> U8(f782_in(T252, T254, T253, T255), .(T252, T253), T254, T255) U8(f782_out1(T259), .(T252, T253), T254, T255) -> f788_out1(.(T252, T259)) f788_in(.(T277, T278), T279, T280) -> U9(f896_in(T277, T279, T278, T280), .(T277, T278), T279, T280) U9(f896_out1(T284), .(T277, T278), T279, T280) -> f788_out1(.(T279, T284)) f899_in(T314, T315, []) -> f899_out1(.(T314, T315)) f899_in(T345, T346, .(T347, T348)) -> U10(f782_in(T345, T347, T346, T348), T345, T346, .(T347, T348)) U10(f782_out1(T352), T345, T346, .(T347, T348)) -> f899_out1(.(T345, T352)) f899_in(T370, T371, .(T372, T373)) -> U11(f896_in(T370, T372, T371, T373), T370, T371, .(T372, T373)) U11(f896_out1(T377), T370, T371, .(T372, T373)) -> f899_out1(.(T372, T377)) f455_in(T31, T32, T33) -> U12(f466_in(T31, T32, T33), T31, T32, T33) U12(f466_out1(T40, T41), T31, T32, T33) -> U13(f467_in(T40, T41), T31, T32, T33, T40, T41) U13(f467_out1(X40, X41, T43), T31, T32, T33, T40, T41) -> f455_out1(T40, T41, X40, X41, T43) f467_in(T40, T41) -> U14(f1_in(T40), T40, T41) U14(f1_out1(T99), T40, T41) -> U15(f731_in(T41, T99), T40, T41, T99) U15(f731_out1(X41, T101), T40, T41, T99) -> f467_out1(T99, X41, T101) f731_in(T41, T99) -> U16(f1_in(T41), T41, T99) U16(f1_out1(T107), T41, T99) -> U17(f737_in(T99, T107), T41, T99, T107) U17(f737_out1(T108), T41, T99, T107) -> f731_out1(T107, T108) f782_in(T177, T179, T178, T180) -> U18(f787_in(T177, T179), T177, T179, T178, T180) U18(f787_out1, T177, T179, T178, T180) -> U19(f788_in(T178, T179, T180), T177, T179, T178, T180) U19(f788_out1(T184), T177, T179, T178, T180) -> f782_out1(T184) f896_in(T277, T279, T278, T280) -> U20(f898_in(T277, T279), T277, T279, T278, T280) U20(f898_out1, T277, T279, T278, T280) -> U21(f899_in(T277, T278, T280), T277, T279, T278, T280) U21(f899_out1(T284), T277, T279, T278, T280) -> f896_out1(T284) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (21) 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. ---------------------------------------- (22) Obligation: Q DP problem: The TRS P consists of the following rules: F645_IN(.(T90, T91)) -> F645_IN(T91) R is empty. Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (23) 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: *F645_IN(.(T90, T91)) -> F645_IN(T91) The graph contains the following edges 1 > 1 ---------------------------------------- (24) YES ---------------------------------------- (25) Obligation: Q DP problem: The TRS P consists of the following rules: F1_IN(.(T31, .(T32, T33))) -> F455_IN(T31, T32, T33) F455_IN(T31, T32, T33) -> U12^1(f466_in(T31, T32, T33), T31, T32, T33) U12^1(f466_out1(T40, T41), T31, T32, T33) -> F467_IN(T40, T41) F467_IN(T40, T41) -> U14^1(f1_in(T40), T40, T41) U14^1(f1_out1(T99), T40, T41) -> F731_IN(T41, T99) F731_IN(T41, T99) -> F1_IN(T41) F467_IN(T40, T41) -> F1_IN(T40) The TRS R consists of the following rules: f1_in([]) -> f1_out1([]) f1_in(.(T17, [])) -> f1_out1(.(T17, [])) f1_in(.(T31, .(T32, T33))) -> U1(f455_in(T31, T32, T33), .(T31, .(T32, T33))) U1(f455_out1(X38, X39, X40, X41, T39), .(T31, .(T32, T33))) -> f1_out1(T39) f645_in([]) -> f645_out1([], []) f645_in(.(T90, T91)) -> U2(f645_in(T91), .(T90, T91)) U2(f645_out1(X130, X129), .(T90, T91)) -> f645_out1(.(T90, X129), X130) f787_in(s(T198), s(T199)) -> U3(f787_in(T198, T199), s(T198), s(T199)) U3(f787_out1, s(T198), s(T199)) -> f787_out1 f787_in(0, s(0)) -> f787_out1 f787_in(0, 0) -> f787_out1 f898_in(s(T298), s(T299)) -> U4(f898_in(T298, T299), s(T298), s(T299)) U4(f898_out1, s(T298), s(T299)) -> f898_out1 f898_in(s(0), 0) -> f898_out1 f466_in(T56, T70, T71) -> U5(f645_in(T71), T56, T70, T71) U5(f645_out1(X99, X98), T56, T70, T71) -> f466_out1(.(T56, X99), .(T70, X98)) f737_in([], T131) -> f737_out1(T131) f737_in(T146, []) -> f737_out1(T146) f737_in(.(T177, T178), .(T179, T180)) -> U6(f782_in(T177, T179, T178, T180), .(T177, T178), .(T179, T180)) U6(f782_out1(T184), .(T177, T178), .(T179, T180)) -> f737_out1(.(T177, T184)) f737_in(.(T395, T396), .(T397, T398)) -> U7(f896_in(T395, T397, T396, T398), .(T395, T396), .(T397, T398)) U7(f896_out1(T402), .(T395, T396), .(T397, T398)) -> f737_out1(.(T397, T402)) f788_in([], T220, T221) -> f788_out1(.(T220, T221)) f788_in(.(T252, T253), T254, T255) -> U8(f782_in(T252, T254, T253, T255), .(T252, T253), T254, T255) U8(f782_out1(T259), .(T252, T253), T254, T255) -> f788_out1(.(T252, T259)) f788_in(.(T277, T278), T279, T280) -> U9(f896_in(T277, T279, T278, T280), .(T277, T278), T279, T280) U9(f896_out1(T284), .(T277, T278), T279, T280) -> f788_out1(.(T279, T284)) f899_in(T314, T315, []) -> f899_out1(.(T314, T315)) f899_in(T345, T346, .(T347, T348)) -> U10(f782_in(T345, T347, T346, T348), T345, T346, .(T347, T348)) U10(f782_out1(T352), T345, T346, .(T347, T348)) -> f899_out1(.(T345, T352)) f899_in(T370, T371, .(T372, T373)) -> U11(f896_in(T370, T372, T371, T373), T370, T371, .(T372, T373)) U11(f896_out1(T377), T370, T371, .(T372, T373)) -> f899_out1(.(T372, T377)) f455_in(T31, T32, T33) -> U12(f466_in(T31, T32, T33), T31, T32, T33) U12(f466_out1(T40, T41), T31, T32, T33) -> U13(f467_in(T40, T41), T31, T32, T33, T40, T41) U13(f467_out1(X40, X41, T43), T31, T32, T33, T40, T41) -> f455_out1(T40, T41, X40, X41, T43) f467_in(T40, T41) -> U14(f1_in(T40), T40, T41) U14(f1_out1(T99), T40, T41) -> U15(f731_in(T41, T99), T40, T41, T99) U15(f731_out1(X41, T101), T40, T41, T99) -> f467_out1(T99, X41, T101) f731_in(T41, T99) -> U16(f1_in(T41), T41, T99) U16(f1_out1(T107), T41, T99) -> U17(f737_in(T99, T107), T41, T99, T107) U17(f737_out1(T108), T41, T99, T107) -> f731_out1(T107, T108) f782_in(T177, T179, T178, T180) -> U18(f787_in(T177, T179), T177, T179, T178, T180) U18(f787_out1, T177, T179, T178, T180) -> U19(f788_in(T178, T179, T180), T177, T179, T178, T180) U19(f788_out1(T184), T177, T179, T178, T180) -> f782_out1(T184) f896_in(T277, T279, T278, T280) -> U20(f898_in(T277, T279), T277, T279, T278, T280) U20(f898_out1, T277, T279, T278, T280) -> U21(f899_in(T277, T278, T280), T277, T279, T278, T280) U21(f899_out1(T284), T277, T279, T278, T280) -> f896_out1(T284) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (26) QDPOrderProof (EQUIVALENT) We use the reduction pair processor [LPAR04,JAR06]. The following pairs can be oriented strictly and are deleted. F1_IN(.(T31, .(T32, T33))) -> F455_IN(T31, T32, T33) The remaining pairs can at least be oriented weakly. Used ordering: Polynomial Order [NEGPOLO,POLO] with Interpretation: POL( U12^1_4(x_1, ..., x_4) ) = x_1 + 2 POL( U12_4(x_1, ..., x_4) ) = 2x_4 + 2 POL( U14^1_3(x_1, ..., x_3) ) = x_3 POL( f466_in_3(x_1, ..., x_3) ) = 2x_3 POL( U5_4(x_1, ..., x_4) ) = 2x_1 POL( f645_in_1(x_1) ) = x_1 POL( f1_in_1(x_1) ) = 0 POL( [] ) = 0 POL( f1_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) ) = max{0, -2} POL( f455_in_3(x_1, ..., x_3) ) = 0 POL( f455_out1_5(x_1, ..., x_5) ) = x_1 + x_2 + 2x_3 + 2x_5 POL( f466_out1_2(x_1, x_2) ) = max{0, x_1 + x_2 - 2} POL( U13_6(x_1, ..., x_6) ) = max{0, x_6 - 2} POL( f467_in_2(x_1, x_2) ) = 0 POL( f467_out1_3(x_1, ..., x_3) ) = 2x_1 + 2x_2 + 2x_3 POL( U14_3(x_1, ..., x_3) ) = max{0, 2x_3 - 2} POL( U15_4(x_1, ..., x_4) ) = max{0, 2x_2 + x_4 - 2} POL( f731_in_2(x_1, x_2) ) = 0 POL( f731_out1_2(x_1, x_2) ) = 2x_1 + x_2 POL( U16_3(x_1, ..., x_3) ) = 2x_3 + 2 POL( U17_4(x_1, ..., x_4) ) = 2x_4 + 2 POL( f737_in_2(x_1, x_2) ) = 0 POL( f645_out1_2(x_1, x_2) ) = x_1 + x_2 POL( U2_2(x_1, x_2) ) = 2x_1 + 1 POL( f737_out1_1(x_1) ) = max{0, -2} POL( U6_3(x_1, ..., x_3) ) = max{0, 2x_1 - 2} POL( f782_in_4(x_1, ..., x_4) ) = 2x_2 + 2x_4 + 2 POL( U7_3(x_1, ..., x_3) ) = max{0, -2} POL( f896_in_4(x_1, ..., x_4) ) = 2x_1 + x_3 + 2x_4 POL( U18_5(x_1, ..., x_5) ) = max{0, x_4 - 2} POL( f787_in_2(x_1, x_2) ) = 2x_1 + 2 POL( f782_out1_1(x_1) ) = 2 POL( U20_5(x_1, ..., x_5) ) = max{0, 2x_1 + 2x_4 + 2x_5 - 2} POL( f898_in_2(x_1, x_2) ) = 2x_1 POL( f896_out1_1(x_1) ) = 2 POL( f787_out1 ) = 0 POL( U19_5(x_1, ..., x_5) ) = max{0, x_1 + 2x_4 + 2x_5 - 2} POL( f788_in_3(x_1, ..., x_3) ) = 0 POL( f788_out1_1(x_1) ) = x_1 + 1 POL( U8_4(x_1, ..., x_4) ) = max{0, 2x_1 + x_2 - 2} POL( s_1(x_1) ) = 0 POL( U3_3(x_1, ..., x_3) ) = 0 POL( 0 ) = 1 POL( U9_4(x_1, ..., x_4) ) = 2x_4 + 2 POL( U4_3(x_1, ..., x_3) ) = max{0, -2} POL( f898_out1 ) = 0 POL( U21_5(x_1, ..., x_5) ) = max{0, x_3 - 2} POL( f899_in_3(x_1, ..., x_3) ) = x_1 + 2x_2 + 2 POL( f899_out1_1(x_1) ) = max{0, -2} POL( U10_4(x_1, ..., x_4) ) = max{0, 2x_1 + 2x_2 - 2} POL( U11_4(x_1, ..., x_4) ) = max{0, 2x_1 + x_3 - 2} POL( F1_IN_1(x_1) ) = x_1 POL( F455_IN_3(x_1, ..., x_3) ) = 2x_3 + 2 POL( F467_IN_2(x_1, x_2) ) = x_1 + x_2 POL( F731_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: f466_in(T56, T70, T71) -> U5(f645_in(T71), T56, T70, T71) f645_in([]) -> f645_out1([], []) f645_in(.(T90, T91)) -> U2(f645_in(T91), .(T90, T91)) U5(f645_out1(X99, X98), T56, T70, T71) -> f466_out1(.(T56, X99), .(T70, X98)) U2(f645_out1(X130, X129), .(T90, T91)) -> f645_out1(.(T90, X129), X130) ---------------------------------------- (27) Obligation: Q DP problem: The TRS P consists of the following rules: F455_IN(T31, T32, T33) -> U12^1(f466_in(T31, T32, T33), T31, T32, T33) U12^1(f466_out1(T40, T41), T31, T32, T33) -> F467_IN(T40, T41) F467_IN(T40, T41) -> U14^1(f1_in(T40), T40, T41) U14^1(f1_out1(T99), T40, T41) -> F731_IN(T41, T99) F731_IN(T41, T99) -> F1_IN(T41) F467_IN(T40, T41) -> F1_IN(T40) The TRS R consists of the following rules: f1_in([]) -> f1_out1([]) f1_in(.(T17, [])) -> f1_out1(.(T17, [])) f1_in(.(T31, .(T32, T33))) -> U1(f455_in(T31, T32, T33), .(T31, .(T32, T33))) U1(f455_out1(X38, X39, X40, X41, T39), .(T31, .(T32, T33))) -> f1_out1(T39) f645_in([]) -> f645_out1([], []) f645_in(.(T90, T91)) -> U2(f645_in(T91), .(T90, T91)) U2(f645_out1(X130, X129), .(T90, T91)) -> f645_out1(.(T90, X129), X130) f787_in(s(T198), s(T199)) -> U3(f787_in(T198, T199), s(T198), s(T199)) U3(f787_out1, s(T198), s(T199)) -> f787_out1 f787_in(0, s(0)) -> f787_out1 f787_in(0, 0) -> f787_out1 f898_in(s(T298), s(T299)) -> U4(f898_in(T298, T299), s(T298), s(T299)) U4(f898_out1, s(T298), s(T299)) -> f898_out1 f898_in(s(0), 0) -> f898_out1 f466_in(T56, T70, T71) -> U5(f645_in(T71), T56, T70, T71) U5(f645_out1(X99, X98), T56, T70, T71) -> f466_out1(.(T56, X99), .(T70, X98)) f737_in([], T131) -> f737_out1(T131) f737_in(T146, []) -> f737_out1(T146) f737_in(.(T177, T178), .(T179, T180)) -> U6(f782_in(T177, T179, T178, T180), .(T177, T178), .(T179, T180)) U6(f782_out1(T184), .(T177, T178), .(T179, T180)) -> f737_out1(.(T177, T184)) f737_in(.(T395, T396), .(T397, T398)) -> U7(f896_in(T395, T397, T396, T398), .(T395, T396), .(T397, T398)) U7(f896_out1(T402), .(T395, T396), .(T397, T398)) -> f737_out1(.(T397, T402)) f788_in([], T220, T221) -> f788_out1(.(T220, T221)) f788_in(.(T252, T253), T254, T255) -> U8(f782_in(T252, T254, T253, T255), .(T252, T253), T254, T255) U8(f782_out1(T259), .(T252, T253), T254, T255) -> f788_out1(.(T252, T259)) f788_in(.(T277, T278), T279, T280) -> U9(f896_in(T277, T279, T278, T280), .(T277, T278), T279, T280) U9(f896_out1(T284), .(T277, T278), T279, T280) -> f788_out1(.(T279, T284)) f899_in(T314, T315, []) -> f899_out1(.(T314, T315)) f899_in(T345, T346, .(T347, T348)) -> U10(f782_in(T345, T347, T346, T348), T345, T346, .(T347, T348)) U10(f782_out1(T352), T345, T346, .(T347, T348)) -> f899_out1(.(T345, T352)) f899_in(T370, T371, .(T372, T373)) -> U11(f896_in(T370, T372, T371, T373), T370, T371, .(T372, T373)) U11(f896_out1(T377), T370, T371, .(T372, T373)) -> f899_out1(.(T372, T377)) f455_in(T31, T32, T33) -> U12(f466_in(T31, T32, T33), T31, T32, T33) U12(f466_out1(T40, T41), T31, T32, T33) -> U13(f467_in(T40, T41), T31, T32, T33, T40, T41) U13(f467_out1(X40, X41, T43), T31, T32, T33, T40, T41) -> f455_out1(T40, T41, X40, X41, T43) f467_in(T40, T41) -> U14(f1_in(T40), T40, T41) U14(f1_out1(T99), T40, T41) -> U15(f731_in(T41, T99), T40, T41, T99) U15(f731_out1(X41, T101), T40, T41, T99) -> f467_out1(T99, X41, T101) f731_in(T41, T99) -> U16(f1_in(T41), T41, T99) U16(f1_out1(T107), T41, T99) -> U17(f737_in(T99, T107), T41, T99, T107) U17(f737_out1(T108), T41, T99, T107) -> f731_out1(T107, T108) f782_in(T177, T179, T178, T180) -> U18(f787_in(T177, T179), T177, T179, T178, T180) U18(f787_out1, T177, T179, T178, T180) -> U19(f788_in(T178, T179, T180), T177, T179, T178, T180) U19(f788_out1(T184), T177, T179, T178, T180) -> f782_out1(T184) f896_in(T277, T279, T278, T280) -> U20(f898_in(T277, T279), T277, T279, T278, T280) U20(f898_out1, T277, T279, T278, T280) -> U21(f899_in(T277, T278, T280), T277, T279, T278, T280) U21(f899_out1(T284), T277, T279, T278, T280) -> f896_out1(T284) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (28) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 0 SCCs with 6 less nodes. ---------------------------------------- (29) TRUE