/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 triangle(g,a) w.r.t. the given Prolog program could successfully be proven: (0) Prolog (1) PrologToDTProblemTransformerProof [SOUND, 39 ms] (2) TRIPLES (3) TPisEmptyProof [EQUIVALENT, 0 ms] (4) YES ---------------------------------------- (0) Obligation: Clauses: triangle(0, 0). triangle(N, T) :- ','(>(N, 0), ','(is(N1, -(N, 1)), ','(triangle(N1, T1), is(T, +(T1, N))))). Query: triangle(g,a) ---------------------------------------- (1) PrologToDTProblemTransformerProof (SOUND) Built DT problem from termination graph DT10. { "root": 3, "program": { "directives": [], "clauses": [ [ "(triangle (0) (0))", null ], [ "(triangle N T)", "(',' (> N (0)) (',' (is N1 (- N (1))) (',' (triangle N1 T1) (is T (+ T1 N)))))" ] ] }, "graph": { "nodes": { "12": { "goal": [ { "clause": -1, "scope": -1, "term": "(true)" }, { "clause": 1, "scope": 1, "term": "(triangle (0) T3)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "23": { "goal": [{ "clause": 1, "scope": 1, "term": "(triangle (0) T3)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "24": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (> (0) (0)) (',' (is X5 (- (0) (1))) (',' (triangle X5 X6) (is T6 (+ X6 (0))))))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [ "X5", "X6" ], "exprvars": [] } }, "14": { "goal": [{ "clause": 1, "scope": 1, "term": "(triangle T2 T3)" }], "kb": { "nonunifying": [[ "(triangle T2 T3)", "(triangle (0) (0))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T2"], "free": [], "exprvars": [] } }, "type": "Nodes", "1712": { "goal": [], "kb": { "nonunifying": [[ "(triangle T9 T3)", "(triangle (0) (0))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [{ "lhs": { "type": "PlainIntegerConstant", "value": "0" }, "type": "PlainIntegerRelation", "rhs": { "name": "T9", "type": "PlainIntegerVariable" }, "operation": ">=" }] }, "ground": ["T9"], "free": [ "X11", "X12" ], "exprvars": ["T9"] } }, "1711": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (is X11 (- T9 (1))) (',' (triangle X11 X12) (is T11 (+ X12 T9))))" }], "kb": { "nonunifying": [[ "(triangle T9 T3)", "(triangle (0) (0))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [{ "lhs": { "type": "PlainIntegerConstant", "value": "0" }, "type": "PlainIntegerRelation", "rhs": { "name": "T9", "type": "PlainIntegerVariable" }, "operation": "<" }] }, "ground": ["T9"], "free": [ "X11", "X12" ], "exprvars": ["T9"] } }, "1722": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (',' (> T16 (0)) (',' (is X23 (- T16 (1))) (',' (triangle X23 X24) (is X25 (+ X24 T16))))) (is T11 (+ X25 T9)))" }], "kb": { "nonunifying": [[ "(triangle T9 T3)", "(triangle (0) (0))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [ { "lhs": { "name": "T12", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "name": "T9", "type": "PlainIntegerVariable" }, { "type": "PlainIntegerConstant", "value": "1" } ], "type": "PlainIntegerOperation", "operation": "-" }, "operation": "=" }, { "lhs": { "arguments": [ { "name": "T9", "type": "PlainIntegerVariable" }, { "type": "PlainIntegerConstant", "value": "1" } ], "type": "PlainIntegerOperation", "operation": "-" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "name": "T9", "type": "PlainIntegerVariable" }, { "type": "PlainIntegerConstant", "value": "1" } ], "type": "PlainIntegerOperation", "operation": "-" }, "operation": "=" }, { "lhs": { "type": "PlainIntegerConstant", "value": "0" }, "type": "PlainIntegerRelation", "rhs": { "name": "T9", "type": "PlainIntegerVariable" }, "operation": "<" }, { "lhs": { "name": "T9", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "name": "T9", "type": "PlainIntegerVariable" }, "operation": "<" } ] }, "ground": [ "T9", "T16" ], "free": [ "X25", "X23", "X24" ], "exprvars": [ "T12", "T16", "T9" ] } }, "1721": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [ { "lhs": { "name": "T12", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "name": "T9", "type": "PlainIntegerVariable" }, { "type": "PlainIntegerConstant", "value": "1" } ], "type": "PlainIntegerOperation", "operation": "-" }, "operation": "=" }, { "lhs": { "arguments": [ { "name": "T9", "type": "PlainIntegerVariable" }, { "type": "PlainIntegerConstant", "value": "1" } ], "type": "PlainIntegerOperation", "operation": "-" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "name": "T9", "type": "PlainIntegerVariable" }, { "type": "PlainIntegerConstant", "value": "1" } ], "type": "PlainIntegerOperation", "operation": "-" }, "operation": "=" }, { "lhs": { "name": "T13", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "type": "PlainIntegerConstant", "value": "0" }, { "name": "T9", "type": "PlainIntegerVariable" } ], "type": "PlainIntegerOperation", "operation": "+" }, "operation": "=" }, { "lhs": { "type": "PlainIntegerConstant", "value": "0" }, "type": "PlainIntegerRelation", "rhs": { "name": "T9", "type": "PlainIntegerVariable" }, "operation": "<" }, { "lhs": { "name": "T9", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "name": "T9", "type": "PlainIntegerVariable" }, "operation": "<" } ] }, "ground": [], "free": [], "exprvars": [ "T13", "T12", "T9" ] } }, "3": { "goal": [{ "clause": -1, "scope": -1, "term": "(triangle T2 T3)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T2"], "free": [], "exprvars": [] } }, "1720": { "goal": [], "kb": { "nonunifying": [[ "(triangle T9 T3)", "(triangle (0) (0))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [ { "lhs": { "name": "T12", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "name": "T9", "type": "PlainIntegerVariable" }, { "type": "PlainIntegerConstant", "value": "1" } ], "type": "PlainIntegerOperation", "operation": "-" }, "operation": "=" }, { "lhs": { "arguments": [ { "name": "T9", "type": "PlainIntegerVariable" }, { "type": "PlainIntegerConstant", "value": "1" } ], "type": "PlainIntegerOperation", "operation": "-" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "name": "T9", "type": "PlainIntegerVariable" }, { "type": "PlainIntegerConstant", "value": "1" } ], "type": "PlainIntegerOperation", "operation": "-" }, "operation": "=" }, { "lhs": { "type": "PlainIntegerConstant", "value": "0" }, "type": "PlainIntegerRelation", "rhs": { "name": "T9", "type": "PlainIntegerVariable" }, "operation": "<" }, { "lhs": { "name": "T9", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "name": "T9", "type": "PlainIntegerVariable" }, "operation": "<" } ] }, "ground": ["T9"], "free": [], "exprvars": [ "T12", "T9" ] } }, "4": { "goal": [ { "clause": 0, "scope": 1, "term": "(triangle T2 T3)" }, { "clause": 1, "scope": 1, "term": "(triangle T2 T3)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T2"], "free": [], "exprvars": [] } }, "1696": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "1695": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (> T9 (0)) (',' (is X11 (- T9 (1))) (',' (triangle X11 X12) (is T11 (+ X12 T9)))))" }], "kb": { "nonunifying": [[ "(triangle T9 T3)", "(triangle (0) (0))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T9"], "free": [ "X11", "X12" ], "exprvars": [] } }, "1694": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [{ "lhs": { "type": "PlainIntegerConstant", "value": "0" }, "type": "PlainIntegerRelation", "rhs": { "type": "PlainIntegerConstant", "value": "0" }, "operation": ">=" }] }, "ground": [], "free": [ "X5", "X6" ], "exprvars": [] } }, "1719": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [[ "(triangle T9 T3)", "(triangle (0) (0))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [ { "lhs": { "name": "T12", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "name": "T9", "type": "PlainIntegerVariable" }, { "type": "PlainIntegerConstant", "value": "1" } ], "type": "PlainIntegerOperation", "operation": "-" }, "operation": "=" }, { "lhs": { "arguments": [ { "name": "T9", "type": "PlainIntegerVariable" }, { "type": "PlainIntegerConstant", "value": "1" } ], "type": "PlainIntegerOperation", "operation": "-" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "name": "T9", "type": "PlainIntegerVariable" }, { "type": "PlainIntegerConstant", "value": "1" } ], "type": "PlainIntegerOperation", "operation": "-" }, "operation": "=" }, { "lhs": { "name": "T13", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "type": "PlainIntegerConstant", "value": "0" }, { "name": "T9", "type": "PlainIntegerVariable" } ], "type": "PlainIntegerOperation", "operation": "+" }, "operation": "=" }, { "lhs": { "type": "PlainIntegerConstant", "value": "0" }, "type": "PlainIntegerRelation", "rhs": { "name": "T9", "type": "PlainIntegerVariable" }, "operation": "<" }, { "lhs": { "name": "T9", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "name": "T9", "type": "PlainIntegerVariable" }, "operation": "<" } ] }, "ground": [ "T13", "T9" ], "free": [], "exprvars": [ "T13", "T12", "T9" ] } }, "1718": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [ { "lhs": { "name": "T12", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "name": "T9", "type": "PlainIntegerVariable" }, { "type": "PlainIntegerConstant", "value": "1" } ], "type": "PlainIntegerOperation", "operation": "-" }, "operation": "=" }, { "lhs": { "type": "PlainIntegerConstant", "value": "0" }, "type": "PlainIntegerRelation", "rhs": { "name": "T9", "type": "PlainIntegerVariable" }, "operation": "<" } ] }, "ground": [], "free": [], "exprvars": [ "T12", "T9" ] } }, "1717": { "goal": [{ "clause": -1, "scope": -1, "term": "(is T11 (+ (0) T9))" }], "kb": { "nonunifying": [[ "(triangle T9 T3)", "(triangle (0) (0))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [ { "lhs": { "name": "T12", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "name": "T9", "type": "PlainIntegerVariable" }, { "type": "PlainIntegerConstant", "value": "1" } ], "type": "PlainIntegerOperation", "operation": "-" }, "operation": "=" }, { "lhs": { "arguments": [ { "name": "T9", "type": "PlainIntegerVariable" }, { "type": "PlainIntegerConstant", "value": "1" } ], "type": "PlainIntegerOperation", "operation": "-" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "name": "T9", "type": "PlainIntegerVariable" }, { "type": "PlainIntegerConstant", "value": "1" } ], "type": "PlainIntegerOperation", "operation": "-" }, "operation": "=" }, { "lhs": { "type": "PlainIntegerConstant", "value": "0" }, "type": "PlainIntegerRelation", "rhs": { "name": "T9", "type": "PlainIntegerVariable" }, "operation": "<" }, { "lhs": { "name": "T9", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "name": "T9", "type": "PlainIntegerVariable" }, "operation": "<" } ] }, "ground": ["T9"], "free": [], "exprvars": [ "T12", "T9" ] } }, "1716": { "goal": [{ "clause": 1, "scope": 2, "term": "(',' (triangle T12 X12) (is T11 (+ X12 T9)))" }], "kb": { "nonunifying": [[ "(triangle T9 T3)", "(triangle (0) (0))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [ { "lhs": { "name": "T12", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "name": "T9", "type": "PlainIntegerVariable" }, { "type": "PlainIntegerConstant", "value": "1" } ], "type": "PlainIntegerOperation", "operation": "-" }, "operation": "=" }, { "lhs": { "type": "PlainIntegerConstant", "value": "0" }, "type": "PlainIntegerRelation", "rhs": { "name": "T9", "type": "PlainIntegerVariable" }, "operation": "<" } ] }, "ground": [ "T12", "T9" ], "free": ["X12"], "exprvars": [ "T12", "T9" ] } }, "1715": { "goal": [{ "clause": 0, "scope": 2, "term": "(',' (triangle T12 X12) (is T11 (+ X12 T9)))" }], "kb": { "nonunifying": [[ "(triangle T9 T3)", "(triangle (0) (0))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [ { "lhs": { "name": "T12", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "name": "T9", "type": "PlainIntegerVariable" }, { "type": "PlainIntegerConstant", "value": "1" } ], "type": "PlainIntegerOperation", "operation": "-" }, "operation": "=" }, { "lhs": { "type": "PlainIntegerConstant", "value": "0" }, "type": "PlainIntegerRelation", "rhs": { "name": "T9", "type": "PlainIntegerVariable" }, "operation": "<" } ] }, "ground": [ "T12", "T9" ], "free": ["X12"], "exprvars": [ "T12", "T9" ] } }, "1714": { "goal": [ { "clause": 0, "scope": 2, "term": "(',' (triangle T12 X12) (is T11 (+ X12 T9)))" }, { "clause": 1, "scope": 2, "term": "(',' (triangle T12 X12) (is T11 (+ X12 T9)))" } ], "kb": { "nonunifying": [[ "(triangle T9 T3)", "(triangle (0) (0))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [ { "lhs": { "name": "T12", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "name": "T9", "type": "PlainIntegerVariable" }, { "type": "PlainIntegerConstant", "value": "1" } ], "type": "PlainIntegerOperation", "operation": "-" }, "operation": "=" }, { "lhs": { "type": "PlainIntegerConstant", "value": "0" }, "type": "PlainIntegerRelation", "rhs": { "name": "T9", "type": "PlainIntegerVariable" }, "operation": "<" } ] }, "ground": [ "T12", "T9" ], "free": ["X12"], "exprvars": [ "T12", "T9" ] } }, "1713": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (triangle T12 X12) (is T11 (+ X12 T9)))" }], "kb": { "nonunifying": [[ "(triangle T9 T3)", "(triangle (0) (0))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [ { "lhs": { "name": "T12", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "name": "T9", "type": "PlainIntegerVariable" }, { "type": "PlainIntegerConstant", "value": "1" } ], "type": "PlainIntegerOperation", "operation": "-" }, "operation": "=" }, { "lhs": { "type": "PlainIntegerConstant", "value": "0" }, "type": "PlainIntegerRelation", "rhs": { "name": "T9", "type": "PlainIntegerVariable" }, "operation": "<" } ] }, "ground": [ "T12", "T9" ], "free": [ "X11", "X12" ], "exprvars": [ "T12", "T9" ] } } }, "edges": [ { "from": 3, "to": 4, "label": "CASE" }, { "from": 4, "to": 12, "label": "EVAL with clause\ntriangle(0, 0).\nand substitutionT2 -> 0,\nT3 -> 0" }, { "from": 4, "to": 14, "label": "EVAL-BACKTRACK" }, { "from": 12, "to": 23, "label": "SUCCESS" }, { "from": 14, "to": 1695, "label": "ONLY EVAL with clause\ntriangle(X9, X10) :- ','(>(X9, 0), ','(is(X11, -(X9, 1)), ','(triangle(X11, X12), is(X10, +(X12, X9))))).\nand substitutionT2 -> T9,\nX9 -> T9,\nT3 -> T11,\nX10 -> T11,\nT10 -> T11" }, { "from": 23, "to": 24, "label": "ONLY EVAL with clause\ntriangle(X3, X4) :- ','(>(X3, 0), ','(is(X5, -(X3, 1)), ','(triangle(X5, X6), is(X4, +(X6, X3))))).\nand substitutionX3 -> 0,\nT3 -> T6,\nX4 -> T6,\nT5 -> T6" }, { "from": 24, "to": 1694, "label": "ARITHCOMP FAIL" }, { "from": 1695, "to": 1696, "label": "IS ERROR" }, { "from": 1695, "to": 1711, "label": "ARITHCOMP SUCCESS" }, { "from": 1695, "to": 1712, "label": "ARITHCOMP FAIL" }, { "from": 1711, "to": 1713, "label": "\nX11 -> T12" }, { "from": 1713, "to": 1714, "label": "CASE" }, { "from": 1714, "to": 1715, "label": "PARALLEL" }, { "from": 1714, "to": 1716, "label": "PARALLEL" }, { "from": 1715, "to": 1717, "label": "EVAL with clause\ntriangle(0, 0).\nand substitutionT12 -> 0,\nX12 -> 0" }, { "from": 1715, "to": 1718, "label": "EVAL-BACKTRACK" }, { "from": 1716, "to": 1722, "label": "ONLY EVAL with clause\ntriangle(X21, X22) :- ','(>(X21, 0), ','(is(X23, -(X21, 1)), ','(triangle(X23, X24), is(X22, +(X24, X21))))).\nand substitutionT12 -> T16,\nX21 -> T16,\nX12 -> X25,\nX22 -> X25" }, { "from": 1717, "to": 1719, "label": "\nT11 -> T13" }, { "from": 1717, "to": 1720, "label": "IS FAIL" }, { "from": 1719, "to": 1721, "label": "SUCCESS" } ], "type": "Graph" } } ---------------------------------------- (2) Obligation: Triples: Clauses: Afs: ---------------------------------------- (3) TPisEmptyProof (EQUIVALENT) There are no more dependency triples. Hence, the dependency triple problem trivially terminates. ---------------------------------------- (4) YES