YES proof of /export/starexec/sandbox/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, 79 ms] (2) QTRS (3) DependencyPairsProof [EQUIVALENT, 8 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, 305 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": { "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", "873": { "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": [] } }, "875": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "90": { "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": [] } }, "91": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "93": { "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": [] } }, "912": { "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": [] } }, "913": { "goal": [{ "clause": 9, "scope": 8, "term": "(gt T277 T279)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T277", "T279" ], "free": [], "exprvars": [] } }, "95": { "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": [] } }, "639": { "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": [] } }, "914": { "goal": [{ "clause": 10, "scope": 8, "term": "(gt T277 T279)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T277", "T279" ], "free": [], "exprvars": [] } }, "915": { "goal": [{ "clause": -1, "scope": -1, "term": "(gt T298 T299)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T298", "T299" ], "free": [], "exprvars": [] } }, "916": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "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": 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": [] } }, "641": { "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": [] } }, "644": { "goal": [{ "clause": -1, "scope": -1, "term": "(split T71 X99 X98 T74)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T71"], "free": [ "X98", "X99" ], "exprvars": [] } }, "645": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "920": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "800": { "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": [] } }, "921": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "801": { "goal": [{ "clause": 11, "scope": 6, "term": "(le T177 T179)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T177", "T179" ], "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": [] } }, "769": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "802": { "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": [] } }, "923": { "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": [] } }, "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": "(le T198 T199)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T198", "T199" ], "free": [], "exprvars": [] } }, "924": { "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": [] } }, "804": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "805": { "goal": [{ "clause": 12, "scope": 6, "term": "(le T177 T179)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T177", "T179" ], "free": [], "exprvars": [] } }, "806": { "goal": [{ "clause": 13, "scope": 6, "term": "(le T177 T179)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T177", "T179" ], "free": [], "exprvars": [] } }, "927": { "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": [] } }, "807": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "928": { "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": [] } }, "808": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "929": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "809": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "770": { "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": [] } }, "771": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "892": { "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": [] } }, "651": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "772": { "goal": [{ "clause": 6, "scope": 5, "term": "(merge T99 T107 T108 (. T109 T110))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T99", "T107" ], "free": [], "exprvars": [] } }, "893": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "652": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "773": { "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": [] } }, "894": { "goal": [{ "clause": -1, "scope": -1, "term": "(gt T277 T279)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T277", "T279" ], "free": [], "exprvars": [] } }, "653": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "774": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "895": { "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": [] } }, "775": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "776": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "656": { "goal": [{ "clause": -1, "scope": -1, "term": "(split T91 X130 X129 T94)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T91"], "free": [ "X129", "X130" ], "exprvars": [] } }, "810": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "657": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "811": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "779": { "goal": [{ "clause": 7, "scope": 5, "term": "(merge T99 T107 T108 (. T109 T110))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T99", "T107" ], "free": [], "exprvars": [] } }, "812": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "934": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "935": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "936": { "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": [] } }, "937": { "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": [] } }, "780": { "goal": [{ "clause": 8, "scope": 5, "term": "(merge T99 T107 T108 (. T109 T110))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T99", "T107" ], "free": [], "exprvars": [] } }, "661": { "goal": [{ "clause": -1, "scope": -1, "term": "(mergesort T40 X40 T42)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T40"], "free": ["X40"], "exprvars": [] } }, "662": { "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": [] } }, "942": { "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": [] } }, "943": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "946": { "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": [] } }, "947": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "948": { "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": [] } }, "949": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "790": { "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": [] } }, "793": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "798": { "goal": [{ "clause": -1, "scope": -1, "term": "(le T177 T179)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T177", "T179" ], "free": [], "exprvars": [] } }, "799": { "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": [] } }, "835": { "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": [] } }, "836": { "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": [] } }, "837": { "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": [] } }, "838": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "839": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "840": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "841": { "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": [] } }, "842": { "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": [] } }, "843": { "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": [] } }, "60": { "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": [] } }, "61": { "goal": [{ "clause": 0, "scope": 1, "term": "(mergesort T1 T2 T3)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T1"], "free": [], "exprvars": [] } }, "62": { "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": [] } }, "69": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "70": { "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": [] } }, "736": { "goal": [{ "clause": -1, "scope": -1, "term": "(merge T99 T107 T108 (. T109 T110))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T99", "T107" ], "free": [], "exprvars": [] } }, "72": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "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": [] } }, "628": { "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": [] } }, "85": { "goal": [{ "clause": 1, "scope": 1, "term": "(mergesort T1 T2 T3)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T1"], "free": [], "exprvars": [] } }, "629": { "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": [] } }, "86": { "goal": [{ "clause": 2, "scope": 1, "term": "(mergesort T1 T2 T3)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T1"], "free": [], "exprvars": [] } }, "87": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } } }, "edges": [ { "from": 1, "to": 60, "label": "CASE" }, { "from": 60, "to": 61, "label": "PARALLEL" }, { "from": 60, "to": 62, "label": "PARALLEL" }, { "from": 61, "to": 69, "label": "EVAL with clause\nmergesort([], [], X5).\nand substitutionT1 -> [],\nT2 -> [],\nT3 -> T8,\nX5 -> T8" }, { "from": 61, "to": 70, "label": "EVAL-BACKTRACK" }, { "from": 62, "to": 85, "label": "PARALLEL" }, { "from": 62, "to": 86, "label": "PARALLEL" }, { "from": 69, "to": 72, "label": "SUCCESS" }, { "from": 85, "to": 87, "label": "EVAL with clause\nmergesort(.(X14, []), .(X14, []), X15).\nand substitutionX14 -> T17,\nT1 -> .(T17, []),\nT2 -> .(T17, []),\nT3 -> T18,\nX15 -> T18" }, { "from": 85, "to": 88, "label": "EVAL-BACKTRACK" }, { "from": 86, "to": 90, "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": 86, "to": 91, "label": "EVAL-BACKTRACK" }, { "from": 87, "to": 89, "label": "SUCCESS" }, { "from": 90, "to": 93, "label": "SPLIT 1" }, { "from": 90, "to": 95, "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": 93, "to": 628, "label": "CASE" }, { "from": 95, "to": 661, "label": "SPLIT 1" }, { "from": 95, "to": 662, "label": "SPLIT 2\nnew knowledge:\nT40 is ground\nT99 is ground\nreplacements:X40 -> T99,\nT42 -> T100,\nT43 -> T101,\nT44 -> T102" }, { "from": 628, "to": 629, "label": "BACKTRACK\nfor clause: split([], [], [], Ls)because of non-unification" }, { "from": 629, "to": 639, "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": 639, "to": 640, "label": "CASE" }, { "from": 640, "to": 641, "label": "BACKTRACK\nfor clause: split([], [], [], Ls)because of non-unification" }, { "from": 641, "to": 644, "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": 641, "to": 645, "label": "EVAL-BACKTRACK" }, { "from": 644, "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": 656, "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": 657, "label": "EVAL-BACKTRACK" }, { "from": 651, "to": 653, "label": "SUCCESS" }, { "from": 656, "to": 644, "label": "INSTANCE with matching:\nT71 -> T91\nX99 -> X130\nX98 -> X129\nT74 -> T94" }, { "from": 661, "to": 1, "label": "INSTANCE with matching:\nT1 -> T40\nT2 -> X40\nT3 -> T42" }, { "from": 662, "to": 735, "label": "SPLIT 1" }, { "from": 662, "to": 736, "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": 736, "to": 742, "label": "CASE" }, { "from": 742, "to": 743, "label": "PARALLEL" }, { "from": 742, "to": 744, "label": "PARALLEL" }, { "from": 743, "to": 769, "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": 770, "label": "EVAL-BACKTRACK" }, { "from": 744, "to": 772, "label": "PARALLEL" }, { "from": 744, "to": 773, "label": "PARALLEL" }, { "from": 769, "to": 771, "label": "SUCCESS" }, { "from": 772, "to": 774, "label": "EVAL with clause\nmerge(X163, [], X163, X164).\nand substitutionT99 -> T146,\nX163 -> T146,\nT107 -> [],\nT108 -> T146,\nT109 -> T147,\nT110 -> T148,\nX164 -> .(T147, T148)" }, { "from": 772, "to": 775, "label": "EVAL-BACKTRACK" }, { "from": 773, "to": 779, "label": "PARALLEL" }, { "from": 773, "to": 780, "label": "PARALLEL" }, { "from": 774, "to": 776, "label": "SUCCESS" }, { "from": 779, "to": 790, "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": 779, "to": 793, "label": "EVAL-BACKTRACK" }, { "from": 780, "to": 948, "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": 780, "to": 949, "label": "EVAL-BACKTRACK" }, { "from": 790, "to": 798, "label": "SPLIT 1" }, { "from": 790, "to": 799, "label": "SPLIT 2\nnew knowledge:\nT177 is ground\nT179 is ground" }, { "from": 798, "to": 800, "label": "CASE" }, { "from": 799, "to": 835, "label": "CASE" }, { "from": 800, "to": 801, "label": "PARALLEL" }, { "from": 800, "to": 802, "label": "PARALLEL" }, { "from": 801, "to": 803, "label": "EVAL with clause\nle(s(X212), s(X213)) :- le(X212, X213).\nand substitutionX212 -> T198,\nT177 -> s(T198),\nX213 -> T199,\nT179 -> s(T199)" }, { "from": 801, "to": 804, "label": "EVAL-BACKTRACK" }, { "from": 802, "to": 805, "label": "PARALLEL" }, { "from": 802, "to": 806, "label": "PARALLEL" }, { "from": 803, "to": 798, "label": "INSTANCE with matching:\nT177 -> T198\nT179 -> T199" }, { "from": 805, "to": 807, "label": "EVAL with clause\nle(0, s(0)).\nand substitutionT177 -> 0,\nT179 -> s(0)" }, { "from": 805, "to": 808, "label": "EVAL-BACKTRACK" }, { "from": 806, "to": 810, "label": "EVAL with clause\nle(0, 0).\nand substitutionT177 -> 0,\nT179 -> 0" }, { "from": 806, "to": 811, "label": "EVAL-BACKTRACK" }, { "from": 807, "to": 809, "label": "SUCCESS" }, { "from": 810, "to": 812, "label": "SUCCESS" }, { "from": 835, "to": 836, "label": "PARALLEL" }, { "from": 835, "to": 837, "label": "PARALLEL" }, { "from": 836, "to": 838, "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": 836, "to": 839, "label": "EVAL-BACKTRACK" }, { "from": 837, "to": 841, "label": "BACKTRACK\nfor clause: merge(Xs, [], Xs, Ls)because of non-unification" }, { "from": 838, "to": 840, "label": "SUCCESS" }, { "from": 841, "to": 842, "label": "PARALLEL" }, { "from": 841, "to": 843, "label": "PARALLEL" }, { "from": 842, "to": 873, "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": 842, "to": 875, "label": "EVAL-BACKTRACK" }, { "from": 843, "to": 892, "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": 843, "to": 893, "label": "EVAL-BACKTRACK" }, { "from": 873, "to": 790, "label": "INSTANCE with matching:\nT177 -> T252\nT179 -> T254\nT178 -> T253\nT180 -> T255\nT184 -> T259\nT185 -> T260" }, { "from": 892, "to": 894, "label": "SPLIT 1" }, { "from": 892, "to": 895, "label": "SPLIT 2\nnew knowledge:\nT277 is ground\nT279 is ground" }, { "from": 894, "to": 912, "label": "CASE" }, { "from": 895, "to": 923, "label": "CASE" }, { "from": 912, "to": 913, "label": "PARALLEL" }, { "from": 912, "to": 914, "label": "PARALLEL" }, { "from": 913, "to": 915, "label": "EVAL with clause\ngt(s(X302), s(X303)) :- gt(X302, X303).\nand substitutionX302 -> T298,\nT277 -> s(T298),\nX303 -> T299,\nT279 -> s(T299)" }, { "from": 913, "to": 916, "label": "EVAL-BACKTRACK" }, { "from": 914, "to": 920, "label": "EVAL with clause\ngt(s(0), 0).\nand substitutionT277 -> s(0),\nT279 -> 0" }, { "from": 914, "to": 921, "label": "EVAL-BACKTRACK" }, { "from": 915, "to": 894, "label": "INSTANCE with matching:\nT277 -> T298\nT279 -> T299" }, { "from": 920, "to": 922, "label": "SUCCESS" }, { "from": 923, "to": 924, "label": "BACKTRACK\nfor clause: merge([], Xs, Xs, Ls)because of non-unification" }, { "from": 924, "to": 927, "label": "PARALLEL" }, { "from": 924, "to": 928, "label": "PARALLEL" }, { "from": 927, "to": 929, "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": 927, "to": 934, "label": "EVAL-BACKTRACK" }, { "from": 928, "to": 936, "label": "PARALLEL" }, { "from": 928, "to": 937, "label": "PARALLEL" }, { "from": 929, "to": 935, "label": "SUCCESS" }, { "from": 936, "to": 942, "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": 936, "to": 943, "label": "EVAL-BACKTRACK" }, { "from": 937, "to": 946, "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": 937, "to": 947, "label": "EVAL-BACKTRACK" }, { "from": 942, "to": 790, "label": "INSTANCE with matching:\nT177 -> T345\nT179 -> T347\nT178 -> T346\nT180 -> T348\nT184 -> T352\nT185 -> T353" }, { "from": 946, "to": 892, "label": "INSTANCE with matching:\nT277 -> T370\nT279 -> T372\nT278 -> T371\nT280 -> T373\nT284 -> T377\nT285 -> T378" }, { "from": 948, "to": 892, "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(f90_in(T31, T32, T33), .(T31, .(T32, T33))) U1(f90_out1(X38, X39, X40, X41, T39), .(T31, .(T32, T33))) -> f1_out1(T39) f644_in([]) -> f644_out1([], []) f644_in(.(T90, T91)) -> U2(f644_in(T91), .(T90, T91)) U2(f644_out1(X130, X129), .(T90, T91)) -> f644_out1(.(T90, X129), X130) f798_in(s(T198), s(T199)) -> U3(f798_in(T198, T199), s(T198), s(T199)) U3(f798_out1, s(T198), s(T199)) -> f798_out1 f798_in(0, s(0)) -> f798_out1 f798_in(0, 0) -> f798_out1 f894_in(s(T298), s(T299)) -> U4(f894_in(T298, T299), s(T298), s(T299)) U4(f894_out1, s(T298), s(T299)) -> f894_out1 f894_in(s(0), 0) -> f894_out1 f93_in(T56, T70, T71) -> U5(f644_in(T71), T56, T70, T71) U5(f644_out1(X99, X98), T56, T70, T71) -> f93_out1(.(T56, X99), .(T70, X98)) f736_in([], T131) -> f736_out1(T131) f736_in(T146, []) -> f736_out1(T146) f736_in(.(T177, T178), .(T179, T180)) -> U6(f790_in(T177, T179, T178, T180), .(T177, T178), .(T179, T180)) U6(f790_out1(T184), .(T177, T178), .(T179, T180)) -> f736_out1(.(T177, T184)) f736_in(.(T395, T396), .(T397, T398)) -> U7(f892_in(T395, T397, T396, T398), .(T395, T396), .(T397, T398)) U7(f892_out1(T402), .(T395, T396), .(T397, T398)) -> f736_out1(.(T397, T402)) f799_in([], T220, T221) -> f799_out1(.(T220, T221)) f799_in(.(T252, T253), T254, T255) -> U8(f790_in(T252, T254, T253, T255), .(T252, T253), T254, T255) U8(f790_out1(T259), .(T252, T253), T254, T255) -> f799_out1(.(T252, T259)) f799_in(.(T277, T278), T279, T280) -> U9(f892_in(T277, T279, T278, T280), .(T277, T278), T279, T280) U9(f892_out1(T284), .(T277, T278), T279, T280) -> f799_out1(.(T279, T284)) f895_in(T314, T315, []) -> f895_out1(.(T314, T315)) f895_in(T345, T346, .(T347, T348)) -> U10(f790_in(T345, T347, T346, T348), T345, T346, .(T347, T348)) U10(f790_out1(T352), T345, T346, .(T347, T348)) -> f895_out1(.(T345, T352)) f895_in(T370, T371, .(T372, T373)) -> U11(f892_in(T370, T372, T371, T373), T370, T371, .(T372, T373)) U11(f892_out1(T377), T370, T371, .(T372, T373)) -> f895_out1(.(T372, T377)) f90_in(T31, T32, T33) -> U12(f93_in(T31, T32, T33), T31, T32, T33) U12(f93_out1(T40, T41), T31, T32, T33) -> U13(f95_in(T40, T41), T31, T32, T33, T40, T41) U13(f95_out1(X40, X41, T43), T31, T32, T33, T40, T41) -> f90_out1(T40, T41, X40, X41, T43) f95_in(T40, T41) -> U14(f1_in(T40), T40, T41) U14(f1_out1(T99), T40, T41) -> U15(f662_in(T41, T99), T40, T41, T99) U15(f662_out1(X41, T101), T40, T41, T99) -> f95_out1(T99, X41, T101) f662_in(T41, T99) -> U16(f1_in(T41), T41, T99) U16(f1_out1(T107), T41, T99) -> U17(f736_in(T99, T107), T41, T99, T107) U17(f736_out1(T108), T41, T99, T107) -> f662_out1(T107, T108) f790_in(T177, T179, T178, T180) -> U18(f798_in(T177, T179), T177, T179, T178, T180) U18(f798_out1, T177, T179, T178, T180) -> U19(f799_in(T178, T179, T180), T177, T179, T178, T180) U19(f799_out1(T184), T177, T179, T178, T180) -> f790_out1(T184) f892_in(T277, T279, T278, T280) -> U20(f894_in(T277, T279), T277, T279, T278, T280) U20(f894_out1, T277, T279, T278, T280) -> U21(f895_in(T277, T278, T280), T277, T279, T278, T280) U21(f895_out1(T284), T277, T279, T278, T280) -> f892_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(f90_in(T31, T32, T33), .(T31, .(T32, T33))) F1_IN(.(T31, .(T32, T33))) -> F90_IN(T31, T32, T33) F644_IN(.(T90, T91)) -> U2^1(f644_in(T91), .(T90, T91)) F644_IN(.(T90, T91)) -> F644_IN(T91) F798_IN(s(T198), s(T199)) -> U3^1(f798_in(T198, T199), s(T198), s(T199)) F798_IN(s(T198), s(T199)) -> F798_IN(T198, T199) F894_IN(s(T298), s(T299)) -> U4^1(f894_in(T298, T299), s(T298), s(T299)) F894_IN(s(T298), s(T299)) -> F894_IN(T298, T299) F93_IN(T56, T70, T71) -> U5^1(f644_in(T71), T56, T70, T71) F93_IN(T56, T70, T71) -> F644_IN(T71) F736_IN(.(T177, T178), .(T179, T180)) -> U6^1(f790_in(T177, T179, T178, T180), .(T177, T178), .(T179, T180)) F736_IN(.(T177, T178), .(T179, T180)) -> F790_IN(T177, T179, T178, T180) F736_IN(.(T395, T396), .(T397, T398)) -> U7^1(f892_in(T395, T397, T396, T398), .(T395, T396), .(T397, T398)) F736_IN(.(T395, T396), .(T397, T398)) -> F892_IN(T395, T397, T396, T398) F799_IN(.(T252, T253), T254, T255) -> U8^1(f790_in(T252, T254, T253, T255), .(T252, T253), T254, T255) F799_IN(.(T252, T253), T254, T255) -> F790_IN(T252, T254, T253, T255) F799_IN(.(T277, T278), T279, T280) -> U9^1(f892_in(T277, T279, T278, T280), .(T277, T278), T279, T280) F799_IN(.(T277, T278), T279, T280) -> F892_IN(T277, T279, T278, T280) F895_IN(T345, T346, .(T347, T348)) -> U10^1(f790_in(T345, T347, T346, T348), T345, T346, .(T347, T348)) F895_IN(T345, T346, .(T347, T348)) -> F790_IN(T345, T347, T346, T348) F895_IN(T370, T371, .(T372, T373)) -> U11^1(f892_in(T370, T372, T371, T373), T370, T371, .(T372, T373)) F895_IN(T370, T371, .(T372, T373)) -> F892_IN(T370, T372, T371, T373) F90_IN(T31, T32, T33) -> U12^1(f93_in(T31, T32, T33), T31, T32, T33) F90_IN(T31, T32, T33) -> F93_IN(T31, T32, T33) U12^1(f93_out1(T40, T41), T31, T32, T33) -> U13^1(f95_in(T40, T41), T31, T32, T33, T40, T41) U12^1(f93_out1(T40, T41), T31, T32, T33) -> F95_IN(T40, T41) F95_IN(T40, T41) -> U14^1(f1_in(T40), T40, T41) F95_IN(T40, T41) -> F1_IN(T40) U14^1(f1_out1(T99), T40, T41) -> U15^1(f662_in(T41, T99), T40, T41, T99) U14^1(f1_out1(T99), T40, T41) -> F662_IN(T41, T99) F662_IN(T41, T99) -> U16^1(f1_in(T41), T41, T99) F662_IN(T41, T99) -> F1_IN(T41) U16^1(f1_out1(T107), T41, T99) -> U17^1(f736_in(T99, T107), T41, T99, T107) U16^1(f1_out1(T107), T41, T99) -> F736_IN(T99, T107) F790_IN(T177, T179, T178, T180) -> U18^1(f798_in(T177, T179), T177, T179, T178, T180) F790_IN(T177, T179, T178, T180) -> F798_IN(T177, T179) U18^1(f798_out1, T177, T179, T178, T180) -> U19^1(f799_in(T178, T179, T180), T177, T179, T178, T180) U18^1(f798_out1, T177, T179, T178, T180) -> F799_IN(T178, T179, T180) F892_IN(T277, T279, T278, T280) -> U20^1(f894_in(T277, T279), T277, T279, T278, T280) F892_IN(T277, T279, T278, T280) -> F894_IN(T277, T279) U20^1(f894_out1, T277, T279, T278, T280) -> U21^1(f895_in(T277, T278, T280), T277, T279, T278, T280) U20^1(f894_out1, T277, T279, T278, T280) -> F895_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(f90_in(T31, T32, T33), .(T31, .(T32, T33))) U1(f90_out1(X38, X39, X40, X41, T39), .(T31, .(T32, T33))) -> f1_out1(T39) f644_in([]) -> f644_out1([], []) f644_in(.(T90, T91)) -> U2(f644_in(T91), .(T90, T91)) U2(f644_out1(X130, X129), .(T90, T91)) -> f644_out1(.(T90, X129), X130) f798_in(s(T198), s(T199)) -> U3(f798_in(T198, T199), s(T198), s(T199)) U3(f798_out1, s(T198), s(T199)) -> f798_out1 f798_in(0, s(0)) -> f798_out1 f798_in(0, 0) -> f798_out1 f894_in(s(T298), s(T299)) -> U4(f894_in(T298, T299), s(T298), s(T299)) U4(f894_out1, s(T298), s(T299)) -> f894_out1 f894_in(s(0), 0) -> f894_out1 f93_in(T56, T70, T71) -> U5(f644_in(T71), T56, T70, T71) U5(f644_out1(X99, X98), T56, T70, T71) -> f93_out1(.(T56, X99), .(T70, X98)) f736_in([], T131) -> f736_out1(T131) f736_in(T146, []) -> f736_out1(T146) f736_in(.(T177, T178), .(T179, T180)) -> U6(f790_in(T177, T179, T178, T180), .(T177, T178), .(T179, T180)) U6(f790_out1(T184), .(T177, T178), .(T179, T180)) -> f736_out1(.(T177, T184)) f736_in(.(T395, T396), .(T397, T398)) -> U7(f892_in(T395, T397, T396, T398), .(T395, T396), .(T397, T398)) U7(f892_out1(T402), .(T395, T396), .(T397, T398)) -> f736_out1(.(T397, T402)) f799_in([], T220, T221) -> f799_out1(.(T220, T221)) f799_in(.(T252, T253), T254, T255) -> U8(f790_in(T252, T254, T253, T255), .(T252, T253), T254, T255) U8(f790_out1(T259), .(T252, T253), T254, T255) -> f799_out1(.(T252, T259)) f799_in(.(T277, T278), T279, T280) -> U9(f892_in(T277, T279, T278, T280), .(T277, T278), T279, T280) U9(f892_out1(T284), .(T277, T278), T279, T280) -> f799_out1(.(T279, T284)) f895_in(T314, T315, []) -> f895_out1(.(T314, T315)) f895_in(T345, T346, .(T347, T348)) -> U10(f790_in(T345, T347, T346, T348), T345, T346, .(T347, T348)) U10(f790_out1(T352), T345, T346, .(T347, T348)) -> f895_out1(.(T345, T352)) f895_in(T370, T371, .(T372, T373)) -> U11(f892_in(T370, T372, T371, T373), T370, T371, .(T372, T373)) U11(f892_out1(T377), T370, T371, .(T372, T373)) -> f895_out1(.(T372, T377)) f90_in(T31, T32, T33) -> U12(f93_in(T31, T32, T33), T31, T32, T33) U12(f93_out1(T40, T41), T31, T32, T33) -> U13(f95_in(T40, T41), T31, T32, T33, T40, T41) U13(f95_out1(X40, X41, T43), T31, T32, T33, T40, T41) -> f90_out1(T40, T41, X40, X41, T43) f95_in(T40, T41) -> U14(f1_in(T40), T40, T41) U14(f1_out1(T99), T40, T41) -> U15(f662_in(T41, T99), T40, T41, T99) U15(f662_out1(X41, T101), T40, T41, T99) -> f95_out1(T99, X41, T101) f662_in(T41, T99) -> U16(f1_in(T41), T41, T99) U16(f1_out1(T107), T41, T99) -> U17(f736_in(T99, T107), T41, T99, T107) U17(f736_out1(T108), T41, T99, T107) -> f662_out1(T107, T108) f790_in(T177, T179, T178, T180) -> U18(f798_in(T177, T179), T177, T179, T178, T180) U18(f798_out1, T177, T179, T178, T180) -> U19(f799_in(T178, T179, T180), T177, T179, T178, T180) U19(f799_out1(T184), T177, T179, T178, T180) -> f790_out1(T184) f892_in(T277, T279, T278, T280) -> U20(f894_in(T277, T279), T277, T279, T278, T280) U20(f894_out1, T277, T279, T278, T280) -> U21(f895_in(T277, T278, T280), T277, T279, T278, T280) U21(f895_out1(T284), T277, T279, T278, T280) -> f892_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: F894_IN(s(T298), s(T299)) -> F894_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(f90_in(T31, T32, T33), .(T31, .(T32, T33))) U1(f90_out1(X38, X39, X40, X41, T39), .(T31, .(T32, T33))) -> f1_out1(T39) f644_in([]) -> f644_out1([], []) f644_in(.(T90, T91)) -> U2(f644_in(T91), .(T90, T91)) U2(f644_out1(X130, X129), .(T90, T91)) -> f644_out1(.(T90, X129), X130) f798_in(s(T198), s(T199)) -> U3(f798_in(T198, T199), s(T198), s(T199)) U3(f798_out1, s(T198), s(T199)) -> f798_out1 f798_in(0, s(0)) -> f798_out1 f798_in(0, 0) -> f798_out1 f894_in(s(T298), s(T299)) -> U4(f894_in(T298, T299), s(T298), s(T299)) U4(f894_out1, s(T298), s(T299)) -> f894_out1 f894_in(s(0), 0) -> f894_out1 f93_in(T56, T70, T71) -> U5(f644_in(T71), T56, T70, T71) U5(f644_out1(X99, X98), T56, T70, T71) -> f93_out1(.(T56, X99), .(T70, X98)) f736_in([], T131) -> f736_out1(T131) f736_in(T146, []) -> f736_out1(T146) f736_in(.(T177, T178), .(T179, T180)) -> U6(f790_in(T177, T179, T178, T180), .(T177, T178), .(T179, T180)) U6(f790_out1(T184), .(T177, T178), .(T179, T180)) -> f736_out1(.(T177, T184)) f736_in(.(T395, T396), .(T397, T398)) -> U7(f892_in(T395, T397, T396, T398), .(T395, T396), .(T397, T398)) U7(f892_out1(T402), .(T395, T396), .(T397, T398)) -> f736_out1(.(T397, T402)) f799_in([], T220, T221) -> f799_out1(.(T220, T221)) f799_in(.(T252, T253), T254, T255) -> U8(f790_in(T252, T254, T253, T255), .(T252, T253), T254, T255) U8(f790_out1(T259), .(T252, T253), T254, T255) -> f799_out1(.(T252, T259)) f799_in(.(T277, T278), T279, T280) -> U9(f892_in(T277, T279, T278, T280), .(T277, T278), T279, T280) U9(f892_out1(T284), .(T277, T278), T279, T280) -> f799_out1(.(T279, T284)) f895_in(T314, T315, []) -> f895_out1(.(T314, T315)) f895_in(T345, T346, .(T347, T348)) -> U10(f790_in(T345, T347, T346, T348), T345, T346, .(T347, T348)) U10(f790_out1(T352), T345, T346, .(T347, T348)) -> f895_out1(.(T345, T352)) f895_in(T370, T371, .(T372, T373)) -> U11(f892_in(T370, T372, T371, T373), T370, T371, .(T372, T373)) U11(f892_out1(T377), T370, T371, .(T372, T373)) -> f895_out1(.(T372, T377)) f90_in(T31, T32, T33) -> U12(f93_in(T31, T32, T33), T31, T32, T33) U12(f93_out1(T40, T41), T31, T32, T33) -> U13(f95_in(T40, T41), T31, T32, T33, T40, T41) U13(f95_out1(X40, X41, T43), T31, T32, T33, T40, T41) -> f90_out1(T40, T41, X40, X41, T43) f95_in(T40, T41) -> U14(f1_in(T40), T40, T41) U14(f1_out1(T99), T40, T41) -> U15(f662_in(T41, T99), T40, T41, T99) U15(f662_out1(X41, T101), T40, T41, T99) -> f95_out1(T99, X41, T101) f662_in(T41, T99) -> U16(f1_in(T41), T41, T99) U16(f1_out1(T107), T41, T99) -> U17(f736_in(T99, T107), T41, T99, T107) U17(f736_out1(T108), T41, T99, T107) -> f662_out1(T107, T108) f790_in(T177, T179, T178, T180) -> U18(f798_in(T177, T179), T177, T179, T178, T180) U18(f798_out1, T177, T179, T178, T180) -> U19(f799_in(T178, T179, T180), T177, T179, T178, T180) U19(f799_out1(T184), T177, T179, T178, T180) -> f790_out1(T184) f892_in(T277, T279, T278, T280) -> U20(f894_in(T277, T279), T277, T279, T278, T280) U20(f894_out1, T277, T279, T278, T280) -> U21(f895_in(T277, T278, T280), T277, T279, T278, T280) U21(f895_out1(T284), T277, T279, T278, T280) -> f892_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: F894_IN(s(T298), s(T299)) -> F894_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: *F894_IN(s(T298), s(T299)) -> F894_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: F798_IN(s(T198), s(T199)) -> F798_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(f90_in(T31, T32, T33), .(T31, .(T32, T33))) U1(f90_out1(X38, X39, X40, X41, T39), .(T31, .(T32, T33))) -> f1_out1(T39) f644_in([]) -> f644_out1([], []) f644_in(.(T90, T91)) -> U2(f644_in(T91), .(T90, T91)) U2(f644_out1(X130, X129), .(T90, T91)) -> f644_out1(.(T90, X129), X130) f798_in(s(T198), s(T199)) -> U3(f798_in(T198, T199), s(T198), s(T199)) U3(f798_out1, s(T198), s(T199)) -> f798_out1 f798_in(0, s(0)) -> f798_out1 f798_in(0, 0) -> f798_out1 f894_in(s(T298), s(T299)) -> U4(f894_in(T298, T299), s(T298), s(T299)) U4(f894_out1, s(T298), s(T299)) -> f894_out1 f894_in(s(0), 0) -> f894_out1 f93_in(T56, T70, T71) -> U5(f644_in(T71), T56, T70, T71) U5(f644_out1(X99, X98), T56, T70, T71) -> f93_out1(.(T56, X99), .(T70, X98)) f736_in([], T131) -> f736_out1(T131) f736_in(T146, []) -> f736_out1(T146) f736_in(.(T177, T178), .(T179, T180)) -> U6(f790_in(T177, T179, T178, T180), .(T177, T178), .(T179, T180)) U6(f790_out1(T184), .(T177, T178), .(T179, T180)) -> f736_out1(.(T177, T184)) f736_in(.(T395, T396), .(T397, T398)) -> U7(f892_in(T395, T397, T396, T398), .(T395, T396), .(T397, T398)) U7(f892_out1(T402), .(T395, T396), .(T397, T398)) -> f736_out1(.(T397, T402)) f799_in([], T220, T221) -> f799_out1(.(T220, T221)) f799_in(.(T252, T253), T254, T255) -> U8(f790_in(T252, T254, T253, T255), .(T252, T253), T254, T255) U8(f790_out1(T259), .(T252, T253), T254, T255) -> f799_out1(.(T252, T259)) f799_in(.(T277, T278), T279, T280) -> U9(f892_in(T277, T279, T278, T280), .(T277, T278), T279, T280) U9(f892_out1(T284), .(T277, T278), T279, T280) -> f799_out1(.(T279, T284)) f895_in(T314, T315, []) -> f895_out1(.(T314, T315)) f895_in(T345, T346, .(T347, T348)) -> U10(f790_in(T345, T347, T346, T348), T345, T346, .(T347, T348)) U10(f790_out1(T352), T345, T346, .(T347, T348)) -> f895_out1(.(T345, T352)) f895_in(T370, T371, .(T372, T373)) -> U11(f892_in(T370, T372, T371, T373), T370, T371, .(T372, T373)) U11(f892_out1(T377), T370, T371, .(T372, T373)) -> f895_out1(.(T372, T377)) f90_in(T31, T32, T33) -> U12(f93_in(T31, T32, T33), T31, T32, T33) U12(f93_out1(T40, T41), T31, T32, T33) -> U13(f95_in(T40, T41), T31, T32, T33, T40, T41) U13(f95_out1(X40, X41, T43), T31, T32, T33, T40, T41) -> f90_out1(T40, T41, X40, X41, T43) f95_in(T40, T41) -> U14(f1_in(T40), T40, T41) U14(f1_out1(T99), T40, T41) -> U15(f662_in(T41, T99), T40, T41, T99) U15(f662_out1(X41, T101), T40, T41, T99) -> f95_out1(T99, X41, T101) f662_in(T41, T99) -> U16(f1_in(T41), T41, T99) U16(f1_out1(T107), T41, T99) -> U17(f736_in(T99, T107), T41, T99, T107) U17(f736_out1(T108), T41, T99, T107) -> f662_out1(T107, T108) f790_in(T177, T179, T178, T180) -> U18(f798_in(T177, T179), T177, T179, T178, T180) U18(f798_out1, T177, T179, T178, T180) -> U19(f799_in(T178, T179, T180), T177, T179, T178, T180) U19(f799_out1(T184), T177, T179, T178, T180) -> f790_out1(T184) f892_in(T277, T279, T278, T280) -> U20(f894_in(T277, T279), T277, T279, T278, T280) U20(f894_out1, T277, T279, T278, T280) -> U21(f895_in(T277, T278, T280), T277, T279, T278, T280) U21(f895_out1(T284), T277, T279, T278, T280) -> f892_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: F798_IN(s(T198), s(T199)) -> F798_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: *F798_IN(s(T198), s(T199)) -> F798_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: F790_IN(T177, T179, T178, T180) -> U18^1(f798_in(T177, T179), T177, T179, T178, T180) U18^1(f798_out1, T177, T179, T178, T180) -> F799_IN(T178, T179, T180) F799_IN(.(T252, T253), T254, T255) -> F790_IN(T252, T254, T253, T255) F799_IN(.(T277, T278), T279, T280) -> F892_IN(T277, T279, T278, T280) F892_IN(T277, T279, T278, T280) -> U20^1(f894_in(T277, T279), T277, T279, T278, T280) U20^1(f894_out1, T277, T279, T278, T280) -> F895_IN(T277, T278, T280) F895_IN(T345, T346, .(T347, T348)) -> F790_IN(T345, T347, T346, T348) F895_IN(T370, T371, .(T372, T373)) -> F892_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(f90_in(T31, T32, T33), .(T31, .(T32, T33))) U1(f90_out1(X38, X39, X40, X41, T39), .(T31, .(T32, T33))) -> f1_out1(T39) f644_in([]) -> f644_out1([], []) f644_in(.(T90, T91)) -> U2(f644_in(T91), .(T90, T91)) U2(f644_out1(X130, X129), .(T90, T91)) -> f644_out1(.(T90, X129), X130) f798_in(s(T198), s(T199)) -> U3(f798_in(T198, T199), s(T198), s(T199)) U3(f798_out1, s(T198), s(T199)) -> f798_out1 f798_in(0, s(0)) -> f798_out1 f798_in(0, 0) -> f798_out1 f894_in(s(T298), s(T299)) -> U4(f894_in(T298, T299), s(T298), s(T299)) U4(f894_out1, s(T298), s(T299)) -> f894_out1 f894_in(s(0), 0) -> f894_out1 f93_in(T56, T70, T71) -> U5(f644_in(T71), T56, T70, T71) U5(f644_out1(X99, X98), T56, T70, T71) -> f93_out1(.(T56, X99), .(T70, X98)) f736_in([], T131) -> f736_out1(T131) f736_in(T146, []) -> f736_out1(T146) f736_in(.(T177, T178), .(T179, T180)) -> U6(f790_in(T177, T179, T178, T180), .(T177, T178), .(T179, T180)) U6(f790_out1(T184), .(T177, T178), .(T179, T180)) -> f736_out1(.(T177, T184)) f736_in(.(T395, T396), .(T397, T398)) -> U7(f892_in(T395, T397, T396, T398), .(T395, T396), .(T397, T398)) U7(f892_out1(T402), .(T395, T396), .(T397, T398)) -> f736_out1(.(T397, T402)) f799_in([], T220, T221) -> f799_out1(.(T220, T221)) f799_in(.(T252, T253), T254, T255) -> U8(f790_in(T252, T254, T253, T255), .(T252, T253), T254, T255) U8(f790_out1(T259), .(T252, T253), T254, T255) -> f799_out1(.(T252, T259)) f799_in(.(T277, T278), T279, T280) -> U9(f892_in(T277, T279, T278, T280), .(T277, T278), T279, T280) U9(f892_out1(T284), .(T277, T278), T279, T280) -> f799_out1(.(T279, T284)) f895_in(T314, T315, []) -> f895_out1(.(T314, T315)) f895_in(T345, T346, .(T347, T348)) -> U10(f790_in(T345, T347, T346, T348), T345, T346, .(T347, T348)) U10(f790_out1(T352), T345, T346, .(T347, T348)) -> f895_out1(.(T345, T352)) f895_in(T370, T371, .(T372, T373)) -> U11(f892_in(T370, T372, T371, T373), T370, T371, .(T372, T373)) U11(f892_out1(T377), T370, T371, .(T372, T373)) -> f895_out1(.(T372, T377)) f90_in(T31, T32, T33) -> U12(f93_in(T31, T32, T33), T31, T32, T33) U12(f93_out1(T40, T41), T31, T32, T33) -> U13(f95_in(T40, T41), T31, T32, T33, T40, T41) U13(f95_out1(X40, X41, T43), T31, T32, T33, T40, T41) -> f90_out1(T40, T41, X40, X41, T43) f95_in(T40, T41) -> U14(f1_in(T40), T40, T41) U14(f1_out1(T99), T40, T41) -> U15(f662_in(T41, T99), T40, T41, T99) U15(f662_out1(X41, T101), T40, T41, T99) -> f95_out1(T99, X41, T101) f662_in(T41, T99) -> U16(f1_in(T41), T41, T99) U16(f1_out1(T107), T41, T99) -> U17(f736_in(T99, T107), T41, T99, T107) U17(f736_out1(T108), T41, T99, T107) -> f662_out1(T107, T108) f790_in(T177, T179, T178, T180) -> U18(f798_in(T177, T179), T177, T179, T178, T180) U18(f798_out1, T177, T179, T178, T180) -> U19(f799_in(T178, T179, T180), T177, T179, T178, T180) U19(f799_out1(T184), T177, T179, T178, T180) -> f790_out1(T184) f892_in(T277, T279, T278, T280) -> U20(f894_in(T277, T279), T277, T279, T278, T280) U20(f894_out1, T277, T279, T278, T280) -> U21(f895_in(T277, T278, T280), T277, T279, T278, T280) U21(f895_out1(T284), T277, T279, T278, T280) -> f892_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(f798_out1, T177, T179, T178, T180) -> F799_IN(T178, T179, T180) The graph contains the following edges 4 >= 1, 3 >= 2, 5 >= 3 *F799_IN(.(T252, T253), T254, T255) -> F790_IN(T252, T254, T253, T255) The graph contains the following edges 1 > 1, 2 >= 2, 1 > 3, 3 >= 4 *F895_IN(T345, T346, .(T347, T348)) -> F790_IN(T345, T347, T346, T348) The graph contains the following edges 1 >= 1, 3 > 2, 2 >= 3, 3 > 4 *F799_IN(.(T277, T278), T279, T280) -> F892_IN(T277, T279, T278, T280) The graph contains the following edges 1 > 1, 2 >= 2, 1 > 3, 3 >= 4 *F790_IN(T177, T179, T178, T180) -> U18^1(f798_in(T177, T179), T177, T179, T178, T180) The graph contains the following edges 1 >= 2, 2 >= 3, 3 >= 4, 4 >= 5 *F892_IN(T277, T279, T278, T280) -> U20^1(f894_in(T277, T279), T277, T279, T278, T280) The graph contains the following edges 1 >= 2, 2 >= 3, 3 >= 4, 4 >= 5 *U20^1(f894_out1, T277, T279, T278, T280) -> F895_IN(T277, T278, T280) The graph contains the following edges 2 >= 1, 4 >= 2, 5 >= 3 *F895_IN(T370, T371, .(T372, T373)) -> F892_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: F644_IN(.(T90, T91)) -> F644_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(f90_in(T31, T32, T33), .(T31, .(T32, T33))) U1(f90_out1(X38, X39, X40, X41, T39), .(T31, .(T32, T33))) -> f1_out1(T39) f644_in([]) -> f644_out1([], []) f644_in(.(T90, T91)) -> U2(f644_in(T91), .(T90, T91)) U2(f644_out1(X130, X129), .(T90, T91)) -> f644_out1(.(T90, X129), X130) f798_in(s(T198), s(T199)) -> U3(f798_in(T198, T199), s(T198), s(T199)) U3(f798_out1, s(T198), s(T199)) -> f798_out1 f798_in(0, s(0)) -> f798_out1 f798_in(0, 0) -> f798_out1 f894_in(s(T298), s(T299)) -> U4(f894_in(T298, T299), s(T298), s(T299)) U4(f894_out1, s(T298), s(T299)) -> f894_out1 f894_in(s(0), 0) -> f894_out1 f93_in(T56, T70, T71) -> U5(f644_in(T71), T56, T70, T71) U5(f644_out1(X99, X98), T56, T70, T71) -> f93_out1(.(T56, X99), .(T70, X98)) f736_in([], T131) -> f736_out1(T131) f736_in(T146, []) -> f736_out1(T146) f736_in(.(T177, T178), .(T179, T180)) -> U6(f790_in(T177, T179, T178, T180), .(T177, T178), .(T179, T180)) U6(f790_out1(T184), .(T177, T178), .(T179, T180)) -> f736_out1(.(T177, T184)) f736_in(.(T395, T396), .(T397, T398)) -> U7(f892_in(T395, T397, T396, T398), .(T395, T396), .(T397, T398)) U7(f892_out1(T402), .(T395, T396), .(T397, T398)) -> f736_out1(.(T397, T402)) f799_in([], T220, T221) -> f799_out1(.(T220, T221)) f799_in(.(T252, T253), T254, T255) -> U8(f790_in(T252, T254, T253, T255), .(T252, T253), T254, T255) U8(f790_out1(T259), .(T252, T253), T254, T255) -> f799_out1(.(T252, T259)) f799_in(.(T277, T278), T279, T280) -> U9(f892_in(T277, T279, T278, T280), .(T277, T278), T279, T280) U9(f892_out1(T284), .(T277, T278), T279, T280) -> f799_out1(.(T279, T284)) f895_in(T314, T315, []) -> f895_out1(.(T314, T315)) f895_in(T345, T346, .(T347, T348)) -> U10(f790_in(T345, T347, T346, T348), T345, T346, .(T347, T348)) U10(f790_out1(T352), T345, T346, .(T347, T348)) -> f895_out1(.(T345, T352)) f895_in(T370, T371, .(T372, T373)) -> U11(f892_in(T370, T372, T371, T373), T370, T371, .(T372, T373)) U11(f892_out1(T377), T370, T371, .(T372, T373)) -> f895_out1(.(T372, T377)) f90_in(T31, T32, T33) -> U12(f93_in(T31, T32, T33), T31, T32, T33) U12(f93_out1(T40, T41), T31, T32, T33) -> U13(f95_in(T40, T41), T31, T32, T33, T40, T41) U13(f95_out1(X40, X41, T43), T31, T32, T33, T40, T41) -> f90_out1(T40, T41, X40, X41, T43) f95_in(T40, T41) -> U14(f1_in(T40), T40, T41) U14(f1_out1(T99), T40, T41) -> U15(f662_in(T41, T99), T40, T41, T99) U15(f662_out1(X41, T101), T40, T41, T99) -> f95_out1(T99, X41, T101) f662_in(T41, T99) -> U16(f1_in(T41), T41, T99) U16(f1_out1(T107), T41, T99) -> U17(f736_in(T99, T107), T41, T99, T107) U17(f736_out1(T108), T41, T99, T107) -> f662_out1(T107, T108) f790_in(T177, T179, T178, T180) -> U18(f798_in(T177, T179), T177, T179, T178, T180) U18(f798_out1, T177, T179, T178, T180) -> U19(f799_in(T178, T179, T180), T177, T179, T178, T180) U19(f799_out1(T184), T177, T179, T178, T180) -> f790_out1(T184) f892_in(T277, T279, T278, T280) -> U20(f894_in(T277, T279), T277, T279, T278, T280) U20(f894_out1, T277, T279, T278, T280) -> U21(f895_in(T277, T278, T280), T277, T279, T278, T280) U21(f895_out1(T284), T277, T279, T278, T280) -> f892_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: F644_IN(.(T90, T91)) -> F644_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: *F644_IN(.(T90, T91)) -> F644_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))) -> F90_IN(T31, T32, T33) F90_IN(T31, T32, T33) -> U12^1(f93_in(T31, T32, T33), T31, T32, T33) U12^1(f93_out1(T40, T41), T31, T32, T33) -> F95_IN(T40, T41) F95_IN(T40, T41) -> U14^1(f1_in(T40), T40, T41) U14^1(f1_out1(T99), T40, T41) -> F662_IN(T41, T99) F662_IN(T41, T99) -> F1_IN(T41) F95_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(f90_in(T31, T32, T33), .(T31, .(T32, T33))) U1(f90_out1(X38, X39, X40, X41, T39), .(T31, .(T32, T33))) -> f1_out1(T39) f644_in([]) -> f644_out1([], []) f644_in(.(T90, T91)) -> U2(f644_in(T91), .(T90, T91)) U2(f644_out1(X130, X129), .(T90, T91)) -> f644_out1(.(T90, X129), X130) f798_in(s(T198), s(T199)) -> U3(f798_in(T198, T199), s(T198), s(T199)) U3(f798_out1, s(T198), s(T199)) -> f798_out1 f798_in(0, s(0)) -> f798_out1 f798_in(0, 0) -> f798_out1 f894_in(s(T298), s(T299)) -> U4(f894_in(T298, T299), s(T298), s(T299)) U4(f894_out1, s(T298), s(T299)) -> f894_out1 f894_in(s(0), 0) -> f894_out1 f93_in(T56, T70, T71) -> U5(f644_in(T71), T56, T70, T71) U5(f644_out1(X99, X98), T56, T70, T71) -> f93_out1(.(T56, X99), .(T70, X98)) f736_in([], T131) -> f736_out1(T131) f736_in(T146, []) -> f736_out1(T146) f736_in(.(T177, T178), .(T179, T180)) -> U6(f790_in(T177, T179, T178, T180), .(T177, T178), .(T179, T180)) U6(f790_out1(T184), .(T177, T178), .(T179, T180)) -> f736_out1(.(T177, T184)) f736_in(.(T395, T396), .(T397, T398)) -> U7(f892_in(T395, T397, T396, T398), .(T395, T396), .(T397, T398)) U7(f892_out1(T402), .(T395, T396), .(T397, T398)) -> f736_out1(.(T397, T402)) f799_in([], T220, T221) -> f799_out1(.(T220, T221)) f799_in(.(T252, T253), T254, T255) -> U8(f790_in(T252, T254, T253, T255), .(T252, T253), T254, T255) U8(f790_out1(T259), .(T252, T253), T254, T255) -> f799_out1(.(T252, T259)) f799_in(.(T277, T278), T279, T280) -> U9(f892_in(T277, T279, T278, T280), .(T277, T278), T279, T280) U9(f892_out1(T284), .(T277, T278), T279, T280) -> f799_out1(.(T279, T284)) f895_in(T314, T315, []) -> f895_out1(.(T314, T315)) f895_in(T345, T346, .(T347, T348)) -> U10(f790_in(T345, T347, T346, T348), T345, T346, .(T347, T348)) U10(f790_out1(T352), T345, T346, .(T347, T348)) -> f895_out1(.(T345, T352)) f895_in(T370, T371, .(T372, T373)) -> U11(f892_in(T370, T372, T371, T373), T370, T371, .(T372, T373)) U11(f892_out1(T377), T370, T371, .(T372, T373)) -> f895_out1(.(T372, T377)) f90_in(T31, T32, T33) -> U12(f93_in(T31, T32, T33), T31, T32, T33) U12(f93_out1(T40, T41), T31, T32, T33) -> U13(f95_in(T40, T41), T31, T32, T33, T40, T41) U13(f95_out1(X40, X41, T43), T31, T32, T33, T40, T41) -> f90_out1(T40, T41, X40, X41, T43) f95_in(T40, T41) -> U14(f1_in(T40), T40, T41) U14(f1_out1(T99), T40, T41) -> U15(f662_in(T41, T99), T40, T41, T99) U15(f662_out1(X41, T101), T40, T41, T99) -> f95_out1(T99, X41, T101) f662_in(T41, T99) -> U16(f1_in(T41), T41, T99) U16(f1_out1(T107), T41, T99) -> U17(f736_in(T99, T107), T41, T99, T107) U17(f736_out1(T108), T41, T99, T107) -> f662_out1(T107, T108) f790_in(T177, T179, T178, T180) -> U18(f798_in(T177, T179), T177, T179, T178, T180) U18(f798_out1, T177, T179, T178, T180) -> U19(f799_in(T178, T179, T180), T177, T179, T178, T180) U19(f799_out1(T184), T177, T179, T178, T180) -> f790_out1(T184) f892_in(T277, T279, T278, T280) -> U20(f894_in(T277, T279), T277, T279, T278, T280) U20(f894_out1, T277, T279, T278, T280) -> U21(f895_in(T277, T278, T280), T277, T279, T278, T280) U21(f895_out1(T284), T277, T279, T278, T280) -> f892_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))) -> F90_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( f93_in_3(x_1, ..., x_3) ) = 2x_3 POL( U5_4(x_1, ..., x_4) ) = 2x_1 POL( f644_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( f90_in_3(x_1, ..., x_3) ) = 0 POL( f90_out1_5(x_1, ..., x_5) ) = x_1 + x_2 + 2x_3 + 2x_5 POL( f93_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( f95_in_2(x_1, x_2) ) = 0 POL( f95_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( f662_in_2(x_1, x_2) ) = 0 POL( f662_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( f736_in_2(x_1, x_2) ) = 0 POL( f644_out1_2(x_1, x_2) ) = x_1 + x_2 POL( U2_2(x_1, x_2) ) = 2x_1 + 1 POL( f736_out1_1(x_1) ) = max{0, -2} POL( U6_3(x_1, ..., x_3) ) = max{0, 2x_1 - 2} POL( f790_in_4(x_1, ..., x_4) ) = 2x_2 + 2x_4 + 2 POL( U7_3(x_1, ..., x_3) ) = max{0, -2} POL( f892_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( f798_in_2(x_1, x_2) ) = 2x_1 + 2 POL( f790_out1_1(x_1) ) = 2 POL( U20_5(x_1, ..., x_5) ) = max{0, 2x_1 + 2x_4 + 2x_5 - 2} POL( f894_in_2(x_1, x_2) ) = 2x_1 POL( f892_out1_1(x_1) ) = 2 POL( f798_out1 ) = 0 POL( U19_5(x_1, ..., x_5) ) = max{0, x_1 + 2x_4 + 2x_5 - 2} POL( f799_in_3(x_1, ..., x_3) ) = 0 POL( f799_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( f894_out1 ) = 0 POL( U21_5(x_1, ..., x_5) ) = max{0, x_3 - 2} POL( f895_in_3(x_1, ..., x_3) ) = x_1 + 2x_2 + 2 POL( f895_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( F90_IN_3(x_1, ..., x_3) ) = 2x_3 + 2 POL( F95_IN_2(x_1, x_2) ) = x_1 + x_2 POL( F662_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: f93_in(T56, T70, T71) -> U5(f644_in(T71), T56, T70, T71) f644_in([]) -> f644_out1([], []) f644_in(.(T90, T91)) -> U2(f644_in(T91), .(T90, T91)) U5(f644_out1(X99, X98), T56, T70, T71) -> f93_out1(.(T56, X99), .(T70, X98)) U2(f644_out1(X130, X129), .(T90, T91)) -> f644_out1(.(T90, X129), X130) ---------------------------------------- (27) Obligation: Q DP problem: The TRS P consists of the following rules: F90_IN(T31, T32, T33) -> U12^1(f93_in(T31, T32, T33), T31, T32, T33) U12^1(f93_out1(T40, T41), T31, T32, T33) -> F95_IN(T40, T41) F95_IN(T40, T41) -> U14^1(f1_in(T40), T40, T41) U14^1(f1_out1(T99), T40, T41) -> F662_IN(T41, T99) F662_IN(T41, T99) -> F1_IN(T41) F95_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(f90_in(T31, T32, T33), .(T31, .(T32, T33))) U1(f90_out1(X38, X39, X40, X41, T39), .(T31, .(T32, T33))) -> f1_out1(T39) f644_in([]) -> f644_out1([], []) f644_in(.(T90, T91)) -> U2(f644_in(T91), .(T90, T91)) U2(f644_out1(X130, X129), .(T90, T91)) -> f644_out1(.(T90, X129), X130) f798_in(s(T198), s(T199)) -> U3(f798_in(T198, T199), s(T198), s(T199)) U3(f798_out1, s(T198), s(T199)) -> f798_out1 f798_in(0, s(0)) -> f798_out1 f798_in(0, 0) -> f798_out1 f894_in(s(T298), s(T299)) -> U4(f894_in(T298, T299), s(T298), s(T299)) U4(f894_out1, s(T298), s(T299)) -> f894_out1 f894_in(s(0), 0) -> f894_out1 f93_in(T56, T70, T71) -> U5(f644_in(T71), T56, T70, T71) U5(f644_out1(X99, X98), T56, T70, T71) -> f93_out1(.(T56, X99), .(T70, X98)) f736_in([], T131) -> f736_out1(T131) f736_in(T146, []) -> f736_out1(T146) f736_in(.(T177, T178), .(T179, T180)) -> U6(f790_in(T177, T179, T178, T180), .(T177, T178), .(T179, T180)) U6(f790_out1(T184), .(T177, T178), .(T179, T180)) -> f736_out1(.(T177, T184)) f736_in(.(T395, T396), .(T397, T398)) -> U7(f892_in(T395, T397, T396, T398), .(T395, T396), .(T397, T398)) U7(f892_out1(T402), .(T395, T396), .(T397, T398)) -> f736_out1(.(T397, T402)) f799_in([], T220, T221) -> f799_out1(.(T220, T221)) f799_in(.(T252, T253), T254, T255) -> U8(f790_in(T252, T254, T253, T255), .(T252, T253), T254, T255) U8(f790_out1(T259), .(T252, T253), T254, T255) -> f799_out1(.(T252, T259)) f799_in(.(T277, T278), T279, T280) -> U9(f892_in(T277, T279, T278, T280), .(T277, T278), T279, T280) U9(f892_out1(T284), .(T277, T278), T279, T280) -> f799_out1(.(T279, T284)) f895_in(T314, T315, []) -> f895_out1(.(T314, T315)) f895_in(T345, T346, .(T347, T348)) -> U10(f790_in(T345, T347, T346, T348), T345, T346, .(T347, T348)) U10(f790_out1(T352), T345, T346, .(T347, T348)) -> f895_out1(.(T345, T352)) f895_in(T370, T371, .(T372, T373)) -> U11(f892_in(T370, T372, T371, T373), T370, T371, .(T372, T373)) U11(f892_out1(T377), T370, T371, .(T372, T373)) -> f895_out1(.(T372, T377)) f90_in(T31, T32, T33) -> U12(f93_in(T31, T32, T33), T31, T32, T33) U12(f93_out1(T40, T41), T31, T32, T33) -> U13(f95_in(T40, T41), T31, T32, T33, T40, T41) U13(f95_out1(X40, X41, T43), T31, T32, T33, T40, T41) -> f90_out1(T40, T41, X40, X41, T43) f95_in(T40, T41) -> U14(f1_in(T40), T40, T41) U14(f1_out1(T99), T40, T41) -> U15(f662_in(T41, T99), T40, T41, T99) U15(f662_out1(X41, T101), T40, T41, T99) -> f95_out1(T99, X41, T101) f662_in(T41, T99) -> U16(f1_in(T41), T41, T99) U16(f1_out1(T107), T41, T99) -> U17(f736_in(T99, T107), T41, T99, T107) U17(f736_out1(T108), T41, T99, T107) -> f662_out1(T107, T108) f790_in(T177, T179, T178, T180) -> U18(f798_in(T177, T179), T177, T179, T178, T180) U18(f798_out1, T177, T179, T178, T180) -> U19(f799_in(T178, T179, T180), T177, T179, T178, T180) U19(f799_out1(T184), T177, T179, T178, T180) -> f790_out1(T184) f892_in(T277, T279, T278, T280) -> U20(f894_in(T277, T279), T277, T279, T278, T280) U20(f894_out1, T277, T279, T278, T280) -> U21(f895_in(T277, T278, T280), T277, T279, T278, T280) U21(f895_out1(T284), T277, T279, T278, T280) -> f892_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