/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 overlap(g,g) 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) AND (7) PiDP (8) PiDPToQDPProof [EQUIVALENT, 0 ms] (9) QDP (10) QDPSizeChangeProof [EQUIVALENT, 0 ms] (11) YES (12) PiDP (13) PiDPToQDPProof [SOUND, 0 ms] (14) QDP (15) QDPSizeChangeProof [EQUIVALENT, 0 ms] (16) YES ---------------------------------------- (0) Obligation: Clauses: overlap(Xs, Ys) :- ','(member(X, Xs), member(X, Ys)). member(X1, []) :- ','(!, failure(a)). member(X, Y) :- head(Y, X). member(X, Y) :- ','(tail(Y, T), member(X, T)). head([], X2). head(.(H, X3), H). tail([], []). tail(.(X4, T), T). failure(b). Query: overlap(g,g) ---------------------------------------- (1) PrologToDTProblemTransformerProof (SOUND) Built DT problem from termination graph DT10. { "root": 1, "program": { "directives": [], "clauses": [ [ "(overlap Xs Ys)", "(',' (member X Xs) (member X Ys))" ], [ "(member X1 ([]))", "(',' (!) (failure (a)))" ], [ "(member X Y)", "(head Y X)" ], [ "(member X Y)", "(',' (tail Y T) (member X T))" ], [ "(head ([]) X2)", null ], [ "(head (. H X3) H)", null ], [ "(tail ([]) ([]))", null ], [ "(tail (. X4 T) T)", null ], [ "(failure (b))", null ] ] }, "graph": { "nodes": { "22": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (member X9 T5) (member X9 T6))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T5", "T6" ], "free": ["X9"], "exprvars": [] } }, "23": { "goal": [ { "clause": 1, "scope": 2, "term": "(',' (member X9 T5) (member X9 T6))" }, { "clause": 2, "scope": 2, "term": "(',' (member X9 T5) (member X9 T6))" }, { "clause": 3, "scope": 2, "term": "(',' (member X9 T5) (member X9 T6))" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T5", "T6" ], "free": ["X9"], "exprvars": [] } }, "49": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (failure (a)) (member X15 T6))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T6"], "free": ["X15"], "exprvars": [] } }, "29": { "goal": [ { "clause": -1, "scope": -1, "term": "(',' (',' (!_2) (failure (a))) (member X15 T6))" }, { "clause": 2, "scope": 2, "term": "(',' (member X9 ([])) (member X9 T6))" }, { "clause": 3, "scope": 2, "term": "(',' (member X9 ([])) (member X9 T6))" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T6"], "free": [ "X9", "X15" ], "exprvars": [] } }, "290": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "171": { "goal": [{ "clause": 2, "scope": 2, "term": "(',' (member X9 T5) (member X9 T6))" }], "kb": { "nonunifying": [[ "(member X9 T5)", "(member X14 ([]))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T5", "T6" ], "free": [ "X9", "X14" ], "exprvars": [] } }, "270": { "goal": [{ "clause": 5, "scope": 7, "term": "(head T31 T30)" }], "kb": { "nonunifying": [[ "(member T30 T31)", "(member X50 ([]))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T30", "T31" ], "free": ["X50"], "exprvars": [] } }, "type": "Nodes", "176": { "goal": [{ "clause": 3, "scope": 2, "term": "(',' (member X9 T5) (member X9 T6))" }], "kb": { "nonunifying": [[ "(member X9 T5)", "(member X14 ([]))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T5", "T6" ], "free": [ "X9", "X14" ], "exprvars": [] } }, "255": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (head T11 X36) (member X36 T6))" }], "kb": { "nonunifying": [[ "(member X9 T11)", "(member X14 ([]))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T6", "T11" ], "free": [ "X9", "X14", "X36" ], "exprvars": [] } }, "256": { "goal": [ { "clause": 4, "scope": 4, "term": "(',' (head T11 X36) (member X36 T6))" }, { "clause": 5, "scope": 4, "term": "(',' (head T11 X36) (member X36 T6))" } ], "kb": { "nonunifying": [[ "(member X9 T11)", "(member X14 ([]))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T6", "T11" ], "free": [ "X9", "X14", "X36" ], "exprvars": [] } }, "257": { "goal": [{ "clause": 5, "scope": 4, "term": "(',' (head T11 X36) (member X36 T6))" }], "kb": { "nonunifying": [[ "(member X9 T11)", "(member X14 ([]))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T6", "T11" ], "free": [ "X9", "X14", "X36" ], "exprvars": [] } }, "258": { "goal": [{ "clause": -1, "scope": -1, "term": "(member T16 T6)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T6", "T16" ], "free": [], "exprvars": [] } }, "259": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "30": { "goal": [ { "clause": 2, "scope": 2, "term": "(',' (member X9 T5) (member X9 T6))" }, { "clause": 3, "scope": 2, "term": "(',' (member X9 T5) (member X9 T6))" } ], "kb": { "nonunifying": [[ "(member X9 T5)", "(member X14 ([]))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T5", "T6" ], "free": [ "X9", "X14" ], "exprvars": [] } }, "54": { "goal": [{ "clause": 8, "scope": 3, "term": "(',' (failure (a)) (member X15 T6))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T6"], "free": ["X15"], "exprvars": [] } }, "57": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "260": { "goal": [ { "clause": 1, "scope": 5, "term": "(member T16 T6)" }, { "clause": 2, "scope": 5, "term": "(member T16 T6)" }, { "clause": 3, "scope": 5, "term": "(member T16 T6)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T6", "T16" ], "free": [], "exprvars": [] } }, "261": { "goal": [ { "clause": -1, "scope": -1, "term": "(',' (!_5) (failure (a)))" }, { "clause": 2, "scope": 5, "term": "(member T21 ([]))" }, { "clause": 3, "scope": 5, "term": "(member T21 ([]))" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T21"], "free": [], "exprvars": [] } }, "283": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "262": { "goal": [ { "clause": 2, "scope": 5, "term": "(member T16 T6)" }, { "clause": 3, "scope": 5, "term": "(member T16 T6)" } ], "kb": { "nonunifying": [[ "(member T16 T6)", "(member X50 ([]))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T6", "T16" ], "free": ["X50"], "exprvars": [] } }, "284": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "263": { "goal": [{ "clause": -1, "scope": -1, "term": "(failure (a))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "285": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "264": { "goal": [{ "clause": 8, "scope": 6, "term": "(failure (a))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "286": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (tail T45 X76) (member T44 X76))" }], "kb": { "nonunifying": [[ "(member T44 T45)", "(member X50 ([]))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T44", "T45" ], "free": [ "X50", "X76" ], "exprvars": [] } }, "341": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (',' (tail T56 X96) (member X97 X96)) (member X97 T6))" }], "kb": { "nonunifying": [[ "(member X9 T56)", "(member X14 ([]))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T6", "T56" ], "free": [ "X9", "X14", "X97", "X96" ], "exprvars": [] } }, "1": { "goal": [{ "clause": -1, "scope": -1, "term": "(overlap T1 T2)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T1", "T2" ], "free": [], "exprvars": [] } }, "265": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "287": { "goal": [ { "clause": 6, "scope": 8, "term": "(',' (tail T45 X76) (member T44 X76))" }, { "clause": 7, "scope": 8, "term": "(',' (tail T45 X76) (member T44 X76))" } ], "kb": { "nonunifying": [[ "(member T44 T45)", "(member X50 ([]))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T44", "T45" ], "free": [ "X50", "X76" ], "exprvars": [] } }, "342": { "goal": [ { "clause": 6, "scope": 9, "term": "(',' (',' (tail T56 X96) (member X97 X96)) (member X97 T6))" }, { "clause": 7, "scope": 9, "term": "(',' (',' (tail T56 X96) (member X97 X96)) (member X97 T6))" } ], "kb": { "nonunifying": [[ "(member X9 T56)", "(member X14 ([]))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T6", "T56" ], "free": [ "X9", "X14", "X97", "X96" ], "exprvars": [] } }, "266": { "goal": [{ "clause": 2, "scope": 5, "term": "(member T16 T6)" }], "kb": { "nonunifying": [[ "(member T16 T6)", "(member X50 ([]))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T6", "T16" ], "free": ["X50"], "exprvars": [] } }, "288": { "goal": [{ "clause": 7, "scope": 8, "term": "(',' (tail T45 X76) (member T44 X76))" }], "kb": { "nonunifying": [[ "(member T44 T45)", "(member X50 ([]))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T44", "T45" ], "free": [ "X50", "X76" ], "exprvars": [] } }, "343": { "goal": [{ "clause": 7, "scope": 9, "term": "(',' (',' (tail T56 X96) (member X97 X96)) (member X97 T6))" }], "kb": { "nonunifying": [[ "(member X9 T56)", "(member X14 ([]))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T6", "T56" ], "free": [ "X9", "X14", "X97", "X96" ], "exprvars": [] } }, "3": { "goal": [{ "clause": 0, "scope": 1, "term": "(overlap T1 T2)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T1", "T2" ], "free": [], "exprvars": [] } }, "267": { "goal": [{ "clause": 3, "scope": 5, "term": "(member T16 T6)" }], "kb": { "nonunifying": [[ "(member T16 T6)", "(member X50 ([]))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T6", "T16" ], "free": ["X50"], "exprvars": [] } }, "289": { "goal": [{ "clause": -1, "scope": -1, "term": "(member T44 T52)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T44", "T52" ], "free": [], "exprvars": [] } }, "344": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (member X97 T62) (member X97 T6))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T6", "T62" ], "free": ["X97"], "exprvars": [] } }, "268": { "goal": [{ "clause": -1, "scope": -1, "term": "(head T31 T30)" }], "kb": { "nonunifying": [[ "(member T30 T31)", "(member X50 ([]))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T30", "T31" ], "free": ["X50"], "exprvars": [] } }, "345": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "269": { "goal": [ { "clause": 4, "scope": 7, "term": "(head T31 T30)" }, { "clause": 5, "scope": 7, "term": "(head T31 T30)" } ], "kb": { "nonunifying": [[ "(member T30 T31)", "(member X50 ([]))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T30", "T31" ], "free": ["X50"], "exprvars": [] } } }, "edges": [ { "from": 1, "to": 3, "label": "CASE" }, { "from": 3, "to": 22, "label": "ONLY EVAL with clause\noverlap(X7, X8) :- ','(member(X9, X7), member(X9, X8)).\nand substitutionT1 -> T5,\nX7 -> T5,\nT2 -> T6,\nX8 -> T6" }, { "from": 22, "to": 23, "label": "CASE" }, { "from": 23, "to": 29, "label": "EVAL with clause\nmember(X14, []) :- ','(!_2, failure(a)).\nand substitutionX9 -> X15,\nX14 -> X15,\nT5 -> []" }, { "from": 23, "to": 30, "label": "EVAL-BACKTRACK" }, { "from": 29, "to": 49, "label": "CUT" }, { "from": 30, "to": 171, "label": "PARALLEL" }, { "from": 30, "to": 176, "label": "PARALLEL" }, { "from": 49, "to": 54, "label": "CASE" }, { "from": 54, "to": 57, "label": "BACKTRACK\nfor clause: failure(b)because of non-unification" }, { "from": 171, "to": 255, "label": "ONLY EVAL with clause\nmember(X34, X35) :- head(X35, X34).\nand substitutionX9 -> X36,\nX34 -> X36,\nT5 -> T11,\nX35 -> T11" }, { "from": 176, "to": 341, "label": "ONLY EVAL with clause\nmember(X94, X95) :- ','(tail(X95, X96), member(X94, X96)).\nand substitutionX9 -> X97,\nX94 -> X97,\nT5 -> T56,\nX95 -> T56" }, { "from": 255, "to": 256, "label": "CASE" }, { "from": 256, "to": 257, "label": "BACKTRACK\nfor clause: head([], X2)\nwith clash: (member(X9, T11), member(X14, []))" }, { "from": 257, "to": 258, "label": "EVAL with clause\nhead(.(X45, X46), X45).\nand substitutionX45 -> T16,\nX46 -> T17,\nT11 -> .(T16, T17),\nX36 -> T16" }, { "from": 257, "to": 259, "label": "EVAL-BACKTRACK" }, { "from": 258, "to": 260, "label": "CASE" }, { "from": 260, "to": 261, "label": "EVAL with clause\nmember(X50, []) :- ','(!_5, failure(a)).\nand substitutionT16 -> T21,\nX50 -> T21,\nT6 -> []" }, { "from": 260, "to": 262, "label": "EVAL-BACKTRACK" }, { "from": 261, "to": 263, "label": "CUT" }, { "from": 262, "to": 266, "label": "PARALLEL" }, { "from": 262, "to": 267, "label": "PARALLEL" }, { "from": 263, "to": 264, "label": "CASE" }, { "from": 264, "to": 265, "label": "BACKTRACK\nfor clause: failure(b)because of non-unification" }, { "from": 266, "to": 268, "label": "ONLY EVAL with clause\nmember(X59, X60) :- head(X60, X59).\nand substitutionT16 -> T30,\nX59 -> T30,\nT6 -> T31,\nX60 -> T31" }, { "from": 267, "to": 286, "label": "ONLY EVAL with clause\nmember(X74, X75) :- ','(tail(X75, X76), member(X74, X76)).\nand substitutionT16 -> T44,\nX74 -> T44,\nT6 -> T45,\nX75 -> T45" }, { "from": 268, "to": 269, "label": "CASE" }, { "from": 269, "to": 270, "label": "BACKTRACK\nfor clause: head([], X2)\nwith clash: (member(T30, T31), member(X50, []))" }, { "from": 270, "to": 283, "label": "EVAL with clause\nhead(.(X66, X67), X66).\nand substitutionX66 -> T37,\nX67 -> T38,\nT31 -> .(T37, T38),\nT30 -> T37" }, { "from": 270, "to": 284, "label": "EVAL-BACKTRACK" }, { "from": 283, "to": 285, "label": "SUCCESS" }, { "from": 286, "to": 287, "label": "CASE" }, { "from": 287, "to": 288, "label": "BACKTRACK\nfor clause: tail([], [])\nwith clash: (member(T44, T45), member(X50, []))" }, { "from": 288, "to": 289, "label": "EVAL with clause\ntail(.(X82, X83), X83).\nand substitutionX82 -> T51,\nX83 -> T52,\nT45 -> .(T51, T52),\nX76 -> T52" }, { "from": 288, "to": 290, "label": "EVAL-BACKTRACK" }, { "from": 289, "to": 258, "label": "INSTANCE with matching:\nT16 -> T44\nT6 -> T52" }, { "from": 341, "to": 342, "label": "CASE" }, { "from": 342, "to": 343, "label": "BACKTRACK\nfor clause: tail([], [])\nwith clash: (member(X9, T56), member(X14, []))" }, { "from": 343, "to": 344, "label": "EVAL with clause\ntail(.(X104, X105), X105).\nand substitutionX104 -> T61,\nX105 -> T62,\nT56 -> .(T61, T62),\nX96 -> T62" }, { "from": 343, "to": 345, "label": "EVAL-BACKTRACK" }, { "from": 344, "to": 22, "label": "INSTANCE with matching:\nX9 -> X97\nT5 -> T62" } ], "type": "Graph" } } ---------------------------------------- (2) Obligation: Triples: memberA(X1, .(X2, X3)) :- memberA(X1, X3). pB(X1, .(X1, X2), X3) :- memberA(X1, X3). pB(X1, .(X2, X3), X4) :- pB(X1, X3, X4). overlapC(X1, X2) :- pB(X3, X1, X2). Clauses: membercA(X1, .(X1, X2)). membercA(X1, .(X2, X3)) :- membercA(X1, X3). qcB(X1, .(X1, X2), X3) :- membercA(X1, X3). qcB(X1, .(X2, X3), X4) :- qcB(X1, X3, X4). Afs: overlapC(x1, x2) = overlapC(x1, x2) ---------------------------------------- (3) TriplesToPiDPProof (SOUND) We use the technique of [DT09]. With regard to the inferred argument filtering the predicates were used in the following modes: overlapC_in_2: (b,b) pB_in_3: (f,b,b) memberA_in_2: (b,b) Transforming TRIPLES into the following Term Rewriting System: Pi DP problem: The TRS P consists of the following rules: OVERLAPC_IN_GG(X1, X2) -> U4_GG(X1, X2, pB_in_agg(X3, X1, X2)) OVERLAPC_IN_GG(X1, X2) -> PB_IN_AGG(X3, X1, X2) PB_IN_AGG(X1, .(X1, X2), X3) -> U2_AGG(X1, X2, X3, memberA_in_gg(X1, X3)) PB_IN_AGG(X1, .(X1, X2), X3) -> MEMBERA_IN_GG(X1, X3) MEMBERA_IN_GG(X1, .(X2, X3)) -> U1_GG(X1, X2, X3, memberA_in_gg(X1, X3)) MEMBERA_IN_GG(X1, .(X2, X3)) -> MEMBERA_IN_GG(X1, X3) PB_IN_AGG(X1, .(X2, X3), X4) -> U3_AGG(X1, X2, X3, X4, pB_in_agg(X1, X3, X4)) PB_IN_AGG(X1, .(X2, X3), X4) -> PB_IN_AGG(X1, X3, X4) R is empty. The argument filtering Pi contains the following mapping: pB_in_agg(x1, x2, x3) = pB_in_agg(x2, x3) .(x1, x2) = .(x1, x2) memberA_in_gg(x1, x2) = memberA_in_gg(x1, x2) OVERLAPC_IN_GG(x1, x2) = OVERLAPC_IN_GG(x1, x2) U4_GG(x1, x2, x3) = U4_GG(x1, x2, x3) PB_IN_AGG(x1, x2, x3) = PB_IN_AGG(x2, x3) U2_AGG(x1, x2, x3, x4) = U2_AGG(x1, x2, x3, x4) MEMBERA_IN_GG(x1, x2) = MEMBERA_IN_GG(x1, x2) U1_GG(x1, x2, x3, x4) = U1_GG(x1, x2, x3, x4) U3_AGG(x1, x2, x3, x4, x5) = U3_AGG(x2, x3, x4, x5) 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: OVERLAPC_IN_GG(X1, X2) -> U4_GG(X1, X2, pB_in_agg(X3, X1, X2)) OVERLAPC_IN_GG(X1, X2) -> PB_IN_AGG(X3, X1, X2) PB_IN_AGG(X1, .(X1, X2), X3) -> U2_AGG(X1, X2, X3, memberA_in_gg(X1, X3)) PB_IN_AGG(X1, .(X1, X2), X3) -> MEMBERA_IN_GG(X1, X3) MEMBERA_IN_GG(X1, .(X2, X3)) -> U1_GG(X1, X2, X3, memberA_in_gg(X1, X3)) MEMBERA_IN_GG(X1, .(X2, X3)) -> MEMBERA_IN_GG(X1, X3) PB_IN_AGG(X1, .(X2, X3), X4) -> U3_AGG(X1, X2, X3, X4, pB_in_agg(X1, X3, X4)) PB_IN_AGG(X1, .(X2, X3), X4) -> PB_IN_AGG(X1, X3, X4) R is empty. The argument filtering Pi contains the following mapping: pB_in_agg(x1, x2, x3) = pB_in_agg(x2, x3) .(x1, x2) = .(x1, x2) memberA_in_gg(x1, x2) = memberA_in_gg(x1, x2) OVERLAPC_IN_GG(x1, x2) = OVERLAPC_IN_GG(x1, x2) U4_GG(x1, x2, x3) = U4_GG(x1, x2, x3) PB_IN_AGG(x1, x2, x3) = PB_IN_AGG(x2, x3) U2_AGG(x1, x2, x3, x4) = U2_AGG(x1, x2, x3, x4) MEMBERA_IN_GG(x1, x2) = MEMBERA_IN_GG(x1, x2) U1_GG(x1, x2, x3, x4) = U1_GG(x1, x2, x3, x4) U3_AGG(x1, x2, x3, x4, x5) = U3_AGG(x2, x3, x4, x5) We have to consider all (P,R,Pi)-chains ---------------------------------------- (5) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LOPSTR] contains 2 SCCs with 6 less nodes. ---------------------------------------- (6) Complex Obligation (AND) ---------------------------------------- (7) Obligation: Pi DP problem: The TRS P consists of the following rules: MEMBERA_IN_GG(X1, .(X2, X3)) -> MEMBERA_IN_GG(X1, X3) R is empty. Pi is empty. We have to consider all (P,R,Pi)-chains ---------------------------------------- (8) PiDPToQDPProof (EQUIVALENT) Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. ---------------------------------------- (9) Obligation: Q DP problem: The TRS P consists of the following rules: MEMBERA_IN_GG(X1, .(X2, X3)) -> MEMBERA_IN_GG(X1, X3) R is empty. Q is empty. We have to consider all (P,Q,R)-chains. ---------------------------------------- (10) QDPSizeChangeProof (EQUIVALENT) By using the subterm criterion [SUBTERM_CRITERION] together with the size-change analysis [AAECC05] we have proven that there are no infinite chains for this DP problem. From the DPs we obtained the following set of size-change graphs: *MEMBERA_IN_GG(X1, .(X2, X3)) -> MEMBERA_IN_GG(X1, X3) The graph contains the following edges 1 >= 1, 2 > 2 ---------------------------------------- (11) YES ---------------------------------------- (12) Obligation: Pi DP problem: The TRS P consists of the following rules: PB_IN_AGG(X1, .(X2, X3), X4) -> PB_IN_AGG(X1, X3, X4) R is empty. The argument filtering Pi contains the following mapping: .(x1, x2) = .(x1, x2) PB_IN_AGG(x1, x2, x3) = PB_IN_AGG(x2, x3) We have to consider all (P,R,Pi)-chains ---------------------------------------- (13) PiDPToQDPProof (SOUND) Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. ---------------------------------------- (14) Obligation: Q DP problem: The TRS P consists of the following rules: PB_IN_AGG(.(X2, X3), X4) -> PB_IN_AGG(X3, X4) R is empty. Q is empty. We have to consider all (P,Q,R)-chains. ---------------------------------------- (15) QDPSizeChangeProof (EQUIVALENT) By using the subterm criterion [SUBTERM_CRITERION] together with the size-change analysis [AAECC05] we have proven that there are no infinite chains for this DP problem. From the DPs we obtained the following set of size-change graphs: *PB_IN_AGG(.(X2, X3), X4) -> PB_IN_AGG(X3, X4) The graph contains the following edges 1 > 1, 2 >= 2 ---------------------------------------- (16) YES