/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 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, 139 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": 5, "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": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "23": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "24": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "19": { "goal": [{ "clause": 1, "scope": 1, "term": "(flat T1 T2)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T1"], "free": [], "exprvars": [] } }, "170": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "type": "Nodes", "151": { "goal": [{ "clause": -1, "scope": -1, "term": "(flat T24 T18)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T24"], "free": [], "exprvars": [] } }, "169": { "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": [] } }, "5": { "goal": [{ "clause": -1, "scope": -1, "term": "(flat T1 T2)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T1"], "free": [], "exprvars": [] } }, "6": { "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": [] } }, "91": { "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": [] } }, "92": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "93": { "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": [] } }, "62": { "goal": [{ "clause": 2, "scope": 1, "term": "(flat T1 T2)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T1"], "free": [], "exprvars": [] } }, "20": { "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": [] } }, "65": { "goal": [{ "clause": 3, "scope": 1, "term": "(flat T1 T2)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T1"], "free": [], "exprvars": [] } } }, "edges": [ { "from": 5, "to": 6, "label": "CASE" }, { "from": 6, "to": 19, "label": "PARALLEL" }, { "from": 6, "to": 20, "label": "PARALLEL" }, { "from": 19, "to": 22, "label": "EVAL with clause\nflat(niltree, nil).\nand substitutionT1 -> niltree,\nT2 -> nil" }, { "from": 19, "to": 23, "label": "EVAL-BACKTRACK" }, { "from": 20, "to": 62, "label": "PARALLEL" }, { "from": 20, "to": 65, "label": "PARALLEL" }, { "from": 22, "to": 24, "label": "SUCCESS" }, { "from": 62, "to": 91, "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": 62, "to": 92, "label": "EVAL-BACKTRACK" }, { "from": 65, "to": 169, "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": 65, "to": 170, "label": "EVAL-BACKTRACK" }, { "from": 91, "to": 93, "label": "CASE" }, { "from": 93, "to": 151, "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": 151, "to": 5, "label": "INSTANCE with matching:\nT1 -> T24\nT2 -> T18" }, { "from": 169, "to": 5, "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: f5_in(niltree) -> f5_out1(nil) f5_in(tree(T23, niltree, T24)) -> U1(f5_in(T24), tree(T23, niltree, T24)) U1(f5_out1(T18), tree(T23, niltree, T24)) -> f5_out1(cons(T23, T18)) f5_in(tree(T37, tree(T38, T39, T40), T41)) -> U2(f5_in(tree(T38, T39, tree(T37, T40, T41))), tree(T37, tree(T38, T39, T40), T41)) U2(f5_out1(T43), tree(T37, tree(T38, T39, T40), T41)) -> f5_out1(T43) Q is empty. ---------------------------------------- (3) QTRSRRRProof (EQUIVALENT) Used ordering: Quasi precedence: [f5_in_1, nil] > niltree > tree_3 [f5_in_1, nil] > [U1_2, cons_2] > f5_out1_1 [f5_in_1, nil] > U2_2 Status: f5_in_1: [1] niltree: multiset status f5_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: f5_in(niltree) -> f5_out1(nil) f5_in(tree(T23, niltree, T24)) -> U1(f5_in(T24), tree(T23, niltree, T24)) U1(f5_out1(T18), tree(T23, niltree, T24)) -> f5_out1(cons(T23, T18)) f5_in(tree(T37, tree(T38, T39, T40), T41)) -> U2(f5_in(tree(T38, T39, tree(T37, T40, T41))), tree(T37, tree(T38, T39, T40), T41)) U2(f5_out1(T43), tree(T37, tree(T38, T39, T40), T41)) -> f5_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