/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 ackermann(g,g,a) w.r.t. the given Prolog program could successfully be proven: (0) Prolog (1) PrologToIRSwTTransformerProof [SOUND, 62 ms] (2) IRSwT (3) IRSwTSimpleDependencyGraphProof [EQUIVALENT, 0 ms] (4) IRSwT (5) IntTRSCompressionProof [EQUIVALENT, 51 ms] (6) IRSwT (7) IRSFormatTransformerProof [EQUIVALENT, 0 ms] (8) IRSwT (9) IRSwTTerminationDigraphProof [EQUIVALENT, 54 ms] (10) IRSwT (11) IntTRSCompressionProof [EQUIVALENT, 0 ms] (12) IRSwT (13) TempFilterProof [SOUND, 51 ms] (14) IntTRS (15) PolynomialOrderProcessor [EQUIVALENT, 6 ms] (16) IntTRS (17) RankingReductionPairProof [EQUIVALENT, 4 ms] (18) YES ---------------------------------------- (0) Obligation: Clauses: ackermann(X, Y, Z) :- ','(=:=(X, 0), ','(>=(Y, 0), is(Z, +(Y, 1)))). ackermann(X, Y, Z) :- ','(>(X, 0), ','(=:=(Y, 0), ackermann(-(X, 1), 1, Z))). ackermann(X, Y, Z) :- ','(>(X, 0), ','(>(Y, 0), ','(ackermann(X, -(Y, 1), W), ackermann(-(X, 1), W, Z)))). Query: ackermann(g,g,a) ---------------------------------------- (1) PrologToIRSwTTransformerProof (SOUND) Transformed Prolog program to IRSwT according to method in Master Thesis of A. Weinert { "root": 4, "program": { "directives": [], "clauses": [ [ "(ackermann X Y Z)", "(',' (=:= X (0)) (',' (>= Y (0)) (is Z (+ Y (1)))))" ], [ "(ackermann X Y Z)", "(',' (> X (0)) (',' (=:= Y (0)) (ackermann (- X (1)) (1) Z)))" ], [ "(ackermann X Y Z)", "(',' (> X (0)) (',' (> Y (0)) (',' (ackermann X (- Y (1)) W) (ackermann (- X (1)) W Z))))" ] ] }, "graph": { "nodes": { "2273": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "2295": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "type": "Nodes", "2272": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [{ "lhs": { "type": "PlainIntegerConstant", "value": "0" }, "type": "PlainIntegerRelation", "rhs": { "name": "T37", "type": "PlainIntegerVariable" }, "operation": ">=" }] }, "ground": [ "T38", "T37" ], "free": [], "exprvars": ["T37"] } }, "2271": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (=:= T38 (0)) (ackermann (- T37 (1)) (1) T40))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [{ "lhs": { "type": "PlainIntegerConstant", "value": "0" }, "type": "PlainIntegerRelation", "rhs": { "name": "T37", "type": "PlainIntegerVariable" }, "operation": "<" }] }, "ground": [ "T38", "T37" ], "free": [], "exprvars": ["T37"] } }, "2293": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [{ "lhs": { "type": "PlainIntegerConstant", "value": "0" }, "type": "PlainIntegerRelation", "rhs": { "name": "T50", "type": "PlainIntegerVariable" }, "operation": ">=" }] }, "ground": [ "T51", "T50" ], "free": ["X44"], "exprvars": ["T50"] } }, "2291": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (> T51 (0)) (',' (ackermann T50 (- T51 (1)) X44) (ackermann (- T50 (1)) X44 T53)))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [{ "lhs": { "type": "PlainIntegerConstant", "value": "0" }, "type": "PlainIntegerRelation", "rhs": { "name": "T50", "type": "PlainIntegerVariable" }, "operation": "<" }] }, "ground": [ "T51", "T50" ], "free": ["X44"], "exprvars": ["T50"] } }, "2206": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "2205": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (> T37 (0)) (',' (=:= T38 (0)) (ackermann (- T37 (1)) (1) T40)))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T37", "T38" ], "free": [], "exprvars": [] } }, "2204": { "goal": [{ "clause": 2, "scope": 1, "term": "(ackermann T1 T2 T3)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T1", "T2" ], "free": [], "exprvars": [] } }, "2203": { "goal": [{ "clause": 1, "scope": 1, "term": "(ackermann T1 T2 T3)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T1", "T2" ], "free": [], "exprvars": [] } }, "2202": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [ { "lhs": { "name": "T18", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "type": "PlainIntegerConstant", "value": "0" }, "operation": "=" }, { "lhs": { "name": "T22", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "name": "T19", "type": "PlainIntegerVariable" }, { "type": "PlainIntegerConstant", "value": "1" } ], "type": "PlainIntegerOperation", "operation": "+" }, "operation": "=" }, { "lhs": { "type": "PlainIntegerConstant", "value": "0" }, "type": "PlainIntegerRelation", "rhs": { "name": "T19", "type": "PlainIntegerVariable" }, "operation": "<=" } ] }, "ground": [], "free": [], "exprvars": [ "T19", "T18", "T22" ] } }, "2201": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [ { "lhs": { "name": "T18", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "type": "PlainIntegerConstant", "value": "0" }, "operation": "=" }, { "lhs": { "type": "PlainIntegerConstant", "value": "0" }, "type": "PlainIntegerRelation", "rhs": { "name": "T19", "type": "PlainIntegerVariable" }, "operation": "<=" } ] }, "ground": [ "T19", "T18" ], "free": [], "exprvars": [ "T19", "T18" ] } }, "238": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (>= T19 (0)) (is T21 (+ T19 (1))))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [{ "lhs": { "name": "T18", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "type": "PlainIntegerConstant", "value": "0" }, "operation": "=" }] }, "ground": [ "T19", "T18" ], "free": [], "exprvars": ["T18"] } }, "2200": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [ { "lhs": { "name": "T18", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "type": "PlainIntegerConstant", "value": "0" }, "operation": "=" }, { "lhs": { "name": "T22", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "name": "T19", "type": "PlainIntegerVariable" }, { "type": "PlainIntegerConstant", "value": "1" } ], "type": "PlainIntegerOperation", "operation": "+" }, "operation": "=" }, { "lhs": { "type": "PlainIntegerConstant", "value": "0" }, "type": "PlainIntegerRelation", "rhs": { "name": "T19", "type": "PlainIntegerVariable" }, "operation": "<=" } ] }, "ground": [ "T19", "T18", "T22" ], "free": [], "exprvars": [ "T19", "T18", "T22" ] } }, "239": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [{ "lhs": { "name": "T18", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "type": "PlainIntegerConstant", "value": "0" }, "operation": "!=" }] }, "ground": [ "T19", "T18" ], "free": [], "exprvars": ["T18"] } }, "2309": { "goal": [{ "clause": -1, "scope": -1, "term": "(ackermann T50 (- T51 (1)) X44)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [ { "lhs": { "type": "PlainIntegerConstant", "value": "0" }, "type": "PlainIntegerRelation", "rhs": { "name": "T50", "type": "PlainIntegerVariable" }, "operation": "<" }, { "lhs": { "type": "PlainIntegerConstant", "value": "0" }, "type": "PlainIntegerRelation", "rhs": { "name": "T51", "type": "PlainIntegerVariable" }, "operation": "<" } ] }, "ground": [ "T51", "T50" ], "free": ["X44"], "exprvars": [ "T51", "T50" ] } }, "2308": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [ { "lhs": { "type": "PlainIntegerConstant", "value": "0" }, "type": "PlainIntegerRelation", "rhs": { "name": "T50", "type": "PlainIntegerVariable" }, "operation": "<" }, { "lhs": { "type": "PlainIntegerConstant", "value": "0" }, "type": "PlainIntegerRelation", "rhs": { "name": "T51", "type": "PlainIntegerVariable" }, "operation": ">=" } ] }, "ground": [ "T51", "T50" ], "free": ["X44"], "exprvars": [ "T51", "T50" ] } }, "2307": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (ackermann T50 (- T51 (1)) X44) (ackermann (- T50 (1)) X44 T53))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [ { "lhs": { "type": "PlainIntegerConstant", "value": "0" }, "type": "PlainIntegerRelation", "rhs": { "name": "T50", "type": "PlainIntegerVariable" }, "operation": "<" }, { "lhs": { "type": "PlainIntegerConstant", "value": "0" }, "type": "PlainIntegerRelation", "rhs": { "name": "T51", "type": "PlainIntegerVariable" }, "operation": "<" } ] }, "ground": [ "T51", "T50" ], "free": ["X44"], "exprvars": [ "T51", "T50" ] } }, "11": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (=:= T18 (0)) (',' (>= T19 (0)) (is T21 (+ T19 (1)))))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T18", "T19" ], "free": [], "exprvars": [] } }, "12": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "2285": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "2284": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (> T50 (0)) (',' (> T51 (0)) (',' (ackermann T50 (- T51 (1)) X44) (ackermann (- T50 (1)) X44 T53))))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T50", "T51" ], "free": ["X44"], "exprvars": [] } }, "240": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "2281": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [ { "lhs": { "name": "T38", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "type": "PlainIntegerConstant", "value": "0" }, "operation": "!=" }, { "lhs": { "type": "PlainIntegerConstant", "value": "0" }, "type": "PlainIntegerRelation", "rhs": { "name": "T37", "type": "PlainIntegerVariable" }, "operation": "<" } ] }, "ground": [ "T38", "T37" ], "free": [], "exprvars": [ "T38", "T37" ] } }, "2280": { "goal": [{ "clause": -1, "scope": -1, "term": "(ackermann (- T37 (1)) (1) T40)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [ { "lhs": { "name": "T38", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "type": "PlainIntegerConstant", "value": "0" }, "operation": "=" }, { "lhs": { "type": "PlainIntegerConstant", "value": "0" }, "type": "PlainIntegerRelation", "rhs": { "name": "T37", "type": "PlainIntegerVariable" }, "operation": "<" } ] }, "ground": [ "T38", "T37" ], "free": [], "exprvars": [ "T38", "T37" ] } }, "1327": { "goal": [{ "clause": -1, "scope": -1, "term": "(is T21 (+ T19 (1)))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [ { "lhs": { "name": "T18", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "type": "PlainIntegerConstant", "value": "0" }, "operation": "=" }, { "lhs": { "type": "PlainIntegerConstant", "value": "0" }, "type": "PlainIntegerRelation", "rhs": { "name": "T19", "type": "PlainIntegerVariable" }, "operation": "<=" } ] }, "ground": [ "T19", "T18" ], "free": [], "exprvars": [ "T19", "T18" ] } }, "4": { "goal": [{ "clause": -1, "scope": -1, "term": "(ackermann T1 T2 T3)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T1", "T2" ], "free": [], "exprvars": [] } }, "6": { "goal": [ { "clause": 0, "scope": 1, "term": "(ackermann T1 T2 T3)" }, { "clause": 1, "scope": 1, "term": "(ackermann T1 T2 T3)" }, { "clause": 2, "scope": 1, "term": "(ackermann T1 T2 T3)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T1", "T2" ], "free": [], "exprvars": [] } }, "2310": { "goal": [{ "clause": -1, "scope": -1, "term": "(ackermann (- T50 (1)) T56 T53)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T50", "T56" ], "free": [], "exprvars": [] } }, "8": { "goal": [{ "clause": 0, "scope": 1, "term": "(ackermann T1 T2 T3)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T1", "T2" ], "free": [], "exprvars": [] } }, "9": { "goal": [ { "clause": 1, "scope": 1, "term": "(ackermann T1 T2 T3)" }, { "clause": 2, "scope": 1, "term": "(ackermann T1 T2 T3)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T1", "T2" ], "free": [], "exprvars": [] } }, "1328": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [ { "lhs": { "name": "T18", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "type": "PlainIntegerConstant", "value": "0" }, "operation": "=" }, { "lhs": { "type": "PlainIntegerConstant", "value": "0" }, "type": "PlainIntegerRelation", "rhs": { "name": "T19", "type": "PlainIntegerVariable" }, "operation": ">" } ] }, "ground": [ "T19", "T18" ], "free": [], "exprvars": [ "T19", "T18" ] } } }, "edges": [ { "from": 4, "to": 6, "label": "CASE" }, { "from": 6, "to": 8, "label": "PARALLEL" }, { "from": 6, "to": 9, "label": "PARALLEL" }, { "from": 8, "to": 11, "label": "ONLY EVAL with clause\nackermann(X13, X14, X15) :- ','(=:=(X13, 0), ','(>=(X14, 0), is(X15, +(X14, 1)))).\nand substitutionT1 -> T18,\nX13 -> T18,\nT2 -> T19,\nX14 -> T19,\nT3 -> T21,\nX15 -> T21,\nT20 -> T21" }, { "from": 9, "to": 2203, "label": "PARALLEL" }, { "from": 9, "to": 2204, "label": "PARALLEL" }, { "from": 11, "to": 12, "label": "IS ERROR" }, { "from": 11, "to": 238, "label": "ARITHCOMP SUCCESS" }, { "from": 11, "to": 239, "label": "ARITHCOMP FAIL" }, { "from": 238, "to": 240, "label": "IS ERROR" }, { "from": 238, "to": 1327, "label": "ARITHCOMP SUCCESS" }, { "from": 238, "to": 1328, "label": "ARITHCOMP FAIL" }, { "from": 1327, "to": 2200, "label": "\nT21 -> T22" }, { "from": 1327, "to": 2201, "label": "IS FAIL" }, { "from": 2200, "to": 2202, "label": "SUCCESS" }, { "from": 2203, "to": 2205, "label": "ONLY EVAL with clause\nackermann(X28, X29, X30) :- ','(>(X28, 0), ','(=:=(X29, 0), ackermann(-(X28, 1), 1, X30))).\nand substitutionT1 -> T37,\nX28 -> T37,\nT2 -> T38,\nX29 -> T38,\nT3 -> T40,\nX30 -> T40,\nT39 -> T40" }, { "from": 2204, "to": 2284, "label": "ONLY EVAL with clause\nackermann(X41, X42, X43) :- ','(>(X41, 0), ','(>(X42, 0), ','(ackermann(X41, -(X42, 1), X44), ackermann(-(X41, 1), X44, X43)))).\nand substitutionT1 -> T50,\nX41 -> T50,\nT2 -> T51,\nX42 -> T51,\nT3 -> T53,\nX43 -> T53,\nT52 -> T53" }, { "from": 2205, "to": 2206, "label": "IS ERROR" }, { "from": 2205, "to": 2271, "label": "ARITHCOMP SUCCESS" }, { "from": 2205, "to": 2272, "label": "ARITHCOMP FAIL" }, { "from": 2271, "to": 2273, "label": "IS ERROR" }, { "from": 2271, "to": 2280, "label": "ARITHCOMP SUCCESS" }, { "from": 2271, "to": 2281, "label": "ARITHCOMP FAIL" }, { "from": 2280, "to": 4, "label": "INSTANCE with matching:\nT1 -> -(T37, 1)\nT2 -> 1\nT3 -> T40" }, { "from": 2284, "to": 2285, "label": "IS ERROR" }, { "from": 2284, "to": 2291, "label": "ARITHCOMP SUCCESS" }, { "from": 2284, "to": 2293, "label": "ARITHCOMP FAIL" }, { "from": 2291, "to": 2295, "label": "IS ERROR" }, { "from": 2291, "to": 2307, "label": "ARITHCOMP SUCCESS" }, { "from": 2291, "to": 2308, "label": "ARITHCOMP FAIL" }, { "from": 2307, "to": 2309, "label": "SPLIT 1" }, { "from": 2307, "to": 2310, "label": "SPLIT 2\nnew knowledge:\nT50 is ground\nT51 is ground\nT56 is ground\nreplacements:X44 -> T56" }, { "from": 2309, "to": 4, "label": "INSTANCE with matching:\nT1 -> T50\nT2 -> -(T51, 1)\nT3 -> X44" }, { "from": 2310, "to": 4, "label": "INSTANCE with matching:\nT1 -> -(T50, 1)\nT2 -> T56\nT3 -> T53" } ], "type": "Graph" } } ---------------------------------------- (2) Obligation: Rules: f2309_out(T50, T51) -> f2310_in(T50, T56) :|: TRUE f2310_out(x, x1) -> f2307_out(x, x2) :|: TRUE f2307_in(x3, x4) -> f2309_in(x3, x4) :|: TRUE f2280_out(T37, T38) -> f2271_out(T38, T37) :|: T38 = 0 f2271_in(x5, x6) -> f2280_in(x6, x5) :|: x5 = 0 f2271_in(x7, x8) -> f2273_in :|: TRUE f2273_out -> f2271_out(x9, x10) :|: TRUE f2281_out(x11, x12) -> f2271_out(x11, x12) :|: !(x11 = 0) f2271_in(x13, x14) -> f2281_in(x13, x14) :|: !(x13 = 0) f2285_out -> f2284_out(x15, x16) :|: TRUE f2284_in(x17, x18) -> f2291_in(x18, x17) :|: x17 > 0 f2293_out(x19, x20) -> f2284_out(x20, x19) :|: x20 <= 0 f2284_in(x21, x22) -> f2285_in :|: TRUE f2291_out(x23, x24) -> f2284_out(x24, x23) :|: x24 > 0 f2284_in(x25, x26) -> f2293_in(x26, x25) :|: x25 <= 0 f9_in(T1, T2) -> f2203_in(T1, T2) :|: TRUE f2203_out(x27, x28) -> f9_out(x27, x28) :|: TRUE f2204_out(x29, x30) -> f9_out(x29, x30) :|: TRUE f9_in(x31, x32) -> f2204_in(x31, x32) :|: TRUE f4_out(x33 - 1, 1) -> f2280_out(x33, x34) :|: TRUE f2280_in(x35, x36) -> f4_in(x35 - 1, 1) :|: TRUE f4_in(x37, x38) -> f6_in(x37, x38) :|: TRUE f6_out(x39, x40) -> f4_out(x39, x40) :|: TRUE f2307_out(x41, x42) -> f2291_out(x42, x41) :|: x42 > 0 f2308_out(x43, x44) -> f2291_out(x43, x44) :|: x43 <= 0 f2291_in(x45, x46) -> f2295_in :|: TRUE f2291_in(x47, x48) -> f2307_in(x48, x47) :|: x47 > 0 f2291_in(x49, x50) -> f2308_in(x49, x50) :|: x49 <= 0 f2295_out -> f2291_out(x51, x52) :|: TRUE f2310_in(x53, x54) -> f4_in(x53 - 1, x54) :|: TRUE f4_out(x55 - 1, x56) -> f2310_out(x55, x56) :|: TRUE f6_in(x57, x58) -> f8_in(x57, x58) :|: TRUE f9_out(x59, x60) -> f6_out(x59, x60) :|: TRUE f6_in(x61, x62) -> f9_in(x61, x62) :|: TRUE f8_out(x63, x64) -> f6_out(x63, x64) :|: TRUE f2309_in(x65, x66) -> f4_in(x65, x66 - 1) :|: TRUE f4_out(x67, x68 - 1) -> f2309_out(x67, x68) :|: TRUE f2284_out(x69, x70) -> f2204_out(x69, x70) :|: TRUE f2204_in(x71, x72) -> f2284_in(x71, x72) :|: TRUE f2205_in(x73, x74) -> f2206_in :|: TRUE f2205_in(x75, x76) -> f2271_in(x76, x75) :|: x75 > 0 f2206_out -> f2205_out(x77, x78) :|: TRUE f2271_out(x79, x80) -> f2205_out(x80, x79) :|: x80 > 0 f2272_out(x81, x82) -> f2205_out(x82, x81) :|: x82 <= 0 f2205_in(x83, x84) -> f2272_in(x84, x83) :|: x83 <= 0 f2203_in(x85, x86) -> f2205_in(x85, x86) :|: TRUE f2205_out(x87, x88) -> f2203_out(x87, x88) :|: TRUE Start term: f4_in(T1, T2) ---------------------------------------- (3) IRSwTSimpleDependencyGraphProof (EQUIVALENT) Constructed simple dependency graph. Simplified to the following IRSwTs: intTRSProblem: f2307_in(x3, x4) -> f2309_in(x3, x4) :|: TRUE f2271_in(x5, x6) -> f2280_in(x6, x5) :|: x5 = 0 f2284_in(x17, x18) -> f2291_in(x18, x17) :|: x17 > 0 f9_in(T1, T2) -> f2203_in(T1, T2) :|: TRUE f9_in(x31, x32) -> f2204_in(x31, x32) :|: TRUE f2280_in(x35, x36) -> f4_in(x35 - 1, 1) :|: TRUE f4_in(x37, x38) -> f6_in(x37, x38) :|: TRUE f2291_in(x47, x48) -> f2307_in(x48, x47) :|: x47 > 0 f6_in(x61, x62) -> f9_in(x61, x62) :|: TRUE f2309_in(x65, x66) -> f4_in(x65, x66 - 1) :|: TRUE f2204_in(x71, x72) -> f2284_in(x71, x72) :|: TRUE f2205_in(x75, x76) -> f2271_in(x76, x75) :|: x75 > 0 f2203_in(x85, x86) -> f2205_in(x85, x86) :|: TRUE ---------------------------------------- (4) Obligation: Rules: f2307_in(x3, x4) -> f2309_in(x3, x4) :|: TRUE f2271_in(x5, x6) -> f2280_in(x6, x5) :|: x5 = 0 f2284_in(x17, x18) -> f2291_in(x18, x17) :|: x17 > 0 f9_in(T1, T2) -> f2203_in(T1, T2) :|: TRUE f9_in(x31, x32) -> f2204_in(x31, x32) :|: TRUE f2280_in(x35, x36) -> f4_in(x35 - 1, 1) :|: TRUE f4_in(x37, x38) -> f6_in(x37, x38) :|: TRUE f2291_in(x47, x48) -> f2307_in(x48, x47) :|: x47 > 0 f6_in(x61, x62) -> f9_in(x61, x62) :|: TRUE f2309_in(x65, x66) -> f4_in(x65, x66 - 1) :|: TRUE f2204_in(x71, x72) -> f2284_in(x71, x72) :|: TRUE f2205_in(x75, x76) -> f2271_in(x76, x75) :|: x75 > 0 f2203_in(x85, x86) -> f2205_in(x85, x86) :|: TRUE ---------------------------------------- (5) IntTRSCompressionProof (EQUIVALENT) Compressed rules. ---------------------------------------- (6) Obligation: Rules: f9_in(T1:0, cons_0) -> f9_in(T1:0 - 1, 1) :|: T1:0 > 0 && cons_0 = 0 f9_in(x31:0, x32:0) -> f9_in(x31:0, x32:0 - 1) :|: x31:0 > 0 && x32:0 > 0 ---------------------------------------- (7) IRSFormatTransformerProof (EQUIVALENT) Reformatted IRS to match normalized format (transformed away non-linear left-hand sides, !=, / and %). ---------------------------------------- (8) Obligation: Rules: f9_in(T1:0, cons_0) -> f9_in(arith, 1) :|: T1:0 > 0 && cons_0 = 0 && arith = T1:0 - 1 f9_in(x, x1) -> f9_in(x, x2) :|: x > 0 && x1 > 0 && x2 = x1 - 1 ---------------------------------------- (9) IRSwTTerminationDigraphProof (EQUIVALENT) Constructed termination digraph! Nodes: (1) f9_in(T1:0, cons_0) -> f9_in(arith, 1) :|: T1:0 > 0 && cons_0 = 0 && arith = T1:0 - 1 (2) f9_in(x, x1) -> f9_in(x, x2) :|: x > 0 && x1 > 0 && x2 = x1 - 1 Arcs: (1) -> (2) (2) -> (1), (2) This digraph is fully evaluated! ---------------------------------------- (10) Obligation: Termination digraph: Nodes: (1) f9_in(T1:0, cons_0) -> f9_in(arith, 1) :|: T1:0 > 0 && cons_0 = 0 && arith = T1:0 - 1 (2) f9_in(x, x1) -> f9_in(x, x2) :|: x > 0 && x1 > 0 && x2 = x1 - 1 Arcs: (1) -> (2) (2) -> (1), (2) This digraph is fully evaluated! ---------------------------------------- (11) IntTRSCompressionProof (EQUIVALENT) Compressed rules. ---------------------------------------- (12) Obligation: Rules: f9_in(T1:0:0, cons_0) -> f9_in(T1:0:0 - 1, 1) :|: T1:0:0 > 0 && cons_0 = 0 f9_in(x:0, x1:0) -> f9_in(x:0, x1:0 - 1) :|: x:0 > 0 && x1:0 > 0 ---------------------------------------- (13) TempFilterProof (SOUND) Used the following sort dictionary for filtering: f9_in(INTEGER, VARIABLE) Replaced non-predefined constructor symbols by 0. ---------------------------------------- (14) Obligation: Rules: f9_in(T1:0:0, c) -> f9_in(c1, c2) :|: c2 = 1 && (c1 = T1:0:0 - 1 && c = 0) && (T1:0:0 > 0 && cons_0 = 0) f9_in(x:0, x1:0) -> f9_in(x:0, c3) :|: c3 = x1:0 - 1 && (x:0 > 0 && x1:0 > 0) ---------------------------------------- (15) PolynomialOrderProcessor (EQUIVALENT) Found the following polynomial interpretation: [f9_in(x, x1)] = x The following rules are decreasing: f9_in(T1:0:0, c) -> f9_in(c1, c2) :|: c2 = 1 && (c1 = T1:0:0 - 1 && c = 0) && (T1:0:0 > 0 && cons_0 = 0) The following rules are bounded: f9_in(T1:0:0, c) -> f9_in(c1, c2) :|: c2 = 1 && (c1 = T1:0:0 - 1 && c = 0) && (T1:0:0 > 0 && cons_0 = 0) f9_in(x:0, x1:0) -> f9_in(x:0, c3) :|: c3 = x1:0 - 1 && (x:0 > 0 && x1:0 > 0) ---------------------------------------- (16) Obligation: Rules: f9_in(x:0, x1:0) -> f9_in(x:0, c3) :|: c3 = x1:0 - 1 && (x:0 > 0 && x1:0 > 0) ---------------------------------------- (17) RankingReductionPairProof (EQUIVALENT) Interpretation: [ f9_in ] = f9_in_2 The following rules are decreasing: f9_in(x:0, x1:0) -> f9_in(x:0, c3) :|: c3 = x1:0 - 1 && (x:0 > 0 && x1:0 > 0) The following rules are bounded: f9_in(x:0, x1:0) -> f9_in(x:0, c3) :|: c3 = x1:0 - 1 && (x:0 > 0 && x1:0 > 0) ---------------------------------------- (18) YES