/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 binomial(g,g,a) w.r.t. the given Prolog program could successfully be proven: (0) Prolog (1) PrologToIRSwTTransformerProof [SOUND, 42 ms] (2) IRSwT (3) IRSwTSimpleDependencyGraphProof [EQUIVALENT, 0 ms] (4) IRSwT (5) IntTRSCompressionProof [EQUIVALENT, 15 ms] (6) IRSwT (7) IRSFormatTransformerProof [EQUIVALENT, 0 ms] (8) IRSwT (9) IRSwTTerminationDigraphProof [EQUIVALENT, 28 ms] (10) IRSwT (11) IntTRSCompressionProof [EQUIVALENT, 0 ms] (12) IRSwT (13) IntTRSUnneededArgumentFilterProof [EQUIVALENT, 0 ms] (14) IRSwT (15) TempFilterProof [SOUND, 37 ms] (16) IntTRS (17) PolynomialOrderProcessor [EQUIVALENT, 14 ms] (18) YES ---------------------------------------- (0) Obligation: Clauses: binomial(N, K, Ret) :- ','(fact(N, NFact), ','(fact(K, KFact), ','(is(NMinK, -(N, K)), ','(fact(NMinK, NMinKFact), is(Ret, //(NFact, *(KFact, NMinKFact))))))). fact(N, 1) :- =<(N, 0). fact(N, Ret) :- ','(>(N, 0), ','(is(NRec, -(N, 1)), ','(fact(NRec, RetRec), is(Ret, *(RetRec, N))))). Query: binomial(g,g,a) ---------------------------------------- (1) PrologToIRSwTTransformerProof (SOUND) Transformed Prolog program to IRSwT according to method in Master Thesis of A. Weinert { "root": 2, "program": { "directives": [], "clauses": [ [ "(binomial N K Ret)", "(',' (fact N NFact) (',' (fact K KFact) (',' (is NMinK (- N K)) (',' (fact NMinK NMinKFact) (is Ret (// NFact (* KFact NMinKFact)))))))" ], [ "(fact N (1))", "(=< N (0))" ], [ "(fact N Ret)", "(',' (> N (0)) (',' (is NRec (- N (1))) (',' (fact NRec RetRec) (is Ret (* RetRec N)))))" ] ] }, "graph": { "nodes": { "2199": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [{ "lhs": { "name": "T23", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "type": "PlainIntegerConstant", "value": "0" }, "operation": ">" }] }, "ground": ["T23"], "free": [], "exprvars": ["T23"] } }, "2232": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (> T26 (0)) (',' (is X36 (- T26 (1))) (',' (fact X36 X37) (is X38 (* X37 T26)))))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T26"], "free": [ "X38", "X36", "X37" ], "exprvars": [] } }, "2198": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [{ "lhs": { "name": "T23", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "type": "PlainIntegerConstant", "value": "0" }, "operation": "<=" }] }, "ground": ["T23"], "free": [], "exprvars": ["T23"] } }, "type": "Nodes", "2405": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (is X36 (- T26 (1))) (',' (fact X36 X37) (is X38 (* X37 T26))))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [{ "lhs": { "type": "PlainIntegerConstant", "value": "0" }, "type": "PlainIntegerRelation", "rhs": { "name": "T26", "type": "PlainIntegerVariable" }, "operation": "<" }] }, "ground": ["T26"], "free": [ "X38", "X36", "X37" ], "exprvars": ["T26"] } }, "2422": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [{ "lhs": { "name": "T39", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "name": "T17", "type": "PlainIntegerVariable" }, { "arguments": [ { "name": "T33", "type": "PlainIntegerVariable" }, { "name": "T37", "type": "PlainIntegerVariable" } ], "type": "PlainIntegerOperation", "operation": "*" } ], "type": "PlainIntegerOperation", "operation": "//t" }, "operation": "=" }] }, "ground": [], "free": [], "exprvars": [ "T39", "T17", "T33", "T37" ] } }, "2421": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T17", "T33", "T37" ], "free": [], "exprvars": [ "T17", "T33", "T37" ] } }, "2200": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [{ "lhs": { "name": "T23", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "type": "PlainIntegerConstant", "value": "0" }, "operation": "<=" }] }, "ground": [], "free": [], "exprvars": ["T23"] } }, "2420": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [{ "lhs": { "name": "T39", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "name": "T17", "type": "PlainIntegerVariable" }, { "arguments": [ { "name": "T33", "type": "PlainIntegerVariable" }, { "name": "T37", "type": "PlainIntegerVariable" } ], "type": "PlainIntegerOperation", "operation": "*" } ], "type": "PlainIntegerOperation", "operation": "//t" }, "operation": "=" }] }, "ground": [ "T17", "T39", "T33", "T37" ], "free": [], "exprvars": [ "T39", "T17", "T33", "T37" ] } }, "2409": { "goal": [{ "clause": -1, "scope": -1, "term": "(is X38 (* T29 T26))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T26", "T29" ], "free": ["X38"], "exprvars": [] } }, "2408": { "goal": [{ "clause": -1, "scope": -1, "term": "(fact T27 X37)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [ { "lhs": { "name": "T27", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "name": "T26", "type": "PlainIntegerVariable" }, { "type": "PlainIntegerConstant", "value": "1" } ], "type": "PlainIntegerOperation", "operation": "-" }, "operation": "=" }, { "lhs": { "type": "PlainIntegerConstant", "value": "0" }, "type": "PlainIntegerRelation", "rhs": { "name": "T26", "type": "PlainIntegerVariable" }, "operation": "<" } ] }, "ground": ["T27"], "free": ["X37"], "exprvars": [ "T27", "T26" ] } }, "2407": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (fact T27 X37) (is X38 (* X37 T26)))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [ { "lhs": { "name": "T27", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "name": "T26", "type": "PlainIntegerVariable" }, { "type": "PlainIntegerConstant", "value": "1" } ], "type": "PlainIntegerOperation", "operation": "-" }, "operation": "=" }, { "lhs": { "type": "PlainIntegerConstant", "value": "0" }, "type": "PlainIntegerRelation", "rhs": { "name": "T26", "type": "PlainIntegerVariable" }, "operation": "<" } ] }, "ground": [ "T27", "T26" ], "free": [ "X38", "X36", "X37" ], "exprvars": [ "T27", "T26" ] } }, "10": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (fact T12 X15) (',' (fact T13 X16) (',' (is X17 (- T12 T13)) (',' (fact X17 X18) (is T15 (// X15 (* X16 X18)))))))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T12", "T13" ], "free": [ "X15", "X16", "X17", "X18" ], "exprvars": [] } }, "2406": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [{ "lhs": { "type": "PlainIntegerConstant", "value": "0" }, "type": "PlainIntegerRelation", "rhs": { "name": "T26", "type": "PlainIntegerVariable" }, "operation": ">=" }] }, "ground": ["T26"], "free": [ "X38", "X36", "X37" ], "exprvars": ["T26"] } }, "15": { "goal": [{ "clause": -1, "scope": -1, "term": "(fact T12 X15)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T12"], "free": ["X15"], "exprvars": [] } }, "16": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (fact T13 X16) (',' (is X17 (- T12 T13)) (',' (fact X17 X18) (is T15 (// T17 (* X16 X18))))))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T12", "T13", "T17" ], "free": [ "X16", "X17", "X18" ], "exprvars": [] } }, "17": { "goal": [ { "clause": 1, "scope": 2, "term": "(fact T12 X15)" }, { "clause": 2, "scope": 2, "term": "(fact T12 X15)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T12"], "free": ["X15"], "exprvars": [] } }, "18": { "goal": [{ "clause": 1, "scope": 2, "term": "(fact T12 X15)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T12"], "free": ["X15"], "exprvars": [] } }, "19": { "goal": [{ "clause": 2, "scope": 2, "term": "(fact T12 X15)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T12"], "free": ["X15"], "exprvars": [] } }, "2416": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (fact T35 X18) (is T15 (// T17 (* T33 X18))))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [{ "lhs": { "name": "T35", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "name": "T12", "type": "PlainIntegerVariable" }, { "name": "T13", "type": "PlainIntegerVariable" } ], "type": "PlainIntegerOperation", "operation": "-" }, "operation": "=" }] }, "ground": [ "T13", "T35", "T12", "T17", "T33" ], "free": [ "X17", "X18" ], "exprvars": [ "T35", "T13", "T12" ] } }, "2415": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "2": { "goal": [{ "clause": -1, "scope": -1, "term": "(binomial T1 T2 T3)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T1", "T2" ], "free": [], "exprvars": [] } }, "2414": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (is X17 (- T12 T13)) (',' (fact X17 X18) (is T15 (// T17 (* T33 X18)))))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T12", "T13", "T17", "T33" ], "free": [ "X17", "X18" ], "exprvars": [] } }, "2413": { "goal": [{ "clause": -1, "scope": -1, "term": "(fact T13 X16)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T13"], "free": ["X16"], "exprvars": [] } }, "2412": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [{ "lhs": { "name": "T31", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "name": "T29", "type": "PlainIntegerVariable" }, { "name": "T26", "type": "PlainIntegerVariable" } ], "type": "PlainIntegerOperation", "operation": "*" }, "operation": "=" }] }, "ground": [], "free": [], "exprvars": [ "T31", "T29", "T26" ] } }, "2411": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [{ "lhs": { "name": "T31", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "name": "T29", "type": "PlainIntegerVariable" }, { "name": "T26", "type": "PlainIntegerVariable" } ], "type": "PlainIntegerOperation", "operation": "*" }, "operation": "=" }] }, "ground": [ "T31", "T29", "T26" ], "free": ["X38"], "exprvars": [ "T31", "T29", "T26" ] } }, "6": { "goal": [{ "clause": 0, "scope": 1, "term": "(binomial T1 T2 T3)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T1", "T2" ], "free": [], "exprvars": [] } }, "2410": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "2233": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "2419": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "20": { "goal": [{ "clause": -1, "scope": -1, "term": "(=< T23 (0))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T23"], "free": [], "exprvars": [] } }, "2418": { "goal": [{ "clause": -1, "scope": -1, "term": "(is T15 (// T17 (* T33 T37)))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T17", "T33", "T37" ], "free": [], "exprvars": [] } }, "21": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "2417": { "goal": [{ "clause": -1, "scope": -1, "term": "(fact T35 X18)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [{ "lhs": { "name": "T35", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "name": "T12", "type": "PlainIntegerVariable" }, { "name": "T13", "type": "PlainIntegerVariable" } ], "type": "PlainIntegerOperation", "operation": "-" }, "operation": "=" }] }, "ground": ["T35"], "free": ["X18"], "exprvars": [ "T35", "T13", "T12" ] } } }, "edges": [ { "from": 2, "to": 6, "label": "CASE" }, { "from": 6, "to": 10, "label": "ONLY EVAL with clause\nbinomial(X12, X13, X14) :- ','(fact(X12, X15), ','(fact(X13, X16), ','(is(X17, -(X12, X13)), ','(fact(X17, X18), is(X14, //(X15, *(X16, X18))))))).\nand substitutionT1 -> T12,\nX12 -> T12,\nT2 -> T13,\nX13 -> T13,\nT3 -> T15,\nX14 -> T15,\nT14 -> T15" }, { "from": 10, "to": 15, "label": "SPLIT 1" }, { "from": 10, "to": 16, "label": "SPLIT 2\nnew knowledge:\nT12 is ground\nT17 is ground\nreplacements:X15 -> T17" }, { "from": 15, "to": 17, "label": "CASE" }, { "from": 16, "to": 2413, "label": "SPLIT 1" }, { "from": 16, "to": 2414, "label": "SPLIT 2\nnew knowledge:\nT13 is ground\nT33 is ground\nreplacements:X16 -> T33" }, { "from": 17, "to": 18, "label": "PARALLEL" }, { "from": 17, "to": 19, "label": "PARALLEL" }, { "from": 18, "to": 20, "label": "ONLY EVAL with clause\nfact(X25, 1) :- =<(X25, 0).\nand substitutionT12 -> T23,\nX25 -> T23,\nX15 -> 1" }, { "from": 19, "to": 2232, "label": "ONLY EVAL with clause\nfact(X34, X35) :- ','(>(X34, 0), ','(is(X36, -(X34, 1)), ','(fact(X36, X37), is(X35, *(X37, X34))))).\nand substitutionT12 -> T26,\nX34 -> T26,\nX15 -> X38,\nX35 -> X38" }, { "from": 20, "to": 21, "label": "IS ERROR" }, { "from": 20, "to": 2198, "label": "ARITHCOMP SUCCESS" }, { "from": 20, "to": 2199, "label": "ARITHCOMP FAIL" }, { "from": 2198, "to": 2200, "label": "SUCCESS" }, { "from": 2232, "to": 2233, "label": "IS ERROR" }, { "from": 2232, "to": 2405, "label": "ARITHCOMP SUCCESS" }, { "from": 2232, "to": 2406, "label": "ARITHCOMP FAIL" }, { "from": 2405, "to": 2407, "label": "\nX36 -> T27" }, { "from": 2407, "to": 2408, "label": "SPLIT 1" }, { "from": 2407, "to": 2409, "label": "SPLIT 2\nnew knowledge:\nT27 is ground\nT29 is ground\nreplacements:X37 -> T29" }, { "from": 2408, "to": 15, "label": "INSTANCE with matching:\nT12 -> T27\nX15 -> X37" }, { "from": 2409, "to": 2410, "label": "IS ERROR" }, { "from": 2409, "to": 2411, "label": "\nX38 -> T31" }, { "from": 2411, "to": 2412, "label": "SUCCESS" }, { "from": 2413, "to": 15, "label": "INSTANCE with matching:\nT12 -> T13\nX15 -> X16" }, { "from": 2414, "to": 2415, "label": "IS ERROR" }, { "from": 2414, "to": 2416, "label": "\nX17 -> T35" }, { "from": 2416, "to": 2417, "label": "SPLIT 1" }, { "from": 2416, "to": 2418, "label": "SPLIT 2\nnew knowledge:\nT35 is ground\nT37 is ground\nreplacements:X18 -> T37" }, { "from": 2417, "to": 15, "label": "INSTANCE with matching:\nT12 -> T35\nX15 -> X18" }, { "from": 2418, "to": 2419, "label": "IS ERROR" }, { "from": 2418, "to": 2420, "label": "\nT15 -> T39" }, { "from": 2418, "to": 2421, "label": "IS FAIL" }, { "from": 2420, "to": 2422, "label": "SUCCESS" } ], "type": "Graph" } } ---------------------------------------- (2) Obligation: Rules: f19_in(T26) -> f2232_in(T26) :|: TRUE f2232_out(x) -> f19_out(x) :|: TRUE f2409_out(x1, x2) -> f2407_out(x3, x2) :|: TRUE f2407_in(x4, x5) -> f2408_in(x4) :|: TRUE f2408_out(x6) -> f2409_in(x7, x8) :|: TRUE f18_out(T12) -> f17_out(T12) :|: TRUE f17_in(x9) -> f19_in(x9) :|: TRUE f17_in(x10) -> f18_in(x10) :|: TRUE f19_out(x11) -> f17_out(x11) :|: TRUE f17_out(x12) -> f15_out(x12) :|: TRUE f15_in(x13) -> f17_in(x13) :|: TRUE f15_out(T27) -> f2408_out(T27) :|: TRUE f2408_in(x14) -> f15_in(x14) :|: TRUE f2232_in(x15) -> f2233_in :|: TRUE f2406_out(x16) -> f2232_out(x16) :|: x16 <= 0 f2232_in(x17) -> f2406_in(x17) :|: x17 <= 0 f2233_out -> f2232_out(x18) :|: TRUE f2405_out(x19) -> f2232_out(x19) :|: x19 > 0 f2232_in(x20) -> f2405_in(x20) :|: x20 > 0 f2407_out(x21, x22) -> f2405_out(x22) :|: TRUE f2405_in(x23) -> f2407_in(x24, x23) :|: x24 = x23 - 1 f2411_out(x25, x26, x27) -> f2409_out(x26, x27) :|: TRUE f2409_in(x28, x29) -> f2410_in :|: TRUE f2409_in(x30, x31) -> f2411_in(x32, x30, x31) :|: x32 = x30 * x31 f2410_out -> f2409_out(x33, x34) :|: TRUE f2411_in(x35, x36, x37) -> f2411_out(x35, x36, x37) :|: TRUE f6_out(T1, T2) -> f2_out(T1, T2) :|: TRUE f2_in(x38, x39) -> f6_in(x38, x39) :|: TRUE f10_out(x40, x41) -> f6_out(x40, x41) :|: TRUE f6_in(x42, x43) -> f10_in(x42, x43) :|: TRUE f10_in(x44, x45) -> f15_in(x44) :|: TRUE f15_out(x46) -> f16_in(x47, x46, x48) :|: TRUE f16_out(x49, x50, x51) -> f10_out(x50, x49) :|: TRUE f16_in(x52, x53, x54) -> f2413_in(x52) :|: TRUE f2413_out(x55) -> f2414_in(x56, x55, x57, x58) :|: TRUE f2414_out(x59, x60, x61, x62) -> f16_out(x60, x59, x61) :|: TRUE f2413_in(T13) -> f15_in(T13) :|: TRUE f15_out(x63) -> f2413_out(x63) :|: TRUE f2414_in(x64, x65, x66, x67) -> f2416_in(x68, x66, x67, x65, x64) :|: x68 = x64 - x65 f2416_out(x69, x70, x71, x72, x73) -> f2414_out(x73, x72, x70, x71) :|: TRUE f2415_out -> f2414_out(x74, x75, x76, x77) :|: TRUE f2414_in(x78, x79, x80, x81) -> f2415_in :|: TRUE f2416_in(x82, x83, x84, x85, x86) -> f2417_in(x82) :|: TRUE f2417_out(T35) -> f2418_in(T17, T33, T37) :|: TRUE f2418_out(x87, x88, x89) -> f2416_out(x90, x87, x88, x91, x92) :|: TRUE f15_out(x93) -> f2417_out(x93) :|: TRUE f2417_in(x94) -> f15_in(x94) :|: TRUE Start term: f2_in(T1, T2) ---------------------------------------- (3) IRSwTSimpleDependencyGraphProof (EQUIVALENT) Constructed simple dependency graph. Simplified to the following IRSwTs: intTRSProblem: f19_in(T26) -> f2232_in(T26) :|: TRUE f2407_in(x4, x5) -> f2408_in(x4) :|: TRUE f17_in(x9) -> f19_in(x9) :|: TRUE f15_in(x13) -> f17_in(x13) :|: TRUE f2408_in(x14) -> f15_in(x14) :|: TRUE f2232_in(x20) -> f2405_in(x20) :|: x20 > 0 f2405_in(x23) -> f2407_in(x24, x23) :|: x24 = x23 - 1 ---------------------------------------- (4) Obligation: Rules: f19_in(T26) -> f2232_in(T26) :|: TRUE f2407_in(x4, x5) -> f2408_in(x4) :|: TRUE f17_in(x9) -> f19_in(x9) :|: TRUE f15_in(x13) -> f17_in(x13) :|: TRUE f2408_in(x14) -> f15_in(x14) :|: TRUE f2232_in(x20) -> f2405_in(x20) :|: x20 > 0 f2405_in(x23) -> f2407_in(x24, x23) :|: x24 = x23 - 1 ---------------------------------------- (5) IntTRSCompressionProof (EQUIVALENT) Compressed rules. ---------------------------------------- (6) Obligation: Rules: f2407_in(x4:0, x5:0) -> f2407_in(x4:0 - 1, x4:0) :|: x4:0 > 0 ---------------------------------------- (7) IRSFormatTransformerProof (EQUIVALENT) Reformatted IRS to match normalized format (transformed away non-linear left-hand sides, !=, / and %). ---------------------------------------- (8) Obligation: Rules: f2407_in(x4:0, x5:0) -> f2407_in(arith, x4:0) :|: x4:0 > 0 && arith = x4:0 - 1 ---------------------------------------- (9) IRSwTTerminationDigraphProof (EQUIVALENT) Constructed termination digraph! Nodes: (1) f2407_in(x4:0, x5:0) -> f2407_in(arith, x4:0) :|: x4:0 > 0 && arith = x4:0 - 1 Arcs: (1) -> (1) This digraph is fully evaluated! ---------------------------------------- (10) Obligation: Termination digraph: Nodes: (1) f2407_in(x4:0, x5:0) -> f2407_in(arith, x4:0) :|: x4:0 > 0 && arith = x4:0 - 1 Arcs: (1) -> (1) This digraph is fully evaluated! ---------------------------------------- (11) IntTRSCompressionProof (EQUIVALENT) Compressed rules. ---------------------------------------- (12) Obligation: Rules: f2407_in(x4:0:0, x5:0:0) -> f2407_in(x4:0:0 - 1, x4:0:0) :|: x4:0:0 > 0 ---------------------------------------- (13) IntTRSUnneededArgumentFilterProof (EQUIVALENT) Some arguments are removed because they cannot influence termination. We removed arguments according to the following replacements: f2407_in(x1, x2) -> f2407_in(x1) ---------------------------------------- (14) Obligation: Rules: f2407_in(x4:0:0) -> f2407_in(x4:0:0 - 1) :|: x4:0:0 > 0 ---------------------------------------- (15) TempFilterProof (SOUND) Used the following sort dictionary for filtering: f2407_in(INTEGER) Replaced non-predefined constructor symbols by 0. ---------------------------------------- (16) Obligation: Rules: f2407_in(x4:0:0) -> f2407_in(c) :|: c = x4:0:0 - 1 && x4:0:0 > 0 ---------------------------------------- (17) PolynomialOrderProcessor (EQUIVALENT) Found the following polynomial interpretation: [f2407_in(x)] = x The following rules are decreasing: f2407_in(x4:0:0) -> f2407_in(c) :|: c = x4:0:0 - 1 && x4:0:0 > 0 The following rules are bounded: f2407_in(x4:0:0) -> f2407_in(c) :|: c = x4:0:0 - 1 && x4:0:0 > 0 ---------------------------------------- (18) YES