/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 fact(a,g) w.r.t. the given Prolog program could successfully be proven: (0) Prolog (1) PrologToIRSwTTransformerProof [SOUND, 38 ms] (2) IRSwT (3) IRSwTSimpleDependencyGraphProof [EQUIVALENT, 0 ms] (4) IRSwT (5) IntTRSCompressionProof [EQUIVALENT, 16 ms] (6) IRSwT (7) IRSFormatTransformerProof [EQUIVALENT, 0 ms] (8) IRSwT (9) IRSwTTerminationDigraphProof [EQUIVALENT, 23 ms] (10) IRSwT (11) IntTRSCompressionProof [EQUIVALENT, 0 ms] (12) IRSwT (13) TempFilterProof [SOUND, 44 ms] (14) IntTRS (15) PolynomialOrderProcessor [EQUIVALENT, 10 ms] (16) YES ---------------------------------------- (0) Obligation: Clauses: fact(X, Y) :- ','(=<(0, X), ','(=<(X, 1), =(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)", "(',' (=< (0) X) (',' (=< X (1)) (= Y (1))))" ], [ "(fact X Y)", "(',' (>= X (2)) (',' (fact (- X (1)) Y1) (is Y (* Y1 X))))" ] ] }, "graph": { "nodes": { "1919": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "2474": { "goal": [{ "clause": 0, "scope": 2, "term": "(fact (- T23 (1)) X18)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [{ "lhs": { "type": "PlainIntegerConstant", "value": "2" }, "type": "PlainIntegerRelation", "rhs": { "name": "T23", "type": "PlainIntegerVariable" }, "operation": "<=" }] }, "ground": ["T23"], "free": ["X18"], "exprvars": ["T23"] } }, "2870": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [{ "lhs": { "name": "T39", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "name": "T25", "type": "PlainIntegerVariable" }, { "name": "T23", "type": "PlainIntegerVariable" } ], "type": "PlainIntegerOperation", "operation": "*" }, "operation": "=" }] }, "ground": [], "free": [], "exprvars": [ "T25", "T23", "T39" ] } }, "2472": { "goal": [ { "clause": 0, "scope": 2, "term": "(fact (- T23 (1)) X18)" }, { "clause": 1, "scope": 2, "term": "(fact (- T23 (1)) X18)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [{ "lhs": { "type": "PlainIntegerConstant", "value": "2" }, "type": "PlainIntegerRelation", "rhs": { "name": "T23", "type": "PlainIntegerVariable" }, "operation": "<=" }] }, "ground": ["T23"], "free": ["X18"], "exprvars": ["T23"] } }, "type": "Nodes", "2470": { "goal": [{ "clause": -1, "scope": -1, "term": "(is T22 (* T25 T23))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T23", "T22", "T25" ], "free": [], "exprvars": [] } }, "2427": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (fact (- T23 (1)) X18) (is T22 (* X18 T23)))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [{ "lhs": { "type": "PlainIntegerConstant", "value": "2" }, "type": "PlainIntegerRelation", "rhs": { "name": "T23", "type": "PlainIntegerVariable" }, "operation": "<=" }] }, "ground": [ "T23", "T22" ], "free": ["X18"], "exprvars": ["T23"] } }, "2867": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "2866": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [{ "lhs": { "name": "T38", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "name": "T36", "type": "PlainIntegerVariable" }, { "arguments": [ { "name": "T34", "type": "PlainIntegerVariable" }, { "type": "PlainIntegerConstant", "value": "1" } ], "type": "PlainIntegerOperation", "operation": "-" } ], "type": "PlainIntegerOperation", "operation": "*" }, "operation": "=" }] }, "ground": [], "free": [], "exprvars": [ "T36", "T34", "T38" ] } }, "2469": { "goal": [{ "clause": -1, "scope": -1, "term": "(fact (- T23 (1)) X18)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [{ "lhs": { "type": "PlainIntegerConstant", "value": "2" }, "type": "PlainIntegerRelation", "rhs": { "name": "T23", "type": "PlainIntegerVariable" }, "operation": "<=" }] }, "ground": ["T23"], "free": ["X18"], "exprvars": ["T23"] } }, "2865": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [{ "lhs": { "name": "T38", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "name": "T36", "type": "PlainIntegerVariable" }, { "arguments": [ { "name": "T34", "type": "PlainIntegerVariable" }, { "type": "PlainIntegerConstant", "value": "1" } ], "type": "PlainIntegerOperation", "operation": "-" } ], "type": "PlainIntegerOperation", "operation": "*" }, "operation": "=" }] }, "ground": [ "T36", "T34", "T38" ], "free": ["X50"], "exprvars": [ "T36", "T34", "T38" ] } }, "2864": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "851": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (=< T15 (1)) (= 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"] } }, "2841": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (>= (- T34 (1)) (2)) (',' (fact (- (- T34 (1)) (1)) X49) (is X50 (* X49 (- T34 (1))))))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [ { "lhs": { "type": "PlainIntegerConstant", "value": "2" }, "type": "PlainIntegerRelation", "rhs": { "name": "T23", "type": "PlainIntegerVariable" }, "operation": "<=" }, { "lhs": { "name": "T34", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "name": "T23", "type": "PlainIntegerVariable" }, "operation": "<=" } ] }, "ground": ["T34"], "free": [ "X50", "X49" ], "exprvars": [ "T23", "T34" ] } }, "852": { "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"] } }, "1918": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [ { "lhs": { "type": "PlainIntegerConstant", "value": "0" }, "type": "PlainIntegerRelation", "rhs": { "name": "T15", "type": "PlainIntegerVariable" }, "operation": "<=" }, { "lhs": { "name": "T15", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "type": "PlainIntegerConstant", "value": "1" }, "operation": "<=" } ] }, "ground": [], "free": [], "exprvars": ["T15"] } }, "1917": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "1916": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [ { "lhs": { "name": "T15", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "type": "PlainIntegerConstant", "value": "1" }, "operation": ">" }, { "lhs": { "type": "PlainIntegerConstant", "value": "0" }, "type": "PlainIntegerRelation", "rhs": { "name": "T15", "type": "PlainIntegerVariable" }, "operation": "<=" } ] }, "ground": [ "T14", "T15" ], "free": [], "exprvars": ["T15"] } }, "1915": { "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": "<=" }, { "lhs": { "name": "T15", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "type": "PlainIntegerConstant", "value": "1" }, "operation": "<=" } ] }, "ground": [ "T14", "T15" ], "free": [], "exprvars": ["T15"] } }, "2869": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T25", "T23", "T22" ], "free": [], "exprvars": [ "T25", "T23" ] } }, "2428": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [{ "lhs": { "type": "PlainIntegerConstant", "value": "2" }, "type": "PlainIntegerRelation", "rhs": { "name": "T23", "type": "PlainIntegerVariable" }, "operation": ">" }] }, "ground": [ "T23", "T22" ], "free": ["X18"], "exprvars": ["T23"] } }, "2868": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [{ "lhs": { "name": "T39", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "name": "T25", "type": "PlainIntegerVariable" }, { "name": "T23", "type": "PlainIntegerVariable" } ], "type": "PlainIntegerOperation", "operation": "*" }, "operation": "=" }] }, "ground": [ "T25", "T23", "T39", "T22" ], "free": [], "exprvars": [ "T25", "T23", "T39" ] } }, "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)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T2"], "free": [], "exprvars": [] } }, "15": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (=< (0) T15) (',' (=< T15 (1)) (= 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": [] } }, "1921": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "2856": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [ { "lhs": { "type": "PlainIntegerConstant", "value": "2" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "name": "T34", "type": "PlainIntegerVariable" }, { "type": "PlainIntegerConstant", "value": "1" } ], "type": "PlainIntegerOperation", "operation": "-" }, "operation": ">" }, { "lhs": { "type": "PlainIntegerConstant", "value": "2" }, "type": "PlainIntegerRelation", "rhs": { "name": "T23", "type": "PlainIntegerVariable" }, "operation": "<=" }, { "lhs": { "name": "T34", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "name": "T23", "type": "PlainIntegerVariable" }, "operation": "<=" } ] }, "ground": ["T34"], "free": [ "X50", "X49" ], "exprvars": [ "T23", "T34" ] } }, "1": { "goal": [{ "clause": -1, "scope": -1, "term": "(fact T1 T2)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T2"], "free": [], "exprvars": [] } }, "1920": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (>= T23 (2)) (',' (fact (- T23 (1)) X18) (is T22 (* X18 T23))))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T22"], "free": ["X18"], "exprvars": [] } }, "2855": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (fact (- (- T34 (1)) (1)) X49) (is X50 (* X49 (- T34 (1)))))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [ { "lhs": { "type": "PlainIntegerConstant", "value": "2" }, "type": "PlainIntegerRelation", "rhs": { "name": "T23", "type": "PlainIntegerVariable" }, "operation": "<=" }, { "lhs": { "name": "T34", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "name": "T23", "type": "PlainIntegerVariable" }, "operation": "<=" }, { "lhs": { "type": "PlainIntegerConstant", "value": "2" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "name": "T34", "type": "PlainIntegerVariable" }, { "type": "PlainIntegerConstant", "value": "1" } ], "type": "PlainIntegerOperation", "operation": "-" }, "operation": "<=" } ] }, "ground": ["T34"], "free": [ "X50", "X49" ], "exprvars": [ "T23", "T34" ] } }, "2511": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [ { "lhs": { "type": "PlainIntegerConstant", "value": "0" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "name": "T31", "type": "PlainIntegerVariable" }, { "type": "PlainIntegerConstant", "value": "1" } ], "type": "PlainIntegerOperation", "operation": "-" }, "operation": ">" }, { "lhs": { "type": "PlainIntegerConstant", "value": "2" }, "type": "PlainIntegerRelation", "rhs": { "name": "T23", "type": "PlainIntegerVariable" }, "operation": "<=" }, { "lhs": { "name": "T31", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "name": "T23", "type": "PlainIntegerVariable" }, "operation": "<=" } ] }, "ground": ["T31"], "free": ["X39"], "exprvars": [ "T31", "T23" ] } }, "5": { "goal": [ { "clause": 0, "scope": 1, "term": "(fact T1 T2)" }, { "clause": 1, "scope": 1, "term": "(fact T1 T2)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T2"], "free": [], "exprvars": [] } }, "2510": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (=< (- T31 (1)) (1)) (= X39 (1)))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [ { "lhs": { "type": "PlainIntegerConstant", "value": "2" }, "type": "PlainIntegerRelation", "rhs": { "name": "T23", "type": "PlainIntegerVariable" }, "operation": "<=" }, { "lhs": { "name": "T31", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "name": "T23", "type": "PlainIntegerVariable" }, "operation": "<=" }, { "lhs": { "type": "PlainIntegerConstant", "value": "0" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "name": "T31", "type": "PlainIntegerVariable" }, { "type": "PlainIntegerConstant", "value": "1" } ], "type": "PlainIntegerOperation", "operation": "-" }, "operation": "<=" } ] }, "ground": ["T31"], "free": ["X39"], "exprvars": [ "T31", "T23" ] } }, "2476": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (=< (0) (- T31 (1))) (',' (=< (- T31 (1)) (1)) (= X39 (1))))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [ { "lhs": { "type": "PlainIntegerConstant", "value": "2" }, "type": "PlainIntegerRelation", "rhs": { "name": "T23", "type": "PlainIntegerVariable" }, "operation": "<=" }, { "lhs": { "name": "T31", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "name": "T23", "type": "PlainIntegerVariable" }, "operation": "<=" } ] }, "ground": ["T31"], "free": ["X39"], "exprvars": [ "T31", "T23" ] } }, "2475": { "goal": [{ "clause": 1, "scope": 2, "term": "(fact (- T23 (1)) X18)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [{ "lhs": { "type": "PlainIntegerConstant", "value": "2" }, "type": "PlainIntegerRelation", "rhs": { "name": "T23", "type": "PlainIntegerVariable" }, "operation": "<=" }] }, "ground": ["T23"], "free": ["X18"], "exprvars": ["T23"] } }, "2839": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "2838": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "2837": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [ { "lhs": { "arguments": [ { "name": "T31", "type": "PlainIntegerVariable" }, { "type": "PlainIntegerConstant", "value": "1" } ], "type": "PlainIntegerOperation", "operation": "-" }, "type": "PlainIntegerRelation", "rhs": { "type": "PlainIntegerConstant", "value": "1" }, "operation": ">" }, { "lhs": { "type": "PlainIntegerConstant", "value": "2" }, "type": "PlainIntegerRelation", "rhs": { "name": "T23", "type": "PlainIntegerVariable" }, "operation": "<=" }, { "lhs": { "name": "T31", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "name": "T23", "type": "PlainIntegerVariable" }, "operation": "<=" }, { "lhs": { "type": "PlainIntegerConstant", "value": "0" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "name": "T31", "type": "PlainIntegerVariable" }, { "type": "PlainIntegerConstant", "value": "1" } ], "type": "PlainIntegerOperation", "operation": "-" }, "operation": "<=" } ] }, "ground": ["T31"], "free": ["X39"], "exprvars": [ "T31", "T23" ] } }, "2836": { "goal": [{ "clause": -1, "scope": -1, "term": "(= X39 (1))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [ { "lhs": { "type": "PlainIntegerConstant", "value": "2" }, "type": "PlainIntegerRelation", "rhs": { "name": "T23", "type": "PlainIntegerVariable" }, "operation": "<=" }, { "lhs": { "name": "T31", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "name": "T23", "type": "PlainIntegerVariable" }, "operation": "<=" }, { "lhs": { "type": "PlainIntegerConstant", "value": "0" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "name": "T31", "type": "PlainIntegerVariable" }, { "type": "PlainIntegerConstant", "value": "1" } ], "type": "PlainIntegerOperation", "operation": "-" }, "operation": "<=" }, { "lhs": { "arguments": [ { "name": "T31", "type": "PlainIntegerVariable" }, { "type": "PlainIntegerConstant", "value": "1" } ], "type": "PlainIntegerOperation", "operation": "-" }, "type": "PlainIntegerRelation", "rhs": { "type": "PlainIntegerConstant", "value": "1" }, "operation": "<=" } ] }, "ground": ["T31"], "free": ["X39"], "exprvars": [ "T31", "T23" ] } }, "2858": { "goal": [{ "clause": -1, "scope": -1, "term": "(is X50 (* T36 (- T34 (1))))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T34", "T36" ], "free": ["X50"], "exprvars": [] } }, "2857": { "goal": [{ "clause": -1, "scope": -1, "term": "(fact (- (- T34 (1)) (1)) X49)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [ { "lhs": { "type": "PlainIntegerConstant", "value": "2" }, "type": "PlainIntegerRelation", "rhs": { "name": "T23", "type": "PlainIntegerVariable" }, "operation": "<=" }, { "lhs": { "name": "T34", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "name": "T23", "type": "PlainIntegerVariable" }, "operation": "<=" }, { "lhs": { "type": "PlainIntegerConstant", "value": "2" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "name": "T34", "type": "PlainIntegerVariable" }, { "type": "PlainIntegerConstant", "value": "1" } ], "type": "PlainIntegerOperation", "operation": "-" }, "operation": "<=" } ] }, "ground": ["T34"], "free": ["X49"], "exprvars": [ "T23", "T34" ] } } }, "edges": [ { "from": 1, "to": 5, "label": "CASE" }, { "from": 5, "to": 13, "label": "PARALLEL" }, { "from": 5, "to": 14, "label": "PARALLEL" }, { "from": 13, "to": 15, "label": "ONLY EVAL with clause\nfact(X9, X10) :- ','(=<(0, X9), ','(=<(X9, 1), =(X10, 1))).\nand substitutionT1 -> T15,\nX9 -> T15,\nT2 -> T14,\nX10 -> T14,\nT13 -> T15" }, { "from": 14, "to": 1920, "label": "ONLY EVAL with clause\nfact(X16, X17) :- ','(>=(X16, 2), ','(fact(-(X16, 1), X18), is(X17, *(X18, X16)))).\nand substitutionT1 -> T23,\nX16 -> T23,\nT2 -> T22,\nX17 -> T22,\nT21 -> T23" }, { "from": 15, "to": 16, "label": "IS ERROR" }, { "from": 15, "to": 851, "label": "ARITHCOMP SUCCESS" }, { "from": 15, "to": 852, "label": "ARITHCOMP FAIL" }, { "from": 851, "to": 1915, "label": "ARITHCOMP SUCCESS" }, { "from": 851, "to": 1916, "label": "ARITHCOMP FAIL" }, { "from": 1915, "to": 1917, "label": "UNIFY CASE with substitutionT14 -> 1" }, { "from": 1915, "to": 1918, "label": "UNIFY-BACKTRACK" }, { "from": 1917, "to": 1919, "label": "SUCCESS" }, { "from": 1920, "to": 1921, "label": "IS ERROR" }, { "from": 1920, "to": 2427, "label": "ARITHCOMP SUCCESS" }, { "from": 1920, "to": 2428, "label": "ARITHCOMP FAIL" }, { "from": 2427, "to": 2469, "label": "SPLIT 1" }, { "from": 2427, "to": 2470, "label": "SPLIT 2\nnew knowledge:\nT23 is ground\nT25 is ground\nreplacements:X18 -> T25" }, { "from": 2469, "to": 2472, "label": "CASE" }, { "from": 2470, "to": 2867, "label": "IS ERROR" }, { "from": 2470, "to": 2868, "label": "\nT22 -> T39" }, { "from": 2470, "to": 2869, "label": "IS FAIL" }, { "from": 2472, "to": 2474, "label": "PARALLEL" }, { "from": 2472, "to": 2475, "label": "PARALLEL" }, { "from": 2474, "to": 2476, "label": "ONLY EVAL with clause\nfact(X37, X38) :- ','(=<(0, X37), ','(=<(X37, 1), =(X38, 1))).\nand substitutionT23 -> T31,\nX37 -> -(T31, 1),\nX18 -> X39,\nX38 -> X39" }, { "from": 2475, "to": 2841, "label": "ONLY EVAL with clause\nfact(X47, X48) :- ','(>=(X47, 2), ','(fact(-(X47, 1), X49), is(X48, *(X49, X47)))).\nand substitutionT23 -> T34,\nX47 -> -(T34, 1),\nX18 -> X50,\nX48 -> X50" }, { "from": 2476, "to": 2510, "label": "ARITHCOMP SUCCESS" }, { "from": 2476, "to": 2511, "label": "ARITHCOMP FAIL" }, { "from": 2510, "to": 2836, "label": "ARITHCOMP SUCCESS" }, { "from": 2510, "to": 2837, "label": "ARITHCOMP FAIL" }, { "from": 2836, "to": 2838, "label": "UNIFY SUCCESS with substitutionX39 -> 1" }, { "from": 2838, "to": 2839, "label": "SUCCESS" }, { "from": 2841, "to": 2855, "label": "ARITHCOMP SUCCESS" }, { "from": 2841, "to": 2856, "label": "ARITHCOMP FAIL" }, { "from": 2855, "to": 2857, "label": "SPLIT 1" }, { "from": 2855, "to": 2858, "label": "SPLIT 2\nnew knowledge:\nT34 is ground\nT36 is ground\nreplacements:X49 -> T36" }, { "from": 2857, "to": 2469, "label": "INSTANCE with matching:\nT23 -> -(T34, 1)\nX18 -> X49" }, { "from": 2858, "to": 2864, "label": "IS ERROR" }, { "from": 2858, "to": 2865, "label": "\nX50 -> T38" }, { "from": 2865, "to": 2866, "label": "SUCCESS" }, { "from": 2868, "to": 2870, "label": "SUCCESS" } ], "type": "Graph" } } ---------------------------------------- (2) Obligation: Rules: f2858_out(T36, T34) -> f2855_out(T34) :|: TRUE f2857_out(x) -> f2858_in(x1, x) :|: TRUE f2855_in(x2) -> f2857_in(x2) :|: TRUE f2857_in(x3) -> f2469_in(x3 - 1) :|: TRUE f2469_out(x4 - 1) -> f2857_out(x4) :|: TRUE f2858_in(x5, x6) -> f2865_in(x5, x6, x7) :|: x7 = x5 * (x6 - 1) f2858_in(x8, x9) -> f2864_in :|: TRUE f2864_out -> f2858_out(x10, x11) :|: TRUE f2865_out(x12, x13, x14) -> f2858_out(x12, x13) :|: TRUE f2474_out(T23) -> f2472_out(T23) :|: TRUE f2472_in(x15) -> f2474_in(x15) :|: TRUE f2472_in(x16) -> f2475_in(x16) :|: TRUE f2475_out(x17) -> f2472_out(x17) :|: TRUE f2472_out(x18) -> f2469_out(x18) :|: TRUE f2469_in(x19) -> f2472_in(x19) :|: TRUE f2865_in(x20, x21, x22) -> f2865_out(x20, x21, x22) :|: TRUE f2841_in(x23) -> f2855_in(x23) :|: x23 - 1 >= 2 f2855_out(x24) -> f2841_out(x24) :|: x24 - 1 >= 2 f2856_out(x25) -> f2841_out(x25) :|: x25 - 1 < 2 f2841_in(x26) -> f2856_in(x26) :|: x26 - 1 < 2 f2475_in(x27) -> f2841_in(x27) :|: TRUE f2841_out(x28) -> f2475_out(x28) :|: TRUE f1_in(T2) -> f5_in(T2) :|: TRUE f5_out(x29) -> f1_out(x29) :|: TRUE f13_out(x30) -> f5_out(x30) :|: TRUE f5_in(x31) -> f13_in(x31) :|: TRUE f14_out(x32) -> f5_out(x32) :|: TRUE f5_in(x33) -> f14_in(x33) :|: TRUE f14_in(T22) -> f1920_in(T22) :|: TRUE f1920_out(x34) -> f14_out(x34) :|: TRUE f1920_in(x35) -> f2427_in(x36, x35) :|: x36 >= 2 f1920_in(x37) -> f1921_in :|: TRUE f2427_out(x38, x39) -> f1920_out(x39) :|: x38 >= 2 f2428_out(x40, x41) -> f1920_out(x41) :|: x40 < 2 f1921_out -> f1920_out(x42) :|: TRUE f1920_in(x43) -> f2428_in(x44, x43) :|: x44 < 2 f2427_in(x45, x46) -> f2469_in(x45) :|: TRUE f2469_out(x47) -> f2470_in(x48, x49, x47) :|: TRUE f2470_out(x50, x51, x52) -> f2427_out(x52, x50) :|: TRUE Start term: f1_in(T2) ---------------------------------------- (3) IRSwTSimpleDependencyGraphProof (EQUIVALENT) Constructed simple dependency graph. Simplified to the following IRSwTs: intTRSProblem: f2855_in(x2) -> f2857_in(x2) :|: TRUE f2857_in(x3) -> f2469_in(x3 - 1) :|: TRUE f2472_in(x16) -> f2475_in(x16) :|: TRUE f2469_in(x19) -> f2472_in(x19) :|: TRUE f2841_in(x23) -> f2855_in(x23) :|: x23 - 1 >= 2 f2475_in(x27) -> f2841_in(x27) :|: TRUE ---------------------------------------- (4) Obligation: Rules: f2855_in(x2) -> f2857_in(x2) :|: TRUE f2857_in(x3) -> f2469_in(x3 - 1) :|: TRUE f2472_in(x16) -> f2475_in(x16) :|: TRUE f2469_in(x19) -> f2472_in(x19) :|: TRUE f2841_in(x23) -> f2855_in(x23) :|: x23 - 1 >= 2 f2475_in(x27) -> f2841_in(x27) :|: TRUE ---------------------------------------- (5) IntTRSCompressionProof (EQUIVALENT) Compressed rules. ---------------------------------------- (6) Obligation: Rules: f2841_in(x23:0) -> f2841_in(x23:0 - 1) :|: x23:0 > 2 ---------------------------------------- (7) IRSFormatTransformerProof (EQUIVALENT) Reformatted IRS to match normalized format (transformed away non-linear left-hand sides, !=, / and %). ---------------------------------------- (8) Obligation: Rules: f2841_in(x23:0) -> f2841_in(arith) :|: x23:0 > 2 && arith = x23:0 - 1 ---------------------------------------- (9) IRSwTTerminationDigraphProof (EQUIVALENT) Constructed termination digraph! Nodes: (1) f2841_in(x23:0) -> f2841_in(arith) :|: x23:0 > 2 && arith = x23:0 - 1 Arcs: (1) -> (1) This digraph is fully evaluated! ---------------------------------------- (10) Obligation: Termination digraph: Nodes: (1) f2841_in(x23:0) -> f2841_in(arith) :|: x23:0 > 2 && arith = x23:0 - 1 Arcs: (1) -> (1) This digraph is fully evaluated! ---------------------------------------- (11) IntTRSCompressionProof (EQUIVALENT) Compressed rules. ---------------------------------------- (12) Obligation: Rules: f2841_in(x23:0:0) -> f2841_in(x23:0:0 - 1) :|: x23:0:0 > 2 ---------------------------------------- (13) TempFilterProof (SOUND) Used the following sort dictionary for filtering: f2841_in(INTEGER) Replaced non-predefined constructor symbols by 0. ---------------------------------------- (14) Obligation: Rules: f2841_in(x23:0:0) -> f2841_in(c) :|: c = x23:0:0 - 1 && x23:0:0 > 2 ---------------------------------------- (15) PolynomialOrderProcessor (EQUIVALENT) Found the following polynomial interpretation: [f2841_in(x)] = x The following rules are decreasing: f2841_in(x23:0:0) -> f2841_in(c) :|: c = x23:0:0 - 1 && x23:0:0 > 2 The following rules are bounded: f2841_in(x23:0:0) -> f2841_in(c) :|: c = x23:0:0 - 1 && x23:0:0 > 2 ---------------------------------------- (16) YES