/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 loop(g,g,g,g) w.r.t. the given Prolog program could successfully be proven: (0) Prolog (1) PrologToDTProblemTransformerProof [SOUND, 59 ms] (2) TRIPLES (3) TPisEmptyProof [EQUIVALENT, 0 ms] (4) YES ---------------------------------------- (0) Obligation: Clauses: loop(A, B, C, R) :- ','(>(R, 0), ','(>=(-(B, C), 1), ','(=:=(A, C), ','(is(B1, 10), ','(is(C1, +(C, +(1, R))), ','(is(A1, C1), loop(A1, B1, C1, R))))))). Query: loop(g,g,g,g) ---------------------------------------- (1) PrologToDTProblemTransformerProof (SOUND) Built DT problem from termination graph DT10. { "root": 3, "program": { "directives": [], "clauses": [[ "(loop A B C R)", "(',' (> R (0)) (',' (>= (- B C) (1)) (',' (=:= A C) (',' (is B1 (10)) (',' (is C1 (+ C (+ (1) R))) (',' (is A1 C1) (loop A1 B1 C1 R)))))))" ]] }, "graph": { "nodes": { "2452": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "2451": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [ { "lhs": { "type": "PlainIntegerConstant", "value": "0" }, "type": "PlainIntegerRelation", "rhs": { "name": "T12", "type": "PlainIntegerVariable" }, "operation": "<" }, { "lhs": { "type": "PlainIntegerConstant", "value": "1" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "name": "T10", "type": "PlainIntegerVariable" }, { "name": "T11", "type": "PlainIntegerVariable" } ], "type": "PlainIntegerOperation", "operation": "-" }, "operation": ">" } ] }, "ground": [ "T12", "T11", "T10", "T9" ], "free": [ "X9", "X10", "X11" ], "exprvars": [ "T12", "T11", "T10" ] } }, "2450": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (=:= T9 T11) (',' (is X9 (10)) (',' (is X10 (+ T11 (+ (1) T12))) (',' (is X11 X10) (loop X11 X9 X10 T12)))))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [ { "lhs": { "type": "PlainIntegerConstant", "value": "0" }, "type": "PlainIntegerRelation", "rhs": { "name": "T12", "type": "PlainIntegerVariable" }, "operation": "<" }, { "lhs": { "type": "PlainIntegerConstant", "value": "1" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "name": "T10", "type": "PlainIntegerVariable" }, { "name": "T11", "type": "PlainIntegerVariable" } ], "type": "PlainIntegerOperation", "operation": "-" }, "operation": "<=" } ] }, "ground": [ "T12", "T11", "T10", "T9" ], "free": [ "X9", "X10", "X11" ], "exprvars": [ "T12", "T11", "T10" ] } }, "type": "Nodes", "395": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (>= (- T10 T11) (1)) (',' (=:= T9 T11) (',' (is X9 (10)) (',' (is X10 (+ T11 (+ (1) T12))) (',' (is X11 X10) (loop X11 X9 X10 T12))))))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [{ "lhs": { "type": "PlainIntegerConstant", "value": "0" }, "type": "PlainIntegerRelation", "rhs": { "name": "T12", "type": "PlainIntegerVariable" }, "operation": "<" }] }, "ground": [ "T12", "T11", "T10", "T9" ], "free": [ "X9", "X10", "X11" ], "exprvars": ["T12"] } }, "397": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [{ "lhs": { "type": "PlainIntegerConstant", "value": "0" }, "type": "PlainIntegerRelation", "rhs": { "name": "T12", "type": "PlainIntegerVariable" }, "operation": ">=" }] }, "ground": [ "T12", "T11", "T10", "T9" ], "free": [ "X9", "X10", "X11" ], "exprvars": ["T12"] } }, "2656": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (> T27 (0)) (',' (>= (- T25 T26) (1)) (',' (=:= T24 T26) (',' (is X27 (10)) (',' (is X28 (+ T26 (+ (1) T27))) (',' (is X29 X28) (loop X29 X27 X28 T27)))))))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [ { "lhs": { "name": "T9", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "name": "T11", "type": "PlainIntegerVariable" }, "operation": "=" }, { "lhs": { "name": "T13", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "type": "PlainIntegerConstant", "value": "10" }, "operation": "=" }, { "lhs": { "name": "T14", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "name": "T11", "type": "PlainIntegerVariable" }, { "arguments": [ { "type": "PlainIntegerConstant", "value": "1" }, { "name": "T12", "type": "PlainIntegerVariable" } ], "type": "PlainIntegerOperation", "operation": "+" } ], "type": "PlainIntegerOperation", "operation": "+" }, "operation": "=" }, { "lhs": { "name": "T15", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "name": "T14", "type": "PlainIntegerVariable" }, "operation": "=" }, { "lhs": { "name": "T11", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "name": "T11", "type": "PlainIntegerVariable" }, "operation": "=" }, { "lhs": { "type": "PlainIntegerConstant", "value": "10" }, "type": "PlainIntegerRelation", "rhs": { "type": "PlainIntegerConstant", "value": "10" }, "operation": "=" }, { "lhs": { "arguments": [ { "name": "T11", "type": "PlainIntegerVariable" }, { "arguments": [ { "type": "PlainIntegerConstant", "value": "1" }, { "name": "T27", "type": "PlainIntegerVariable" } ], "type": "PlainIntegerOperation", "operation": "+" } ], "type": "PlainIntegerOperation", "operation": "+" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "name": "T11", "type": "PlainIntegerVariable" }, { "arguments": [ { "type": "PlainIntegerConstant", "value": "1" }, { "name": "T12", "type": "PlainIntegerVariable" } ], "type": "PlainIntegerOperation", "operation": "+" } ], "type": "PlainIntegerOperation", "operation": "+" }, "operation": "=" }, { "lhs": { "name": "T26", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "name": "T14", "type": "PlainIntegerVariable" }, "operation": "=" }, { "lhs": { "type": "PlainIntegerConstant", "value": "0" }, "type": "PlainIntegerRelation", "rhs": { "name": "T12", "type": "PlainIntegerVariable" }, "operation": "<" }, { "lhs": { "name": "T27", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "name": "T12", "type": "PlainIntegerVariable" }, "operation": "<" }, { "lhs": { "type": "PlainIntegerConstant", "value": "1" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "name": "T10", "type": "PlainIntegerVariable" }, { "name": "T11", "type": "PlainIntegerVariable" } ], "type": "PlainIntegerOperation", "operation": "-" }, "operation": "<=" }, { "lhs": { "arguments": [ { "name": "T10", "type": "PlainIntegerVariable" }, { "name": "T11", "type": "PlainIntegerVariable" } ], "type": "PlainIntegerOperation", "operation": "-" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "name": "T10", "type": "PlainIntegerVariable" }, { "name": "T11", "type": "PlainIntegerVariable" } ], "type": "PlainIntegerOperation", "operation": "-" }, "operation": "<=" } ] }, "ground": [ "T24", "T25", "T26", "T27" ], "free": [ "X27", "X28", "X29" ], "exprvars": [ "T14", "T25", "T13", "T24", "T12", "T11", "T27", "T10", "T9", "T15", "T26" ] } }, "3": { "goal": [{ "clause": -1, "scope": -1, "term": "(loop T1 T2 T3 T4)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T4", "T1", "T2", "T3" ], "free": [], "exprvars": [] } }, "2655": { "goal": [{ "clause": 0, "scope": 2, "term": "(loop T15 T13 T14 T12)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [ { "lhs": { "name": "T9", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "name": "T11", "type": "PlainIntegerVariable" }, "operation": "=" }, { "lhs": { "name": "T13", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "type": "PlainIntegerConstant", "value": "10" }, "operation": "=" }, { "lhs": { "name": "T14", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "name": "T11", "type": "PlainIntegerVariable" }, { "arguments": [ { "type": "PlainIntegerConstant", "value": "1" }, { "name": "T12", "type": "PlainIntegerVariable" } ], "type": "PlainIntegerOperation", "operation": "+" } ], "type": "PlainIntegerOperation", "operation": "+" }, "operation": "=" }, { "lhs": { "name": "T15", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "name": "T14", "type": "PlainIntegerVariable" }, "operation": "=" }, { "lhs": { "type": "PlainIntegerConstant", "value": "0" }, "type": "PlainIntegerRelation", "rhs": { "name": "T12", "type": "PlainIntegerVariable" }, "operation": "<" }, { "lhs": { "type": "PlainIntegerConstant", "value": "1" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "name": "T10", "type": "PlainIntegerVariable" }, { "name": "T11", "type": "PlainIntegerVariable" } ], "type": "PlainIntegerOperation", "operation": "-" }, "operation": "<=" } ] }, "ground": [ "T14", "T13", "T12", "T15" ], "free": [], "exprvars": [ "T14", "T13", "T12", "T11", "T10", "T9", "T15" ] } }, "400": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "6": { "goal": [{ "clause": 0, "scope": 1, "term": "(loop T1 T2 T3 T4)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T4", "T1", "T2", "T3" ], "free": [], "exprvars": [] } }, "2630": { "goal": [{ "clause": -1, "scope": -1, "term": "(loop T15 T13 T14 T12)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [ { "lhs": { "name": "T9", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "name": "T11", "type": "PlainIntegerVariable" }, "operation": "=" }, { "lhs": { "name": "T13", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "type": "PlainIntegerConstant", "value": "10" }, "operation": "=" }, { "lhs": { "name": "T14", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "name": "T11", "type": "PlainIntegerVariable" }, { "arguments": [ { "type": "PlainIntegerConstant", "value": "1" }, { "name": "T12", "type": "PlainIntegerVariable" } ], "type": "PlainIntegerOperation", "operation": "+" } ], "type": "PlainIntegerOperation", "operation": "+" }, "operation": "=" }, { "lhs": { "name": "T15", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "name": "T14", "type": "PlainIntegerVariable" }, "operation": "=" }, { "lhs": { "type": "PlainIntegerConstant", "value": "0" }, "type": "PlainIntegerRelation", "rhs": { "name": "T12", "type": "PlainIntegerVariable" }, "operation": "<" }, { "lhs": { "type": "PlainIntegerConstant", "value": "1" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "name": "T10", "type": "PlainIntegerVariable" }, { "name": "T11", "type": "PlainIntegerVariable" } ], "type": "PlainIntegerOperation", "operation": "-" }, "operation": "<=" } ] }, "ground": [ "T14", "T13", "T12", "T11", "T10", "T9", "T15" ], "free": [ "X9", "X10", "X11" ], "exprvars": [ "T14", "T13", "T12", "T11", "T10", "T9", "T15" ] } }, "7": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (> T12 (0)) (',' (>= (- T10 T11) (1)) (',' (=:= T9 T11) (',' (is X9 (10)) (',' (is X10 (+ T11 (+ (1) T12))) (',' (is X11 X10) (loop X11 X9 X10 T12)))))))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T9", "T10", "T11", "T12" ], "free": [ "X9", "X10", "X11" ], "exprvars": [] } }, "8": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "2629": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (is X11 T14) (loop X11 T13 T14 T12))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [ { "lhs": { "name": "T9", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "name": "T11", "type": "PlainIntegerVariable" }, "operation": "=" }, { "lhs": { "name": "T13", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "type": "PlainIntegerConstant", "value": "10" }, "operation": "=" }, { "lhs": { "name": "T14", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "name": "T11", "type": "PlainIntegerVariable" }, { "arguments": [ { "type": "PlainIntegerConstant", "value": "1" }, { "name": "T12", "type": "PlainIntegerVariable" } ], "type": "PlainIntegerOperation", "operation": "+" } ], "type": "PlainIntegerOperation", "operation": "+" }, "operation": "=" }, { "lhs": { "type": "PlainIntegerConstant", "value": "0" }, "type": "PlainIntegerRelation", "rhs": { "name": "T12", "type": "PlainIntegerVariable" }, "operation": "<" }, { "lhs": { "type": "PlainIntegerConstant", "value": "1" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "name": "T10", "type": "PlainIntegerVariable" }, { "name": "T11", "type": "PlainIntegerVariable" } ], "type": "PlainIntegerOperation", "operation": "-" }, "operation": "<=" } ] }, "ground": [ "T14", "T13", "T12", "T11", "T10", "T9" ], "free": [ "X9", "X10", "X11" ], "exprvars": [ "T14", "T13", "T12", "T11", "T10", "T9" ] } }, "2628": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (is X10 (+ T11 (+ (1) T12))) (',' (is X11 X10) (loop X11 T13 X10 T12)))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [ { "lhs": { "name": "T9", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "name": "T11", "type": "PlainIntegerVariable" }, "operation": "=" }, { "lhs": { "name": "T13", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "type": "PlainIntegerConstant", "value": "10" }, "operation": "=" }, { "lhs": { "type": "PlainIntegerConstant", "value": "0" }, "type": "PlainIntegerRelation", "rhs": { "name": "T12", "type": "PlainIntegerVariable" }, "operation": "<" }, { "lhs": { "type": "PlainIntegerConstant", "value": "1" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "name": "T10", "type": "PlainIntegerVariable" }, { "name": "T11", "type": "PlainIntegerVariable" } ], "type": "PlainIntegerOperation", "operation": "-" }, "operation": "<=" } ] }, "ground": [ "T13", "T12", "T11", "T10", "T9" ], "free": [ "X9", "X10", "X11" ], "exprvars": [ "T13", "T12", "T11", "T10", "T9" ] } }, "2627": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [ { "lhs": { "name": "T9", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "name": "T11", "type": "PlainIntegerVariable" }, "operation": "!=" }, { "lhs": { "type": "PlainIntegerConstant", "value": "0" }, "type": "PlainIntegerRelation", "rhs": { "name": "T12", "type": "PlainIntegerVariable" }, "operation": "<" }, { "lhs": { "type": "PlainIntegerConstant", "value": "1" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "name": "T10", "type": "PlainIntegerVariable" }, { "name": "T11", "type": "PlainIntegerVariable" } ], "type": "PlainIntegerOperation", "operation": "-" }, "operation": "<=" } ] }, "ground": [ "T12", "T11", "T10", "T9" ], "free": [ "X9", "X10", "X11" ], "exprvars": [ "T12", "T11", "T10", "T9" ] } }, "2626": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (is X9 (10)) (',' (is X10 (+ T11 (+ (1) T12))) (',' (is X11 X10) (loop X11 X9 X10 T12))))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [ { "lhs": { "name": "T9", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "name": "T11", "type": "PlainIntegerVariable" }, "operation": "=" }, { "lhs": { "type": "PlainIntegerConstant", "value": "0" }, "type": "PlainIntegerRelation", "rhs": { "name": "T12", "type": "PlainIntegerVariable" }, "operation": "<" }, { "lhs": { "type": "PlainIntegerConstant", "value": "1" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "name": "T10", "type": "PlainIntegerVariable" }, { "name": "T11", "type": "PlainIntegerVariable" } ], "type": "PlainIntegerOperation", "operation": "-" }, "operation": "<=" } ] }, "ground": [ "T12", "T11", "T10", "T9" ], "free": [ "X9", "X10", "X11" ], "exprvars": [ "T12", "T11", "T10", "T9" ] } } }, "edges": [ { "from": 3, "to": 6, "label": "CASE" }, { "from": 6, "to": 7, "label": "ONLY EVAL with clause\nloop(X5, X6, X7, X8) :- ','(>(X8, 0), ','(>=(-(X6, X7), 1), ','(=:=(X5, X7), ','(is(X9, 10), ','(is(X10, +(X7, +(1, X8))), ','(is(X11, X10), loop(X11, X9, X10, X8))))))).\nand substitutionT1 -> T9,\nX5 -> T9,\nT2 -> T10,\nX6 -> T10,\nT3 -> T11,\nX7 -> T11,\nT4 -> T12,\nX8 -> T12" }, { "from": 7, "to": 8, "label": "IS ERROR" }, { "from": 7, "to": 395, "label": "ARITHCOMP SUCCESS" }, { "from": 7, "to": 397, "label": "ARITHCOMP FAIL" }, { "from": 395, "to": 400, "label": "IS ERROR" }, { "from": 395, "to": 2450, "label": "ARITHCOMP SUCCESS" }, { "from": 395, "to": 2451, "label": "ARITHCOMP FAIL" }, { "from": 2450, "to": 2452, "label": "IS ERROR" }, { "from": 2450, "to": 2626, "label": "ARITHCOMP SUCCESS" }, { "from": 2450, "to": 2627, "label": "ARITHCOMP FAIL" }, { "from": 2626, "to": 2628, "label": "\nX9 -> T13" }, { "from": 2628, "to": 2629, "label": "\nX10 -> T14" }, { "from": 2629, "to": 2630, "label": "\nX11 -> T15" }, { "from": 2630, "to": 2655, "label": "CASE" }, { "from": 2655, "to": 2656, "label": "ONLY EVAL with clause\nloop(X23, X24, X25, X26) :- ','(>(X26, 0), ','(>=(-(X24, X25), 1), ','(=:=(X23, X25), ','(is(X27, 10), ','(is(X28, +(X25, +(1, X26))), ','(is(X29, X28), loop(X29, X27, X28, X26))))))).\nand substitutionT15 -> T24,\nX23 -> T24,\nT13 -> T25,\nX24 -> T25,\nT14 -> T26,\nX25 -> T26,\nT12 -> T27,\nX26 -> T27" } ], "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