/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 sublist(g,g) w.r.t. the given Prolog program could successfully be proven: (0) Prolog (1) PrologToDTProblemTransformerProof [SOUND, 45 ms] (2) TRIPLES (3) TriplesToPiDPProof [SOUND, 0 ms] (4) PiDP (5) DependencyGraphProof [EQUIVALENT, 0 ms] (6) AND (7) PiDP (8) UsableRulesProof [EQUIVALENT, 0 ms] (9) PiDP (10) PiDPToQDPProof [SOUND, 0 ms] (11) QDP (12) QDPSizeChangeProof [EQUIVALENT, 0 ms] (13) YES (14) PiDP (15) UsableRulesProof [EQUIVALENT, 0 ms] (16) PiDP (17) PiDPToQDPProof [SOUND, 0 ms] (18) QDP (19) QDPSizeChangeProof [EQUIVALENT, 0 ms] (20) YES ---------------------------------------- (0) Obligation: Clauses: append([], Ys, Ys). append(.(X, Xs), Ys, .(X, Zs)) :- append(Xs, Ys, Zs). sublist(X, Y) :- ','(append(P, X1, Y), append(X2, X, P)). Query: sublist(g,g) ---------------------------------------- (1) PrologToDTProblemTransformerProof (SOUND) Built DT problem from termination graph DT10. { "root": 1, "program": { "directives": [], "clauses": [ [ "(append ([]) Ys Ys)", null ], [ "(append (. X Xs) Ys (. X Zs))", "(append Xs Ys Zs)" ], [ "(sublist X Y)", "(',' (append P X1 Y) (append X2 X P))" ] ] }, "graph": { "nodes": { "171": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "type": "Nodes", "153": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "230": { "goal": [{ "clause": 1, "scope": 6, "term": "(append X123 T81 T83)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T81", "T83" ], "free": ["X123"], "exprvars": [] } }, "231": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "199": { "goal": [{ "clause": -1, "scope": -1, "term": "(append X56 X57 T29)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T29"], "free": [ "X56", "X57" ], "exprvars": [] } }, "232": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "211": { "goal": [{ "clause": -1, "scope": -1, "term": "(append X93 X94 T50)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T50"], "free": [ "X93", "X94" ], "exprvars": [] } }, "233": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "212": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "234": { "goal": [{ "clause": -1, "scope": -1, "term": "(append X148 T97 T99)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T97", "T99" ], "free": ["X148"], "exprvars": [] } }, "136": { "goal": [{ "clause": -1, "scope": -1, "term": "(append X9 T5 ([]))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T5"], "free": ["X9"], "exprvars": [] } }, "213": { "goal": [ { "clause": 0, "scope": 5, "term": "(append X9 T5 (. T28 T37))" }, { "clause": 1, "scope": 5, "term": "(append X9 T5 (. T28 T37))" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T5", "T28", "T37" ], "free": ["X9"], "exprvars": [] } }, "235": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "214": { "goal": [{ "clause": 0, "scope": 5, "term": "(append X9 T5 (. T28 T37))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T5", "T28", "T37" ], "free": ["X9"], "exprvars": [] } }, "215": { "goal": [{ "clause": 1, "scope": 5, "term": "(append X9 T5 (. T28 T37))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T5", "T28", "T37" ], "free": ["X9"], "exprvars": [] } }, "216": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "217": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "218": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "75": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (append X7 X8 T6) (append X9 T5 X7))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T5", "T6" ], "free": [ "X7", "X8", "X9" ], "exprvars": [] } }, "76": { "goal": [ { "clause": 0, "scope": 2, "term": "(',' (append X7 X8 T6) (append X9 T5 X7))" }, { "clause": 1, "scope": 2, "term": "(',' (append X7 X8 T6) (append X9 T5 X7))" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T5", "T6" ], "free": [ "X7", "X8", "X9" ], "exprvars": [] } }, "186": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (append X56 X57 T29) (append X9 T5 (. T28 X56)))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T5", "T28", "T29" ], "free": [ "X9", "X56", "X57" ], "exprvars": [] } }, "143": { "goal": [ { "clause": 0, "scope": 3, "term": "(append X9 T5 ([]))" }, { "clause": 1, "scope": 3, "term": "(append X9 T5 ([]))" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T5"], "free": ["X9"], "exprvars": [] } }, "165": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "187": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "1": { "goal": [{ "clause": -1, "scope": -1, "term": "(sublist T1 T2)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T1", "T2" ], "free": [], "exprvars": [] } }, "166": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "200": { "goal": [{ "clause": -1, "scope": -1, "term": "(append X9 T5 (. T28 T37))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T5", "T28", "T37" ], "free": ["X9"], "exprvars": [] } }, "124": { "goal": [{ "clause": 0, "scope": 2, "term": "(',' (append X7 X8 T6) (append X9 T5 X7))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T5", "T6" ], "free": [ "X7", "X8", "X9" ], "exprvars": [] } }, "125": { "goal": [{ "clause": 1, "scope": 2, "term": "(',' (append X7 X8 T6) (append X9 T5 X7))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T5", "T6" ], "free": [ "X7", "X8", "X9" ], "exprvars": [] } }, "147": { "goal": [{ "clause": 0, "scope": 3, "term": "(append X9 T5 ([]))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T5"], "free": ["X9"], "exprvars": [] } }, "149": { "goal": [{ "clause": 1, "scope": 3, "term": "(append X9 T5 ([]))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T5"], "free": ["X9"], "exprvars": [] } }, "204": { "goal": [ { "clause": 0, "scope": 4, "term": "(append X56 X57 T29)" }, { "clause": 1, "scope": 4, "term": "(append X56 X57 T29)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T29"], "free": [ "X56", "X57" ], "exprvars": [] } }, "205": { "goal": [{ "clause": 0, "scope": 4, "term": "(append X56 X57 T29)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T29"], "free": [ "X56", "X57" ], "exprvars": [] } }, "227": { "goal": [{ "clause": -1, "scope": -1, "term": "(append X123 T81 T83)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T81", "T83" ], "free": ["X123"], "exprvars": [] } }, "206": { "goal": [{ "clause": 1, "scope": 4, "term": "(append X56 X57 T29)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T29"], "free": [ "X56", "X57" ], "exprvars": [] } }, "228": { "goal": [ { "clause": 0, "scope": 6, "term": "(append X123 T81 T83)" }, { "clause": 1, "scope": 6, "term": "(append X123 T81 T83)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T81", "T83" ], "free": ["X123"], "exprvars": [] } }, "207": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "229": { "goal": [{ "clause": 0, "scope": 6, "term": "(append X123 T81 T83)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T81", "T83" ], "free": ["X123"], "exprvars": [] } }, "208": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "20": { "goal": [{ "clause": 2, "scope": 1, "term": "(sublist T1 T2)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T1", "T2" ], "free": [], "exprvars": [] } } }, "edges": [ { "from": 1, "to": 20, "label": "CASE" }, { "from": 20, "to": 75, "label": "ONLY EVAL with clause\nsublist(X5, X6) :- ','(append(X7, X8, X6), append(X9, X5, X7)).\nand substitutionT1 -> T5,\nX5 -> T5,\nT2 -> T6,\nX6 -> T6" }, { "from": 75, "to": 76, "label": "CASE" }, { "from": 76, "to": 124, "label": "PARALLEL" }, { "from": 76, "to": 125, "label": "PARALLEL" }, { "from": 124, "to": 136, "label": "ONLY EVAL with clause\nappend([], X22, X22).\nand substitutionX7 -> [],\nX8 -> T15,\nX22 -> T15,\nT6 -> T15,\nX23 -> T15" }, { "from": 125, "to": 186, "label": "EVAL with clause\nappend(.(X51, X52), X53, .(X51, X54)) :- append(X52, X53, X54).\nand substitutionX51 -> T28,\nX52 -> X56,\nX7 -> .(T28, X56),\nX8 -> X57,\nX53 -> X57,\nX55 -> T28,\nX54 -> T29,\nT6 -> .(T28, T29)" }, { "from": 125, "to": 187, "label": "EVAL-BACKTRACK" }, { "from": 136, "to": 143, "label": "CASE" }, { "from": 143, "to": 147, "label": "PARALLEL" }, { "from": 143, "to": 149, "label": "PARALLEL" }, { "from": 147, "to": 153, "label": "EVAL with clause\nappend([], X30, X30).\nand substitutionX9 -> [],\nT5 -> [],\nX30 -> [],\nT22 -> []" }, { "from": 147, "to": 165, "label": "EVAL-BACKTRACK" }, { "from": 149, "to": 171, "label": "BACKTRACK\nfor clause: append(.(X, Xs), Ys, .(X, Zs)) :- append(Xs, Ys, Zs)because of non-unification" }, { "from": 153, "to": 166, "label": "SUCCESS" }, { "from": 186, "to": 199, "label": "SPLIT 1" }, { "from": 186, "to": 200, "label": "SPLIT 2\nnew knowledge:\nT37 is ground\nT38 is ground\nT29 is ground\nreplacements:X56 -> T37,\nX57 -> T38" }, { "from": 199, "to": 204, "label": "CASE" }, { "from": 200, "to": 213, "label": "CASE" }, { "from": 204, "to": 205, "label": "PARALLEL" }, { "from": 204, "to": 206, "label": "PARALLEL" }, { "from": 205, "to": 207, "label": "ONLY EVAL with clause\nappend([], X72, X72).\nand substitutionX56 -> [],\nX57 -> T44,\nX72 -> T44,\nT29 -> T44,\nX73 -> T44" }, { "from": 206, "to": 211, "label": "EVAL with clause\nappend(.(X88, X89), X90, .(X88, X91)) :- append(X89, X90, X91).\nand substitutionX88 -> T49,\nX89 -> X93,\nX56 -> .(T49, X93),\nX57 -> X94,\nX90 -> X94,\nX92 -> T49,\nX91 -> T50,\nT29 -> .(T49, T50)" }, { "from": 206, "to": 212, "label": "EVAL-BACKTRACK" }, { "from": 207, "to": 208, "label": "SUCCESS" }, { "from": 211, "to": 199, "label": "INSTANCE with matching:\nX56 -> X93\nX57 -> X94\nT29 -> T50" }, { "from": 213, "to": 214, "label": "PARALLEL" }, { "from": 213, "to": 215, "label": "PARALLEL" }, { "from": 214, "to": 216, "label": "EVAL with clause\nappend([], X103, X103).\nand substitutionX9 -> [],\nT5 -> .(T71, T72),\nX103 -> .(T71, T72),\nT28 -> T71,\nT37 -> T72,\nT70 -> .(T71, T72)" }, { "from": 214, "to": 217, "label": "EVAL-BACKTRACK" }, { "from": 215, "to": 227, "label": "ONLY EVAL with clause\nappend(.(X118, X119), X120, .(X118, X121)) :- append(X119, X120, X121).\nand substitutionX118 -> T82,\nX119 -> X123,\nX9 -> .(T82, X123),\nT5 -> T81,\nX120 -> T81,\nT28 -> T82,\nX122 -> T82,\nT37 -> T83,\nX121 -> T83" }, { "from": 216, "to": 218, "label": "SUCCESS" }, { "from": 227, "to": 228, "label": "CASE" }, { "from": 228, "to": 229, "label": "PARALLEL" }, { "from": 228, "to": 230, "label": "PARALLEL" }, { "from": 229, "to": 231, "label": "EVAL with clause\nappend([], X130, X130).\nand substitutionX123 -> [],\nT81 -> T90,\nX130 -> T90,\nT83 -> T90" }, { "from": 229, "to": 232, "label": "EVAL-BACKTRACK" }, { "from": 230, "to": 234, "label": "EVAL with clause\nappend(.(X143, X144), X145, .(X143, X146)) :- append(X144, X145, X146).\nand substitutionX143 -> T98,\nX144 -> X148,\nX123 -> .(T98, X148),\nT81 -> T97,\nX145 -> T97,\nX147 -> T98,\nX146 -> T99,\nT83 -> .(T98, T99)" }, { "from": 230, "to": 235, "label": "EVAL-BACKTRACK" }, { "from": 231, "to": 233, "label": "SUCCESS" }, { "from": 234, "to": 227, "label": "INSTANCE with matching:\nX123 -> X148\nT81 -> T97\nT83 -> T99" } ], "type": "Graph" } } ---------------------------------------- (2) Obligation: Triples: appendA(.(X1, X2), X3, .(X1, X4)) :- appendA(X2, X3, X4). appendB(.(X1, X2), X3, .(X1, X4)) :- appendB(X2, X3, X4). sublistC(X1, .(X2, X3)) :- appendA(X4, X5, X3). sublistC(X1, .(X2, X3)) :- ','(appendcA(X4, X5, X3), appendB(X6, X1, X4)). Clauses: appendcA([], X1, X1). appendcA(.(X1, X2), X3, .(X1, X4)) :- appendcA(X2, X3, X4). appendcB([], X1, X1). appendcB(.(X1, X2), X3, .(X1, X4)) :- appendcB(X2, X3, X4). Afs: sublistC(x1, x2) = sublistC(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: sublistC_in_2: (b,b) appendA_in_3: (f,f,b) appendcA_in_3: (f,f,b) appendB_in_3: (f,b,b) Transforming TRIPLES into the following Term Rewriting System: Pi DP problem: The TRS P consists of the following rules: SUBLISTC_IN_GG(X1, .(X2, X3)) -> U3_GG(X1, X2, X3, appendA_in_aag(X4, X5, X3)) SUBLISTC_IN_GG(X1, .(X2, X3)) -> APPENDA_IN_AAG(X4, X5, X3) APPENDA_IN_AAG(.(X1, X2), X3, .(X1, X4)) -> U1_AAG(X1, X2, X3, X4, appendA_in_aag(X2, X3, X4)) APPENDA_IN_AAG(.(X1, X2), X3, .(X1, X4)) -> APPENDA_IN_AAG(X2, X3, X4) SUBLISTC_IN_GG(X1, .(X2, X3)) -> U4_GG(X1, X2, X3, appendcA_in_aag(X4, X5, X3)) U4_GG(X1, X2, X3, appendcA_out_aag(X4, X5, X3)) -> U5_GG(X1, X2, X3, appendB_in_agg(X6, X1, X4)) U4_GG(X1, X2, X3, appendcA_out_aag(X4, X5, X3)) -> APPENDB_IN_AGG(X6, X1, X4) APPENDB_IN_AGG(.(X1, X2), X3, .(X1, X4)) -> U2_AGG(X1, X2, X3, X4, appendB_in_agg(X2, X3, X4)) APPENDB_IN_AGG(.(X1, X2), X3, .(X1, X4)) -> APPENDB_IN_AGG(X2, X3, X4) The TRS R consists of the following rules: appendcA_in_aag([], X1, X1) -> appendcA_out_aag([], X1, X1) appendcA_in_aag(.(X1, X2), X3, .(X1, X4)) -> U7_aag(X1, X2, X3, X4, appendcA_in_aag(X2, X3, X4)) U7_aag(X1, X2, X3, X4, appendcA_out_aag(X2, X3, X4)) -> appendcA_out_aag(.(X1, X2), X3, .(X1, X4)) The argument filtering Pi contains the following mapping: .(x1, x2) = .(x1, x2) appendA_in_aag(x1, x2, x3) = appendA_in_aag(x3) appendcA_in_aag(x1, x2, x3) = appendcA_in_aag(x3) appendcA_out_aag(x1, x2, x3) = appendcA_out_aag(x1, x2, x3) U7_aag(x1, x2, x3, x4, x5) = U7_aag(x1, x4, x5) appendB_in_agg(x1, x2, x3) = appendB_in_agg(x2, x3) SUBLISTC_IN_GG(x1, x2) = SUBLISTC_IN_GG(x1, x2) U3_GG(x1, x2, x3, x4) = U3_GG(x1, x2, x3, x4) APPENDA_IN_AAG(x1, x2, x3) = APPENDA_IN_AAG(x3) U1_AAG(x1, x2, x3, x4, x5) = U1_AAG(x1, x4, x5) U4_GG(x1, x2, x3, x4) = U4_GG(x1, x2, x3, x4) U5_GG(x1, x2, x3, x4) = U5_GG(x1, x2, x3, x4) APPENDB_IN_AGG(x1, x2, x3) = APPENDB_IN_AGG(x2, x3) U2_AGG(x1, x2, x3, x4, x5) = U2_AGG(x1, 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: SUBLISTC_IN_GG(X1, .(X2, X3)) -> U3_GG(X1, X2, X3, appendA_in_aag(X4, X5, X3)) SUBLISTC_IN_GG(X1, .(X2, X3)) -> APPENDA_IN_AAG(X4, X5, X3) APPENDA_IN_AAG(.(X1, X2), X3, .(X1, X4)) -> U1_AAG(X1, X2, X3, X4, appendA_in_aag(X2, X3, X4)) APPENDA_IN_AAG(.(X1, X2), X3, .(X1, X4)) -> APPENDA_IN_AAG(X2, X3, X4) SUBLISTC_IN_GG(X1, .(X2, X3)) -> U4_GG(X1, X2, X3, appendcA_in_aag(X4, X5, X3)) U4_GG(X1, X2, X3, appendcA_out_aag(X4, X5, X3)) -> U5_GG(X1, X2, X3, appendB_in_agg(X6, X1, X4)) U4_GG(X1, X2, X3, appendcA_out_aag(X4, X5, X3)) -> APPENDB_IN_AGG(X6, X1, X4) APPENDB_IN_AGG(.(X1, X2), X3, .(X1, X4)) -> U2_AGG(X1, X2, X3, X4, appendB_in_agg(X2, X3, X4)) APPENDB_IN_AGG(.(X1, X2), X3, .(X1, X4)) -> APPENDB_IN_AGG(X2, X3, X4) The TRS R consists of the following rules: appendcA_in_aag([], X1, X1) -> appendcA_out_aag([], X1, X1) appendcA_in_aag(.(X1, X2), X3, .(X1, X4)) -> U7_aag(X1, X2, X3, X4, appendcA_in_aag(X2, X3, X4)) U7_aag(X1, X2, X3, X4, appendcA_out_aag(X2, X3, X4)) -> appendcA_out_aag(.(X1, X2), X3, .(X1, X4)) The argument filtering Pi contains the following mapping: .(x1, x2) = .(x1, x2) appendA_in_aag(x1, x2, x3) = appendA_in_aag(x3) appendcA_in_aag(x1, x2, x3) = appendcA_in_aag(x3) appendcA_out_aag(x1, x2, x3) = appendcA_out_aag(x1, x2, x3) U7_aag(x1, x2, x3, x4, x5) = U7_aag(x1, x4, x5) appendB_in_agg(x1, x2, x3) = appendB_in_agg(x2, x3) SUBLISTC_IN_GG(x1, x2) = SUBLISTC_IN_GG(x1, x2) U3_GG(x1, x2, x3, x4) = U3_GG(x1, x2, x3, x4) APPENDA_IN_AAG(x1, x2, x3) = APPENDA_IN_AAG(x3) U1_AAG(x1, x2, x3, x4, x5) = U1_AAG(x1, x4, x5) U4_GG(x1, x2, x3, x4) = U4_GG(x1, x2, x3, x4) U5_GG(x1, x2, x3, x4) = U5_GG(x1, x2, x3, x4) APPENDB_IN_AGG(x1, x2, x3) = APPENDB_IN_AGG(x2, x3) U2_AGG(x1, x2, x3, x4, x5) = U2_AGG(x1, 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 7 less nodes. ---------------------------------------- (6) Complex Obligation (AND) ---------------------------------------- (7) Obligation: Pi DP problem: The TRS P consists of the following rules: APPENDB_IN_AGG(.(X1, X2), X3, .(X1, X4)) -> APPENDB_IN_AGG(X2, X3, X4) The TRS R consists of the following rules: appendcA_in_aag([], X1, X1) -> appendcA_out_aag([], X1, X1) appendcA_in_aag(.(X1, X2), X3, .(X1, X4)) -> U7_aag(X1, X2, X3, X4, appendcA_in_aag(X2, X3, X4)) U7_aag(X1, X2, X3, X4, appendcA_out_aag(X2, X3, X4)) -> appendcA_out_aag(.(X1, X2), X3, .(X1, X4)) The argument filtering Pi contains the following mapping: .(x1, x2) = .(x1, x2) appendcA_in_aag(x1, x2, x3) = appendcA_in_aag(x3) appendcA_out_aag(x1, x2, x3) = appendcA_out_aag(x1, x2, x3) U7_aag(x1, x2, x3, x4, x5) = U7_aag(x1, x4, x5) APPENDB_IN_AGG(x1, x2, x3) = APPENDB_IN_AGG(x2, x3) We have to consider all (P,R,Pi)-chains ---------------------------------------- (8) UsableRulesProof (EQUIVALENT) For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. ---------------------------------------- (9) Obligation: Pi DP problem: The TRS P consists of the following rules: APPENDB_IN_AGG(.(X1, X2), X3, .(X1, X4)) -> APPENDB_IN_AGG(X2, X3, X4) R is empty. The argument filtering Pi contains the following mapping: .(x1, x2) = .(x1, x2) APPENDB_IN_AGG(x1, x2, x3) = APPENDB_IN_AGG(x2, x3) We have to consider all (P,R,Pi)-chains ---------------------------------------- (10) PiDPToQDPProof (SOUND) Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. ---------------------------------------- (11) Obligation: Q DP problem: The TRS P consists of the following rules: APPENDB_IN_AGG(X3, .(X1, X4)) -> APPENDB_IN_AGG(X3, X4) R is empty. Q is empty. We have to consider all (P,Q,R)-chains. ---------------------------------------- (12) 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: *APPENDB_IN_AGG(X3, .(X1, X4)) -> APPENDB_IN_AGG(X3, X4) The graph contains the following edges 1 >= 1, 2 > 2 ---------------------------------------- (13) YES ---------------------------------------- (14) Obligation: Pi DP problem: The TRS P consists of the following rules: APPENDA_IN_AAG(.(X1, X2), X3, .(X1, X4)) -> APPENDA_IN_AAG(X2, X3, X4) The TRS R consists of the following rules: appendcA_in_aag([], X1, X1) -> appendcA_out_aag([], X1, X1) appendcA_in_aag(.(X1, X2), X3, .(X1, X4)) -> U7_aag(X1, X2, X3, X4, appendcA_in_aag(X2, X3, X4)) U7_aag(X1, X2, X3, X4, appendcA_out_aag(X2, X3, X4)) -> appendcA_out_aag(.(X1, X2), X3, .(X1, X4)) The argument filtering Pi contains the following mapping: .(x1, x2) = .(x1, x2) appendcA_in_aag(x1, x2, x3) = appendcA_in_aag(x3) appendcA_out_aag(x1, x2, x3) = appendcA_out_aag(x1, x2, x3) U7_aag(x1, x2, x3, x4, x5) = U7_aag(x1, x4, x5) APPENDA_IN_AAG(x1, x2, x3) = APPENDA_IN_AAG(x3) We have to consider all (P,R,Pi)-chains ---------------------------------------- (15) UsableRulesProof (EQUIVALENT) For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. ---------------------------------------- (16) Obligation: Pi DP problem: The TRS P consists of the following rules: APPENDA_IN_AAG(.(X1, X2), X3, .(X1, X4)) -> APPENDA_IN_AAG(X2, X3, X4) R is empty. The argument filtering Pi contains the following mapping: .(x1, x2) = .(x1, x2) APPENDA_IN_AAG(x1, x2, x3) = APPENDA_IN_AAG(x3) We have to consider all (P,R,Pi)-chains ---------------------------------------- (17) PiDPToQDPProof (SOUND) Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. ---------------------------------------- (18) Obligation: Q DP problem: The TRS P consists of the following rules: APPENDA_IN_AAG(.(X1, X4)) -> APPENDA_IN_AAG(X4) R is empty. Q is empty. We have to consider all (P,Q,R)-chains. ---------------------------------------- (19) 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: *APPENDA_IN_AAG(.(X1, X4)) -> APPENDA_IN_AAG(X4) The graph contains the following edges 1 > 1 ---------------------------------------- (20) YES