/export/starexec/sandbox/solver/bin/starexec_run_standard /export/starexec/sandbox/benchmark/theBenchmark.pl /export/starexec/sandbox/output/output_files -------------------------------------------------------------------------------- YES proof of /export/starexec/sandbox/benchmark/theBenchmark.pl # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty Left Termination of the query pattern merge(g,g,a) w.r.t. the given Prolog program could successfully be proven: (0) Prolog (1) PrologToDTProblemTransformerProof [SOUND, 50 ms] (2) TRIPLES (3) TriplesToPiDPProof [SOUND, 24 ms] (4) PiDP (5) DependencyGraphProof [EQUIVALENT, 0 ms] (6) AND (7) PiDP (8) UsableRulesProof [EQUIVALENT, 0 ms] (9) PiDP (10) PiDPToQDPProof [EQUIVALENT, 0 ms] (11) QDP (12) QDPSizeChangeProof [EQUIVALENT, 0 ms] (13) YES (14) PiDP (15) UsableRulesProof [EQUIVALENT, 0 ms] (16) PiDP (17) PiDPToQDPProof [EQUIVALENT, 0 ms] (18) QDP (19) QDPSizeChangeProof [EQUIVALENT, 0 ms] (20) YES (21) PiDP (22) PiDPToQDPProof [SOUND, 0 ms] (23) QDP (24) MRRProof [EQUIVALENT, 48 ms] (25) QDP (26) DependencyGraphProof [EQUIVALENT, 0 ms] (27) QDP (28) UsableRulesProof [EQUIVALENT, 0 ms] (29) QDP (30) QReductionProof [EQUIVALENT, 0 ms] (31) QDP (32) QDPSizeChangeProof [EQUIVALENT, 0 ms] (33) YES ---------------------------------------- (0) Obligation: Clauses: merge([], X, X). merge(X, [], X). merge(.(X, Xs), .(Y, Ys), .(X, Zs)) :- ','(leq(X, Y), merge(Xs, .(Y, Ys), Zs)). merge(.(X, Xs), .(Y, Ys), .(Y, Zs)) :- ','(less(Y, X), merge(.(X, Xs), Ys, Zs)). less(0, s(0)). less(s(X), s(Y)) :- less(X, Y). leq(0, 0). leq(0, s(0)). leq(s(X), s(Y)) :- leq(X, Y). Query: merge(g,g,a) ---------------------------------------- (1) PrologToDTProblemTransformerProof (SOUND) Built DT problem from termination graph DT10. { "root": 1, "program": { "directives": [], "clauses": [ [ "(merge ([]) X X)", null ], [ "(merge X ([]) X)", null ], [ "(merge (. X Xs) (. Y Ys) (. X Zs))", "(',' (leq X Y) (merge Xs (. Y Ys) Zs))" ], [ "(merge (. X Xs) (. Y Ys) (. Y Zs))", "(',' (less Y X) (merge (. X Xs) Ys Zs))" ], [ "(less (0) (s (0)))", null ], [ "(less (s X) (s Y))", "(less X Y)" ], [ "(leq (0) (0))", null ], [ "(leq (0) (s (0)))", null ], [ "(leq (s X) (s Y))", "(leq X Y)" ] ] }, "graph": { "nodes": { "390": { "goal": [{ "clause": -1, "scope": -1, "term": "(leq T35 T36)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T35", "T36" ], "free": [], "exprvars": [] } }, "270": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "391": { "goal": [{ "clause": -1, "scope": -1, "term": "(merge T18 (. (s T36) T20) T22)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T18", "T20", "T36" ], "free": [], "exprvars": [] } }, "type": "Nodes", "271": { "goal": [{ "clause": 3, "scope": 1, "term": "(merge ([]) T5 T3)" }], "kb": { "nonunifying": [[ "(merge ([]) T5 T3)", "(merge X4 ([]) X4)" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T5"], "free": ["X4"], "exprvars": [] } }, "392": { "goal": [ { "clause": 6, "scope": 3, "term": "(leq T35 T36)" }, { "clause": 7, "scope": 3, "term": "(leq T35 T36)" }, { "clause": 8, "scope": 3, "term": "(leq T35 T36)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T35", "T36" ], "free": [], "exprvars": [] } }, "393": { "goal": [{ "clause": 6, "scope": 3, "term": "(leq T35 T36)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T35", "T36" ], "free": [], "exprvars": [] } }, "273": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "394": { "goal": [ { "clause": 7, "scope": 3, "term": "(leq T35 T36)" }, { "clause": 8, "scope": 3, "term": "(leq T35 T36)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T35", "T36" ], "free": [], "exprvars": [] } }, "395": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "396": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "397": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "398": { "goal": [{ "clause": 7, "scope": 3, "term": "(leq T35 T36)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T35", "T36" ], "free": [], "exprvars": [] } }, "399": { "goal": [{ "clause": 8, "scope": 3, "term": "(leq T35 T36)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T35", "T36" ], "free": [], "exprvars": [] } }, "319": { "goal": [ { "clause": -1, "scope": -1, "term": "(true)" }, { "clause": 2, "scope": 1, "term": "(merge T7 ([]) T3)" }, { "clause": 3, "scope": 1, "term": "(merge T7 ([]) T3)" } ], "kb": { "nonunifying": [[ "(merge T7 ([]) T3)", "(merge ([]) X2 X2)" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T7"], "free": ["X2"], "exprvars": [] } }, "1": { "goal": [{ "clause": -1, "scope": -1, "term": "(merge T1 T2 T3)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T1", "T2" ], "free": [], "exprvars": [] } }, "320": { "goal": [ { "clause": 2, "scope": 1, "term": "(merge T1 T2 T3)" }, { "clause": 3, "scope": 1, "term": "(merge T1 T2 T3)" } ], "kb": { "nonunifying": [ [ "(merge T1 T2 T3)", "(merge ([]) X2 X2)" ], [ "(merge T1 T2 T3)", "(merge X26 ([]) X26)" ] ], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T1", "T2" ], "free": [ "X2", "X26" ], "exprvars": [] } }, "321": { "goal": [ { "clause": 2, "scope": 1, "term": "(merge T7 ([]) T3)" }, { "clause": 3, "scope": 1, "term": "(merge T7 ([]) T3)" } ], "kb": { "nonunifying": [[ "(merge T7 ([]) T3)", "(merge ([]) X2 X2)" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T7"], "free": ["X2"], "exprvars": [] } }, "3": { "goal": [ { "clause": 0, "scope": 1, "term": "(merge T1 T2 T3)" }, { "clause": 1, "scope": 1, "term": "(merge T1 T2 T3)" }, { "clause": 2, "scope": 1, "term": "(merge T1 T2 T3)" }, { "clause": 3, "scope": 1, "term": "(merge T1 T2 T3)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T1", "T2" ], "free": [], "exprvars": [] } }, "400": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "401": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "325": { "goal": [{ "clause": 3, "scope": 1, "term": "(merge T7 ([]) T3)" }], "kb": { "nonunifying": [[ "(merge T7 ([]) T3)", "(merge ([]) X2 X2)" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T7"], "free": ["X2"], "exprvars": [] } }, "402": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "403": { "goal": [{ "clause": -1, "scope": -1, "term": "(leq T41 T42)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T41", "T42" ], "free": [], "exprvars": [] } }, "404": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "328": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "405": { "goal": [{ "clause": 3, "scope": 1, "term": "(merge (. T17 T18) (. T19 T20) T3)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T17", "T18", "T19", "T20" ], "free": [], "exprvars": [] } }, "406": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (less T59 T57) (merge (. T57 T58) T60 T62))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T57", "T58", "T59", "T60" ], "free": [], "exprvars": [] } }, "407": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "408": { "goal": [{ "clause": -1, "scope": -1, "term": "(less T59 T57)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T57", "T59" ], "free": [], "exprvars": [] } }, "409": { "goal": [{ "clause": -1, "scope": -1, "term": "(merge (. T57 T58) T60 T62)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T57", "T58", "T60" ], "free": [], "exprvars": [] } }, "372": { "goal": [{ "clause": 7, "scope": 2, "term": "(',' (leq T17 T19) (merge T18 (. T19 T20) T22))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T17", "T18", "T19", "T20" ], "free": [], "exprvars": [] } }, "373": { "goal": [ { "clause": 8, "scope": 2, "term": "(',' (leq T17 T19) (merge T18 (. T19 T20) T22))" }, { "clause": -1, "scope": 2, "term": null }, { "clause": 3, "scope": 1, "term": "(merge (. T17 T18) (. T19 T20) T3)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T17", "T18", "T19", "T20" ], "free": [], "exprvars": [] } }, "374": { "goal": [{ "clause": -1, "scope": -1, "term": "(merge T18 (. (s (0)) T20) T22)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T18", "T20" ], "free": [], "exprvars": [] } }, "375": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "410": { "goal": [ { "clause": 4, "scope": 4, "term": "(less T59 T57)" }, { "clause": 5, "scope": 4, "term": "(less T59 T57)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T57", "T59" ], "free": [], "exprvars": [] } }, "334": { "goal": [ { "clause": -1, "scope": -1, "term": "(',' (leq T17 T19) (merge T18 (. T19 T20) T22))" }, { "clause": 3, "scope": 1, "term": "(merge (. T17 T18) (. T19 T20) T3)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T17", "T18", "T19", "T20" ], "free": [], "exprvars": [] } }, "411": { "goal": [{ "clause": 4, "scope": 4, "term": "(less T59 T57)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T57", "T59" ], "free": [], "exprvars": [] } }, "335": { "goal": [{ "clause": 3, "scope": 1, "term": "(merge T1 T2 T3)" }], "kb": { "nonunifying": [ [ "(merge T1 T2 T3)", "(merge ([]) X2 X2)" ], [ "(merge T1 T2 T3)", "(merge X26 ([]) X26)" ], [ "(merge T1 T2 T3)", "(merge (. X42 X43) (. X44 X45) (. X42 X46))" ] ], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T1", "T2" ], "free": [ "X2", "X26", "X42", "X43", "X44", "X45", "X46" ], "exprvars": [] } }, "412": { "goal": [{ "clause": 5, "scope": 4, "term": "(less T59 T57)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T57", "T59" ], "free": [], "exprvars": [] } }, "336": { "goal": [ { "clause": 6, "scope": 2, "term": "(',' (leq T17 T19) (merge T18 (. T19 T20) T22))" }, { "clause": 7, "scope": 2, "term": "(',' (leq T17 T19) (merge T18 (. T19 T20) T22))" }, { "clause": 8, "scope": 2, "term": "(',' (leq T17 T19) (merge T18 (. T19 T20) T22))" }, { "clause": -1, "scope": 2, "term": null }, { "clause": 3, "scope": 1, "term": "(merge (. T17 T18) (. T19 T20) T3)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T17", "T18", "T19", "T20" ], "free": [], "exprvars": [] } }, "413": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "337": { "goal": [{ "clause": 6, "scope": 2, "term": "(',' (leq T17 T19) (merge T18 (. T19 T20) T22))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T17", "T18", "T19", "T20" ], "free": [], "exprvars": [] } }, "414": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "338": { "goal": [ { "clause": 7, "scope": 2, "term": "(',' (leq T17 T19) (merge T18 (. T19 T20) T22))" }, { "clause": 8, "scope": 2, "term": "(',' (leq T17 T19) (merge T18 (. T19 T20) T22))" }, { "clause": -1, "scope": 2, "term": null }, { "clause": 3, "scope": 1, "term": "(merge (. T17 T18) (. T19 T20) T3)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T17", "T18", "T19", "T20" ], "free": [], "exprvars": [] } }, "415": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "339": { "goal": [{ "clause": -1, "scope": -1, "term": "(merge T18 (. (0) T20) T22)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T18", "T20" ], "free": [], "exprvars": [] } }, "416": { "goal": [{ "clause": -1, "scope": -1, "term": "(less T67 T68)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T67", "T68" ], "free": [], "exprvars": [] } }, "417": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "418": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (less T76 T74) (merge (. T74 T75) T77 T79))" }], "kb": { "nonunifying": [[ "(merge (. T74 T75) (. T76 T77) T3)", "(merge (. X42 X43) (. X44 X45) (. X42 X46))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T74", "T75", "T76", "T77" ], "free": [ "X42", "X43", "X44", "X45", "X46" ], "exprvars": [] } }, "419": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "261": { "goal": [ { "clause": -1, "scope": -1, "term": "(true)" }, { "clause": 1, "scope": 1, "term": "(merge ([]) T5 T3)" }, { "clause": 2, "scope": 1, "term": "(merge ([]) T5 T3)" }, { "clause": 3, "scope": 1, "term": "(merge ([]) T5 T3)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T5"], "free": [], "exprvars": [] } }, "262": { "goal": [ { "clause": 1, "scope": 1, "term": "(merge T1 T2 T3)" }, { "clause": 2, "scope": 1, "term": "(merge T1 T2 T3)" }, { "clause": 3, "scope": 1, "term": "(merge T1 T2 T3)" } ], "kb": { "nonunifying": [[ "(merge T1 T2 T3)", "(merge ([]) X2 X2)" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T1", "T2" ], "free": ["X2"], "exprvars": [] } }, "263": { "goal": [ { "clause": 1, "scope": 1, "term": "(merge ([]) T5 T3)" }, { "clause": 2, "scope": 1, "term": "(merge ([]) T5 T3)" }, { "clause": 3, "scope": 1, "term": "(merge ([]) T5 T3)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T5"], "free": [], "exprvars": [] } }, "340": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "264": { "goal": [ { "clause": -1, "scope": -1, "term": "(true)" }, { "clause": 2, "scope": 1, "term": "(merge ([]) ([]) T3)" }, { "clause": 3, "scope": 1, "term": "(merge ([]) ([]) T3)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "386": { "goal": [{ "clause": 8, "scope": 2, "term": "(',' (leq T17 T19) (merge T18 (. T19 T20) T22))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T17", "T18", "T19", "T20" ], "free": [], "exprvars": [] } }, "387": { "goal": [ { "clause": -1, "scope": 2, "term": null }, { "clause": 3, "scope": 1, "term": "(merge (. T17 T18) (. T19 T20) T3)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T17", "T18", "T19", "T20" ], "free": [], "exprvars": [] } }, "420": { "goal": [ { "clause": 4, "scope": 5, "term": "(',' (less T76 T74) (merge (. T74 T75) T77 T79))" }, { "clause": 5, "scope": 5, "term": "(',' (less T76 T74) (merge (. T74 T75) T77 T79))" } ], "kb": { "nonunifying": [[ "(merge (. T74 T75) (. T76 T77) T3)", "(merge (. X42 X43) (. X44 X45) (. X42 X46))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T74", "T75", "T76", "T77" ], "free": [ "X42", "X43", "X44", "X45", "X46" ], "exprvars": [] } }, "267": { "goal": [ { "clause": 2, "scope": 1, "term": "(merge ([]) T5 T3)" }, { "clause": 3, "scope": 1, "term": "(merge ([]) T5 T3)" } ], "kb": { "nonunifying": [[ "(merge ([]) T5 T3)", "(merge X4 ([]) X4)" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T5"], "free": ["X4"], "exprvars": [] } }, "388": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (leq T35 T36) (merge T18 (. (s T36) T20) T22))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T18", "T20", "T35", "T36" ], "free": [], "exprvars": [] } }, "421": { "goal": [{ "clause": 4, "scope": 5, "term": "(',' (less T76 T74) (merge (. T74 T75) T77 T79))" }], "kb": { "nonunifying": [[ "(merge (. T74 T75) (. T76 T77) T3)", "(merge (. X42 X43) (. X44 X45) (. X42 X46))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T74", "T75", "T76", "T77" ], "free": [ "X42", "X43", "X44", "X45", "X46" ], "exprvars": [] } }, "268": { "goal": [ { "clause": 2, "scope": 1, "term": "(merge ([]) ([]) T3)" }, { "clause": 3, "scope": 1, "term": "(merge ([]) ([]) T3)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "389": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "422": { "goal": [{ "clause": 5, "scope": 5, "term": "(',' (less T76 T74) (merge (. T74 T75) T77 T79))" }], "kb": { "nonunifying": [[ "(merge (. T74 T75) (. T76 T77) T3)", "(merge (. X42 X43) (. X44 X45) (. X42 X46))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T74", "T75", "T76", "T77" ], "free": [ "X42", "X43", "X44", "X45", "X46" ], "exprvars": [] } }, "269": { "goal": [{ "clause": 3, "scope": 1, "term": "(merge ([]) ([]) T3)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "423": { "goal": [{ "clause": -1, "scope": -1, "term": "(merge (. (s (0)) T75) T77 T79)" }], "kb": { "nonunifying": [[ "(merge (. (s (0)) T75) (. (0) T77) T3)", "(merge (. X42 X43) (. X44 X45) (. X42 X46))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T75", "T77" ], "free": [ "X42", "X43", "X44", "X45", "X46" ], "exprvars": [] } }, "424": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "425": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (less T84 T85) (merge (. (s T85) T75) T77 T79))" }], "kb": { "nonunifying": [[ "(merge (. (s T85) T75) (. (s T84) T77) T3)", "(merge (. X42 X43) (. X44 X45) (. X42 X46))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T75", "T77", "T84", "T85" ], "free": [ "X42", "X43", "X44", "X45", "X46" ], "exprvars": [] } }, "426": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "427": { "goal": [{ "clause": -1, "scope": -1, "term": "(less T84 T85)" }], "kb": { "nonunifying": [[ "(merge (. (s T85) T75) (. (s T84) T77) T3)", "(merge (. X42 X43) (. X44 X45) (. X42 X46))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T75", "T77", "T84", "T85" ], "free": [ "X42", "X43", "X44", "X45", "X46" ], "exprvars": [] } }, "428": { "goal": [{ "clause": -1, "scope": -1, "term": "(merge (. (s T85) T75) T77 T79)" }], "kb": { "nonunifying": [[ "(merge (. (s T85) T75) (. (s T84) T77) T3)", "(merge (. X42 X43) (. X44 X45) (. X42 X46))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T75", "T77", "T84", "T85" ], "free": [ "X42", "X43", "X44", "X45", "X46" ], "exprvars": [] } } }, "edges": [ { "from": 1, "to": 3, "label": "CASE" }, { "from": 3, "to": 261, "label": "EVAL with clause\nmerge([], X2, X2).\nand substitutionT1 -> [],\nT2 -> T5,\nX2 -> T5,\nT3 -> T5" }, { "from": 3, "to": 262, "label": "EVAL-BACKTRACK" }, { "from": 261, "to": 263, "label": "SUCCESS" }, { "from": 262, "to": 319, "label": "EVAL with clause\nmerge(X26, [], X26).\nand substitutionT1 -> T7,\nX26 -> T7,\nT2 -> [],\nT3 -> T7" }, { "from": 262, "to": 320, "label": "EVAL-BACKTRACK" }, { "from": 263, "to": 264, "label": "EVAL with clause\nmerge(X4, [], X4).\nand substitutionX4 -> [],\nT5 -> [],\nT3 -> []" }, { "from": 263, "to": 267, "label": "EVAL-BACKTRACK" }, { "from": 264, "to": 268, "label": "SUCCESS" }, { "from": 267, "to": 271, "label": "BACKTRACK\nfor clause: merge(.(X, Xs), .(Y, Ys), .(X, Zs)) :- ','(leq(X, Y), merge(Xs, .(Y, Ys), Zs))because of non-unification" }, { "from": 268, "to": 269, "label": "BACKTRACK\nfor clause: merge(.(X, Xs), .(Y, Ys), .(X, Zs)) :- ','(leq(X, Y), merge(Xs, .(Y, Ys), Zs))because of non-unification" }, { "from": 269, "to": 270, "label": "BACKTRACK\nfor clause: merge(.(X, Xs), .(Y, Ys), .(Y, Zs)) :- ','(less(Y, X), merge(.(X, Xs), Ys, Zs))because of non-unification" }, { "from": 271, "to": 273, "label": "BACKTRACK\nfor clause: merge(.(X, Xs), .(Y, Ys), .(Y, Zs)) :- ','(less(Y, X), merge(.(X, Xs), Ys, Zs))because of non-unification" }, { "from": 319, "to": 321, "label": "SUCCESS" }, { "from": 320, "to": 334, "label": "EVAL with clause\nmerge(.(X42, X43), .(X44, X45), .(X42, X46)) :- ','(leq(X42, X44), merge(X43, .(X44, X45), X46)).\nand substitutionX42 -> T17,\nX43 -> T18,\nT1 -> .(T17, T18),\nX44 -> T19,\nX45 -> T20,\nT2 -> .(T19, T20),\nX46 -> T22,\nT3 -> .(T17, T22),\nT21 -> T22" }, { "from": 320, "to": 335, "label": "EVAL-BACKTRACK" }, { "from": 321, "to": 325, "label": "BACKTRACK\nfor clause: merge(.(X, Xs), .(Y, Ys), .(X, Zs)) :- ','(leq(X, Y), merge(Xs, .(Y, Ys), Zs))because of non-unification" }, { "from": 325, "to": 328, "label": "BACKTRACK\nfor clause: merge(.(X, Xs), .(Y, Ys), .(Y, Zs)) :- ','(less(Y, X), merge(.(X, Xs), Ys, Zs))because of non-unification" }, { "from": 334, "to": 336, "label": "CASE" }, { "from": 335, "to": 418, "label": "EVAL with clause\nmerge(.(X97, X98), .(X99, X100), .(X99, X101)) :- ','(less(X99, X97), merge(.(X97, X98), X100, X101)).\nand substitutionX97 -> T74,\nX98 -> T75,\nT1 -> .(T74, T75),\nX99 -> T76,\nX100 -> T77,\nT2 -> .(T76, T77),\nX101 -> T79,\nT3 -> .(T76, T79),\nT78 -> T79" }, { "from": 335, "to": 419, "label": "EVAL-BACKTRACK" }, { "from": 336, "to": 337, "label": "PARALLEL" }, { "from": 336, "to": 338, "label": "PARALLEL" }, { "from": 337, "to": 339, "label": "EVAL with clause\nleq(0, 0).\nand substitutionT17 -> 0,\nT19 -> 0" }, { "from": 337, "to": 340, "label": "EVAL-BACKTRACK" }, { "from": 338, "to": 372, "label": "PARALLEL" }, { "from": 338, "to": 373, "label": "PARALLEL" }, { "from": 339, "to": 1, "label": "INSTANCE with matching:\nT1 -> T18\nT2 -> .(0, T20)\nT3 -> T22" }, { "from": 372, "to": 374, "label": "EVAL with clause\nleq(0, s(0)).\nand substitutionT17 -> 0,\nT19 -> s(0)" }, { "from": 372, "to": 375, "label": "EVAL-BACKTRACK" }, { "from": 373, "to": 386, "label": "PARALLEL" }, { "from": 373, "to": 387, "label": "PARALLEL" }, { "from": 374, "to": 1, "label": "INSTANCE with matching:\nT1 -> T18\nT2 -> .(s(0), T20)\nT3 -> T22" }, { "from": 386, "to": 388, "label": "EVAL with clause\nleq(s(X59), s(X60)) :- leq(X59, X60).\nand substitutionX59 -> T35,\nT17 -> s(T35),\nX60 -> T36,\nT19 -> s(T36)" }, { "from": 386, "to": 389, "label": "EVAL-BACKTRACK" }, { "from": 387, "to": 405, "label": "FAILURE" }, { "from": 388, "to": 390, "label": "SPLIT 1" }, { "from": 388, "to": 391, "label": "SPLIT 2\nnew knowledge:\nT35 is ground\nT36 is ground" }, { "from": 390, "to": 392, "label": "CASE" }, { "from": 391, "to": 1, "label": "INSTANCE with matching:\nT1 -> T18\nT2 -> .(s(T36), T20)\nT3 -> T22" }, { "from": 392, "to": 393, "label": "PARALLEL" }, { "from": 392, "to": 394, "label": "PARALLEL" }, { "from": 393, "to": 395, "label": "EVAL with clause\nleq(0, 0).\nand substitutionT35 -> 0,\nT36 -> 0" }, { "from": 393, "to": 396, "label": "EVAL-BACKTRACK" }, { "from": 394, "to": 398, "label": "PARALLEL" }, { "from": 394, "to": 399, "label": "PARALLEL" }, { "from": 395, "to": 397, "label": "SUCCESS" }, { "from": 398, "to": 400, "label": "EVAL with clause\nleq(0, s(0)).\nand substitutionT35 -> 0,\nT36 -> s(0)" }, { "from": 398, "to": 401, "label": "EVAL-BACKTRACK" }, { "from": 399, "to": 403, "label": "EVAL with clause\nleq(s(X65), s(X66)) :- leq(X65, X66).\nand substitutionX65 -> T41,\nT35 -> s(T41),\nX66 -> T42,\nT36 -> s(T42)" }, { "from": 399, "to": 404, "label": "EVAL-BACKTRACK" }, { "from": 400, "to": 402, "label": "SUCCESS" }, { "from": 403, "to": 390, "label": "INSTANCE with matching:\nT35 -> T41\nT36 -> T42" }, { "from": 405, "to": 406, "label": "EVAL with clause\nmerge(.(X79, X80), .(X81, X82), .(X81, X83)) :- ','(less(X81, X79), merge(.(X79, X80), X82, X83)).\nand substitutionT17 -> T57,\nX79 -> T57,\nT18 -> T58,\nX80 -> T58,\nT19 -> T59,\nX81 -> T59,\nT20 -> T60,\nX82 -> T60,\nX83 -> T62,\nT3 -> .(T59, T62),\nT61 -> T62" }, { "from": 405, "to": 407, "label": "EVAL-BACKTRACK" }, { "from": 406, "to": 408, "label": "SPLIT 1" }, { "from": 406, "to": 409, "label": "SPLIT 2\nnew knowledge:\nT59 is ground\nT57 is ground" }, { "from": 408, "to": 410, "label": "CASE" }, { "from": 409, "to": 1, "label": "INSTANCE with matching:\nT1 -> .(T57, T58)\nT2 -> T60\nT3 -> T62" }, { "from": 410, "to": 411, "label": "PARALLEL" }, { "from": 410, "to": 412, "label": "PARALLEL" }, { "from": 411, "to": 413, "label": "EVAL with clause\nless(0, s(0)).\nand substitutionT59 -> 0,\nT57 -> s(0)" }, { "from": 411, "to": 414, "label": "EVAL-BACKTRACK" }, { "from": 412, "to": 416, "label": "EVAL with clause\nless(s(X88), s(X89)) :- less(X88, X89).\nand substitutionX88 -> T67,\nT59 -> s(T67),\nX89 -> T68,\nT57 -> s(T68)" }, { "from": 412, "to": 417, "label": "EVAL-BACKTRACK" }, { "from": 413, "to": 415, "label": "SUCCESS" }, { "from": 416, "to": 408, "label": "INSTANCE with matching:\nT59 -> T67\nT57 -> T68" }, { "from": 418, "to": 420, "label": "CASE" }, { "from": 420, "to": 421, "label": "PARALLEL" }, { "from": 420, "to": 422, "label": "PARALLEL" }, { "from": 421, "to": 423, "label": "EVAL with clause\nless(0, s(0)).\nand substitutionT76 -> 0,\nT74 -> s(0)" }, { "from": 421, "to": 424, "label": "EVAL-BACKTRACK" }, { "from": 422, "to": 425, "label": "EVAL with clause\nless(s(X108), s(X109)) :- less(X108, X109).\nand substitutionX108 -> T84,\nT76 -> s(T84),\nX109 -> T85,\nT74 -> s(T85)" }, { "from": 422, "to": 426, "label": "EVAL-BACKTRACK" }, { "from": 423, "to": 1, "label": "INSTANCE with matching:\nT1 -> .(s(0), T75)\nT2 -> T77\nT3 -> T79" }, { "from": 425, "to": 427, "label": "SPLIT 1" }, { "from": 425, "to": 428, "label": "SPLIT 2\nnew knowledge:\nT84 is ground\nT85 is ground" }, { "from": 427, "to": 408, "label": "INSTANCE with matching:\nT59 -> T84\nT57 -> T85" }, { "from": 428, "to": 1, "label": "INSTANCE with matching:\nT1 -> .(s(T85), T75)\nT2 -> T77\nT3 -> T79" } ], "type": "Graph" } } ---------------------------------------- (2) Obligation: Triples: leqB(s(X1), s(X2)) :- leqB(X1, X2). lessC(s(X1), s(X2)) :- lessC(X1, X2). mergeA(.(0, X1), .(0, X2), .(0, X3)) :- mergeA(X1, .(0, X2), X3). mergeA(.(0, X1), .(s(0), X2), .(0, X3)) :- mergeA(X1, .(s(0), X2), X3). mergeA(.(s(X1), X2), .(s(X3), X4), .(s(X1), X5)) :- leqB(X1, X3). mergeA(.(s(X1), X2), .(s(X3), X4), .(s(X1), X5)) :- ','(leqcB(X1, X3), mergeA(X2, .(s(X3), X4), X5)). mergeA(.(X1, X2), .(X3, X4), .(X3, X5)) :- lessC(X3, X1). mergeA(.(X1, X2), .(X3, X4), .(X3, X5)) :- ','(lesscC(X3, X1), mergeA(.(X1, X2), X4, X5)). mergeA(.(s(0), X1), .(0, X2), .(0, X3)) :- mergeA(.(s(0), X1), X2, X3). mergeA(.(s(X1), X2), .(s(X3), X4), .(s(X3), X5)) :- lessC(X3, X1). mergeA(.(s(X1), X2), .(s(X3), X4), .(s(X3), X5)) :- ','(lesscC(X3, X1), mergeA(.(s(X1), X2), X4, X5)). Clauses: mergecA([], X1, X1). mergecA([], [], []). mergecA(X1, [], X1). mergecA(.(0, X1), .(0, X2), .(0, X3)) :- mergecA(X1, .(0, X2), X3). mergecA(.(0, X1), .(s(0), X2), .(0, X3)) :- mergecA(X1, .(s(0), X2), X3). mergecA(.(s(X1), X2), .(s(X3), X4), .(s(X1), X5)) :- ','(leqcB(X1, X3), mergecA(X2, .(s(X3), X4), X5)). mergecA(.(X1, X2), .(X3, X4), .(X3, X5)) :- ','(lesscC(X3, X1), mergecA(.(X1, X2), X4, X5)). mergecA(.(s(0), X1), .(0, X2), .(0, X3)) :- mergecA(.(s(0), X1), X2, X3). mergecA(.(s(X1), X2), .(s(X3), X4), .(s(X3), X5)) :- ','(lesscC(X3, X1), mergecA(.(s(X1), X2), X4, X5)). leqcB(0, 0). leqcB(0, s(0)). leqcB(s(X1), s(X2)) :- leqcB(X1, X2). lesscC(0, s(0)). lesscC(s(X1), s(X2)) :- lesscC(X1, X2). Afs: mergeA(x1, x2, x3) = mergeA(x1, x2) ---------------------------------------- (3) TriplesToPiDPProof (SOUND) We use the technique of [DT09]. With regard to the inferred argument filtering the predicates were used in the following modes: mergeA_in_3: (b,b,f) leqB_in_2: (b,b) leqcB_in_2: (b,b) lessC_in_2: (b,b) lesscC_in_2: (b,b) Transforming TRIPLES into the following Term Rewriting System: Pi DP problem: The TRS P consists of the following rules: MERGEA_IN_GGA(.(0, X1), .(0, X2), .(0, X3)) -> U3_GGA(X1, X2, X3, mergeA_in_gga(X1, .(0, X2), X3)) MERGEA_IN_GGA(.(0, X1), .(0, X2), .(0, X3)) -> MERGEA_IN_GGA(X1, .(0, X2), X3) MERGEA_IN_GGA(.(0, X1), .(s(0), X2), .(0, X3)) -> U4_GGA(X1, X2, X3, mergeA_in_gga(X1, .(s(0), X2), X3)) MERGEA_IN_GGA(.(0, X1), .(s(0), X2), .(0, X3)) -> MERGEA_IN_GGA(X1, .(s(0), X2), X3) MERGEA_IN_GGA(.(s(X1), X2), .(s(X3), X4), .(s(X1), X5)) -> U5_GGA(X1, X2, X3, X4, X5, leqB_in_gg(X1, X3)) MERGEA_IN_GGA(.(s(X1), X2), .(s(X3), X4), .(s(X1), X5)) -> LEQB_IN_GG(X1, X3) LEQB_IN_GG(s(X1), s(X2)) -> U1_GG(X1, X2, leqB_in_gg(X1, X2)) LEQB_IN_GG(s(X1), s(X2)) -> LEQB_IN_GG(X1, X2) MERGEA_IN_GGA(.(s(X1), X2), .(s(X3), X4), .(s(X1), X5)) -> U6_GGA(X1, X2, X3, X4, X5, leqcB_in_gg(X1, X3)) U6_GGA(X1, X2, X3, X4, X5, leqcB_out_gg(X1, X3)) -> U7_GGA(X1, X2, X3, X4, X5, mergeA_in_gga(X2, .(s(X3), X4), X5)) U6_GGA(X1, X2, X3, X4, X5, leqcB_out_gg(X1, X3)) -> MERGEA_IN_GGA(X2, .(s(X3), X4), X5) MERGEA_IN_GGA(.(X1, X2), .(X3, X4), .(X3, X5)) -> U8_GGA(X1, X2, X3, X4, X5, lessC_in_gg(X3, X1)) MERGEA_IN_GGA(.(X1, X2), .(X3, X4), .(X3, X5)) -> LESSC_IN_GG(X3, X1) LESSC_IN_GG(s(X1), s(X2)) -> U2_GG(X1, X2, lessC_in_gg(X1, X2)) LESSC_IN_GG(s(X1), s(X2)) -> LESSC_IN_GG(X1, X2) MERGEA_IN_GGA(.(X1, X2), .(X3, X4), .(X3, X5)) -> U9_GGA(X1, X2, X3, X4, X5, lesscC_in_gg(X3, X1)) U9_GGA(X1, X2, X3, X4, X5, lesscC_out_gg(X3, X1)) -> U10_GGA(X1, X2, X3, X4, X5, mergeA_in_gga(.(X1, X2), X4, X5)) U9_GGA(X1, X2, X3, X4, X5, lesscC_out_gg(X3, X1)) -> MERGEA_IN_GGA(.(X1, X2), X4, X5) MERGEA_IN_GGA(.(s(0), X1), .(0, X2), .(0, X3)) -> U11_GGA(X1, X2, X3, mergeA_in_gga(.(s(0), X1), X2, X3)) MERGEA_IN_GGA(.(s(0), X1), .(0, X2), .(0, X3)) -> MERGEA_IN_GGA(.(s(0), X1), X2, X3) MERGEA_IN_GGA(.(s(X1), X2), .(s(X3), X4), .(s(X3), X5)) -> U12_GGA(X1, X2, X3, X4, X5, lessC_in_gg(X3, X1)) MERGEA_IN_GGA(.(s(X1), X2), .(s(X3), X4), .(s(X3), X5)) -> LESSC_IN_GG(X3, X1) MERGEA_IN_GGA(.(s(X1), X2), .(s(X3), X4), .(s(X3), X5)) -> U13_GGA(X1, X2, X3, X4, X5, lesscC_in_gg(X3, X1)) U13_GGA(X1, X2, X3, X4, X5, lesscC_out_gg(X3, X1)) -> U14_GGA(X1, X2, X3, X4, X5, mergeA_in_gga(.(s(X1), X2), X4, X5)) U13_GGA(X1, X2, X3, X4, X5, lesscC_out_gg(X3, X1)) -> MERGEA_IN_GGA(.(s(X1), X2), X4, X5) The TRS R consists of the following rules: leqcB_in_gg(0, 0) -> leqcB_out_gg(0, 0) leqcB_in_gg(0, s(0)) -> leqcB_out_gg(0, s(0)) leqcB_in_gg(s(X1), s(X2)) -> U25_gg(X1, X2, leqcB_in_gg(X1, X2)) U25_gg(X1, X2, leqcB_out_gg(X1, X2)) -> leqcB_out_gg(s(X1), s(X2)) lesscC_in_gg(0, s(0)) -> lesscC_out_gg(0, s(0)) lesscC_in_gg(s(X1), s(X2)) -> U26_gg(X1, X2, lesscC_in_gg(X1, X2)) U26_gg(X1, X2, lesscC_out_gg(X1, X2)) -> lesscC_out_gg(s(X1), s(X2)) The argument filtering Pi contains the following mapping: mergeA_in_gga(x1, x2, x3) = mergeA_in_gga(x1, x2) .(x1, x2) = .(x1, x2) 0 = 0 s(x1) = s(x1) leqB_in_gg(x1, x2) = leqB_in_gg(x1, x2) leqcB_in_gg(x1, x2) = leqcB_in_gg(x1, x2) leqcB_out_gg(x1, x2) = leqcB_out_gg(x1, x2) U25_gg(x1, x2, x3) = U25_gg(x1, x2, x3) lessC_in_gg(x1, x2) = lessC_in_gg(x1, x2) lesscC_in_gg(x1, x2) = lesscC_in_gg(x1, x2) lesscC_out_gg(x1, x2) = lesscC_out_gg(x1, x2) U26_gg(x1, x2, x3) = U26_gg(x1, x2, x3) MERGEA_IN_GGA(x1, x2, x3) = MERGEA_IN_GGA(x1, x2) U3_GGA(x1, x2, x3, x4) = U3_GGA(x1, x2, x4) U4_GGA(x1, x2, x3, x4) = U4_GGA(x1, x2, x4) U5_GGA(x1, x2, x3, x4, x5, x6) = U5_GGA(x1, x2, x3, x4, x6) LEQB_IN_GG(x1, x2) = LEQB_IN_GG(x1, x2) U1_GG(x1, x2, x3) = U1_GG(x1, x2, x3) U6_GGA(x1, x2, x3, x4, x5, x6) = U6_GGA(x1, x2, x3, x4, x6) U7_GGA(x1, x2, x3, x4, x5, x6) = U7_GGA(x1, x2, x3, x4, x6) U8_GGA(x1, x2, x3, x4, x5, x6) = U8_GGA(x1, x2, x3, x4, x6) LESSC_IN_GG(x1, x2) = LESSC_IN_GG(x1, x2) U2_GG(x1, x2, x3) = U2_GG(x1, x2, x3) U9_GGA(x1, x2, x3, x4, x5, x6) = U9_GGA(x1, x2, x3, x4, x6) U10_GGA(x1, x2, x3, x4, x5, x6) = U10_GGA(x1, x2, x3, x4, x6) U11_GGA(x1, x2, x3, x4) = U11_GGA(x1, x2, x4) U12_GGA(x1, x2, x3, x4, x5, x6) = U12_GGA(x1, x2, x3, x4, x6) U13_GGA(x1, x2, x3, x4, x5, x6) = U13_GGA(x1, x2, x3, x4, x6) U14_GGA(x1, x2, x3, x4, x5, x6) = U14_GGA(x1, x2, x3, x4, x6) We have to consider all (P,R,Pi)-chains Infinitary Constructor Rewriting Termination of PiDP implies Termination of TRIPLES ---------------------------------------- (4) Obligation: Pi DP problem: The TRS P consists of the following rules: MERGEA_IN_GGA(.(0, X1), .(0, X2), .(0, X3)) -> U3_GGA(X1, X2, X3, mergeA_in_gga(X1, .(0, X2), X3)) MERGEA_IN_GGA(.(0, X1), .(0, X2), .(0, X3)) -> MERGEA_IN_GGA(X1, .(0, X2), X3) MERGEA_IN_GGA(.(0, X1), .(s(0), X2), .(0, X3)) -> U4_GGA(X1, X2, X3, mergeA_in_gga(X1, .(s(0), X2), X3)) MERGEA_IN_GGA(.(0, X1), .(s(0), X2), .(0, X3)) -> MERGEA_IN_GGA(X1, .(s(0), X2), X3) MERGEA_IN_GGA(.(s(X1), X2), .(s(X3), X4), .(s(X1), X5)) -> U5_GGA(X1, X2, X3, X4, X5, leqB_in_gg(X1, X3)) MERGEA_IN_GGA(.(s(X1), X2), .(s(X3), X4), .(s(X1), X5)) -> LEQB_IN_GG(X1, X3) LEQB_IN_GG(s(X1), s(X2)) -> U1_GG(X1, X2, leqB_in_gg(X1, X2)) LEQB_IN_GG(s(X1), s(X2)) -> LEQB_IN_GG(X1, X2) MERGEA_IN_GGA(.(s(X1), X2), .(s(X3), X4), .(s(X1), X5)) -> U6_GGA(X1, X2, X3, X4, X5, leqcB_in_gg(X1, X3)) U6_GGA(X1, X2, X3, X4, X5, leqcB_out_gg(X1, X3)) -> U7_GGA(X1, X2, X3, X4, X5, mergeA_in_gga(X2, .(s(X3), X4), X5)) U6_GGA(X1, X2, X3, X4, X5, leqcB_out_gg(X1, X3)) -> MERGEA_IN_GGA(X2, .(s(X3), X4), X5) MERGEA_IN_GGA(.(X1, X2), .(X3, X4), .(X3, X5)) -> U8_GGA(X1, X2, X3, X4, X5, lessC_in_gg(X3, X1)) MERGEA_IN_GGA(.(X1, X2), .(X3, X4), .(X3, X5)) -> LESSC_IN_GG(X3, X1) LESSC_IN_GG(s(X1), s(X2)) -> U2_GG(X1, X2, lessC_in_gg(X1, X2)) LESSC_IN_GG(s(X1), s(X2)) -> LESSC_IN_GG(X1, X2) MERGEA_IN_GGA(.(X1, X2), .(X3, X4), .(X3, X5)) -> U9_GGA(X1, X2, X3, X4, X5, lesscC_in_gg(X3, X1)) U9_GGA(X1, X2, X3, X4, X5, lesscC_out_gg(X3, X1)) -> U10_GGA(X1, X2, X3, X4, X5, mergeA_in_gga(.(X1, X2), X4, X5)) U9_GGA(X1, X2, X3, X4, X5, lesscC_out_gg(X3, X1)) -> MERGEA_IN_GGA(.(X1, X2), X4, X5) MERGEA_IN_GGA(.(s(0), X1), .(0, X2), .(0, X3)) -> U11_GGA(X1, X2, X3, mergeA_in_gga(.(s(0), X1), X2, X3)) MERGEA_IN_GGA(.(s(0), X1), .(0, X2), .(0, X3)) -> MERGEA_IN_GGA(.(s(0), X1), X2, X3) MERGEA_IN_GGA(.(s(X1), X2), .(s(X3), X4), .(s(X3), X5)) -> U12_GGA(X1, X2, X3, X4, X5, lessC_in_gg(X3, X1)) MERGEA_IN_GGA(.(s(X1), X2), .(s(X3), X4), .(s(X3), X5)) -> LESSC_IN_GG(X3, X1) MERGEA_IN_GGA(.(s(X1), X2), .(s(X3), X4), .(s(X3), X5)) -> U13_GGA(X1, X2, X3, X4, X5, lesscC_in_gg(X3, X1)) U13_GGA(X1, X2, X3, X4, X5, lesscC_out_gg(X3, X1)) -> U14_GGA(X1, X2, X3, X4, X5, mergeA_in_gga(.(s(X1), X2), X4, X5)) U13_GGA(X1, X2, X3, X4, X5, lesscC_out_gg(X3, X1)) -> MERGEA_IN_GGA(.(s(X1), X2), X4, X5) The TRS R consists of the following rules: leqcB_in_gg(0, 0) -> leqcB_out_gg(0, 0) leqcB_in_gg(0, s(0)) -> leqcB_out_gg(0, s(0)) leqcB_in_gg(s(X1), s(X2)) -> U25_gg(X1, X2, leqcB_in_gg(X1, X2)) U25_gg(X1, X2, leqcB_out_gg(X1, X2)) -> leqcB_out_gg(s(X1), s(X2)) lesscC_in_gg(0, s(0)) -> lesscC_out_gg(0, s(0)) lesscC_in_gg(s(X1), s(X2)) -> U26_gg(X1, X2, lesscC_in_gg(X1, X2)) U26_gg(X1, X2, lesscC_out_gg(X1, X2)) -> lesscC_out_gg(s(X1), s(X2)) The argument filtering Pi contains the following mapping: mergeA_in_gga(x1, x2, x3) = mergeA_in_gga(x1, x2) .(x1, x2) = .(x1, x2) 0 = 0 s(x1) = s(x1) leqB_in_gg(x1, x2) = leqB_in_gg(x1, x2) leqcB_in_gg(x1, x2) = leqcB_in_gg(x1, x2) leqcB_out_gg(x1, x2) = leqcB_out_gg(x1, x2) U25_gg(x1, x2, x3) = U25_gg(x1, x2, x3) lessC_in_gg(x1, x2) = lessC_in_gg(x1, x2) lesscC_in_gg(x1, x2) = lesscC_in_gg(x1, x2) lesscC_out_gg(x1, x2) = lesscC_out_gg(x1, x2) U26_gg(x1, x2, x3) = U26_gg(x1, x2, x3) MERGEA_IN_GGA(x1, x2, x3) = MERGEA_IN_GGA(x1, x2) U3_GGA(x1, x2, x3, x4) = U3_GGA(x1, x2, x4) U4_GGA(x1, x2, x3, x4) = U4_GGA(x1, x2, x4) U5_GGA(x1, x2, x3, x4, x5, x6) = U5_GGA(x1, x2, x3, x4, x6) LEQB_IN_GG(x1, x2) = LEQB_IN_GG(x1, x2) U1_GG(x1, x2, x3) = U1_GG(x1, x2, x3) U6_GGA(x1, x2, x3, x4, x5, x6) = U6_GGA(x1, x2, x3, x4, x6) U7_GGA(x1, x2, x3, x4, x5, x6) = U7_GGA(x1, x2, x3, x4, x6) U8_GGA(x1, x2, x3, x4, x5, x6) = U8_GGA(x1, x2, x3, x4, x6) LESSC_IN_GG(x1, x2) = LESSC_IN_GG(x1, x2) U2_GG(x1, x2, x3) = U2_GG(x1, x2, x3) U9_GGA(x1, x2, x3, x4, x5, x6) = U9_GGA(x1, x2, x3, x4, x6) U10_GGA(x1, x2, x3, x4, x5, x6) = U10_GGA(x1, x2, x3, x4, x6) U11_GGA(x1, x2, x3, x4) = U11_GGA(x1, x2, x4) U12_GGA(x1, x2, x3, x4, x5, x6) = U12_GGA(x1, x2, x3, x4, x6) U13_GGA(x1, x2, x3, x4, x5, x6) = U13_GGA(x1, x2, x3, x4, x6) U14_GGA(x1, x2, x3, x4, x5, x6) = U14_GGA(x1, x2, x3, x4, x6) We have to consider all (P,R,Pi)-chains ---------------------------------------- (5) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LOPSTR] contains 3 SCCs with 14 less nodes. ---------------------------------------- (6) Complex Obligation (AND) ---------------------------------------- (7) Obligation: Pi DP problem: The TRS P consists of the following rules: LESSC_IN_GG(s(X1), s(X2)) -> LESSC_IN_GG(X1, X2) The TRS R consists of the following rules: leqcB_in_gg(0, 0) -> leqcB_out_gg(0, 0) leqcB_in_gg(0, s(0)) -> leqcB_out_gg(0, s(0)) leqcB_in_gg(s(X1), s(X2)) -> U25_gg(X1, X2, leqcB_in_gg(X1, X2)) U25_gg(X1, X2, leqcB_out_gg(X1, X2)) -> leqcB_out_gg(s(X1), s(X2)) lesscC_in_gg(0, s(0)) -> lesscC_out_gg(0, s(0)) lesscC_in_gg(s(X1), s(X2)) -> U26_gg(X1, X2, lesscC_in_gg(X1, X2)) U26_gg(X1, X2, lesscC_out_gg(X1, X2)) -> lesscC_out_gg(s(X1), s(X2)) Pi is empty. We have to consider all (P,R,Pi)-chains ---------------------------------------- (8) UsableRulesProof (EQUIVALENT) For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. ---------------------------------------- (9) Obligation: Pi DP problem: The TRS P consists of the following rules: LESSC_IN_GG(s(X1), s(X2)) -> LESSC_IN_GG(X1, X2) R is empty. Pi is empty. We have to consider all (P,R,Pi)-chains ---------------------------------------- (10) PiDPToQDPProof (EQUIVALENT) Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. ---------------------------------------- (11) Obligation: Q DP problem: The TRS P consists of the following rules: LESSC_IN_GG(s(X1), s(X2)) -> LESSC_IN_GG(X1, X2) R is empty. Q is empty. We have to consider all (P,Q,R)-chains. ---------------------------------------- (12) QDPSizeChangeProof (EQUIVALENT) By using the subterm criterion [SUBTERM_CRITERION] together with the size-change analysis [AAECC05] we have proven that there are no infinite chains for this DP problem. From the DPs we obtained the following set of size-change graphs: *LESSC_IN_GG(s(X1), s(X2)) -> LESSC_IN_GG(X1, X2) The graph contains the following edges 1 > 1, 2 > 2 ---------------------------------------- (13) YES ---------------------------------------- (14) Obligation: Pi DP problem: The TRS P consists of the following rules: LEQB_IN_GG(s(X1), s(X2)) -> LEQB_IN_GG(X1, X2) The TRS R consists of the following rules: leqcB_in_gg(0, 0) -> leqcB_out_gg(0, 0) leqcB_in_gg(0, s(0)) -> leqcB_out_gg(0, s(0)) leqcB_in_gg(s(X1), s(X2)) -> U25_gg(X1, X2, leqcB_in_gg(X1, X2)) U25_gg(X1, X2, leqcB_out_gg(X1, X2)) -> leqcB_out_gg(s(X1), s(X2)) lesscC_in_gg(0, s(0)) -> lesscC_out_gg(0, s(0)) lesscC_in_gg(s(X1), s(X2)) -> U26_gg(X1, X2, lesscC_in_gg(X1, X2)) U26_gg(X1, X2, lesscC_out_gg(X1, X2)) -> lesscC_out_gg(s(X1), s(X2)) Pi is empty. We have to consider all (P,R,Pi)-chains ---------------------------------------- (15) UsableRulesProof (EQUIVALENT) For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. ---------------------------------------- (16) Obligation: Pi DP problem: The TRS P consists of the following rules: LEQB_IN_GG(s(X1), s(X2)) -> LEQB_IN_GG(X1, X2) R is empty. Pi is empty. We have to consider all (P,R,Pi)-chains ---------------------------------------- (17) PiDPToQDPProof (EQUIVALENT) Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. ---------------------------------------- (18) Obligation: Q DP problem: The TRS P consists of the following rules: LEQB_IN_GG(s(X1), s(X2)) -> LEQB_IN_GG(X1, X2) R is empty. Q is empty. We have to consider all (P,Q,R)-chains. ---------------------------------------- (19) QDPSizeChangeProof (EQUIVALENT) By using the subterm criterion [SUBTERM_CRITERION] together with the size-change analysis [AAECC05] we have proven that there are no infinite chains for this DP problem. From the DPs we obtained the following set of size-change graphs: *LEQB_IN_GG(s(X1), s(X2)) -> LEQB_IN_GG(X1, X2) The graph contains the following edges 1 > 1, 2 > 2 ---------------------------------------- (20) YES ---------------------------------------- (21) Obligation: Pi DP problem: The TRS P consists of the following rules: MERGEA_IN_GGA(.(X1, X2), .(X3, X4), .(X3, X5)) -> U9_GGA(X1, X2, X3, X4, X5, lesscC_in_gg(X3, X1)) U9_GGA(X1, X2, X3, X4, X5, lesscC_out_gg(X3, X1)) -> MERGEA_IN_GGA(.(X1, X2), X4, X5) MERGEA_IN_GGA(.(0, X1), .(0, X2), .(0, X3)) -> MERGEA_IN_GGA(X1, .(0, X2), X3) MERGEA_IN_GGA(.(s(0), X1), .(0, X2), .(0, X3)) -> MERGEA_IN_GGA(.(s(0), X1), X2, X3) MERGEA_IN_GGA(.(s(X1), X2), .(s(X3), X4), .(s(X1), X5)) -> U6_GGA(X1, X2, X3, X4, X5, leqcB_in_gg(X1, X3)) U6_GGA(X1, X2, X3, X4, X5, leqcB_out_gg(X1, X3)) -> MERGEA_IN_GGA(X2, .(s(X3), X4), X5) MERGEA_IN_GGA(.(0, X1), .(s(0), X2), .(0, X3)) -> MERGEA_IN_GGA(X1, .(s(0), X2), X3) MERGEA_IN_GGA(.(s(X1), X2), .(s(X3), X4), .(s(X3), X5)) -> U13_GGA(X1, X2, X3, X4, X5, lesscC_in_gg(X3, X1)) U13_GGA(X1, X2, X3, X4, X5, lesscC_out_gg(X3, X1)) -> MERGEA_IN_GGA(.(s(X1), X2), X4, X5) The TRS R consists of the following rules: leqcB_in_gg(0, 0) -> leqcB_out_gg(0, 0) leqcB_in_gg(0, s(0)) -> leqcB_out_gg(0, s(0)) leqcB_in_gg(s(X1), s(X2)) -> U25_gg(X1, X2, leqcB_in_gg(X1, X2)) U25_gg(X1, X2, leqcB_out_gg(X1, X2)) -> leqcB_out_gg(s(X1), s(X2)) lesscC_in_gg(0, s(0)) -> lesscC_out_gg(0, s(0)) lesscC_in_gg(s(X1), s(X2)) -> U26_gg(X1, X2, lesscC_in_gg(X1, X2)) U26_gg(X1, X2, lesscC_out_gg(X1, X2)) -> lesscC_out_gg(s(X1), s(X2)) The argument filtering Pi contains the following mapping: .(x1, x2) = .(x1, x2) 0 = 0 s(x1) = s(x1) leqcB_in_gg(x1, x2) = leqcB_in_gg(x1, x2) leqcB_out_gg(x1, x2) = leqcB_out_gg(x1, x2) U25_gg(x1, x2, x3) = U25_gg(x1, x2, x3) lesscC_in_gg(x1, x2) = lesscC_in_gg(x1, x2) lesscC_out_gg(x1, x2) = lesscC_out_gg(x1, x2) U26_gg(x1, x2, x3) = U26_gg(x1, x2, x3) MERGEA_IN_GGA(x1, x2, x3) = MERGEA_IN_GGA(x1, x2) U6_GGA(x1, x2, x3, x4, x5, x6) = U6_GGA(x1, x2, x3, x4, x6) U9_GGA(x1, x2, x3, x4, x5, x6) = U9_GGA(x1, x2, x3, x4, x6) U13_GGA(x1, x2, x3, x4, x5, x6) = U13_GGA(x1, x2, x3, x4, x6) We have to consider all (P,R,Pi)-chains ---------------------------------------- (22) PiDPToQDPProof (SOUND) Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. ---------------------------------------- (23) Obligation: Q DP problem: The TRS P consists of the following rules: MERGEA_IN_GGA(.(X1, X2), .(X3, X4)) -> U9_GGA(X1, X2, X3, X4, lesscC_in_gg(X3, X1)) U9_GGA(X1, X2, X3, X4, lesscC_out_gg(X3, X1)) -> MERGEA_IN_GGA(.(X1, X2), X4) MERGEA_IN_GGA(.(0, X1), .(0, X2)) -> MERGEA_IN_GGA(X1, .(0, X2)) MERGEA_IN_GGA(.(s(0), X1), .(0, X2)) -> MERGEA_IN_GGA(.(s(0), X1), X2) MERGEA_IN_GGA(.(s(X1), X2), .(s(X3), X4)) -> U6_GGA(X1, X2, X3, X4, leqcB_in_gg(X1, X3)) U6_GGA(X1, X2, X3, X4, leqcB_out_gg(X1, X3)) -> MERGEA_IN_GGA(X2, .(s(X3), X4)) MERGEA_IN_GGA(.(0, X1), .(s(0), X2)) -> MERGEA_IN_GGA(X1, .(s(0), X2)) MERGEA_IN_GGA(.(s(X1), X2), .(s(X3), X4)) -> U13_GGA(X1, X2, X3, X4, lesscC_in_gg(X3, X1)) U13_GGA(X1, X2, X3, X4, lesscC_out_gg(X3, X1)) -> MERGEA_IN_GGA(.(s(X1), X2), X4) The TRS R consists of the following rules: leqcB_in_gg(0, 0) -> leqcB_out_gg(0, 0) leqcB_in_gg(0, s(0)) -> leqcB_out_gg(0, s(0)) leqcB_in_gg(s(X1), s(X2)) -> U25_gg(X1, X2, leqcB_in_gg(X1, X2)) U25_gg(X1, X2, leqcB_out_gg(X1, X2)) -> leqcB_out_gg(s(X1), s(X2)) lesscC_in_gg(0, s(0)) -> lesscC_out_gg(0, s(0)) lesscC_in_gg(s(X1), s(X2)) -> U26_gg(X1, X2, lesscC_in_gg(X1, X2)) U26_gg(X1, X2, lesscC_out_gg(X1, X2)) -> lesscC_out_gg(s(X1), s(X2)) The set Q consists of the following terms: leqcB_in_gg(x0, x1) U25_gg(x0, x1, x2) lesscC_in_gg(x0, x1) U26_gg(x0, x1, x2) We have to consider all (P,Q,R)-chains. ---------------------------------------- (24) MRRProof (EQUIVALENT) By using the rule removal processor [LPAR04] with the following ordering, at least one Dependency Pair or term rewrite system rule of this QDP problem can be strictly oriented. Strictly oriented dependency pairs: MERGEA_IN_GGA(.(0, X1), .(0, X2)) -> MERGEA_IN_GGA(X1, .(0, X2)) MERGEA_IN_GGA(.(s(0), X1), .(0, X2)) -> MERGEA_IN_GGA(.(s(0), X1), X2) U6_GGA(X1, X2, X3, X4, leqcB_out_gg(X1, X3)) -> MERGEA_IN_GGA(X2, .(s(X3), X4)) MERGEA_IN_GGA(.(0, X1), .(s(0), X2)) -> MERGEA_IN_GGA(X1, .(s(0), X2)) Strictly oriented rules of the TRS R: leqcB_in_gg(0, 0) -> leqcB_out_gg(0, 0) leqcB_in_gg(0, s(0)) -> leqcB_out_gg(0, s(0)) Used ordering: Polynomial interpretation [POLO]: POL(.(x_1, x_2)) = x_1 + x_2 POL(0) = 2 POL(MERGEA_IN_GGA(x_1, x_2)) = 2*x_1 + 2*x_2 POL(U13_GGA(x_1, x_2, x_3, x_4, x_5)) = 2*x_1 + 2*x_2 + 2*x_3 + 2*x_4 + 2*x_5 POL(U25_gg(x_1, x_2, x_3)) = x_1 + 2*x_2 + x_3 POL(U26_gg(x_1, x_2, x_3)) = x_1 + x_2 + x_3 POL(U6_GGA(x_1, x_2, x_3, x_4, x_5)) = x_1 + 2*x_2 + 2*x_3 + 2*x_4 + x_5 POL(U9_GGA(x_1, x_2, x_3, x_4, x_5)) = x_1 + 2*x_2 + x_3 + 2*x_4 + x_5 POL(leqcB_in_gg(x_1, x_2)) = 2*x_1 + 2*x_2 POL(leqcB_out_gg(x_1, x_2)) = 1 + x_1 + 2*x_2 POL(lesscC_in_gg(x_1, x_2)) = x_1 + x_2 POL(lesscC_out_gg(x_1, x_2)) = x_1 + x_2 POL(s(x_1)) = 2*x_1 ---------------------------------------- (25) Obligation: Q DP problem: The TRS P consists of the following rules: MERGEA_IN_GGA(.(X1, X2), .(X3, X4)) -> U9_GGA(X1, X2, X3, X4, lesscC_in_gg(X3, X1)) U9_GGA(X1, X2, X3, X4, lesscC_out_gg(X3, X1)) -> MERGEA_IN_GGA(.(X1, X2), X4) MERGEA_IN_GGA(.(s(X1), X2), .(s(X3), X4)) -> U6_GGA(X1, X2, X3, X4, leqcB_in_gg(X1, X3)) MERGEA_IN_GGA(.(s(X1), X2), .(s(X3), X4)) -> U13_GGA(X1, X2, X3, X4, lesscC_in_gg(X3, X1)) U13_GGA(X1, X2, X3, X4, lesscC_out_gg(X3, X1)) -> MERGEA_IN_GGA(.(s(X1), X2), X4) The TRS R consists of the following rules: leqcB_in_gg(s(X1), s(X2)) -> U25_gg(X1, X2, leqcB_in_gg(X1, X2)) U25_gg(X1, X2, leqcB_out_gg(X1, X2)) -> leqcB_out_gg(s(X1), s(X2)) lesscC_in_gg(0, s(0)) -> lesscC_out_gg(0, s(0)) lesscC_in_gg(s(X1), s(X2)) -> U26_gg(X1, X2, lesscC_in_gg(X1, X2)) U26_gg(X1, X2, lesscC_out_gg(X1, X2)) -> lesscC_out_gg(s(X1), s(X2)) The set Q consists of the following terms: leqcB_in_gg(x0, x1) U25_gg(x0, x1, x2) lesscC_in_gg(x0, x1) U26_gg(x0, x1, x2) We have to consider all (P,Q,R)-chains. ---------------------------------------- (26) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 1 less node. ---------------------------------------- (27) Obligation: Q DP problem: The TRS P consists of the following rules: U9_GGA(X1, X2, X3, X4, lesscC_out_gg(X3, X1)) -> MERGEA_IN_GGA(.(X1, X2), X4) MERGEA_IN_GGA(.(X1, X2), .(X3, X4)) -> U9_GGA(X1, X2, X3, X4, lesscC_in_gg(X3, X1)) MERGEA_IN_GGA(.(s(X1), X2), .(s(X3), X4)) -> U13_GGA(X1, X2, X3, X4, lesscC_in_gg(X3, X1)) U13_GGA(X1, X2, X3, X4, lesscC_out_gg(X3, X1)) -> MERGEA_IN_GGA(.(s(X1), X2), X4) The TRS R consists of the following rules: leqcB_in_gg(s(X1), s(X2)) -> U25_gg(X1, X2, leqcB_in_gg(X1, X2)) U25_gg(X1, X2, leqcB_out_gg(X1, X2)) -> leqcB_out_gg(s(X1), s(X2)) lesscC_in_gg(0, s(0)) -> lesscC_out_gg(0, s(0)) lesscC_in_gg(s(X1), s(X2)) -> U26_gg(X1, X2, lesscC_in_gg(X1, X2)) U26_gg(X1, X2, lesscC_out_gg(X1, X2)) -> lesscC_out_gg(s(X1), s(X2)) The set Q consists of the following terms: leqcB_in_gg(x0, x1) U25_gg(x0, x1, x2) lesscC_in_gg(x0, x1) U26_gg(x0, x1, x2) We have to consider all (P,Q,R)-chains. ---------------------------------------- (28) UsableRulesProof (EQUIVALENT) As all Q-normal forms are R-normal forms we are in the innermost case. Hence, by the usable rules processor [LPAR04] we can delete all non-usable rules [FROCOS05] from R. ---------------------------------------- (29) Obligation: Q DP problem: The TRS P consists of the following rules: U9_GGA(X1, X2, X3, X4, lesscC_out_gg(X3, X1)) -> MERGEA_IN_GGA(.(X1, X2), X4) MERGEA_IN_GGA(.(X1, X2), .(X3, X4)) -> U9_GGA(X1, X2, X3, X4, lesscC_in_gg(X3, X1)) MERGEA_IN_GGA(.(s(X1), X2), .(s(X3), X4)) -> U13_GGA(X1, X2, X3, X4, lesscC_in_gg(X3, X1)) U13_GGA(X1, X2, X3, X4, lesscC_out_gg(X3, X1)) -> MERGEA_IN_GGA(.(s(X1), X2), X4) The TRS R consists of the following rules: lesscC_in_gg(0, s(0)) -> lesscC_out_gg(0, s(0)) lesscC_in_gg(s(X1), s(X2)) -> U26_gg(X1, X2, lesscC_in_gg(X1, X2)) U26_gg(X1, X2, lesscC_out_gg(X1, X2)) -> lesscC_out_gg(s(X1), s(X2)) The set Q consists of the following terms: leqcB_in_gg(x0, x1) U25_gg(x0, x1, x2) lesscC_in_gg(x0, x1) U26_gg(x0, x1, x2) We have to consider all (P,Q,R)-chains. ---------------------------------------- (30) QReductionProof (EQUIVALENT) We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. leqcB_in_gg(x0, x1) U25_gg(x0, x1, x2) ---------------------------------------- (31) Obligation: Q DP problem: The TRS P consists of the following rules: U9_GGA(X1, X2, X3, X4, lesscC_out_gg(X3, X1)) -> MERGEA_IN_GGA(.(X1, X2), X4) MERGEA_IN_GGA(.(X1, X2), .(X3, X4)) -> U9_GGA(X1, X2, X3, X4, lesscC_in_gg(X3, X1)) MERGEA_IN_GGA(.(s(X1), X2), .(s(X3), X4)) -> U13_GGA(X1, X2, X3, X4, lesscC_in_gg(X3, X1)) U13_GGA(X1, X2, X3, X4, lesscC_out_gg(X3, X1)) -> MERGEA_IN_GGA(.(s(X1), X2), X4) The TRS R consists of the following rules: lesscC_in_gg(0, s(0)) -> lesscC_out_gg(0, s(0)) lesscC_in_gg(s(X1), s(X2)) -> U26_gg(X1, X2, lesscC_in_gg(X1, X2)) U26_gg(X1, X2, lesscC_out_gg(X1, X2)) -> lesscC_out_gg(s(X1), s(X2)) The set Q consists of the following terms: lesscC_in_gg(x0, x1) U26_gg(x0, x1, x2) We have to consider all (P,Q,R)-chains. ---------------------------------------- (32) 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: *MERGEA_IN_GGA(.(X1, X2), .(X3, X4)) -> U9_GGA(X1, X2, X3, X4, lesscC_in_gg(X3, X1)) The graph contains the following edges 1 > 1, 1 > 2, 2 > 3, 2 > 4 *MERGEA_IN_GGA(.(s(X1), X2), .(s(X3), X4)) -> U13_GGA(X1, X2, X3, X4, lesscC_in_gg(X3, X1)) The graph contains the following edges 1 > 1, 1 > 2, 2 > 3, 2 > 4 *U9_GGA(X1, X2, X3, X4, lesscC_out_gg(X3, X1)) -> MERGEA_IN_GGA(.(X1, X2), X4) The graph contains the following edges 4 >= 2 *U13_GGA(X1, X2, X3, X4, lesscC_out_gg(X3, X1)) -> MERGEA_IN_GGA(.(s(X1), X2), X4) The graph contains the following edges 4 >= 2 ---------------------------------------- (33) YES