/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: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty Left Termination of the query pattern main() w.r.t. the given Prolog program could successfully be proven: (0) Prolog (1) PrologToIRSwTTransformerProof [SOUND, 20 ms] (2) TRUE ---------------------------------------- (0) Obligation: Clauses: main :- main(0, 0). main(I, C) :- ','(<(I, 20), body(I, C)). main(I, C) :- ','(>=(I, 20), body(I, C)). body(I, C) :- ','(is(I1, +(I, 1)), ','(=<(I1, 10), body(I1, C))). body(I, C) :- ','(is(I1, +(I, 1)), ','(>(I1, 10), ','(is(C1, +(C, 1)), body(I1, C1)))). Query: main() ---------------------------------------- (1) PrologToIRSwTTransformerProof (SOUND) Transformed Prolog program to IRSwT according to method in Master Thesis of A. Weinert { "root": 2, "program": { "directives": [], "clauses": [ [ "(main)", "(main (0) (0))" ], [ "(main I C)", "(',' (< I (20)) (body I C))" ], [ "(main I C)", "(',' (>= I (20)) (body I C))" ], [ "(body I C)", "(',' (is I1 (+ I (1))) (',' (=< I1 (10)) (body I1 C)))" ], [ "(body I C)", "(',' (is I1 (+ I (1))) (',' (> I1 (10)) (',' (is C1 (+ C (1))) (body I1 C1))))" ] ] }, "graph": { "nodes": { "15": { "goal": [ { "clause": 1, "scope": 2, "term": "(main (0) (0))" }, { "clause": 2, "scope": 2, "term": "(main (0) (0))" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "16": { "goal": [{ "clause": 1, "scope": 2, "term": "(main (0) (0))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "17": { "goal": [{ "clause": 2, "scope": 2, "term": "(main (0) (0))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "18": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (< (0) (20)) (body (0) (0)))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "2484": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (> T2 (10)) (',' (is X40 (+ (0) (1))) (body T2 X40)))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [ { "lhs": { "name": "T2", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "type": "PlainIntegerConstant", "value": "0" }, { "type": "PlainIntegerConstant", "value": "1" } ], "type": "PlainIntegerOperation", "operation": "+" }, "operation": "=" }, { "lhs": { "type": "PlainIntegerConstant", "value": "0" }, "type": "PlainIntegerRelation", "rhs": { "type": "PlainIntegerConstant", "value": "20" }, "operation": "<" }, { "lhs": { "type": "PlainIntegerConstant", "value": "20" }, "type": "PlainIntegerRelation", "rhs": { "type": "PlainIntegerConstant", "value": "20" }, "operation": "<" } ] }, "ground": ["T2"], "free": [ "X39", "X40" ], "exprvars": ["T2"] } }, "2483": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (is X39 (+ (0) (1))) (',' (> X39 (10)) (',' (is X40 (+ (0) (1))) (body X39 X40))))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [ { "lhs": { "type": "PlainIntegerConstant", "value": "0" }, "type": "PlainIntegerRelation", "rhs": { "type": "PlainIntegerConstant", "value": "20" }, "operation": "<" }, { "lhs": { "type": "PlainIntegerConstant", "value": "20" }, "type": "PlainIntegerRelation", "rhs": { "type": "PlainIntegerConstant", "value": "20" }, "operation": "<" } ] }, "ground": [], "free": [ "X39", "X40" ], "exprvars": [] } }, "2482": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (=< T1 (10)) (body T1 (0)))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [ { "lhs": { "name": "T1", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "type": "PlainIntegerConstant", "value": "0" }, { "type": "PlainIntegerConstant", "value": "1" } ], "type": "PlainIntegerOperation", "operation": "+" }, "operation": "=" }, { "lhs": { "type": "PlainIntegerConstant", "value": "0" }, "type": "PlainIntegerRelation", "rhs": { "type": "PlainIntegerConstant", "value": "20" }, "operation": "<" }, { "lhs": { "type": "PlainIntegerConstant", "value": "20" }, "type": "PlainIntegerRelation", "rhs": { "type": "PlainIntegerConstant", "value": "20" }, "operation": "<" } ] }, "ground": ["T1"], "free": ["X30"], "exprvars": ["T1"] } }, "type": "Nodes", "2491": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [{ "lhs": { "type": "PlainIntegerConstant", "value": "20" }, "type": "PlainIntegerRelation", "rhs": { "type": "PlainIntegerConstant", "value": "0" }, "operation": ">" }] }, "ground": [], "free": [], "exprvars": [] } }, "2404": { "goal": [ { "clause": 3, "scope": 3, "term": "(body (0) (0))" }, { "clause": 4, "scope": 3, "term": "(body (0) (0))" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [{ "lhs": { "type": "PlainIntegerConstant", "value": "0" }, "type": "PlainIntegerRelation", "rhs": { "type": "PlainIntegerConstant", "value": "20" }, "operation": "<" }] }, "ground": [], "free": [], "exprvars": [] } }, "2": { "goal": [{ "clause": -1, "scope": -1, "term": "(main)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "2413": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (is X30 (+ (0) (1))) (',' (=< X30 (10)) (body X30 (0))))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [ { "lhs": { "type": "PlainIntegerConstant", "value": "0" }, "type": "PlainIntegerRelation", "rhs": { "type": "PlainIntegerConstant", "value": "20" }, "operation": "<" }, { "lhs": { "type": "PlainIntegerConstant", "value": "20" }, "type": "PlainIntegerRelation", "rhs": { "type": "PlainIntegerConstant", "value": "20" }, "operation": "<" } ] }, "ground": [], "free": ["X30"], "exprvars": [] } }, "6": { "goal": [{ "clause": 0, "scope": 1, "term": "(main)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "2399": { "goal": [{ "clause": -1, "scope": -1, "term": "(body (0) (0))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [{ "lhs": { "type": "PlainIntegerConstant", "value": "0" }, "type": "PlainIntegerRelation", "rhs": { "type": "PlainIntegerConstant", "value": "20" }, "operation": "<" }] }, "ground": [], "free": [], "exprvars": [] } }, "2410": { "goal": [{ "clause": 4, "scope": 3, "term": "(body (0) (0))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [{ "lhs": { "type": "PlainIntegerConstant", "value": "0" }, "type": "PlainIntegerRelation", "rhs": { "type": "PlainIntegerConstant", "value": "20" }, "operation": "<" }] }, "ground": [], "free": [], "exprvars": [] } }, "2487": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (>= (0) (20)) (body (0) (0)))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "8": { "goal": [{ "clause": -1, "scope": -1, "term": "(main (0) (0))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "2409": { "goal": [{ "clause": 3, "scope": 3, "term": "(body (0) (0))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [{ "lhs": { "type": "PlainIntegerConstant", "value": "0" }, "type": "PlainIntegerRelation", "rhs": { "type": "PlainIntegerConstant", "value": "20" }, "operation": "<" }] }, "ground": [], "free": [], "exprvars": [] } } }, "edges": [ { "from": 2, "to": 6, "label": "CASE" }, { "from": 6, "to": 8, "label": "ONLY EVAL with clause\nmain :- main(0, 0).\nand substitution" }, { "from": 8, "to": 15, "label": "CASE" }, { "from": 15, "to": 16, "label": "PARALLEL" }, { "from": 15, "to": 17, "label": "PARALLEL" }, { "from": 16, "to": 18, "label": "ONLY EVAL with clause\nmain(X13, X14) :- ','(<(X13, 20), body(X13, X14)).\nand substitutionX13 -> 0,\nX14 -> 0" }, { "from": 17, "to": 2487, "label": "ONLY EVAL with clause\nmain(X45, X46) :- ','(>=(X45, 20), body(X45, X46)).\nand substitutionX45 -> 0,\nX46 -> 0" }, { "from": 18, "to": 2399, "label": "ARITHCOMP SUCCESS" }, { "from": 2399, "to": 2404, "label": "CASE" }, { "from": 2404, "to": 2409, "label": "PARALLEL" }, { "from": 2404, "to": 2410, "label": "PARALLEL" }, { "from": 2409, "to": 2413, "label": "ONLY EVAL with clause\nbody(X28, X29) :- ','(is(X30, +(X28, 1)), ','(=<(X30, 10), body(X30, X29))).\nand substitutionX28 -> 0,\nX29 -> 0" }, { "from": 2410, "to": 2483, "label": "ONLY EVAL with clause\nbody(X37, X38) :- ','(is(X39, +(X37, 1)), ','(>(X39, 10), ','(is(X40, +(X38, 1)), body(X39, X40)))).\nand substitutionX37 -> 0,\nX38 -> 0" }, { "from": 2413, "to": 2482, "label": "\nX30 -> T1" }, { "from": 2483, "to": 2484, "label": "\nX39 -> T2" }, { "from": 2487, "to": 2491, "label": "ARITHCOMP FAIL" } ], "type": "Graph" } } ---------------------------------------- (2) TRUE