/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, 70 ms] (2) TRIPLES (3) TriplesToPiDPProof [SOUND, 0 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, 42 ms] (25) QDP (26) DependencyGraphProof [EQUIVALENT, 0 ms] (27) TRUE ---------------------------------------- (0) Obligation: Clauses: merge(X, [], X). merge([], X, X). merge(.(A, X), .(B, Y), .(A, Z)) :- ','(le(A, B), merge(X, .(B, Y), Z)). merge(.(A, X), .(B, Y), .(B, Z)) :- ','(gt(A, B), merge(.(A, X), Y, Z)). gt(s(X), s(Y)) :- gt(X, Y). gt(s(X), zero). le(s(X), s(Y)) :- le(X, Y). le(zero, s(Y)). le(zero, zero). 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 (. A X) (. B Y) (. A Z))", "(',' (le A B) (merge X (. B Y) Z))" ], [ "(merge (. A X) (. B Y) (. B Z))", "(',' (gt A B) (merge (. A X) Y Z))" ], [ "(gt (s X) (s Y))", "(gt X Y)" ], [ "(gt (s X) (zero))", null ], [ "(le (s X) (s Y))", "(le X Y)" ], [ "(le (zero) (s Y))", null ], [ "(le (zero) (zero))", null ] ] }, "graph": { "nodes": { "390": { "goal": [{ "clause": 7, "scope": 3, "term": "(le T31 T32)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T31", "T32" ], "free": [], "exprvars": [] } }, "391": { "goal": [{ "clause": 8, "scope": 3, "term": "(le T31 T32)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T31", "T32" ], "free": [], "exprvars": [] } }, "type": "Nodes", "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": [] } }, "430": { "goal": [{ "clause": -1, "scope": -1, "term": "(merge (. (s T123) T110) T112 T114)" }], "kb": { "nonunifying": [[ "(merge (. (s T123) T110) (. (s T124) T112) T3)", "(merge (. X42 X43) (. X44 X45) (. X42 X46))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T110", "T112", "T123", "T124" ], "free": [ "X42", "X43", "X44", "X45", "X46" ], "exprvars": [] } }, "398": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "431": { "goal": [{ "clause": -1, "scope": -1, "term": "(merge (. (s T135) T110) T112 T114)" }], "kb": { "nonunifying": [[ "(merge (. (s T135) T110) (. (zero) T112) T3)", "(merge (. X42 X43) (. X44 X45) (. X42 X46))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T110", "T112", "T135" ], "free": [ "X42", "X43", "X44", "X45", "X46" ], "exprvars": [] } }, "355": { "goal": [ { "clause": 2, "scope": 1, "term": "(merge ([]) T11 T3)" }, { "clause": 3, "scope": 1, "term": "(merge ([]) T11 T3)" } ], "kb": { "nonunifying": [[ "(merge ([]) T11 T3)", "(merge X2 ([]) X2)" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T11"], "free": ["X2"], "exprvars": [] } }, "399": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "432": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "52": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "53": { "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": [] } }, "56": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "58": { "goal": [ { "clause": -1, "scope": -1, "term": "(true)" }, { "clause": 2, "scope": 1, "term": "(merge ([]) T11 T3)" }, { "clause": 3, "scope": 1, "term": "(merge ([]) T11 T3)" } ], "kb": { "nonunifying": [[ "(merge ([]) T11 T3)", "(merge X2 ([]) X2)" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T11"], "free": ["X2"], "exprvars": [] } }, "360": { "goal": [{ "clause": 3, "scope": 1, "term": "(merge ([]) T11 T3)" }], "kb": { "nonunifying": [[ "(merge ([]) T11 T3)", "(merge X2 ([]) X2)" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T11"], "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": [] } }, "364": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "4": { "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": [] } }, "367": { "goal": [ { "clause": -1, "scope": -1, "term": "(',' (le 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": [] } }, "400": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "368": { "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": [] } }, "401": { "goal": [{ "clause": 7, "scope": 2, "term": "(',' (le T17 T19) (merge T18 (. T19 T20) T22))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T17", "T18", "T19", "T20" ], "free": [], "exprvars": [] } }, "369": { "goal": [ { "clause": 6, "scope": 2, "term": "(',' (le T17 T19) (merge T18 (. T19 T20) T22))" }, { "clause": 7, "scope": 2, "term": "(',' (le T17 T19) (merge T18 (. T19 T20) T22))" }, { "clause": 8, "scope": 2, "term": "(',' (le 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": [] } }, "402": { "goal": [ { "clause": 8, "scope": 2, "term": "(',' (le 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": [] } }, "403": { "goal": [{ "clause": -1, "scope": -1, "term": "(merge T18 (. (s T60) T20) T22)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T18", "T20", "T60" ], "free": [], "exprvars": [] } }, "404": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "405": { "goal": [{ "clause": 8, "scope": 2, "term": "(',' (le T17 T19) (merge T18 (. T19 T20) T22))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T17", "T18", "T19", "T20" ], "free": [], "exprvars": [] } }, "406": { "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": [] } }, "407": { "goal": [{ "clause": -1, "scope": -1, "term": "(merge T18 (. (zero) T20) T22)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T18", "T20" ], "free": [], "exprvars": [] } }, "408": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "409": { "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": [] } }, "22": { "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": [] } }, "23": { "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": [] } }, "24": { "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": [] } }, "27": { "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": [] } }, "28": { "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": [] } }, "29": { "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": [] } }, "370": { "goal": [{ "clause": 6, "scope": 2, "term": "(',' (le T17 T19) (merge T18 (. T19 T20) T22))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T17", "T18", "T19", "T20" ], "free": [], "exprvars": [] } }, "371": { "goal": [ { "clause": 7, "scope": 2, "term": "(',' (le T17 T19) (merge T18 (. T19 T20) T22))" }, { "clause": 8, "scope": 2, "term": "(',' (le 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": "(',' (le T31 T32) (merge T18 (. (s T32) T20) T22))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T18", "T20", "T31", "T32" ], "free": [], "exprvars": [] } }, "375": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "410": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (gt T75 T77) (merge (. T75 T76) T78 T80))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T75", "T76", "T77", "T78" ], "free": [], "exprvars": [] } }, "378": { "goal": [{ "clause": -1, "scope": -1, "term": "(le T31 T32)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T31", "T32" ], "free": [], "exprvars": [] } }, "411": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "379": { "goal": [{ "clause": -1, "scope": -1, "term": "(merge T18 (. (s T32) T20) T22)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T18", "T20", "T32" ], "free": [], "exprvars": [] } }, "412": { "goal": [{ "clause": -1, "scope": -1, "term": "(gt T75 T77)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T75", "T77" ], "free": [], "exprvars": [] } }, "413": { "goal": [{ "clause": -1, "scope": -1, "term": "(merge (. T75 T76) T78 T80)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T75", "T76", "T78" ], "free": [], "exprvars": [] } }, "414": { "goal": [ { "clause": 4, "scope": 4, "term": "(gt T75 T77)" }, { "clause": 5, "scope": 4, "term": "(gt T75 T77)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T75", "T77" ], "free": [], "exprvars": [] } }, "415": { "goal": [{ "clause": 4, "scope": 4, "term": "(gt T75 T77)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T75", "T77" ], "free": [], "exprvars": [] } }, "416": { "goal": [{ "clause": 5, "scope": 4, "term": "(gt T75 T77)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T75", "T77" ], "free": [], "exprvars": [] } }, "417": { "goal": [{ "clause": -1, "scope": -1, "term": "(gt T93 T94)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T93", "T94" ], "free": [], "exprvars": [] } }, "418": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "419": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "32": { "goal": [{ "clause": 3, "scope": 1, "term": "(merge ([]) ([]) T3)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "381": { "goal": [ { "clause": 6, "scope": 3, "term": "(le T31 T32)" }, { "clause": 7, "scope": 3, "term": "(le T31 T32)" }, { "clause": 8, "scope": 3, "term": "(le T31 T32)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T31", "T32" ], "free": [], "exprvars": [] } }, "384": { "goal": [{ "clause": 6, "scope": 3, "term": "(le T31 T32)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T31", "T32" ], "free": [], "exprvars": [] } }, "385": { "goal": [ { "clause": 7, "scope": 3, "term": "(le T31 T32)" }, { "clause": 8, "scope": 3, "term": "(le T31 T32)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T31", "T32" ], "free": [], "exprvars": [] } }, "420": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "388": { "goal": [{ "clause": -1, "scope": -1, "term": "(le T45 T46)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T45", "T46" ], "free": [], "exprvars": [] } }, "421": { "goal": [], "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": -1, "scope": -1, "term": "(',' (gt T109 T111) (merge (. T109 T110) T112 T114))" }], "kb": { "nonunifying": [[ "(merge (. T109 T110) (. T111 T112) T3)", "(merge (. X42 X43) (. X44 X45) (. X42 X46))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T109", "T110", "T111", "T112" ], "free": [ "X42", "X43", "X44", "X45", "X46" ], "exprvars": [] } }, "423": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "424": { "goal": [ { "clause": 4, "scope": 5, "term": "(',' (gt T109 T111) (merge (. T109 T110) T112 T114))" }, { "clause": 5, "scope": 5, "term": "(',' (gt T109 T111) (merge (. T109 T110) T112 T114))" } ], "kb": { "nonunifying": [[ "(merge (. T109 T110) (. T111 T112) T3)", "(merge (. X42 X43) (. X44 X45) (. X42 X46))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T109", "T110", "T111", "T112" ], "free": [ "X42", "X43", "X44", "X45", "X46" ], "exprvars": [] } }, "425": { "goal": [{ "clause": 4, "scope": 5, "term": "(',' (gt T109 T111) (merge (. T109 T110) T112 T114))" }], "kb": { "nonunifying": [[ "(merge (. T109 T110) (. T111 T112) T3)", "(merge (. X42 X43) (. X44 X45) (. X42 X46))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T109", "T110", "T111", "T112" ], "free": [ "X42", "X43", "X44", "X45", "X46" ], "exprvars": [] } }, "349": { "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": [] } }, "426": { "goal": [{ "clause": 5, "scope": 5, "term": "(',' (gt T109 T111) (merge (. T109 T110) T112 T114))" }], "kb": { "nonunifying": [[ "(merge (. T109 T110) (. T111 T112) T3)", "(merge (. X42 X43) (. X44 X45) (. X42 X46))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T109", "T110", "T111", "T112" ], "free": [ "X42", "X43", "X44", "X45", "X46" ], "exprvars": [] } }, "427": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (gt T123 T124) (merge (. (s T123) T110) T112 T114))" }], "kb": { "nonunifying": [[ "(merge (. (s T123) T110) (. (s T124) T112) T3)", "(merge (. X42 X43) (. X44 X45) (. X42 X46))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T110", "T112", "T123", "T124" ], "free": [ "X42", "X43", "X44", "X45", "X46" ], "exprvars": [] } }, "428": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "429": { "goal": [{ "clause": -1, "scope": -1, "term": "(gt T123 T124)" }], "kb": { "nonunifying": [[ "(merge (. (s T123) T110) (. (s T124) T112) T3)", "(merge (. X42 X43) (. X44 X45) (. X42 X46))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T110", "T112", "T123", "T124" ], "free": [ "X42", "X43", "X44", "X45", "X46" ], "exprvars": [] } } }, "edges": [ { "from": 1, "to": 4, "label": "CASE" }, { "from": 4, "to": 22, "label": "EVAL with clause\nmerge(X2, [], X2).\nand substitutionT1 -> T5,\nX2 -> T5,\nT2 -> [],\nT3 -> T5" }, { "from": 4, "to": 23, "label": "EVAL-BACKTRACK" }, { "from": 22, "to": 24, "label": "SUCCESS" }, { "from": 23, "to": 58, "label": "EVAL with clause\nmerge([], X26, X26).\nand substitutionT1 -> [],\nT2 -> T11,\nX26 -> T11,\nT3 -> T11" }, { "from": 23, "to": 349, "label": "EVAL-BACKTRACK" }, { "from": 24, "to": 27, "label": "EVAL with clause\nmerge([], X4, X4).\nand substitutionT5 -> [],\nX4 -> [],\nT3 -> []" }, { "from": 24, "to": 28, "label": "EVAL-BACKTRACK" }, { "from": 27, "to": 29, "label": "SUCCESS" }, { "from": 28, "to": 53, "label": "BACKTRACK\nfor clause: merge(.(A, X), .(B, Y), .(A, Z)) :- ','(le(A, B), merge(X, .(B, Y), Z))because of non-unification" }, { "from": 29, "to": 32, "label": "BACKTRACK\nfor clause: merge(.(A, X), .(B, Y), .(A, Z)) :- ','(le(A, B), merge(X, .(B, Y), Z))because of non-unification" }, { "from": 32, "to": 52, "label": "BACKTRACK\nfor clause: merge(.(A, X), .(B, Y), .(B, Z)) :- ','(gt(A, B), merge(.(A, X), Y, Z))because of non-unification" }, { "from": 53, "to": 56, "label": "BACKTRACK\nfor clause: merge(.(A, X), .(B, Y), .(B, Z)) :- ','(gt(A, B), merge(.(A, X), Y, Z))because of non-unification" }, { "from": 58, "to": 355, "label": "SUCCESS" }, { "from": 349, "to": 367, "label": "EVAL with clause\nmerge(.(X42, X43), .(X44, X45), .(X42, X46)) :- ','(le(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": 349, "to": 368, "label": "EVAL-BACKTRACK" }, { "from": 355, "to": 360, "label": "BACKTRACK\nfor clause: merge(.(A, X), .(B, Y), .(A, Z)) :- ','(le(A, B), merge(X, .(B, Y), Z))because of non-unification" }, { "from": 360, "to": 364, "label": "BACKTRACK\nfor clause: merge(.(A, X), .(B, Y), .(B, Z)) :- ','(gt(A, B), merge(.(A, X), Y, Z))because of non-unification" }, { "from": 367, "to": 369, "label": "CASE" }, { "from": 368, "to": 422, "label": "EVAL with clause\nmerge(.(X130, X131), .(X132, X133), .(X132, X134)) :- ','(gt(X130, X132), merge(.(X130, X131), X133, X134)).\nand substitutionX130 -> T109,\nX131 -> T110,\nT1 -> .(T109, T110),\nX132 -> T111,\nX133 -> T112,\nT2 -> .(T111, T112),\nX134 -> T114,\nT3 -> .(T111, T114),\nT113 -> T114" }, { "from": 368, "to": 423, "label": "EVAL-BACKTRACK" }, { "from": 369, "to": 370, "label": "PARALLEL" }, { "from": 369, "to": 371, "label": "PARALLEL" }, { "from": 370, "to": 374, "label": "EVAL with clause\nle(s(X55), s(X56)) :- le(X55, X56).\nand substitutionX55 -> T31,\nT17 -> s(T31),\nX56 -> T32,\nT19 -> s(T32)" }, { "from": 370, "to": 375, "label": "EVAL-BACKTRACK" }, { "from": 371, "to": 401, "label": "PARALLEL" }, { "from": 371, "to": 402, "label": "PARALLEL" }, { "from": 374, "to": 378, "label": "SPLIT 1" }, { "from": 374, "to": 379, "label": "SPLIT 2\nnew knowledge:\nT31 is ground\nT32 is ground" }, { "from": 378, "to": 381, "label": "CASE" }, { "from": 379, "to": 1, "label": "INSTANCE with matching:\nT1 -> T18\nT2 -> .(s(T32), T20)\nT3 -> T22" }, { "from": 381, "to": 384, "label": "PARALLEL" }, { "from": 381, "to": 385, "label": "PARALLEL" }, { "from": 384, "to": 388, "label": "EVAL with clause\nle(s(X69), s(X70)) :- le(X69, X70).\nand substitutionX69 -> T45,\nT31 -> s(T45),\nX70 -> T46,\nT32 -> s(T46)" }, { "from": 384, "to": 389, "label": "EVAL-BACKTRACK" }, { "from": 385, "to": 390, "label": "PARALLEL" }, { "from": 385, "to": 391, "label": "PARALLEL" }, { "from": 388, "to": 378, "label": "INSTANCE with matching:\nT31 -> T45\nT32 -> T46" }, { "from": 390, "to": 395, "label": "EVAL with clause\nle(zero, s(X77)).\nand substitutionT31 -> zero,\nX77 -> T53,\nT32 -> s(T53)" }, { "from": 390, "to": 396, "label": "EVAL-BACKTRACK" }, { "from": 391, "to": 398, "label": "EVAL with clause\nle(zero, zero).\nand substitutionT31 -> zero,\nT32 -> zero" }, { "from": 391, "to": 399, "label": "EVAL-BACKTRACK" }, { "from": 395, "to": 397, "label": "SUCCESS" }, { "from": 398, "to": 400, "label": "SUCCESS" }, { "from": 401, "to": 403, "label": "EVAL with clause\nle(zero, s(X84)).\nand substitutionT17 -> zero,\nX84 -> T60,\nT19 -> s(T60)" }, { "from": 401, "to": 404, "label": "EVAL-BACKTRACK" }, { "from": 402, "to": 405, "label": "PARALLEL" }, { "from": 402, "to": 406, "label": "PARALLEL" }, { "from": 403, "to": 1, "label": "INSTANCE with matching:\nT1 -> T18\nT2 -> .(s(T60), T20)\nT3 -> T22" }, { "from": 405, "to": 407, "label": "EVAL with clause\nle(zero, zero).\nand substitutionT17 -> zero,\nT19 -> zero" }, { "from": 405, "to": 408, "label": "EVAL-BACKTRACK" }, { "from": 406, "to": 409, "label": "FAILURE" }, { "from": 407, "to": 1, "label": "INSTANCE with matching:\nT1 -> T18\nT2 -> .(zero, T20)\nT3 -> T22" }, { "from": 409, "to": 410, "label": "EVAL with clause\nmerge(.(X99, X100), .(X101, X102), .(X101, X103)) :- ','(gt(X99, X101), merge(.(X99, X100), X102, X103)).\nand substitutionT17 -> T75,\nX99 -> T75,\nT18 -> T76,\nX100 -> T76,\nT19 -> T77,\nX101 -> T77,\nT20 -> T78,\nX102 -> T78,\nX103 -> T80,\nT3 -> .(T77, T80),\nT79 -> T80" }, { "from": 409, "to": 411, "label": "EVAL-BACKTRACK" }, { "from": 410, "to": 412, "label": "SPLIT 1" }, { "from": 410, "to": 413, "label": "SPLIT 2\nnew knowledge:\nT75 is ground\nT77 is ground" }, { "from": 412, "to": 414, "label": "CASE" }, { "from": 413, "to": 1, "label": "INSTANCE with matching:\nT1 -> .(T75, T76)\nT2 -> T78\nT3 -> T80" }, { "from": 414, "to": 415, "label": "PARALLEL" }, { "from": 414, "to": 416, "label": "PARALLEL" }, { "from": 415, "to": 417, "label": "EVAL with clause\ngt(s(X116), s(X117)) :- gt(X116, X117).\nand substitutionX116 -> T93,\nT75 -> s(T93),\nX117 -> T94,\nT77 -> s(T94)" }, { "from": 415, "to": 418, "label": "EVAL-BACKTRACK" }, { "from": 416, "to": 419, "label": "EVAL with clause\ngt(s(X122), zero).\nand substitutionX122 -> T99,\nT75 -> s(T99),\nT77 -> zero" }, { "from": 416, "to": 420, "label": "EVAL-BACKTRACK" }, { "from": 417, "to": 412, "label": "INSTANCE with matching:\nT75 -> T93\nT77 -> T94" }, { "from": 419, "to": 421, "label": "SUCCESS" }, { "from": 422, "to": 424, "label": "CASE" }, { "from": 424, "to": 425, "label": "PARALLEL" }, { "from": 424, "to": 426, "label": "PARALLEL" }, { "from": 425, "to": 427, "label": "EVAL with clause\ngt(s(X143), s(X144)) :- gt(X143, X144).\nand substitutionX143 -> T123,\nT109 -> s(T123),\nX144 -> T124,\nT111 -> s(T124)" }, { "from": 425, "to": 428, "label": "EVAL-BACKTRACK" }, { "from": 426, "to": 431, "label": "EVAL with clause\ngt(s(X153), zero).\nand substitutionX153 -> T135,\nT109 -> s(T135),\nT111 -> zero" }, { "from": 426, "to": 432, "label": "EVAL-BACKTRACK" }, { "from": 427, "to": 429, "label": "SPLIT 1" }, { "from": 427, "to": 430, "label": "SPLIT 2\nnew knowledge:\nT123 is ground\nT124 is ground" }, { "from": 429, "to": 412, "label": "INSTANCE with matching:\nT75 -> T123\nT77 -> T124" }, { "from": 430, "to": 1, "label": "INSTANCE with matching:\nT1 -> .(s(T123), T110)\nT2 -> T112\nT3 -> T114" }, { "from": 431, "to": 1, "label": "INSTANCE with matching:\nT1 -> .(s(T135), T110)\nT2 -> T112\nT3 -> T114" } ], "type": "Graph" } } ---------------------------------------- (2) Obligation: Triples: leB(s(X1), s(X2)) :- leB(X1, X2). gtC(s(X1), s(X2)) :- gtC(X1, X2). mergeA(.(s(X1), X2), .(s(X3), X4), .(s(X1), X5)) :- leB(X1, X3). mergeA(.(s(X1), X2), .(s(X3), X4), .(s(X1), X5)) :- ','(lecB(X1, X3), mergeA(X2, .(s(X3), X4), X5)). mergeA(.(zero, X1), .(s(X2), X3), .(zero, X4)) :- mergeA(X1, .(s(X2), X3), X4). mergeA(.(zero, X1), .(zero, X2), .(zero, X3)) :- mergeA(X1, .(zero, X2), X3). mergeA(.(X1, X2), .(X3, X4), .(X3, X5)) :- gtC(X1, X3). mergeA(.(X1, X2), .(X3, X4), .(X3, X5)) :- ','(gtcC(X1, X3), mergeA(.(X1, X2), X4, X5)). mergeA(.(s(X1), X2), .(s(X3), X4), .(s(X3), X5)) :- gtC(X1, X3). mergeA(.(s(X1), X2), .(s(X3), X4), .(s(X3), X5)) :- ','(gtcC(X1, X3), mergeA(.(s(X1), X2), X4, X5)). mergeA(.(s(X1), X2), .(zero, X3), .(zero, X4)) :- mergeA(.(s(X1), X2), X3, X4). Clauses: mergecA(X1, [], X1). mergecA([], [], []). mergecA([], X1, X1). mergecA(.(s(X1), X2), .(s(X3), X4), .(s(X1), X5)) :- ','(lecB(X1, X3), mergecA(X2, .(s(X3), X4), X5)). mergecA(.(zero, X1), .(s(X2), X3), .(zero, X4)) :- mergecA(X1, .(s(X2), X3), X4). mergecA(.(zero, X1), .(zero, X2), .(zero, X3)) :- mergecA(X1, .(zero, X2), X3). mergecA(.(X1, X2), .(X3, X4), .(X3, X5)) :- ','(gtcC(X1, X3), mergecA(.(X1, X2), X4, X5)). mergecA(.(s(X1), X2), .(s(X3), X4), .(s(X3), X5)) :- ','(gtcC(X1, X3), mergecA(.(s(X1), X2), X4, X5)). mergecA(.(s(X1), X2), .(zero, X3), .(zero, X4)) :- mergecA(.(s(X1), X2), X3, X4). lecB(s(X1), s(X2)) :- lecB(X1, X2). lecB(zero, s(X1)). lecB(zero, zero). gtcC(s(X1), s(X2)) :- gtcC(X1, X2). gtcC(s(X1), zero). 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) leB_in_2: (b,b) lecB_in_2: (b,b) gtC_in_2: (b,b) gtcC_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(.(s(X1), X2), .(s(X3), X4), .(s(X1), X5)) -> U3_GGA(X1, X2, X3, X4, X5, leB_in_gg(X1, X3)) MERGEA_IN_GGA(.(s(X1), X2), .(s(X3), X4), .(s(X1), X5)) -> LEB_IN_GG(X1, X3) LEB_IN_GG(s(X1), s(X2)) -> U1_GG(X1, X2, leB_in_gg(X1, X2)) LEB_IN_GG(s(X1), s(X2)) -> LEB_IN_GG(X1, X2) MERGEA_IN_GGA(.(s(X1), X2), .(s(X3), X4), .(s(X1), X5)) -> U4_GGA(X1, X2, X3, X4, X5, lecB_in_gg(X1, X3)) U4_GGA(X1, X2, X3, X4, X5, lecB_out_gg(X1, X3)) -> U5_GGA(X1, X2, X3, X4, X5, mergeA_in_gga(X2, .(s(X3), X4), X5)) U4_GGA(X1, X2, X3, X4, X5, lecB_out_gg(X1, X3)) -> MERGEA_IN_GGA(X2, .(s(X3), X4), X5) MERGEA_IN_GGA(.(zero, X1), .(s(X2), X3), .(zero, X4)) -> U6_GGA(X1, X2, X3, X4, mergeA_in_gga(X1, .(s(X2), X3), X4)) MERGEA_IN_GGA(.(zero, X1), .(s(X2), X3), .(zero, X4)) -> MERGEA_IN_GGA(X1, .(s(X2), X3), X4) MERGEA_IN_GGA(.(zero, X1), .(zero, X2), .(zero, X3)) -> U7_GGA(X1, X2, X3, mergeA_in_gga(X1, .(zero, X2), X3)) MERGEA_IN_GGA(.(zero, X1), .(zero, X2), .(zero, X3)) -> MERGEA_IN_GGA(X1, .(zero, X2), X3) MERGEA_IN_GGA(.(X1, X2), .(X3, X4), .(X3, X5)) -> U8_GGA(X1, X2, X3, X4, X5, gtC_in_gg(X1, X3)) MERGEA_IN_GGA(.(X1, X2), .(X3, X4), .(X3, X5)) -> GTC_IN_GG(X1, X3) GTC_IN_GG(s(X1), s(X2)) -> U2_GG(X1, X2, gtC_in_gg(X1, X2)) GTC_IN_GG(s(X1), s(X2)) -> GTC_IN_GG(X1, X2) MERGEA_IN_GGA(.(X1, X2), .(X3, X4), .(X3, X5)) -> U9_GGA(X1, X2, X3, X4, X5, gtcC_in_gg(X1, X3)) U9_GGA(X1, X2, X3, X4, X5, gtcC_out_gg(X1, X3)) -> U10_GGA(X1, X2, X3, X4, X5, mergeA_in_gga(.(X1, X2), X4, X5)) U9_GGA(X1, X2, X3, X4, X5, gtcC_out_gg(X1, X3)) -> MERGEA_IN_GGA(.(X1, X2), X4, X5) MERGEA_IN_GGA(.(s(X1), X2), .(s(X3), X4), .(s(X3), X5)) -> U11_GGA(X1, X2, X3, X4, X5, gtC_in_gg(X1, X3)) MERGEA_IN_GGA(.(s(X1), X2), .(s(X3), X4), .(s(X3), X5)) -> GTC_IN_GG(X1, X3) MERGEA_IN_GGA(.(s(X1), X2), .(s(X3), X4), .(s(X3), X5)) -> U12_GGA(X1, X2, X3, X4, X5, gtcC_in_gg(X1, X3)) U12_GGA(X1, X2, X3, X4, X5, gtcC_out_gg(X1, X3)) -> U13_GGA(X1, X2, X3, X4, X5, mergeA_in_gga(.(s(X1), X2), X4, X5)) U12_GGA(X1, X2, X3, X4, X5, gtcC_out_gg(X1, X3)) -> MERGEA_IN_GGA(.(s(X1), X2), X4, X5) MERGEA_IN_GGA(.(s(X1), X2), .(zero, X3), .(zero, X4)) -> U14_GGA(X1, X2, X3, X4, mergeA_in_gga(.(s(X1), X2), X3, X4)) MERGEA_IN_GGA(.(s(X1), X2), .(zero, X3), .(zero, X4)) -> MERGEA_IN_GGA(.(s(X1), X2), X3, X4) The TRS R consists of the following rules: lecB_in_gg(s(X1), s(X2)) -> U25_gg(X1, X2, lecB_in_gg(X1, X2)) lecB_in_gg(zero, s(X1)) -> lecB_out_gg(zero, s(X1)) lecB_in_gg(zero, zero) -> lecB_out_gg(zero, zero) U25_gg(X1, X2, lecB_out_gg(X1, X2)) -> lecB_out_gg(s(X1), s(X2)) gtcC_in_gg(s(X1), s(X2)) -> U26_gg(X1, X2, gtcC_in_gg(X1, X2)) gtcC_in_gg(s(X1), zero) -> gtcC_out_gg(s(X1), zero) U26_gg(X1, X2, gtcC_out_gg(X1, X2)) -> gtcC_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) s(x1) = s(x1) leB_in_gg(x1, x2) = leB_in_gg(x1, x2) lecB_in_gg(x1, x2) = lecB_in_gg(x1, x2) U25_gg(x1, x2, x3) = U25_gg(x1, x2, x3) zero = zero lecB_out_gg(x1, x2) = lecB_out_gg(x1, x2) gtC_in_gg(x1, x2) = gtC_in_gg(x1, x2) gtcC_in_gg(x1, x2) = gtcC_in_gg(x1, x2) U26_gg(x1, x2, x3) = U26_gg(x1, x2, x3) gtcC_out_gg(x1, x2) = gtcC_out_gg(x1, x2) MERGEA_IN_GGA(x1, x2, x3) = MERGEA_IN_GGA(x1, x2) U3_GGA(x1, x2, x3, x4, x5, x6) = U3_GGA(x1, x2, x3, x4, x6) LEB_IN_GG(x1, x2) = LEB_IN_GG(x1, x2) U1_GG(x1, x2, x3) = U1_GG(x1, x2, x3) U4_GGA(x1, x2, x3, x4, x5, x6) = U4_GGA(x1, x2, x3, x4, x6) U5_GGA(x1, x2, x3, x4, x5, x6) = U5_GGA(x1, x2, x3, x4, x6) U6_GGA(x1, x2, x3, x4, x5) = U6_GGA(x1, x2, x3, x5) U7_GGA(x1, x2, x3, x4) = U7_GGA(x1, x2, x4) U8_GGA(x1, x2, x3, x4, x5, x6) = U8_GGA(x1, x2, x3, x4, x6) GTC_IN_GG(x1, x2) = GTC_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, x5, x6) = U11_GGA(x1, x2, x3, x4, x6) 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) = U14_GGA(x1, x2, x3, x5) 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(.(s(X1), X2), .(s(X3), X4), .(s(X1), X5)) -> U3_GGA(X1, X2, X3, X4, X5, leB_in_gg(X1, X3)) MERGEA_IN_GGA(.(s(X1), X2), .(s(X3), X4), .(s(X1), X5)) -> LEB_IN_GG(X1, X3) LEB_IN_GG(s(X1), s(X2)) -> U1_GG(X1, X2, leB_in_gg(X1, X2)) LEB_IN_GG(s(X1), s(X2)) -> LEB_IN_GG(X1, X2) MERGEA_IN_GGA(.(s(X1), X2), .(s(X3), X4), .(s(X1), X5)) -> U4_GGA(X1, X2, X3, X4, X5, lecB_in_gg(X1, X3)) U4_GGA(X1, X2, X3, X4, X5, lecB_out_gg(X1, X3)) -> U5_GGA(X1, X2, X3, X4, X5, mergeA_in_gga(X2, .(s(X3), X4), X5)) U4_GGA(X1, X2, X3, X4, X5, lecB_out_gg(X1, X3)) -> MERGEA_IN_GGA(X2, .(s(X3), X4), X5) MERGEA_IN_GGA(.(zero, X1), .(s(X2), X3), .(zero, X4)) -> U6_GGA(X1, X2, X3, X4, mergeA_in_gga(X1, .(s(X2), X3), X4)) MERGEA_IN_GGA(.(zero, X1), .(s(X2), X3), .(zero, X4)) -> MERGEA_IN_GGA(X1, .(s(X2), X3), X4) MERGEA_IN_GGA(.(zero, X1), .(zero, X2), .(zero, X3)) -> U7_GGA(X1, X2, X3, mergeA_in_gga(X1, .(zero, X2), X3)) MERGEA_IN_GGA(.(zero, X1), .(zero, X2), .(zero, X3)) -> MERGEA_IN_GGA(X1, .(zero, X2), X3) MERGEA_IN_GGA(.(X1, X2), .(X3, X4), .(X3, X5)) -> U8_GGA(X1, X2, X3, X4, X5, gtC_in_gg(X1, X3)) MERGEA_IN_GGA(.(X1, X2), .(X3, X4), .(X3, X5)) -> GTC_IN_GG(X1, X3) GTC_IN_GG(s(X1), s(X2)) -> U2_GG(X1, X2, gtC_in_gg(X1, X2)) GTC_IN_GG(s(X1), s(X2)) -> GTC_IN_GG(X1, X2) MERGEA_IN_GGA(.(X1, X2), .(X3, X4), .(X3, X5)) -> U9_GGA(X1, X2, X3, X4, X5, gtcC_in_gg(X1, X3)) U9_GGA(X1, X2, X3, X4, X5, gtcC_out_gg(X1, X3)) -> U10_GGA(X1, X2, X3, X4, X5, mergeA_in_gga(.(X1, X2), X4, X5)) U9_GGA(X1, X2, X3, X4, X5, gtcC_out_gg(X1, X3)) -> MERGEA_IN_GGA(.(X1, X2), X4, X5) MERGEA_IN_GGA(.(s(X1), X2), .(s(X3), X4), .(s(X3), X5)) -> U11_GGA(X1, X2, X3, X4, X5, gtC_in_gg(X1, X3)) MERGEA_IN_GGA(.(s(X1), X2), .(s(X3), X4), .(s(X3), X5)) -> GTC_IN_GG(X1, X3) MERGEA_IN_GGA(.(s(X1), X2), .(s(X3), X4), .(s(X3), X5)) -> U12_GGA(X1, X2, X3, X4, X5, gtcC_in_gg(X1, X3)) U12_GGA(X1, X2, X3, X4, X5, gtcC_out_gg(X1, X3)) -> U13_GGA(X1, X2, X3, X4, X5, mergeA_in_gga(.(s(X1), X2), X4, X5)) U12_GGA(X1, X2, X3, X4, X5, gtcC_out_gg(X1, X3)) -> MERGEA_IN_GGA(.(s(X1), X2), X4, X5) MERGEA_IN_GGA(.(s(X1), X2), .(zero, X3), .(zero, X4)) -> U14_GGA(X1, X2, X3, X4, mergeA_in_gga(.(s(X1), X2), X3, X4)) MERGEA_IN_GGA(.(s(X1), X2), .(zero, X3), .(zero, X4)) -> MERGEA_IN_GGA(.(s(X1), X2), X3, X4) The TRS R consists of the following rules: lecB_in_gg(s(X1), s(X2)) -> U25_gg(X1, X2, lecB_in_gg(X1, X2)) lecB_in_gg(zero, s(X1)) -> lecB_out_gg(zero, s(X1)) lecB_in_gg(zero, zero) -> lecB_out_gg(zero, zero) U25_gg(X1, X2, lecB_out_gg(X1, X2)) -> lecB_out_gg(s(X1), s(X2)) gtcC_in_gg(s(X1), s(X2)) -> U26_gg(X1, X2, gtcC_in_gg(X1, X2)) gtcC_in_gg(s(X1), zero) -> gtcC_out_gg(s(X1), zero) U26_gg(X1, X2, gtcC_out_gg(X1, X2)) -> gtcC_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) s(x1) = s(x1) leB_in_gg(x1, x2) = leB_in_gg(x1, x2) lecB_in_gg(x1, x2) = lecB_in_gg(x1, x2) U25_gg(x1, x2, x3) = U25_gg(x1, x2, x3) zero = zero lecB_out_gg(x1, x2) = lecB_out_gg(x1, x2) gtC_in_gg(x1, x2) = gtC_in_gg(x1, x2) gtcC_in_gg(x1, x2) = gtcC_in_gg(x1, x2) U26_gg(x1, x2, x3) = U26_gg(x1, x2, x3) gtcC_out_gg(x1, x2) = gtcC_out_gg(x1, x2) MERGEA_IN_GGA(x1, x2, x3) = MERGEA_IN_GGA(x1, x2) U3_GGA(x1, x2, x3, x4, x5, x6) = U3_GGA(x1, x2, x3, x4, x6) LEB_IN_GG(x1, x2) = LEB_IN_GG(x1, x2) U1_GG(x1, x2, x3) = U1_GG(x1, x2, x3) U4_GGA(x1, x2, x3, x4, x5, x6) = U4_GGA(x1, x2, x3, x4, x6) U5_GGA(x1, x2, x3, x4, x5, x6) = U5_GGA(x1, x2, x3, x4, x6) U6_GGA(x1, x2, x3, x4, x5) = U6_GGA(x1, x2, x3, x5) U7_GGA(x1, x2, x3, x4) = U7_GGA(x1, x2, x4) U8_GGA(x1, x2, x3, x4, x5, x6) = U8_GGA(x1, x2, x3, x4, x6) GTC_IN_GG(x1, x2) = GTC_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, x5, x6) = U11_GGA(x1, x2, x3, x4, x6) 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) = U14_GGA(x1, x2, x3, x5) 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: GTC_IN_GG(s(X1), s(X2)) -> GTC_IN_GG(X1, X2) The TRS R consists of the following rules: lecB_in_gg(s(X1), s(X2)) -> U25_gg(X1, X2, lecB_in_gg(X1, X2)) lecB_in_gg(zero, s(X1)) -> lecB_out_gg(zero, s(X1)) lecB_in_gg(zero, zero) -> lecB_out_gg(zero, zero) U25_gg(X1, X2, lecB_out_gg(X1, X2)) -> lecB_out_gg(s(X1), s(X2)) gtcC_in_gg(s(X1), s(X2)) -> U26_gg(X1, X2, gtcC_in_gg(X1, X2)) gtcC_in_gg(s(X1), zero) -> gtcC_out_gg(s(X1), zero) U26_gg(X1, X2, gtcC_out_gg(X1, X2)) -> gtcC_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: GTC_IN_GG(s(X1), s(X2)) -> GTC_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: GTC_IN_GG(s(X1), s(X2)) -> GTC_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: *GTC_IN_GG(s(X1), s(X2)) -> GTC_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: LEB_IN_GG(s(X1), s(X2)) -> LEB_IN_GG(X1, X2) The TRS R consists of the following rules: lecB_in_gg(s(X1), s(X2)) -> U25_gg(X1, X2, lecB_in_gg(X1, X2)) lecB_in_gg(zero, s(X1)) -> lecB_out_gg(zero, s(X1)) lecB_in_gg(zero, zero) -> lecB_out_gg(zero, zero) U25_gg(X1, X2, lecB_out_gg(X1, X2)) -> lecB_out_gg(s(X1), s(X2)) gtcC_in_gg(s(X1), s(X2)) -> U26_gg(X1, X2, gtcC_in_gg(X1, X2)) gtcC_in_gg(s(X1), zero) -> gtcC_out_gg(s(X1), zero) U26_gg(X1, X2, gtcC_out_gg(X1, X2)) -> gtcC_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: LEB_IN_GG(s(X1), s(X2)) -> LEB_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: LEB_IN_GG(s(X1), s(X2)) -> LEB_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: *LEB_IN_GG(s(X1), s(X2)) -> LEB_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(.(s(X1), X2), .(s(X3), X4), .(s(X1), X5)) -> U4_GGA(X1, X2, X3, X4, X5, lecB_in_gg(X1, X3)) U4_GGA(X1, X2, X3, X4, X5, lecB_out_gg(X1, X3)) -> MERGEA_IN_GGA(X2, .(s(X3), X4), X5) MERGEA_IN_GGA(.(zero, X1), .(s(X2), X3), .(zero, X4)) -> MERGEA_IN_GGA(X1, .(s(X2), X3), X4) MERGEA_IN_GGA(.(X1, X2), .(X3, X4), .(X3, X5)) -> U9_GGA(X1, X2, X3, X4, X5, gtcC_in_gg(X1, X3)) U9_GGA(X1, X2, X3, X4, X5, gtcC_out_gg(X1, X3)) -> MERGEA_IN_GGA(.(X1, X2), X4, X5) MERGEA_IN_GGA(.(zero, X1), .(zero, X2), .(zero, X3)) -> MERGEA_IN_GGA(X1, .(zero, X2), X3) MERGEA_IN_GGA(.(s(X1), X2), .(zero, X3), .(zero, X4)) -> MERGEA_IN_GGA(.(s(X1), X2), X3, X4) MERGEA_IN_GGA(.(s(X1), X2), .(s(X3), X4), .(s(X3), X5)) -> U12_GGA(X1, X2, X3, X4, X5, gtcC_in_gg(X1, X3)) U12_GGA(X1, X2, X3, X4, X5, gtcC_out_gg(X1, X3)) -> MERGEA_IN_GGA(.(s(X1), X2), X4, X5) The TRS R consists of the following rules: lecB_in_gg(s(X1), s(X2)) -> U25_gg(X1, X2, lecB_in_gg(X1, X2)) lecB_in_gg(zero, s(X1)) -> lecB_out_gg(zero, s(X1)) lecB_in_gg(zero, zero) -> lecB_out_gg(zero, zero) U25_gg(X1, X2, lecB_out_gg(X1, X2)) -> lecB_out_gg(s(X1), s(X2)) gtcC_in_gg(s(X1), s(X2)) -> U26_gg(X1, X2, gtcC_in_gg(X1, X2)) gtcC_in_gg(s(X1), zero) -> gtcC_out_gg(s(X1), zero) U26_gg(X1, X2, gtcC_out_gg(X1, X2)) -> gtcC_out_gg(s(X1), s(X2)) The argument filtering Pi contains the following mapping: .(x1, x2) = .(x1, x2) s(x1) = s(x1) lecB_in_gg(x1, x2) = lecB_in_gg(x1, x2) U25_gg(x1, x2, x3) = U25_gg(x1, x2, x3) zero = zero lecB_out_gg(x1, x2) = lecB_out_gg(x1, x2) gtcC_in_gg(x1, x2) = gtcC_in_gg(x1, x2) U26_gg(x1, x2, x3) = U26_gg(x1, x2, x3) gtcC_out_gg(x1, x2) = gtcC_out_gg(x1, x2) MERGEA_IN_GGA(x1, x2, x3) = MERGEA_IN_GGA(x1, x2) U4_GGA(x1, x2, x3, x4, x5, x6) = U4_GGA(x1, x2, x3, x4, x6) U9_GGA(x1, x2, x3, x4, x5, x6) = U9_GGA(x1, x2, x3, x4, x6) U12_GGA(x1, x2, x3, x4, x5, x6) = U12_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(.(s(X1), X2), .(s(X3), X4)) -> U4_GGA(X1, X2, X3, X4, lecB_in_gg(X1, X3)) U4_GGA(X1, X2, X3, X4, lecB_out_gg(X1, X3)) -> MERGEA_IN_GGA(X2, .(s(X3), X4)) MERGEA_IN_GGA(.(zero, X1), .(s(X2), X3)) -> MERGEA_IN_GGA(X1, .(s(X2), X3)) MERGEA_IN_GGA(.(X1, X2), .(X3, X4)) -> U9_GGA(X1, X2, X3, X4, gtcC_in_gg(X1, X3)) U9_GGA(X1, X2, X3, X4, gtcC_out_gg(X1, X3)) -> MERGEA_IN_GGA(.(X1, X2), X4) MERGEA_IN_GGA(.(zero, X1), .(zero, X2)) -> MERGEA_IN_GGA(X1, .(zero, X2)) MERGEA_IN_GGA(.(s(X1), X2), .(zero, X3)) -> MERGEA_IN_GGA(.(s(X1), X2), X3) MERGEA_IN_GGA(.(s(X1), X2), .(s(X3), X4)) -> U12_GGA(X1, X2, X3, X4, gtcC_in_gg(X1, X3)) U12_GGA(X1, X2, X3, X4, gtcC_out_gg(X1, X3)) -> MERGEA_IN_GGA(.(s(X1), X2), X4) The TRS R consists of the following rules: lecB_in_gg(s(X1), s(X2)) -> U25_gg(X1, X2, lecB_in_gg(X1, X2)) lecB_in_gg(zero, s(X1)) -> lecB_out_gg(zero, s(X1)) lecB_in_gg(zero, zero) -> lecB_out_gg(zero, zero) U25_gg(X1, X2, lecB_out_gg(X1, X2)) -> lecB_out_gg(s(X1), s(X2)) gtcC_in_gg(s(X1), s(X2)) -> U26_gg(X1, X2, gtcC_in_gg(X1, X2)) gtcC_in_gg(s(X1), zero) -> gtcC_out_gg(s(X1), zero) U26_gg(X1, X2, gtcC_out_gg(X1, X2)) -> gtcC_out_gg(s(X1), s(X2)) The set Q consists of the following terms: lecB_in_gg(x0, x1) U25_gg(x0, x1, x2) gtcC_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(.(s(X1), X2), .(s(X3), X4)) -> U4_GGA(X1, X2, X3, X4, lecB_in_gg(X1, X3)) MERGEA_IN_GGA(.(zero, X1), .(s(X2), X3)) -> MERGEA_IN_GGA(X1, .(s(X2), X3)) MERGEA_IN_GGA(.(X1, X2), .(X3, X4)) -> U9_GGA(X1, X2, X3, X4, gtcC_in_gg(X1, X3)) MERGEA_IN_GGA(.(zero, X1), .(zero, X2)) -> MERGEA_IN_GGA(X1, .(zero, X2)) MERGEA_IN_GGA(.(s(X1), X2), .(zero, X3)) -> MERGEA_IN_GGA(.(s(X1), X2), X3) MERGEA_IN_GGA(.(s(X1), X2), .(s(X3), X4)) -> U12_GGA(X1, X2, X3, X4, gtcC_in_gg(X1, X3)) Used ordering: Polynomial interpretation [POLO]: POL(.(x_1, x_2)) = 2 + 2*x_1 + x_2 POL(MERGEA_IN_GGA(x_1, x_2)) = x_1 + x_2 POL(U12_GGA(x_1, x_2, x_3, x_4, x_5)) = 2 + 2*x_1 + x_2 + x_3 + x_4 + 2*x_5 POL(U25_gg(x_1, x_2, x_3)) = 2*x_1 + 2*x_2 + x_3 POL(U26_gg(x_1, x_2, x_3)) = x_1 + x_2 + x_3 POL(U4_GGA(x_1, x_2, x_3, x_4, x_5)) = 2 + 2*x_1 + x_2 + 2*x_3 + x_4 + x_5 POL(U9_GGA(x_1, x_2, x_3, x_4, x_5)) = 2 + x_1 + x_2 + x_3 + x_4 + x_5 POL(gtcC_in_gg(x_1, x_2)) = x_1 + x_2 POL(gtcC_out_gg(x_1, x_2)) = x_1 + x_2 POL(lecB_in_gg(x_1, x_2)) = 2*x_1 + 2*x_2 POL(lecB_out_gg(x_1, x_2)) = x_1 + 2*x_2 POL(s(x_1)) = 2*x_1 POL(zero) = 0 ---------------------------------------- (25) Obligation: Q DP problem: The TRS P consists of the following rules: U4_GGA(X1, X2, X3, X4, lecB_out_gg(X1, X3)) -> MERGEA_IN_GGA(X2, .(s(X3), X4)) U9_GGA(X1, X2, X3, X4, gtcC_out_gg(X1, X3)) -> MERGEA_IN_GGA(.(X1, X2), X4) U12_GGA(X1, X2, X3, X4, gtcC_out_gg(X1, X3)) -> MERGEA_IN_GGA(.(s(X1), X2), X4) The TRS R consists of the following rules: lecB_in_gg(s(X1), s(X2)) -> U25_gg(X1, X2, lecB_in_gg(X1, X2)) lecB_in_gg(zero, s(X1)) -> lecB_out_gg(zero, s(X1)) lecB_in_gg(zero, zero) -> lecB_out_gg(zero, zero) U25_gg(X1, X2, lecB_out_gg(X1, X2)) -> lecB_out_gg(s(X1), s(X2)) gtcC_in_gg(s(X1), s(X2)) -> U26_gg(X1, X2, gtcC_in_gg(X1, X2)) gtcC_in_gg(s(X1), zero) -> gtcC_out_gg(s(X1), zero) U26_gg(X1, X2, gtcC_out_gg(X1, X2)) -> gtcC_out_gg(s(X1), s(X2)) The set Q consists of the following terms: lecB_in_gg(x0, x1) U25_gg(x0, x1, x2) gtcC_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 0 SCCs with 3 less nodes. ---------------------------------------- (27) TRUE