/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: 794c25de1cacf0d048858bcd21c9a779e1221865 marcel 20200619 unpublished dirty Left Termination of the query pattern flat(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, 129 ms] (4) QTRS (5) RisEmptyProof [EQUIVALENT, 0 ms] (6) YES ---------------------------------------- (0) Obligation: Clauses: right(tree(X, XS1, XS2), XS2). flat(niltree, nil). flat(tree(X, niltree, XS), cons(X, YS)) :- ','(right(tree(X, niltree, XS), ZS), flat(ZS, YS)). flat(tree(X, tree(Y, YS1, YS2), XS), ZS) :- flat(tree(Y, YS1, tree(X, YS2, XS)), ZS). Query: flat(g,a) ---------------------------------------- (1) PrologToTRSTransformerProof (SOUND) Transformed Prolog program to TRS. { "root": 19, "program": { "directives": [], "clauses": [ [ "(right (tree X XS1 XS2) XS2)", null ], [ "(flat (niltree) (nil))", null ], [ "(flat (tree X (niltree) XS) (cons X YS))", "(',' (right (tree X (niltree) XS) ZS) (flat ZS YS))" ], [ "(flat (tree X (tree Y YS1 YS2) XS) ZS)", "(flat (tree Y YS1 (tree X YS2 XS)) ZS)" ] ] }, "graph": { "nodes": { "22": { "goal": [ { "clause": 1, "scope": 1, "term": "(flat T1 T2)" }, { "clause": 2, "scope": 1, "term": "(flat T1 T2)" }, { "clause": 3, "scope": 1, "term": "(flat T1 T2)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T1"], "free": [], "exprvars": [] } }, "23": { "goal": [{ "clause": 1, "scope": 1, "term": "(flat T1 T2)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T1"], "free": [], "exprvars": [] } }, "24": { "goal": [ { "clause": 2, "scope": 1, "term": "(flat T1 T2)" }, { "clause": 3, "scope": 1, "term": "(flat T1 T2)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T1"], "free": [], "exprvars": [] } }, "19": { "goal": [{ "clause": -1, "scope": -1, "term": "(flat T1 T2)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T1"], "free": [], "exprvars": [] } }, "171": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (right (tree T15 (niltree) T16) X18) (flat X18 T18))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T15", "T16" ], "free": ["X18"], "exprvars": [] } }, "type": "Nodes", "172": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "173": { "goal": [{ "clause": 0, "scope": 2, "term": "(',' (right (tree T15 (niltree) T16) X18) (flat X18 T18))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T15", "T16" ], "free": ["X18"], "exprvars": [] } }, "175": { "goal": [{ "clause": -1, "scope": -1, "term": "(flat T24 T18)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T24"], "free": [], "exprvars": [] } }, "166": { "goal": [{ "clause": 2, "scope": 1, "term": "(flat T1 T2)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T1"], "free": [], "exprvars": [] } }, "134": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "167": { "goal": [{ "clause": 3, "scope": 1, "term": "(flat T1 T2)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T1"], "free": [], "exprvars": [] } }, "157": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "203": { "goal": [{ "clause": -1, "scope": -1, "term": "(flat (tree T38 T39 (tree T37 T40 T41)) T43)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T37", "T38", "T39", "T40", "T41" ], "free": [], "exprvars": [] } }, "204": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "129": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } } }, "edges": [ { "from": 19, "to": 22, "label": "CASE" }, { "from": 22, "to": 23, "label": "PARALLEL" }, { "from": 22, "to": 24, "label": "PARALLEL" }, { "from": 23, "to": 129, "label": "EVAL with clause\nflat(niltree, nil).\nand substitutionT1 -> niltree,\nT2 -> nil" }, { "from": 23, "to": 134, "label": "EVAL-BACKTRACK" }, { "from": 24, "to": 166, "label": "PARALLEL" }, { "from": 24, "to": 167, "label": "PARALLEL" }, { "from": 129, "to": 157, "label": "SUCCESS" }, { "from": 166, "to": 171, "label": "EVAL with clause\nflat(tree(X15, niltree, X16), cons(X15, X17)) :- ','(right(tree(X15, niltree, X16), X18), flat(X18, X17)).\nand substitutionX15 -> T15,\nX16 -> T16,\nT1 -> tree(T15, niltree, T16),\nX17 -> T18,\nT2 -> cons(T15, T18),\nT17 -> T18" }, { "from": 166, "to": 172, "label": "EVAL-BACKTRACK" }, { "from": 167, "to": 203, "label": "EVAL with clause\nflat(tree(X40, tree(X41, X42, X43), X44), X45) :- flat(tree(X41, X42, tree(X40, X43, X44)), X45).\nand substitutionX40 -> T37,\nX41 -> T38,\nX42 -> T39,\nX43 -> T40,\nX44 -> T41,\nT1 -> tree(T37, tree(T38, T39, T40), T41),\nT2 -> T43,\nX45 -> T43,\nT42 -> T43" }, { "from": 167, "to": 204, "label": "EVAL-BACKTRACK" }, { "from": 171, "to": 173, "label": "CASE" }, { "from": 173, "to": 175, "label": "ONLY EVAL with clause\nright(tree(X25, X26, X27), X27).\nand substitutionT15 -> T23,\nX25 -> T23,\nX26 -> niltree,\nT16 -> T24,\nX27 -> T24,\nX18 -> T24" }, { "from": 175, "to": 19, "label": "INSTANCE with matching:\nT1 -> T24\nT2 -> T18" }, { "from": 203, "to": 19, "label": "INSTANCE with matching:\nT1 -> tree(T38, T39, tree(T37, T40, T41))\nT2 -> T43" } ], "type": "Graph" } } ---------------------------------------- (2) Obligation: Q restricted rewrite system: The TRS R consists of the following rules: f19_in(niltree) -> f19_out1(nil) f19_in(tree(T23, niltree, T24)) -> U1(f19_in(T24), tree(T23, niltree, T24)) U1(f19_out1(T18), tree(T23, niltree, T24)) -> f19_out1(cons(T23, T18)) f19_in(tree(T37, tree(T38, T39, T40), T41)) -> U2(f19_in(tree(T38, T39, tree(T37, T40, T41))), tree(T37, tree(T38, T39, T40), T41)) U2(f19_out1(T43), tree(T37, tree(T38, T39, T40), T41)) -> f19_out1(T43) Q is empty. ---------------------------------------- (3) QTRSRRRProof (EQUIVALENT) Used ordering: Quasi precedence: [f19_in_1, nil] > niltree > tree_3 [f19_in_1, nil] > [U1_2, cons_2] > f19_out1_1 [f19_in_1, nil] > U2_2 Status: f19_in_1: [1] niltree: multiset status f19_out1_1: multiset status nil: multiset status tree_3: [2,3,1] U1_2: multiset status cons_2: multiset status U2_2: multiset status With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: f19_in(niltree) -> f19_out1(nil) f19_in(tree(T23, niltree, T24)) -> U1(f19_in(T24), tree(T23, niltree, T24)) U1(f19_out1(T18), tree(T23, niltree, T24)) -> f19_out1(cons(T23, T18)) f19_in(tree(T37, tree(T38, T39, T40), T41)) -> U2(f19_in(tree(T38, T39, tree(T37, T40, T41))), tree(T37, tree(T38, T39, T40), T41)) U2(f19_out1(T43), tree(T37, tree(T38, T39, T40), T41)) -> f19_out1(T43) ---------------------------------------- (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