/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 add(a,g,a) w.r.t. the given Prolog program could successfully be proven: (0) Prolog (1) PrologToTRSTransformerProof [SOUND, 0 ms] (2) QTRS (3) QTRSRRRProof [EQUIVALENT, 14 ms] (4) QTRS (5) RisEmptyProof [EQUIVALENT, 0 ms] (6) YES ---------------------------------------- (0) Obligation: Clauses: add(X, 0, X). add(X, Y, s(Z)) :- ','(no(zero(Y)), ','(p(Y, P), add(X, P, Z))). p(0, 0). p(s(X), X). zero(0). no(X) :- ','(X, ','(!, failure(a))). no(X). failure(b). Query: add(a,g,a) ---------------------------------------- (1) PrologToTRSTransformerProof (SOUND) Transformed Prolog program to TRS. { "root": 1, "program": { "directives": [], "clauses": [ [ "(add X (0) X)", null ], [ "(add X Y (s Z))", "(',' (no (zero Y)) (',' (p Y P) (add X P Z)))" ], [ "(p (0) (0))", null ], [ "(p (s X) X)", null ], [ "(zero (0))", null ], [ "(no X)", "(',' X (',' (!) (failure (a))))" ], [ "(no X)", null ], [ "(failure (b))", null ] ] }, "graph": { "nodes": { "66": { "goal": [{ "clause": 7, "scope": 5, "term": "(',' (failure (a)) (',' (p (0) X16) (add T18 X16 T19)))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X16"], "exprvars": [] } }, "67": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "68": { "goal": [ { "clause": -1, "scope": 3, "term": null }, { "clause": 6, "scope": 2, "term": "(',' (no (zero T24)) (',' (p T24 X16) (add T18 X16 T19)))" } ], "kb": { "nonunifying": [[ "(zero T24)", "(zero (0))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T24"], "free": ["X16"], "exprvars": [] } }, "69": { "goal": [{ "clause": 6, "scope": 2, "term": "(',' (no (zero T24)) (',' (p T24 X16) (add T18 X16 T19)))" }], "kb": { "nonunifying": [[ "(zero T24)", "(zero (0))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T24"], "free": ["X16"], "exprvars": [] } }, "type": "Nodes", "70": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (p T31 X16) (add T18 X16 T19))" }], "kb": { "nonunifying": [[ "(zero T31)", "(zero (0))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T31"], "free": ["X16"], "exprvars": [] } }, "71": { "goal": [ { "clause": 2, "scope": 6, "term": "(',' (p T31 X16) (add T18 X16 T19))" }, { "clause": 3, "scope": 6, "term": "(',' (p T31 X16) (add T18 X16 T19))" } ], "kb": { "nonunifying": [[ "(zero T31)", "(zero (0))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T31"], "free": ["X16"], "exprvars": [] } }, "72": { "goal": [{ "clause": 3, "scope": 6, "term": "(',' (p T31 X16) (add T18 X16 T19))" }], "kb": { "nonunifying": [[ "(zero T31)", "(zero (0))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T31"], "free": ["X16"], "exprvars": [] } }, "73": { "goal": [{ "clause": -1, "scope": -1, "term": "(add T18 T36 T19)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T36"], "free": [], "exprvars": [] } }, "74": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "54": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "55": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "56": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "57": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (no (zero T16)) (',' (p T16 X16) (add T18 X16 T19)))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T16"], "free": ["X16"], "exprvars": [] } }, "58": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "59": { "goal": [ { "clause": 5, "scope": 2, "term": "(',' (no (zero T16)) (',' (p T16 X16) (add T18 X16 T19)))" }, { "clause": 6, "scope": 2, "term": "(',' (no (zero T16)) (',' (p T16 X16) (add T18 X16 T19)))" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T16"], "free": ["X16"], "exprvars": [] } }, "1": { "goal": [{ "clause": -1, "scope": -1, "term": "(add T1 T2 T3)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T2"], "free": [], "exprvars": [] } }, "2": { "goal": [ { "clause": 0, "scope": 1, "term": "(add T1 T2 T3)" }, { "clause": 1, "scope": 1, "term": "(add T1 T2 T3)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T2"], "free": [], "exprvars": [] } }, "5": { "goal": [{ "clause": 0, "scope": 1, "term": "(add T1 T2 T3)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T2"], "free": [], "exprvars": [] } }, "6": { "goal": [{ "clause": 1, "scope": 1, "term": "(add T1 T2 T3)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T2"], "free": [], "exprvars": [] } }, "60": { "goal": [ { "clause": -1, "scope": -1, "term": "(',' (',' (call (zero T24)) (',' (!_2) (failure (a)))) (',' (p T24 X16) (add T18 X16 T19)))" }, { "clause": 6, "scope": 2, "term": "(',' (no (zero T24)) (',' (p T24 X16) (add T18 X16 T19)))" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T24"], "free": ["X16"], "exprvars": [] } }, "61": { "goal": [ { "clause": -1, "scope": -1, "term": "(',' (zero T24) (',' (',' (!_2) (failure (a))) (',' (p T24 X16) (add T18 X16 T19))))" }, { "clause": -1, "scope": 3, "term": null }, { "clause": 6, "scope": 2, "term": "(',' (no (zero T24)) (',' (p T24 X16) (add T18 X16 T19)))" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T24"], "free": ["X16"], "exprvars": [] } }, "62": { "goal": [ { "clause": 4, "scope": 4, "term": "(',' (zero T24) (',' (',' (!_2) (failure (a))) (',' (p T24 X16) (add T18 X16 T19))))" }, { "clause": -1, "scope": 4, "term": null }, { "clause": -1, "scope": 3, "term": null }, { "clause": 6, "scope": 2, "term": "(',' (no (zero T24)) (',' (p T24 X16) (add T18 X16 T19)))" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T24"], "free": ["X16"], "exprvars": [] } }, "63": { "goal": [ { "clause": -1, "scope": -1, "term": "(',' (',' (!_2) (failure (a))) (',' (p (0) X16) (add T18 X16 T19)))" }, { "clause": -1, "scope": 4, "term": null }, { "clause": -1, "scope": 3, "term": null }, { "clause": 6, "scope": 2, "term": "(',' (no (zero (0))) (',' (p (0) X16) (add T18 X16 T19)))" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X16"], "exprvars": [] } }, "64": { "goal": [ { "clause": -1, "scope": 4, "term": null }, { "clause": -1, "scope": 3, "term": null }, { "clause": 6, "scope": 2, "term": "(',' (no (zero T24)) (',' (p T24 X16) (add T18 X16 T19)))" } ], "kb": { "nonunifying": [[ "(zero T24)", "(zero (0))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T24"], "free": ["X16"], "exprvars": [] } }, "65": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (failure (a)) (',' (p (0) X16) (add T18 X16 T19)))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X16"], "exprvars": [] } } }, "edges": [ { "from": 1, "to": 2, "label": "CASE" }, { "from": 2, "to": 5, "label": "PARALLEL" }, { "from": 2, "to": 6, "label": "PARALLEL" }, { "from": 5, "to": 54, "label": "EVAL with clause\nadd(X5, 0, X5).\nand substitutionT1 -> T8,\nX5 -> T8,\nT2 -> 0,\nT3 -> T8" }, { "from": 5, "to": 55, "label": "EVAL-BACKTRACK" }, { "from": 6, "to": 57, "label": "EVAL with clause\nadd(X13, X14, s(X15)) :- ','(no(zero(X14)), ','(p(X14, X16), add(X13, X16, X15))).\nand substitutionT1 -> T18,\nX13 -> T18,\nT2 -> T16,\nX14 -> T16,\nX15 -> T19,\nT3 -> s(T19),\nT15 -> T18,\nT17 -> T19" }, { "from": 6, "to": 58, "label": "EVAL-BACKTRACK" }, { "from": 54, "to": 56, "label": "SUCCESS" }, { "from": 57, "to": 59, "label": "CASE" }, { "from": 59, "to": 60, "label": "ONLY EVAL with clause\nno(X21) :- ','(call(X21), ','(!_2, failure(a))).\nand substitutionT16 -> T24,\nX21 -> zero(T24)" }, { "from": 60, "to": 61, "label": "CALL" }, { "from": 61, "to": 62, "label": "CASE" }, { "from": 62, "to": 63, "label": "EVAL with clause\nzero(0).\nand substitutionT24 -> 0" }, { "from": 62, "to": 64, "label": "EVAL-BACKTRACK" }, { "from": 63, "to": 65, "label": "CUT" }, { "from": 64, "to": 68, "label": "FAILURE" }, { "from": 65, "to": 66, "label": "CASE" }, { "from": 66, "to": 67, "label": "BACKTRACK\nfor clause: failure(b)because of non-unification" }, { "from": 68, "to": 69, "label": "FAILURE" }, { "from": 69, "to": 70, "label": "ONLY EVAL with clause\nno(X28).\nand substitutionT24 -> T31,\nX28 -> zero(T31)" }, { "from": 70, "to": 71, "label": "CASE" }, { "from": 71, "to": 72, "label": "BACKTRACK\nfor clause: p(0, 0)\nwith clash: (zero(T31), zero(0))" }, { "from": 72, "to": 73, "label": "EVAL with clause\np(s(X33), X33).\nand substitutionX33 -> T36,\nT31 -> s(T36),\nX16 -> T36" }, { "from": 72, "to": 74, "label": "EVAL-BACKTRACK" }, { "from": 73, "to": 1, "label": "INSTANCE with matching:\nT1 -> T18\nT2 -> T36\nT3 -> T19" } ], "type": "Graph" } } ---------------------------------------- (2) Obligation: Q restricted rewrite system: The TRS R consists of the following rules: f1_in(0) -> f1_out1 f1_in(s(T36)) -> U1(f1_in(T36), s(T36)) U1(f1_out1, s(T36)) -> f1_out1 Q is empty. ---------------------------------------- (3) QTRSRRRProof (EQUIVALENT) Used ordering: Polynomial interpretation [POLO]: POL(0) = 1 POL(U1(x_1, x_2)) = x_1 + x_2 POL(f1_in(x_1)) = 1 + 2*x_1 POL(f1_out1) = 0 POL(s(x_1)) = 1 + 2*x_1 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: f1_in(0) -> f1_out1 f1_in(s(T36)) -> U1(f1_in(T36), s(T36)) U1(f1_out1, s(T36)) -> f1_out1 ---------------------------------------- (4) Obligation: Q restricted rewrite system: R is empty. Q is empty. ---------------------------------------- (5) RisEmptyProof (EQUIVALENT) The TRS R is empty. Hence, termination is trivially proven. ---------------------------------------- (6) YES