/export/starexec/sandbox2/solver/bin/starexec_run_standard /export/starexec/sandbox2/benchmark/theBenchmark.pl /export/starexec/sandbox2/output/output_files -------------------------------------------------------------------------------- YES proof of /export/starexec/sandbox2/benchmark/theBenchmark.pl # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty Left Termination of the query pattern overlap(g,g) w.r.t. the given Prolog program could successfully be proven: (0) Prolog (1) PrologToDTProblemTransformerProof [SOUND, 0 ms] (2) TRIPLES (3) TriplesToPiDPProof [SOUND, 0 ms] (4) PiDP (5) DependencyGraphProof [EQUIVALENT, 0 ms] (6) AND (7) PiDP (8) PiDPToQDPProof [EQUIVALENT, 0 ms] (9) QDP (10) QDPSizeChangeProof [EQUIVALENT, 0 ms] (11) YES (12) PiDP (13) PiDPToQDPProof [SOUND, 1 ms] (14) QDP (15) QDPSizeChangeProof [EQUIVALENT, 0 ms] (16) YES ---------------------------------------- (0) Obligation: Clauses: overlap(Xs, Ys) :- ','(member(X, Xs), member(X, Ys)). member(X, Y) :- ','(no(empty(Y)), head(Y, X)). member(X, Y) :- ','(no(empty(Y)), ','(tail(Y, T), member(X, T))). head([], X1). head(.(H, X2), H). tail([], []). tail(.(X3, T), T). empty([]). no(X) :- ','(X, ','(!, failure(a))). no(X4). failure(b). Query: overlap(g,g) ---------------------------------------- (1) PrologToDTProblemTransformerProof (SOUND) Built DT problem from termination graph DT10. { "root": 1, "program": { "directives": [], "clauses": [ [ "(overlap Xs Ys)", "(',' (member X Xs) (member X Ys))" ], [ "(member X Y)", "(',' (no (empty Y)) (head Y X))" ], [ "(member X Y)", "(',' (no (empty Y)) (',' (tail Y T) (member X T)))" ], [ "(head ([]) X1)", null ], [ "(head (. H X2) H)", null ], [ "(tail ([]) ([]))", null ], [ "(tail (. X3 T) T)", null ], [ "(empty ([]))", null ], [ "(no X)", "(',' X (',' (!) (failure (a))))" ], [ "(no X4)", null ], [ "(failure (b))", null ] ] }, "graph": { "nodes": { "44": { "goal": [ { "clause": 1, "scope": 8, "term": "(member T28 T6)" }, { "clause": 2, "scope": 8, "term": "(member T28 T6)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T6", "T28" ], "free": [], "exprvars": [] } }, "type": "Nodes", "150": { "goal": [ { "clause": -1, "scope": -1, "term": "(',' (',' (call (empty T85)) (',' (!_19) (failure (a)))) (',' (',' (tail T85 X132) (member X133 X132)) (member X133 T6)))" }, { "clause": 9, "scope": 19, "term": "(',' (',' (no (empty T85)) (',' (tail T85 X132) (member X133 X132))) (member X133 T6))" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T6", "T85" ], "free": [ "X133", "X132" ], "exprvars": [] } }, "151": { "goal": [ { "clause": -1, "scope": -1, "term": "(',' (empty T85) (',' (',' (!_19) (failure (a))) (',' (',' (tail T85 X132) (member X133 X132)) (member X133 T6))))" }, { "clause": -1, "scope": 20, "term": null }, { "clause": 9, "scope": 19, "term": "(',' (',' (no (empty T85)) (',' (tail T85 X132) (member X133 X132))) (member X133 T6))" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T6", "T85" ], "free": [ "X133", "X132" ], "exprvars": [] } }, "152": { "goal": [ { "clause": 7, "scope": 21, "term": "(',' (empty T85) (',' (',' (!_19) (failure (a))) (',' (',' (tail T85 X132) (member X133 X132)) (member X133 T6))))" }, { "clause": -1, "scope": 21, "term": null }, { "clause": -1, "scope": 20, "term": null }, { "clause": 9, "scope": 19, "term": "(',' (',' (no (empty T85)) (',' (tail T85 X132) (member X133 X132))) (member X133 T6))" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T6", "T85" ], "free": [ "X133", "X132" ], "exprvars": [] } }, "153": { "goal": [ { "clause": -1, "scope": -1, "term": "(',' (',' (!_19) (failure (a))) (',' (',' (tail ([]) X132) (member X133 X132)) (member X133 T6)))" }, { "clause": -1, "scope": 21, "term": null }, { "clause": -1, "scope": 20, "term": null }, { "clause": 9, "scope": 19, "term": "(',' (',' (no (empty ([]))) (',' (tail ([]) X132) (member X133 X132))) (member X133 T6))" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T6"], "free": [ "X133", "X132" ], "exprvars": [] } }, "154": { "goal": [ { "clause": -1, "scope": 21, "term": null }, { "clause": -1, "scope": 20, "term": null }, { "clause": 9, "scope": 19, "term": "(',' (',' (no (empty T85)) (',' (tail T85 X132) (member X133 X132))) (member X133 T6))" } ], "kb": { "nonunifying": [[ "(empty T85)", "(empty ([]))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T6", "T85" ], "free": [ "X133", "X132" ], "exprvars": [] } }, "111": { "goal": [{ "clause": 1, "scope": 8, "term": "(member T28 T6)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T6", "T28" ], "free": [], "exprvars": [] } }, "155": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (failure (a)) (',' (',' (tail ([]) X132) (member X133 X132)) (member X133 T6)))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T6"], "free": [ "X133", "X132" ], "exprvars": [] } }, "112": { "goal": [{ "clause": 2, "scope": 8, "term": "(member T28 T6)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T6", "T28" ], "free": [], "exprvars": [] } }, "156": { "goal": [{ "clause": 10, "scope": 22, "term": "(',' (failure (a)) (',' (',' (tail ([]) X132) (member X133 X132)) (member X133 T6)))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T6"], "free": [ "X133", "X132" ], "exprvars": [] } }, "113": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (no (empty T41)) (head T41 T40))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T40", "T41" ], "free": [], "exprvars": [] } }, "157": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "114": { "goal": [ { "clause": 8, "scope": 9, "term": "(',' (no (empty T41)) (head T41 T40))" }, { "clause": 9, "scope": 9, "term": "(',' (no (empty T41)) (head T41 T40))" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T40", "T41" ], "free": [], "exprvars": [] } }, "158": { "goal": [ { "clause": -1, "scope": 20, "term": null }, { "clause": 9, "scope": 19, "term": "(',' (',' (no (empty T85)) (',' (tail T85 X132) (member X133 X132))) (member X133 T6))" } ], "kb": { "nonunifying": [[ "(empty T85)", "(empty ([]))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T6", "T85" ], "free": [ "X133", "X132" ], "exprvars": [] } }, "115": { "goal": [ { "clause": -1, "scope": -1, "term": "(',' (',' (call (empty T44)) (',' (!_9) (failure (a)))) (head T44 T40))" }, { "clause": 9, "scope": 9, "term": "(',' (no (empty T44)) (head T44 T40))" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T40", "T44" ], "free": [], "exprvars": [] } }, "159": { "goal": [{ "clause": 9, "scope": 19, "term": "(',' (',' (no (empty T85)) (',' (tail T85 X132) (member X133 X132))) (member X133 T6))" }], "kb": { "nonunifying": [[ "(empty T85)", "(empty ([]))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T6", "T85" ], "free": [ "X133", "X132" ], "exprvars": [] } }, "116": { "goal": [ { "clause": -1, "scope": -1, "term": "(',' (empty T44) (',' (',' (!_9) (failure (a))) (head T44 T40)))" }, { "clause": -1, "scope": 10, "term": null }, { "clause": 9, "scope": 9, "term": "(',' (no (empty T44)) (head T44 T40))" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T40", "T44" ], "free": [], "exprvars": [] } }, "117": { "goal": [ { "clause": 7, "scope": 11, "term": "(',' (empty T44) (',' (',' (!_9) (failure (a))) (head T44 T40)))" }, { "clause": -1, "scope": 11, "term": null }, { "clause": -1, "scope": 10, "term": null }, { "clause": 9, "scope": 9, "term": "(',' (no (empty T44)) (head T44 T40))" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T40", "T44" ], "free": [], "exprvars": [] } }, "118": { "goal": [ { "clause": -1, "scope": -1, "term": "(',' (',' (!_9) (failure (a))) (head ([]) T40))" }, { "clause": -1, "scope": 11, "term": null }, { "clause": -1, "scope": 10, "term": null }, { "clause": 9, "scope": 9, "term": "(',' (no (empty ([]))) (head ([]) T40))" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T40"], "free": [], "exprvars": [] } }, "119": { "goal": [ { "clause": -1, "scope": 11, "term": null }, { "clause": -1, "scope": 10, "term": null }, { "clause": 9, "scope": 9, "term": "(',' (no (empty T44)) (head T44 T40))" } ], "kb": { "nonunifying": [[ "(empty T44)", "(empty ([]))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T40", "T44" ], "free": [], "exprvars": [] } }, "10": { "goal": [ { "clause": 1, "scope": 2, "term": "(',' (member X9 T5) (member X9 T6))" }, { "clause": 2, "scope": 2, "term": "(',' (member X9 T5) (member X9 T6))" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T5", "T6" ], "free": ["X9"], "exprvars": [] } }, "11": { "goal": [{ "clause": 1, "scope": 2, "term": "(',' (member X9 T5) (member X9 T6))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T5", "T6" ], "free": ["X9"], "exprvars": [] } }, "12": { "goal": [{ "clause": 2, "scope": 2, "term": "(',' (member X9 T5) (member X9 T6))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T5", "T6" ], "free": ["X9"], "exprvars": [] } }, "14": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (',' (no (empty T13)) (head T13 X30)) (member X30 T6))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T6", "T13" ], "free": ["X30"], "exprvars": [] } }, "15": { "goal": [ { "clause": 8, "scope": 3, "term": "(',' (',' (no (empty T13)) (head T13 X30)) (member X30 T6))" }, { "clause": 9, "scope": 3, "term": "(',' (',' (no (empty T13)) (head T13 X30)) (member X30 T6))" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T6", "T13" ], "free": ["X30"], "exprvars": [] } }, "19": { "goal": [ { "clause": -1, "scope": -1, "term": "(',' (',' (call (empty T17)) (',' (!_3) (failure (a)))) (',' (head T17 X30) (member X30 T6)))" }, { "clause": 9, "scope": 3, "term": "(',' (',' (no (empty T17)) (head T17 X30)) (member X30 T6))" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T6", "T17" ], "free": ["X30"], "exprvars": [] } }, "160": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (',' (tail T88 X132) (member X133 X132)) (member X133 T6))" }], "kb": { "nonunifying": [[ "(empty T88)", "(empty ([]))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T6", "T88" ], "free": [ "X133", "X132" ], "exprvars": [] } }, "161": { "goal": [ { "clause": 5, "scope": 23, "term": "(',' (',' (tail T88 X132) (member X133 X132)) (member X133 T6))" }, { "clause": 6, "scope": 23, "term": "(',' (',' (tail T88 X132) (member X133 X132)) (member X133 T6))" } ], "kb": { "nonunifying": [[ "(empty T88)", "(empty ([]))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T6", "T88" ], "free": [ "X133", "X132" ], "exprvars": [] } }, "162": { "goal": [{ "clause": 6, "scope": 23, "term": "(',' (',' (tail T88 X132) (member X133 X132)) (member X133 T6))" }], "kb": { "nonunifying": [[ "(empty T88)", "(empty ([]))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T6", "T88" ], "free": [ "X133", "X132" ], "exprvars": [] } }, "163": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (member X133 T94) (member X133 T6))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T6", "T94" ], "free": ["X133"], "exprvars": [] } }, "120": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (failure (a)) (head ([]) T40))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T40"], "free": [], "exprvars": [] } }, "164": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "121": { "goal": [{ "clause": 10, "scope": 12, "term": "(',' (failure (a)) (head ([]) T40))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T40"], "free": [], "exprvars": [] } }, "1": { "goal": [{ "clause": -1, "scope": -1, "term": "(overlap T1 T2)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T1", "T2" ], "free": [], "exprvars": [] } }, "122": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "123": { "goal": [ { "clause": -1, "scope": 10, "term": null }, { "clause": 9, "scope": 9, "term": "(',' (no (empty T44)) (head T44 T40))" } ], "kb": { "nonunifying": [[ "(empty T44)", "(empty ([]))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T40", "T44" ], "free": [], "exprvars": [] } }, "124": { "goal": [{ "clause": 9, "scope": 9, "term": "(',' (no (empty T44)) (head T44 T40))" }], "kb": { "nonunifying": [[ "(empty T44)", "(empty ([]))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T40", "T44" ], "free": [], "exprvars": [] } }, "125": { "goal": [{ "clause": -1, "scope": -1, "term": "(head T47 T40)" }], "kb": { "nonunifying": [[ "(empty T47)", "(empty ([]))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T40", "T47" ], "free": [], "exprvars": [] } }, "126": { "goal": [ { "clause": 3, "scope": 13, "term": "(head T47 T40)" }, { "clause": 4, "scope": 13, "term": "(head T47 T40)" } ], "kb": { "nonunifying": [[ "(empty T47)", "(empty ([]))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T40", "T47" ], "free": [], "exprvars": [] } }, "127": { "goal": [{ "clause": 4, "scope": 13, "term": "(head T47 T40)" }], "kb": { "nonunifying": [[ "(empty T47)", "(empty ([]))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T40", "T47" ], "free": [], "exprvars": [] } }, "128": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "8": { "goal": [{ "clause": 0, "scope": 1, "term": "(overlap T1 T2)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T1", "T2" ], "free": [], "exprvars": [] } }, "129": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "9": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (member X9 T5) (member X9 T6))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T5", "T6" ], "free": ["X9"], "exprvars": [] } }, "20": { "goal": [ { "clause": -1, "scope": -1, "term": "(',' (empty T17) (',' (',' (!_3) (failure (a))) (',' (head T17 X30) (member X30 T6))))" }, { "clause": -1, "scope": 4, "term": null }, { "clause": 9, "scope": 3, "term": "(',' (',' (no (empty T17)) (head T17 X30)) (member X30 T6))" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T6", "T17" ], "free": ["X30"], "exprvars": [] } }, "21": { "goal": [ { "clause": 7, "scope": 5, "term": "(',' (empty T17) (',' (',' (!_3) (failure (a))) (',' (head T17 X30) (member X30 T6))))" }, { "clause": -1, "scope": 5, "term": null }, { "clause": -1, "scope": 4, "term": null }, { "clause": 9, "scope": 3, "term": "(',' (',' (no (empty T17)) (head T17 X30)) (member X30 T6))" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T6", "T17" ], "free": ["X30"], "exprvars": [] } }, "22": { "goal": [ { "clause": -1, "scope": -1, "term": "(',' (',' (!_3) (failure (a))) (',' (head ([]) X30) (member X30 T6)))" }, { "clause": -1, "scope": 5, "term": null }, { "clause": -1, "scope": 4, "term": null }, { "clause": 9, "scope": 3, "term": "(',' (',' (no (empty ([]))) (head ([]) X30)) (member X30 T6))" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T6"], "free": ["X30"], "exprvars": [] } }, "23": { "goal": [ { "clause": -1, "scope": 5, "term": null }, { "clause": -1, "scope": 4, "term": null }, { "clause": 9, "scope": 3, "term": "(',' (',' (no (empty T17)) (head T17 X30)) (member X30 T6))" } ], "kb": { "nonunifying": [[ "(empty T17)", "(empty ([]))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T6", "T17" ], "free": ["X30"], "exprvars": [] } }, "24": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (failure (a)) (',' (head ([]) X30) (member X30 T6)))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T6"], "free": ["X30"], "exprvars": [] } }, "25": { "goal": [{ "clause": 10, "scope": 6, "term": "(',' (failure (a)) (',' (head ([]) X30) (member X30 T6)))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T6"], "free": ["X30"], "exprvars": [] } }, "26": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "28": { "goal": [ { "clause": -1, "scope": 4, "term": null }, { "clause": 9, "scope": 3, "term": "(',' (',' (no (empty T17)) (head T17 X30)) (member X30 T6))" } ], "kb": { "nonunifying": [[ "(empty T17)", "(empty ([]))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T6", "T17" ], "free": ["X30"], "exprvars": [] } }, "29": { "goal": [{ "clause": 9, "scope": 3, "term": "(',' (',' (no (empty T17)) (head T17 X30)) (member X30 T6))" }], "kb": { "nonunifying": [[ "(empty T17)", "(empty ([]))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T6", "T17" ], "free": ["X30"], "exprvars": [] } }, "130": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "131": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (no (empty T61)) (',' (tail T61 X92) (member T60 X92)))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T60", "T61" ], "free": ["X92"], "exprvars": [] } }, "132": { "goal": [ { "clause": 8, "scope": 14, "term": "(',' (no (empty T61)) (',' (tail T61 X92) (member T60 X92)))" }, { "clause": 9, "scope": 14, "term": "(',' (no (empty T61)) (',' (tail T61 X92) (member T60 X92)))" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T60", "T61" ], "free": ["X92"], "exprvars": [] } }, "133": { "goal": [ { "clause": -1, "scope": -1, "term": "(',' (',' (call (empty T65)) (',' (!_14) (failure (a)))) (',' (tail T65 X92) (member T60 X92)))" }, { "clause": 9, "scope": 14, "term": "(',' (no (empty T65)) (',' (tail T65 X92) (member T60 X92)))" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T60", "T65" ], "free": ["X92"], "exprvars": [] } }, "134": { "goal": [ { "clause": -1, "scope": -1, "term": "(',' (empty T65) (',' (',' (!_14) (failure (a))) (',' (tail T65 X92) (member T60 X92))))" }, { "clause": -1, "scope": 15, "term": null }, { "clause": 9, "scope": 14, "term": "(',' (no (empty T65)) (',' (tail T65 X92) (member T60 X92)))" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T60", "T65" ], "free": ["X92"], "exprvars": [] } }, "135": { "goal": [ { "clause": 7, "scope": 16, "term": "(',' (empty T65) (',' (',' (!_14) (failure (a))) (',' (tail T65 X92) (member T60 X92))))" }, { "clause": -1, "scope": 16, "term": null }, { "clause": -1, "scope": 15, "term": null }, { "clause": 9, "scope": 14, "term": "(',' (no (empty T65)) (',' (tail T65 X92) (member T60 X92)))" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T60", "T65" ], "free": ["X92"], "exprvars": [] } }, "136": { "goal": [ { "clause": -1, "scope": -1, "term": "(',' (',' (!_14) (failure (a))) (',' (tail ([]) X92) (member T60 X92)))" }, { "clause": -1, "scope": 16, "term": null }, { "clause": -1, "scope": 15, "term": null }, { "clause": 9, "scope": 14, "term": "(',' (no (empty ([]))) (',' (tail ([]) X92) (member T60 X92)))" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T60"], "free": ["X92"], "exprvars": [] } }, "137": { "goal": [ { "clause": -1, "scope": 16, "term": null }, { "clause": -1, "scope": 15, "term": null }, { "clause": 9, "scope": 14, "term": "(',' (no (empty T65)) (',' (tail T65 X92) (member T60 X92)))" } ], "kb": { "nonunifying": [[ "(empty T65)", "(empty ([]))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T60", "T65" ], "free": ["X92"], "exprvars": [] } }, "138": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (failure (a)) (',' (tail ([]) X92) (member T60 X92)))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T60"], "free": ["X92"], "exprvars": [] } }, "139": { "goal": [{ "clause": 10, "scope": 17, "term": "(',' (failure (a)) (',' (tail ([]) X92) (member T60 X92)))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T60"], "free": ["X92"], "exprvars": [] } }, "32": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (head T22 X30) (member X30 T6))" }], "kb": { "nonunifying": [[ "(empty T22)", "(empty ([]))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T6", "T22" ], "free": ["X30"], "exprvars": [] } }, "33": { "goal": [ { "clause": 3, "scope": 7, "term": "(',' (head T22 X30) (member X30 T6))" }, { "clause": 4, "scope": 7, "term": "(',' (head T22 X30) (member X30 T6))" } ], "kb": { "nonunifying": [[ "(empty T22)", "(empty ([]))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T6", "T22" ], "free": ["X30"], "exprvars": [] } }, "35": { "goal": [{ "clause": 4, "scope": 7, "term": "(',' (head T22 X30) (member X30 T6))" }], "kb": { "nonunifying": [[ "(empty T22)", "(empty ([]))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T6", "T22" ], "free": ["X30"], "exprvars": [] } }, "38": { "goal": [{ "clause": -1, "scope": -1, "term": "(member T28 T6)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T6", "T28" ], "free": [], "exprvars": [] } }, "140": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "141": { "goal": [ { "clause": -1, "scope": 15, "term": null }, { "clause": 9, "scope": 14, "term": "(',' (no (empty T65)) (',' (tail T65 X92) (member T60 X92)))" } ], "kb": { "nonunifying": [[ "(empty T65)", "(empty ([]))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T60", "T65" ], "free": ["X92"], "exprvars": [] } }, "142": { "goal": [{ "clause": 9, "scope": 14, "term": "(',' (no (empty T65)) (',' (tail T65 X92) (member T60 X92)))" }], "kb": { "nonunifying": [[ "(empty T65)", "(empty ([]))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T60", "T65" ], "free": ["X92"], "exprvars": [] } }, "143": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (tail T70 X92) (member T60 X92))" }], "kb": { "nonunifying": [[ "(empty T70)", "(empty ([]))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T60", "T70" ], "free": ["X92"], "exprvars": [] } }, "144": { "goal": [ { "clause": 5, "scope": 18, "term": "(',' (tail T70 X92) (member T60 X92))" }, { "clause": 6, "scope": 18, "term": "(',' (tail T70 X92) (member T60 X92))" } ], "kb": { "nonunifying": [[ "(empty T70)", "(empty ([]))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T60", "T70" ], "free": ["X92"], "exprvars": [] } }, "145": { "goal": [{ "clause": 6, "scope": 18, "term": "(',' (tail T70 X92) (member T60 X92))" }], "kb": { "nonunifying": [[ "(empty T70)", "(empty ([]))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T60", "T70" ], "free": ["X92"], "exprvars": [] } }, "146": { "goal": [{ "clause": -1, "scope": -1, "term": "(member T60 T77)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T60", "T77" ], "free": [], "exprvars": [] } }, "147": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "148": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (',' (no (empty T82)) (',' (tail T82 X132) (member X133 X132))) (member X133 T6))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T6", "T82" ], "free": [ "X133", "X132" ], "exprvars": [] } }, "149": { "goal": [ { "clause": 8, "scope": 19, "term": "(',' (',' (no (empty T82)) (',' (tail T82 X132) (member X133 X132))) (member X133 T6))" }, { "clause": 9, "scope": 19, "term": "(',' (',' (no (empty T82)) (',' (tail T82 X132) (member X133 X132))) (member X133 T6))" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T6", "T82" ], "free": [ "X133", "X132" ], "exprvars": [] } }, "40": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } } }, "edges": [ { "from": 1, "to": 8, "label": "CASE" }, { "from": 8, "to": 9, "label": "ONLY EVAL with clause\noverlap(X7, X8) :- ','(member(X9, X7), member(X9, X8)).\nand substitutionT1 -> T5,\nX7 -> T5,\nT2 -> T6,\nX8 -> T6" }, { "from": 9, "to": 10, "label": "CASE" }, { "from": 10, "to": 11, "label": "PARALLEL" }, { "from": 10, "to": 12, "label": "PARALLEL" }, { "from": 11, "to": 14, "label": "ONLY EVAL with clause\nmember(X28, X29) :- ','(no(empty(X29)), head(X29, X28)).\nand substitutionX9 -> X30,\nX28 -> X30,\nT5 -> T13,\nX29 -> T13" }, { "from": 12, "to": 148, "label": "ONLY EVAL with clause\nmember(X130, X131) :- ','(no(empty(X131)), ','(tail(X131, X132), member(X130, X132))).\nand substitutionX9 -> X133,\nX130 -> X133,\nT5 -> T82,\nX131 -> T82" }, { "from": 14, "to": 15, "label": "CASE" }, { "from": 15, "to": 19, "label": "ONLY EVAL with clause\nno(X36) :- ','(call(X36), ','(!_3, failure(a))).\nand substitutionT13 -> T17,\nX36 -> empty(T17)" }, { "from": 19, "to": 20, "label": "CALL" }, { "from": 20, "to": 21, "label": "CASE" }, { "from": 21, "to": 22, "label": "EVAL with clause\nempty([]).\nand substitutionT17 -> []" }, { "from": 21, "to": 23, "label": "EVAL-BACKTRACK" }, { "from": 22, "to": 24, "label": "CUT" }, { "from": 23, "to": 28, "label": "FAILURE" }, { "from": 24, "to": 25, "label": "CASE" }, { "from": 25, "to": 26, "label": "BACKTRACK\nfor clause: failure(b)because of non-unification" }, { "from": 28, "to": 29, "label": "FAILURE" }, { "from": 29, "to": 32, "label": "ONLY EVAL with clause\nno(X45).\nand substitutionT17 -> T22,\nX45 -> empty(T22)" }, { "from": 32, "to": 33, "label": "CASE" }, { "from": 33, "to": 35, "label": "BACKTRACK\nfor clause: head([], X1)\nwith clash: (empty(T22), empty([]))" }, { "from": 35, "to": 38, "label": "EVAL with clause\nhead(.(X55, X56), X55).\nand substitutionX55 -> T28,\nX56 -> T29,\nT22 -> .(T28, T29),\nX30 -> T28" }, { "from": 35, "to": 40, "label": "EVAL-BACKTRACK" }, { "from": 38, "to": 44, "label": "CASE" }, { "from": 44, "to": 111, "label": "PARALLEL" }, { "from": 44, "to": 112, "label": "PARALLEL" }, { "from": 111, "to": 113, "label": "ONLY EVAL with clause\nmember(X67, X68) :- ','(no(empty(X68)), head(X68, X67)).\nand substitutionT28 -> T40,\nX67 -> T40,\nT6 -> T41,\nX68 -> T41" }, { "from": 112, "to": 131, "label": "ONLY EVAL with clause\nmember(X90, X91) :- ','(no(empty(X91)), ','(tail(X91, X92), member(X90, X92))).\nand substitutionT28 -> T60,\nX90 -> T60,\nT6 -> T61,\nX91 -> T61" }, { "from": 113, "to": 114, "label": "CASE" }, { "from": 114, "to": 115, "label": "ONLY EVAL with clause\nno(X71) :- ','(call(X71), ','(!_9, failure(a))).\nand substitutionT41 -> T44,\nX71 -> empty(T44)" }, { "from": 115, "to": 116, "label": "CALL" }, { "from": 116, "to": 117, "label": "CASE" }, { "from": 117, "to": 118, "label": "EVAL with clause\nempty([]).\nand substitutionT44 -> []" }, { "from": 117, "to": 119, "label": "EVAL-BACKTRACK" }, { "from": 118, "to": 120, "label": "CUT" }, { "from": 119, "to": 123, "label": "FAILURE" }, { "from": 120, "to": 121, "label": "CASE" }, { "from": 121, "to": 122, "label": "BACKTRACK\nfor clause: failure(b)because of non-unification" }, { "from": 123, "to": 124, "label": "FAILURE" }, { "from": 124, "to": 125, "label": "ONLY EVAL with clause\nno(X74).\nand substitutionT44 -> T47,\nX74 -> empty(T47)" }, { "from": 125, "to": 126, "label": "CASE" }, { "from": 126, "to": 127, "label": "BACKTRACK\nfor clause: head([], X1)\nwith clash: (empty(T47), empty([]))" }, { "from": 127, "to": 128, "label": "EVAL with clause\nhead(.(X80, X81), X80).\nand substitutionX80 -> T53,\nX81 -> T54,\nT47 -> .(T53, T54),\nT40 -> T53" }, { "from": 127, "to": 129, "label": "EVAL-BACKTRACK" }, { "from": 128, "to": 130, "label": "SUCCESS" }, { "from": 131, "to": 132, "label": "CASE" }, { "from": 132, "to": 133, "label": "ONLY EVAL with clause\nno(X98) :- ','(call(X98), ','(!_14, failure(a))).\nand substitutionT61 -> T65,\nX98 -> empty(T65)" }, { "from": 133, "to": 134, "label": "CALL" }, { "from": 134, "to": 135, "label": "CASE" }, { "from": 135, "to": 136, "label": "EVAL with clause\nempty([]).\nand substitutionT65 -> []" }, { "from": 135, "to": 137, "label": "EVAL-BACKTRACK" }, { "from": 136, "to": 138, "label": "CUT" }, { "from": 137, "to": 141, "label": "FAILURE" }, { "from": 138, "to": 139, "label": "CASE" }, { "from": 139, "to": 140, "label": "BACKTRACK\nfor clause: failure(b)because of non-unification" }, { "from": 141, "to": 142, "label": "FAILURE" }, { "from": 142, "to": 143, "label": "ONLY EVAL with clause\nno(X107).\nand substitutionT65 -> T70,\nX107 -> empty(T70)" }, { "from": 143, "to": 144, "label": "CASE" }, { "from": 144, "to": 145, "label": "BACKTRACK\nfor clause: tail([], [])\nwith clash: (empty(T70), empty([]))" }, { "from": 145, "to": 146, "label": "EVAL with clause\ntail(.(X115, X116), X116).\nand substitutionX115 -> T76,\nX116 -> T77,\nT70 -> .(T76, T77),\nX92 -> T77" }, { "from": 145, "to": 147, "label": "EVAL-BACKTRACK" }, { "from": 146, "to": 38, "label": "INSTANCE with matching:\nT28 -> T60\nT6 -> T77" }, { "from": 148, "to": 149, "label": "CASE" }, { "from": 149, "to": 150, "label": "ONLY EVAL with clause\nno(X140) :- ','(call(X140), ','(!_19, failure(a))).\nand substitutionT82 -> T85,\nX140 -> empty(T85)" }, { "from": 150, "to": 151, "label": "CALL" }, { "from": 151, "to": 152, "label": "CASE" }, { "from": 152, "to": 153, "label": "EVAL with clause\nempty([]).\nand substitutionT85 -> []" }, { "from": 152, "to": 154, "label": "EVAL-BACKTRACK" }, { "from": 153, "to": 155, "label": "CUT" }, { "from": 154, "to": 158, "label": "FAILURE" }, { "from": 155, "to": 156, "label": "CASE" }, { "from": 156, "to": 157, "label": "BACKTRACK\nfor clause: failure(b)because of non-unification" }, { "from": 158, "to": 159, "label": "FAILURE" }, { "from": 159, "to": 160, "label": "ONLY EVAL with clause\nno(X151).\nand substitutionT85 -> T88,\nX151 -> empty(T88)" }, { "from": 160, "to": 161, "label": "CASE" }, { "from": 161, "to": 162, "label": "BACKTRACK\nfor clause: tail([], [])\nwith clash: (empty(T88), empty([]))" }, { "from": 162, "to": 163, "label": "EVAL with clause\ntail(.(X160, X161), X161).\nand substitutionX160 -> T93,\nX161 -> T94,\nT88 -> .(T93, T94),\nX132 -> T94" }, { "from": 162, "to": 164, "label": "EVAL-BACKTRACK" }, { "from": 163, "to": 9, "label": "INSTANCE with matching:\nX9 -> X133\nT5 -> T94" } ], "type": "Graph" } } ---------------------------------------- (2) Obligation: Triples: memberA(X1, .(X2, X3)) :- memberA(X1, X3). pB(X1, .(X1, X2), X3) :- memberA(X1, X3). pB(X1, .(X2, X3), X4) :- pB(X1, X3, X4). overlapC(X1, X2) :- pB(X3, X1, X2). Clauses: membercA(X1, .(X1, X2)). membercA(X1, .(X2, X3)) :- membercA(X1, X3). qcB(X1, .(X1, X2), X3) :- membercA(X1, X3). qcB(X1, .(X2, X3), X4) :- qcB(X1, X3, X4). Afs: overlapC(x1, x2) = overlapC(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: overlapC_in_2: (b,b) pB_in_3: (f,b,b) memberA_in_2: (b,b) Transforming TRIPLES into the following Term Rewriting System: Pi DP problem: The TRS P consists of the following rules: OVERLAPC_IN_GG(X1, X2) -> U4_GG(X1, X2, pB_in_agg(X3, X1, X2)) OVERLAPC_IN_GG(X1, X2) -> PB_IN_AGG(X3, X1, X2) PB_IN_AGG(X1, .(X1, X2), X3) -> U2_AGG(X1, X2, X3, memberA_in_gg(X1, X3)) PB_IN_AGG(X1, .(X1, X2), X3) -> MEMBERA_IN_GG(X1, X3) MEMBERA_IN_GG(X1, .(X2, X3)) -> U1_GG(X1, X2, X3, memberA_in_gg(X1, X3)) MEMBERA_IN_GG(X1, .(X2, X3)) -> MEMBERA_IN_GG(X1, X3) PB_IN_AGG(X1, .(X2, X3), X4) -> U3_AGG(X1, X2, X3, X4, pB_in_agg(X1, X3, X4)) PB_IN_AGG(X1, .(X2, X3), X4) -> PB_IN_AGG(X1, X3, X4) R is empty. The argument filtering Pi contains the following mapping: pB_in_agg(x1, x2, x3) = pB_in_agg(x2, x3) .(x1, x2) = .(x1, x2) memberA_in_gg(x1, x2) = memberA_in_gg(x1, x2) OVERLAPC_IN_GG(x1, x2) = OVERLAPC_IN_GG(x1, x2) U4_GG(x1, x2, x3) = U4_GG(x1, x2, x3) PB_IN_AGG(x1, x2, x3) = PB_IN_AGG(x2, x3) U2_AGG(x1, x2, x3, x4) = U2_AGG(x1, x2, x3, x4) MEMBERA_IN_GG(x1, x2) = MEMBERA_IN_GG(x1, x2) U1_GG(x1, x2, x3, x4) = U1_GG(x1, x2, x3, x4) U3_AGG(x1, x2, x3, x4, x5) = U3_AGG(x2, x3, x4, 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: OVERLAPC_IN_GG(X1, X2) -> U4_GG(X1, X2, pB_in_agg(X3, X1, X2)) OVERLAPC_IN_GG(X1, X2) -> PB_IN_AGG(X3, X1, X2) PB_IN_AGG(X1, .(X1, X2), X3) -> U2_AGG(X1, X2, X3, memberA_in_gg(X1, X3)) PB_IN_AGG(X1, .(X1, X2), X3) -> MEMBERA_IN_GG(X1, X3) MEMBERA_IN_GG(X1, .(X2, X3)) -> U1_GG(X1, X2, X3, memberA_in_gg(X1, X3)) MEMBERA_IN_GG(X1, .(X2, X3)) -> MEMBERA_IN_GG(X1, X3) PB_IN_AGG(X1, .(X2, X3), X4) -> U3_AGG(X1, X2, X3, X4, pB_in_agg(X1, X3, X4)) PB_IN_AGG(X1, .(X2, X3), X4) -> PB_IN_AGG(X1, X3, X4) R is empty. The argument filtering Pi contains the following mapping: pB_in_agg(x1, x2, x3) = pB_in_agg(x2, x3) .(x1, x2) = .(x1, x2) memberA_in_gg(x1, x2) = memberA_in_gg(x1, x2) OVERLAPC_IN_GG(x1, x2) = OVERLAPC_IN_GG(x1, x2) U4_GG(x1, x2, x3) = U4_GG(x1, x2, x3) PB_IN_AGG(x1, x2, x3) = PB_IN_AGG(x2, x3) U2_AGG(x1, x2, x3, x4) = U2_AGG(x1, x2, x3, x4) MEMBERA_IN_GG(x1, x2) = MEMBERA_IN_GG(x1, x2) U1_GG(x1, x2, x3, x4) = U1_GG(x1, x2, x3, x4) U3_AGG(x1, x2, x3, x4, x5) = U3_AGG(x2, x3, x4, x5) We have to consider all (P,R,Pi)-chains ---------------------------------------- (5) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LOPSTR] contains 2 SCCs with 6 less nodes. ---------------------------------------- (6) Complex Obligation (AND) ---------------------------------------- (7) Obligation: Pi DP problem: The TRS P consists of the following rules: MEMBERA_IN_GG(X1, .(X2, X3)) -> MEMBERA_IN_GG(X1, X3) R is empty. Pi is empty. We have to consider all (P,R,Pi)-chains ---------------------------------------- (8) PiDPToQDPProof (EQUIVALENT) Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. ---------------------------------------- (9) Obligation: Q DP problem: The TRS P consists of the following rules: MEMBERA_IN_GG(X1, .(X2, X3)) -> MEMBERA_IN_GG(X1, X3) R is empty. Q is empty. We have to consider all (P,Q,R)-chains. ---------------------------------------- (10) QDPSizeChangeProof (EQUIVALENT) By using the subterm criterion [SUBTERM_CRITERION] together with the size-change analysis [AAECC05] we have proven that there are no infinite chains for this DP problem. From the DPs we obtained the following set of size-change graphs: *MEMBERA_IN_GG(X1, .(X2, X3)) -> MEMBERA_IN_GG(X1, X3) The graph contains the following edges 1 >= 1, 2 > 2 ---------------------------------------- (11) YES ---------------------------------------- (12) Obligation: Pi DP problem: The TRS P consists of the following rules: PB_IN_AGG(X1, .(X2, X3), X4) -> PB_IN_AGG(X1, X3, X4) R is empty. The argument filtering Pi contains the following mapping: .(x1, x2) = .(x1, x2) PB_IN_AGG(x1, x2, x3) = PB_IN_AGG(x2, x3) We have to consider all (P,R,Pi)-chains ---------------------------------------- (13) PiDPToQDPProof (SOUND) Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. ---------------------------------------- (14) Obligation: Q DP problem: The TRS P consists of the following rules: PB_IN_AGG(.(X2, X3), X4) -> PB_IN_AGG(X3, X4) R is empty. Q is empty. We have to consider all (P,Q,R)-chains. ---------------------------------------- (15) QDPSizeChangeProof (EQUIVALENT) By using the subterm criterion [SUBTERM_CRITERION] together with the size-change analysis [AAECC05] we have proven that there are no infinite chains for this DP problem. From the DPs we obtained the following set of size-change graphs: *PB_IN_AGG(.(X2, X3), X4) -> PB_IN_AGG(X3, X4) The graph contains the following edges 1 > 1, 2 >= 2 ---------------------------------------- (16) YES