YES proof of /export/starexec/sandbox2/benchmark/theBenchmark.pl # AProVE Commit ID: 794c25de1cacf0d048858bcd21c9a779e1221865 marcel 20200619 unpublished dirty Left Termination of the query pattern f(g,a,a) w.r.t. the given Prolog program could successfully be proven: (0) Prolog (1) PrologToTRSTransformerProof [SOUND, 0 ms] (2) QTRS (3) QTRSRRRProof [EQUIVALENT, 63 ms] (4) QTRS (5) RisEmptyProof [EQUIVALENT, 0 ms] (6) YES ---------------------------------------- (0) Obligation: Clauses: f(0, Y, 0). f(s(X), Y, Z) :- ','(f(X, Y, U), f(U, Y, Z)). Query: f(g,a,a) ---------------------------------------- (1) PrologToTRSTransformerProof (SOUND) Transformed Prolog program to TRS. { "root": 3, "program": { "directives": [], "clauses": [ [ "(f (0) Y (0))", null ], [ "(f (s X) Y Z)", "(',' (f X Y U) (f U Y Z))" ] ] }, "graph": { "nodes": { "11": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "13": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "3": { "goal": [{ "clause": -1, "scope": -1, "term": "(f T1 T2 T3)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T1"], "free": [], "exprvars": [] } }, "4": { "goal": [ { "clause": 0, "scope": 1, "term": "(f T1 T2 T3)" }, { "clause": 1, "scope": 1, "term": "(f T1 T2 T3)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T1"], "free": [], "exprvars": [] } }, "15": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "27": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "6": { "goal": [{ "clause": 0, "scope": 1, "term": "(f T1 T2 T3)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T1"], "free": [], "exprvars": [] } }, "7": { "goal": [{ "clause": 1, "scope": 1, "term": "(f T1 T2 T3)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T1"], "free": [], "exprvars": [] } }, "18": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (f T15 T18 X16) (f X16 T18 T19))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T15"], "free": ["X16"], "exprvars": [] } }, "type": "Nodes", "40": { "goal": [{ "clause": -1, "scope": -1, "term": "(f T15 T18 X16)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T15"], "free": ["X16"], "exprvars": [] } }, "41": { "goal": [{ "clause": -1, "scope": -1, "term": "(f T22 T23 T24)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T22"], "free": [], "exprvars": [] } } }, "edges": [ { "from": 3, "to": 4, "label": "CASE" }, { "from": 4, "to": 6, "label": "PARALLEL" }, { "from": 4, "to": 7, "label": "PARALLEL" }, { "from": 6, "to": 11, "label": "EVAL with clause\nf(0, X5, 0).\nand substitutionT1 -> 0,\nT2 -> T8,\nX5 -> T8,\nT3 -> 0" }, { "from": 6, "to": 13, "label": "EVAL-BACKTRACK" }, { "from": 7, "to": 18, "label": "EVAL with clause\nf(s(X13), X14, X15) :- ','(f(X13, X14, X16), f(X16, X14, X15)).\nand substitutionX13 -> T15,\nT1 -> s(T15),\nT2 -> T18,\nX14 -> T18,\nT3 -> T19,\nX15 -> T19,\nT16 -> T18,\nT17 -> T19" }, { "from": 7, "to": 27, "label": "EVAL-BACKTRACK" }, { "from": 11, "to": 15, "label": "SUCCESS" }, { "from": 18, "to": 40, "label": "SPLIT 1" }, { "from": 18, "to": 41, "label": "SPLIT 2\nnew knowledge:\nT15 is ground\nT22 is ground\nreplacements:X16 -> T22,\nT18 -> T23,\nT19 -> T24" }, { "from": 40, "to": 3, "label": "INSTANCE with matching:\nT1 -> T15\nT2 -> T18\nT3 -> X16" }, { "from": 41, "to": 3, "label": "INSTANCE with matching:\nT1 -> T22\nT2 -> T23\nT3 -> T24" } ], "type": "Graph" } } ---------------------------------------- (2) Obligation: Q restricted rewrite system: The TRS R consists of the following rules: f3_in(0) -> f3_out1(0) f3_in(s(T15)) -> U1(f18_in(T15), s(T15)) U1(f18_out1(X16, T19), s(T15)) -> f3_out1(T19) f18_in(T15) -> U2(f3_in(T15), T15) U2(f3_out1(T22), T15) -> U3(f3_in(T22), T15, T22) U3(f3_out1(T24), T15, T22) -> f18_out1(T22, T24) Q is empty. ---------------------------------------- (3) QTRSRRRProof (EQUIVALENT) Used ordering: Quasi precedence: 0 > f3_out1_1 s_1 > f18_in_1 > U2_2 > f3_in_1 > U1_2 > f3_out1_1 s_1 > f18_in_1 > U2_2 > U3_3 > f18_out1_2 > f3_out1_1 Status: f3_in_1: multiset status 0: multiset status f3_out1_1: multiset status s_1: [1] U1_2: multiset status f18_in_1: [1] f18_out1_2: multiset status U2_2: multiset status U3_3: multiset status With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: f3_in(0) -> f3_out1(0) f3_in(s(T15)) -> U1(f18_in(T15), s(T15)) U1(f18_out1(X16, T19), s(T15)) -> f3_out1(T19) f18_in(T15) -> U2(f3_in(T15), T15) U2(f3_out1(T22), T15) -> U3(f3_in(T22), T15, T22) U3(f3_out1(T24), T15, T22) -> f18_out1(T22, T24) ---------------------------------------- (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