/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: 794c25de1cacf0d048858bcd21c9a779e1221865 marcel 20200619 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": 19, "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": { "67": { "goal": [{ "clause": 1, "scope": 2, "term": "(p (s (s (0))))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "68": { "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": [] } }, "37": { "goal": [{ "clause": -1, "scope": -1, "term": "(p (s (s (0))))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "19": { "goal": [{ "clause": -1, "scope": -1, "term": "(q)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "type": "Nodes", "120": { "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": [] } }, "121": { "goal": [{ "clause": 2, "scope": 4, "term": "(p (0))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "122": { "goal": [{ "clause": 3, "scope": 4, "term": "(p (0))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "123": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "124": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "114": { "goal": [{ "clause": -1, "scope": -1, "term": "(p (0))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "125": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "126": { "goal": [{ "clause": 3, "scope": 3, "term": "(p (s (0)))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "127": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "128": { "goal": [{ "clause": 3, "scope": 2, "term": "(p (s (s (0))))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "107": { "goal": [{ "clause": 1, "scope": 3, "term": "(p (s (0)))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "129": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "70": { "goal": [{ "clause": -1, "scope": -1, "term": "(p (s (0)))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "108": { "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": [] } }, "119": { "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": [] } }, "73": { "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": [] } }, "20": { "goal": [{ "clause": 0, "scope": 1, "term": "(q)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "65": { "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": [] } } }, "edges": [ { "from": 19, "to": 20, "label": "CASE" }, { "from": 20, "to": 37, "label": "ONLY EVAL with clause\nq :- p(s(s(0))).\nand substitution" }, { "from": 37, "to": 65, "label": "CASE" }, { "from": 65, "to": 67, "label": "PARALLEL" }, { "from": 65, "to": 68, "label": "PARALLEL" }, { "from": 67, "to": 70, "label": "ONLY EVAL with clause\np(s(X9)) :- p(X9).\nand substitutionX9 -> s(0)" }, { "from": 68, "to": 128, "label": "BACKTRACK\nfor clause: p(0)because of non-unification" }, { "from": 70, "to": 73, "label": "CASE" }, { "from": 73, "to": 107, "label": "PARALLEL" }, { "from": 73, "to": 108, "label": "PARALLEL" }, { "from": 107, "to": 114, "label": "ONLY EVAL with clause\np(s(X17)) :- p(X17).\nand substitutionX17 -> 0" }, { "from": 108, "to": 126, "label": "BACKTRACK\nfor clause: p(0)because of non-unification" }, { "from": 114, "to": 119, "label": "CASE" }, { "from": 119, "to": 120, "label": "BACKTRACK\nfor clause: p(s(X)) :- p(X)because of non-unification" }, { "from": 120, "to": 121, "label": "PARALLEL" }, { "from": 120, "to": 122, "label": "PARALLEL" }, { "from": 121, "to": 123, "label": "ONLY EVAL with clause\np(0).\nand substitution" }, { "from": 122, "to": 125, "label": "BACKTRACK\nfor clause: p(s(s(s(0)))) :- p(s(s(s(0))))because of non-unification" }, { "from": 123, "to": 124, "label": "SUCCESS" }, { "from": 126, "to": 127, "label": "BACKTRACK\nfor clause: p(s(s(s(0)))) :- p(s(s(s(0))))because of non-unification" }, { "from": 128, "to": 129, "label": "BACKTRACK\nfor clause: p(s(s(s(0)))) :- p(s(s(s(0))))because of non-unification" } ], "type": "Graph" } } ---------------------------------------- (2) TRUE