/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) w.r.t. the given Prolog program could successfully be proven: (0) Prolog (1) PrologToDTProblemTransformerProof [SOUND, 30 ms] (2) TRIPLES (3) TPisEmptyProof [EQUIVALENT, 0 ms] (4) YES ---------------------------------------- (0) Obligation: Clauses: loop(A, B, R) :- ','(>(R, 0), ','(>(B, 0), ','(is(B1, -(B, +(1, R))), ','(is(A1, -(A, +(1, R))), loop(A1, B1, R))))). Query: loop(g,g,g) ---------------------------------------- (1) PrologToDTProblemTransformerProof (SOUND) Built DT problem from termination graph DT10. { "root": 1, "program": { "directives": [], "clauses": [[ "(loop A B R)", "(',' (> R (0)) (',' (> B (0)) (',' (is B1 (- B (+ (1) R))) (',' (is A1 (- A (+ (1) R))) (loop A1 B1 R)))))" ]] }, "graph": { "nodes": { "type": "Nodes", "1635": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (> T8 (0)) (',' (is X7 (- T8 (+ (1) T9))) (',' (is X8 (- T7 (+ (1) T9))) (loop X8 X7 T9))))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [{ "lhs": { "type": "PlainIntegerConstant", "value": "0" }, "type": "PlainIntegerRelation", "rhs": { "name": "T9", "type": "PlainIntegerVariable" }, "operation": "<" }] }, "ground": [ "T7", "T8", "T9" ], "free": [ "X7", "X8" ], "exprvars": ["T9"] } }, "1833": { "goal": [{ "clause": -1, "scope": -1, "term": "(loop T11 T10 T9)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [ { "lhs": { "name": "T10", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "name": "T8", "type": "PlainIntegerVariable" }, { "arguments": [ { "type": "PlainIntegerConstant", "value": "1" }, { "name": "T9", "type": "PlainIntegerVariable" } ], "type": "PlainIntegerOperation", "operation": "+" } ], "type": "PlainIntegerOperation", "operation": "-" }, "operation": "=" }, { "lhs": { "name": "T11", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "name": "T7", "type": "PlainIntegerVariable" }, { "arguments": [ { "type": "PlainIntegerConstant", "value": "1" }, { "name": "T9", "type": "PlainIntegerVariable" } ], "type": "PlainIntegerOperation", "operation": "+" } ], "type": "PlainIntegerOperation", "operation": "-" }, "operation": "=" }, { "lhs": { "type": "PlainIntegerConstant", "value": "0" }, "type": "PlainIntegerRelation", "rhs": { "name": "T9", "type": "PlainIntegerVariable" }, "operation": "<" }, { "lhs": { "type": "PlainIntegerConstant", "value": "0" }, "type": "PlainIntegerRelation", "rhs": { "name": "T8", "type": "PlainIntegerVariable" }, "operation": "<" } ] }, "ground": [ "T7", "T11", "T8", "T10", "T9" ], "free": [ "X7", "X8" ], "exprvars": [ "T7", "T11", "T8", "T10", "T9" ] } }, "1": { "goal": [{ "clause": -1, "scope": -1, "term": "(loop T1 T2 T3)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T1", "T2", "T3" ], "free": [], "exprvars": [] } }, "1832": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "1655": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "1831": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (is X8 (- T7 (+ (1) T9))) (loop X8 T10 T9))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [ { "lhs": { "name": "T10", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "name": "T8", "type": "PlainIntegerVariable" }, { "arguments": [ { "type": "PlainIntegerConstant", "value": "1" }, { "name": "T9", "type": "PlainIntegerVariable" } ], "type": "PlainIntegerOperation", "operation": "+" } ], "type": "PlainIntegerOperation", "operation": "-" }, "operation": "=" }, { "lhs": { "type": "PlainIntegerConstant", "value": "0" }, "type": "PlainIntegerRelation", "rhs": { "name": "T9", "type": "PlainIntegerVariable" }, "operation": "<" }, { "lhs": { "type": "PlainIntegerConstant", "value": "0" }, "type": "PlainIntegerRelation", "rhs": { "name": "T8", "type": "PlainIntegerVariable" }, "operation": "<" } ] }, "ground": [ "T7", "T8", "T10", "T9" ], "free": [ "X7", "X8" ], "exprvars": [ "T8", "T10", "T9" ] } }, "5": { "goal": [{ "clause": 0, "scope": 1, "term": "(loop T1 T2 T3)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T1", "T2", "T3" ], "free": [], "exprvars": [] } }, "1652": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [{ "lhs": { "type": "PlainIntegerConstant", "value": "0" }, "type": "PlainIntegerRelation", "rhs": { "name": "T9", "type": "PlainIntegerVariable" }, "operation": ">=" }] }, "ground": [ "T7", "T8", "T9" ], "free": [ "X7", "X8" ], "exprvars": ["T9"] } }, "9": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (> T9 (0)) (',' (> T8 (0)) (',' (is X7 (- T8 (+ (1) T9))) (',' (is X8 (- T7 (+ (1) T9))) (loop X8 X7 T9)))))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T7", "T8", "T9" ], "free": [ "X7", "X8" ], "exprvars": [] } }, "1905": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (> T20 (0)) (',' (> T19 (0)) (',' (is X20 (- T19 (+ (1) T20))) (',' (is X21 (- T18 (+ (1) T20))) (loop X21 X20 T20)))))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [ { "lhs": { "name": "T10", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "name": "T8", "type": "PlainIntegerVariable" }, { "arguments": [ { "type": "PlainIntegerConstant", "value": "1" }, { "name": "T9", "type": "PlainIntegerVariable" } ], "type": "PlainIntegerOperation", "operation": "+" } ], "type": "PlainIntegerOperation", "operation": "-" }, "operation": "=" }, { "lhs": { "name": "T11", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "name": "T7", "type": "PlainIntegerVariable" }, { "arguments": [ { "type": "PlainIntegerConstant", "value": "1" }, { "name": "T9", "type": "PlainIntegerVariable" } ], "type": "PlainIntegerOperation", "operation": "+" } ], "type": "PlainIntegerOperation", "operation": "-" }, "operation": "=" }, { "lhs": { "arguments": [ { "name": "T8", "type": "PlainIntegerVariable" }, { "arguments": [ { "type": "PlainIntegerConstant", "value": "1" }, { "name": "T20", "type": "PlainIntegerVariable" } ], "type": "PlainIntegerOperation", "operation": "+" } ], "type": "PlainIntegerOperation", "operation": "-" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "name": "T8", "type": "PlainIntegerVariable" }, { "arguments": [ { "type": "PlainIntegerConstant", "value": "1" }, { "name": "T9", "type": "PlainIntegerVariable" } ], "type": "PlainIntegerOperation", "operation": "+" } ], "type": "PlainIntegerOperation", "operation": "-" }, "operation": "=" }, { "lhs": { "arguments": [ { "name": "T7", "type": "PlainIntegerVariable" }, { "arguments": [ { "type": "PlainIntegerConstant", "value": "1" }, { "name": "T20", "type": "PlainIntegerVariable" } ], "type": "PlainIntegerOperation", "operation": "+" } ], "type": "PlainIntegerOperation", "operation": "-" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "name": "T7", "type": "PlainIntegerVariable" }, { "arguments": [ { "type": "PlainIntegerConstant", "value": "1" }, { "name": "T9", "type": "PlainIntegerVariable" } ], "type": "PlainIntegerOperation", "operation": "+" } ], "type": "PlainIntegerOperation", "operation": "-" }, "operation": "=" }, { "lhs": { "type": "PlainIntegerConstant", "value": "0" }, "type": "PlainIntegerRelation", "rhs": { "name": "T9", "type": "PlainIntegerVariable" }, "operation": "<" }, { "lhs": { "type": "PlainIntegerConstant", "value": "0" }, "type": "PlainIntegerRelation", "rhs": { "name": "T8", "type": "PlainIntegerVariable" }, "operation": "<" }, { "lhs": { "name": "T20", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "name": "T9", "type": "PlainIntegerVariable" }, "operation": "<" }, { "lhs": { "name": "T8", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "name": "T8", "type": "PlainIntegerVariable" }, "operation": "<" } ] }, "ground": [ "T18", "T19", "T20" ], "free": [ "X20", "X21" ], "exprvars": [ "T20", "T19", "T18", "T7", "T11", "T8", "T10", "T9" ] } }, "1824": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [ { "lhs": { "type": "PlainIntegerConstant", "value": "0" }, "type": "PlainIntegerRelation", "rhs": { "name": "T9", "type": "PlainIntegerVariable" }, "operation": "<" }, { "lhs": { "type": "PlainIntegerConstant", "value": "0" }, "type": "PlainIntegerRelation", "rhs": { "name": "T8", "type": "PlainIntegerVariable" }, "operation": ">=" } ] }, "ground": [ "T7", "T8", "T9" ], "free": [ "X7", "X8" ], "exprvars": [ "T8", "T9" ] } }, "10": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "1823": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (is X7 (- T8 (+ (1) T9))) (',' (is X8 (- T7 (+ (1) T9))) (loop X8 X7 T9)))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [ { "lhs": { "type": "PlainIntegerConstant", "value": "0" }, "type": "PlainIntegerRelation", "rhs": { "name": "T9", "type": "PlainIntegerVariable" }, "operation": "<" }, { "lhs": { "type": "PlainIntegerConstant", "value": "0" }, "type": "PlainIntegerRelation", "rhs": { "name": "T8", "type": "PlainIntegerVariable" }, "operation": "<" } ] }, "ground": [ "T7", "T8", "T9" ], "free": [ "X7", "X8" ], "exprvars": [ "T8", "T9" ] } }, "1834": { "goal": [{ "clause": 0, "scope": 2, "term": "(loop T11 T10 T9)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [ { "lhs": { "name": "T10", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "name": "T8", "type": "PlainIntegerVariable" }, { "arguments": [ { "type": "PlainIntegerConstant", "value": "1" }, { "name": "T9", "type": "PlainIntegerVariable" } ], "type": "PlainIntegerOperation", "operation": "+" } ], "type": "PlainIntegerOperation", "operation": "-" }, "operation": "=" }, { "lhs": { "name": "T11", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "name": "T7", "type": "PlainIntegerVariable" }, { "arguments": [ { "type": "PlainIntegerConstant", "value": "1" }, { "name": "T9", "type": "PlainIntegerVariable" } ], "type": "PlainIntegerOperation", "operation": "+" } ], "type": "PlainIntegerOperation", "operation": "-" }, "operation": "=" }, { "lhs": { "type": "PlainIntegerConstant", "value": "0" }, "type": "PlainIntegerRelation", "rhs": { "name": "T9", "type": "PlainIntegerVariable" }, "operation": "<" }, { "lhs": { "type": "PlainIntegerConstant", "value": "0" }, "type": "PlainIntegerRelation", "rhs": { "name": "T8", "type": "PlainIntegerVariable" }, "operation": "<" } ] }, "ground": [ "T11", "T10", "T9" ], "free": [], "exprvars": [ "T7", "T11", "T8", "T10", "T9" ] } } }, "edges": [ { "from": 1, "to": 5, "label": "CASE" }, { "from": 5, "to": 9, "label": "ONLY EVAL with clause\nloop(X4, X5, X6) :- ','(>(X6, 0), ','(>(X5, 0), ','(is(X7, -(X5, +(1, X6))), ','(is(X8, -(X4, +(1, X6))), loop(X8, X7, X6))))).\nand substitutionT1 -> T7,\nX4 -> T7,\nT2 -> T8,\nX5 -> T8,\nT3 -> T9,\nX6 -> T9" }, { "from": 9, "to": 10, "label": "IS ERROR" }, { "from": 9, "to": 1635, "label": "ARITHCOMP SUCCESS" }, { "from": 9, "to": 1652, "label": "ARITHCOMP FAIL" }, { "from": 1635, "to": 1655, "label": "IS ERROR" }, { "from": 1635, "to": 1823, "label": "ARITHCOMP SUCCESS" }, { "from": 1635, "to": 1824, "label": "ARITHCOMP FAIL" }, { "from": 1823, "to": 1831, "label": "\nX7 -> T10" }, { "from": 1831, "to": 1832, "label": "IS ERROR" }, { "from": 1831, "to": 1833, "label": "\nX8 -> T11" }, { "from": 1833, "to": 1834, "label": "CASE" }, { "from": 1834, "to": 1905, "label": "ONLY EVAL with clause\nloop(X17, X18, X19) :- ','(>(X19, 0), ','(>(X18, 0), ','(is(X20, -(X18, +(1, X19))), ','(is(X21, -(X17, +(1, X19))), loop(X21, X20, X19))))).\nand substitutionT11 -> T18,\nX17 -> T18,\nT10 -> T19,\nX18 -> T19,\nT9 -> T20,\nX19 -> T20" } ], "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