/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 gopher(g,a) w.r.t. the given Prolog program could successfully be proven: (0) Prolog (1) PrologToDTProblemTransformerProof [SOUND, 64 ms] (2) TRIPLES (3) TriplesToPiDPProof [SOUND, 0 ms] (4) PiDP (5) DependencyGraphProof [EQUIVALENT, 0 ms] (6) TRUE ---------------------------------------- (0) Obligation: Clauses: gopher(nil, L) :- ','(!, eq(L, nil)). gopher(X, Y) :- ','(head(X, nil), ','(!, ','(tail(X, T), eq(Y, cons(nil, T))))). gopher(X, Y) :- ','(head(X, H), ','(head(H, U), ','(tail(H, V), ','(tail(X, W), gopher(cons(U, cons(V, W)), Y))))). head([], X1). head(.(X, X2), X). tail([], []). tail(.(X3, X), X). eq(X, X). Query: gopher(g,a) ---------------------------------------- (1) PrologToDTProblemTransformerProof (SOUND) Built DT problem from termination graph DT10. { "root": 1, "program": { "directives": [], "clauses": [ [ "(gopher (nil) L)", "(',' (!) (eq L (nil)))" ], [ "(gopher X Y)", "(',' (head X (nil)) (',' (!) (',' (tail X T) (eq Y (cons (nil) T)))))" ], [ "(gopher X Y)", "(',' (head X H) (',' (head H U) (',' (tail H V) (',' (tail X W) (gopher (cons U (cons V W)) Y)))))" ], [ "(head ([]) X1)", null ], [ "(head (. X X2) X)", null ], [ "(tail ([]) ([]))", null ], [ "(tail (. X3 X) X)", null ], [ "(eq X X)", null ] ] }, "graph": { "nodes": { "46": { "goal": [ { "clause": 4, "scope": 3, "term": "(',' (head T11 (nil)) (',' (!_1) (',' (tail T11 X13) (eq T13 (cons (nil) X13)))))" }, { "clause": -1, "scope": 3, "term": null }, { "clause": 2, "scope": 1, "term": "(gopher T11 T2)" } ], "kb": { "nonunifying": [ [ "(gopher T11 T2)", "(gopher (nil) X5)" ], [ "(head T11 (nil))", "(head ([]) X16)" ] ], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T11"], "free": [ "X5", "X13", "X16" ], "exprvars": [] } }, "47": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (tail ([]) X13) (eq T13 (cons (nil) X13)))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X13"], "exprvars": [] } }, "48": { "goal": [ { "clause": 5, "scope": 4, "term": "(',' (tail ([]) X13) (eq T13 (cons (nil) X13)))" }, { "clause": 6, "scope": 4, "term": "(',' (tail ([]) X13) (eq T13 (cons (nil) X13)))" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X13"], "exprvars": [] } }, "49": { "goal": [{ "clause": 5, "scope": 4, "term": "(',' (tail ([]) X13) (eq T13 (cons (nil) X13)))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X13"], "exprvars": [] } }, "390": { "goal": [{ "clause": -1, "scope": -1, "term": "(gopher (cons X71 (cons ([]) T48)) T39)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T48"], "free": ["X71"], "exprvars": [] } }, "type": "Nodes", "392": { "goal": [ { "clause": 0, "scope": 12, "term": "(gopher (cons X71 (cons ([]) T48)) T39)" }, { "clause": 1, "scope": 12, "term": "(gopher (cons X71 (cons ([]) T48)) T39)" }, { "clause": 2, "scope": 12, "term": "(gopher (cons X71 (cons ([]) T48)) T39)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T48"], "free": ["X71"], "exprvars": [] } }, "470": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (tail (. T69 T70) X50) (',' (tail (. (. T69 T70) T45) X51) (gopher (cons T69 (cons X50 X51)) T39)))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T45", "T69", "T70" ], "free": [ "X50", "X51" ], "exprvars": [] } }, "394": { "goal": [ { "clause": 1, "scope": 12, "term": "(gopher (cons X71 (cons ([]) T48)) T39)" }, { "clause": 2, "scope": 12, "term": "(gopher (cons X71 (cons ([]) T48)) T39)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T48"], "free": ["X71"], "exprvars": [] } }, "110": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "473": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "111": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "112": { "goal": [{ "clause": 2, "scope": 1, "term": "(gopher T11 T2)" }], "kb": { "nonunifying": [ [ "(gopher T11 T2)", "(gopher (nil) X5)" ], [ "(head T11 (nil))", "(head ([]) X16)" ], [ "(head T11 (nil))", "(head (. X26 X27) X26)" ] ], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T11"], "free": [ "X5", "X16", "X26", "X27" ], "exprvars": [] } }, "398": { "goal": [ { "clause": -1, "scope": -1, "term": "(',' (head (cons X95 (cons ([]) T54)) (nil)) (',' (!_12) (',' (tail (cons X95 (cons ([]) T54)) X94) (eq T56 (cons (nil) X94)))))" }, { "clause": 2, "scope": 12, "term": "(gopher (cons X71 (cons ([]) T54)) T39)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T54"], "free": [ "X71", "X95", "X94" ], "exprvars": [] } }, "278": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (head T37 X48) (',' (head X48 X49) (',' (tail X48 X50) (',' (tail T37 X51) (gopher (cons X49 (cons X50 X51)) T39)))))" }], "kb": { "nonunifying": [ [ "(gopher T37 T2)", "(gopher (nil) X5)" ], [ "(head T37 (nil))", "(head ([]) X16)" ], [ "(head T37 (nil))", "(head (. X26 X27) X26)" ] ], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T37"], "free": [ "X5", "X16", "X26", "X27", "X48", "X49", "X50", "X51" ], "exprvars": [] } }, "311": { "goal": [{ "clause": 6, "scope": 10, "term": "(',' (tail ([]) X50) (',' (tail (. ([]) T45) X51) (gopher (cons X71 (cons X50 X51)) T39)))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T45"], "free": [ "X50", "X51", "X71" ], "exprvars": [] } }, "399": { "goal": [ { "clause": 3, "scope": 13, "term": "(',' (head (cons X95 (cons ([]) T54)) (nil)) (',' (!_12) (',' (tail (cons X95 (cons ([]) T54)) X94) (eq T56 (cons (nil) X94)))))" }, { "clause": 4, "scope": 13, "term": "(',' (head (cons X95 (cons ([]) T54)) (nil)) (',' (!_12) (',' (tail (cons X95 (cons ([]) T54)) X94) (eq T56 (cons (nil) X94)))))" }, { "clause": -1, "scope": 13, "term": null }, { "clause": 2, "scope": 12, "term": "(gopher (cons X71 (cons ([]) T54)) T39)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T54"], "free": [ "X71", "X95", "X94" ], "exprvars": [] } }, "312": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (tail (. ([]) T45) X51) (gopher (cons X71 (cons ([]) X51)) T39))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T45"], "free": [ "X51", "X71" ], "exprvars": [] } }, "313": { "goal": [ { "clause": 5, "scope": 11, "term": "(',' (tail (. ([]) T45) X51) (gopher (cons X71 (cons ([]) X51)) T39))" }, { "clause": 6, "scope": 11, "term": "(',' (tail (. ([]) T45) X51) (gopher (cons X71 (cons ([]) X51)) T39))" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T45"], "free": [ "X51", "X71" ], "exprvars": [] } }, "314": { "goal": [{ "clause": 6, "scope": 11, "term": "(',' (tail (. ([]) T45) X51) (gopher (cons X71 (cons ([]) X51)) T39))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T45"], "free": [ "X51", "X71" ], "exprvars": [] } }, "479": { "goal": [ { "clause": 5, "scope": 15, "term": "(',' (tail (. T69 T70) X50) (',' (tail (. (. T69 T70) T45) X51) (gopher (cons T69 (cons X50 X51)) T39)))" }, { "clause": 6, "scope": 15, "term": "(',' (tail (. T69 T70) X50) (',' (tail (. (. T69 T70) T45) X51) (gopher (cons T69 (cons X50 X51)) T39)))" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T45", "T69", "T70" ], "free": [ "X50", "X51" ], "exprvars": [] } }, "437": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (head (cons X116 (cons ([]) T62)) X112) (',' (head X112 X113) (',' (tail X112 X114) (',' (tail (cons X116 (cons ([]) T62)) X115) (gopher (cons X113 (cons X114 X115)) T64)))))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T62"], "free": [ "X116", "X112", "X113", "X114", "X115" ], "exprvars": [] } }, "50": { "goal": [{ "clause": 6, "scope": 4, "term": "(',' (tail ([]) X13) (eq T13 (cons (nil) X13)))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X13"], "exprvars": [] } }, "96": { "goal": [{ "clause": -1, "scope": -1, "term": "(eq T13 (cons (nil) ([])))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "97": { "goal": [{ "clause": 7, "scope": 5, "term": "(eq T13 (cons (nil) ([])))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "98": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "99": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "283": { "goal": [ { "clause": 3, "scope": 8, "term": "(',' (head T37 X48) (',' (head X48 X49) (',' (tail X48 X50) (',' (tail T37 X51) (gopher (cons X49 (cons X50 X51)) T39)))))" }, { "clause": 4, "scope": 8, "term": "(',' (head T37 X48) (',' (head X48 X49) (',' (tail X48 X50) (',' (tail T37 X51) (gopher (cons X49 (cons X50 X51)) T39)))))" } ], "kb": { "nonunifying": [ [ "(gopher T37 T2)", "(gopher (nil) X5)" ], [ "(head T37 (nil))", "(head ([]) X16)" ], [ "(head T37 (nil))", "(head (. X26 X27) X26)" ] ], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T37"], "free": [ "X5", "X16", "X26", "X27", "X48", "X49", "X50", "X51" ], "exprvars": [] } }, "482": { "goal": [{ "clause": 6, "scope": 15, "term": "(',' (tail (. T69 T70) X50) (',' (tail (. (. T69 T70) T45) X51) (gopher (cons T69 (cons X50 X51)) T39)))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T45", "T69", "T70" ], "free": [ "X50", "X51" ], "exprvars": [] } }, "286": { "goal": [{ "clause": 4, "scope": 8, "term": "(',' (head T37 X48) (',' (head X48 X49) (',' (tail X48 X50) (',' (tail T37 X51) (gopher (cons X49 (cons X50 X51)) T39)))))" }], "kb": { "nonunifying": [ [ "(gopher T37 T2)", "(gopher (nil) X5)" ], [ "(head T37 (nil))", "(head ([]) X16)" ], [ "(head T37 (nil))", "(head (. X26 X27) X26)" ] ], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T37"], "free": [ "X5", "X16", "X26", "X27", "X48", "X49", "X50", "X51" ], "exprvars": [] } }, "1": { "goal": [{ "clause": -1, "scope": -1, "term": "(gopher T1 T2)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T1"], "free": [], "exprvars": [] } }, "3": { "goal": [ { "clause": 0, "scope": 1, "term": "(gopher T1 T2)" }, { "clause": 1, "scope": 1, "term": "(gopher T1 T2)" }, { "clause": 2, "scope": 1, "term": "(gopher T1 T2)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T1"], "free": [], "exprvars": [] } }, "443": { "goal": [ { "clause": 3, "scope": 14, "term": "(',' (head (cons X116 (cons ([]) T62)) X112) (',' (head X112 X113) (',' (tail X112 X114) (',' (tail (cons X116 (cons ([]) T62)) X115) (gopher (cons X113 (cons X114 X115)) T64)))))" }, { "clause": 4, "scope": 14, "term": "(',' (head (cons X116 (cons ([]) T62)) X112) (',' (head X112 X113) (',' (tail X112 X114) (',' (tail (cons X116 (cons ([]) T62)) X115) (gopher (cons X113 (cons X114 X115)) T64)))))" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T62"], "free": [ "X116", "X112", "X113", "X114", "X115" ], "exprvars": [] } }, "400": { "goal": [ { "clause": 4, "scope": 13, "term": "(',' (head (cons X95 (cons ([]) T54)) (nil)) (',' (!_12) (',' (tail (cons X95 (cons ([]) T54)) X94) (eq T56 (cons (nil) X94)))))" }, { "clause": -1, "scope": 13, "term": null }, { "clause": 2, "scope": 12, "term": "(gopher (cons X71 (cons ([]) T54)) T39)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T54"], "free": [ "X71", "X95", "X94" ], "exprvars": [] } }, "402": { "goal": [ { "clause": -1, "scope": 13, "term": null }, { "clause": 2, "scope": 12, "term": "(gopher (cons X71 (cons ([]) T54)) T39)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T54"], "free": ["X71"], "exprvars": [] } }, "446": { "goal": [{ "clause": 4, "scope": 14, "term": "(',' (head (cons X116 (cons ([]) T62)) X112) (',' (head X112 X113) (',' (tail X112 X114) (',' (tail (cons X116 (cons ([]) T62)) X115) (gopher (cons X113 (cons X114 X115)) T64)))))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T62"], "free": [ "X116", "X112", "X113", "X114", "X115" ], "exprvars": [] } }, "524": { "goal": [{ "clause": -1, "scope": -1, "term": "(gopher (cons T83 (cons T84 T85)) T39)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T83", "T84", "T85" ], "free": [], "exprvars": [] } }, "404": { "goal": [{ "clause": 2, "scope": 12, "term": "(gopher (cons X71 (cons ([]) T54)) T39)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T54"], "free": ["X71"], "exprvars": [] } }, "22": { "goal": [ { "clause": -1, "scope": -1, "term": "(',' (!_1) (eq T5 (nil)))" }, { "clause": 1, "scope": 1, "term": "(gopher (nil) T2)" }, { "clause": 2, "scope": 1, "term": "(gopher (nil) T2)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "23": { "goal": [ { "clause": 1, "scope": 1, "term": "(gopher T1 T2)" }, { "clause": 2, "scope": 1, "term": "(gopher T1 T2)" } ], "kb": { "nonunifying": [[ "(gopher T1 T2)", "(gopher (nil) X5)" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T1"], "free": ["X5"], "exprvars": [] } }, "24": { "goal": [{ "clause": -1, "scope": -1, "term": "(eq T5 (nil))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "25": { "goal": [{ "clause": 7, "scope": 2, "term": "(eq T5 (nil))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "26": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "29": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "291": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (head T44 X49) (',' (tail T44 X50) (',' (tail (. T44 T45) X51) (gopher (cons X49 (cons X50 X51)) T39))))" }], "kb": { "nonunifying": [[ "(head (. T44 T45) (nil))", "(head (. X26 X27) X26)" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T44", "T45" ], "free": [ "X26", "X27", "X49", "X50", "X51" ], "exprvars": [] } }, "292": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "294": { "goal": [ { "clause": 3, "scope": 9, "term": "(',' (head T44 X49) (',' (tail T44 X50) (',' (tail (. T44 T45) X51) (gopher (cons X49 (cons X50 X51)) T39))))" }, { "clause": 4, "scope": 9, "term": "(',' (head T44 X49) (',' (tail T44 X50) (',' (tail (. T44 T45) X51) (gopher (cons X49 (cons X50 X51)) T39))))" } ], "kb": { "nonunifying": [[ "(head (. T44 T45) (nil))", "(head (. X26 X27) X26)" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T44", "T45" ], "free": [ "X26", "X27", "X49", "X50", "X51" ], "exprvars": [] } }, "450": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "299": { "goal": [{ "clause": 3, "scope": 9, "term": "(',' (head T44 X49) (',' (tail T44 X50) (',' (tail (. T44 T45) X51) (gopher (cons X49 (cons X50 X51)) T39))))" }], "kb": { "nonunifying": [[ "(head (. T44 T45) (nil))", "(head (. X26 X27) X26)" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T44", "T45" ], "free": [ "X26", "X27", "X49", "X50", "X51" ], "exprvars": [] } }, "455": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "499": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (tail (. (. T75 T76) T45) X51) (gopher (cons T75 (cons T76 X51)) T39))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T45", "T75", "T76" ], "free": ["X51"], "exprvars": [] } }, "30": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "36": { "goal": [ { "clause": -1, "scope": -1, "term": "(',' (head T11 (nil)) (',' (!_1) (',' (tail T11 X13) (eq T13 (cons (nil) X13)))))" }, { "clause": 2, "scope": 1, "term": "(gopher T11 T2)" } ], "kb": { "nonunifying": [[ "(gopher T11 T2)", "(gopher (nil) X5)" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T11"], "free": [ "X5", "X13" ], "exprvars": [] } }, "39": { "goal": [ { "clause": 3, "scope": 3, "term": "(',' (head T11 (nil)) (',' (!_1) (',' (tail T11 X13) (eq T13 (cons (nil) X13)))))" }, { "clause": 4, "scope": 3, "term": "(',' (head T11 (nil)) (',' (!_1) (',' (tail T11 X13) (eq T13 (cons (nil) X13)))))" }, { "clause": -1, "scope": 3, "term": null }, { "clause": 2, "scope": 1, "term": "(gopher T11 T2)" } ], "kb": { "nonunifying": [[ "(gopher T11 T2)", "(gopher (nil) X5)" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T11"], "free": [ "X5", "X13" ], "exprvars": [] } }, "100": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "101": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "102": { "goal": [ { "clause": -1, "scope": -1, "term": "(',' (!_1) (',' (tail (. (nil) T22) X13) (eq T13 (cons (nil) X13))))" }, { "clause": -1, "scope": 3, "term": null }, { "clause": 2, "scope": 1, "term": "(gopher (. (nil) T22) T2)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T22"], "free": ["X13"], "exprvars": [] } }, "300": { "goal": [{ "clause": 4, "scope": 9, "term": "(',' (head T44 X49) (',' (tail T44 X50) (',' (tail (. T44 T45) X51) (gopher (cons X49 (cons X50 X51)) T39))))" }], "kb": { "nonunifying": [[ "(head (. T44 T45) (nil))", "(head (. X26 X27) X26)" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T44", "T45" ], "free": [ "X26", "X27", "X49", "X50", "X51" ], "exprvars": [] } }, "103": { "goal": [ { "clause": -1, "scope": 3, "term": null }, { "clause": 2, "scope": 1, "term": "(gopher T11 T2)" } ], "kb": { "nonunifying": [ [ "(gopher T11 T2)", "(gopher (nil) X5)" ], [ "(head T11 (nil))", "(head ([]) X16)" ], [ "(head T11 (nil))", "(head (. X26 X27) X26)" ] ], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T11"], "free": [ "X5", "X16", "X26", "X27" ], "exprvars": [] } }, "104": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (tail (. (nil) T22) X13) (eq T13 (cons (nil) X13)))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T22"], "free": ["X13"], "exprvars": [] } }, "105": { "goal": [ { "clause": 5, "scope": 6, "term": "(',' (tail (. (nil) T22) X13) (eq T13 (cons (nil) X13)))" }, { "clause": 6, "scope": 6, "term": "(',' (tail (. (nil) T22) X13) (eq T13 (cons (nil) X13)))" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T22"], "free": ["X13"], "exprvars": [] } }, "303": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (tail ([]) X50) (',' (tail (. ([]) T45) X51) (gopher (cons X71 (cons X50 X51)) T39)))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T45"], "free": [ "X50", "X51", "X71" ], "exprvars": [] } }, "106": { "goal": [{ "clause": 6, "scope": 6, "term": "(',' (tail (. (nil) T22) X13) (eq T13 (cons (nil) X13)))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T22"], "free": ["X13"], "exprvars": [] } }, "304": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "107": { "goal": [{ "clause": -1, "scope": -1, "term": "(eq T13 (cons (nil) T25))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T25"], "free": [], "exprvars": [] } }, "503": { "goal": [ { "clause": 5, "scope": 16, "term": "(',' (tail (. (. T75 T76) T45) X51) (gopher (cons T75 (cons T76 X51)) T39))" }, { "clause": 6, "scope": 16, "term": "(',' (tail (. (. T75 T76) T45) X51) (gopher (cons T75 (cons T76 X51)) T39))" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T45", "T75", "T76" ], "free": ["X51"], "exprvars": [] } }, "108": { "goal": [{ "clause": 7, "scope": 7, "term": "(eq T13 (cons (nil) T25))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T25"], "free": [], "exprvars": [] } }, "306": { "goal": [ { "clause": 5, "scope": 10, "term": "(',' (tail ([]) X50) (',' (tail (. ([]) T45) X51) (gopher (cons X71 (cons X50 X51)) T39)))" }, { "clause": 6, "scope": 10, "term": "(',' (tail ([]) X50) (',' (tail (. ([]) T45) X51) (gopher (cons X71 (cons X50 X51)) T39)))" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T45"], "free": [ "X50", "X51", "X71" ], "exprvars": [] } }, "109": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "309": { "goal": [{ "clause": 5, "scope": 10, "term": "(',' (tail ([]) X50) (',' (tail (. ([]) T45) X51) (gopher (cons X71 (cons X50 X51)) T39)))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T45"], "free": [ "X50", "X51", "X71" ], "exprvars": [] } }, "507": { "goal": [{ "clause": 6, "scope": 16, "term": "(',' (tail (. (. T75 T76) T45) X51) (gopher (cons T75 (cons T76 X51)) T39))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T45", "T75", "T76" ], "free": ["X51"], "exprvars": [] } }, "42": { "goal": [ { "clause": -1, "scope": -1, "term": "(',' (!_1) (',' (tail ([]) X13) (eq T13 (cons (nil) X13))))" }, { "clause": 4, "scope": 3, "term": "(',' (head ([]) (nil)) (',' (!_1) (',' (tail ([]) X13) (eq T13 (cons (nil) X13)))))" }, { "clause": -1, "scope": 3, "term": null }, { "clause": 2, "scope": 1, "term": "(gopher ([]) T2)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X13"], "exprvars": [] } } }, "edges": [ { "from": 1, "to": 3, "label": "CASE" }, { "from": 3, "to": 22, "label": "EVAL with clause\ngopher(nil, X5) :- ','(!_1, eq(X5, nil)).\nand substitutionT1 -> nil,\nT2 -> T5,\nX5 -> T5,\nT4 -> T5" }, { "from": 3, "to": 23, "label": "EVAL-BACKTRACK" }, { "from": 22, "to": 24, "label": "CUT" }, { "from": 23, "to": 36, "label": "ONLY EVAL with clause\ngopher(X11, X12) :- ','(head(X11, nil), ','(!_1, ','(tail(X11, X13), eq(X12, cons(nil, X13))))).\nand substitutionT1 -> T11,\nX11 -> T11,\nT2 -> T13,\nX12 -> T13,\nT12 -> T13" }, { "from": 24, "to": 25, "label": "CASE" }, { "from": 25, "to": 26, "label": "EVAL with clause\neq(X8, X8).\nand substitutionT5 -> nil,\nX8 -> nil,\nT8 -> nil" }, { "from": 25, "to": 29, "label": "EVAL-BACKTRACK" }, { "from": 26, "to": 30, "label": "SUCCESS" }, { "from": 36, "to": 39, "label": "CASE" }, { "from": 39, "to": 42, "label": "EVAL with clause\nhead([], X16).\nand substitutionT11 -> [],\nX16 -> nil" }, { "from": 39, "to": 46, "label": "EVAL-BACKTRACK" }, { "from": 42, "to": 47, "label": "CUT" }, { "from": 46, "to": 102, "label": "EVAL with clause\nhead(.(X26, X27), X26).\nand substitutionX26 -> nil,\nX27 -> T22,\nT11 -> .(nil, T22),\nT21 -> nil" }, { "from": 46, "to": 103, "label": "EVAL-BACKTRACK" }, { "from": 47, "to": 48, "label": "CASE" }, { "from": 48, "to": 49, "label": "PARALLEL" }, { "from": 48, "to": 50, "label": "PARALLEL" }, { "from": 49, "to": 96, "label": "ONLY EVAL with clause\ntail([], []).\nand substitutionX13 -> []" }, { "from": 50, "to": 101, "label": "BACKTRACK\nfor clause: tail(.(X3, X), X)because of non-unification" }, { "from": 96, "to": 97, "label": "CASE" }, { "from": 97, "to": 98, "label": "EVAL with clause\neq(X19, X19).\nand substitutionT13 -> cons(nil, []),\nX19 -> cons(nil, []),\nT16 -> cons(nil, [])" }, { "from": 97, "to": 99, "label": "EVAL-BACKTRACK" }, { "from": 98, "to": 100, "label": "SUCCESS" }, { "from": 102, "to": 104, "label": "CUT" }, { "from": 103, "to": 112, "label": "FAILURE" }, { "from": 104, "to": 105, "label": "CASE" }, { "from": 105, "to": 106, "label": "BACKTRACK\nfor clause: tail([], [])because of non-unification" }, { "from": 106, "to": 107, "label": "ONLY EVAL with clause\ntail(.(X32, X33), X33).\nand substitutionX32 -> nil,\nT22 -> T25,\nX33 -> T25,\nX13 -> T25" }, { "from": 107, "to": 108, "label": "CASE" }, { "from": 108, "to": 109, "label": "EVAL with clause\neq(X36, X36).\nand substitutionT13 -> cons(nil, T31),\nX36 -> cons(nil, T31),\nT25 -> T31,\nT30 -> cons(nil, T31)" }, { "from": 108, "to": 110, "label": "EVAL-BACKTRACK" }, { "from": 109, "to": 111, "label": "SUCCESS" }, { "from": 112, "to": 278, "label": "ONLY EVAL with clause\ngopher(X46, X47) :- ','(head(X46, X48), ','(head(X48, X49), ','(tail(X48, X50), ','(tail(X46, X51), gopher(cons(X49, cons(X50, X51)), X47))))).\nand substitutionT11 -> T37,\nX46 -> T37,\nT2 -> T39,\nX47 -> T39,\nT38 -> T39" }, { "from": 278, "to": 283, "label": "CASE" }, { "from": 283, "to": 286, "label": "BACKTRACK\nfor clause: head([], X1)\nwith clash: (head(T37, nil), head([], X16))" }, { "from": 286, "to": 291, "label": "EVAL with clause\nhead(.(X59, X60), X59).\nand substitutionX59 -> T44,\nX60 -> T45,\nT37 -> .(T44, T45),\nX48 -> T44" }, { "from": 286, "to": 292, "label": "EVAL-BACKTRACK" }, { "from": 291, "to": 294, "label": "CASE" }, { "from": 294, "to": 299, "label": "PARALLEL" }, { "from": 294, "to": 300, "label": "PARALLEL" }, { "from": 299, "to": 303, "label": "EVAL with clause\nhead([], X70).\nand substitutionT44 -> [],\nX49 -> X71,\nX70 -> X71" }, { "from": 299, "to": 304, "label": "EVAL-BACKTRACK" }, { "from": 300, "to": 470, "label": "EVAL with clause\nhead(.(X127, X128), X127).\nand substitutionX127 -> T69,\nX128 -> T70,\nT44 -> .(T69, T70),\nX49 -> T69" }, { "from": 300, "to": 473, "label": "EVAL-BACKTRACK" }, { "from": 303, "to": 306, "label": "CASE" }, { "from": 306, "to": 309, "label": "PARALLEL" }, { "from": 306, "to": 311, "label": "PARALLEL" }, { "from": 309, "to": 312, "label": "ONLY EVAL with clause\ntail([], []).\nand substitutionX50 -> []" }, { "from": 311, "to": 455, "label": "BACKTRACK\nfor clause: tail(.(X3, X), X)because of non-unification" }, { "from": 312, "to": 313, "label": "CASE" }, { "from": 313, "to": 314, "label": "BACKTRACK\nfor clause: tail([], [])because of non-unification" }, { "from": 314, "to": 390, "label": "ONLY EVAL with clause\ntail(.(X81, X82), X82).\nand substitutionX81 -> [],\nT45 -> T48,\nX82 -> T48,\nX51 -> T48" }, { "from": 390, "to": 392, "label": "CASE" }, { "from": 392, "to": 394, "label": "BACKTRACK\nfor clause: gopher(nil, L) :- ','(!, eq(L, nil))because of non-unification" }, { "from": 394, "to": 398, "label": "ONLY EVAL with clause\ngopher(X92, X93) :- ','(head(X92, nil), ','(!_12, ','(tail(X92, X94), eq(X93, cons(nil, X94))))).\nand substitutionX71 -> X95,\nT48 -> T54,\nX92 -> cons(X95, cons([], T54)),\nT39 -> T56,\nX93 -> T56,\nT55 -> T56" }, { "from": 398, "to": 399, "label": "CASE" }, { "from": 399, "to": 400, "label": "BACKTRACK\nfor clause: head([], X1)because of non-unification" }, { "from": 400, "to": 402, "label": "BACKTRACK\nfor clause: head(.(X, X2), X)because of non-unification" }, { "from": 402, "to": 404, "label": "FAILURE" }, { "from": 404, "to": 437, "label": "ONLY EVAL with clause\ngopher(X110, X111) :- ','(head(X110, X112), ','(head(X112, X113), ','(tail(X112, X114), ','(tail(X110, X115), gopher(cons(X113, cons(X114, X115)), X111))))).\nand substitutionX71 -> X116,\nT54 -> T62,\nX110 -> cons(X116, cons([], T62)),\nT39 -> T64,\nX111 -> T64,\nT63 -> T64" }, { "from": 437, "to": 443, "label": "CASE" }, { "from": 443, "to": 446, "label": "BACKTRACK\nfor clause: head([], X1)because of non-unification" }, { "from": 446, "to": 450, "label": "BACKTRACK\nfor clause: head(.(X, X2), X)because of non-unification" }, { "from": 470, "to": 479, "label": "CASE" }, { "from": 479, "to": 482, "label": "BACKTRACK\nfor clause: tail([], [])because of non-unification" }, { "from": 482, "to": 499, "label": "ONLY EVAL with clause\ntail(.(X135, X136), X136).\nand substitutionT69 -> T75,\nX135 -> T75,\nT70 -> T76,\nX136 -> T76,\nX50 -> T76" }, { "from": 499, "to": 503, "label": "CASE" }, { "from": 503, "to": 507, "label": "BACKTRACK\nfor clause: tail([], [])because of non-unification" }, { "from": 507, "to": 524, "label": "ONLY EVAL with clause\ntail(.(X143, X144), X144).\nand substitutionT75 -> T83,\nT76 -> T84,\nX143 -> .(T83, T84),\nT45 -> T85,\nX144 -> T85,\nX51 -> T85" }, { "from": 524, "to": 1, "label": "INSTANCE with matching:\nT1 -> cons(T83, cons(T84, T85))\nT2 -> T39" } ], "type": "Graph" } } ---------------------------------------- (2) Obligation: Triples: gopherA(.(.(X1, X2), X3), X4) :- gopherA(cons(X1, cons(X2, X3)), X4). Clauses: gophercA(nil, nil). gophercA([], cons(nil, [])). gophercA(.(nil, X1), cons(nil, X1)). gophercA(.(.(X1, X2), X3), X4) :- gophercA(cons(X1, cons(X2, X3)), X4). Afs: gopherA(x1, x2) = gopherA(x1) ---------------------------------------- (3) TriplesToPiDPProof (SOUND) We use the technique of [DT09]. With regard to the inferred argument filtering the predicates were used in the following modes: gopherA_in_2: (b,f) Transforming TRIPLES into the following Term Rewriting System: Pi DP problem: The TRS P consists of the following rules: GOPHERA_IN_GA(.(.(X1, X2), X3), X4) -> U1_GA(X1, X2, X3, X4, gopherA_in_ga(cons(X1, cons(X2, X3)), X4)) GOPHERA_IN_GA(.(.(X1, X2), X3), X4) -> GOPHERA_IN_GA(cons(X1, cons(X2, X3)), X4) R is empty. The argument filtering Pi contains the following mapping: gopherA_in_ga(x1, x2) = gopherA_in_ga(x1) .(x1, x2) = .(x1, x2) cons(x1, x2) = cons(x1, x2) GOPHERA_IN_GA(x1, x2) = GOPHERA_IN_GA(x1) U1_GA(x1, x2, x3, x4, x5) = U1_GA(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: GOPHERA_IN_GA(.(.(X1, X2), X3), X4) -> U1_GA(X1, X2, X3, X4, gopherA_in_ga(cons(X1, cons(X2, X3)), X4)) GOPHERA_IN_GA(.(.(X1, X2), X3), X4) -> GOPHERA_IN_GA(cons(X1, cons(X2, X3)), X4) R is empty. The argument filtering Pi contains the following mapping: gopherA_in_ga(x1, x2) = gopherA_in_ga(x1) .(x1, x2) = .(x1, x2) cons(x1, x2) = cons(x1, x2) GOPHERA_IN_GA(x1, x2) = GOPHERA_IN_GA(x1) U1_GA(x1, x2, x3, x4, x5) = U1_GA(x1, x2, x3, x5) We have to consider all (P,R,Pi)-chains ---------------------------------------- (5) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LOPSTR] contains 0 SCCs with 2 less nodes. ---------------------------------------- (6) TRUE