/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(a) w.r.t. the given Prolog program could successfully be proven: (0) Prolog (1) PrologToIRSwTTransformerProof [SOUND, 0 ms] (2) IRSwT (3) IRSwTSimpleDependencyGraphProof [EQUIVALENT, 0 ms] (4) TRUE ---------------------------------------- (0) Obligation: Clauses: q(X) :- ','(p(s(s(0)), X), r(X)). p(0, 0). p(s(X), s(Y)) :- p(X, Y). r(s(s(0))) :- !. r(X) :- r(X). Query: q(a) ---------------------------------------- (1) PrologToIRSwTTransformerProof (SOUND) Transformed Prolog program to IRSwT according to method in Master Thesis of A. Weinert { "root": 2, "program": { "directives": [], "clauses": [ [ "(q X)", "(',' (p (s (s (0))) X) (r X))" ], [ "(p (0) (0))", null ], [ "(p (s X) (s Y))", "(p X Y)" ], [ "(r (s (s (0))))", "(!)" ], [ "(r X)", "(r X)" ] ] }, "graph": { "nodes": { "44": { "goal": [ { "clause": 1, "scope": 2, "term": "(p (s (s (0))) T6)" }, { "clause": 2, "scope": 2, "term": "(p (s (s (0))) T6)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "45": { "goal": [{ "clause": 2, "scope": 2, "term": "(p (s (s (0))) T6)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "47": { "goal": [{ "clause": -1, "scope": -1, "term": "(p (s (0)) T11)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "48": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "49": { "goal": [ { "clause": 1, "scope": 3, "term": "(p (s (0)) T11)" }, { "clause": 2, "scope": 3, "term": "(p (s (0)) T11)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "type": "Nodes", "50": { "goal": [{ "clause": 2, "scope": 3, "term": "(p (s (0)) T11)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "51": { "goal": [{ "clause": -1, "scope": -1, "term": "(p (0) T15)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "52": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "53": { "goal": [ { "clause": 1, "scope": 4, "term": "(p (0) T15)" }, { "clause": 2, "scope": 4, "term": "(p (0) T15)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "54": { "goal": [{ "clause": 1, "scope": 4, "term": "(p (0) T15)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "55": { "goal": [{ "clause": 2, "scope": 4, "term": "(p (0) T15)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "56": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "57": { "goal": [], "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": [] } }, "2": { "goal": [{ "clause": -1, "scope": -1, "term": "(q T1)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "5": { "goal": [{ "clause": 0, "scope": 1, "term": "(q T1)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "60": { "goal": [ { "clause": 3, "scope": 5, "term": "(r T7)" }, { "clause": 4, "scope": 5, "term": "(r T7)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T7"], "free": [], "exprvars": [] } }, "61": { "goal": [ { "clause": -1, "scope": -1, "term": "(!_5)" }, { "clause": 4, "scope": 5, "term": "(r (s (s (0))))" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "40": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (p (s (s (0))) T6) (r T6))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "62": { "goal": [{ "clause": 4, "scope": 5, "term": "(r T7)" }], "kb": { "nonunifying": [[ "(r T7)", "(r (s (s (0))))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T7"], "free": [], "exprvars": [] } }, "63": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "42": { "goal": [{ "clause": -1, "scope": -1, "term": "(p (s (s (0))) T6)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "64": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "43": { "goal": [{ "clause": -1, "scope": -1, "term": "(r T7)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T7"], "free": [], "exprvars": [] } }, "65": { "goal": [{ "clause": -1, "scope": -1, "term": "(r T19)" }], "kb": { "nonunifying": [[ "(r T19)", "(r (s (s (0))))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T19"], "free": [], "exprvars": [] } } }, "edges": [ { "from": 2, "to": 5, "label": "CASE" }, { "from": 5, "to": 40, "label": "ONLY EVAL with clause\nq(X3) :- ','(p(s(s(0)), X3), r(X3)).\nand substitutionT1 -> T6,\nX3 -> T6,\nT5 -> T6" }, { "from": 40, "to": 42, "label": "SPLIT 1" }, { "from": 40, "to": 43, "label": "SPLIT 2\nnew knowledge:\nT7 is ground\nreplacements:T6 -> T7" }, { "from": 42, "to": 44, "label": "CASE" }, { "from": 43, "to": 60, "label": "CASE" }, { "from": 44, "to": 45, "label": "BACKTRACK\nfor clause: p(0, 0)because of non-unification" }, { "from": 45, "to": 47, "label": "EVAL with clause\np(s(X8), s(X9)) :- p(X8, X9).\nand substitutionX8 -> s(0),\nX9 -> T11,\nT6 -> s(T11),\nT10 -> T11" }, { "from": 45, "to": 48, "label": "EVAL-BACKTRACK" }, { "from": 47, "to": 49, "label": "CASE" }, { "from": 49, "to": 50, "label": "BACKTRACK\nfor clause: p(0, 0)because of non-unification" }, { "from": 50, "to": 51, "label": "EVAL with clause\np(s(X14), s(X15)) :- p(X14, X15).\nand substitutionX14 -> 0,\nX15 -> T15,\nT11 -> s(T15),\nT14 -> T15" }, { "from": 50, "to": 52, "label": "EVAL-BACKTRACK" }, { "from": 51, "to": 53, "label": "CASE" }, { "from": 53, "to": 54, "label": "PARALLEL" }, { "from": 53, "to": 55, "label": "PARALLEL" }, { "from": 54, "to": 56, "label": "EVAL with clause\np(0, 0).\nand substitutionT15 -> 0" }, { "from": 54, "to": 57, "label": "EVAL-BACKTRACK" }, { "from": 55, "to": 59, "label": "BACKTRACK\nfor clause: p(s(X), s(Y)) :- p(X, Y)because of non-unification" }, { "from": 56, "to": 58, "label": "SUCCESS" }, { "from": 60, "to": 61, "label": "EVAL with clause\nr(s(s(0))) :- !_5.\nand substitutionT7 -> s(s(0))" }, { "from": 60, "to": 62, "label": "EVAL-BACKTRACK" }, { "from": 61, "to": 63, "label": "CUT" }, { "from": 62, "to": 65, "label": "ONLY EVAL with clause\nr(X21) :- r(X21).\nand substitutionT7 -> T19,\nX21 -> T19" }, { "from": 63, "to": 64, "label": "SUCCESS" }, { "from": 65, "to": 43, "label": "INSTANCE with matching:\nT7 -> T19" } ], "type": "Graph" } } ---------------------------------------- (2) Obligation: Rules: f62_in(T19) -> f65_in(T19) :|: TRUE f65_out(x) -> f62_out(x) :|: TRUE f65_in(x1) -> f43_in(x1) :|: TRUE f43_out(x2) -> f65_out(x2) :|: TRUE f60_out(T7) -> f43_out(T7) :|: TRUE f43_in(x3) -> f60_in(x3) :|: TRUE f60_in(x4) -> f62_in(x4) :|: TRUE f61_out -> f60_out(s(s(0))) :|: TRUE f60_in(s(s(0))) -> f61_in :|: TRUE f62_out(x5) -> f60_out(x5) :|: TRUE f2_in -> f5_in :|: TRUE f5_out -> f2_out :|: TRUE f40_out -> f5_out :|: TRUE f5_in -> f40_in :|: TRUE f43_out(x6) -> f40_out :|: TRUE f42_out -> f43_in(x7) :|: TRUE f40_in -> f42_in :|: TRUE Start term: f2_in ---------------------------------------- (3) IRSwTSimpleDependencyGraphProof (EQUIVALENT) Constructed simple dependency graph. Simplified to the following IRSwTs: ---------------------------------------- (4) TRUE