/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: 794c25de1cacf0d048858bcd21c9a779e1221865 marcel 20200619 unpublished dirty Left Termination of the query pattern flat(g,a) w.r.t. the given Prolog program could successfully be proven: (0) Prolog (1) PrologToDTProblemTransformerProof [SOUND, 0 ms] (2) TRIPLES (3) TriplesToPiDPProof [SOUND, 0 ms] (4) PiDP (5) DependencyGraphProof [EQUIVALENT, 0 ms] (6) PiDP (7) PiDPToQDPProof [SOUND, 0 ms] (8) QDP (9) UsableRulesReductionPairsProof [EQUIVALENT, 11 ms] (10) QDP (11) MRRProof [EQUIVALENT, 0 ms] (12) QDP (13) PisEmptyProof [EQUIVALENT, 0 ms] (14) YES ---------------------------------------- (0) Obligation: Clauses: flat([], []). flat(.([], T), R) :- flat(T, R). flat(.(.(H, T), TT), .(H, R)) :- flat(.(T, TT), R). Query: flat(g,a) ---------------------------------------- (1) PrologToDTProblemTransformerProof (SOUND) Built DT problem from termination graph DT10. { "root": 2, "program": { "directives": [], "clauses": [ [ "(flat ([]) ([]))", null ], [ "(flat (. ([]) T) R)", "(flat T R)" ], [ "(flat (. (. H T) TT) (. H R))", "(flat (. T TT) R)" ] ] }, "graph": { "nodes": { "23": { "goal": [ { "clause": -1, "scope": -1, "term": "(true)" }, { "clause": 1, "scope": 1, "term": "(flat ([]) T2)" }, { "clause": 2, "scope": 1, "term": "(flat ([]) T2)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "type": "Nodes", "130": { "goal": [ { "clause": 2, "scope": 2, "term": "(flat T5 T7)" }, { "clause": -1, "scope": 2, "term": null }, { "clause": 2, "scope": 1, "term": "(flat (. ([]) T5) T2)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T5"], "free": [], "exprvars": [] } }, "131": { "goal": [{ "clause": -1, "scope": -1, "term": "(flat T16 T18)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T16"], "free": [], "exprvars": [] } }, "132": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "133": { "goal": [{ "clause": 2, "scope": 2, "term": "(flat T5 T7)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T5"], "free": [], "exprvars": [] } }, "134": { "goal": [ { "clause": -1, "scope": 2, "term": null }, { "clause": 2, "scope": 1, "term": "(flat (. ([]) T5) T2)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T5"], "free": [], "exprvars": [] } }, "135": { "goal": [{ "clause": -1, "scope": -1, "term": "(flat (. T36 T37) T39)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T36", "T37" ], "free": [], "exprvars": [] } }, "136": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "137": { "goal": [{ "clause": 2, "scope": 1, "term": "(flat (. ([]) T5) T2)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T5"], "free": [], "exprvars": [] } }, "138": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "117": { "goal": [ { "clause": 1, "scope": 1, "term": "(flat T1 T2)" }, { "clause": 2, "scope": 1, "term": "(flat T1 T2)" } ], "kb": { "nonunifying": [[ "(flat T1 T2)", "(flat ([]) ([]))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T1"], "free": [], "exprvars": [] } }, "139": { "goal": [{ "clause": -1, "scope": -1, "term": "(flat (. T45 T46) T48)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T45", "T46" ], "free": [], "exprvars": [] } }, "118": { "goal": [ { "clause": 1, "scope": 1, "term": "(flat ([]) T2)" }, { "clause": 2, "scope": 1, "term": "(flat ([]) T2)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "119": { "goal": [{ "clause": 2, "scope": 1, "term": "(flat ([]) T2)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "140": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "141": { "goal": [ { "clause": 0, "scope": 3, "term": "(flat (. T45 T46) T48)" }, { "clause": 1, "scope": 3, "term": "(flat (. T45 T46) T48)" }, { "clause": 2, "scope": 3, "term": "(flat (. T45 T46) T48)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T45", "T46" ], "free": [], "exprvars": [] } }, "120": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "142": { "goal": [ { "clause": 1, "scope": 3, "term": "(flat (. T45 T46) T48)" }, { "clause": 2, "scope": 3, "term": "(flat (. T45 T46) T48)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T45", "T46" ], "free": [], "exprvars": [] } }, "121": { "goal": [ { "clause": -1, "scope": -1, "term": "(flat T5 T7)" }, { "clause": 2, "scope": 1, "term": "(flat (. ([]) T5) T2)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T5"], "free": [], "exprvars": [] } }, "143": { "goal": [{ "clause": 1, "scope": 3, "term": "(flat (. T45 T46) T48)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T45", "T46" ], "free": [], "exprvars": [] } }, "122": { "goal": [{ "clause": 2, "scope": 1, "term": "(flat T1 T2)" }], "kb": { "nonunifying": [ [ "(flat T1 T2)", "(flat ([]) ([]))" ], [ "(flat T1 T2)", "(flat (. ([]) X9) X10)" ] ], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T1"], "free": [ "X9", "X10" ], "exprvars": [] } }, "144": { "goal": [{ "clause": 2, "scope": 3, "term": "(flat (. T45 T46) T48)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T45", "T46" ], "free": [], "exprvars": [] } }, "2": { "goal": [{ "clause": -1, "scope": -1, "term": "(flat T1 T2)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T1"], "free": [], "exprvars": [] } }, "123": { "goal": [ { "clause": 0, "scope": 2, "term": "(flat T5 T7)" }, { "clause": 1, "scope": 2, "term": "(flat T5 T7)" }, { "clause": 2, "scope": 2, "term": "(flat T5 T7)" }, { "clause": -1, "scope": 2, "term": null }, { "clause": 2, "scope": 1, "term": "(flat (. ([]) T5) T2)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T5"], "free": [], "exprvars": [] } }, "145": { "goal": [{ "clause": -1, "scope": -1, "term": "(flat T57 T59)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T57"], "free": [], "exprvars": [] } }, "124": { "goal": [{ "clause": 0, "scope": 2, "term": "(flat T5 T7)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T5"], "free": [], "exprvars": [] } }, "146": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "4": { "goal": [ { "clause": 0, "scope": 1, "term": "(flat T1 T2)" }, { "clause": 1, "scope": 1, "term": "(flat T1 T2)" }, { "clause": 2, "scope": 1, "term": "(flat T1 T2)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T1"], "free": [], "exprvars": [] } }, "125": { "goal": [ { "clause": 1, "scope": 2, "term": "(flat T5 T7)" }, { "clause": 2, "scope": 2, "term": "(flat T5 T7)" }, { "clause": -1, "scope": 2, "term": null }, { "clause": 2, "scope": 1, "term": "(flat (. ([]) T5) T2)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T5"], "free": [], "exprvars": [] } }, "147": { "goal": [{ "clause": -1, "scope": -1, "term": "(flat (. T69 T70) T72)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T69", "T70" ], "free": [], "exprvars": [] } }, "126": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "148": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "127": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "128": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "129": { "goal": [{ "clause": 1, "scope": 2, "term": "(flat T5 T7)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T5"], "free": [], "exprvars": [] } } }, "edges": [ { "from": 2, "to": 4, "label": "CASE" }, { "from": 4, "to": 23, "label": "EVAL with clause\nflat([], []).\nand substitutionT1 -> [],\nT2 -> []" }, { "from": 4, "to": 117, "label": "EVAL-BACKTRACK" }, { "from": 23, "to": 118, "label": "SUCCESS" }, { "from": 117, "to": 121, "label": "EVAL with clause\nflat(.([], X9), X10) :- flat(X9, X10).\nand substitutionX9 -> T5,\nT1 -> .([], T5),\nT2 -> T7,\nX10 -> T7,\nT6 -> T7" }, { "from": 117, "to": 122, "label": "EVAL-BACKTRACK" }, { "from": 118, "to": 119, "label": "BACKTRACK\nfor clause: flat(.([], T), R) :- flat(T, R)because of non-unification" }, { "from": 119, "to": 120, "label": "BACKTRACK\nfor clause: flat(.(.(H, T), TT), .(H, R)) :- flat(.(T, TT), R)because of non-unification" }, { "from": 121, "to": 123, "label": "CASE" }, { "from": 122, "to": 139, "label": "EVAL with clause\nflat(.(.(X49, X50), X51), .(X49, X52)) :- flat(.(X50, X51), X52).\nand substitutionX49 -> T44,\nX50 -> T45,\nX51 -> T46,\nT1 -> .(.(T44, T45), T46),\nX52 -> T48,\nT2 -> .(T44, T48),\nT47 -> T48" }, { "from": 122, "to": 140, "label": "EVAL-BACKTRACK" }, { "from": 123, "to": 124, "label": "PARALLEL" }, { "from": 123, "to": 125, "label": "PARALLEL" }, { "from": 124, "to": 126, "label": "EVAL with clause\nflat([], []).\nand substitutionT5 -> [],\nT7 -> []" }, { "from": 124, "to": 127, "label": "EVAL-BACKTRACK" }, { "from": 125, "to": 129, "label": "PARALLEL" }, { "from": 125, "to": 130, "label": "PARALLEL" }, { "from": 126, "to": 128, "label": "SUCCESS" }, { "from": 129, "to": 131, "label": "EVAL with clause\nflat(.([], X19), X20) :- flat(X19, X20).\nand substitutionX19 -> T16,\nT5 -> .([], T16),\nT7 -> T18,\nX20 -> T18,\nT17 -> T18" }, { "from": 129, "to": 132, "label": "EVAL-BACKTRACK" }, { "from": 130, "to": 133, "label": "PARALLEL" }, { "from": 130, "to": 134, "label": "PARALLEL" }, { "from": 131, "to": 2, "label": "INSTANCE with matching:\nT1 -> T16\nT2 -> T18" }, { "from": 133, "to": 135, "label": "EVAL with clause\nflat(.(.(X37, X38), X39), .(X37, X40)) :- flat(.(X38, X39), X40).\nand substitutionX37 -> T35,\nX38 -> T36,\nX39 -> T37,\nT5 -> .(.(T35, T36), T37),\nX40 -> T39,\nT7 -> .(T35, T39),\nT38 -> T39" }, { "from": 133, "to": 136, "label": "EVAL-BACKTRACK" }, { "from": 134, "to": 137, "label": "FAILURE" }, { "from": 135, "to": 2, "label": "INSTANCE with matching:\nT1 -> .(T36, T37)\nT2 -> T39" }, { "from": 137, "to": 138, "label": "BACKTRACK\nfor clause: flat(.(.(H, T), TT), .(H, R)) :- flat(.(T, TT), R)because of non-unification" }, { "from": 139, "to": 141, "label": "CASE" }, { "from": 141, "to": 142, "label": "BACKTRACK\nfor clause: flat([], [])because of non-unification" }, { "from": 142, "to": 143, "label": "PARALLEL" }, { "from": 142, "to": 144, "label": "PARALLEL" }, { "from": 143, "to": 145, "label": "EVAL with clause\nflat(.([], X61), X62) :- flat(X61, X62).\nand substitutionT45 -> [],\nT46 -> T57,\nX61 -> T57,\nT48 -> T59,\nX62 -> T59,\nT58 -> T59" }, { "from": 143, "to": 146, "label": "EVAL-BACKTRACK" }, { "from": 144, "to": 147, "label": "EVAL with clause\nflat(.(.(X71, X72), X73), .(X71, X74)) :- flat(.(X72, X73), X74).\nand substitutionX71 -> T68,\nX72 -> T69,\nT45 -> .(T68, T69),\nT46 -> T70,\nX73 -> T70,\nX74 -> T72,\nT48 -> .(T68, T72),\nT71 -> T72" }, { "from": 144, "to": 148, "label": "EVAL-BACKTRACK" }, { "from": 145, "to": 2, "label": "INSTANCE with matching:\nT1 -> T57\nT2 -> T59" }, { "from": 147, "to": 2, "label": "INSTANCE with matching:\nT1 -> .(T69, T70)\nT2 -> T72" } ], "type": "Graph" } } ---------------------------------------- (2) Obligation: Triples: flatA(.([], .([], X1)), X2) :- flatA(X1, X2). flatA(.([], .(.(X1, X2), X3)), .(X1, X4)) :- flatA(.(X2, X3), X4). flatA(.(.(X1, []), X2), .(X1, X3)) :- flatA(X2, X3). flatA(.(.(X1, .(X2, X3)), X4), .(X1, .(X2, X5))) :- flatA(.(X3, X4), X5). Clauses: flatcA([], []). flatcA(.([], []), []). flatcA(.([], .([], X1)), X2) :- flatcA(X1, X2). flatcA(.([], .(.(X1, X2), X3)), .(X1, X4)) :- flatcA(.(X2, X3), X4). flatcA(.(.(X1, []), X2), .(X1, X3)) :- flatcA(X2, X3). flatcA(.(.(X1, .(X2, X3)), X4), .(X1, .(X2, X5))) :- flatcA(.(X3, X4), X5). Afs: flatA(x1, x2) = flatA(x1) ---------------------------------------- (3) TriplesToPiDPProof (SOUND) We use the technique of [DT09]. With regard to the inferred argument filtering the predicates were used in the following modes: flatA_in_2: (b,f) Transforming TRIPLES into the following Term Rewriting System: Pi DP problem: The TRS P consists of the following rules: FLATA_IN_GA(.([], .([], X1)), X2) -> U1_GA(X1, X2, flatA_in_ga(X1, X2)) FLATA_IN_GA(.([], .([], X1)), X2) -> FLATA_IN_GA(X1, X2) FLATA_IN_GA(.([], .(.(X1, X2), X3)), .(X1, X4)) -> U2_GA(X1, X2, X3, X4, flatA_in_ga(.(X2, X3), X4)) FLATA_IN_GA(.([], .(.(X1, X2), X3)), .(X1, X4)) -> FLATA_IN_GA(.(X2, X3), X4) FLATA_IN_GA(.(.(X1, []), X2), .(X1, X3)) -> U3_GA(X1, X2, X3, flatA_in_ga(X2, X3)) FLATA_IN_GA(.(.(X1, []), X2), .(X1, X3)) -> FLATA_IN_GA(X2, X3) FLATA_IN_GA(.(.(X1, .(X2, X3)), X4), .(X1, .(X2, X5))) -> U4_GA(X1, X2, X3, X4, X5, flatA_in_ga(.(X3, X4), X5)) FLATA_IN_GA(.(.(X1, .(X2, X3)), X4), .(X1, .(X2, X5))) -> FLATA_IN_GA(.(X3, X4), X5) R is empty. The argument filtering Pi contains the following mapping: flatA_in_ga(x1, x2) = flatA_in_ga(x1) .(x1, x2) = .(x1, x2) [] = [] FLATA_IN_GA(x1, x2) = FLATA_IN_GA(x1) U1_GA(x1, x2, x3) = U1_GA(x1, x3) U2_GA(x1, x2, x3, x4, x5) = U2_GA(x1, x2, x3, x5) U3_GA(x1, x2, x3, x4) = U3_GA(x1, x2, x4) U4_GA(x1, x2, x3, x4, x5, x6) = U4_GA(x1, x2, x3, x4, x6) We have to consider all (P,R,Pi)-chains Infinitary Constructor Rewriting Termination of PiDP implies Termination of TRIPLES ---------------------------------------- (4) Obligation: Pi DP problem: The TRS P consists of the following rules: FLATA_IN_GA(.([], .([], X1)), X2) -> U1_GA(X1, X2, flatA_in_ga(X1, X2)) FLATA_IN_GA(.([], .([], X1)), X2) -> FLATA_IN_GA(X1, X2) FLATA_IN_GA(.([], .(.(X1, X2), X3)), .(X1, X4)) -> U2_GA(X1, X2, X3, X4, flatA_in_ga(.(X2, X3), X4)) FLATA_IN_GA(.([], .(.(X1, X2), X3)), .(X1, X4)) -> FLATA_IN_GA(.(X2, X3), X4) FLATA_IN_GA(.(.(X1, []), X2), .(X1, X3)) -> U3_GA(X1, X2, X3, flatA_in_ga(X2, X3)) FLATA_IN_GA(.(.(X1, []), X2), .(X1, X3)) -> FLATA_IN_GA(X2, X3) FLATA_IN_GA(.(.(X1, .(X2, X3)), X4), .(X1, .(X2, X5))) -> U4_GA(X1, X2, X3, X4, X5, flatA_in_ga(.(X3, X4), X5)) FLATA_IN_GA(.(.(X1, .(X2, X3)), X4), .(X1, .(X2, X5))) -> FLATA_IN_GA(.(X3, X4), X5) R is empty. The argument filtering Pi contains the following mapping: flatA_in_ga(x1, x2) = flatA_in_ga(x1) .(x1, x2) = .(x1, x2) [] = [] FLATA_IN_GA(x1, x2) = FLATA_IN_GA(x1) U1_GA(x1, x2, x3) = U1_GA(x1, x3) U2_GA(x1, x2, x3, x4, x5) = U2_GA(x1, x2, x3, x5) U3_GA(x1, x2, x3, x4) = U3_GA(x1, x2, x4) U4_GA(x1, x2, x3, x4, x5, x6) = U4_GA(x1, x2, x3, x4, x6) We have to consider all (P,R,Pi)-chains ---------------------------------------- (5) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LOPSTR] contains 1 SCC with 4 less nodes. ---------------------------------------- (6) Obligation: Pi DP problem: The TRS P consists of the following rules: FLATA_IN_GA(.([], .(.(X1, X2), X3)), .(X1, X4)) -> FLATA_IN_GA(.(X2, X3), X4) FLATA_IN_GA(.([], .([], X1)), X2) -> FLATA_IN_GA(X1, X2) FLATA_IN_GA(.(.(X1, []), X2), .(X1, X3)) -> FLATA_IN_GA(X2, X3) FLATA_IN_GA(.(.(X1, .(X2, X3)), X4), .(X1, .(X2, X5))) -> FLATA_IN_GA(.(X3, X4), X5) R is empty. The argument filtering Pi contains the following mapping: .(x1, x2) = .(x1, x2) [] = [] FLATA_IN_GA(x1, x2) = FLATA_IN_GA(x1) We have to consider all (P,R,Pi)-chains ---------------------------------------- (7) PiDPToQDPProof (SOUND) Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. ---------------------------------------- (8) Obligation: Q DP problem: The TRS P consists of the following rules: FLATA_IN_GA(.([], .(.(X1, X2), X3))) -> FLATA_IN_GA(.(X2, X3)) FLATA_IN_GA(.([], .([], X1))) -> FLATA_IN_GA(X1) FLATA_IN_GA(.(.(X1, []), X2)) -> FLATA_IN_GA(X2) FLATA_IN_GA(.(.(X1, .(X2, X3)), X4)) -> FLATA_IN_GA(.(X3, X4)) R is empty. Q is empty. We have to consider all (P,Q,R)-chains. ---------------------------------------- (9) UsableRulesReductionPairsProof (EQUIVALENT) By using the usable rules with reduction pair processor [LPAR04] with a polynomial ordering [POLO], all dependency pairs and the corresponding usable rules [FROCOS05] can be oriented non-strictly. All non-usable rules are removed, and those dependency pairs and usable rules that have been oriented strictly or contain non-usable symbols in their left-hand side are removed as well. The following dependency pairs can be deleted: FLATA_IN_GA(.([], .(.(X1, X2), X3))) -> FLATA_IN_GA(.(X2, X3)) FLATA_IN_GA(.([], .([], X1))) -> FLATA_IN_GA(X1) FLATA_IN_GA(.(.(X1, []), X2)) -> FLATA_IN_GA(X2) No rules are removed from R. Used ordering: POLO with Polynomial interpretation [POLO]: POL(.(x_1, x_2)) = x_1 + 2*x_2 POL(FLATA_IN_GA(x_1)) = 2*x_1 POL([]) = 0 ---------------------------------------- (10) Obligation: Q DP problem: The TRS P consists of the following rules: FLATA_IN_GA(.(.(X1, .(X2, X3)), X4)) -> FLATA_IN_GA(.(X3, X4)) R is empty. Q is empty. We have to consider all (P,Q,R)-chains. ---------------------------------------- (11) MRRProof (EQUIVALENT) 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: FLATA_IN_GA(.(.(X1, .(X2, X3)), X4)) -> FLATA_IN_GA(.(X3, X4)) Used ordering: Knuth-Bendix order [KBO] with precedence:._2 > FLATA_IN_GA_1 and weight map: FLATA_IN_GA_1=1 ._2=0 The variable weight is 1 ---------------------------------------- (12) Obligation: Q DP problem: P is empty. R is empty. Q is empty. We have to consider all (P,Q,R)-chains. ---------------------------------------- (13) PisEmptyProof (EQUIVALENT) The TRS P is empty. Hence, there is no (P,Q,R) chain. ---------------------------------------- (14) YES