/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 fact(a,g) w.r.t. the given Prolog program could successfully be proven: (0) Prolog (1) PrologToIRSwTTransformerProof [SOUND, 44 ms] (2) IRSwT (3) IRSwTSimpleDependencyGraphProof [EQUIVALENT, 0 ms] (4) IRSwT (5) IntTRSCompressionProof [EQUIVALENT, 22 ms] (6) IRSwT (7) IRSFormatTransformerProof [EQUIVALENT, 0 ms] (8) IRSwT (9) IRSwTTerminationDigraphProof [EQUIVALENT, 7 ms] (10) IRSwT (11) IntTRSCompressionProof [EQUIVALENT, 0 ms] (12) IRSwT (13) TempFilterProof [SOUND, 38 ms] (14) IntTRS (15) RankingReductionPairProof [EQUIVALENT, 22 ms] (16) YES ---------------------------------------- (0) Obligation: Clauses: fact(X, Y) :- ','(is(0, X), =(Y, 1)). fact(X, Y) :- ','(is(1, X), =(Y, 1)). fact(X, Y) :- ','(>=(X, 2), ','(fact(-(X, 1), Y1), is(Y, *(Y1, X)))). Query: fact(a,g) ---------------------------------------- (1) PrologToIRSwTTransformerProof (SOUND) Transformed Prolog program to IRSwT according to method in Master Thesis of A. Weinert { "root": 1, "program": { "directives": [], "clauses": [ [ "(fact X Y)", "(',' (is (0) X) (= Y (1)))" ], [ "(fact X Y)", "(',' (is (1) X) (= Y (1)))" ], [ "(fact X Y)", "(',' (>= X (2)) (',' (fact (- X (1)) Y1) (is Y (* Y1 X))))" ] ] }, "graph": { "nodes": { "type": "Nodes", "2150": { "goal": [{ "clause": -1, "scope": -1, "term": "(is X75 (* T54 (- T52 (1))))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T52", "T54" ], "free": ["X75"], "exprvars": [] } }, "1734": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [{ "lhs": { "type": "PlainIntegerConstant", "value": "1" }, "type": "PlainIntegerRelation", "rhs": { "name": "T28", "type": "PlainIntegerVariable" }, "operation": "!=" }] }, "ground": [ "T28", "T27" ], "free": [], "exprvars": ["T28"] } }, "1898": { "goal": [ { "clause": 0, "scope": 2, "term": "(fact (- T36 (1)) X28)" }, { "clause": 1, "scope": 2, "term": "(fact (- T36 (1)) X28)" }, { "clause": 2, "scope": 2, "term": "(fact (- T36 (1)) X28)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [{ "lhs": { "type": "PlainIntegerConstant", "value": "2" }, "type": "PlainIntegerRelation", "rhs": { "name": "T36", "type": "PlainIntegerVariable" }, "operation": "<=" }] }, "ground": ["T36"], "free": ["X28"], "exprvars": ["T36"] } }, "1732": { "goal": [{ "clause": -1, "scope": -1, "term": "(= T27 (1))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [{ "lhs": { "type": "PlainIntegerConstant", "value": "1" }, "type": "PlainIntegerRelation", "rhs": { "name": "T28", "type": "PlainIntegerVariable" }, "operation": "=" }] }, "ground": [ "T28", "T27" ], "free": [], "exprvars": ["T28"] } }, "1897": { "goal": [{ "clause": -1, "scope": -1, "term": "(is T35 (* T38 T36))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T36", "T35", "T38" ], "free": [], "exprvars": [] } }, "1896": { "goal": [{ "clause": -1, "scope": -1, "term": "(fact (- T36 (1)) X28)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [{ "lhs": { "type": "PlainIntegerConstant", "value": "2" }, "type": "PlainIntegerRelation", "rhs": { "name": "T36", "type": "PlainIntegerVariable" }, "operation": "<=" }] }, "ground": ["T36"], "free": ["X28"], "exprvars": ["T36"] } }, "2149": { "goal": [{ "clause": -1, "scope": -1, "term": "(fact (- (- T52 (1)) (1)) X74)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [ { "lhs": { "type": "PlainIntegerConstant", "value": "2" }, "type": "PlainIntegerRelation", "rhs": { "name": "T36", "type": "PlainIntegerVariable" }, "operation": "<=" }, { "lhs": { "name": "T52", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "name": "T36", "type": "PlainIntegerVariable" }, "operation": "<=" }, { "lhs": { "type": "PlainIntegerConstant", "value": "2" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "name": "T52", "type": "PlainIntegerVariable" }, { "type": "PlainIntegerConstant", "value": "1" } ], "type": "PlainIntegerOperation", "operation": "-" }, "operation": "<=" } ] }, "ground": ["T52"], "free": ["X74"], "exprvars": [ "T36", "T52" ] } }, "1895": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [{ "lhs": { "type": "PlainIntegerConstant", "value": "2" }, "type": "PlainIntegerRelation", "rhs": { "name": "T36", "type": "PlainIntegerVariable" }, "operation": ">" }] }, "ground": [ "T36", "T35" ], "free": ["X28"], "exprvars": ["T36"] } }, "2148": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [ { "lhs": { "type": "PlainIntegerConstant", "value": "2" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "name": "T52", "type": "PlainIntegerVariable" }, { "type": "PlainIntegerConstant", "value": "1" } ], "type": "PlainIntegerOperation", "operation": "-" }, "operation": ">" }, { "lhs": { "type": "PlainIntegerConstant", "value": "2" }, "type": "PlainIntegerRelation", "rhs": { "name": "T36", "type": "PlainIntegerVariable" }, "operation": "<=" }, { "lhs": { "name": "T52", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "name": "T36", "type": "PlainIntegerVariable" }, "operation": "<=" } ] }, "ground": ["T52"], "free": [ "X75", "X74" ], "exprvars": [ "T36", "T52" ] } }, "1894": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (fact (- T36 (1)) X28) (is T35 (* X28 T36)))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [{ "lhs": { "type": "PlainIntegerConstant", "value": "2" }, "type": "PlainIntegerRelation", "rhs": { "name": "T36", "type": "PlainIntegerVariable" }, "operation": "<=" }] }, "ground": [ "T36", "T35" ], "free": ["X28"], "exprvars": ["T36"] } }, "2147": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (fact (- (- T52 (1)) (1)) X74) (is X75 (* X74 (- T52 (1)))))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [ { "lhs": { "type": "PlainIntegerConstant", "value": "2" }, "type": "PlainIntegerRelation", "rhs": { "name": "T36", "type": "PlainIntegerVariable" }, "operation": "<=" }, { "lhs": { "name": "T52", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "name": "T36", "type": "PlainIntegerVariable" }, "operation": "<=" }, { "lhs": { "type": "PlainIntegerConstant", "value": "2" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "name": "T52", "type": "PlainIntegerVariable" }, { "type": "PlainIntegerConstant", "value": "1" } ], "type": "PlainIntegerOperation", "operation": "-" }, "operation": "<=" } ] }, "ground": ["T52"], "free": [ "X75", "X74" ], "exprvars": [ "T36", "T52" ] } }, "710": { "goal": [{ "clause": 1, "scope": 1, "term": "(fact T1 T2)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T2"], "free": [], "exprvars": [] } }, "2025": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (is (1) (- T49 (1))) (= X64 (1)))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [ { "lhs": { "type": "PlainIntegerConstant", "value": "2" }, "type": "PlainIntegerRelation", "rhs": { "name": "T36", "type": "PlainIntegerVariable" }, "operation": "<=" }, { "lhs": { "name": "T49", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "name": "T36", "type": "PlainIntegerVariable" }, "operation": "<=" } ] }, "ground": ["T49"], "free": ["X64"], "exprvars": [ "T36", "T49" ] } }, "711": { "goal": [{ "clause": 2, "scope": 1, "term": "(fact T1 T2)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T2"], "free": [], "exprvars": [] } }, "2024": { "goal": [{ "clause": 2, "scope": 2, "term": "(fact (- T36 (1)) X28)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [{ "lhs": { "type": "PlainIntegerConstant", "value": "2" }, "type": "PlainIntegerRelation", "rhs": { "name": "T36", "type": "PlainIntegerVariable" }, "operation": "<=" }] }, "ground": ["T36"], "free": ["X28"], "exprvars": ["T36"] } }, "714": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (is (1) T28) (= T27 (1)))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T27"], "free": [], "exprvars": [] } }, "715": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "13": { "goal": [{ "clause": 0, "scope": 1, "term": "(fact T1 T2)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T2"], "free": [], "exprvars": [] } }, "14": { "goal": [ { "clause": 1, "scope": 1, "term": "(fact T1 T2)" }, { "clause": 2, "scope": 1, "term": "(fact T1 T2)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T2"], "free": [], "exprvars": [] } }, "15": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (is (0) T15) (= T14 (1)))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T14"], "free": [], "exprvars": [] } }, "16": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "1908": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (is (0) (- T44 (1))) (= X49 (1)))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [ { "lhs": { "type": "PlainIntegerConstant", "value": "2" }, "type": "PlainIntegerRelation", "rhs": { "name": "T36", "type": "PlainIntegerVariable" }, "operation": "<=" }, { "lhs": { "name": "T44", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "name": "T36", "type": "PlainIntegerVariable" }, "operation": "<=" } ] }, "ground": ["T44"], "free": ["X49"], "exprvars": [ "T36", "T44" ] } }, "2164": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [{ "lhs": { "name": "T57", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "name": "T38", "type": "PlainIntegerVariable" }, { "name": "T36", "type": "PlainIntegerVariable" } ], "type": "PlainIntegerOperation", "operation": "*" }, "operation": "=" }] }, "ground": [], "free": [], "exprvars": [ "T36", "T57", "T38" ] } }, "2163": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T36", "T35", "T38" ], "free": [], "exprvars": [ "T36", "T38" ] } }, "2162": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [{ "lhs": { "name": "T57", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "name": "T38", "type": "PlainIntegerVariable" }, { "name": "T36", "type": "PlainIntegerVariable" } ], "type": "PlainIntegerOperation", "operation": "*" }, "operation": "=" }] }, "ground": [ "T36", "T35", "T57", "T38" ], "free": [], "exprvars": [ "T36", "T57", "T38" ] } }, "2161": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "2160": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [{ "lhs": { "name": "T56", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "name": "T54", "type": "PlainIntegerVariable" }, { "arguments": [ { "name": "T52", "type": "PlainIntegerVariable" }, { "type": "PlainIntegerConstant", "value": "1" } ], "type": "PlainIntegerOperation", "operation": "-" } ], "type": "PlainIntegerOperation", "operation": "*" }, "operation": "=" }] }, "ground": [], "free": [], "exprvars": [ "T52", "T56", "T54" ] } }, "1": { "goal": [{ "clause": -1, "scope": -1, "term": "(fact T1 T2)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T2"], "free": [], "exprvars": [] } }, "1744": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [{ "lhs": { "type": "PlainIntegerConstant", "value": "1" }, "type": "PlainIntegerRelation", "rhs": { "name": "T28", "type": "PlainIntegerVariable" }, "operation": "=" }] }, "ground": [], "free": [], "exprvars": ["T28"] } }, "1741": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "2159": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [{ "lhs": { "name": "T56", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "name": "T54", "type": "PlainIntegerVariable" }, { "arguments": [ { "name": "T52", "type": "PlainIntegerVariable" }, { "type": "PlainIntegerConstant", "value": "1" } ], "type": "PlainIntegerOperation", "operation": "-" } ], "type": "PlainIntegerOperation", "operation": "*" }, "operation": "=" }] }, "ground": [ "T52", "T56", "T54" ], "free": ["X75"], "exprvars": [ "T52", "T56", "T54" ] } }, "2158": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "6": { "goal": [ { "clause": 0, "scope": 1, "term": "(fact T1 T2)" }, { "clause": 1, "scope": 1, "term": "(fact T1 T2)" }, { "clause": 2, "scope": 1, "term": "(fact T1 T2)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T2"], "free": [], "exprvars": [] } }, "1907": { "goal": [ { "clause": 1, "scope": 2, "term": "(fact (- T36 (1)) X28)" }, { "clause": 2, "scope": 2, "term": "(fact (- T36 (1)) X28)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [{ "lhs": { "type": "PlainIntegerConstant", "value": "2" }, "type": "PlainIntegerRelation", "rhs": { "name": "T36", "type": "PlainIntegerVariable" }, "operation": "<=" }] }, "ground": ["T36"], "free": ["X28"], "exprvars": ["T36"] } }, "1906": { "goal": [{ "clause": 0, "scope": 2, "term": "(fact (- T36 (1)) X28)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [{ "lhs": { "type": "PlainIntegerConstant", "value": "2" }, "type": "PlainIntegerRelation", "rhs": { "name": "T36", "type": "PlainIntegerVariable" }, "operation": "<=" }] }, "ground": ["T36"], "free": ["X28"], "exprvars": ["T36"] } }, "1747": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "2131": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (>= (- T52 (1)) (2)) (',' (fact (- (- T52 (1)) (1)) X74) (is X75 (* X74 (- T52 (1))))))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [ { "lhs": { "type": "PlainIntegerConstant", "value": "2" }, "type": "PlainIntegerRelation", "rhs": { "name": "T36", "type": "PlainIntegerVariable" }, "operation": "<=" }, { "lhs": { "name": "T52", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "name": "T36", "type": "PlainIntegerVariable" }, "operation": "<=" } ] }, "ground": ["T52"], "free": [ "X75", "X74" ], "exprvars": [ "T36", "T52" ] } }, "2130": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "693": { "goal": [{ "clause": -1, "scope": -1, "term": "(= T14 (1))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [{ "lhs": { "type": "PlainIntegerConstant", "value": "0" }, "type": "PlainIntegerRelation", "rhs": { "name": "T15", "type": "PlainIntegerVariable" }, "operation": "=" }] }, "ground": [ "T14", "T15" ], "free": [], "exprvars": ["T15"] } }, "694": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [{ "lhs": { "type": "PlainIntegerConstant", "value": "0" }, "type": "PlainIntegerRelation", "rhs": { "name": "T15", "type": "PlainIntegerVariable" }, "operation": "!=" }] }, "ground": [ "T14", "T15" ], "free": [], "exprvars": ["T15"] } }, "2129": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "2128": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [ { "lhs": { "type": "PlainIntegerConstant", "value": "1" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "name": "T49", "type": "PlainIntegerVariable" }, { "type": "PlainIntegerConstant", "value": "1" } ], "type": "PlainIntegerOperation", "operation": "-" }, "operation": "!=" }, { "lhs": { "type": "PlainIntegerConstant", "value": "2" }, "type": "PlainIntegerRelation", "rhs": { "name": "T36", "type": "PlainIntegerVariable" }, "operation": "<=" }, { "lhs": { "name": "T49", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "name": "T36", "type": "PlainIntegerVariable" }, "operation": "<=" } ] }, "ground": ["T49"], "free": ["X64"], "exprvars": [ "T36", "T49" ] } }, "696": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "2127": { "goal": [{ "clause": -1, "scope": -1, "term": "(= X64 (1))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [ { "lhs": { "type": "PlainIntegerConstant", "value": "1" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "name": "T49", "type": "PlainIntegerVariable" }, { "type": "PlainIntegerConstant", "value": "1" } ], "type": "PlainIntegerOperation", "operation": "-" }, "operation": "=" }, { "lhs": { "type": "PlainIntegerConstant", "value": "2" }, "type": "PlainIntegerRelation", "rhs": { "name": "T36", "type": "PlainIntegerVariable" }, "operation": "<=" }, { "lhs": { "name": "T49", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "name": "T36", "type": "PlainIntegerVariable" }, "operation": "<=" } ] }, "ground": ["T49"], "free": ["X64"], "exprvars": [ "T36", "T49" ] } }, "698": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [{ "lhs": { "type": "PlainIntegerConstant", "value": "0" }, "type": "PlainIntegerRelation", "rhs": { "name": "T15", "type": "PlainIntegerVariable" }, "operation": "=" }] }, "ground": [], "free": [], "exprvars": ["T15"] } }, "2023": { "goal": [{ "clause": 1, "scope": 2, "term": "(fact (- T36 (1)) X28)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [{ "lhs": { "type": "PlainIntegerConstant", "value": "2" }, "type": "PlainIntegerRelation", "rhs": { "name": "T36", "type": "PlainIntegerVariable" }, "operation": "<=" }] }, "ground": ["T36"], "free": ["X28"], "exprvars": ["T36"] } }, "2022": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "2021": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "2020": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [ { "lhs": { "type": "PlainIntegerConstant", "value": "0" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "name": "T44", "type": "PlainIntegerVariable" }, { "type": "PlainIntegerConstant", "value": "1" } ], "type": "PlainIntegerOperation", "operation": "-" }, "operation": "!=" }, { "lhs": { "type": "PlainIntegerConstant", "value": "2" }, "type": "PlainIntegerRelation", "rhs": { "name": "T36", "type": "PlainIntegerVariable" }, "operation": "<=" }, { "lhs": { "name": "T44", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "name": "T36", "type": "PlainIntegerVariable" }, "operation": "<=" } ] }, "ground": ["T44"], "free": ["X49"], "exprvars": [ "T36", "T44" ] } }, "1766": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "2019": { "goal": [{ "clause": -1, "scope": -1, "term": "(= X49 (1))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [ { "lhs": { "type": "PlainIntegerConstant", "value": "0" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "name": "T44", "type": "PlainIntegerVariable" }, { "type": "PlainIntegerConstant", "value": "1" } ], "type": "PlainIntegerOperation", "operation": "-" }, "operation": "=" }, { "lhs": { "type": "PlainIntegerConstant", "value": "2" }, "type": "PlainIntegerRelation", "rhs": { "name": "T36", "type": "PlainIntegerVariable" }, "operation": "<=" }, { "lhs": { "name": "T44", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "name": "T36", "type": "PlainIntegerVariable" }, "operation": "<=" } ] }, "ground": ["T44"], "free": ["X49"], "exprvars": [ "T36", "T44" ] } }, "1765": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (>= T36 (2)) (',' (fact (- T36 (1)) X28) (is T35 (* X28 T36))))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T35"], "free": ["X28"], "exprvars": [] } }, "702": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } } }, "edges": [ { "from": 1, "to": 6, "label": "CASE" }, { "from": 6, "to": 13, "label": "PARALLEL" }, { "from": 6, "to": 14, "label": "PARALLEL" }, { "from": 13, "to": 15, "label": "ONLY EVAL with clause\nfact(X9, X10) :- ','(is(0, X9), =(X10, 1)).\nand substitutionT1 -> T15,\nX9 -> T15,\nT2 -> T14,\nX10 -> T14,\nT13 -> T15" }, { "from": 14, "to": 710, "label": "PARALLEL" }, { "from": 14, "to": 711, "label": "PARALLEL" }, { "from": 15, "to": 16, "label": "IS ERROR" }, { "from": 15, "to": 693, "label": "\n" }, { "from": 15, "to": 694, "label": "IS FAIL" }, { "from": 693, "to": 696, "label": "UNIFY CASE with substitutionT14 -> 1" }, { "from": 693, "to": 698, "label": "UNIFY-BACKTRACK" }, { "from": 696, "to": 702, "label": "SUCCESS" }, { "from": 710, "to": 714, "label": "ONLY EVAL with clause\nfact(X19, X20) :- ','(is(1, X19), =(X20, 1)).\nand substitutionT1 -> T28,\nX19 -> T28,\nT2 -> T27,\nX20 -> T27,\nT26 -> T28" }, { "from": 711, "to": 1765, "label": "ONLY EVAL with clause\nfact(X26, X27) :- ','(>=(X26, 2), ','(fact(-(X26, 1), X28), is(X27, *(X28, X26)))).\nand substitutionT1 -> T36,\nX26 -> T36,\nT2 -> T35,\nX27 -> T35,\nT34 -> T36" }, { "from": 714, "to": 715, "label": "IS ERROR" }, { "from": 714, "to": 1732, "label": "\n" }, { "from": 714, "to": 1734, "label": "IS FAIL" }, { "from": 1732, "to": 1741, "label": "UNIFY CASE with substitutionT27 -> 1" }, { "from": 1732, "to": 1744, "label": "UNIFY-BACKTRACK" }, { "from": 1741, "to": 1747, "label": "SUCCESS" }, { "from": 1765, "to": 1766, "label": "IS ERROR" }, { "from": 1765, "to": 1894, "label": "ARITHCOMP SUCCESS" }, { "from": 1765, "to": 1895, "label": "ARITHCOMP FAIL" }, { "from": 1894, "to": 1896, "label": "SPLIT 1" }, { "from": 1894, "to": 1897, "label": "SPLIT 2\nnew knowledge:\nT36 is ground\nT38 is ground\nreplacements:X28 -> T38" }, { "from": 1896, "to": 1898, "label": "CASE" }, { "from": 1897, "to": 2161, "label": "IS ERROR" }, { "from": 1897, "to": 2162, "label": "\nT35 -> T57" }, { "from": 1897, "to": 2163, "label": "IS FAIL" }, { "from": 1898, "to": 1906, "label": "PARALLEL" }, { "from": 1898, "to": 1907, "label": "PARALLEL" }, { "from": 1906, "to": 1908, "label": "ONLY EVAL with clause\nfact(X47, X48) :- ','(is(0, X47), =(X48, 1)).\nand substitutionT36 -> T44,\nX47 -> -(T44, 1),\nX28 -> X49,\nX48 -> X49" }, { "from": 1907, "to": 2023, "label": "PARALLEL" }, { "from": 1907, "to": 2024, "label": "PARALLEL" }, { "from": 1908, "to": 2019, "label": "\n" }, { "from": 1908, "to": 2020, "label": "IS FAIL" }, { "from": 2019, "to": 2021, "label": "UNIFY SUCCESS with substitutionX49 -> 1" }, { "from": 2021, "to": 2022, "label": "SUCCESS" }, { "from": 2023, "to": 2025, "label": "ONLY EVAL with clause\nfact(X62, X63) :- ','(is(1, X62), =(X63, 1)).\nand substitutionT36 -> T49,\nX62 -> -(T49, 1),\nX28 -> X64,\nX63 -> X64" }, { "from": 2024, "to": 2131, "label": "ONLY EVAL with clause\nfact(X72, X73) :- ','(>=(X72, 2), ','(fact(-(X72, 1), X74), is(X73, *(X74, X72)))).\nand substitutionT36 -> T52,\nX72 -> -(T52, 1),\nX28 -> X75,\nX73 -> X75" }, { "from": 2025, "to": 2127, "label": "\n" }, { "from": 2025, "to": 2128, "label": "IS FAIL" }, { "from": 2127, "to": 2129, "label": "UNIFY SUCCESS with substitutionX64 -> 1" }, { "from": 2129, "to": 2130, "label": "SUCCESS" }, { "from": 2131, "to": 2147, "label": "ARITHCOMP SUCCESS" }, { "from": 2131, "to": 2148, "label": "ARITHCOMP FAIL" }, { "from": 2147, "to": 2149, "label": "SPLIT 1" }, { "from": 2147, "to": 2150, "label": "SPLIT 2\nnew knowledge:\nT52 is ground\nT54 is ground\nreplacements:X74 -> T54" }, { "from": 2149, "to": 1896, "label": "INSTANCE with matching:\nT36 -> -(T52, 1)\nX28 -> X74" }, { "from": 2150, "to": 2158, "label": "IS ERROR" }, { "from": 2150, "to": 2159, "label": "\nX75 -> T56" }, { "from": 2159, "to": 2160, "label": "SUCCESS" }, { "from": 2162, "to": 2164, "label": "SUCCESS" } ], "type": "Graph" } } ---------------------------------------- (2) Obligation: Rules: f2147_out(T52) -> f2131_out(T52) :|: T52 - 1 >= 2 f2148_out(x) -> f2131_out(x) :|: x - 1 < 2 f2131_in(x1) -> f2147_in(x1) :|: x1 - 1 >= 2 f2131_in(x2) -> f2148_in(x2) :|: x2 - 1 < 2 f1898_in(T36) -> f1906_in(T36) :|: TRUE f1907_out(x3) -> f1898_out(x3) :|: TRUE f1906_out(x4) -> f1898_out(x4) :|: TRUE f1898_in(x5) -> f1907_in(x5) :|: TRUE f2024_in(x6) -> f2131_in(x6) :|: TRUE f2131_out(x7) -> f2024_out(x7) :|: TRUE f2159_out(x8, x9, x10) -> f2150_out(x10, x8) :|: TRUE f2150_in(x11, x12) -> f2158_in :|: TRUE f2150_in(x13, x14) -> f2159_in(x14, x15, x13) :|: x15 = x13 * (x14 - 1) f2158_out -> f2150_out(x16, x17) :|: TRUE f2159_in(x18, x19, x20) -> f2159_out(x18, x19, x20) :|: TRUE f2024_out(x21) -> f1907_out(x21) :|: TRUE f2023_out(x22) -> f1907_out(x22) :|: TRUE f1907_in(x23) -> f2024_in(x23) :|: TRUE f1907_in(x24) -> f2023_in(x24) :|: TRUE f1896_out(x25 - 1) -> f2149_out(x25) :|: TRUE f2149_in(x26) -> f1896_in(x26 - 1) :|: TRUE f1896_in(x27) -> f1898_in(x27) :|: TRUE f1898_out(x28) -> f1896_out(x28) :|: TRUE f2150_out(x29, x30) -> f2147_out(x30) :|: TRUE f2147_in(x31) -> f2149_in(x31) :|: TRUE f2149_out(x32) -> f2150_in(x33, x32) :|: TRUE f1_in(T2) -> f6_in(T2) :|: TRUE f6_out(x34) -> f1_out(x34) :|: TRUE f13_out(x35) -> f6_out(x35) :|: TRUE f14_out(x36) -> f6_out(x36) :|: TRUE f6_in(x37) -> f14_in(x37) :|: TRUE f6_in(x38) -> f13_in(x38) :|: TRUE f710_out(x39) -> f14_out(x39) :|: TRUE f711_out(x40) -> f14_out(x40) :|: TRUE f14_in(x41) -> f710_in(x41) :|: TRUE f14_in(x42) -> f711_in(x42) :|: TRUE f1765_out(T35) -> f711_out(T35) :|: TRUE f711_in(x43) -> f1765_in(x43) :|: TRUE f1894_out(x44, x45) -> f1765_out(x45) :|: x44 >= 2 f1765_in(x46) -> f1895_in(x47, x46) :|: x47 < 2 f1895_out(x48, x49) -> f1765_out(x49) :|: x48 < 2 f1766_out -> f1765_out(x50) :|: TRUE f1765_in(x51) -> f1766_in :|: TRUE f1765_in(x52) -> f1894_in(x53, x52) :|: x53 >= 2 f1896_out(x54) -> f1897_in(x55, x56, x54) :|: TRUE f1894_in(x57, x58) -> f1896_in(x57) :|: TRUE f1897_out(x59, x60, x61) -> f1894_out(x61, x59) :|: TRUE Start term: f1_in(T2) ---------------------------------------- (3) IRSwTSimpleDependencyGraphProof (EQUIVALENT) Constructed simple dependency graph. Simplified to the following IRSwTs: intTRSProblem: f2131_in(x1) -> f2147_in(x1) :|: x1 - 1 >= 2 f1898_in(x5) -> f1907_in(x5) :|: TRUE f2024_in(x6) -> f2131_in(x6) :|: TRUE f1907_in(x23) -> f2024_in(x23) :|: TRUE f2149_in(x26) -> f1896_in(x26 - 1) :|: TRUE f1896_in(x27) -> f1898_in(x27) :|: TRUE f2147_in(x31) -> f2149_in(x31) :|: TRUE ---------------------------------------- (4) Obligation: Rules: f2131_in(x1) -> f2147_in(x1) :|: x1 - 1 >= 2 f1898_in(x5) -> f1907_in(x5) :|: TRUE f2024_in(x6) -> f2131_in(x6) :|: TRUE f1907_in(x23) -> f2024_in(x23) :|: TRUE f2149_in(x26) -> f1896_in(x26 - 1) :|: TRUE f1896_in(x27) -> f1898_in(x27) :|: TRUE f2147_in(x31) -> f2149_in(x31) :|: TRUE ---------------------------------------- (5) IntTRSCompressionProof (EQUIVALENT) Compressed rules. ---------------------------------------- (6) Obligation: Rules: f2149_in(x26:0) -> f2149_in(x26:0 - 1) :|: x26:0 > 3 ---------------------------------------- (7) IRSFormatTransformerProof (EQUIVALENT) Reformatted IRS to match normalized format (transformed away non-linear left-hand sides, !=, / and %). ---------------------------------------- (8) Obligation: Rules: f2149_in(x26:0) -> f2149_in(arith) :|: x26:0 > 3 && arith = x26:0 - 1 ---------------------------------------- (9) IRSwTTerminationDigraphProof (EQUIVALENT) Constructed termination digraph! Nodes: (1) f2149_in(x26:0) -> f2149_in(arith) :|: x26:0 > 3 && arith = x26:0 - 1 Arcs: (1) -> (1) This digraph is fully evaluated! ---------------------------------------- (10) Obligation: Termination digraph: Nodes: (1) f2149_in(x26:0) -> f2149_in(arith) :|: x26:0 > 3 && arith = x26:0 - 1 Arcs: (1) -> (1) This digraph is fully evaluated! ---------------------------------------- (11) IntTRSCompressionProof (EQUIVALENT) Compressed rules. ---------------------------------------- (12) Obligation: Rules: f2149_in(x26:0:0) -> f2149_in(x26:0:0 - 1) :|: x26:0:0 > 3 ---------------------------------------- (13) TempFilterProof (SOUND) Used the following sort dictionary for filtering: f2149_in(INTEGER) Replaced non-predefined constructor symbols by 0. ---------------------------------------- (14) Obligation: Rules: f2149_in(x26:0:0) -> f2149_in(c) :|: c = x26:0:0 - 1 && x26:0:0 > 3 ---------------------------------------- (15) RankingReductionPairProof (EQUIVALENT) Interpretation: [ f2149_in ] = f2149_in_1 The following rules are decreasing: f2149_in(x26:0:0) -> f2149_in(c) :|: c = x26:0:0 - 1 && x26:0:0 > 3 The following rules are bounded: f2149_in(x26:0:0) -> f2149_in(c) :|: c = x26:0:0 - 1 && x26:0:0 > 3 ---------------------------------------- (16) YES