/export/starexec/sandbox2/solver/bin/starexec_run_standard /export/starexec/sandbox2/benchmark/theBenchmark.pl /export/starexec/sandbox2/output/output_files -------------------------------------------------------------------------------- YES proof of /export/starexec/sandbox2/benchmark/theBenchmark.pl # AProVE Commit ID: 794c25de1cacf0d048858bcd21c9a779e1221865 marcel 20200619 unpublished dirty Left Termination of the query pattern mergesort(g,a,a) w.r.t. the given Prolog program could successfully be proven: (0) Prolog (1) PrologToTRSTransformerProof [SOUND, 87 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) 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, 313 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": 4, "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": { "88": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "89": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "type": "Nodes", "591": { "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": [] } }, "592": { "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": [] } }, "593": { "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": [] } }, "233": { "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": [] } }, "597": { "goal": [{ "clause": -1, "scope": -1, "term": "(split T71 X99 X98 T74)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T71"], "free": [ "X98", "X99" ], "exprvars": [] } }, "598": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "599": { "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": [] } }, "874": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "754": { "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": [] } }, "755": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "91": { "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": [] } }, "93": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "10": { "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": [] } }, "17": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "19": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "4": { "goal": [{ "clause": -1, "scope": -1, "term": "(mergesort T1 T2 T3)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T1"], "free": [], "exprvars": [] } }, "6": { "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": [] } }, "800": { "goal": [{ "clause": 11, "scope": 6, "term": "(le T177 T179)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T177", "T179" ], "free": [], "exprvars": [] } }, "9": { "goal": [{ "clause": 0, "scope": 1, "term": "(mergesort T1 T2 T3)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T1"], "free": [], "exprvars": [] } }, "801": { "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": [] } }, "922": { "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": [] } }, "924": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "804": { "goal": [{ "clause": -1, "scope": -1, "term": "(le T198 T199)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T198", "T199" ], "free": [], "exprvars": [] } }, "925": { "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": [] } }, "805": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "926": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "20": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "806": { "goal": [{ "clause": 12, "scope": 6, "term": "(le T177 T179)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T177", "T179" ], "free": [], "exprvars": [] } }, "927": { "goal": [{ "clause": -1, "scope": -1, "term": "(gt T277 T279)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T277", "T279" ], "free": [], "exprvars": [] } }, "807": { "goal": [{ "clause": 13, "scope": 6, "term": "(le T177 T179)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T177", "T179" ], "free": [], "exprvars": [] } }, "928": { "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": [] } }, "808": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "929": { "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": [] } }, "809": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "27": { "goal": [{ "clause": 1, "scope": 1, "term": "(mergesort T1 T2 T3)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T1"], "free": [], "exprvars": [] } }, "28": { "goal": [{ "clause": 2, "scope": 1, "term": "(mergesort T1 T2 T3)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T1"], "free": [], "exprvars": [] } }, "892": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "893": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "256": { "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": [] } }, "894": { "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": [] } }, "259": { "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": [] } }, "930": { "goal": [{ "clause": 9, "scope": 8, "term": "(gt T277 T279)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T277", "T279" ], "free": [], "exprvars": [] } }, "810": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "931": { "goal": [{ "clause": 10, "scope": 8, "term": "(gt T277 T279)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T277", "T279" ], "free": [], "exprvars": [] } }, "811": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "932": { "goal": [{ "clause": -1, "scope": -1, "term": "(gt T298 T299)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T298", "T299" ], "free": [], "exprvars": [] } }, "812": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "933": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "813": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "934": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "814": { "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": [] } }, "935": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "936": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "816": { "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": [] } }, "937": { "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": [] } }, "938": { "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": [] } }, "818": { "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": [] } }, "939": { "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": [] } }, "940": { "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": [] } }, "666": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "941": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "700": { "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": [] } }, "942": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "668": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "701": { "goal": [{ "clause": 5, "scope": 5, "term": "(merge T99 T107 T108 (. T109 T110))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T99", "T107" ], "free": [], "exprvars": [] } }, "943": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "702": { "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": [] } }, "944": { "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": [] } }, "703": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "945": { "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": [] } }, "704": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "946": { "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": [] } }, "705": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "947": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "948": { "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": [] } }, "707": { "goal": [{ "clause": 6, "scope": 5, "term": "(merge T99 T107 T108 (. T109 T110))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T99", "T107" ], "free": [], "exprvars": [] } }, "949": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "708": { "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": [] } }, "796": { "goal": [{ "clause": -1, "scope": -1, "term": "(le T177 T179)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T177", "T179" ], "free": [], "exprvars": [] } }, "950": { "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": [] } }, "676": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "797": { "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": [] } }, "951": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "799": { "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": [] } }, "714": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "717": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "718": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "680": { "goal": [{ "clause": -1, "scope": -1, "term": "(split T91 X130 X129 T94)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T91"], "free": [ "X129", "X130" ], "exprvars": [] } }, "681": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "682": { "goal": [{ "clause": -1, "scope": -1, "term": "(mergesort T40 X40 T42)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T40"], "free": ["X40"], "exprvars": [] } }, "683": { "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": [] } }, "600": { "goal": [{ "clause": 3, "scope": 4, "term": "(split T71 X99 X98 T74)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T71"], "free": [ "X98", "X99" ], "exprvars": [] } }, "601": { "goal": [{ "clause": 4, "scope": 4, "term": "(split T71 X99 X98 T74)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T71"], "free": [ "X98", "X99" ], "exprvars": [] } }, "698": { "goal": [{ "clause": -1, "scope": -1, "term": "(mergesort T41 X41 T100)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T41"], "free": ["X41"], "exprvars": [] } }, "699": { "goal": [{ "clause": -1, "scope": -1, "term": "(merge T99 T107 T108 (. T109 T110))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T99", "T107" ], "free": [], "exprvars": [] } }, "228": { "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": [] } }, "746": { "goal": [{ "clause": 7, "scope": 5, "term": "(merge T99 T107 T108 (. T109 T110))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T99", "T107" ], "free": [], "exprvars": [] } }, "747": { "goal": [{ "clause": 8, "scope": 5, "term": "(merge T99 T107 T108 (. T109 T110))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T99", "T107" ], "free": [], "exprvars": [] } }, "902": { "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": [] } }, "903": { "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": [] } }, "86": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } } }, "edges": [ { "from": 4, "to": 6, "label": "CASE" }, { "from": 6, "to": 9, "label": "PARALLEL" }, { "from": 6, "to": 10, "label": "PARALLEL" }, { "from": 9, "to": 17, "label": "EVAL with clause\nmergesort([], [], X5).\nand substitutionT1 -> [],\nT2 -> [],\nT3 -> T8,\nX5 -> T8" }, { "from": 9, "to": 19, "label": "EVAL-BACKTRACK" }, { "from": 10, "to": 27, "label": "PARALLEL" }, { "from": 10, "to": 28, "label": "PARALLEL" }, { "from": 17, "to": 20, "label": "SUCCESS" }, { "from": 27, "to": 86, "label": "EVAL with clause\nmergesort(.(X14, []), .(X14, []), X15).\nand substitutionX14 -> T17,\nT1 -> .(T17, []),\nT2 -> .(T17, []),\nT3 -> T18,\nX15 -> T18" }, { "from": 27, "to": 88, "label": "EVAL-BACKTRACK" }, { "from": 28, "to": 91, "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": 28, "to": 93, "label": "EVAL-BACKTRACK" }, { "from": 86, "to": 89, "label": "SUCCESS" }, { "from": 91, "to": 228, "label": "SPLIT 1" }, { "from": 91, "to": 233, "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": 228, "to": 256, "label": "CASE" }, { "from": 233, "to": 682, "label": "SPLIT 1" }, { "from": 233, "to": 683, "label": "SPLIT 2\nnew knowledge:\nT40 is ground\nT99 is ground\nreplacements:X40 -> T99,\nT42 -> T100,\nT43 -> T101,\nT44 -> T102" }, { "from": 256, "to": 259, "label": "BACKTRACK\nfor clause: split([], [], [], Ls)because of non-unification" }, { "from": 259, "to": 591, "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": 591, "to": 592, "label": "CASE" }, { "from": 592, "to": 593, "label": "BACKTRACK\nfor clause: split([], [], [], Ls)because of non-unification" }, { "from": 593, "to": 597, "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": 593, "to": 598, "label": "EVAL-BACKTRACK" }, { "from": 597, "to": 599, "label": "CASE" }, { "from": 599, "to": 600, "label": "PARALLEL" }, { "from": 599, "to": 601, "label": "PARALLEL" }, { "from": 600, "to": 666, "label": "EVAL with clause\nsplit([], [], [], X106).\nand substitutionT71 -> [],\nX99 -> [],\nX98 -> [],\nT74 -> T81,\nX106 -> T81" }, { "from": 600, "to": 668, "label": "EVAL-BACKTRACK" }, { "from": 601, "to": 680, "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": 601, "to": 681, "label": "EVAL-BACKTRACK" }, { "from": 666, "to": 676, "label": "SUCCESS" }, { "from": 680, "to": 597, "label": "INSTANCE with matching:\nT71 -> T91\nX99 -> X130\nX98 -> X129\nT74 -> T94" }, { "from": 682, "to": 4, "label": "INSTANCE with matching:\nT1 -> T40\nT2 -> X40\nT3 -> T42" }, { "from": 683, "to": 698, "label": "SPLIT 1" }, { "from": 683, "to": 699, "label": "SPLIT 2\nnew knowledge:\nT41 is ground\nT107 is ground\nreplacements:X41 -> T107,\nT101 -> T108,\nT102 -> T109,\nT100 -> T110" }, { "from": 698, "to": 4, "label": "INSTANCE with matching:\nT1 -> T41\nT2 -> X41\nT3 -> T100" }, { "from": 699, "to": 700, "label": "CASE" }, { "from": 700, "to": 701, "label": "PARALLEL" }, { "from": 700, "to": 702, "label": "PARALLEL" }, { "from": 701, "to": 703, "label": "EVAL with clause\nmerge([], X153, X153, X154).\nand substitutionT99 -> [],\nT107 -> T131,\nX153 -> T131,\nT108 -> T131,\nT109 -> T132,\nT110 -> T133,\nX154 -> .(T132, T133)" }, { "from": 701, "to": 704, "label": "EVAL-BACKTRACK" }, { "from": 702, "to": 707, "label": "PARALLEL" }, { "from": 702, "to": 708, "label": "PARALLEL" }, { "from": 703, "to": 705, "label": "SUCCESS" }, { "from": 707, "to": 714, "label": "EVAL with clause\nmerge(X163, [], X163, X164).\nand substitutionT99 -> T146,\nX163 -> T146,\nT107 -> [],\nT108 -> T146,\nT109 -> T147,\nT110 -> T148,\nX164 -> .(T147, T148)" }, { "from": 707, "to": 717, "label": "EVAL-BACKTRACK" }, { "from": 708, "to": 746, "label": "PARALLEL" }, { "from": 708, "to": 747, "label": "PARALLEL" }, { "from": 714, "to": 718, "label": "SUCCESS" }, { "from": 746, "to": 754, "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": 746, "to": 755, "label": "EVAL-BACKTRACK" }, { "from": 747, "to": 950, "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": 747, "to": 951, "label": "EVAL-BACKTRACK" }, { "from": 754, "to": 796, "label": "SPLIT 1" }, { "from": 754, "to": 797, "label": "SPLIT 2\nnew knowledge:\nT177 is ground\nT179 is ground" }, { "from": 796, "to": 799, "label": "CASE" }, { "from": 797, "to": 814, "label": "CASE" }, { "from": 799, "to": 800, "label": "PARALLEL" }, { "from": 799, "to": 801, "label": "PARALLEL" }, { "from": 800, "to": 804, "label": "EVAL with clause\nle(s(X212), s(X213)) :- le(X212, X213).\nand substitutionX212 -> T198,\nT177 -> s(T198),\nX213 -> T199,\nT179 -> s(T199)" }, { "from": 800, "to": 805, "label": "EVAL-BACKTRACK" }, { "from": 801, "to": 806, "label": "PARALLEL" }, { "from": 801, "to": 807, "label": "PARALLEL" }, { "from": 804, "to": 796, "label": "INSTANCE with matching:\nT177 -> T198\nT179 -> T199" }, { "from": 806, "to": 808, "label": "EVAL with clause\nle(0, s(0)).\nand substitutionT177 -> 0,\nT179 -> s(0)" }, { "from": 806, "to": 809, "label": "EVAL-BACKTRACK" }, { "from": 807, "to": 811, "label": "EVAL with clause\nle(0, 0).\nand substitutionT177 -> 0,\nT179 -> 0" }, { "from": 807, "to": 812, "label": "EVAL-BACKTRACK" }, { "from": 808, "to": 810, "label": "SUCCESS" }, { "from": 811, "to": 813, "label": "SUCCESS" }, { "from": 814, "to": 816, "label": "PARALLEL" }, { "from": 814, "to": 818, "label": "PARALLEL" }, { "from": 816, "to": 874, "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": 816, "to": 892, "label": "EVAL-BACKTRACK" }, { "from": 818, "to": 894, "label": "BACKTRACK\nfor clause: merge(Xs, [], Xs, Ls)because of non-unification" }, { "from": 874, "to": 893, "label": "SUCCESS" }, { "from": 894, "to": 902, "label": "PARALLEL" }, { "from": 894, "to": 903, "label": "PARALLEL" }, { "from": 902, "to": 922, "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": 902, "to": 924, "label": "EVAL-BACKTRACK" }, { "from": 903, "to": 925, "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": 903, "to": 926, "label": "EVAL-BACKTRACK" }, { "from": 922, "to": 754, "label": "INSTANCE with matching:\nT177 -> T252\nT179 -> T254\nT178 -> T253\nT180 -> T255\nT184 -> T259\nT185 -> T260" }, { "from": 925, "to": 927, "label": "SPLIT 1" }, { "from": 925, "to": 928, "label": "SPLIT 2\nnew knowledge:\nT277 is ground\nT279 is ground" }, { "from": 927, "to": 929, "label": "CASE" }, { "from": 928, "to": 937, "label": "CASE" }, { "from": 929, "to": 930, "label": "PARALLEL" }, { "from": 929, "to": 931, "label": "PARALLEL" }, { "from": 930, "to": 932, "label": "EVAL with clause\ngt(s(X302), s(X303)) :- gt(X302, X303).\nand substitutionX302 -> T298,\nT277 -> s(T298),\nX303 -> T299,\nT279 -> s(T299)" }, { "from": 930, "to": 933, "label": "EVAL-BACKTRACK" }, { "from": 931, "to": 934, "label": "EVAL with clause\ngt(s(0), 0).\nand substitutionT277 -> s(0),\nT279 -> 0" }, { "from": 931, "to": 935, "label": "EVAL-BACKTRACK" }, { "from": 932, "to": 927, "label": "INSTANCE with matching:\nT277 -> T298\nT279 -> T299" }, { "from": 934, "to": 936, "label": "SUCCESS" }, { "from": 937, "to": 938, "label": "BACKTRACK\nfor clause: merge([], Xs, Xs, Ls)because of non-unification" }, { "from": 938, "to": 939, "label": "PARALLEL" }, { "from": 938, "to": 940, "label": "PARALLEL" }, { "from": 939, "to": 941, "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": 939, "to": 942, "label": "EVAL-BACKTRACK" }, { "from": 940, "to": 944, "label": "PARALLEL" }, { "from": 940, "to": 945, "label": "PARALLEL" }, { "from": 941, "to": 943, "label": "SUCCESS" }, { "from": 944, "to": 946, "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": 944, "to": 947, "label": "EVAL-BACKTRACK" }, { "from": 945, "to": 948, "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": 945, "to": 949, "label": "EVAL-BACKTRACK" }, { "from": 946, "to": 754, "label": "INSTANCE with matching:\nT177 -> T345\nT179 -> T347\nT178 -> T346\nT180 -> T348\nT184 -> T352\nT185 -> T353" }, { "from": 948, "to": 925, "label": "INSTANCE with matching:\nT277 -> T370\nT279 -> T372\nT278 -> T371\nT280 -> T373\nT284 -> T377\nT285 -> T378" }, { "from": 950, "to": 925, "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: f4_in([]) -> f4_out1([]) f4_in(.(T17, [])) -> f4_out1(.(T17, [])) f4_in(.(T31, .(T32, T33))) -> U1(f91_in(T31, T32, T33), .(T31, .(T32, T33))) U1(f91_out1(X38, X39, X40, X41, T39), .(T31, .(T32, T33))) -> f4_out1(T39) f597_in([]) -> f597_out1([], []) f597_in(.(T90, T91)) -> U2(f597_in(T91), .(T90, T91)) U2(f597_out1(X130, X129), .(T90, T91)) -> f597_out1(.(T90, X129), X130) f796_in(s(T198), s(T199)) -> U3(f796_in(T198, T199), s(T198), s(T199)) U3(f796_out1, s(T198), s(T199)) -> f796_out1 f796_in(0, s(0)) -> f796_out1 f796_in(0, 0) -> f796_out1 f927_in(s(T298), s(T299)) -> U4(f927_in(T298, T299), s(T298), s(T299)) U4(f927_out1, s(T298), s(T299)) -> f927_out1 f927_in(s(0), 0) -> f927_out1 f228_in(T56, T70, T71) -> U5(f597_in(T71), T56, T70, T71) U5(f597_out1(X99, X98), T56, T70, T71) -> f228_out1(.(T56, X99), .(T70, X98)) f699_in([], T131) -> f699_out1(T131) f699_in(T146, []) -> f699_out1(T146) f699_in(.(T177, T178), .(T179, T180)) -> U6(f754_in(T177, T179, T178, T180), .(T177, T178), .(T179, T180)) U6(f754_out1(T184), .(T177, T178), .(T179, T180)) -> f699_out1(.(T177, T184)) f699_in(.(T395, T396), .(T397, T398)) -> U7(f925_in(T395, T397, T396, T398), .(T395, T396), .(T397, T398)) U7(f925_out1(T402), .(T395, T396), .(T397, T398)) -> f699_out1(.(T397, T402)) f797_in([], T220, T221) -> f797_out1(.(T220, T221)) f797_in(.(T252, T253), T254, T255) -> U8(f754_in(T252, T254, T253, T255), .(T252, T253), T254, T255) U8(f754_out1(T259), .(T252, T253), T254, T255) -> f797_out1(.(T252, T259)) f797_in(.(T277, T278), T279, T280) -> U9(f925_in(T277, T279, T278, T280), .(T277, T278), T279, T280) U9(f925_out1(T284), .(T277, T278), T279, T280) -> f797_out1(.(T279, T284)) f928_in(T314, T315, []) -> f928_out1(.(T314, T315)) f928_in(T345, T346, .(T347, T348)) -> U10(f754_in(T345, T347, T346, T348), T345, T346, .(T347, T348)) U10(f754_out1(T352), T345, T346, .(T347, T348)) -> f928_out1(.(T345, T352)) f928_in(T370, T371, .(T372, T373)) -> U11(f925_in(T370, T372, T371, T373), T370, T371, .(T372, T373)) U11(f925_out1(T377), T370, T371, .(T372, T373)) -> f928_out1(.(T372, T377)) f91_in(T31, T32, T33) -> U12(f228_in(T31, T32, T33), T31, T32, T33) U12(f228_out1(T40, T41), T31, T32, T33) -> U13(f233_in(T40, T41), T31, T32, T33, T40, T41) U13(f233_out1(X40, X41, T43), T31, T32, T33, T40, T41) -> f91_out1(T40, T41, X40, X41, T43) f233_in(T40, T41) -> U14(f4_in(T40), T40, T41) U14(f4_out1(T99), T40, T41) -> U15(f683_in(T41, T99), T40, T41, T99) U15(f683_out1(X41, T101), T40, T41, T99) -> f233_out1(T99, X41, T101) f683_in(T41, T99) -> U16(f4_in(T41), T41, T99) U16(f4_out1(T107), T41, T99) -> U17(f699_in(T99, T107), T41, T99, T107) U17(f699_out1(T108), T41, T99, T107) -> f683_out1(T107, T108) f754_in(T177, T179, T178, T180) -> U18(f796_in(T177, T179), T177, T179, T178, T180) U18(f796_out1, T177, T179, T178, T180) -> U19(f797_in(T178, T179, T180), T177, T179, T178, T180) U19(f797_out1(T184), T177, T179, T178, T180) -> f754_out1(T184) f925_in(T277, T279, T278, T280) -> U20(f927_in(T277, T279), T277, T279, T278, T280) U20(f927_out1, T277, T279, T278, T280) -> U21(f928_in(T277, T278, T280), T277, T279, T278, T280) U21(f928_out1(T284), T277, T279, T278, T280) -> f925_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: F4_IN(.(T31, .(T32, T33))) -> U1^1(f91_in(T31, T32, T33), .(T31, .(T32, T33))) F4_IN(.(T31, .(T32, T33))) -> F91_IN(T31, T32, T33) F597_IN(.(T90, T91)) -> U2^1(f597_in(T91), .(T90, T91)) F597_IN(.(T90, T91)) -> F597_IN(T91) F796_IN(s(T198), s(T199)) -> U3^1(f796_in(T198, T199), s(T198), s(T199)) F796_IN(s(T198), s(T199)) -> F796_IN(T198, T199) F927_IN(s(T298), s(T299)) -> U4^1(f927_in(T298, T299), s(T298), s(T299)) F927_IN(s(T298), s(T299)) -> F927_IN(T298, T299) F228_IN(T56, T70, T71) -> U5^1(f597_in(T71), T56, T70, T71) F228_IN(T56, T70, T71) -> F597_IN(T71) F699_IN(.(T177, T178), .(T179, T180)) -> U6^1(f754_in(T177, T179, T178, T180), .(T177, T178), .(T179, T180)) F699_IN(.(T177, T178), .(T179, T180)) -> F754_IN(T177, T179, T178, T180) F699_IN(.(T395, T396), .(T397, T398)) -> U7^1(f925_in(T395, T397, T396, T398), .(T395, T396), .(T397, T398)) F699_IN(.(T395, T396), .(T397, T398)) -> F925_IN(T395, T397, T396, T398) F797_IN(.(T252, T253), T254, T255) -> U8^1(f754_in(T252, T254, T253, T255), .(T252, T253), T254, T255) F797_IN(.(T252, T253), T254, T255) -> F754_IN(T252, T254, T253, T255) F797_IN(.(T277, T278), T279, T280) -> U9^1(f925_in(T277, T279, T278, T280), .(T277, T278), T279, T280) F797_IN(.(T277, T278), T279, T280) -> F925_IN(T277, T279, T278, T280) F928_IN(T345, T346, .(T347, T348)) -> U10^1(f754_in(T345, T347, T346, T348), T345, T346, .(T347, T348)) F928_IN(T345, T346, .(T347, T348)) -> F754_IN(T345, T347, T346, T348) F928_IN(T370, T371, .(T372, T373)) -> U11^1(f925_in(T370, T372, T371, T373), T370, T371, .(T372, T373)) F928_IN(T370, T371, .(T372, T373)) -> F925_IN(T370, T372, T371, T373) F91_IN(T31, T32, T33) -> U12^1(f228_in(T31, T32, T33), T31, T32, T33) F91_IN(T31, T32, T33) -> F228_IN(T31, T32, T33) U12^1(f228_out1(T40, T41), T31, T32, T33) -> U13^1(f233_in(T40, T41), T31, T32, T33, T40, T41) U12^1(f228_out1(T40, T41), T31, T32, T33) -> F233_IN(T40, T41) F233_IN(T40, T41) -> U14^1(f4_in(T40), T40, T41) F233_IN(T40, T41) -> F4_IN(T40) U14^1(f4_out1(T99), T40, T41) -> U15^1(f683_in(T41, T99), T40, T41, T99) U14^1(f4_out1(T99), T40, T41) -> F683_IN(T41, T99) F683_IN(T41, T99) -> U16^1(f4_in(T41), T41, T99) F683_IN(T41, T99) -> F4_IN(T41) U16^1(f4_out1(T107), T41, T99) -> U17^1(f699_in(T99, T107), T41, T99, T107) U16^1(f4_out1(T107), T41, T99) -> F699_IN(T99, T107) F754_IN(T177, T179, T178, T180) -> U18^1(f796_in(T177, T179), T177, T179, T178, T180) F754_IN(T177, T179, T178, T180) -> F796_IN(T177, T179) U18^1(f796_out1, T177, T179, T178, T180) -> U19^1(f797_in(T178, T179, T180), T177, T179, T178, T180) U18^1(f796_out1, T177, T179, T178, T180) -> F797_IN(T178, T179, T180) F925_IN(T277, T279, T278, T280) -> U20^1(f927_in(T277, T279), T277, T279, T278, T280) F925_IN(T277, T279, T278, T280) -> F927_IN(T277, T279) U20^1(f927_out1, T277, T279, T278, T280) -> U21^1(f928_in(T277, T278, T280), T277, T279, T278, T280) U20^1(f927_out1, T277, T279, T278, T280) -> F928_IN(T277, T278, T280) The TRS R consists of the following rules: f4_in([]) -> f4_out1([]) f4_in(.(T17, [])) -> f4_out1(.(T17, [])) f4_in(.(T31, .(T32, T33))) -> U1(f91_in(T31, T32, T33), .(T31, .(T32, T33))) U1(f91_out1(X38, X39, X40, X41, T39), .(T31, .(T32, T33))) -> f4_out1(T39) f597_in([]) -> f597_out1([], []) f597_in(.(T90, T91)) -> U2(f597_in(T91), .(T90, T91)) U2(f597_out1(X130, X129), .(T90, T91)) -> f597_out1(.(T90, X129), X130) f796_in(s(T198), s(T199)) -> U3(f796_in(T198, T199), s(T198), s(T199)) U3(f796_out1, s(T198), s(T199)) -> f796_out1 f796_in(0, s(0)) -> f796_out1 f796_in(0, 0) -> f796_out1 f927_in(s(T298), s(T299)) -> U4(f927_in(T298, T299), s(T298), s(T299)) U4(f927_out1, s(T298), s(T299)) -> f927_out1 f927_in(s(0), 0) -> f927_out1 f228_in(T56, T70, T71) -> U5(f597_in(T71), T56, T70, T71) U5(f597_out1(X99, X98), T56, T70, T71) -> f228_out1(.(T56, X99), .(T70, X98)) f699_in([], T131) -> f699_out1(T131) f699_in(T146, []) -> f699_out1(T146) f699_in(.(T177, T178), .(T179, T180)) -> U6(f754_in(T177, T179, T178, T180), .(T177, T178), .(T179, T180)) U6(f754_out1(T184), .(T177, T178), .(T179, T180)) -> f699_out1(.(T177, T184)) f699_in(.(T395, T396), .(T397, T398)) -> U7(f925_in(T395, T397, T396, T398), .(T395, T396), .(T397, T398)) U7(f925_out1(T402), .(T395, T396), .(T397, T398)) -> f699_out1(.(T397, T402)) f797_in([], T220, T221) -> f797_out1(.(T220, T221)) f797_in(.(T252, T253), T254, T255) -> U8(f754_in(T252, T254, T253, T255), .(T252, T253), T254, T255) U8(f754_out1(T259), .(T252, T253), T254, T255) -> f797_out1(.(T252, T259)) f797_in(.(T277, T278), T279, T280) -> U9(f925_in(T277, T279, T278, T280), .(T277, T278), T279, T280) U9(f925_out1(T284), .(T277, T278), T279, T280) -> f797_out1(.(T279, T284)) f928_in(T314, T315, []) -> f928_out1(.(T314, T315)) f928_in(T345, T346, .(T347, T348)) -> U10(f754_in(T345, T347, T346, T348), T345, T346, .(T347, T348)) U10(f754_out1(T352), T345, T346, .(T347, T348)) -> f928_out1(.(T345, T352)) f928_in(T370, T371, .(T372, T373)) -> U11(f925_in(T370, T372, T371, T373), T370, T371, .(T372, T373)) U11(f925_out1(T377), T370, T371, .(T372, T373)) -> f928_out1(.(T372, T377)) f91_in(T31, T32, T33) -> U12(f228_in(T31, T32, T33), T31, T32, T33) U12(f228_out1(T40, T41), T31, T32, T33) -> U13(f233_in(T40, T41), T31, T32, T33, T40, T41) U13(f233_out1(X40, X41, T43), T31, T32, T33, T40, T41) -> f91_out1(T40, T41, X40, X41, T43) f233_in(T40, T41) -> U14(f4_in(T40), T40, T41) U14(f4_out1(T99), T40, T41) -> U15(f683_in(T41, T99), T40, T41, T99) U15(f683_out1(X41, T101), T40, T41, T99) -> f233_out1(T99, X41, T101) f683_in(T41, T99) -> U16(f4_in(T41), T41, T99) U16(f4_out1(T107), T41, T99) -> U17(f699_in(T99, T107), T41, T99, T107) U17(f699_out1(T108), T41, T99, T107) -> f683_out1(T107, T108) f754_in(T177, T179, T178, T180) -> U18(f796_in(T177, T179), T177, T179, T178, T180) U18(f796_out1, T177, T179, T178, T180) -> U19(f797_in(T178, T179, T180), T177, T179, T178, T180) U19(f797_out1(T184), T177, T179, T178, T180) -> f754_out1(T184) f925_in(T277, T279, T278, T280) -> U20(f927_in(T277, T279), T277, T279, T278, T280) U20(f927_out1, T277, T279, T278, T280) -> U21(f928_in(T277, T278, T280), T277, T279, T278, T280) U21(f928_out1(T284), T277, T279, T278, T280) -> f925_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: F927_IN(s(T298), s(T299)) -> F927_IN(T298, T299) The TRS R consists of the following rules: f4_in([]) -> f4_out1([]) f4_in(.(T17, [])) -> f4_out1(.(T17, [])) f4_in(.(T31, .(T32, T33))) -> U1(f91_in(T31, T32, T33), .(T31, .(T32, T33))) U1(f91_out1(X38, X39, X40, X41, T39), .(T31, .(T32, T33))) -> f4_out1(T39) f597_in([]) -> f597_out1([], []) f597_in(.(T90, T91)) -> U2(f597_in(T91), .(T90, T91)) U2(f597_out1(X130, X129), .(T90, T91)) -> f597_out1(.(T90, X129), X130) f796_in(s(T198), s(T199)) -> U3(f796_in(T198, T199), s(T198), s(T199)) U3(f796_out1, s(T198), s(T199)) -> f796_out1 f796_in(0, s(0)) -> f796_out1 f796_in(0, 0) -> f796_out1 f927_in(s(T298), s(T299)) -> U4(f927_in(T298, T299), s(T298), s(T299)) U4(f927_out1, s(T298), s(T299)) -> f927_out1 f927_in(s(0), 0) -> f927_out1 f228_in(T56, T70, T71) -> U5(f597_in(T71), T56, T70, T71) U5(f597_out1(X99, X98), T56, T70, T71) -> f228_out1(.(T56, X99), .(T70, X98)) f699_in([], T131) -> f699_out1(T131) f699_in(T146, []) -> f699_out1(T146) f699_in(.(T177, T178), .(T179, T180)) -> U6(f754_in(T177, T179, T178, T180), .(T177, T178), .(T179, T180)) U6(f754_out1(T184), .(T177, T178), .(T179, T180)) -> f699_out1(.(T177, T184)) f699_in(.(T395, T396), .(T397, T398)) -> U7(f925_in(T395, T397, T396, T398), .(T395, T396), .(T397, T398)) U7(f925_out1(T402), .(T395, T396), .(T397, T398)) -> f699_out1(.(T397, T402)) f797_in([], T220, T221) -> f797_out1(.(T220, T221)) f797_in(.(T252, T253), T254, T255) -> U8(f754_in(T252, T254, T253, T255), .(T252, T253), T254, T255) U8(f754_out1(T259), .(T252, T253), T254, T255) -> f797_out1(.(T252, T259)) f797_in(.(T277, T278), T279, T280) -> U9(f925_in(T277, T279, T278, T280), .(T277, T278), T279, T280) U9(f925_out1(T284), .(T277, T278), T279, T280) -> f797_out1(.(T279, T284)) f928_in(T314, T315, []) -> f928_out1(.(T314, T315)) f928_in(T345, T346, .(T347, T348)) -> U10(f754_in(T345, T347, T346, T348), T345, T346, .(T347, T348)) U10(f754_out1(T352), T345, T346, .(T347, T348)) -> f928_out1(.(T345, T352)) f928_in(T370, T371, .(T372, T373)) -> U11(f925_in(T370, T372, T371, T373), T370, T371, .(T372, T373)) U11(f925_out1(T377), T370, T371, .(T372, T373)) -> f928_out1(.(T372, T377)) f91_in(T31, T32, T33) -> U12(f228_in(T31, T32, T33), T31, T32, T33) U12(f228_out1(T40, T41), T31, T32, T33) -> U13(f233_in(T40, T41), T31, T32, T33, T40, T41) U13(f233_out1(X40, X41, T43), T31, T32, T33, T40, T41) -> f91_out1(T40, T41, X40, X41, T43) f233_in(T40, T41) -> U14(f4_in(T40), T40, T41) U14(f4_out1(T99), T40, T41) -> U15(f683_in(T41, T99), T40, T41, T99) U15(f683_out1(X41, T101), T40, T41, T99) -> f233_out1(T99, X41, T101) f683_in(T41, T99) -> U16(f4_in(T41), T41, T99) U16(f4_out1(T107), T41, T99) -> U17(f699_in(T99, T107), T41, T99, T107) U17(f699_out1(T108), T41, T99, T107) -> f683_out1(T107, T108) f754_in(T177, T179, T178, T180) -> U18(f796_in(T177, T179), T177, T179, T178, T180) U18(f796_out1, T177, T179, T178, T180) -> U19(f797_in(T178, T179, T180), T177, T179, T178, T180) U19(f797_out1(T184), T177, T179, T178, T180) -> f754_out1(T184) f925_in(T277, T279, T278, T280) -> U20(f927_in(T277, T279), T277, T279, T278, T280) U20(f927_out1, T277, T279, T278, T280) -> U21(f928_in(T277, T278, T280), T277, T279, T278, T280) U21(f928_out1(T284), T277, T279, T278, T280) -> f925_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: F927_IN(s(T298), s(T299)) -> F927_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: *F927_IN(s(T298), s(T299)) -> F927_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: F796_IN(s(T198), s(T199)) -> F796_IN(T198, T199) The TRS R consists of the following rules: f4_in([]) -> f4_out1([]) f4_in(.(T17, [])) -> f4_out1(.(T17, [])) f4_in(.(T31, .(T32, T33))) -> U1(f91_in(T31, T32, T33), .(T31, .(T32, T33))) U1(f91_out1(X38, X39, X40, X41, T39), .(T31, .(T32, T33))) -> f4_out1(T39) f597_in([]) -> f597_out1([], []) f597_in(.(T90, T91)) -> U2(f597_in(T91), .(T90, T91)) U2(f597_out1(X130, X129), .(T90, T91)) -> f597_out1(.(T90, X129), X130) f796_in(s(T198), s(T199)) -> U3(f796_in(T198, T199), s(T198), s(T199)) U3(f796_out1, s(T198), s(T199)) -> f796_out1 f796_in(0, s(0)) -> f796_out1 f796_in(0, 0) -> f796_out1 f927_in(s(T298), s(T299)) -> U4(f927_in(T298, T299), s(T298), s(T299)) U4(f927_out1, s(T298), s(T299)) -> f927_out1 f927_in(s(0), 0) -> f927_out1 f228_in(T56, T70, T71) -> U5(f597_in(T71), T56, T70, T71) U5(f597_out1(X99, X98), T56, T70, T71) -> f228_out1(.(T56, X99), .(T70, X98)) f699_in([], T131) -> f699_out1(T131) f699_in(T146, []) -> f699_out1(T146) f699_in(.(T177, T178), .(T179, T180)) -> U6(f754_in(T177, T179, T178, T180), .(T177, T178), .(T179, T180)) U6(f754_out1(T184), .(T177, T178), .(T179, T180)) -> f699_out1(.(T177, T184)) f699_in(.(T395, T396), .(T397, T398)) -> U7(f925_in(T395, T397, T396, T398), .(T395, T396), .(T397, T398)) U7(f925_out1(T402), .(T395, T396), .(T397, T398)) -> f699_out1(.(T397, T402)) f797_in([], T220, T221) -> f797_out1(.(T220, T221)) f797_in(.(T252, T253), T254, T255) -> U8(f754_in(T252, T254, T253, T255), .(T252, T253), T254, T255) U8(f754_out1(T259), .(T252, T253), T254, T255) -> f797_out1(.(T252, T259)) f797_in(.(T277, T278), T279, T280) -> U9(f925_in(T277, T279, T278, T280), .(T277, T278), T279, T280) U9(f925_out1(T284), .(T277, T278), T279, T280) -> f797_out1(.(T279, T284)) f928_in(T314, T315, []) -> f928_out1(.(T314, T315)) f928_in(T345, T346, .(T347, T348)) -> U10(f754_in(T345, T347, T346, T348), T345, T346, .(T347, T348)) U10(f754_out1(T352), T345, T346, .(T347, T348)) -> f928_out1(.(T345, T352)) f928_in(T370, T371, .(T372, T373)) -> U11(f925_in(T370, T372, T371, T373), T370, T371, .(T372, T373)) U11(f925_out1(T377), T370, T371, .(T372, T373)) -> f928_out1(.(T372, T377)) f91_in(T31, T32, T33) -> U12(f228_in(T31, T32, T33), T31, T32, T33) U12(f228_out1(T40, T41), T31, T32, T33) -> U13(f233_in(T40, T41), T31, T32, T33, T40, T41) U13(f233_out1(X40, X41, T43), T31, T32, T33, T40, T41) -> f91_out1(T40, T41, X40, X41, T43) f233_in(T40, T41) -> U14(f4_in(T40), T40, T41) U14(f4_out1(T99), T40, T41) -> U15(f683_in(T41, T99), T40, T41, T99) U15(f683_out1(X41, T101), T40, T41, T99) -> f233_out1(T99, X41, T101) f683_in(T41, T99) -> U16(f4_in(T41), T41, T99) U16(f4_out1(T107), T41, T99) -> U17(f699_in(T99, T107), T41, T99, T107) U17(f699_out1(T108), T41, T99, T107) -> f683_out1(T107, T108) f754_in(T177, T179, T178, T180) -> U18(f796_in(T177, T179), T177, T179, T178, T180) U18(f796_out1, T177, T179, T178, T180) -> U19(f797_in(T178, T179, T180), T177, T179, T178, T180) U19(f797_out1(T184), T177, T179, T178, T180) -> f754_out1(T184) f925_in(T277, T279, T278, T280) -> U20(f927_in(T277, T279), T277, T279, T278, T280) U20(f927_out1, T277, T279, T278, T280) -> U21(f928_in(T277, T278, T280), T277, T279, T278, T280) U21(f928_out1(T284), T277, T279, T278, T280) -> f925_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: F796_IN(s(T198), s(T199)) -> F796_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: *F796_IN(s(T198), s(T199)) -> F796_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: F754_IN(T177, T179, T178, T180) -> U18^1(f796_in(T177, T179), T177, T179, T178, T180) U18^1(f796_out1, T177, T179, T178, T180) -> F797_IN(T178, T179, T180) F797_IN(.(T252, T253), T254, T255) -> F754_IN(T252, T254, T253, T255) F797_IN(.(T277, T278), T279, T280) -> F925_IN(T277, T279, T278, T280) F925_IN(T277, T279, T278, T280) -> U20^1(f927_in(T277, T279), T277, T279, T278, T280) U20^1(f927_out1, T277, T279, T278, T280) -> F928_IN(T277, T278, T280) F928_IN(T345, T346, .(T347, T348)) -> F754_IN(T345, T347, T346, T348) F928_IN(T370, T371, .(T372, T373)) -> F925_IN(T370, T372, T371, T373) The TRS R consists of the following rules: f4_in([]) -> f4_out1([]) f4_in(.(T17, [])) -> f4_out1(.(T17, [])) f4_in(.(T31, .(T32, T33))) -> U1(f91_in(T31, T32, T33), .(T31, .(T32, T33))) U1(f91_out1(X38, X39, X40, X41, T39), .(T31, .(T32, T33))) -> f4_out1(T39) f597_in([]) -> f597_out1([], []) f597_in(.(T90, T91)) -> U2(f597_in(T91), .(T90, T91)) U2(f597_out1(X130, X129), .(T90, T91)) -> f597_out1(.(T90, X129), X130) f796_in(s(T198), s(T199)) -> U3(f796_in(T198, T199), s(T198), s(T199)) U3(f796_out1, s(T198), s(T199)) -> f796_out1 f796_in(0, s(0)) -> f796_out1 f796_in(0, 0) -> f796_out1 f927_in(s(T298), s(T299)) -> U4(f927_in(T298, T299), s(T298), s(T299)) U4(f927_out1, s(T298), s(T299)) -> f927_out1 f927_in(s(0), 0) -> f927_out1 f228_in(T56, T70, T71) -> U5(f597_in(T71), T56, T70, T71) U5(f597_out1(X99, X98), T56, T70, T71) -> f228_out1(.(T56, X99), .(T70, X98)) f699_in([], T131) -> f699_out1(T131) f699_in(T146, []) -> f699_out1(T146) f699_in(.(T177, T178), .(T179, T180)) -> U6(f754_in(T177, T179, T178, T180), .(T177, T178), .(T179, T180)) U6(f754_out1(T184), .(T177, T178), .(T179, T180)) -> f699_out1(.(T177, T184)) f699_in(.(T395, T396), .(T397, T398)) -> U7(f925_in(T395, T397, T396, T398), .(T395, T396), .(T397, T398)) U7(f925_out1(T402), .(T395, T396), .(T397, T398)) -> f699_out1(.(T397, T402)) f797_in([], T220, T221) -> f797_out1(.(T220, T221)) f797_in(.(T252, T253), T254, T255) -> U8(f754_in(T252, T254, T253, T255), .(T252, T253), T254, T255) U8(f754_out1(T259), .(T252, T253), T254, T255) -> f797_out1(.(T252, T259)) f797_in(.(T277, T278), T279, T280) -> U9(f925_in(T277, T279, T278, T280), .(T277, T278), T279, T280) U9(f925_out1(T284), .(T277, T278), T279, T280) -> f797_out1(.(T279, T284)) f928_in(T314, T315, []) -> f928_out1(.(T314, T315)) f928_in(T345, T346, .(T347, T348)) -> U10(f754_in(T345, T347, T346, T348), T345, T346, .(T347, T348)) U10(f754_out1(T352), T345, T346, .(T347, T348)) -> f928_out1(.(T345, T352)) f928_in(T370, T371, .(T372, T373)) -> U11(f925_in(T370, T372, T371, T373), T370, T371, .(T372, T373)) U11(f925_out1(T377), T370, T371, .(T372, T373)) -> f928_out1(.(T372, T377)) f91_in(T31, T32, T33) -> U12(f228_in(T31, T32, T33), T31, T32, T33) U12(f228_out1(T40, T41), T31, T32, T33) -> U13(f233_in(T40, T41), T31, T32, T33, T40, T41) U13(f233_out1(X40, X41, T43), T31, T32, T33, T40, T41) -> f91_out1(T40, T41, X40, X41, T43) f233_in(T40, T41) -> U14(f4_in(T40), T40, T41) U14(f4_out1(T99), T40, T41) -> U15(f683_in(T41, T99), T40, T41, T99) U15(f683_out1(X41, T101), T40, T41, T99) -> f233_out1(T99, X41, T101) f683_in(T41, T99) -> U16(f4_in(T41), T41, T99) U16(f4_out1(T107), T41, T99) -> U17(f699_in(T99, T107), T41, T99, T107) U17(f699_out1(T108), T41, T99, T107) -> f683_out1(T107, T108) f754_in(T177, T179, T178, T180) -> U18(f796_in(T177, T179), T177, T179, T178, T180) U18(f796_out1, T177, T179, T178, T180) -> U19(f797_in(T178, T179, T180), T177, T179, T178, T180) U19(f797_out1(T184), T177, T179, T178, T180) -> f754_out1(T184) f925_in(T277, T279, T278, T280) -> U20(f927_in(T277, T279), T277, T279, T278, T280) U20(f927_out1, T277, T279, T278, T280) -> U21(f928_in(T277, T278, T280), T277, T279, T278, T280) U21(f928_out1(T284), T277, T279, T278, T280) -> f925_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(f796_out1, T177, T179, T178, T180) -> F797_IN(T178, T179, T180) The graph contains the following edges 4 >= 1, 3 >= 2, 5 >= 3 *F797_IN(.(T252, T253), T254, T255) -> F754_IN(T252, T254, T253, T255) The graph contains the following edges 1 > 1, 2 >= 2, 1 > 3, 3 >= 4 *F928_IN(T345, T346, .(T347, T348)) -> F754_IN(T345, T347, T346, T348) The graph contains the following edges 1 >= 1, 3 > 2, 2 >= 3, 3 > 4 *F797_IN(.(T277, T278), T279, T280) -> F925_IN(T277, T279, T278, T280) The graph contains the following edges 1 > 1, 2 >= 2, 1 > 3, 3 >= 4 *F754_IN(T177, T179, T178, T180) -> U18^1(f796_in(T177, T179), T177, T179, T178, T180) The graph contains the following edges 1 >= 2, 2 >= 3, 3 >= 4, 4 >= 5 *F925_IN(T277, T279, T278, T280) -> U20^1(f927_in(T277, T279), T277, T279, T278, T280) The graph contains the following edges 1 >= 2, 2 >= 3, 3 >= 4, 4 >= 5 *U20^1(f927_out1, T277, T279, T278, T280) -> F928_IN(T277, T278, T280) The graph contains the following edges 2 >= 1, 4 >= 2, 5 >= 3 *F928_IN(T370, T371, .(T372, T373)) -> F925_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: F597_IN(.(T90, T91)) -> F597_IN(T91) The TRS R consists of the following rules: f4_in([]) -> f4_out1([]) f4_in(.(T17, [])) -> f4_out1(.(T17, [])) f4_in(.(T31, .(T32, T33))) -> U1(f91_in(T31, T32, T33), .(T31, .(T32, T33))) U1(f91_out1(X38, X39, X40, X41, T39), .(T31, .(T32, T33))) -> f4_out1(T39) f597_in([]) -> f597_out1([], []) f597_in(.(T90, T91)) -> U2(f597_in(T91), .(T90, T91)) U2(f597_out1(X130, X129), .(T90, T91)) -> f597_out1(.(T90, X129), X130) f796_in(s(T198), s(T199)) -> U3(f796_in(T198, T199), s(T198), s(T199)) U3(f796_out1, s(T198), s(T199)) -> f796_out1 f796_in(0, s(0)) -> f796_out1 f796_in(0, 0) -> f796_out1 f927_in(s(T298), s(T299)) -> U4(f927_in(T298, T299), s(T298), s(T299)) U4(f927_out1, s(T298), s(T299)) -> f927_out1 f927_in(s(0), 0) -> f927_out1 f228_in(T56, T70, T71) -> U5(f597_in(T71), T56, T70, T71) U5(f597_out1(X99, X98), T56, T70, T71) -> f228_out1(.(T56, X99), .(T70, X98)) f699_in([], T131) -> f699_out1(T131) f699_in(T146, []) -> f699_out1(T146) f699_in(.(T177, T178), .(T179, T180)) -> U6(f754_in(T177, T179, T178, T180), .(T177, T178), .(T179, T180)) U6(f754_out1(T184), .(T177, T178), .(T179, T180)) -> f699_out1(.(T177, T184)) f699_in(.(T395, T396), .(T397, T398)) -> U7(f925_in(T395, T397, T396, T398), .(T395, T396), .(T397, T398)) U7(f925_out1(T402), .(T395, T396), .(T397, T398)) -> f699_out1(.(T397, T402)) f797_in([], T220, T221) -> f797_out1(.(T220, T221)) f797_in(.(T252, T253), T254, T255) -> U8(f754_in(T252, T254, T253, T255), .(T252, T253), T254, T255) U8(f754_out1(T259), .(T252, T253), T254, T255) -> f797_out1(.(T252, T259)) f797_in(.(T277, T278), T279, T280) -> U9(f925_in(T277, T279, T278, T280), .(T277, T278), T279, T280) U9(f925_out1(T284), .(T277, T278), T279, T280) -> f797_out1(.(T279, T284)) f928_in(T314, T315, []) -> f928_out1(.(T314, T315)) f928_in(T345, T346, .(T347, T348)) -> U10(f754_in(T345, T347, T346, T348), T345, T346, .(T347, T348)) U10(f754_out1(T352), T345, T346, .(T347, T348)) -> f928_out1(.(T345, T352)) f928_in(T370, T371, .(T372, T373)) -> U11(f925_in(T370, T372, T371, T373), T370, T371, .(T372, T373)) U11(f925_out1(T377), T370, T371, .(T372, T373)) -> f928_out1(.(T372, T377)) f91_in(T31, T32, T33) -> U12(f228_in(T31, T32, T33), T31, T32, T33) U12(f228_out1(T40, T41), T31, T32, T33) -> U13(f233_in(T40, T41), T31, T32, T33, T40, T41) U13(f233_out1(X40, X41, T43), T31, T32, T33, T40, T41) -> f91_out1(T40, T41, X40, X41, T43) f233_in(T40, T41) -> U14(f4_in(T40), T40, T41) U14(f4_out1(T99), T40, T41) -> U15(f683_in(T41, T99), T40, T41, T99) U15(f683_out1(X41, T101), T40, T41, T99) -> f233_out1(T99, X41, T101) f683_in(T41, T99) -> U16(f4_in(T41), T41, T99) U16(f4_out1(T107), T41, T99) -> U17(f699_in(T99, T107), T41, T99, T107) U17(f699_out1(T108), T41, T99, T107) -> f683_out1(T107, T108) f754_in(T177, T179, T178, T180) -> U18(f796_in(T177, T179), T177, T179, T178, T180) U18(f796_out1, T177, T179, T178, T180) -> U19(f797_in(T178, T179, T180), T177, T179, T178, T180) U19(f797_out1(T184), T177, T179, T178, T180) -> f754_out1(T184) f925_in(T277, T279, T278, T280) -> U20(f927_in(T277, T279), T277, T279, T278, T280) U20(f927_out1, T277, T279, T278, T280) -> U21(f928_in(T277, T278, T280), T277, T279, T278, T280) U21(f928_out1(T284), T277, T279, T278, T280) -> f925_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: F597_IN(.(T90, T91)) -> F597_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: *F597_IN(.(T90, T91)) -> F597_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: F4_IN(.(T31, .(T32, T33))) -> F91_IN(T31, T32, T33) F91_IN(T31, T32, T33) -> U12^1(f228_in(T31, T32, T33), T31, T32, T33) U12^1(f228_out1(T40, T41), T31, T32, T33) -> F233_IN(T40, T41) F233_IN(T40, T41) -> U14^1(f4_in(T40), T40, T41) U14^1(f4_out1(T99), T40, T41) -> F683_IN(T41, T99) F683_IN(T41, T99) -> F4_IN(T41) F233_IN(T40, T41) -> F4_IN(T40) The TRS R consists of the following rules: f4_in([]) -> f4_out1([]) f4_in(.(T17, [])) -> f4_out1(.(T17, [])) f4_in(.(T31, .(T32, T33))) -> U1(f91_in(T31, T32, T33), .(T31, .(T32, T33))) U1(f91_out1(X38, X39, X40, X41, T39), .(T31, .(T32, T33))) -> f4_out1(T39) f597_in([]) -> f597_out1([], []) f597_in(.(T90, T91)) -> U2(f597_in(T91), .(T90, T91)) U2(f597_out1(X130, X129), .(T90, T91)) -> f597_out1(.(T90, X129), X130) f796_in(s(T198), s(T199)) -> U3(f796_in(T198, T199), s(T198), s(T199)) U3(f796_out1, s(T198), s(T199)) -> f796_out1 f796_in(0, s(0)) -> f796_out1 f796_in(0, 0) -> f796_out1 f927_in(s(T298), s(T299)) -> U4(f927_in(T298, T299), s(T298), s(T299)) U4(f927_out1, s(T298), s(T299)) -> f927_out1 f927_in(s(0), 0) -> f927_out1 f228_in(T56, T70, T71) -> U5(f597_in(T71), T56, T70, T71) U5(f597_out1(X99, X98), T56, T70, T71) -> f228_out1(.(T56, X99), .(T70, X98)) f699_in([], T131) -> f699_out1(T131) f699_in(T146, []) -> f699_out1(T146) f699_in(.(T177, T178), .(T179, T180)) -> U6(f754_in(T177, T179, T178, T180), .(T177, T178), .(T179, T180)) U6(f754_out1(T184), .(T177, T178), .(T179, T180)) -> f699_out1(.(T177, T184)) f699_in(.(T395, T396), .(T397, T398)) -> U7(f925_in(T395, T397, T396, T398), .(T395, T396), .(T397, T398)) U7(f925_out1(T402), .(T395, T396), .(T397, T398)) -> f699_out1(.(T397, T402)) f797_in([], T220, T221) -> f797_out1(.(T220, T221)) f797_in(.(T252, T253), T254, T255) -> U8(f754_in(T252, T254, T253, T255), .(T252, T253), T254, T255) U8(f754_out1(T259), .(T252, T253), T254, T255) -> f797_out1(.(T252, T259)) f797_in(.(T277, T278), T279, T280) -> U9(f925_in(T277, T279, T278, T280), .(T277, T278), T279, T280) U9(f925_out1(T284), .(T277, T278), T279, T280) -> f797_out1(.(T279, T284)) f928_in(T314, T315, []) -> f928_out1(.(T314, T315)) f928_in(T345, T346, .(T347, T348)) -> U10(f754_in(T345, T347, T346, T348), T345, T346, .(T347, T348)) U10(f754_out1(T352), T345, T346, .(T347, T348)) -> f928_out1(.(T345, T352)) f928_in(T370, T371, .(T372, T373)) -> U11(f925_in(T370, T372, T371, T373), T370, T371, .(T372, T373)) U11(f925_out1(T377), T370, T371, .(T372, T373)) -> f928_out1(.(T372, T377)) f91_in(T31, T32, T33) -> U12(f228_in(T31, T32, T33), T31, T32, T33) U12(f228_out1(T40, T41), T31, T32, T33) -> U13(f233_in(T40, T41), T31, T32, T33, T40, T41) U13(f233_out1(X40, X41, T43), T31, T32, T33, T40, T41) -> f91_out1(T40, T41, X40, X41, T43) f233_in(T40, T41) -> U14(f4_in(T40), T40, T41) U14(f4_out1(T99), T40, T41) -> U15(f683_in(T41, T99), T40, T41, T99) U15(f683_out1(X41, T101), T40, T41, T99) -> f233_out1(T99, X41, T101) f683_in(T41, T99) -> U16(f4_in(T41), T41, T99) U16(f4_out1(T107), T41, T99) -> U17(f699_in(T99, T107), T41, T99, T107) U17(f699_out1(T108), T41, T99, T107) -> f683_out1(T107, T108) f754_in(T177, T179, T178, T180) -> U18(f796_in(T177, T179), T177, T179, T178, T180) U18(f796_out1, T177, T179, T178, T180) -> U19(f797_in(T178, T179, T180), T177, T179, T178, T180) U19(f797_out1(T184), T177, T179, T178, T180) -> f754_out1(T184) f925_in(T277, T279, T278, T280) -> U20(f927_in(T277, T279), T277, T279, T278, T280) U20(f927_out1, T277, T279, T278, T280) -> U21(f928_in(T277, T278, T280), T277, T279, T278, T280) U21(f928_out1(T284), T277, T279, T278, T280) -> f925_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. F4_IN(.(T31, .(T32, T33))) -> F91_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( f228_in_3(x_1, ..., x_3) ) = 2x_3 POL( U5_4(x_1, ..., x_4) ) = 2x_1 POL( f597_in_1(x_1) ) = x_1 POL( f4_in_1(x_1) ) = 0 POL( [] ) = 0 POL( f4_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( f91_in_3(x_1, ..., x_3) ) = 0 POL( f91_out1_5(x_1, ..., x_5) ) = x_1 + x_2 + 2x_3 + 2x_5 POL( f228_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( f233_in_2(x_1, x_2) ) = 0 POL( f233_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( f683_in_2(x_1, x_2) ) = 0 POL( f683_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( f699_in_2(x_1, x_2) ) = 0 POL( f597_out1_2(x_1, x_2) ) = x_1 + x_2 POL( U2_2(x_1, x_2) ) = 2x_1 + 1 POL( f699_out1_1(x_1) ) = max{0, -2} POL( U6_3(x_1, ..., x_3) ) = max{0, 2x_1 - 2} POL( f754_in_4(x_1, ..., x_4) ) = 2x_2 + 2x_4 + 2 POL( U7_3(x_1, ..., x_3) ) = max{0, -2} POL( f925_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( f796_in_2(x_1, x_2) ) = 2x_1 + 2 POL( f754_out1_1(x_1) ) = 2 POL( U20_5(x_1, ..., x_5) ) = max{0, 2x_1 + 2x_4 + 2x_5 - 2} POL( f927_in_2(x_1, x_2) ) = 2x_1 POL( f925_out1_1(x_1) ) = 2 POL( f796_out1 ) = 0 POL( U19_5(x_1, ..., x_5) ) = max{0, x_1 + 2x_4 + 2x_5 - 2} POL( f797_in_3(x_1, ..., x_3) ) = 0 POL( f797_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( f927_out1 ) = 0 POL( U21_5(x_1, ..., x_5) ) = max{0, x_3 - 2} POL( f928_in_3(x_1, ..., x_3) ) = x_1 + 2x_2 + 2 POL( f928_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( F4_IN_1(x_1) ) = x_1 POL( F91_IN_3(x_1, ..., x_3) ) = 2x_3 + 2 POL( F233_IN_2(x_1, x_2) ) = x_1 + x_2 POL( F683_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: f228_in(T56, T70, T71) -> U5(f597_in(T71), T56, T70, T71) f597_in([]) -> f597_out1([], []) f597_in(.(T90, T91)) -> U2(f597_in(T91), .(T90, T91)) U5(f597_out1(X99, X98), T56, T70, T71) -> f228_out1(.(T56, X99), .(T70, X98)) U2(f597_out1(X130, X129), .(T90, T91)) -> f597_out1(.(T90, X129), X130) ---------------------------------------- (27) Obligation: Q DP problem: The TRS P consists of the following rules: F91_IN(T31, T32, T33) -> U12^1(f228_in(T31, T32, T33), T31, T32, T33) U12^1(f228_out1(T40, T41), T31, T32, T33) -> F233_IN(T40, T41) F233_IN(T40, T41) -> U14^1(f4_in(T40), T40, T41) U14^1(f4_out1(T99), T40, T41) -> F683_IN(T41, T99) F683_IN(T41, T99) -> F4_IN(T41) F233_IN(T40, T41) -> F4_IN(T40) The TRS R consists of the following rules: f4_in([]) -> f4_out1([]) f4_in(.(T17, [])) -> f4_out1(.(T17, [])) f4_in(.(T31, .(T32, T33))) -> U1(f91_in(T31, T32, T33), .(T31, .(T32, T33))) U1(f91_out1(X38, X39, X40, X41, T39), .(T31, .(T32, T33))) -> f4_out1(T39) f597_in([]) -> f597_out1([], []) f597_in(.(T90, T91)) -> U2(f597_in(T91), .(T90, T91)) U2(f597_out1(X130, X129), .(T90, T91)) -> f597_out1(.(T90, X129), X130) f796_in(s(T198), s(T199)) -> U3(f796_in(T198, T199), s(T198), s(T199)) U3(f796_out1, s(T198), s(T199)) -> f796_out1 f796_in(0, s(0)) -> f796_out1 f796_in(0, 0) -> f796_out1 f927_in(s(T298), s(T299)) -> U4(f927_in(T298, T299), s(T298), s(T299)) U4(f927_out1, s(T298), s(T299)) -> f927_out1 f927_in(s(0), 0) -> f927_out1 f228_in(T56, T70, T71) -> U5(f597_in(T71), T56, T70, T71) U5(f597_out1(X99, X98), T56, T70, T71) -> f228_out1(.(T56, X99), .(T70, X98)) f699_in([], T131) -> f699_out1(T131) f699_in(T146, []) -> f699_out1(T146) f699_in(.(T177, T178), .(T179, T180)) -> U6(f754_in(T177, T179, T178, T180), .(T177, T178), .(T179, T180)) U6(f754_out1(T184), .(T177, T178), .(T179, T180)) -> f699_out1(.(T177, T184)) f699_in(.(T395, T396), .(T397, T398)) -> U7(f925_in(T395, T397, T396, T398), .(T395, T396), .(T397, T398)) U7(f925_out1(T402), .(T395, T396), .(T397, T398)) -> f699_out1(.(T397, T402)) f797_in([], T220, T221) -> f797_out1(.(T220, T221)) f797_in(.(T252, T253), T254, T255) -> U8(f754_in(T252, T254, T253, T255), .(T252, T253), T254, T255) U8(f754_out1(T259), .(T252, T253), T254, T255) -> f797_out1(.(T252, T259)) f797_in(.(T277, T278), T279, T280) -> U9(f925_in(T277, T279, T278, T280), .(T277, T278), T279, T280) U9(f925_out1(T284), .(T277, T278), T279, T280) -> f797_out1(.(T279, T284)) f928_in(T314, T315, []) -> f928_out1(.(T314, T315)) f928_in(T345, T346, .(T347, T348)) -> U10(f754_in(T345, T347, T346, T348), T345, T346, .(T347, T348)) U10(f754_out1(T352), T345, T346, .(T347, T348)) -> f928_out1(.(T345, T352)) f928_in(T370, T371, .(T372, T373)) -> U11(f925_in(T370, T372, T371, T373), T370, T371, .(T372, T373)) U11(f925_out1(T377), T370, T371, .(T372, T373)) -> f928_out1(.(T372, T377)) f91_in(T31, T32, T33) -> U12(f228_in(T31, T32, T33), T31, T32, T33) U12(f228_out1(T40, T41), T31, T32, T33) -> U13(f233_in(T40, T41), T31, T32, T33, T40, T41) U13(f233_out1(X40, X41, T43), T31, T32, T33, T40, T41) -> f91_out1(T40, T41, X40, X41, T43) f233_in(T40, T41) -> U14(f4_in(T40), T40, T41) U14(f4_out1(T99), T40, T41) -> U15(f683_in(T41, T99), T40, T41, T99) U15(f683_out1(X41, T101), T40, T41, T99) -> f233_out1(T99, X41, T101) f683_in(T41, T99) -> U16(f4_in(T41), T41, T99) U16(f4_out1(T107), T41, T99) -> U17(f699_in(T99, T107), T41, T99, T107) U17(f699_out1(T108), T41, T99, T107) -> f683_out1(T107, T108) f754_in(T177, T179, T178, T180) -> U18(f796_in(T177, T179), T177, T179, T178, T180) U18(f796_out1, T177, T179, T178, T180) -> U19(f797_in(T178, T179, T180), T177, T179, T178, T180) U19(f797_out1(T184), T177, T179, T178, T180) -> f754_out1(T184) f925_in(T277, T279, T278, T280) -> U20(f927_in(T277, T279), T277, T279, T278, T280) U20(f927_out1, T277, T279, T278, T280) -> U21(f928_in(T277, T278, T280), T277, T279, T278, T280) U21(f928_out1(T284), T277, T279, T278, T280) -> f925_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