/export/starexec/sandbox/solver/bin/starexec_run_standard /export/starexec/sandbox/benchmark/theBenchmark.pl /export/starexec/sandbox/output/output_files -------------------------------------------------------------------------------- YES proof of /export/starexec/sandbox/benchmark/theBenchmark.pl # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty Left Termination of the query pattern test_fun(g,g,g) w.r.t. the given Prolog program could successfully be proven: (0) Prolog (1) PrologToIRSwTTransformerProof [SOUND, 43 ms] (2) TRUE ---------------------------------------- (0) Obligation: Clauses: test_fun(X, Y, R) :- loop(X, Y, 1). loop(X, Y, R) :- ','(>(Y, 0), ','(is(R1, *(R, X)), ','(is(Y1, -(Y, 1)), loop(X, Y1, R1)))). loop(X, Y, R) :- =<(Y, 0). Query: test_fun(g,g,g) ---------------------------------------- (1) PrologToIRSwTTransformerProof (SOUND) Transformed Prolog program to IRSwT according to method in Master Thesis of A. Weinert { "root": 4, "program": { "directives": [], "clauses": [ [ "(test_fun X Y R)", "(loop X Y (1))" ], [ "(loop X Y R)", "(',' (> Y (0)) (',' (is R1 (* R X)) (',' (is Y1 (- Y (1))) (loop X Y1 R1))))" ], [ "(loop X Y R)", "(=< Y (0))" ] ] }, "graph": { "nodes": { "15": { "goal": [ { "clause": 1, "scope": 2, "term": "(loop T12 T13 (1))" }, { "clause": 2, "scope": 2, "term": "(loop T12 T13 (1))" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T12", "T13" ], "free": [], "exprvars": [] } }, "16": { "goal": [{ "clause": 1, "scope": 2, "term": "(loop T12 T13 (1))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T12", "T13" ], "free": [], "exprvars": [] } }, "17": { "goal": [{ "clause": 2, "scope": 2, "term": "(loop T12 T13 (1))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T12", "T13" ], "free": [], "exprvars": [] } }, "18": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (> T26 (0)) (',' (is X39 (* (1) T25)) (',' (is X40 (- T26 (1))) (loop T25 X40 X39))))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T25", "T26" ], "free": [ "X39", "X40" ], "exprvars": [] } }, "19": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "2188": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [{ "lhs": { "name": "T61", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "type": "PlainIntegerConstant", "value": "0" }, "operation": ">" }] }, "ground": ["T61"], "free": [], "exprvars": ["T61"] } }, "2187": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [{ "lhs": { "name": "T61", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "type": "PlainIntegerConstant", "value": "0" }, "operation": "<=" }] }, "ground": ["T61"], "free": [], "exprvars": ["T61"] } }, "2153": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (> T45 (0)) (',' (is X65 (* T46 T44)) (',' (is X66 (- T45 (1))) (loop T44 X66 X65))))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [ { "lhs": { "name": "T27", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "type": "PlainIntegerConstant", "value": "1" }, { "name": "T25", "type": "PlainIntegerVariable" } ], "type": "PlainIntegerOperation", "operation": "*" }, "operation": "=" }, { "lhs": { "name": "T28", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "name": "T26", "type": "PlainIntegerVariable" }, { "type": "PlainIntegerConstant", "value": "1" } ], "type": "PlainIntegerOperation", "operation": "-" }, "operation": "=" }, { "lhs": { "arguments": [ { "type": "PlainIntegerConstant", "value": "1" }, { "name": "T44", "type": "PlainIntegerVariable" } ], "type": "PlainIntegerOperation", "operation": "*" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "type": "PlainIntegerConstant", "value": "1" }, { "name": "T25", "type": "PlainIntegerVariable" } ], "type": "PlainIntegerOperation", "operation": "*" }, "operation": "=" }, { "lhs": { "arguments": [ { "name": "T26", "type": "PlainIntegerVariable" }, { "type": "PlainIntegerConstant", "value": "1" } ], "type": "PlainIntegerOperation", "operation": "-" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "name": "T26", "type": "PlainIntegerVariable" }, { "type": "PlainIntegerConstant", "value": "1" } ], "type": "PlainIntegerOperation", "operation": "-" }, "operation": "=" }, { "lhs": { "type": "PlainIntegerConstant", "value": "0" }, "type": "PlainIntegerRelation", "rhs": { "name": "T26", "type": "PlainIntegerVariable" }, "operation": "<" }, { "lhs": { "name": "T26", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "name": "T26", "type": "PlainIntegerVariable" }, "operation": "<" } ] }, "ground": [ "T44", "T45", "T46" ], "free": [ "X65", "X66" ], "exprvars": [ "T25", "T46", "T45", "T28", "T44", "T27", "T26" ] } }, "2164": { "goal": [{ "clause": -1, "scope": -1, "term": "(=< T54 (0))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [ { "lhs": { "name": "T27", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "type": "PlainIntegerConstant", "value": "1" }, { "name": "T25", "type": "PlainIntegerVariable" } ], "type": "PlainIntegerOperation", "operation": "*" }, "operation": "=" }, { "lhs": { "name": "T28", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "name": "T26", "type": "PlainIntegerVariable" }, { "type": "PlainIntegerConstant", "value": "1" } ], "type": "PlainIntegerOperation", "operation": "-" }, "operation": "=" }, { "lhs": { "arguments": [ { "type": "PlainIntegerConstant", "value": "1" }, { "name": "T53", "type": "PlainIntegerVariable" } ], "type": "PlainIntegerOperation", "operation": "*" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "type": "PlainIntegerConstant", "value": "1" }, { "name": "T25", "type": "PlainIntegerVariable" } ], "type": "PlainIntegerOperation", "operation": "*" }, "operation": "=" }, { "lhs": { "arguments": [ { "name": "T26", "type": "PlainIntegerVariable" }, { "type": "PlainIntegerConstant", "value": "1" } ], "type": "PlainIntegerOperation", "operation": "-" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "name": "T26", "type": "PlainIntegerVariable" }, { "type": "PlainIntegerConstant", "value": "1" } ], "type": "PlainIntegerOperation", "operation": "-" }, "operation": "=" }, { "lhs": { "type": "PlainIntegerConstant", "value": "0" }, "type": "PlainIntegerRelation", "rhs": { "name": "T26", "type": "PlainIntegerVariable" }, "operation": "<" }, { "lhs": { "name": "T26", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "name": "T26", "type": "PlainIntegerVariable" }, "operation": "<" } ] }, "ground": ["T54"], "free": [], "exprvars": [ "T53", "T25", "T28", "T55", "T27", "T54", "T26" ] } }, "type": "Nodes", "2151": { "goal": [{ "clause": 2, "scope": 3, "term": "(loop T25 T28 T27)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [ { "lhs": { "name": "T27", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "type": "PlainIntegerConstant", "value": "1" }, { "name": "T25", "type": "PlainIntegerVariable" } ], "type": "PlainIntegerOperation", "operation": "*" }, "operation": "=" }, { "lhs": { "name": "T28", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "name": "T26", "type": "PlainIntegerVariable" }, { "type": "PlainIntegerConstant", "value": "1" } ], "type": "PlainIntegerOperation", "operation": "-" }, "operation": "=" }, { "lhs": { "type": "PlainIntegerConstant", "value": "0" }, "type": "PlainIntegerRelation", "rhs": { "name": "T26", "type": "PlainIntegerVariable" }, "operation": "<" } ] }, "ground": [ "T25", "T28", "T27" ], "free": [], "exprvars": [ "T25", "T28", "T27", "T26" ] } }, "2150": { "goal": [{ "clause": 1, "scope": 3, "term": "(loop T25 T28 T27)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [ { "lhs": { "name": "T27", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "type": "PlainIntegerConstant", "value": "1" }, { "name": "T25", "type": "PlainIntegerVariable" } ], "type": "PlainIntegerOperation", "operation": "*" }, "operation": "=" }, { "lhs": { "name": "T28", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "name": "T26", "type": "PlainIntegerVariable" }, { "type": "PlainIntegerConstant", "value": "1" } ], "type": "PlainIntegerOperation", "operation": "-" }, "operation": "=" }, { "lhs": { "type": "PlainIntegerConstant", "value": "0" }, "type": "PlainIntegerRelation", "rhs": { "name": "T26", "type": "PlainIntegerVariable" }, "operation": "<" } ] }, "ground": [ "T25", "T28", "T27" ], "free": [], "exprvars": [ "T25", "T28", "T27", "T26" ] } }, "2182": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "2181": { "goal": [{ "clause": -1, "scope": -1, "term": "(=< T61 (0))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T61"], "free": [], "exprvars": [] } }, "2139": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "2138": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [{ "lhs": { "type": "PlainIntegerConstant", "value": "0" }, "type": "PlainIntegerRelation", "rhs": { "name": "T26", "type": "PlainIntegerVariable" }, "operation": ">=" }] }, "ground": [ "T25", "T26" ], "free": [ "X39", "X40" ], "exprvars": ["T26"] } }, "4": { "goal": [{ "clause": -1, "scope": -1, "term": "(test_fun T1 T2 T3)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T1", "T2", "T3" ], "free": [], "exprvars": [] } }, "5": { "goal": [{ "clause": 0, "scope": 1, "term": "(test_fun T1 T2 T3)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T1", "T2", "T3" ], "free": [], "exprvars": [] } }, "2147": { "goal": [ { "clause": 1, "scope": 3, "term": "(loop T25 T28 T27)" }, { "clause": 2, "scope": 3, "term": "(loop T25 T28 T27)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [ { "lhs": { "name": "T27", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "type": "PlainIntegerConstant", "value": "1" }, { "name": "T25", "type": "PlainIntegerVariable" } ], "type": "PlainIntegerOperation", "operation": "*" }, "operation": "=" }, { "lhs": { "name": "T28", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "name": "T26", "type": "PlainIntegerVariable" }, { "type": "PlainIntegerConstant", "value": "1" } ], "type": "PlainIntegerOperation", "operation": "-" }, "operation": "=" }, { "lhs": { "type": "PlainIntegerConstant", "value": "0" }, "type": "PlainIntegerRelation", "rhs": { "name": "T26", "type": "PlainIntegerVariable" }, "operation": "<" } ] }, "ground": [ "T25", "T28", "T27" ], "free": [], "exprvars": [ "T25", "T28", "T27", "T26" ] } }, "2135": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (is X39 (* (1) T25)) (',' (is X40 (- T26 (1))) (loop T25 X40 X39)))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [{ "lhs": { "type": "PlainIntegerConstant", "value": "0" }, "type": "PlainIntegerRelation", "rhs": { "name": "T26", "type": "PlainIntegerVariable" }, "operation": "<" }] }, "ground": [ "T25", "T26" ], "free": [ "X39", "X40" ], "exprvars": ["T26"] } }, "2146": { "goal": [{ "clause": -1, "scope": -1, "term": "(loop T25 T28 T27)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [ { "lhs": { "name": "T27", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "type": "PlainIntegerConstant", "value": "1" }, { "name": "T25", "type": "PlainIntegerVariable" } ], "type": "PlainIntegerOperation", "operation": "*" }, "operation": "=" }, { "lhs": { "name": "T28", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "name": "T26", "type": "PlainIntegerVariable" }, { "type": "PlainIntegerConstant", "value": "1" } ], "type": "PlainIntegerOperation", "operation": "-" }, "operation": "=" }, { "lhs": { "type": "PlainIntegerConstant", "value": "0" }, "type": "PlainIntegerRelation", "rhs": { "name": "T26", "type": "PlainIntegerVariable" }, "operation": "<" } ] }, "ground": [ "T25", "T28", "T27", "T26" ], "free": [ "X39", "X40" ], "exprvars": [ "T25", "T28", "T27", "T26" ] } }, "7": { "goal": [{ "clause": -1, "scope": -1, "term": "(loop T12 T13 (1))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T12", "T13" ], "free": [], "exprvars": [] } }, "2145": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (is X40 (- T26 (1))) (loop T25 X40 T27))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [ { "lhs": { "name": "T27", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "type": "PlainIntegerConstant", "value": "1" }, { "name": "T25", "type": "PlainIntegerVariable" } ], "type": "PlainIntegerOperation", "operation": "*" }, "operation": "=" }, { "lhs": { "type": "PlainIntegerConstant", "value": "0" }, "type": "PlainIntegerRelation", "rhs": { "name": "T26", "type": "PlainIntegerVariable" }, "operation": "<" } ] }, "ground": [ "T25", "T27", "T26" ], "free": [ "X39", "X40" ], "exprvars": [ "T25", "T27", "T26" ] } }, "2189": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [{ "lhs": { "name": "T61", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "type": "PlainIntegerConstant", "value": "0" }, "operation": "<=" }] }, "ground": [], "free": [], "exprvars": ["T61"] } } }, "edges": [ { "from": 4, "to": 5, "label": "CASE" }, { "from": 5, "to": 7, "label": "ONLY EVAL with clause\ntest_fun(X12, X13, X14) :- loop(X12, X13, 1).\nand substitutionT1 -> T12,\nX12 -> T12,\nT2 -> T13,\nX13 -> T13,\nT3 -> T14,\nX14 -> T14" }, { "from": 7, "to": 15, "label": "CASE" }, { "from": 15, "to": 16, "label": "PARALLEL" }, { "from": 15, "to": 17, "label": "PARALLEL" }, { "from": 16, "to": 18, "label": "ONLY EVAL with clause\nloop(X36, X37, X38) :- ','(>(X37, 0), ','(is(X39, *(X38, X36)), ','(is(X40, -(X37, 1)), loop(X36, X40, X39)))).\nand substitutionT12 -> T25,\nX36 -> T25,\nT13 -> T26,\nX37 -> T26,\nX38 -> 1" }, { "from": 17, "to": 2181, "label": "ONLY EVAL with clause\nloop(X82, X83, X84) :- =<(X83, 0).\nand substitutionT12 -> T60,\nX82 -> T60,\nT13 -> T61,\nX83 -> T61,\nX84 -> 1" }, { "from": 18, "to": 19, "label": "IS ERROR" }, { "from": 18, "to": 2135, "label": "ARITHCOMP SUCCESS" }, { "from": 18, "to": 2138, "label": "ARITHCOMP FAIL" }, { "from": 2135, "to": 2139, "label": "IS ERROR" }, { "from": 2135, "to": 2145, "label": "\nX39 -> T27" }, { "from": 2145, "to": 2146, "label": "\nX40 -> T28" }, { "from": 2146, "to": 2147, "label": "CASE" }, { "from": 2147, "to": 2150, "label": "PARALLEL" }, { "from": 2147, "to": 2151, "label": "PARALLEL" }, { "from": 2150, "to": 2153, "label": "ONLY EVAL with clause\nloop(X62, X63, X64) :- ','(>(X63, 0), ','(is(X65, *(X64, X62)), ','(is(X66, -(X63, 1)), loop(X62, X66, X65)))).\nand substitutionT25 -> T44,\nX62 -> T44,\nT28 -> T45,\nX63 -> T45,\nT27 -> T46,\nX64 -> T46" }, { "from": 2151, "to": 2164, "label": "ONLY EVAL with clause\nloop(X73, X74, X75) :- =<(X74, 0).\nand substitutionT25 -> T53,\nX73 -> T53,\nT28 -> T54,\nX74 -> T54,\nT27 -> T55,\nX75 -> T55" }, { "from": 2181, "to": 2182, "label": "IS ERROR" }, { "from": 2181, "to": 2187, "label": "ARITHCOMP SUCCESS" }, { "from": 2181, "to": 2188, "label": "ARITHCOMP FAIL" }, { "from": 2187, "to": 2189, "label": "SUCCESS" } ], "type": "Graph" } } ---------------------------------------- (2) TRUE