/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 factorial(g,a) w.r.t. the given Prolog program could successfully be proven: (0) Prolog (1) PrologToIRSwTTransformerProof [SOUND, 53 ms] (2) IRSwT (3) IRSwTSimpleDependencyGraphProof [EQUIVALENT, 0 ms] (4) IRSwT (5) IntTRSCompressionProof [EQUIVALENT, 8 ms] (6) IRSwT (7) IRSFormatTransformerProof [EQUIVALENT, 0 ms] (8) IRSwT (9) IRSwTTerminationDigraphProof [EQUIVALENT, 35 ms] (10) IRSwT (11) IntTRSCompressionProof [EQUIVALENT, 0 ms] (12) IRSwT (13) IntTRSUnneededArgumentFilterProof [EQUIVALENT, 0 ms] (14) IRSwT (15) TempFilterProof [SOUND, 41 ms] (16) IntTRS (17) PolynomialOrderProcessor [EQUIVALENT, 0 ms] (18) YES ---------------------------------------- (0) Obligation: Clauses: factorial(N, F) :- factorial(0, N, 1, F). factorial(I, N, T, F) :- ','(<(I, N), ','(is(I1, +(I, 1)), ','(is(T1, *(T, I1)), factorial(I1, N, T1, F)))). factorial(N, N, F, F). Query: factorial(g,a) ---------------------------------------- (1) PrologToIRSwTTransformerProof (SOUND) Transformed Prolog program to IRSwT according to method in Master Thesis of A. Weinert { "root": 1, "program": { "directives": [], "clauses": [ [ "(factorial N F)", "(factorial (0) N (1) F)" ], [ "(factorial I N T F)", "(',' (< I N) (',' (is I1 (+ I (1))) (',' (is T1 (* T I1)) (factorial I1 N T1 F))))" ], [ "(factorial N N F F)", null ] ] }, "graph": { "nodes": { "22": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (< (0) T26) (',' (is X43 (+ (0) (1))) (',' (is X44 (* (1) X43)) (factorial X43 T26 X44 T28))))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T26"], "free": [ "X43", "X44" ], "exprvars": [] } }, "24": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "2034": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (is X76 (* T55 T58)) (factorial T58 T54 X76 T57))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [ { "lhs": { "name": "T29", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "type": "PlainIntegerConstant", "value": "0" }, { "type": "PlainIntegerConstant", "value": "1" } ], "type": "PlainIntegerOperation", "operation": "+" }, "operation": "=" }, { "lhs": { "name": "T30", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "type": "PlainIntegerConstant", "value": "1" }, { "name": "T29", "type": "PlainIntegerVariable" } ], "type": "PlainIntegerOperation", "operation": "*" }, "operation": "=" }, { "lhs": { "arguments": [ { "type": "PlainIntegerConstant", "value": "0" }, { "type": "PlainIntegerConstant", "value": "1" } ], "type": "PlainIntegerOperation", "operation": "+" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "type": "PlainIntegerConstant", "value": "0" }, { "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": "T29", "type": "PlainIntegerVariable" } ], "type": "PlainIntegerOperation", "operation": "*" }, "operation": "=" }, { "lhs": { "name": "T58", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "name": "T53", "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": "T54", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "name": "T26", "type": "PlainIntegerVariable" }, "operation": "<" }, { "lhs": { "name": "T53", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "name": "T54", "type": "PlainIntegerVariable" }, "operation": "<" } ] }, "ground": [ "T53", "T58", "T55", "T54" ], "free": [ "X75", "X76" ], "exprvars": [ "T53", "T58", "T30", "T29", "T55", "T54", "T26" ] } }, "2210": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [ { "lhs": { "name": "T29", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "type": "PlainIntegerConstant", "value": "0" }, { "type": "PlainIntegerConstant", "value": "1" } ], "type": "PlainIntegerOperation", "operation": "+" }, "operation": "=" }, { "lhs": { "name": "T30", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "type": "PlainIntegerConstant", "value": "1" }, { "name": "T29", "type": "PlainIntegerVariable" } ], "type": "PlainIntegerOperation", "operation": "*" }, "operation": "=" }, { "lhs": { "type": "PlainIntegerConstant", "value": "0" }, "type": "PlainIntegerRelation", "rhs": { "name": "T26", "type": "PlainIntegerVariable" }, "operation": "<" } ] }, "ground": [], "free": [], "exprvars": [ "T30", "T29", "T26" ] } }, "2033": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [ { "lhs": { "name": "T29", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "type": "PlainIntegerConstant", "value": "0" }, { "type": "PlainIntegerConstant", "value": "1" } ], "type": "PlainIntegerOperation", "operation": "+" }, "operation": "=" }, { "lhs": { "name": "T30", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "type": "PlainIntegerConstant", "value": "1" }, { "name": "T29", "type": "PlainIntegerVariable" } ], "type": "PlainIntegerOperation", "operation": "*" }, "operation": "=" }, { "lhs": { "arguments": [ { "type": "PlainIntegerConstant", "value": "0" }, { "type": "PlainIntegerConstant", "value": "1" } ], "type": "PlainIntegerOperation", "operation": "+" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "type": "PlainIntegerConstant", "value": "0" }, { "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": "T29", "type": "PlainIntegerVariable" } ], "type": "PlainIntegerOperation", "operation": "*" }, "operation": "=" }, { "lhs": { "type": "PlainIntegerConstant", "value": "0" }, "type": "PlainIntegerRelation", "rhs": { "name": "T26", "type": "PlainIntegerVariable" }, "operation": "<" }, { "lhs": { "name": "T54", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "name": "T26", "type": "PlainIntegerVariable" }, "operation": "<" }, { "lhs": { "name": "T53", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "name": "T54", "type": "PlainIntegerVariable" }, "operation": ">=" } ] }, "ground": [ "T53", "T55", "T54" ], "free": [ "X75", "X76" ], "exprvars": [ "T53", "T30", "T29", "T55", "T54", "T26" ] } }, "2032": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (is X75 (+ T53 (1))) (',' (is X76 (* T55 X75)) (factorial X75 T54 X76 T57)))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [ { "lhs": { "name": "T29", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "type": "PlainIntegerConstant", "value": "0" }, { "type": "PlainIntegerConstant", "value": "1" } ], "type": "PlainIntegerOperation", "operation": "+" }, "operation": "=" }, { "lhs": { "name": "T30", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "type": "PlainIntegerConstant", "value": "1" }, { "name": "T29", "type": "PlainIntegerVariable" } ], "type": "PlainIntegerOperation", "operation": "*" }, "operation": "=" }, { "lhs": { "arguments": [ { "type": "PlainIntegerConstant", "value": "0" }, { "type": "PlainIntegerConstant", "value": "1" } ], "type": "PlainIntegerOperation", "operation": "+" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "type": "PlainIntegerConstant", "value": "0" }, { "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": "T29", "type": "PlainIntegerVariable" } ], "type": "PlainIntegerOperation", "operation": "*" }, "operation": "=" }, { "lhs": { "type": "PlainIntegerConstant", "value": "0" }, "type": "PlainIntegerRelation", "rhs": { "name": "T26", "type": "PlainIntegerVariable" }, "operation": "<" }, { "lhs": { "name": "T54", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "name": "T26", "type": "PlainIntegerVariable" }, "operation": "<" }, { "lhs": { "name": "T53", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "name": "T54", "type": "PlainIntegerVariable" }, "operation": "<" } ] }, "ground": [ "T53", "T55", "T54" ], "free": [ "X75", "X76" ], "exprvars": [ "T53", "T30", "T29", "T55", "T54", "T26" ] } }, "type": "Nodes", "1335": { "goal": [{ "clause": 1, "scope": 3, "term": "(factorial T29 T26 T30 T28)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [ { "lhs": { "name": "T29", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "type": "PlainIntegerConstant", "value": "0" }, { "type": "PlainIntegerConstant", "value": "1" } ], "type": "PlainIntegerOperation", "operation": "+" }, "operation": "=" }, { "lhs": { "name": "T30", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "type": "PlainIntegerConstant", "value": "1" }, { "name": "T29", "type": "PlainIntegerVariable" } ], "type": "PlainIntegerOperation", "operation": "*" }, "operation": "=" }, { "lhs": { "type": "PlainIntegerConstant", "value": "0" }, "type": "PlainIntegerRelation", "rhs": { "name": "T26", "type": "PlainIntegerVariable" }, "operation": "<" } ] }, "ground": [ "T30", "T29", "T26" ], "free": [], "exprvars": [ "T30", "T29", "T26" ] } }, "1111": { "goal": [{ "clause": -1, "scope": -1, "term": "(factorial T29 T26 T30 T28)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [ { "lhs": { "name": "T29", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "type": "PlainIntegerConstant", "value": "0" }, { "type": "PlainIntegerConstant", "value": "1" } ], "type": "PlainIntegerOperation", "operation": "+" }, "operation": "=" }, { "lhs": { "name": "T30", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "type": "PlainIntegerConstant", "value": "1" }, { "name": "T29", "type": "PlainIntegerVariable" } ], "type": "PlainIntegerOperation", "operation": "*" }, "operation": "=" }, { "lhs": { "type": "PlainIntegerConstant", "value": "0" }, "type": "PlainIntegerRelation", "rhs": { "name": "T26", "type": "PlainIntegerVariable" }, "operation": "<" } ] }, "ground": [ "T30", "T29", "T26" ], "free": [ "X43", "X44" ], "exprvars": [ "T30", "T29", "T26" ] } }, "2209": { "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": "0" }, { "type": "PlainIntegerConstant", "value": "1" } ], "type": "PlainIntegerOperation", "operation": "+" }, "operation": "=" }, { "lhs": { "name": "T30", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "type": "PlainIntegerConstant", "value": "1" }, { "name": "T29", "type": "PlainIntegerVariable" } ], "type": "PlainIntegerOperation", "operation": "*" }, "operation": "=" }, { "lhs": { "arguments": [ { "type": "PlainIntegerConstant", "value": "0" }, { "type": "PlainIntegerConstant", "value": "1" } ], "type": "PlainIntegerOperation", "operation": "+" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "type": "PlainIntegerConstant", "value": "0" }, { "type": "PlainIntegerConstant", "value": "1" } ], "type": "PlainIntegerOperation", "operation": "+" }, "operation": "=" }, { "lhs": { "arguments": [ { "type": "PlainIntegerConstant", "value": "1" }, { "name": "T68", "type": "PlainIntegerVariable" } ], "type": "PlainIntegerOperation", "operation": "*" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "type": "PlainIntegerConstant", "value": "1" }, { "name": "T29", "type": "PlainIntegerVariable" } ], "type": "PlainIntegerOperation", "operation": "*" }, "operation": "=" }, { "lhs": { "type": "PlainIntegerConstant", "value": "0" }, "type": "PlainIntegerRelation", "rhs": { "name": "T26", "type": "PlainIntegerVariable" }, "operation": "<" }, { "lhs": { "name": "T68", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "name": "T26", "type": "PlainIntegerVariable" }, "operation": "<" } ] }, "ground": [], "free": [], "exprvars": [ "T69", "T30", "T68", "T29", "T26" ] } }, "10": { "goal": [{ "clause": -1, "scope": -1, "term": "(factorial (0) T11 (1) T13)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T11"], "free": [], "exprvars": [] } }, "1713": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (< T53 T54) (',' (is X75 (+ T53 (1))) (',' (is X76 (* T55 X75)) (factorial X75 T54 X76 T57))))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [ { "lhs": { "name": "T29", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "type": "PlainIntegerConstant", "value": "0" }, { "type": "PlainIntegerConstant", "value": "1" } ], "type": "PlainIntegerOperation", "operation": "+" }, "operation": "=" }, { "lhs": { "name": "T30", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "type": "PlainIntegerConstant", "value": "1" }, { "name": "T29", "type": "PlainIntegerVariable" } ], "type": "PlainIntegerOperation", "operation": "*" }, "operation": "=" }, { "lhs": { "arguments": [ { "type": "PlainIntegerConstant", "value": "0" }, { "type": "PlainIntegerConstant", "value": "1" } ], "type": "PlainIntegerOperation", "operation": "+" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "type": "PlainIntegerConstant", "value": "0" }, { "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": "T29", "type": "PlainIntegerVariable" } ], "type": "PlainIntegerOperation", "operation": "*" }, "operation": "=" }, { "lhs": { "type": "PlainIntegerConstant", "value": "0" }, "type": "PlainIntegerRelation", "rhs": { "name": "T26", "type": "PlainIntegerVariable" }, "operation": "<" }, { "lhs": { "name": "T54", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "name": "T26", "type": "PlainIntegerVariable" }, "operation": "<" } ] }, "ground": [ "T53", "T54", "T55" ], "free": [ "X75", "X76" ], "exprvars": [ "T53", "T30", "T29", "T55", "T54", "T26" ] } }, "13": { "goal": [ { "clause": 1, "scope": 2, "term": "(factorial (0) T11 (1) T13)" }, { "clause": 2, "scope": 2, "term": "(factorial (0) T11 (1) T13)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T11"], "free": [], "exprvars": [] } }, "15": { "goal": [{ "clause": 1, "scope": 2, "term": "(factorial (0) T11 (1) T13)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T11"], "free": [], "exprvars": [] } }, "17": { "goal": [{ "clause": 2, "scope": 2, "term": "(factorial (0) T11 (1) T13)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T11"], "free": [], "exprvars": [] } }, "1097": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (is X44 (* (1) T29)) (factorial T29 T26 X44 T28))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [ { "lhs": { "name": "T29", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "type": "PlainIntegerConstant", "value": "0" }, { "type": "PlainIntegerConstant", "value": "1" } ], "type": "PlainIntegerOperation", "operation": "+" }, "operation": "=" }, { "lhs": { "type": "PlainIntegerConstant", "value": "0" }, "type": "PlainIntegerRelation", "rhs": { "name": "T26", "type": "PlainIntegerVariable" }, "operation": "<" } ] }, "ground": [ "T29", "T26" ], "free": [ "X43", "X44" ], "exprvars": [ "T29", "T26" ] } }, "1": { "goal": [{ "clause": -1, "scope": -1, "term": "(factorial T2 T3)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T2"], "free": [], "exprvars": [] } }, "1128": { "goal": [ { "clause": 1, "scope": 3, "term": "(factorial T29 T26 T30 T28)" }, { "clause": 2, "scope": 3, "term": "(factorial T29 T26 T30 T28)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [ { "lhs": { "name": "T29", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "type": "PlainIntegerConstant", "value": "0" }, { "type": "PlainIntegerConstant", "value": "1" } ], "type": "PlainIntegerOperation", "operation": "+" }, "operation": "=" }, { "lhs": { "name": "T30", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "type": "PlainIntegerConstant", "value": "1" }, { "name": "T29", "type": "PlainIntegerVariable" } ], "type": "PlainIntegerOperation", "operation": "*" }, "operation": "=" }, { "lhs": { "type": "PlainIntegerConstant", "value": "0" }, "type": "PlainIntegerRelation", "rhs": { "name": "T26", "type": "PlainIntegerVariable" }, "operation": "<" } ] }, "ground": [ "T30", "T29", "T26" ], "free": [], "exprvars": [ "T30", "T29", "T26" ] } }, "442": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (is X43 (+ (0) (1))) (',' (is X44 (* (1) X43)) (factorial X43 T26 X44 T28)))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [{ "lhs": { "type": "PlainIntegerConstant", "value": "0" }, "type": "PlainIntegerRelation", "rhs": { "name": "T26", "type": "PlainIntegerVariable" }, "operation": "<" }] }, "ground": ["T26"], "free": [ "X43", "X44" ], "exprvars": ["T26"] } }, "444": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [{ "lhs": { "type": "PlainIntegerConstant", "value": "0" }, "type": "PlainIntegerRelation", "rhs": { "name": "T26", "type": "PlainIntegerVariable" }, "operation": ">=" }] }, "ground": ["T26"], "free": [ "X43", "X44" ], "exprvars": ["T26"] } }, "2214": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "5": { "goal": [{ "clause": 0, "scope": 1, "term": "(factorial T2 T3)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T2"], "free": [], "exprvars": [] } }, "2213": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "1343": { "goal": [{ "clause": 2, "scope": 3, "term": "(factorial T29 T26 T30 T28)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [ { "lhs": { "name": "T29", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "type": "PlainIntegerConstant", "value": "0" }, { "type": "PlainIntegerConstant", "value": "1" } ], "type": "PlainIntegerOperation", "operation": "+" }, "operation": "=" }, { "lhs": { "name": "T30", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "type": "PlainIntegerConstant", "value": "1" }, { "name": "T29", "type": "PlainIntegerVariable" } ], "type": "PlainIntegerOperation", "operation": "*" }, "operation": "=" }, { "lhs": { "type": "PlainIntegerConstant", "value": "0" }, "type": "PlainIntegerRelation", "rhs": { "name": "T26", "type": "PlainIntegerVariable" }, "operation": "<" } ] }, "ground": [ "T30", "T29", "T26" ], "free": [], "exprvars": [ "T30", "T29", "T26" ] } }, "2212": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "2035": { "goal": [{ "clause": -1, "scope": -1, "term": "(factorial T58 T54 T59 T57)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [ { "lhs": { "name": "T29", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "type": "PlainIntegerConstant", "value": "0" }, { "type": "PlainIntegerConstant", "value": "1" } ], "type": "PlainIntegerOperation", "operation": "+" }, "operation": "=" }, { "lhs": { "name": "T30", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "type": "PlainIntegerConstant", "value": "1" }, { "name": "T29", "type": "PlainIntegerVariable" } ], "type": "PlainIntegerOperation", "operation": "*" }, "operation": "=" }, { "lhs": { "arguments": [ { "type": "PlainIntegerConstant", "value": "0" }, { "type": "PlainIntegerConstant", "value": "1" } ], "type": "PlainIntegerOperation", "operation": "+" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "type": "PlainIntegerConstant", "value": "0" }, { "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": "T29", "type": "PlainIntegerVariable" } ], "type": "PlainIntegerOperation", "operation": "*" }, "operation": "=" }, { "lhs": { "name": "T58", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "name": "T53", "type": "PlainIntegerVariable" }, { "type": "PlainIntegerConstant", "value": "1" } ], "type": "PlainIntegerOperation", "operation": "+" }, "operation": "=" }, { "lhs": { "name": "T59", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "name": "T55", "type": "PlainIntegerVariable" }, { "name": "T58", "type": "PlainIntegerVariable" } ], "type": "PlainIntegerOperation", "operation": "*" }, "operation": "=" }, { "lhs": { "type": "PlainIntegerConstant", "value": "0" }, "type": "PlainIntegerRelation", "rhs": { "name": "T26", "type": "PlainIntegerVariable" }, "operation": "<" }, { "lhs": { "name": "T54", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "name": "T26", "type": "PlainIntegerVariable" }, "operation": "<" }, { "lhs": { "name": "T53", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "name": "T54", "type": "PlainIntegerVariable" }, "operation": "<" } ] }, "ground": [ "T53", "T58", "T55", "T54", "T59" ], "free": [ "X75", "X76" ], "exprvars": [ "T53", "T58", "T30", "T29", "T55", "T54", "T26", "T59" ] } }, "2211": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [ { "lhs": { "name": "T29", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "type": "PlainIntegerConstant", "value": "0" }, { "type": "PlainIntegerConstant", "value": "1" } ], "type": "PlainIntegerOperation", "operation": "+" }, "operation": "=" }, { "lhs": { "name": "T30", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "type": "PlainIntegerConstant", "value": "1" }, { "name": "T29", "type": "PlainIntegerVariable" } ], "type": "PlainIntegerOperation", "operation": "*" }, "operation": "=" }, { "lhs": { "arguments": [ { "type": "PlainIntegerConstant", "value": "0" }, { "type": "PlainIntegerConstant", "value": "1" } ], "type": "PlainIntegerOperation", "operation": "+" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "type": "PlainIntegerConstant", "value": "0" }, { "type": "PlainIntegerConstant", "value": "1" } ], "type": "PlainIntegerOperation", "operation": "+" }, "operation": "=" }, { "lhs": { "arguments": [ { "type": "PlainIntegerConstant", "value": "1" }, { "name": "T68", "type": "PlainIntegerVariable" } ], "type": "PlainIntegerOperation", "operation": "*" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "type": "PlainIntegerConstant", "value": "1" }, { "name": "T29", "type": "PlainIntegerVariable" } ], "type": "PlainIntegerOperation", "operation": "*" }, "operation": "=" }, { "lhs": { "type": "PlainIntegerConstant", "value": "0" }, "type": "PlainIntegerRelation", "rhs": { "name": "T26", "type": "PlainIntegerVariable" }, "operation": "<" }, { "lhs": { "name": "T68", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "name": "T26", "type": "PlainIntegerVariable" }, "operation": "<" } ] }, "ground": [], "free": [], "exprvars": [ "T69", "T30", "T68", "T29", "T26" ] } } }, "edges": [ { "from": 1, "to": 5, "label": "CASE" }, { "from": 5, "to": 10, "label": "ONLY EVAL with clause\nfactorial(X11, X12) :- factorial(0, X11, 1, X12).\nand substitutionT2 -> T11,\nX11 -> T11,\nT3 -> T13,\nX12 -> T13,\nT12 -> T13" }, { "from": 10, "to": 13, "label": "CASE" }, { "from": 13, "to": 15, "label": "PARALLEL" }, { "from": 13, "to": 17, "label": "PARALLEL" }, { "from": 15, "to": 22, "label": "ONLY EVAL with clause\nfactorial(X39, X40, X41, X42) :- ','(<(X39, X40), ','(is(X43, +(X39, 1)), ','(is(X44, *(X41, X43)), factorial(X43, X40, X44, X42)))).\nand substitutionX39 -> 0,\nT11 -> T26,\nX40 -> T26,\nX41 -> 1,\nT13 -> T28,\nX42 -> T28,\nT27 -> T28" }, { "from": 17, "to": 2212, "label": "EVAL with clause\nfactorial(X93, X93, X94, X94).\nand substitutionX93 -> 0,\nT11 -> 0,\nX94 -> 1,\nT13 -> 1" }, { "from": 17, "to": 2213, "label": "EVAL-BACKTRACK" }, { "from": 22, "to": 24, "label": "IS ERROR" }, { "from": 22, "to": 442, "label": "ARITHCOMP SUCCESS" }, { "from": 22, "to": 444, "label": "ARITHCOMP FAIL" }, { "from": 442, "to": 1097, "label": "\nX43 -> T29" }, { "from": 1097, "to": 1111, "label": "\nX44 -> T30" }, { "from": 1111, "to": 1128, "label": "CASE" }, { "from": 1128, "to": 1335, "label": "PARALLEL" }, { "from": 1128, "to": 1343, "label": "PARALLEL" }, { "from": 1335, "to": 1713, "label": "ONLY EVAL with clause\nfactorial(X71, X72, X73, X74) :- ','(<(X71, X72), ','(is(X75, +(X71, 1)), ','(is(X76, *(X73, X75)), factorial(X75, X72, X76, X74)))).\nand substitutionT29 -> T53,\nX71 -> T53,\nT26 -> T54,\nX72 -> T54,\nT30 -> T55,\nX73 -> T55,\nT28 -> T57,\nX74 -> T57,\nT56 -> T57" }, { "from": 1343, "to": 2209, "label": "EVAL with clause\nfactorial(X87, X87, X88, X88).\nand substitutionT29 -> T68,\nX87 -> T68,\nT26 -> T68,\nT30 -> T69,\nX88 -> T69,\nT28 -> T69" }, { "from": 1343, "to": 2210, "label": "EVAL-BACKTRACK" }, { "from": 1713, "to": 2032, "label": "ARITHCOMP SUCCESS" }, { "from": 1713, "to": 2033, "label": "ARITHCOMP FAIL" }, { "from": 2032, "to": 2034, "label": "\nX75 -> T58" }, { "from": 2034, "to": 2035, "label": "\nX76 -> T59" }, { "from": 2035, "to": 1111, "label": "INSTANCE with matching:\nT29 -> T58\nT26 -> T54\nT30 -> T59\nT28 -> T57\nX43 -> X75\nX44 -> X76" }, { "from": 2209, "to": 2211, "label": "SUCCESS" }, { "from": 2212, "to": 2214, "label": "SUCCESS" } ], "type": "Graph" } } ---------------------------------------- (2) Obligation: Rules: f2034_in(T55, T58, T54, T53) -> f2035_in(T58, T54, T59, T53, T55) :|: T59 = T55 * T58 f2035_out(x, x1, x2, x3, x4) -> f2034_out(x4, x, x1, x3) :|: TRUE f2032_in(x5, x6, x7) -> f2034_in(x6, x8, x7, x5) :|: x8 = x5 + 1 f2034_out(x9, x10, x11, x12) -> f2032_out(x12, x9, x11) :|: TRUE f1111_out(x13, x14, x15) -> f2035_out(x13, x14, x15, x16, x17) :|: TRUE f2035_in(x18, x19, x20, x21, x22) -> f1111_in(x18, x19, x20) :|: TRUE f1128_in(T29, T26, T30) -> f1343_in(T29, T26, T30) :|: TRUE f1128_in(x23, x24, x25) -> f1335_in(x23, x24, x25) :|: TRUE f1335_out(x26, x27, x28) -> f1128_out(x26, x27, x28) :|: TRUE f1343_out(x29, x30, x31) -> f1128_out(x29, x30, x31) :|: TRUE f1335_in(x32, x33, x34) -> f1713_in(x32, x33, x34) :|: TRUE f1713_out(x35, x36, x37) -> f1335_out(x35, x36, x37) :|: TRUE f1713_in(x38, x39, x40) -> f2033_in(x38, x40, x39) :|: x38 >= x39 f1713_in(x41, x42, x43) -> f2032_in(x41, x43, x42) :|: x41 < x42 f2032_out(x44, x45, x46) -> f1713_out(x44, x46, x45) :|: x44 < x46 f2033_out(x47, x48, x49) -> f1713_out(x47, x49, x48) :|: x47 >= x49 f1111_in(x50, x51, x52) -> f1128_in(x50, x51, x52) :|: TRUE f1128_out(x53, x54, x55) -> f1111_out(x53, x54, x55) :|: TRUE f1_in(T2) -> f5_in(T2) :|: TRUE f5_out(x56) -> f1_out(x56) :|: TRUE f10_out(T11) -> f5_out(T11) :|: TRUE f5_in(x57) -> f10_in(x57) :|: TRUE f13_out(x58) -> f10_out(x58) :|: TRUE f10_in(x59) -> f13_in(x59) :|: TRUE f13_in(x60) -> f15_in(x60) :|: TRUE f15_out(x61) -> f13_out(x61) :|: TRUE f13_in(x62) -> f17_in(x62) :|: TRUE f17_out(x63) -> f13_out(x63) :|: TRUE f15_in(x64) -> f22_in(x64) :|: TRUE f22_out(x65) -> f15_out(x65) :|: TRUE f24_out -> f22_out(x66) :|: TRUE f22_in(x67) -> f442_in(x67) :|: 0 < x67 f22_in(x68) -> f24_in :|: TRUE f22_in(x69) -> f444_in(x69) :|: 0 >= x69 f444_out(x70) -> f22_out(x70) :|: 0 >= x70 f442_out(x71) -> f22_out(x71) :|: 0 < x71 f1097_out(x72, x73) -> f442_out(x73) :|: TRUE f442_in(x74) -> f1097_in(x75, x74) :|: x75 = 0 + 1 f1097_in(x76, x77) -> f1111_in(x76, x77, x78) :|: x78 = 1 * x76 f1111_out(x79, x80, x81) -> f1097_out(x79, x80) :|: TRUE Start term: f1_in(T2) ---------------------------------------- (3) IRSwTSimpleDependencyGraphProof (EQUIVALENT) Constructed simple dependency graph. Simplified to the following IRSwTs: intTRSProblem: f2034_in(T55, T58, T54, T53) -> f2035_in(T58, T54, T59, T53, T55) :|: T59 = T55 * T58 f2032_in(x5, x6, x7) -> f2034_in(x6, x8, x7, x5) :|: x8 = x5 + 1 f2035_in(x18, x19, x20, x21, x22) -> f1111_in(x18, x19, x20) :|: TRUE f1128_in(x23, x24, x25) -> f1335_in(x23, x24, x25) :|: TRUE f1335_in(x32, x33, x34) -> f1713_in(x32, x33, x34) :|: TRUE f1713_in(x41, x42, x43) -> f2032_in(x41, x43, x42) :|: x41 < x42 f1111_in(x50, x51, x52) -> f1128_in(x50, x51, x52) :|: TRUE ---------------------------------------- (4) Obligation: Rules: f2034_in(T55, T58, T54, T53) -> f2035_in(T58, T54, T59, T53, T55) :|: T59 = T55 * T58 f2032_in(x5, x6, x7) -> f2034_in(x6, x8, x7, x5) :|: x8 = x5 + 1 f2035_in(x18, x19, x20, x21, x22) -> f1111_in(x18, x19, x20) :|: TRUE f1128_in(x23, x24, x25) -> f1335_in(x23, x24, x25) :|: TRUE f1335_in(x32, x33, x34) -> f1713_in(x32, x33, x34) :|: TRUE f1713_in(x41, x42, x43) -> f2032_in(x41, x43, x42) :|: x41 < x42 f1111_in(x50, x51, x52) -> f1128_in(x50, x51, x52) :|: TRUE ---------------------------------------- (5) IntTRSCompressionProof (EQUIVALENT) Compressed rules. ---------------------------------------- (6) Obligation: Rules: f1128_in(x23:0, x24:0, x25:0) -> f1128_in(x23:0 + 1, x24:0, x25:0 * (x23:0 + 1)) :|: x24:0 > x23:0 ---------------------------------------- (7) IRSFormatTransformerProof (EQUIVALENT) Reformatted IRS to match normalized format (transformed away non-linear left-hand sides, !=, / and %). ---------------------------------------- (8) Obligation: Rules: f1128_in(x23:0, x24:0, x25:0) -> f1128_in(arith, x24:0, arith1) :|: x24:0 > x23:0 && arith = x23:0 + 1 && arith1 = x25:0 * (x23:0 + 1) ---------------------------------------- (9) IRSwTTerminationDigraphProof (EQUIVALENT) Constructed termination digraph! Nodes: (1) f1128_in(x23:0, x24:0, x25:0) -> f1128_in(arith, x24:0, arith1) :|: x24:0 > x23:0 && arith = x23:0 + 1 && arith1 = x25:0 * (x23:0 + 1) Arcs: (1) -> (1) This digraph is fully evaluated! ---------------------------------------- (10) Obligation: Termination digraph: Nodes: (1) f1128_in(x23:0, x24:0, x25:0) -> f1128_in(arith, x24:0, arith1) :|: x24:0 > x23:0 && arith = x23:0 + 1 && arith1 = x25:0 * (x23:0 + 1) Arcs: (1) -> (1) This digraph is fully evaluated! ---------------------------------------- (11) IntTRSCompressionProof (EQUIVALENT) Compressed rules. ---------------------------------------- (12) Obligation: Rules: f1128_in(x23:0:0, x24:0:0, x25:0:0) -> f1128_in(x23:0:0 + 1, x24:0:0, x25:0:0 * (x23:0:0 + 1)) :|: x24:0:0 > x23:0:0 ---------------------------------------- (13) IntTRSUnneededArgumentFilterProof (EQUIVALENT) Some arguments are removed because they cannot influence termination. We removed arguments according to the following replacements: f1128_in(x1, x2, x3) -> f1128_in(x1, x2) ---------------------------------------- (14) Obligation: Rules: f1128_in(x23:0:0, x24:0:0) -> f1128_in(x23:0:0 + 1, x24:0:0) :|: x24:0:0 > x23:0:0 ---------------------------------------- (15) TempFilterProof (SOUND) Used the following sort dictionary for filtering: f1128_in(INTEGER, INTEGER) Replaced non-predefined constructor symbols by 0. ---------------------------------------- (16) Obligation: Rules: f1128_in(x23:0:0, x24:0:0) -> f1128_in(c, x24:0:0) :|: c = x23:0:0 + 1 && x24:0:0 > x23:0:0 ---------------------------------------- (17) PolynomialOrderProcessor (EQUIVALENT) Found the following polynomial interpretation: [f1128_in(x, x1)] = -x + x1 The following rules are decreasing: f1128_in(x23:0:0, x24:0:0) -> f1128_in(c, x24:0:0) :|: c = x23:0:0 + 1 && x24:0:0 > x23:0:0 The following rules are bounded: f1128_in(x23:0:0, x24:0:0) -> f1128_in(c, x24:0:0) :|: c = x23:0:0 + 1 && x24:0:0 > x23:0:0 ---------------------------------------- (18) YES