/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 p(a) w.r.t. the given Prolog program could successfully be proven: (0) Prolog (1) BuiltinConflictTransformerProof [EQUIVALENT, 0 ms] (2) Prolog (3) PrologToIRSwTTransformerProof [SOUND, 0 ms] (4) TRUE ---------------------------------------- (0) Obligation: Clauses: p(X) :- ','(q(X), r(X)). p(X) :- =(X, 2). q(X) :- ','(=(X, 1), !). q(X) :- =(X, 3). r(X) :- ','(=(X, 1), !). r(X) :- =(X, 4). =(X, X). Query: p(a) ---------------------------------------- (1) BuiltinConflictTransformerProof (EQUIVALENT) Renamed defined predicates conflicting with built-in predicates [PROLOG]. ---------------------------------------- (2) Obligation: Clauses: p(X) :- ','(q(X), r(X)). p(X) :- user_defined_=(X, 2). q(X) :- ','(user_defined_=(X, 1), !). q(X) :- user_defined_=(X, 3). r(X) :- ','(user_defined_=(X, 1), !). r(X) :- user_defined_=(X, 4). user_defined_=(X, X). Query: p(a) ---------------------------------------- (3) PrologToIRSwTTransformerProof (SOUND) Transformed Prolog program to IRSwT according to method in Master Thesis of A. Weinert { "root": 2, "program": { "directives": [], "clauses": [ [ "(p X)", "(',' (q X) (r X))" ], [ "(p X)", "(user_defined_= X (2))" ], [ "(q X)", "(',' (user_defined_= X (1)) (!))" ], [ "(q X)", "(user_defined_= X (3))" ], [ "(r X)", "(',' (user_defined_= X (1)) (!))" ], [ "(r X)", "(user_defined_= X (4))" ], [ "(user_defined_= X X)", null ] ] }, "graph": { "nodes": { "type": "Nodes", "150": { "goal": [ { "clause": -1, "scope": 3, "term": null }, { "clause": 3, "scope": 2, "term": "(',' (q T9) (r T9))" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "250": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "251": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "230": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "252": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "231": { "goal": [ { "clause": 4, "scope": 7, "term": "(r (3))" }, { "clause": 5, "scope": 7, "term": "(r (3))" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "211": { "goal": [ { "clause": -1, "scope": -1, "term": "(!_4)" }, { "clause": -1, "scope": 5, "term": null }, { "clause": 5, "scope": 4, "term": "(r (1))" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "233": { "goal": [ { "clause": -1, "scope": -1, "term": "(',' (user_defined_= (3) (1)) (!_7))" }, { "clause": 5, "scope": 7, "term": "(r (3))" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "212": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "234": { "goal": [ { "clause": 6, "scope": 8, "term": "(',' (user_defined_= (3) (1)) (!_7))" }, { "clause": -1, "scope": 8, "term": null }, { "clause": 5, "scope": 7, "term": "(r (3))" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "214": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "236": { "goal": [ { "clause": -1, "scope": 8, "term": null }, { "clause": 5, "scope": 7, "term": "(r (3))" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "237": { "goal": [{ "clause": 5, "scope": 7, "term": "(r (3))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "218": { "goal": [{ "clause": 3, "scope": 2, "term": "(',' (q T9) (r T9))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "240": { "goal": [{ "clause": -1, "scope": -1, "term": "(user_defined_= (3) (4))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "142": { "goal": [ { "clause": 0, "scope": 1, "term": "(p T1)" }, { "clause": 1, "scope": 1, "term": "(p T1)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "241": { "goal": [{ "clause": 6, "scope": 9, "term": "(user_defined_= (3) (4))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "143": { "goal": [{ "clause": 0, "scope": 1, "term": "(p T1)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "242": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "144": { "goal": [{ "clause": 1, "scope": 1, "term": "(p T1)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "2": { "goal": [{ "clause": -1, "scope": -1, "term": "(p T1)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "145": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (q T9) (r T9))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "146": { "goal": [ { "clause": 2, "scope": 2, "term": "(',' (q T9) (r T9))" }, { "clause": 3, "scope": 2, "term": "(',' (q T9) (r T9))" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "201": { "goal": [{ "clause": -1, "scope": -1, "term": "(r (1))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "245": { "goal": [{ "clause": -1, "scope": -1, "term": "(user_defined_= T30 (2))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "147": { "goal": [ { "clause": -1, "scope": -1, "term": "(',' (',' (user_defined_= T14 (1)) (!_2)) (r T14))" }, { "clause": 3, "scope": 2, "term": "(',' (q T9) (r T9))" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "202": { "goal": [ { "clause": 4, "scope": 4, "term": "(r (1))" }, { "clause": 5, "scope": 4, "term": "(r (1))" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "224": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (user_defined_= T22 (3)) (r T22))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "246": { "goal": [{ "clause": 6, "scope": 10, "term": "(user_defined_= T30 (2))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "148": { "goal": [ { "clause": 6, "scope": 3, "term": "(',' (',' (user_defined_= T14 (1)) (!_2)) (r T14))" }, { "clause": -1, "scope": 3, "term": null }, { "clause": 3, "scope": 2, "term": "(',' (q T9) (r T9))" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "225": { "goal": [{ "clause": 6, "scope": 6, "term": "(',' (user_defined_= T22 (3)) (r T22))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "149": { "goal": [ { "clause": -1, "scope": -1, "term": "(',' (!_2) (r (1)))" }, { "clause": -1, "scope": 3, "term": null }, { "clause": 3, "scope": 2, "term": "(',' (q T9) (r T9))" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "228": { "goal": [{ "clause": -1, "scope": -1, "term": "(r (3))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "207": { "goal": [ { "clause": -1, "scope": -1, "term": "(',' (user_defined_= (1) (1)) (!_4))" }, { "clause": 5, "scope": 4, "term": "(r (1))" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "208": { "goal": [ { "clause": 6, "scope": 5, "term": "(',' (user_defined_= (1) (1)) (!_4))" }, { "clause": -1, "scope": 5, "term": null }, { "clause": 5, "scope": 4, "term": "(r (1))" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } } }, "edges": [ { "from": 2, "to": 142, "label": "CASE" }, { "from": 142, "to": 143, "label": "PARALLEL" }, { "from": 142, "to": 144, "label": "PARALLEL" }, { "from": 143, "to": 145, "label": "ONLY EVAL with clause\np(X5) :- ','(q(X5), r(X5)).\nand substitutionT1 -> T9,\nX5 -> T9,\nT8 -> T9" }, { "from": 144, "to": 245, "label": "ONLY EVAL with clause\np(X34) :- user_defined_=(X34, 2).\nand substitutionT1 -> T30,\nX34 -> T30,\nT29 -> T30" }, { "from": 145, "to": 146, "label": "CASE" }, { "from": 146, "to": 147, "label": "ONLY EVAL with clause\nq(X8) :- ','(user_defined_=(X8, 1), !_2).\nand substitutionT9 -> T14,\nX8 -> T14,\nT13 -> T14" }, { "from": 147, "to": 148, "label": "CASE" }, { "from": 148, "to": 149, "label": "EVAL with clause\nuser_defined_=(X11, X11).\nand substitutionT14 -> 1,\nX11 -> 1,\nT17 -> 1" }, { "from": 148, "to": 150, "label": "EVAL-BACKTRACK" }, { "from": 149, "to": 201, "label": "CUT" }, { "from": 150, "to": 218, "label": "FAILURE" }, { "from": 201, "to": 202, "label": "CASE" }, { "from": 202, "to": 207, "label": "ONLY EVAL with clause\nr(X14) :- ','(user_defined_=(X14, 1), !_4).\nand substitutionX14 -> 1" }, { "from": 207, "to": 208, "label": "CASE" }, { "from": 208, "to": 211, "label": "ONLY EVAL with clause\nuser_defined_=(X17, X17).\nand substitutionX17 -> 1" }, { "from": 211, "to": 212, "label": "CUT" }, { "from": 212, "to": 214, "label": "SUCCESS" }, { "from": 218, "to": 224, "label": "ONLY EVAL with clause\nq(X20) :- user_defined_=(X20, 3).\nand substitutionT9 -> T22,\nX20 -> T22,\nT21 -> T22" }, { "from": 224, "to": 225, "label": "CASE" }, { "from": 225, "to": 228, "label": "EVAL with clause\nuser_defined_=(X23, X23).\nand substitutionT22 -> 3,\nX23 -> 3,\nT25 -> 3" }, { "from": 225, "to": 230, "label": "EVAL-BACKTRACK" }, { "from": 228, "to": 231, "label": "CASE" }, { "from": 231, "to": 233, "label": "ONLY EVAL with clause\nr(X26) :- ','(user_defined_=(X26, 1), !_7).\nand substitutionX26 -> 3" }, { "from": 233, "to": 234, "label": "CASE" }, { "from": 234, "to": 236, "label": "BACKTRACK\nfor clause: user_defined_=(X, X)because of non-unification" }, { "from": 236, "to": 237, "label": "FAILURE" }, { "from": 237, "to": 240, "label": "ONLY EVAL with clause\nr(X30) :- user_defined_=(X30, 4).\nand substitutionX30 -> 3" }, { "from": 240, "to": 241, "label": "CASE" }, { "from": 241, "to": 242, "label": "BACKTRACK\nfor clause: user_defined_=(X, X)because of non-unification" }, { "from": 245, "to": 246, "label": "CASE" }, { "from": 246, "to": 250, "label": "EVAL with clause\nuser_defined_=(X37, X37).\nand substitutionT30 -> 2,\nX37 -> 2,\nT33 -> 2" }, { "from": 246, "to": 251, "label": "EVAL-BACKTRACK" }, { "from": 250, "to": 252, "label": "SUCCESS" } ], "type": "Graph" } } ---------------------------------------- (4) TRUE