/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 factorial(g,a) w.r.t. the given Prolog program could successfully be proven: (0) Prolog (1) PrologToIRSwTTransformerProof [SOUND, 47 ms] (2) TRUE ---------------------------------------- (0) Obligation: Clauses: factorial(N, F) :- factorial(N, 1, F). factorial(N, T, F) :- ','(>(N, 0), ','(is(T1, *(T, N)), ','(is(N1, -(N, 1)), factorial(N1, T1, F)))). factorial(0, F, F). Query: factorial(g,a) ---------------------------------------- (1) PrologToIRSwTTransformerProof (SOUND) Transformed Prolog program to IRSwT according to method in Master Thesis of A. Weinert { "root": 3, "program": { "directives": [], "clauses": [ [ "(factorial N F)", "(factorial N (1) F)" ], [ "(factorial N T F)", "(',' (> N (0)) (',' (is T1 (* T N)) (',' (is N1 (- N (1))) (factorial N1 T1 F))))" ], [ "(factorial (0) F F)", null ] ] }, "graph": { "nodes": { "13": { "goal": [ { "clause": 1, "scope": 2, "term": "(factorial T11 (1) T13)" }, { "clause": 2, "scope": 2, "term": "(factorial T11 (1) T13)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T11"], "free": [], "exprvars": [] } }, "15": { "goal": [{ "clause": 1, "scope": 2, "term": "(factorial T11 (1) T13)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T11"], "free": [], "exprvars": [] } }, "17": { "goal": [{ "clause": 2, "scope": 2, "term": "(factorial T11 (1) T13)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T11"], "free": [], "exprvars": [] } }, "18": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (> T26 (0)) (',' (is X36 (* (1) T26)) (',' (is X37 (- T26 (1))) (factorial X37 X36 T28))))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T26"], "free": [ "X36", "X37" ], "exprvars": [] } }, "19": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "type": "Nodes", "1931": { "goal": [ { "clause": 1, "scope": 3, "term": "(factorial T30 T29 T28)" }, { "clause": 2, "scope": 3, "term": "(factorial T30 T29 T28)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [ { "lhs": { "name": "T29", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "type": "PlainIntegerConstant", "value": "1" }, { "name": "T26", "type": "PlainIntegerVariable" } ], "type": "PlainIntegerOperation", "operation": "*" }, "operation": "=" }, { "lhs": { "name": "T30", "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": [ "T30", "T29" ], "free": [], "exprvars": [ "T30", "T29", "T26" ] } }, "1953": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "1930": { "goal": [{ "clause": -1, "scope": -1, "term": "(factorial T30 T29 T28)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [ { "lhs": { "name": "T29", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "type": "PlainIntegerConstant", "value": "1" }, { "name": "T26", "type": "PlainIntegerVariable" } ], "type": "PlainIntegerOperation", "operation": "*" }, "operation": "=" }, { "lhs": { "name": "T30", "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": [ "T30", "T29", "T26" ], "free": [ "X36", "X37" ], "exprvars": [ "T30", "T29", "T26" ] } }, "1952": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "3": { "goal": [{ "clause": -1, "scope": -1, "term": "(factorial T2 T3)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T2"], "free": [], "exprvars": [] } }, "1951": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "4": { "goal": [{ "clause": 0, "scope": 1, "term": "(factorial T2 T3)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T2"], "free": [], "exprvars": [] } }, "1950": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [ { "lhs": { "name": "T29", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "type": "PlainIntegerConstant", "value": "1" }, { "name": "T26", "type": "PlainIntegerVariable" } ], "type": "PlainIntegerOperation", "operation": "*" }, "operation": "=" }, { "lhs": { "name": "T30", "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": "T26", "type": "PlainIntegerVariable" } ], "type": "PlainIntegerOperation", "operation": "*" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "type": "PlainIntegerConstant", "value": "1" }, { "name": "T26", "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": [], "free": [], "exprvars": [ "T30", "T29", "T54", "T26" ] } }, "1929": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (is X37 (- T26 (1))) (factorial X37 T29 T28))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [ { "lhs": { "name": "T29", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "type": "PlainIntegerConstant", "value": "1" }, { "name": "T26", "type": "PlainIntegerVariable" } ], "type": "PlainIntegerOperation", "operation": "*" }, "operation": "=" }, { "lhs": { "type": "PlainIntegerConstant", "value": "0" }, "type": "PlainIntegerRelation", "rhs": { "name": "T26", "type": "PlainIntegerVariable" }, "operation": "<" } ] }, "ground": [ "T29", "T26" ], "free": [ "X36", "X37" ], "exprvars": [ "T29", "T26" ] } }, "9": { "goal": [{ "clause": -1, "scope": -1, "term": "(factorial T11 (1) T13)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T11"], "free": [], "exprvars": [] } }, "1917": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [{ "lhs": { "type": "PlainIntegerConstant", "value": "0" }, "type": "PlainIntegerRelation", "rhs": { "name": "T26", "type": "PlainIntegerVariable" }, "operation": ">=" }] }, "ground": ["T26"], "free": [ "X36", "X37" ], "exprvars": ["T26"] } }, "1916": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (is X36 (* (1) T26)) (',' (is X37 (- T26 (1))) (factorial X37 X36 T28)))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [{ "lhs": { "type": "PlainIntegerConstant", "value": "0" }, "type": "PlainIntegerRelation", "rhs": { "name": "T26", "type": "PlainIntegerVariable" }, "operation": "<" }] }, "ground": ["T26"], "free": [ "X36", "X37" ], "exprvars": ["T26"] } }, "1949": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [ { "lhs": { "name": "T29", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "type": "PlainIntegerConstant", "value": "1" }, { "name": "T26", "type": "PlainIntegerVariable" } ], "type": "PlainIntegerOperation", "operation": "*" }, "operation": "=" }, { "lhs": { "name": "T30", "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": [], "free": [], "exprvars": [ "T30", "T29", "T26" ] } }, "1948": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [ { "lhs": { "name": "T29", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "type": "PlainIntegerConstant", "value": "1" }, { "name": "T26", "type": "PlainIntegerVariable" } ], "type": "PlainIntegerOperation", "operation": "*" }, "operation": "=" }, { "lhs": { "name": "T30", "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": "T26", "type": "PlainIntegerVariable" } ], "type": "PlainIntegerOperation", "operation": "*" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "type": "PlainIntegerConstant", "value": "1" }, { "name": "T26", "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": [], "free": [], "exprvars": [ "T30", "T29", "T54", "T26" ] } }, "1935": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (> T48 (0)) (',' (is X62 (* T49 T48)) (',' (is X63 (- T48 (1))) (factorial X63 X62 T51))))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [ { "lhs": { "name": "T29", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "type": "PlainIntegerConstant", "value": "1" }, { "name": "T26", "type": "PlainIntegerVariable" } ], "type": "PlainIntegerOperation", "operation": "*" }, "operation": "=" }, { "lhs": { "name": "T30", "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": "T26", "type": "PlainIntegerVariable" } ], "type": "PlainIntegerOperation", "operation": "*" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "type": "PlainIntegerConstant", "value": "1" }, { "name": "T26", "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": [ "T48", "T49" ], "free": [ "X62", "X63" ], "exprvars": [ "T30", "T29", "T49", "T26", "T48" ] } }, "1934": { "goal": [{ "clause": 2, "scope": 3, "term": "(factorial T30 T29 T28)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [ { "lhs": { "name": "T29", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "type": "PlainIntegerConstant", "value": "1" }, { "name": "T26", "type": "PlainIntegerVariable" } ], "type": "PlainIntegerOperation", "operation": "*" }, "operation": "=" }, { "lhs": { "name": "T30", "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": [ "T30", "T29" ], "free": [], "exprvars": [ "T30", "T29", "T26" ] } }, "1933": { "goal": [{ "clause": 1, "scope": 3, "term": "(factorial T30 T29 T28)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [ { "lhs": { "name": "T29", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "type": "PlainIntegerConstant", "value": "1" }, { "name": "T26", "type": "PlainIntegerVariable" } ], "type": "PlainIntegerOperation", "operation": "*" }, "operation": "=" }, { "lhs": { "name": "T30", "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": [ "T30", "T29" ], "free": [], "exprvars": [ "T30", "T29", "T26" ] } } }, "edges": [ { "from": 3, "to": 4, "label": "CASE" }, { "from": 4, "to": 9, "label": "ONLY EVAL with clause\nfactorial(X10, X11) :- factorial(X10, 1, X11).\nand substitutionT2 -> T11,\nX10 -> T11,\nT3 -> T13,\nX11 -> T13,\nT12 -> T13" }, { "from": 9, "to": 13, "label": "CASE" }, { "from": 13, "to": 15, "label": "PARALLEL" }, { "from": 13, "to": 17, "label": "PARALLEL" }, { "from": 15, "to": 18, "label": "ONLY EVAL with clause\nfactorial(X33, X34, X35) :- ','(>(X33, 0), ','(is(X36, *(X34, X33)), ','(is(X37, -(X33, 1)), factorial(X37, X36, X35)))).\nand substitutionT11 -> T26,\nX33 -> T26,\nX34 -> 1,\nT13 -> T28,\nX35 -> T28,\nT27 -> T28" }, { "from": 17, "to": 1951, "label": "EVAL with clause\nfactorial(0, X69, X69).\nand substitutionT11 -> 0,\nX69 -> 1,\nT13 -> 1" }, { "from": 17, "to": 1952, "label": "EVAL-BACKTRACK" }, { "from": 18, "to": 19, "label": "IS ERROR" }, { "from": 18, "to": 1916, "label": "ARITHCOMP SUCCESS" }, { "from": 18, "to": 1917, "label": "ARITHCOMP FAIL" }, { "from": 1916, "to": 1929, "label": "\nX36 -> T29" }, { "from": 1929, "to": 1930, "label": "\nX37 -> T30" }, { "from": 1930, "to": 1931, "label": "CASE" }, { "from": 1931, "to": 1933, "label": "PARALLEL" }, { "from": 1931, "to": 1934, "label": "PARALLEL" }, { "from": 1933, "to": 1935, "label": "ONLY EVAL with clause\nfactorial(X59, X60, X61) :- ','(>(X59, 0), ','(is(X62, *(X60, X59)), ','(is(X63, -(X59, 1)), factorial(X63, X62, X61)))).\nand substitutionT30 -> T48,\nX59 -> T48,\nT29 -> T49,\nX60 -> T49,\nT28 -> T51,\nX61 -> T51,\nT50 -> T51" }, { "from": 1934, "to": 1948, "label": "EVAL with clause\nfactorial(0, X66, X66).\nand substitutionT30 -> 0,\nT29 -> T54,\nX66 -> T54,\nT28 -> T54" }, { "from": 1934, "to": 1949, "label": "EVAL-BACKTRACK" }, { "from": 1948, "to": 1950, "label": "SUCCESS" }, { "from": 1951, "to": 1953, "label": "SUCCESS" } ], "type": "Graph" } } ---------------------------------------- (2) TRUE