/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 decode(g,a) w.r.t. the given Prolog program could successfully be proven: (0) Prolog (1) PrologToIRSwTTransformerProof [SOUND, 21 ms] (2) IRSwT (3) IRSwTSimpleDependencyGraphProof [EQUIVALENT, 0 ms] (4) IRSwT (5) IntTRSCompressionProof [EQUIVALENT, 58 ms] (6) IRSwT (7) IRSFormatTransformerProof [EQUIVALENT, 0 ms] (8) IRSwT (9) IRSwTTerminationDigraphProof [EQUIVALENT, 41 ms] (10) IRSwT (11) IntTRSCompressionProof [EQUIVALENT, 0 ms] (12) IRSwT (13) TempFilterProof [SOUND, 172 ms] (14) IRSwT (15) IRSwTTerminationDigraphProof [EQUIVALENT, 0 ms] (16) IRSwT (17) IRSwTOrderProof [EQUIVALENT, 15 ms] (18) YES ---------------------------------------- (0) Obligation: Clauses: decode([], []). decode(.(X, Ys), .(X, Zs)) :- ','(\+(is_list(X)), decode(Ys, Zs)). decode(.(.(1, .(X, [])), Ys), .(X, Zs)) :- decode(Ys, Zs). decode(.(.(N, .(X, [])), Ys), .(X, Zs)) :- ','(>(N, 1), ','(is(N1, -(N, 1)), decode(.(.(N1, .(X, [])), Ys), Zs))). Query: decode(g,a) ---------------------------------------- (1) PrologToIRSwTTransformerProof (SOUND) Transformed Prolog program to IRSwT according to method in Master Thesis of A. Weinert { "root": 3, "program": { "directives": [], "clauses": [ [ "(decode ([]) ([]))", null ], [ "(decode (. X Ys) (. X Zs))", "(',' (\\+ (is_list X)) (decode Ys Zs))" ], [ "(decode (. (. (1) (. X ([]))) Ys) (. X Zs))", "(decode Ys Zs)" ], [ "(decode (. (. N (. X ([]))) Ys) (. X Zs))", "(',' (> N (1)) (',' (is N1 (- N (1))) (decode (. (. N1 (. X ([]))) Ys) Zs)))" ] ] }, "graph": { "nodes": { "46": { "goal": [{ "clause": 2, "scope": 1, "term": "(decode T1 T2)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T1"], "free": [], "exprvars": [] } }, "25": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "47": { "goal": [{ "clause": 3, "scope": 1, "term": "(decode T1 T2)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T1"], "free": [], "exprvars": [] } }, "26": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "49": { "goal": [{ "clause": -1, "scope": -1, "term": "(decode T32 T34)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T32"], "free": [], "exprvars": [] } }, "28": { "goal": [{ "clause": 1, "scope": 1, "term": "(decode T1 T2)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T1"], "free": [], "exprvars": [] } }, "type": "Nodes", "2103": { "goal": [{ "clause": -1, "scope": -1, "term": "(decode (. (. T48 (. T44 ([]))) T45) T47)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [ { "lhs": { "name": "T48", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "name": "T43", "type": "PlainIntegerVariable" }, { "type": "PlainIntegerConstant", "value": "1" } ], "type": "PlainIntegerOperation", "operation": "-" }, "operation": "=" }, { "lhs": { "type": "PlainIntegerConstant", "value": "1" }, "type": "PlainIntegerRelation", "rhs": { "name": "T43", "type": "PlainIntegerVariable" }, "operation": "<" } ] }, "ground": [ "T45", "T44", "T43", "T48" ], "free": ["X44"], "exprvars": [ "T43", "T48" ] } }, "2102": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [{ "lhs": { "type": "PlainIntegerConstant", "value": "1" }, "type": "PlainIntegerRelation", "rhs": { "name": "T43", "type": "PlainIntegerVariable" }, "operation": ">=" }] }, "ground": [ "T45", "T44", "T43" ], "free": ["X44"], "exprvars": ["T43"] } }, "2101": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (is X44 (- T43 (1))) (decode (. (. X44 (. T44 ([]))) T45) T47))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [{ "lhs": { "type": "PlainIntegerConstant", "value": "1" }, "type": "PlainIntegerRelation", "rhs": { "name": "T43", "type": "PlainIntegerVariable" }, "operation": "<" }] }, "ground": [ "T45", "T44", "T43" ], "free": ["X44"], "exprvars": ["T43"] } }, "50": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "30": { "goal": [ { "clause": 2, "scope": 1, "term": "(decode T1 T2)" }, { "clause": 3, "scope": 1, "term": "(decode T1 T2)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T1"], "free": [], "exprvars": [] } }, "11": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "77": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (> T43 (1)) (',' (is X44 (- T43 (1))) (decode (. (. X44 (. T44 ([]))) T45) T47)))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T43", "T44", "T45" ], "free": ["X44"], "exprvars": [] } }, "78": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "35": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (\\+ (is_list T15)) (decode T16 T18))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T15", "T16" ], "free": [], "exprvars": [] } }, "79": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "36": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "37": { "goal": [ { "clause": -1, "scope": -1, "term": "(',' (call (is_list T15)) (',' (!_2) (fail)))" }, { "clause": -1, "scope": -1, "term": "(decode T16 T18)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T15", "T16" ], "free": [], "exprvars": [] } }, "39": { "goal": [ { "clause": -1, "scope": -1, "term": "(',' (is_list T15) (',' (!_2) (fail)))" }, { "clause": -1, "scope": 3, "term": null }, { "clause": -1, "scope": -1, "term": "(decode T16 T18)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T15", "T16" ], "free": [], "exprvars": [] } }, "3": { "goal": [{ "clause": -1, "scope": -1, "term": "(decode T1 T2)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T1"], "free": [], "exprvars": [] } }, "5": { "goal": [ { "clause": 0, "scope": 1, "term": "(decode T1 T2)" }, { "clause": 1, "scope": 1, "term": "(decode T1 T2)" }, { "clause": 2, "scope": 1, "term": "(decode T1 T2)" }, { "clause": 3, "scope": 1, "term": "(decode T1 T2)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T1"], "free": [], "exprvars": [] } }, "7": { "goal": [{ "clause": 0, "scope": 1, "term": "(decode T1 T2)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T1"], "free": [], "exprvars": [] } }, "8": { "goal": [ { "clause": 1, "scope": 1, "term": "(decode T1 T2)" }, { "clause": 2, "scope": 1, "term": "(decode T1 T2)" }, { "clause": 3, "scope": 1, "term": "(decode T1 T2)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T1"], "free": [], "exprvars": [] } }, "40": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } } }, "edges": [ { "from": 3, "to": 5, "label": "CASE" }, { "from": 5, "to": 7, "label": "PARALLEL" }, { "from": 5, "to": 8, "label": "PARALLEL" }, { "from": 7, "to": 11, "label": "EVAL with clause\ndecode([], []).\nand substitutionT1 -> [],\nT2 -> []" }, { "from": 7, "to": 25, "label": "EVAL-BACKTRACK" }, { "from": 8, "to": 28, "label": "PARALLEL" }, { "from": 8, "to": 30, "label": "PARALLEL" }, { "from": 11, "to": 26, "label": "SUCCESS" }, { "from": 28, "to": 35, "label": "EVAL with clause\ndecode(.(X13, X14), .(X13, X15)) :- ','(\\+(is_list(X13)), decode(X14, X15)).\nand substitutionX13 -> T15,\nX14 -> T16,\nT1 -> .(T15, T16),\nX15 -> T18,\nT2 -> .(T15, T18),\nT17 -> T18" }, { "from": 28, "to": 36, "label": "EVAL-BACKTRACK" }, { "from": 30, "to": 46, "label": "PARALLEL" }, { "from": 30, "to": 47, "label": "PARALLEL" }, { "from": 35, "to": 37, "label": "NOT" }, { "from": 37, "to": 39, "label": "CALL" }, { "from": 39, "to": 40, "label": "UNDEFINED ERROR" }, { "from": 46, "to": 49, "label": "EVAL with clause\ndecode(.(.(1, .(X28, [])), X29), .(X28, X30)) :- decode(X29, X30).\nand substitutionX28 -> T31,\nX29 -> T32,\nT1 -> .(.(1, .(T31, [])), T32),\nX30 -> T34,\nT2 -> .(T31, T34),\nT33 -> T34" }, { "from": 46, "to": 50, "label": "EVAL-BACKTRACK" }, { "from": 47, "to": 77, "label": "EVAL with clause\ndecode(.(.(X40, .(X41, [])), X42), .(X41, X43)) :- ','(>(X40, 1), ','(is(X44, -(X40, 1)), decode(.(.(X44, .(X41, [])), X42), X43))).\nand substitutionX40 -> T43,\nX41 -> T44,\nX42 -> T45,\nT1 -> .(.(T43, .(T44, [])), T45),\nX43 -> T47,\nT2 -> .(T44, T47),\nT46 -> T47" }, { "from": 47, "to": 78, "label": "EVAL-BACKTRACK" }, { "from": 49, "to": 3, "label": "INSTANCE with matching:\nT1 -> T32\nT2 -> T34" }, { "from": 77, "to": 79, "label": "IS ERROR" }, { "from": 77, "to": 2101, "label": "ARITHCOMP SUCCESS" }, { "from": 77, "to": 2102, "label": "ARITHCOMP FAIL" }, { "from": 2101, "to": 2103, "label": "\nX44 -> T48" }, { "from": 2103, "to": 3, "label": "INSTANCE with matching:\nT1 -> .(.(T48, .(T44, [])), T45)\nT2 -> T47" } ], "type": "Graph" } } ---------------------------------------- (2) Obligation: Rules: f2101_in(T43, T44, T45) -> f2103_in(T48, T44, T45, T43) :|: T48 = T43 - 1 f2103_out(x, x1, x2, x3) -> f2101_out(x3, x1, x2) :|: TRUE f78_out -> f47_out(T1) :|: TRUE f47_in(.(.(x4, .(x5, [])), x6)) -> f77_in(x4, x5, x6) :|: TRUE f47_in(x7) -> f78_in :|: TRUE f77_out(x8, x9, x10) -> f47_out(.(.(x8, .(x9, [])), x10)) :|: TRUE f3_out(T32) -> f49_out(T32) :|: TRUE f49_in(x11) -> f3_in(x11) :|: TRUE f77_in(x12, x13, x14) -> f79_in :|: TRUE f77_in(x15, x16, x17) -> f2101_in(x15, x16, x17) :|: x15 > 1 f77_in(x18, x19, x20) -> f2102_in(x20, x19, x18) :|: x18 <= 1 f2101_out(x21, x22, x23) -> f77_out(x21, x22, x23) :|: x21 > 1 f2102_out(x24, x25, x26) -> f77_out(x26, x25, x24) :|: x26 <= 1 f79_out -> f77_out(x27, x28, x29) :|: TRUE f3_out(.(.(x30, .(x31, [])), x32)) -> f2103_out(x30, x31, x32, x33) :|: TRUE f2103_in(x34, x35, x36, x37) -> f3_in(.(.(x34, .(x35, [])), x36)) :|: TRUE f8_in(x38) -> f28_in(x38) :|: TRUE f30_out(x39) -> f8_out(x39) :|: TRUE f28_out(x40) -> f8_out(x40) :|: TRUE f8_in(x41) -> f30_in(x41) :|: TRUE f7_out(x42) -> f5_out(x42) :|: TRUE f5_in(x43) -> f7_in(x43) :|: TRUE f5_in(x44) -> f8_in(x44) :|: TRUE f8_out(x45) -> f5_out(x45) :|: TRUE f5_out(x46) -> f3_out(x46) :|: TRUE f3_in(x47) -> f5_in(x47) :|: TRUE f47_out(x48) -> f30_out(x48) :|: TRUE f30_in(x49) -> f46_in(x49) :|: TRUE f46_out(x50) -> f30_out(x50) :|: TRUE f30_in(x51) -> f47_in(x51) :|: TRUE f49_out(x52) -> f46_out(.(.(1, .(x53, [])), x52)) :|: TRUE f46_in(x54) -> f50_in :|: TRUE f46_in(.(.(1, .(x55, [])), x56)) -> f49_in(x56) :|: TRUE f50_out -> f46_out(x57) :|: TRUE Start term: f3_in(T1) ---------------------------------------- (3) IRSwTSimpleDependencyGraphProof (EQUIVALENT) Constructed simple dependency graph. Simplified to the following IRSwTs: intTRSProblem: f2101_in(T43, T44, T45) -> f2103_in(T48, T44, T45, T43) :|: T48 = T43 - 1 f47_in(.(.(x4, .(x5, [])), x6)) -> f77_in(x4, x5, x6) :|: TRUE f49_in(x11) -> f3_in(x11) :|: TRUE f77_in(x15, x16, x17) -> f2101_in(x15, x16, x17) :|: x15 > 1 f2103_in(x34, x35, x36, x37) -> f3_in(.(.(x34, .(x35, [])), x36)) :|: TRUE f8_in(x41) -> f30_in(x41) :|: TRUE f5_in(x44) -> f8_in(x44) :|: TRUE f3_in(x47) -> f5_in(x47) :|: TRUE f30_in(x49) -> f46_in(x49) :|: TRUE f30_in(x51) -> f47_in(x51) :|: TRUE f46_in(.(.(1, .(x55, [])), x56)) -> f49_in(x56) :|: TRUE ---------------------------------------- (4) Obligation: Rules: f2101_in(T43, T44, T45) -> f2103_in(T48, T44, T45, T43) :|: T48 = T43 - 1 f47_in(.(.(x4, .(x5, [])), x6)) -> f77_in(x4, x5, x6) :|: TRUE f49_in(x11) -> f3_in(x11) :|: TRUE f77_in(x15, x16, x17) -> f2101_in(x15, x16, x17) :|: x15 > 1 f2103_in(x34, x35, x36, x37) -> f3_in(.(.(x34, .(x35, [])), x36)) :|: TRUE f8_in(x41) -> f30_in(x41) :|: TRUE f5_in(x44) -> f8_in(x44) :|: TRUE f3_in(x47) -> f5_in(x47) :|: TRUE f30_in(x49) -> f46_in(x49) :|: TRUE f30_in(x51) -> f47_in(x51) :|: TRUE f46_in(.(.(1, .(x55, [])), x56)) -> f49_in(x56) :|: TRUE ---------------------------------------- (5) IntTRSCompressionProof (EQUIVALENT) Compressed rules. ---------------------------------------- (6) Obligation: Rules: f5_in(.(.(x4:0, .(x5:0, [])), x6:0)) -> f5_in(.(.(x4:0 - 1, .(x5:0, [])), x6:0)) :|: x4:0 > 1 f5_in(.(.(cons_1, .(x55:0, [])), x56:0)) -> f5_in(x56:0) :|: TRUE && cons_1 = 1 ---------------------------------------- (7) IRSFormatTransformerProof (EQUIVALENT) Reformatted IRS to match normalized format (transformed away non-linear left-hand sides, !=, / and %). ---------------------------------------- (8) Obligation: Rules: f5_in(.(.(x4:0, .(x5:0, [])), x6:0)) -> f5_in(.(.(arith, .(x5:0, [])), x6:0)) :|: x4:0 > 1 && arith = x4:0 - 1 f5_in(.(.(cons_1, .(x55:0, [])), x56:0)) -> f5_in(x56:0) :|: TRUE && cons_1 = 1 ---------------------------------------- (9) IRSwTTerminationDigraphProof (EQUIVALENT) Constructed termination digraph! Nodes: (1) f5_in(.(.(x4:0, .(x5:0, [])), x6:0)) -> f5_in(.(.(arith, .(x5:0, [])), x6:0)) :|: x4:0 > 1 && arith = x4:0 - 1 (2) f5_in(.(.(cons_1, .(x55:0, [])), x56:0)) -> f5_in(x56:0) :|: TRUE && cons_1 = 1 Arcs: (1) -> (1), (2) (2) -> (1), (2) This digraph is fully evaluated! ---------------------------------------- (10) Obligation: Termination digraph: Nodes: (1) f5_in(.(.(x4:0, .(x5:0, [])), x6:0)) -> f5_in(.(.(arith, .(x5:0, [])), x6:0)) :|: x4:0 > 1 && arith = x4:0 - 1 (2) f5_in(.(.(cons_1, .(x55:0, [])), x56:0)) -> f5_in(x56:0) :|: TRUE && cons_1 = 1 Arcs: (1) -> (1), (2) (2) -> (1), (2) This digraph is fully evaluated! ---------------------------------------- (11) IntTRSCompressionProof (EQUIVALENT) Compressed rules. ---------------------------------------- (12) Obligation: Rules: f5_in(.(.(x4:0:0, .(x5:0:0, [])), x6:0:0)) -> f5_in(.(.(x4:0:0 - 1, .(x5:0:0, [])), x6:0:0)) :|: x4:0:0 > 1 f5_in(.(.(cons_1, .(x55:0:0, [])), x56:0:0)) -> f5_in(x56:0:0) :|: TRUE && cons_1 = 1 ---------------------------------------- (13) TempFilterProof (SOUND) Used the following sort dictionary for filtering: f5_in(VARIABLE) .(VARIABLE, VARIABLE) []() Removed predefined arithmetic.The following proof was generated: # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty Termination of the given IRSwT could not be shown: - IRSwT - IRSwTToQDPProof Rules: f5_in(.(.(x4:0:0, .(x5:0:0, [])), x6:0:0)) -> f5_in(.(.(predef, .(x5:0:0, [])), x6:0:0)) f5_in(.(.(predef, .(x55:0:0, [])), x56:0:0)) -> f5_in(x56:0:0) Removed the integers and created a QDP-Problem. - IRSwT - IRSwTToQDPProof - QDP - MRRProof Q DP problem: The TRS P consists of the following rules: f5_in(.(.(x4:0:0, .(x5:0:0, [])), x6:0:0)) -> f5_in(.(.(predef, .(x5:0:0, [])), x6:0:0)) f5_in(.(.(predef, .(x55:0:0, [])), x56:0:0)) -> f5_in(x56:0:0) R is empty. Q is empty. We have to consider all (P,Q,R)-chains. By using the rule removal processor [LPAR04] with the following ordering, at least one Dependency Pair or term rewrite system rule of this QDP problem can be strictly oriented. Strictly oriented dependency pairs: f5_in(.(.(predef, .(x55:0:0, [])), x56:0:0)) -> f5_in(x56:0:0) Used ordering: Polynomial interpretation [POLO]: POL(.(x_1, x_2)) = 1 + x_1 + x_2 POL([]) = 0 POL(f5_in(x_1)) = 2*x_1 POL(predef) = 0 - IRSwT - IRSwTToQDPProof - QDP - MRRProof - QDP Q DP problem: The TRS P consists of the following rules: f5_in(.(.(x4:0:0, .(x5:0:0, [])), x6:0:0)) -> f5_in(.(.(predef, .(x5:0:0, [])), x6:0:0)) R is empty. Q is empty. We have to consider all (P,Q,R)-chains. ---------------------------------------- (14) Obligation: Rules: f5_in(.(.(x4:0:0, .(x5:0:0, [])), x6:0:0)) -> f5_in(.(.(x4:0:0 - 1, .(x5:0:0, [])), x6:0:0)) :|: x4:0:0 > 1 ---------------------------------------- (15) IRSwTTerminationDigraphProof (EQUIVALENT) Constructed termination digraph! Nodes: (1) f5_in(.(.(x4:0:0, .(x5:0:0, [])), x6:0:0)) -> f5_in(.(.(x4:0:0 - 1, .(x5:0:0, [])), x6:0:0)) :|: x4:0:0 > 1 Arcs: (1) -> (1) This digraph is fully evaluated! ---------------------------------------- (16) Obligation: Termination digraph: Nodes: (1) f5_in(.(.(x4:0:0, .(x5:0:0, [])), x6:0:0)) -> f5_in(.(.(x4:0:0 - 1, .(x5:0:0, [])), x6:0:0)) :|: x4:0:0 > 1 Arcs: (1) -> (1) This digraph is fully evaluated! ---------------------------------------- (17) IRSwTOrderProof (EQUIVALENT) [f5_in(x)] = -8 + 4*x [.(x1, x2)] = 0 + 1*x1 + 0*x2 [[]()] = 0 The following rules are decreasing: f5_in(.(.(x4:0:0, .(x5:0:0, [])), x6:0:0)) -> f5_in(.(.(x4:0:0 - 1, .(x5:0:0, [])), x6:0:0)) :|: x4:0:0 > 1 The following rules are bounded: f5_in(.(.(x4:0:0, .(x5:0:0, [])), x6:0:0)) -> f5_in(.(.(x4:0:0 - 1, .(x5:0:0, [])), x6:0:0)) :|: x4:0:0 > 1 ---------------------------------------- (18) YES