/export/starexec/sandbox/solver/bin/starexec_run_standard /export/starexec/sandbox/benchmark/theBenchmark.pl /export/starexec/sandbox/output/output_files -------------------------------------------------------------------------------- YES proof of /export/starexec/sandbox/benchmark/theBenchmark.pl # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty Left Termination of the query pattern q() w.r.t. the given Prolog program could successfully be proven: (0) Prolog (1) PrologToIRSwTTransformerProof [SOUND, 0 ms] (2) TRUE ---------------------------------------- (0) Obligation: Clauses: q :- p(s(s(0))). p(s(X)) :- p(X). p(0). p(s(s(s(0)))) :- p(s(s(s(0)))). Query: q() ---------------------------------------- (1) PrologToIRSwTTransformerProof (SOUND) Transformed Prolog program to IRSwT according to method in Master Thesis of A. Weinert { "root": 12, "program": { "directives": [], "clauses": [ [ "(q)", "(p (s (s (0))))" ], [ "(p (s X))", "(p X)" ], [ "(p (0))", null ], [ "(p (s (s (s (0)))))", "(p (s (s (s (0)))))" ] ] }, "graph": { "nodes": { "88": { "goal": [{ "clause": 1, "scope": 3, "term": "(p (s (0)))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "12": { "goal": [{ "clause": -1, "scope": -1, "term": "(q)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "78": { "goal": [{ "clause": -1, "scope": -1, "term": "(p (s (0)))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "89": { "goal": [ { "clause": 2, "scope": 3, "term": "(p (s (0)))" }, { "clause": 3, "scope": 3, "term": "(p (s (0)))" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "13": { "goal": [{ "clause": 0, "scope": 1, "term": "(q)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "49": { "goal": [{ "clause": -1, "scope": -1, "term": "(p (s (s (0))))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "type": "Nodes", "110": { "goal": [{ "clause": 3, "scope": 2, "term": "(p (s (s (0))))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "111": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "103": { "goal": [{ "clause": 2, "scope": 4, "term": "(p (0))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "104": { "goal": [{ "clause": 3, "scope": 4, "term": "(p (0))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "105": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "106": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "80": { "goal": [ { "clause": 1, "scope": 3, "term": "(p (s (0)))" }, { "clause": 2, "scope": 3, "term": "(p (s (0)))" }, { "clause": 3, "scope": 3, "term": "(p (s (0)))" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "107": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "92": { "goal": [{ "clause": -1, "scope": -1, "term": "(p (0))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "108": { "goal": [{ "clause": 3, "scope": 3, "term": "(p (s (0)))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "109": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "72": { "goal": [ { "clause": 1, "scope": 2, "term": "(p (s (s (0))))" }, { "clause": 2, "scope": 2, "term": "(p (s (s (0))))" }, { "clause": 3, "scope": 2, "term": "(p (s (s (0))))" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "94": { "goal": [ { "clause": 1, "scope": 4, "term": "(p (0))" }, { "clause": 2, "scope": 4, "term": "(p (0))" }, { "clause": 3, "scope": 4, "term": "(p (0))" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "95": { "goal": [ { "clause": 2, "scope": 4, "term": "(p (0))" }, { "clause": 3, "scope": 4, "term": "(p (0))" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "75": { "goal": [{ "clause": 1, "scope": 2, "term": "(p (s (s (0))))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "76": { "goal": [ { "clause": 2, "scope": 2, "term": "(p (s (s (0))))" }, { "clause": 3, "scope": 2, "term": "(p (s (s (0))))" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } } }, "edges": [ { "from": 12, "to": 13, "label": "CASE" }, { "from": 13, "to": 49, "label": "ONLY EVAL with clause\nq :- p(s(s(0))).\nand substitution" }, { "from": 49, "to": 72, "label": "CASE" }, { "from": 72, "to": 75, "label": "PARALLEL" }, { "from": 72, "to": 76, "label": "PARALLEL" }, { "from": 75, "to": 78, "label": "ONLY EVAL with clause\np(s(X9)) :- p(X9).\nand substitutionX9 -> s(0)" }, { "from": 76, "to": 110, "label": "BACKTRACK\nfor clause: p(0)because of non-unification" }, { "from": 78, "to": 80, "label": "CASE" }, { "from": 80, "to": 88, "label": "PARALLEL" }, { "from": 80, "to": 89, "label": "PARALLEL" }, { "from": 88, "to": 92, "label": "ONLY EVAL with clause\np(s(X17)) :- p(X17).\nand substitutionX17 -> 0" }, { "from": 89, "to": 108, "label": "BACKTRACK\nfor clause: p(0)because of non-unification" }, { "from": 92, "to": 94, "label": "CASE" }, { "from": 94, "to": 95, "label": "BACKTRACK\nfor clause: p(s(X)) :- p(X)because of non-unification" }, { "from": 95, "to": 103, "label": "PARALLEL" }, { "from": 95, "to": 104, "label": "PARALLEL" }, { "from": 103, "to": 105, "label": "ONLY EVAL with clause\np(0).\nand substitution" }, { "from": 104, "to": 107, "label": "BACKTRACK\nfor clause: p(s(s(s(0)))) :- p(s(s(s(0))))because of non-unification" }, { "from": 105, "to": 106, "label": "SUCCESS" }, { "from": 108, "to": 109, "label": "BACKTRACK\nfor clause: p(s(s(s(0)))) :- p(s(s(s(0))))because of non-unification" }, { "from": 110, "to": 111, "label": "BACKTRACK\nfor clause: p(s(s(s(0)))) :- p(s(s(s(0))))because of non-unification" } ], "type": "Graph" } } ---------------------------------------- (2) TRUE