/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 range(g,g,a) w.r.t. the given Prolog program could successfully be proven: (0) Prolog (1) PrologToIRSwTTransformerProof [SOUND, 20 ms] (2) TRUE ---------------------------------------- (0) Obligation: Clauses: range(I, J, Ks) :- range(I, J, [], Ks). range(I, I, Ks, .(I, Ks)) :- !. range(I, J, As, Ks) :- ','(<(I, J), ','(is(J1, -(J, 1)), range(I, J1, .(J, As), Ks))). Query: range(g,g,a) ---------------------------------------- (1) PrologToIRSwTTransformerProof (SOUND) Transformed Prolog program to IRSwT according to method in Master Thesis of A. Weinert { "root": 3, "program": { "directives": [], "clauses": [ [ "(range I J Ks)", "(range I J ([]) Ks)" ], [ "(range I I Ks (. I Ks))", "(!)" ], [ "(range I J As Ks)", "(',' (< I J) (',' (is J1 (- J (1))) (range I J1 (. J As) Ks)))" ] ] }, "graph": { "nodes": { "13": { "goal": [ { "clause": 1, "scope": 2, "term": "(range T12 T13 ([]) T15)" }, { "clause": 2, "scope": 2, "term": "(range T12 T13 ([]) T15)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T12", "T13" ], "free": [], "exprvars": [] } }, "25": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "26": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (< T27 T28) (',' (is X33 (- T28 (1))) (range T27 X33 (. T28 ([])) T30)))" }], "kb": { "nonunifying": [[ "(range T27 T28 ([]) T15)", "(range X18 X18 X19 (. X18 X19))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T27", "T28" ], "free": [ "X18", "X19", "X33" ], "exprvars": [] } }, "16": { "goal": [ { "clause": -1, "scope": -1, "term": "(!_2)" }, { "clause": 2, "scope": 2, "term": "(range T19 T19 ([]) T15)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T19"], "free": [], "exprvars": [] } }, "27": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "17": { "goal": [{ "clause": 2, "scope": 2, "term": "(range T12 T13 ([]) T15)" }], "kb": { "nonunifying": [[ "(range T12 T13 ([]) T15)", "(range X18 X18 X19 (. X18 X19))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T12", "T13" ], "free": [ "X18", "X19" ], "exprvars": [] } }, "18": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "1660": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (is X33 (- T28 (1))) (range T27 X33 (. T28 ([])) T30))" }], "kb": { "nonunifying": [[ "(range T27 T28 ([]) T15)", "(range X18 X18 X19 (. X18 X19))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [{ "lhs": { "name": "T27", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "name": "T28", "type": "PlainIntegerVariable" }, "operation": "<" }] }, "ground": [ "T28", "T27" ], "free": [ "X18", "X19", "X33" ], "exprvars": [ "T28", "T27" ] } }, "type": "Nodes", "1667": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [ { "lhs": { "name": "T31", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "name": "T28", "type": "PlainIntegerVariable" }, { "type": "PlainIntegerConstant", "value": "1" } ], "type": "PlainIntegerOperation", "operation": "-" }, "operation": "=" }, { "lhs": { "arguments": [ { "name": "T39", "type": "PlainIntegerVariable" }, { "type": "PlainIntegerConstant", "value": "1" } ], "type": "PlainIntegerOperation", "operation": "-" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "name": "T28", "type": "PlainIntegerVariable" }, { "type": "PlainIntegerConstant", "value": "1" } ], "type": "PlainIntegerOperation", "operation": "-" }, "operation": "=" }, { "lhs": { "name": "T27", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "name": "T28", "type": "PlainIntegerVariable" }, "operation": "<" }, { "lhs": { "name": "T39", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "name": "T28", "type": "PlainIntegerVariable" }, "operation": "<" } ] }, "ground": [], "free": [], "exprvars": [ "T31", "T28", "T39", "T27", "T38" ] } }, "1666": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [ { "lhs": { "name": "T31", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "name": "T28", "type": "PlainIntegerVariable" }, { "type": "PlainIntegerConstant", "value": "1" } ], "type": "PlainIntegerOperation", "operation": "-" }, "operation": "=" }, { "lhs": { "arguments": [ { "name": "T39", "type": "PlainIntegerVariable" }, { "type": "PlainIntegerConstant", "value": "1" } ], "type": "PlainIntegerOperation", "operation": "-" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "name": "T28", "type": "PlainIntegerVariable" }, { "type": "PlainIntegerConstant", "value": "1" } ], "type": "PlainIntegerOperation", "operation": "-" }, "operation": "=" }, { "lhs": { "name": "T27", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "name": "T28", "type": "PlainIntegerVariable" }, "operation": "<" }, { "lhs": { "name": "T39", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "name": "T28", "type": "PlainIntegerVariable" }, "operation": "<" } ] }, "ground": [], "free": [], "exprvars": [ "T31", "T28", "T39", "T27", "T38" ] } }, "3": { "goal": [{ "clause": -1, "scope": -1, "term": "(range T1 T2 T3)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T1", "T2" ], "free": [], "exprvars": [] } }, "1665": { "goal": [{ "clause": 2, "scope": 3, "term": "(range T27 T31 (. T28 ([])) T30)" }], "kb": { "nonunifying": [ [ "(range T27 T28 ([]) T15)", "(range X18 X18 X19 (. X18 X19))" ], [ "(range T27 T31 (. T28 ([])) T30)", "(range X40 X40 X41 (. X40 X41))" ] ], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [ { "lhs": { "name": "T31", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "name": "T28", "type": "PlainIntegerVariable" }, { "type": "PlainIntegerConstant", "value": "1" } ], "type": "PlainIntegerOperation", "operation": "-" }, "operation": "=" }, { "lhs": { "name": "T27", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "name": "T28", "type": "PlainIntegerVariable" }, "operation": "<" } ] }, "ground": [ "T31", "T28", "T27" ], "free": [ "X18", "X19", "X40", "X41" ], "exprvars": [ "T31", "T28", "T27" ] } }, "1664": { "goal": [ { "clause": -1, "scope": -1, "term": "(!_3)" }, { "clause": 2, "scope": 3, "term": "(range T38 T38 (. T39 ([])) T30)" } ], "kb": { "nonunifying": [[ "(range T38 T39 ([]) T15)", "(range X18 X18 X19 (. X18 X19))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [ { "lhs": { "name": "T31", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "name": "T28", "type": "PlainIntegerVariable" }, { "type": "PlainIntegerConstant", "value": "1" } ], "type": "PlainIntegerOperation", "operation": "-" }, "operation": "=" }, { "lhs": { "arguments": [ { "name": "T39", "type": "PlainIntegerVariable" }, { "type": "PlainIntegerConstant", "value": "1" } ], "type": "PlainIntegerOperation", "operation": "-" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "name": "T28", "type": "PlainIntegerVariable" }, { "type": "PlainIntegerConstant", "value": "1" } ], "type": "PlainIntegerOperation", "operation": "-" }, "operation": "=" }, { "lhs": { "name": "T27", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "name": "T28", "type": "PlainIntegerVariable" }, "operation": "<" }, { "lhs": { "name": "T39", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "name": "T28", "type": "PlainIntegerVariable" }, "operation": "<" } ] }, "ground": [ "T38", "T39" ], "free": [ "X18", "X19" ], "exprvars": [ "T31", "T28", "T39", "T27", "T38" ] } }, "1663": { "goal": [ { "clause": 1, "scope": 3, "term": "(range T27 T31 (. T28 ([])) T30)" }, { "clause": 2, "scope": 3, "term": "(range T27 T31 (. T28 ([])) T30)" } ], "kb": { "nonunifying": [[ "(range T27 T28 ([]) T15)", "(range X18 X18 X19 (. X18 X19))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [ { "lhs": { "name": "T31", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "name": "T28", "type": "PlainIntegerVariable" }, { "type": "PlainIntegerConstant", "value": "1" } ], "type": "PlainIntegerOperation", "operation": "-" }, "operation": "=" }, { "lhs": { "name": "T27", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "name": "T28", "type": "PlainIntegerVariable" }, "operation": "<" } ] }, "ground": [ "T31", "T28", "T27" ], "free": [ "X18", "X19" ], "exprvars": [ "T31", "T28", "T27" ] } }, "6": { "goal": [{ "clause": 0, "scope": 1, "term": "(range T1 T2 T3)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T1", "T2" ], "free": [], "exprvars": [] } }, "1662": { "goal": [{ "clause": -1, "scope": -1, "term": "(range T27 T31 (. T28 ([])) T30)" }], "kb": { "nonunifying": [[ "(range T27 T28 ([]) T15)", "(range X18 X18 X19 (. X18 X19))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [ { "lhs": { "name": "T31", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "name": "T28", "type": "PlainIntegerVariable" }, { "type": "PlainIntegerConstant", "value": "1" } ], "type": "PlainIntegerOperation", "operation": "-" }, "operation": "=" }, { "lhs": { "name": "T27", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "name": "T28", "type": "PlainIntegerVariable" }, "operation": "<" } ] }, "ground": [ "T31", "T28", "T27" ], "free": [ "X18", "X19", "X33" ], "exprvars": [ "T31", "T28", "T27" ] } }, "1661": { "goal": [], "kb": { "nonunifying": [[ "(range T27 T28 ([]) T15)", "(range X18 X18 X19 (. X18 X19))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [{ "lhs": { "name": "T27", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "name": "T28", "type": "PlainIntegerVariable" }, "operation": ">=" }] }, "ground": [ "T28", "T27" ], "free": [ "X18", "X19", "X33" ], "exprvars": [ "T28", "T27" ] } }, "9": { "goal": [{ "clause": -1, "scope": -1, "term": "(range T12 T13 ([]) T15)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T12", "T13" ], "free": [], "exprvars": [] } }, "1669": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (< T49 T50) (',' (is X55 (- T50 (1))) (range T49 X55 (. T50 (. T51 ([]))) T53)))" }], "kb": { "nonunifying": [ [ "(range T49 T51 ([]) T15)", "(range X18 X18 X19 (. X18 X19))" ], [ "(range T49 T50 (. T51 ([])) T30)", "(range X40 X40 X41 (. X40 X41))" ] ], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [ { "lhs": { "name": "T31", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "name": "T28", "type": "PlainIntegerVariable" }, { "type": "PlainIntegerConstant", "value": "1" } ], "type": "PlainIntegerOperation", "operation": "-" }, "operation": "=" }, { "lhs": { "arguments": [ { "name": "T51", "type": "PlainIntegerVariable" }, { "type": "PlainIntegerConstant", "value": "1" } ], "type": "PlainIntegerOperation", "operation": "-" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "name": "T28", "type": "PlainIntegerVariable" }, { "type": "PlainIntegerConstant", "value": "1" } ], "type": "PlainIntegerOperation", "operation": "-" }, "operation": "=" }, { "lhs": { "name": "T27", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "name": "T28", "type": "PlainIntegerVariable" }, "operation": "<" }, { "lhs": { "name": "T51", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "name": "T28", "type": "PlainIntegerVariable" }, "operation": "<" } ] }, "ground": [ "T49", "T50", "T51" ], "free": [ "X18", "X19", "X40", "X41", "X55" ], "exprvars": [ "T31", "T51", "T28", "T50", "T27", "T49" ] } } }, "edges": [ { "from": 3, "to": 6, "label": "CASE" }, { "from": 6, "to": 9, "label": "ONLY EVAL with clause\nrange(X9, X10, X11) :- range(X9, X10, [], X11).\nand substitutionT1 -> T12,\nX9 -> T12,\nT2 -> T13,\nX10 -> T13,\nT3 -> T15,\nX11 -> T15,\nT14 -> T15" }, { "from": 9, "to": 13, "label": "CASE" }, { "from": 13, "to": 16, "label": "EVAL with clause\nrange(X18, X18, X19, .(X18, X19)) :- !_2.\nand substitutionT12 -> T19,\nX18 -> T19,\nT13 -> T19,\nX19 -> [],\nT15 -> .(T19, [])" }, { "from": 13, "to": 17, "label": "EVAL-BACKTRACK" }, { "from": 16, "to": 18, "label": "CUT" }, { "from": 17, "to": 26, "label": "ONLY EVAL with clause\nrange(X29, X30, X31, X32) :- ','(<(X29, X30), ','(is(X33, -(X30, 1)), range(X29, X33, .(X30, X31), X32))).\nand substitutionT12 -> T27,\nX29 -> T27,\nT13 -> T28,\nX30 -> T28,\nX31 -> [],\nT15 -> T30,\nX32 -> T30,\nT29 -> T30" }, { "from": 18, "to": 25, "label": "SUCCESS" }, { "from": 26, "to": 27, "label": "IS ERROR" }, { "from": 26, "to": 1660, "label": "ARITHCOMP SUCCESS" }, { "from": 26, "to": 1661, "label": "ARITHCOMP FAIL" }, { "from": 1660, "to": 1662, "label": "\nX33 -> T31" }, { "from": 1662, "to": 1663, "label": "CASE" }, { "from": 1663, "to": 1664, "label": "EVAL with clause\nrange(X40, X40, X41, .(X40, X41)) :- !_3.\nand substitutionT27 -> T38,\nX40 -> T38,\nT31 -> T38,\nT28 -> T39,\nX41 -> .(T39, []),\nT30 -> .(T38, .(T39, []))" }, { "from": 1663, "to": 1665, "label": "EVAL-BACKTRACK" }, { "from": 1664, "to": 1666, "label": "CUT" }, { "from": 1665, "to": 1669, "label": "ONLY EVAL with clause\nrange(X51, X52, X53, X54) :- ','(<(X51, X52), ','(is(X55, -(X52, 1)), range(X51, X55, .(X52, X53), X54))).\nand substitutionT27 -> T49,\nX51 -> T49,\nT31 -> T50,\nX52 -> T50,\nT28 -> T51,\nX53 -> .(T51, []),\nT30 -> T53,\nX54 -> T53,\nT52 -> T53" }, { "from": 1666, "to": 1667, "label": "SUCCESS" } ], "type": "Graph" } } ---------------------------------------- (2) TRUE