YES proof of /export/starexec/sandbox2/benchmark/theBenchmark.pl # AProVE Commit ID: 794c25de1cacf0d048858bcd21c9a779e1221865 marcel 20200619 unpublished dirty Left Termination of the query pattern at(a,a) w.r.t. the given Prolog program could successfully be proven: (0) Prolog (1) PrologToIRSwTTransformerProof [SOUND, 0 ms] (2) TRUE ---------------------------------------- (0) Obligation: Clauses: at(X, fido) :- ','(at(X, mary), near(X)). at(ta, mary). at(jm, mary). near(jm). Query: at(a,a) ---------------------------------------- (1) PrologToIRSwTTransformerProof (SOUND) Transformed Prolog program to IRSwT according to method in Master Thesis of A. Weinert { "root": 2, "program": { "directives": [], "clauses": [ [ "(at X (fido))", "(',' (at X (mary)) (near X))" ], [ "(at (ta) (mary))", null ], [ "(at (jm) (mary))", null ], [ "(near (jm))", null ] ] }, "graph": { "nodes": { "23": { "goal": [ { "clause": 1, "scope": 1, "term": "(at T1 T2)" }, { "clause": 2, "scope": 1, "term": "(at T1 T2)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "67": { "goal": [{ "clause": 1, "scope": 1, "term": "(at T1 T2)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "68": { "goal": [{ "clause": 2, "scope": 1, "term": "(at T1 T2)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "27": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (at T8 (mary)) (near T8))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "49": { "goal": [ { "clause": 0, "scope": 2, "term": "(at T8 (mary))" }, { "clause": 1, "scope": 2, "term": "(at T8 (mary))" }, { "clause": 2, "scope": 2, "term": "(at T8 (mary))" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "28": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "type": "Nodes", "71": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "50": { "goal": [ { "clause": 1, "scope": 2, "term": "(at T8 (mary))" }, { "clause": 2, "scope": 2, "term": "(at T8 (mary))" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "51": { "goal": [{ "clause": 1, "scope": 2, "term": "(at T8 (mary))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "73": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "52": { "goal": [{ "clause": 2, "scope": 2, "term": "(at T8 (mary))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "74": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "53": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "54": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "55": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "77": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "78": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "57": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "58": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "59": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "38": { "goal": [{ "clause": -1, "scope": -1, "term": "(at T8 (mary))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "2": { "goal": [{ "clause": -1, "scope": -1, "term": "(at T1 T2)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "6": { "goal": [ { "clause": 0, "scope": 1, "term": "(at T1 T2)" }, { "clause": 1, "scope": 1, "term": "(at T1 T2)" }, { "clause": 2, "scope": 1, "term": "(at T1 T2)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "80": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "60": { "goal": [{ "clause": 3, "scope": 3, "term": "(near T10)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T10"], "free": [], "exprvars": [] } }, "40": { "goal": [{ "clause": -1, "scope": -1, "term": "(near T10)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T10"], "free": [], "exprvars": [] } }, "62": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "63": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "64": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "21": { "goal": [{ "clause": 0, "scope": 1, "term": "(at T1 T2)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } } }, "edges": [ { "from": 2, "to": 6, "label": "CASE" }, { "from": 6, "to": 21, "label": "PARALLEL" }, { "from": 6, "to": 23, "label": "PARALLEL" }, { "from": 21, "to": 27, "label": "EVAL with clause\nat(X5, fido) :- ','(at(X5, mary), near(X5)).\nand substitutionT1 -> T8,\nX5 -> T8,\nT2 -> fido,\nT7 -> T8" }, { "from": 21, "to": 28, "label": "EVAL-BACKTRACK" }, { "from": 23, "to": 67, "label": "PARALLEL" }, { "from": 23, "to": 68, "label": "PARALLEL" }, { "from": 27, "to": 38, "label": "SPLIT 1" }, { "from": 27, "to": 40, "label": "SPLIT 2\nnew knowledge:\nT10 is ground\nreplacements:T8 -> T10" }, { "from": 38, "to": 49, "label": "CASE" }, { "from": 40, "to": 60, "label": "CASE" }, { "from": 49, "to": 50, "label": "BACKTRACK\nfor clause: at(X, fido) :- ','(at(X, mary), near(X))because of non-unification" }, { "from": 50, "to": 51, "label": "PARALLEL" }, { "from": 50, "to": 52, "label": "PARALLEL" }, { "from": 51, "to": 53, "label": "EVAL with clause\nat(ta, mary).\nand substitutionT8 -> ta" }, { "from": 51, "to": 54, "label": "EVAL-BACKTRACK" }, { "from": 52, "to": 57, "label": "EVAL with clause\nat(jm, mary).\nand substitutionT8 -> jm" }, { "from": 52, "to": 58, "label": "EVAL-BACKTRACK" }, { "from": 53, "to": 55, "label": "SUCCESS" }, { "from": 57, "to": 59, "label": "SUCCESS" }, { "from": 60, "to": 62, "label": "EVAL with clause\nnear(jm).\nand substitutionT10 -> jm" }, { "from": 60, "to": 63, "label": "EVAL-BACKTRACK" }, { "from": 62, "to": 64, "label": "SUCCESS" }, { "from": 67, "to": 71, "label": "EVAL with clause\nat(ta, mary).\nand substitutionT1 -> ta,\nT2 -> mary" }, { "from": 67, "to": 73, "label": "EVAL-BACKTRACK" }, { "from": 68, "to": 77, "label": "EVAL with clause\nat(jm, mary).\nand substitutionT1 -> jm,\nT2 -> mary" }, { "from": 68, "to": 78, "label": "EVAL-BACKTRACK" }, { "from": 71, "to": 74, "label": "SUCCESS" }, { "from": 77, "to": 80, "label": "SUCCESS" } ], "type": "Graph" } } ---------------------------------------- (2) TRUE