/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 check_length(g,a) w.r.t. the given Prolog program could successfully be proven: (0) Prolog (1) PrologToIRSwTTransformerProof [SOUND, 10 ms] (2) TRUE ---------------------------------------- (0) Obligation: Clauses: check_length(.(X1, Xs), N) :- ','(>(N, 0), ','(is(N1, -(N, 1)), check_length(Xs, N1))). check_length([], 0). Query: check_length(g,a) ---------------------------------------- (1) PrologToIRSwTTransformerProof (SOUND) Transformed Prolog program to IRSwT according to method in Master Thesis of A. Weinert { "root": 3, "program": { "directives": [], "clauses": [ [ "(check_length (. X1 Xs) N)", "(',' (> N (0)) (',' (is N1 (- N (1))) (check_length Xs N1)))" ], [ "(check_length ([]) (0))", null ] ] }, "graph": { "nodes": { "17": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (> T18 (0)) (',' (is X19 (- T18 (1))) (check_length T16 X19)))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T16"], "free": ["X19"], "exprvars": [] } }, "18": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "19": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "1550": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "1351": { "goal": [{ "clause": -1, "scope": -1, "term": "(check_length T16 T19)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [ { "lhs": { "name": "T19", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "name": "T18", "type": "PlainIntegerVariable" }, { "type": "PlainIntegerConstant", "value": "1" } ], "type": "PlainIntegerOperation", "operation": "-" }, "operation": "=" }, { "lhs": { "type": "PlainIntegerConstant", "value": "0" }, "type": "PlainIntegerRelation", "rhs": { "name": "T18", "type": "PlainIntegerVariable" }, "operation": "<" } ] }, "ground": [ "T19", "T18", "T16" ], "free": ["X19"], "exprvars": [ "T19", "T18" ] } }, "1384": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (> T37 (0)) (',' (is X41 (- T37 (1))) (check_length T36 X41)))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [ { "lhs": { "name": "T19", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "name": "T18", "type": "PlainIntegerVariable" }, { "type": "PlainIntegerConstant", "value": "1" } ], "type": "PlainIntegerOperation", "operation": "-" }, "operation": "=" }, { "lhs": { "arguments": [ { "name": "T18", "type": "PlainIntegerVariable" }, { "type": "PlainIntegerConstant", "value": "1" } ], "type": "PlainIntegerOperation", "operation": "-" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "name": "T18", "type": "PlainIntegerVariable" }, { "type": "PlainIntegerConstant", "value": "1" } ], "type": "PlainIntegerOperation", "operation": "-" }, "operation": "=" }, { "lhs": { "type": "PlainIntegerConstant", "value": "0" }, "type": "PlainIntegerRelation", "rhs": { "name": "T18", "type": "PlainIntegerVariable" }, "operation": "<" }, { "lhs": { "name": "T18", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "name": "T18", "type": "PlainIntegerVariable" }, "operation": "<" } ] }, "ground": [ "T36", "T37" ], "free": ["X41"], "exprvars": [ "T19", "T18", "T37" ] } }, "1372": { "goal": [{ "clause": 1, "scope": 2, "term": "(check_length T16 T19)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [ { "lhs": { "name": "T19", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "name": "T18", "type": "PlainIntegerVariable" }, { "type": "PlainIntegerConstant", "value": "1" } ], "type": "PlainIntegerOperation", "operation": "-" }, "operation": "=" }, { "lhs": { "type": "PlainIntegerConstant", "value": "0" }, "type": "PlainIntegerRelation", "rhs": { "name": "T18", "type": "PlainIntegerVariable" }, "operation": "<" } ] }, "ground": [ "T19", "T16" ], "free": [], "exprvars": [ "T19", "T18" ] } }, "1195": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [{ "lhs": { "type": "PlainIntegerConstant", "value": "0" }, "type": "PlainIntegerRelation", "rhs": { "name": "T18", "type": "PlainIntegerVariable" }, "operation": ">=" }] }, "ground": [ "T18", "T16" ], "free": ["X19"], "exprvars": ["T18"] } }, "1371": { "goal": [{ "clause": 0, "scope": 2, "term": "(check_length T16 T19)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [ { "lhs": { "name": "T19", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "name": "T18", "type": "PlainIntegerVariable" }, { "type": "PlainIntegerConstant", "value": "1" } ], "type": "PlainIntegerOperation", "operation": "-" }, "operation": "=" }, { "lhs": { "type": "PlainIntegerConstant", "value": "0" }, "type": "PlainIntegerRelation", "rhs": { "name": "T18", "type": "PlainIntegerVariable" }, "operation": "<" } ] }, "ground": [ "T19", "T16" ], "free": [], "exprvars": [ "T19", "T18" ] } }, "type": "Nodes", "1194": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (is X19 (- T18 (1))) (check_length T16 X19))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [{ "lhs": { "type": "PlainIntegerConstant", "value": "0" }, "type": "PlainIntegerRelation", "rhs": { "name": "T18", "type": "PlainIntegerVariable" }, "operation": "<" }] }, "ground": [ "T18", "T16" ], "free": ["X19"], "exprvars": ["T18"] } }, "1546": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [ { "lhs": { "name": "T19", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "name": "T18", "type": "PlainIntegerVariable" }, { "type": "PlainIntegerConstant", "value": "1" } ], "type": "PlainIntegerOperation", "operation": "-" }, "operation": "=" }, { "lhs": { "arguments": [ { "name": "T18", "type": "PlainIntegerVariable" }, { "type": "PlainIntegerConstant", "value": "1" } ], "type": "PlainIntegerOperation", "operation": "-" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "name": "T18", "type": "PlainIntegerVariable" }, { "type": "PlainIntegerConstant", "value": "1" } ], "type": "PlainIntegerOperation", "operation": "-" }, "operation": "=" }, { "lhs": { "type": "PlainIntegerConstant", "value": "0" }, "type": "PlainIntegerRelation", "rhs": { "name": "T18", "type": "PlainIntegerVariable" }, "operation": "<" }, { "lhs": { "name": "T18", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "name": "T18", "type": "PlainIntegerVariable" }, "operation": "<" } ] }, "ground": [], "free": [], "exprvars": [ "T19", "T18" ] } }, "1545": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [ { "lhs": { "name": "T19", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "name": "T18", "type": "PlainIntegerVariable" }, { "type": "PlainIntegerConstant", "value": "1" } ], "type": "PlainIntegerOperation", "operation": "-" }, "operation": "=" }, { "lhs": { "type": "PlainIntegerConstant", "value": "0" }, "type": "PlainIntegerRelation", "rhs": { "name": "T18", "type": "PlainIntegerVariable" }, "operation": "<" } ] }, "ground": [], "free": [], "exprvars": [ "T19", "T18" ] } }, "3": { "goal": [{ "clause": -1, "scope": -1, "term": "(check_length T1 T2)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T1"], "free": [], "exprvars": [] } }, "1544": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [ { "lhs": { "name": "T19", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "name": "T18", "type": "PlainIntegerVariable" }, { "type": "PlainIntegerConstant", "value": "1" } ], "type": "PlainIntegerOperation", "operation": "-" }, "operation": "=" }, { "lhs": { "arguments": [ { "name": "T18", "type": "PlainIntegerVariable" }, { "type": "PlainIntegerConstant", "value": "1" } ], "type": "PlainIntegerOperation", "operation": "-" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "name": "T18", "type": "PlainIntegerVariable" }, { "type": "PlainIntegerConstant", "value": "1" } ], "type": "PlainIntegerOperation", "operation": "-" }, "operation": "=" }, { "lhs": { "type": "PlainIntegerConstant", "value": "0" }, "type": "PlainIntegerRelation", "rhs": { "name": "T18", "type": "PlainIntegerVariable" }, "operation": "<" }, { "lhs": { "name": "T18", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "name": "T18", "type": "PlainIntegerVariable" }, "operation": "<" } ] }, "ground": [], "free": [], "exprvars": [ "T19", "T18" ] } }, "4": { "goal": [ { "clause": 0, "scope": 1, "term": "(check_length T1 T2)" }, { "clause": 1, "scope": 1, "term": "(check_length T1 T2)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T1"], "free": [], "exprvars": [] } }, "1389": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [ { "lhs": { "name": "T19", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "name": "T18", "type": "PlainIntegerVariable" }, { "type": "PlainIntegerConstant", "value": "1" } ], "type": "PlainIntegerOperation", "operation": "-" }, "operation": "=" }, { "lhs": { "type": "PlainIntegerConstant", "value": "0" }, "type": "PlainIntegerRelation", "rhs": { "name": "T18", "type": "PlainIntegerVariable" }, "operation": "<" } ] }, "ground": [], "free": [], "exprvars": [ "T19", "T18" ] } }, "7": { "goal": [{ "clause": 0, "scope": 1, "term": "(check_length T1 T2)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T1"], "free": [], "exprvars": [] } }, "1353": { "goal": [ { "clause": 0, "scope": 2, "term": "(check_length T16 T19)" }, { "clause": 1, "scope": 2, "term": "(check_length T16 T19)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [ { "lhs": { "name": "T19", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "name": "T18", "type": "PlainIntegerVariable" }, { "type": "PlainIntegerConstant", "value": "1" } ], "type": "PlainIntegerOperation", "operation": "-" }, "operation": "=" }, { "lhs": { "type": "PlainIntegerConstant", "value": "0" }, "type": "PlainIntegerRelation", "rhs": { "name": "T18", "type": "PlainIntegerVariable" }, "operation": "<" } ] }, "ground": [ "T19", "T16" ], "free": [], "exprvars": [ "T19", "T18" ] } }, "1551": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "8": { "goal": [{ "clause": 1, "scope": 1, "term": "(check_length T1 T2)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T1"], "free": [], "exprvars": [] } }, "1549": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } } }, "edges": [ { "from": 3, "to": 4, "label": "CASE" }, { "from": 4, "to": 7, "label": "PARALLEL" }, { "from": 4, "to": 8, "label": "PARALLEL" }, { "from": 7, "to": 17, "label": "EVAL with clause\ncheck_length(.(X16, X17), X18) :- ','(>(X18, 0), ','(is(X19, -(X18, 1)), check_length(X17, X19))).\nand substitutionX16 -> T15,\nX17 -> T16,\nT1 -> .(T15, T16),\nT2 -> T18,\nX18 -> T18,\nT17 -> T18" }, { "from": 7, "to": 18, "label": "EVAL-BACKTRACK" }, { "from": 8, "to": 1549, "label": "EVAL with clause\ncheck_length([], 0).\nand substitutionT1 -> [],\nT2 -> 0" }, { "from": 8, "to": 1550, "label": "EVAL-BACKTRACK" }, { "from": 17, "to": 19, "label": "IS ERROR" }, { "from": 17, "to": 1194, "label": "ARITHCOMP SUCCESS" }, { "from": 17, "to": 1195, "label": "ARITHCOMP FAIL" }, { "from": 1194, "to": 1351, "label": "\nX19 -> T19" }, { "from": 1351, "to": 1353, "label": "CASE" }, { "from": 1353, "to": 1371, "label": "PARALLEL" }, { "from": 1353, "to": 1372, "label": "PARALLEL" }, { "from": 1371, "to": 1384, "label": "EVAL with clause\ncheck_length(.(X38, X39), X40) :- ','(>(X40, 0), ','(is(X41, -(X40, 1)), check_length(X39, X41))).\nand substitutionX38 -> T35,\nX39 -> T36,\nT16 -> .(T35, T36),\nT19 -> T37,\nX40 -> T37" }, { "from": 1371, "to": 1389, "label": "EVAL-BACKTRACK" }, { "from": 1372, "to": 1544, "label": "EVAL with clause\ncheck_length([], 0).\nand substitutionT16 -> [],\nT19 -> 0" }, { "from": 1372, "to": 1545, "label": "EVAL-BACKTRACK" }, { "from": 1544, "to": 1546, "label": "SUCCESS" }, { "from": 1549, "to": 1551, "label": "SUCCESS" } ], "type": "Graph" } } ---------------------------------------- (2) TRUE