/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 tak(g,g,g,a) w.r.t. the given Prolog program could successfully be proven: (0) Prolog (1) PrologToDTProblemTransformerProof [SOUND, 62 ms] (2) TRIPLES (3) TPisEmptyProof [EQUIVALENT, 0 ms] (4) YES ---------------------------------------- (0) Obligation: Clauses: tak(X, Y, Z, A) :- ','(=<(X, Y), ','(!, =(Z, A))). tak(X, Y, Z, A) :- ','(is(X1, -(X, 1)), ','(is(Y1, -(Y, 1)), ','(is(Z1, -(Z, 1)), ','(tak(Z1, X, Y, A3), ','(tak(Y1, Z, X, A2), ','(tak(X1, Y, Z, A1), tak(A1, A2, A3, A))))))). test :- ','(tak(14, 12, 6, X), ','(write(X), nl)). Query: tak(g,g,g,a) ---------------------------------------- (1) PrologToDTProblemTransformerProof (SOUND) Built DT problem from termination graph DT10. { "root": 1, "program": { "directives": [], "clauses": [ [ "(tak X Y Z A)", "(',' (=< X Y) (',' (!) (= Z A)))" ], [ "(tak X Y Z A)", "(',' (is X1 (- X (1))) (',' (is Y1 (- Y (1))) (',' (is Z1 (- Z (1))) (',' (tak Z1 X Y A3) (',' (tak Y1 Z X A2) (',' (tak X1 Y Z A1) (tak A1 A2 A3 A)))))))" ], [ "(test)", "(',' (tak (14) (12) (6) X) (',' (write X) (nl)))" ] ] }, "graph": { "nodes": { "3123": { "goal": [{ "clause": -1, "scope": -1, "term": "(= T11 T13)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [{ "lhs": { "name": "T9", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "name": "T10", "type": "PlainIntegerVariable" }, "operation": "<=" }] }, "ground": ["T11"], "free": [], "exprvars": [ "T10", "T9" ] } }, "3122": { "goal": [{ "clause": 1, "scope": 1, "term": "(tak T9 T10 T11 T4)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [{ "lhs": { "name": "T9", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "name": "T10", "type": "PlainIntegerVariable" }, "operation": ">" }] }, "ground": [ "T11", "T10", "T9" ], "free": [], "exprvars": [ "T10", "T9" ] } }, "3231": { "goal": [ { "clause": -1, "scope": -1, "term": "(',' (',' (=< T34 T35) (',' (!_2) (= T36 X38))) (',' (tak T26 T22 T35 X22) (',' (tak T25 T36 T22 X23) (tak X23 X22 X38 T24))))" }, { "clause": 1, "scope": 2, "term": "(',' (tak T34 T35 T36 X21) (',' (tak T26 T22 T35 X22) (',' (tak T25 T36 T22 X23) (tak X23 X22 X21 T24))))" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [ { "lhs": { "name": "T25", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "name": "T20", "type": "PlainIntegerVariable" }, { "type": "PlainIntegerConstant", "value": "1" } ], "type": "PlainIntegerOperation", "operation": "-" }, "operation": "=" }, { "lhs": { "name": "T26", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "name": "T21", "type": "PlainIntegerVariable" }, { "type": "PlainIntegerConstant", "value": "1" } ], "type": "PlainIntegerOperation", "operation": "-" }, "operation": "=" }, { "lhs": { "name": "T27", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "name": "T22", "type": "PlainIntegerVariable" }, { "type": "PlainIntegerConstant", "value": "1" } ], "type": "PlainIntegerOperation", "operation": "-" }, "operation": "=" }, { "lhs": { "arguments": [ { "name": "T35", "type": "PlainIntegerVariable" }, { "type": "PlainIntegerConstant", "value": "1" } ], "type": "PlainIntegerOperation", "operation": "-" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "name": "T20", "type": "PlainIntegerVariable" }, { "type": "PlainIntegerConstant", "value": "1" } ], "type": "PlainIntegerOperation", "operation": "-" }, "operation": "=" }, { "lhs": { "arguments": [ { "name": "T36", "type": "PlainIntegerVariable" }, { "type": "PlainIntegerConstant", "value": "1" } ], "type": "PlainIntegerOperation", "operation": "-" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "name": "T21", "type": "PlainIntegerVariable" }, { "type": "PlainIntegerConstant", "value": "1" } ], "type": "PlainIntegerOperation", "operation": "-" }, "operation": "=" }, { "lhs": { "arguments": [ { "name": "T22", "type": "PlainIntegerVariable" }, { "type": "PlainIntegerConstant", "value": "1" } ], "type": "PlainIntegerOperation", "operation": "-" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "name": "T22", "type": "PlainIntegerVariable" }, { "type": "PlainIntegerConstant", "value": "1" } ], "type": "PlainIntegerOperation", "operation": "-" }, "operation": "=" }, { "lhs": { "name": "T9", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "name": "T10", "type": "PlainIntegerVariable" }, "operation": ">" }, { "lhs": { "name": "T21", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "name": "T10", "type": "PlainIntegerVariable" }, "operation": ">" }, { "lhs": { "name": "T10", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "name": "T10", "type": "PlainIntegerVariable" }, "operation": ">" }, { "lhs": { "name": "T10", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "name": "T10", "type": "PlainIntegerVariable" }, "operation": ">" } ] }, "ground": [ "T25", "T22", "T26", "T34", "T35", "T36" ], "free": [ "X21", "X22", "X23", "X38" ], "exprvars": [ "T20", "T25", "T36", "T35", "T34", "T22", "T27", "T10", "T21", "T9", "T26" ] } }, "3230": { "goal": [ { "clause": 0, "scope": 2, "term": "(',' (tak T27 T20 T21 X21) (',' (tak T26 T22 T20 X22) (',' (tak T25 T21 T22 X23) (tak X23 X22 X21 T24))))" }, { "clause": 1, "scope": 2, "term": "(',' (tak T27 T20 T21 X21) (',' (tak T26 T22 T20 X22) (',' (tak T25 T21 T22 X23) (tak X23 X22 X21 T24))))" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [ { "lhs": { "name": "T25", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "name": "T20", "type": "PlainIntegerVariable" }, { "type": "PlainIntegerConstant", "value": "1" } ], "type": "PlainIntegerOperation", "operation": "-" }, "operation": "=" }, { "lhs": { "name": "T26", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "name": "T21", "type": "PlainIntegerVariable" }, { "type": "PlainIntegerConstant", "value": "1" } ], "type": "PlainIntegerOperation", "operation": "-" }, "operation": "=" }, { "lhs": { "name": "T27", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "name": "T22", "type": "PlainIntegerVariable" }, { "type": "PlainIntegerConstant", "value": "1" } ], "type": "PlainIntegerOperation", "operation": "-" }, "operation": "=" }, { "lhs": { "name": "T9", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "name": "T10", "type": "PlainIntegerVariable" }, "operation": ">" }, { "lhs": { "name": "T21", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "name": "T10", "type": "PlainIntegerVariable" }, "operation": ">" } ] }, "ground": [ "T20", "T25", "T22", "T27", "T21", "T26" ], "free": [ "X21", "X22", "X23" ], "exprvars": [ "T20", "T25", "T22", "T27", "T10", "T21", "T9", "T26" ] } }, "type": "Nodes", "3086": { "goal": [ { "clause": -1, "scope": -1, "term": "(',' (!_1) (= T11 T13))" }, { "clause": 1, "scope": 1, "term": "(tak T9 T10 T11 T4)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [{ "lhs": { "name": "T9", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "name": "T10", "type": "PlainIntegerVariable" }, "operation": "<=" }] }, "ground": [ "T11", "T10", "T9" ], "free": [], "exprvars": [ "T10", "T9" ] } }, "1": { "goal": [{ "clause": -1, "scope": -1, "term": "(tak T1 T2 T3 T4)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T1", "T2", "T3" ], "free": [], "exprvars": [] } }, "3229": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (tak T27 T20 T21 X21) (',' (tak T26 T22 T20 X22) (',' (tak T25 T21 T22 X23) (tak X23 X22 X21 T24))))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [ { "lhs": { "name": "T25", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "name": "T20", "type": "PlainIntegerVariable" }, { "type": "PlainIntegerConstant", "value": "1" } ], "type": "PlainIntegerOperation", "operation": "-" }, "operation": "=" }, { "lhs": { "name": "T26", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "name": "T21", "type": "PlainIntegerVariable" }, { "type": "PlainIntegerConstant", "value": "1" } ], "type": "PlainIntegerOperation", "operation": "-" }, "operation": "=" }, { "lhs": { "name": "T27", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "name": "T22", "type": "PlainIntegerVariable" }, { "type": "PlainIntegerConstant", "value": "1" } ], "type": "PlainIntegerOperation", "operation": "-" }, "operation": "=" }, { "lhs": { "name": "T9", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "name": "T10", "type": "PlainIntegerVariable" }, "operation": ">" }, { "lhs": { "name": "T21", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "name": "T10", "type": "PlainIntegerVariable" }, "operation": ">" } ] }, "ground": [ "T20", "T25", "T22", "T27", "T21", "T26" ], "free": [ "X18", "X19", "X20", "X21", "X22", "X23" ], "exprvars": [ "T20", "T25", "T22", "T27", "T10", "T21", "T9", "T26" ] } }, "3228": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "3": { "goal": [ { "clause": 0, "scope": 1, "term": "(tak T1 T2 T3 T4)" }, { "clause": 1, "scope": 1, "term": "(tak T1 T2 T3 T4)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T1", "T2", "T3" ], "free": [], "exprvars": [] } }, "3227": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (is X20 (- T22 (1))) (',' (tak X20 T20 T21 X21) (',' (tak T26 T22 T20 X22) (',' (tak T25 T21 T22 X23) (tak X23 X22 X21 T24)))))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [ { "lhs": { "name": "T25", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "name": "T20", "type": "PlainIntegerVariable" }, { "type": "PlainIntegerConstant", "value": "1" } ], "type": "PlainIntegerOperation", "operation": "-" }, "operation": "=" }, { "lhs": { "name": "T26", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "name": "T21", "type": "PlainIntegerVariable" }, { "type": "PlainIntegerConstant", "value": "1" } ], "type": "PlainIntegerOperation", "operation": "-" }, "operation": "=" }, { "lhs": { "name": "T9", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "name": "T10", "type": "PlainIntegerVariable" }, "operation": ">" }, { "lhs": { "name": "T21", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "name": "T10", "type": "PlainIntegerVariable" }, "operation": ">" } ] }, "ground": [ "T20", "T25", "T22", "T21", "T26" ], "free": [ "X18", "X19", "X20", "X21", "X22", "X23" ], "exprvars": [ "T20", "T25", "T10", "T21", "T9", "T26" ] } }, "3127": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (is X18 (- T20 (1))) (',' (is X19 (- T21 (1))) (',' (is X20 (- T22 (1))) (',' (tak X20 T20 T21 X21) (',' (tak X19 T22 T20 X22) (',' (tak X18 T21 T22 X23) (tak X23 X22 X21 T24)))))))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [ { "lhs": { "name": "T9", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "name": "T10", "type": "PlainIntegerVariable" }, "operation": ">" }, { "lhs": { "name": "T21", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "name": "T10", "type": "PlainIntegerVariable" }, "operation": ">" } ] }, "ground": [ "T20", "T21", "T22" ], "free": [ "X18", "X19", "X20", "X21", "X22", "X23" ], "exprvars": [ "T20", "T10", "T21", "T9" ] } }, "3226": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (is X19 (- T21 (1))) (',' (is X20 (- T22 (1))) (',' (tak X20 T20 T21 X21) (',' (tak X19 T22 T20 X22) (',' (tak T25 T21 T22 X23) (tak X23 X22 X21 T24))))))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [ { "lhs": { "name": "T25", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "name": "T20", "type": "PlainIntegerVariable" }, { "type": "PlainIntegerConstant", "value": "1" } ], "type": "PlainIntegerOperation", "operation": "-" }, "operation": "=" }, { "lhs": { "name": "T9", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "name": "T10", "type": "PlainIntegerVariable" }, "operation": ">" }, { "lhs": { "name": "T21", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "name": "T10", "type": "PlainIntegerVariable" }, "operation": ">" } ] }, "ground": [ "T20", "T25", "T22", "T21" ], "free": [ "X18", "X19", "X20", "X21", "X22", "X23" ], "exprvars": [ "T20", "T25", "T10", "T21", "T9" ] } }, "3126": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "6": { "goal": [ { "clause": -1, "scope": -1, "term": "(',' (=< T9 T10) (',' (!_1) (= T11 T13)))" }, { "clause": 1, "scope": 1, "term": "(tak T9 T10 T11 T4)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T9", "T10", "T11" ], "free": [], "exprvars": [] } }, "3125": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [{ "lhs": { "name": "T9", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "name": "T10", "type": "PlainIntegerVariable" }, "operation": "<=" }] }, "ground": [], "free": [], "exprvars": [ "T10", "T9" ] } }, "7": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "3124": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } } }, "edges": [ { "from": 1, "to": 3, "label": "CASE" }, { "from": 3, "to": 6, "label": "ONLY EVAL with clause\ntak(X6, X7, X8, X9) :- ','(=<(X6, X7), ','(!_1, =(X8, X9))).\nand substitutionT1 -> T9,\nX6 -> T9,\nT2 -> T10,\nX7 -> T10,\nT3 -> T11,\nX8 -> T11,\nT4 -> T13,\nX9 -> T13,\nT12 -> T13" }, { "from": 6, "to": 7, "label": "IS ERROR" }, { "from": 6, "to": 3086, "label": "ARITHCOMP SUCCESS" }, { "from": 6, "to": 3122, "label": "ARITHCOMP FAIL" }, { "from": 3086, "to": 3123, "label": "CUT" }, { "from": 3122, "to": 3127, "label": "ONLY EVAL with clause\ntak(X14, X15, X16, X17) :- ','(is(X18, -(X14, 1)), ','(is(X19, -(X15, 1)), ','(is(X20, -(X16, 1)), ','(tak(X20, X14, X15, X21), ','(tak(X19, X16, X14, X22), ','(tak(X18, X15, X16, X23), tak(X23, X22, X21, X17))))))).\nand substitutionT9 -> T20,\nX14 -> T20,\nT10 -> T21,\nX15 -> T21,\nT11 -> T22,\nX16 -> T22,\nT4 -> T24,\nX17 -> T24,\nT23 -> T24" }, { "from": 3123, "to": 3124, "label": "UNIFY CASE with substitutionT11 -> T15,\nT13 -> T15" }, { "from": 3123, "to": 3125, "label": "UNIFY-BACKTRACK" }, { "from": 3124, "to": 3126, "label": "SUCCESS" }, { "from": 3127, "to": 3226, "label": "\nX18 -> T25" }, { "from": 3226, "to": 3227, "label": "\nX19 -> T26" }, { "from": 3227, "to": 3228, "label": "IS ERROR" }, { "from": 3227, "to": 3229, "label": "\nX20 -> T27" }, { "from": 3229, "to": 3230, "label": "CASE" }, { "from": 3230, "to": 3231, "label": "ONLY EVAL with clause\ntak(X34, X35, X36, X37) :- ','(=<(X34, X35), ','(!_2, =(X36, X37))).\nand substitutionT27 -> T34,\nX34 -> T34,\nT20 -> T35,\nX35 -> T35,\nT21 -> T36,\nX36 -> T36,\nX21 -> X38,\nX37 -> X38" } ], "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