/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 f(a) w.r.t. the given Prolog program could successfully be proven: (0) Prolog (1) PrologToIRSwTTransformerProof [SOUND, 0 ms] (2) TRUE ---------------------------------------- (0) Obligation: Clauses: f(X) :- ','(p(X), q(X)). p(a). p(X) :- ','(p(a), !). q(b). Query: f(a) ---------------------------------------- (1) PrologToIRSwTTransformerProof (SOUND) Transformed Prolog program to IRSwT according to method in Master Thesis of A. Weinert { "root": 2, "program": { "directives": [], "clauses": [ [ "(f X)", "(',' (p X) (q X))" ], [ "(p (a))", null ], [ "(p X)", "(',' (p (a)) (!))" ], [ "(q (b))", null ] ] }, "graph": { "nodes": { "88": { "goal": [{ "clause": -1, "scope": -1, "term": "(p T6)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "23": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (p T6) (q T6))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "89": { "goal": [{ "clause": -1, "scope": -1, "term": "(q T7)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "type": "Nodes", "150": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "151": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (p (a)) (!_2))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "130": { "goal": [ { "clause": -1, "scope": -1, "term": "(true)" }, { "clause": 2, "scope": 2, "term": "(p T6)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "152": { "goal": [ { "clause": 1, "scope": 4, "term": "(',' (p (a)) (!_2))" }, { "clause": 2, "scope": 4, "term": "(',' (p (a)) (!_2))" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "142": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (p (a)) (!_2))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "153": { "goal": [ { "clause": -1, "scope": -1, "term": "(!_2)" }, { "clause": 2, "scope": 4, "term": "(',' (p (a)) (!_2))" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "132": { "goal": [{ "clause": 2, "scope": 2, "term": "(p T6)" }], "kb": { "nonunifying": [[ "(p T6)", "(p (a))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "154": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "155": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "2": { "goal": [{ "clause": -1, "scope": -1, "term": "(f T1)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "156": { "goal": [{ "clause": 3, "scope": 5, "term": "(q T7)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "135": { "goal": [{ "clause": 2, "scope": 2, "term": "(p T6)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "157": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "4": { "goal": [{ "clause": 0, "scope": 1, "term": "(f T1)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "125": { "goal": [ { "clause": 1, "scope": 2, "term": "(p T6)" }, { "clause": 2, "scope": 2, "term": "(p T6)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "147": { "goal": [ { "clause": 1, "scope": 3, "term": "(',' (p (a)) (!_2))" }, { "clause": 2, "scope": 3, "term": "(',' (p (a)) (!_2))" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "158": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "148": { "goal": [ { "clause": -1, "scope": -1, "term": "(!_2)" }, { "clause": 2, "scope": 3, "term": "(',' (p (a)) (!_2))" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "159": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "149": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } } }, "edges": [ { "from": 2, "to": 4, "label": "CASE" }, { "from": 4, "to": 23, "label": "ONLY EVAL with clause\nf(X3) :- ','(p(X3), q(X3)).\nand substitutionT1 -> T6,\nX3 -> T6,\nT5 -> T6" }, { "from": 23, "to": 88, "label": "SPLIT 1" }, { "from": 23, "to": 89, "label": "SPLIT 2\nreplacements:T6 -> T7" }, { "from": 88, "to": 125, "label": "CASE" }, { "from": 89, "to": 156, "label": "CASE" }, { "from": 125, "to": 130, "label": "EVAL with clause\np(a).\nand substitutionT6 -> a" }, { "from": 125, "to": 132, "label": "EVAL-BACKTRACK" }, { "from": 130, "to": 135, "label": "SUCCESS" }, { "from": 132, "to": 151, "label": "ONLY EVAL with clause\np(X9) :- ','(p(a), !_2).\nand substitutionT6 -> T13,\nX9 -> T13" }, { "from": 135, "to": 142, "label": "ONLY EVAL with clause\np(X6) :- ','(p(a), !_2).\nand substitutionT6 -> T10,\nX6 -> T10" }, { "from": 142, "to": 147, "label": "CASE" }, { "from": 147, "to": 148, "label": "ONLY EVAL with clause\np(a).\nand substitution" }, { "from": 148, "to": 149, "label": "CUT" }, { "from": 149, "to": 150, "label": "SUCCESS" }, { "from": 151, "to": 152, "label": "CASE" }, { "from": 152, "to": 153, "label": "ONLY EVAL with clause\np(a).\nand substitution" }, { "from": 153, "to": 154, "label": "CUT" }, { "from": 154, "to": 155, "label": "SUCCESS" }, { "from": 156, "to": 157, "label": "EVAL with clause\nq(b).\nand substitutionT7 -> b" }, { "from": 156, "to": 158, "label": "EVAL-BACKTRACK" }, { "from": 157, "to": 159, "label": "SUCCESS" } ], "type": "Graph" } } ---------------------------------------- (2) TRUE