/export/starexec/sandbox/solver/bin/starexec_run_standard /export/starexec/sandbox/benchmark/theBenchmark.pl /export/starexec/sandbox/output/output_files -------------------------------------------------------------------------------- Graph construction failed Graph construction failed YES proof of /export/starexec/sandbox/benchmark/theBenchmark.pl # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty Left Termination of the query pattern init_vars(g,g,a,a) w.r.t. the given Prolog program could successfully be proven: (0) Prolog (1) PrologToDTProblemTransformerProof [SOUND, 0 ms] (2) TRIPLES (3) TriplesToPiDPProof [SOUND, 3 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 (21) PiDP (22) UsableRulesProof [EQUIVALENT, 0 ms] (23) PiDP (24) PiDPToQDPProof [SOUND, 0 ms] (25) QDP (26) QDPSizeChangeProof [EQUIVALENT, 0 ms] (27) YES ---------------------------------------- (0) Obligation: Clauses: init_vars(E1, E2, E1init, E2init) :- ','(find_all_vars(E1, Vars1), ','(find_all_vars(E2, Vars2), ','(intersect(Vars1, Vars2, _X, Notin1, Notin2), ','(init_vars2(Notin1, E1, E1init), init_vars2(Notin2, E2, E2init))))). find_all_vars(E, Vars) :- ','(find_all_vars2(E, Vars0), sort(Vars0, Vars)). find_all_vars2([], []). find_all_vars2(.(=(Vars, _Values), Es), AllVars) :- ','(append(Vars, AllVars1, AllVars), find_all_vars2(Es, AllVars1)). init_vars2(Notin, E, Einit) :- ','(init_vars3(Notin, E, Einit0), sort(Einit0, Einit)). init_vars3([], E, E). init_vars3(.(Var, Vars), E, .(=(.(Var, []), .(unbound, [])), Es)) :- init_vars3(Vars, E, Es). append([], A, A). append(.(A, B), C, .(A, D)) :- append(B, C, D). intersect(As, [], [], [], As) :- !. intersect([], Bs, [], Bs, []) :- !. intersect(.(A, As), .(B, Bs), Cs, Ds, Es) :- ;(;(->(=(A, B), ','(=(Cs, .(A, Cs2)), intersect(As, Bs, Cs2, Ds, Es))), ->(@<(A, B), ','(=(Es, .(A, Es2)), intersect(As, .(B, Bs), Cs, Ds, Es2)))), ','(=(Ds, .(B, Ds2)), intersect(.(A, As), Bs, Cs, Ds2, Es))). get_query(E1, E2) :- ','(=(E1, .(=(X, .(a, [])), .(=(X, .(a, [])), .(=(X, .(a, [])), .(=(X, .(a, [])), []))))), ','(=(E2, .(=(Y, .(a, [])), .(=(Y, .(a, [])), .(=(Y, .(a, [])), .(=(Y, .(a, [])), []))))), ','(=(X, .(5, .(7, .(8, .(3, .(2, .(4, .(1, .(6, .(9, .(15, .(17, .(18, .(13, .(12, .(14, .(11, .(16, .(19, .(25, .(27, .(28, .(23, .(22, .(24, .(21, .(26, .(29, [])))))))))))))))))))))))))))), =(Y, .(15, .(17, .(18, .(13, .(12, .(14, .(11, .(16, .(19, .(35, .(37, .(38, .(33, .(32, .(34, .(5, .(7, .(8, .(3, .(2, .(4, .(1, .(6, .(9, .(31, .(36, .(39, []))))))))))))))))))))))))))))))). Query: init_vars(g,g,a,a) ---------------------------------------- (1) PrologToDTProblemTransformerProof (SOUND) Built DT problem from termination graph DT10. { "root": 1, "program": { "directives": [], "clauses": [ [ "(init_vars E1 E2 E1init E2init)", "(',' (find_all_vars E1 Vars1) (',' (find_all_vars E2 Vars2) (',' (intersect Vars1 Vars2 _X Notin1 Notin2) (',' (init_vars2 Notin1 E1 E1init) (init_vars2 Notin2 E2 E2init)))))" ], [ "(find_all_vars E Vars)", "(',' (find_all_vars2 E Vars0) (sort Vars0 Vars))" ], [ "(find_all_vars2 ([]) ([]))", null ], [ "(find_all_vars2 (. (= Vars _Values) Es) AllVars)", "(',' (append Vars AllVars1 AllVars) (find_all_vars2 Es AllVars1))" ], [ "(init_vars2 Notin E Einit)", "(',' (init_vars3 Notin E Einit0) (sort Einit0 Einit))" ], [ "(init_vars3 ([]) E E)", null ], [ "(init_vars3 (. Var Vars) E (. (= (. Var ([])) (. (unbound) ([]))) Es))", "(init_vars3 Vars E Es)" ], [ "(append ([]) A A)", null ], [ "(append (. A B) C (. A D))", "(append B C D)" ], [ "(intersect As ([]) ([]) ([]) As)", "(!)" ], [ "(intersect ([]) Bs ([]) Bs ([]))", "(!)" ], [ "(intersect (. A As) (. B Bs) Cs Ds Es)", "(; (; (-> (= A B) (',' (= Cs (. A Cs2)) (intersect As Bs Cs2 Ds Es))) (-> (@< A B) (',' (= Es (. A Es2)) (intersect As (. B Bs) Cs Ds Es2)))) (',' (= Ds (. B Ds2)) (intersect (. A As) Bs Cs Ds2 Es)))" ], [ "(get_query E1 E2)", "(',' (= E1 (. (= X (. (a) ([]))) (. (= X (. (a) ([]))) (. (= X (. (a) ([]))) (. (= X (. (a) ([]))) ([])))))) (',' (= E2 (. (= Y (. (a) ([]))) (. (= Y (. (a) ([]))) (. (= Y (. (a) ([]))) (. (= Y (. (a) ([]))) ([])))))) (',' (= X (. (5) (. (7) (. (8) (. (3) (. (2) (. (4) (. (1) (. (6) (. (9) (. (15) (. (17) (. (18) (. (13) (. (12) (. (14) (. (11) (. (16) (. (19) (. (25) (. (27) (. (28) (. (23) (. (22) (. (24) (. (21) (. (26) (. (29) ([]))))))))))))))))))))))))))))) (= Y (. (15) (. (17) (. (18) (. (13) (. (12) (. (14) (. (11) (. (16) (. (19) (. (35) (. (37) (. (38) (. (33) (. (32) (. (34) (. (5) (. (7) (. (8) (. (3) (. (2) (. (4) (. (1) (. (6) (. (9) (. (31) (. (36) (. (39) ([]))))))))))))))))))))))))))))))))" ] ] }, "graph": { "nodes": { "44": { "goal": [ { "clause": 7, "scope": 4, "term": "(append T25 X40 X41)" }, { "clause": 8, "scope": 4, "term": "(append T25 X40 X41)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T25"], "free": [ "X41", "X40" ], "exprvars": [] } }, "23": { "goal": [{ "clause": 2, "scope": 3, "term": "(find_all_vars2 T17 X23)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T17"], "free": ["X23"], "exprvars": [] } }, "24": { "goal": [{ "clause": 3, "scope": 3, "term": "(find_all_vars2 T17 X23)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T17"], "free": ["X23"], "exprvars": [] } }, "46": { "goal": [{ "clause": 7, "scope": 4, "term": "(append T25 X40 X41)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T25"], "free": [ "X41", "X40" ], "exprvars": [] } }, "47": { "goal": [{ "clause": 8, "scope": 4, "term": "(append T25 X40 X41)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T25"], "free": [ "X41", "X40" ], "exprvars": [] } }, "28": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "type": "Nodes", "112": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "90": { "goal": [ { "clause": 7, "scope": 6, "term": "(append T44 X95 T48)" }, { "clause": 8, "scope": 6, "term": "(append T44 X95 T48)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T44"], "free": ["X95"], "exprvars": [] } }, "91": { "goal": [{ "clause": 7, "scope": 6, "term": "(append T44 X95 T48)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T44"], "free": ["X95"], "exprvars": [] } }, "70": { "goal": [ { "clause": 2, "scope": 5, "term": "(find_all_vars2 T27 T28)" }, { "clause": 3, "scope": 5, "term": "(find_all_vars2 T27 T28)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T27"], "free": [], "exprvars": [] } }, "92": { "goal": [{ "clause": 8, "scope": 6, "term": "(append T44 X95 T48)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T44"], "free": ["X95"], "exprvars": [] } }, "71": { "goal": [{ "clause": 2, "scope": 5, "term": "(find_all_vars2 T27 T28)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T27"], "free": [], "exprvars": [] } }, "50": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "72": { "goal": [{ "clause": 3, "scope": 5, "term": "(find_all_vars2 T27 T28)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T27"], "free": [], "exprvars": [] } }, "51": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "73": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "52": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "74": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "96": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "31": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "97": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "76": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "99": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "12": { "goal": [{ "clause": -1, "scope": -1, "term": "(find_all_vars2 T17 X23)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T17"], "free": ["X23"], "exprvars": [] } }, "34": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "56": { "goal": [{ "clause": -1, "scope": -1, "term": "(append T35 X76 X77)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T35"], "free": [ "X76", "X77" ], "exprvars": [] } }, "57": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "14": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (sort T18 X24) (',' (find_all_vars T10 X10) (',' (intersect X24 X10 X11 X12 X13) (',' (init_vars2 X12 T17 T13) (init_vars2 X13 T10 T14)))))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T10", "T17" ], "free": [ "X10", "X11", "X12", "X13", "X24" ], "exprvars": [] } }, "36": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (append T25 X40 X41) (find_all_vars2 T27 X40))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T25", "T27" ], "free": [ "X41", "X40" ], "exprvars": [] } }, "37": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "18": { "goal": [ { "clause": 2, "scope": 3, "term": "(find_all_vars2 T17 X23)" }, { "clause": 3, "scope": 3, "term": "(find_all_vars2 T17 X23)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T17"], "free": ["X23"], "exprvars": [] } }, "1": { "goal": [{ "clause": -1, "scope": -1, "term": "(init_vars T1 T2 T3 T4)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T1", "T2" ], "free": [], "exprvars": [] } }, "3": { "goal": [{ "clause": 0, "scope": 1, "term": "(init_vars T1 T2 T3 T4)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T1", "T2" ], "free": [], "exprvars": [] } }, "6": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (find_all_vars T9 X9) (',' (find_all_vars T10 X10) (',' (intersect X9 X10 X11 X12 X13) (',' (init_vars2 X12 T9 T13) (init_vars2 X13 T10 T14)))))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T9", "T10" ], "free": [ "X9", "X10", "X11", "X12", "X13" ], "exprvars": [] } }, "7": { "goal": [{ "clause": 1, "scope": 2, "term": "(',' (find_all_vars T9 X9) (',' (find_all_vars T10 X10) (',' (intersect X9 X10 X11 X12 X13) (',' (init_vars2 X12 T9 T13) (init_vars2 X13 T10 T14)))))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T9", "T10" ], "free": [ "X9", "X10", "X11", "X12", "X13" ], "exprvars": [] } }, "8": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (',' (find_all_vars2 T17 X23) (sort X23 X24)) (',' (find_all_vars T10 X10) (',' (intersect X24 X10 X11 X12 X13) (',' (init_vars2 X12 T17 T13) (init_vars2 X13 T10 T14)))))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T10", "T17" ], "free": [ "X10", "X11", "X12", "X13", "X24", "X23" ], "exprvars": [] } }, "81": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (append T44 X95 T48) (find_all_vars2 T46 X95))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T44", "T46" ], "free": ["X95"], "exprvars": [] } }, "108": { "goal": [{ "clause": -1, "scope": -1, "term": "(append T66 X128 T68)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T66"], "free": ["X128"], "exprvars": [] } }, "82": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "109": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "40": { "goal": [{ "clause": -1, "scope": -1, "term": "(append T25 X40 X41)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T25"], "free": [ "X41", "X40" ], "exprvars": [] } }, "41": { "goal": [{ "clause": -1, "scope": -1, "term": "(find_all_vars2 T27 T28)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T27"], "free": [], "exprvars": [] } }, "86": { "goal": [{ "clause": -1, "scope": -1, "term": "(append T44 X95 T48)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T44"], "free": ["X95"], "exprvars": [] } }, "87": { "goal": [{ "clause": -1, "scope": -1, "term": "(find_all_vars2 T46 T51)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T46"], "free": [], "exprvars": [] } } }, "edges": [ { "from": 1, "to": 3, "label": "CASE" }, { "from": 3, "to": 6, "label": "ONLY EVAL with clause\ninit_vars(X5, X6, X7, X8) :- ','(find_all_vars(X5, X9), ','(find_all_vars(X6, X10), ','(intersect(X9, X10, X11, X12, X13), ','(init_vars2(X12, X5, X7), init_vars2(X13, X6, X8))))).\nand substitutionT1 -> T9,\nX5 -> T9,\nT2 -> T10,\nX6 -> T10,\nT3 -> T13,\nX7 -> T13,\nT4 -> T14,\nX8 -> T14,\nT11 -> T13,\nT12 -> T14" }, { "from": 6, "to": 7, "label": "CASE" }, { "from": 7, "to": 8, "label": "ONLY EVAL with clause\nfind_all_vars(X21, X22) :- ','(find_all_vars2(X21, X23), sort(X23, X22)).\nand substitutionT9 -> T17,\nX21 -> T17,\nX9 -> X24,\nX22 -> X24" }, { "from": 8, "to": 12, "label": "SPLIT 1" }, { "from": 8, "to": 14, "label": "SPLIT 2\nnew knowledge:\nT17 is ground\nreplacements:X23 -> T18" }, { "from": 12, "to": 18, "label": "CASE" }, { "from": 14, "to": 112, "label": "UNDEFINED ERROR" }, { "from": 18, "to": 23, "label": "PARALLEL" }, { "from": 18, "to": 24, "label": "PARALLEL" }, { "from": 23, "to": 28, "label": "EVAL with clause\nfind_all_vars2([], []).\nand substitutionT17 -> [],\nX23 -> []" }, { "from": 23, "to": 31, "label": "EVAL-BACKTRACK" }, { "from": 24, "to": 36, "label": "EVAL with clause\nfind_all_vars2(.(=(X36, X37), X38), X39) :- ','(append(X36, X40, X39), find_all_vars2(X38, X40)).\nand substitutionX36 -> T25,\nX37 -> T26,\nX38 -> T27,\nT17 -> .(=(T25, T26), T27),\nX23 -> X41,\nX39 -> X41" }, { "from": 24, "to": 37, "label": "EVAL-BACKTRACK" }, { "from": 28, "to": 34, "label": "SUCCESS" }, { "from": 36, "to": 40, "label": "SPLIT 1" }, { "from": 36, "to": 41, "label": "SPLIT 2\nnew knowledge:\nT25 is ground\nreplacements:X40 -> T28,\nX41 -> T29" }, { "from": 40, "to": 44, "label": "CASE" }, { "from": 41, "to": 70, "label": "CASE" }, { "from": 44, "to": 46, "label": "PARALLEL" }, { "from": 44, "to": 47, "label": "PARALLEL" }, { "from": 46, "to": 50, "label": "EVAL with clause\nappend([], X58, X58).\nand substitutionT25 -> [],\nX40 -> X59,\nX58 -> X59,\nX41 -> X59" }, { "from": 46, "to": 51, "label": "EVAL-BACKTRACK" }, { "from": 47, "to": 56, "label": "EVAL with clause\nappend(.(X72, X73), X74, .(X72, X75)) :- append(X73, X74, X75).\nand substitutionX72 -> T34,\nX73 -> T35,\nT25 -> .(T34, T35),\nX40 -> X76,\nX74 -> X76,\nX75 -> X77,\nX41 -> .(T34, X77)" }, { "from": 47, "to": 57, "label": "EVAL-BACKTRACK" }, { "from": 50, "to": 52, "label": "SUCCESS" }, { "from": 56, "to": 40, "label": "INSTANCE with matching:\nT25 -> T35\nX40 -> X76\nX41 -> X77" }, { "from": 70, "to": 71, "label": "PARALLEL" }, { "from": 70, "to": 72, "label": "PARALLEL" }, { "from": 71, "to": 73, "label": "EVAL with clause\nfind_all_vars2([], []).\nand substitutionT27 -> [],\nT28 -> []" }, { "from": 71, "to": 74, "label": "EVAL-BACKTRACK" }, { "from": 72, "to": 81, "label": "EVAL with clause\nfind_all_vars2(.(=(X91, X92), X93), X94) :- ','(append(X91, X95, X94), find_all_vars2(X93, X95)).\nand substitutionX91 -> T44,\nX92 -> T45,\nX93 -> T46,\nT27 -> .(=(T44, T45), T46),\nT28 -> T48,\nX94 -> T48,\nT47 -> T48" }, { "from": 72, "to": 82, "label": "EVAL-BACKTRACK" }, { "from": 73, "to": 76, "label": "SUCCESS" }, { "from": 81, "to": 86, "label": "SPLIT 1" }, { "from": 81, "to": 87, "label": "SPLIT 2\nnew knowledge:\nT44 is ground\nreplacements:X95 -> T51" }, { "from": 86, "to": 90, "label": "CASE" }, { "from": 87, "to": 41, "label": "INSTANCE with matching:\nT27 -> T46\nT28 -> T51" }, { "from": 90, "to": 91, "label": "PARALLEL" }, { "from": 90, "to": 92, "label": "PARALLEL" }, { "from": 91, "to": 96, "label": "EVAL with clause\nappend([], X112, X112).\nand substitutionT44 -> [],\nX95 -> T58,\nX112 -> T58,\nT48 -> T58,\nX113 -> T58" }, { "from": 91, "to": 97, "label": "EVAL-BACKTRACK" }, { "from": 92, "to": 108, "label": "EVAL with clause\nappend(.(X124, X125), X126, .(X124, X127)) :- append(X125, X126, X127).\nand substitutionX124 -> T65,\nX125 -> T66,\nT44 -> .(T65, T66),\nX95 -> X128,\nX126 -> X128,\nX127 -> T68,\nT48 -> .(T65, T68),\nT67 -> T68" }, { "from": 92, "to": 109, "label": "EVAL-BACKTRACK" }, { "from": 96, "to": 99, "label": "SUCCESS" }, { "from": 108, "to": 86, "label": "INSTANCE with matching:\nT44 -> T66\nX95 -> X128\nT48 -> T68" } ], "type": "Graph" } } ---------------------------------------- (2) Obligation: Triples: appendA(.(X1, X2), X3, .(X1, X4)) :- appendA(X2, X3, X4). find_all_vars2B(.(=(X1, X2), X3), X4) :- appendC(X1, X5, X4). find_all_vars2B(.(=(X1, X2), X3), X4) :- ','(appendcC(X1, X5, X4), find_all_vars2B(X3, X5)). appendC(.(X1, X2), X3, .(X1, X4)) :- appendC(X2, X3, X4). init_varsE(.(=(X1, X2), X3), X4, X5, X6) :- appendA(X1, X7, X8). init_varsE(.(=(X1, X2), X3), X4, X5, X6) :- ','(appendcA(X1, X7, X8), find_all_vars2B(X3, X7)). Clauses: appendcA([], X1, X1). appendcA(.(X1, X2), X3, .(X1, X4)) :- appendcA(X2, X3, X4). find_all_vars2cB([], []). find_all_vars2cB(.(=(X1, X2), X3), X4) :- ','(appendcC(X1, X5, X4), find_all_vars2cB(X3, X5)). appendcC([], X1, X1). appendcC(.(X1, X2), X3, .(X1, X4)) :- appendcC(X2, X3, X4). find_all_vars2cD([], []). find_all_vars2cD(.(=(X1, X2), X3), X4) :- ','(appendcA(X1, X5, X4), find_all_vars2cB(X3, X5)). Afs: init_varsE(x1, x2, x3, x4) = init_varsE(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: init_varsE_in_4: (b,b,f,f) appendA_in_3: (b,f,f) appendcA_in_3: (b,f,f) find_all_vars2B_in_2: (b,f) appendC_in_3: (b,f,f) appendcC_in_3: (b,f,f) Transforming TRIPLES into the following Term Rewriting System: Pi DP problem: The TRS P consists of the following rules: INIT_VARSE_IN_GGAA(.(=(X1, X2), X3), X4, X5, X6) -> U6_GGAA(X1, X2, X3, X4, X5, X6, appendA_in_gaa(X1, X7, X8)) INIT_VARSE_IN_GGAA(.(=(X1, X2), X3), X4, X5, X6) -> APPENDA_IN_GAA(X1, X7, X8) APPENDA_IN_GAA(.(X1, X2), X3, .(X1, X4)) -> U1_GAA(X1, X2, X3, X4, appendA_in_gaa(X2, X3, X4)) APPENDA_IN_GAA(.(X1, X2), X3, .(X1, X4)) -> APPENDA_IN_GAA(X2, X3, X4) INIT_VARSE_IN_GGAA(.(=(X1, X2), X3), X4, X5, X6) -> U7_GGAA(X1, X2, X3, X4, X5, X6, appendcA_in_gaa(X1, X7, X8)) U7_GGAA(X1, X2, X3, X4, X5, X6, appendcA_out_gaa(X1, X7, X8)) -> U8_GGAA(X1, X2, X3, X4, X5, X6, find_all_vars2B_in_ga(X3, X7)) U7_GGAA(X1, X2, X3, X4, X5, X6, appendcA_out_gaa(X1, X7, X8)) -> FIND_ALL_VARS2B_IN_GA(X3, X7) FIND_ALL_VARS2B_IN_GA(.(=(X1, X2), X3), X4) -> U2_GA(X1, X2, X3, X4, appendC_in_gaa(X1, X5, X4)) FIND_ALL_VARS2B_IN_GA(.(=(X1, X2), X3), X4) -> APPENDC_IN_GAA(X1, X5, X4) APPENDC_IN_GAA(.(X1, X2), X3, .(X1, X4)) -> U5_GAA(X1, X2, X3, X4, appendC_in_gaa(X2, X3, X4)) APPENDC_IN_GAA(.(X1, X2), X3, .(X1, X4)) -> APPENDC_IN_GAA(X2, X3, X4) FIND_ALL_VARS2B_IN_GA(.(=(X1, X2), X3), X4) -> U3_GA(X1, X2, X3, X4, appendcC_in_gaa(X1, X5, X4)) U3_GA(X1, X2, X3, X4, appendcC_out_gaa(X1, X5, X4)) -> U4_GA(X1, X2, X3, X4, find_all_vars2B_in_ga(X3, X5)) U3_GA(X1, X2, X3, X4, appendcC_out_gaa(X1, X5, X4)) -> FIND_ALL_VARS2B_IN_GA(X3, X5) The TRS R consists of the following rules: appendcA_in_gaa([], X1, X1) -> appendcA_out_gaa([], X1, X1) appendcA_in_gaa(.(X1, X2), X3, .(X1, X4)) -> U10_gaa(X1, X2, X3, X4, appendcA_in_gaa(X2, X3, X4)) U10_gaa(X1, X2, X3, X4, appendcA_out_gaa(X2, X3, X4)) -> appendcA_out_gaa(.(X1, X2), X3, .(X1, X4)) appendcC_in_gaa([], X1, X1) -> appendcC_out_gaa([], X1, X1) appendcC_in_gaa(.(X1, X2), X3, .(X1, X4)) -> U13_gaa(X1, X2, X3, X4, appendcC_in_gaa(X2, X3, X4)) U13_gaa(X1, X2, X3, X4, appendcC_out_gaa(X2, X3, X4)) -> appendcC_out_gaa(.(X1, X2), X3, .(X1, X4)) The argument filtering Pi contains the following mapping: .(x1, x2) = .(x1, x2) =(x1, x2) = =(x1, x2) appendA_in_gaa(x1, x2, x3) = appendA_in_gaa(x1) appendcA_in_gaa(x1, x2, x3) = appendcA_in_gaa(x1) [] = [] appendcA_out_gaa(x1, x2, x3) = appendcA_out_gaa(x1) U10_gaa(x1, x2, x3, x4, x5) = U10_gaa(x1, x2, x5) find_all_vars2B_in_ga(x1, x2) = find_all_vars2B_in_ga(x1) appendC_in_gaa(x1, x2, x3) = appendC_in_gaa(x1) appendcC_in_gaa(x1, x2, x3) = appendcC_in_gaa(x1) appendcC_out_gaa(x1, x2, x3) = appendcC_out_gaa(x1) U13_gaa(x1, x2, x3, x4, x5) = U13_gaa(x1, x2, x5) INIT_VARSE_IN_GGAA(x1, x2, x3, x4) = INIT_VARSE_IN_GGAA(x1, x2) U6_GGAA(x1, x2, x3, x4, x5, x6, x7) = U6_GGAA(x1, x2, x3, x4, x7) APPENDA_IN_GAA(x1, x2, x3) = APPENDA_IN_GAA(x1) U1_GAA(x1, x2, x3, x4, x5) = U1_GAA(x1, x2, x5) U7_GGAA(x1, x2, x3, x4, x5, x6, x7) = U7_GGAA(x1, x2, x3, x4, x7) U8_GGAA(x1, x2, x3, x4, x5, x6, x7) = U8_GGAA(x1, x2, x3, x4, x7) FIND_ALL_VARS2B_IN_GA(x1, x2) = FIND_ALL_VARS2B_IN_GA(x1) U2_GA(x1, x2, x3, x4, x5) = U2_GA(x1, x2, x3, x5) APPENDC_IN_GAA(x1, x2, x3) = APPENDC_IN_GAA(x1) U5_GAA(x1, x2, x3, x4, x5) = U5_GAA(x1, x2, x5) U3_GA(x1, x2, x3, x4, x5) = U3_GA(x1, x2, x3, x5) U4_GA(x1, x2, x3, x4, x5) = U4_GA(x1, x2, x3, 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: INIT_VARSE_IN_GGAA(.(=(X1, X2), X3), X4, X5, X6) -> U6_GGAA(X1, X2, X3, X4, X5, X6, appendA_in_gaa(X1, X7, X8)) INIT_VARSE_IN_GGAA(.(=(X1, X2), X3), X4, X5, X6) -> APPENDA_IN_GAA(X1, X7, X8) APPENDA_IN_GAA(.(X1, X2), X3, .(X1, X4)) -> U1_GAA(X1, X2, X3, X4, appendA_in_gaa(X2, X3, X4)) APPENDA_IN_GAA(.(X1, X2), X3, .(X1, X4)) -> APPENDA_IN_GAA(X2, X3, X4) INIT_VARSE_IN_GGAA(.(=(X1, X2), X3), X4, X5, X6) -> U7_GGAA(X1, X2, X3, X4, X5, X6, appendcA_in_gaa(X1, X7, X8)) U7_GGAA(X1, X2, X3, X4, X5, X6, appendcA_out_gaa(X1, X7, X8)) -> U8_GGAA(X1, X2, X3, X4, X5, X6, find_all_vars2B_in_ga(X3, X7)) U7_GGAA(X1, X2, X3, X4, X5, X6, appendcA_out_gaa(X1, X7, X8)) -> FIND_ALL_VARS2B_IN_GA(X3, X7) FIND_ALL_VARS2B_IN_GA(.(=(X1, X2), X3), X4) -> U2_GA(X1, X2, X3, X4, appendC_in_gaa(X1, X5, X4)) FIND_ALL_VARS2B_IN_GA(.(=(X1, X2), X3), X4) -> APPENDC_IN_GAA(X1, X5, X4) APPENDC_IN_GAA(.(X1, X2), X3, .(X1, X4)) -> U5_GAA(X1, X2, X3, X4, appendC_in_gaa(X2, X3, X4)) APPENDC_IN_GAA(.(X1, X2), X3, .(X1, X4)) -> APPENDC_IN_GAA(X2, X3, X4) FIND_ALL_VARS2B_IN_GA(.(=(X1, X2), X3), X4) -> U3_GA(X1, X2, X3, X4, appendcC_in_gaa(X1, X5, X4)) U3_GA(X1, X2, X3, X4, appendcC_out_gaa(X1, X5, X4)) -> U4_GA(X1, X2, X3, X4, find_all_vars2B_in_ga(X3, X5)) U3_GA(X1, X2, X3, X4, appendcC_out_gaa(X1, X5, X4)) -> FIND_ALL_VARS2B_IN_GA(X3, X5) The TRS R consists of the following rules: appendcA_in_gaa([], X1, X1) -> appendcA_out_gaa([], X1, X1) appendcA_in_gaa(.(X1, X2), X3, .(X1, X4)) -> U10_gaa(X1, X2, X3, X4, appendcA_in_gaa(X2, X3, X4)) U10_gaa(X1, X2, X3, X4, appendcA_out_gaa(X2, X3, X4)) -> appendcA_out_gaa(.(X1, X2), X3, .(X1, X4)) appendcC_in_gaa([], X1, X1) -> appendcC_out_gaa([], X1, X1) appendcC_in_gaa(.(X1, X2), X3, .(X1, X4)) -> U13_gaa(X1, X2, X3, X4, appendcC_in_gaa(X2, X3, X4)) U13_gaa(X1, X2, X3, X4, appendcC_out_gaa(X2, X3, X4)) -> appendcC_out_gaa(.(X1, X2), X3, .(X1, X4)) The argument filtering Pi contains the following mapping: .(x1, x2) = .(x1, x2) =(x1, x2) = =(x1, x2) appendA_in_gaa(x1, x2, x3) = appendA_in_gaa(x1) appendcA_in_gaa(x1, x2, x3) = appendcA_in_gaa(x1) [] = [] appendcA_out_gaa(x1, x2, x3) = appendcA_out_gaa(x1) U10_gaa(x1, x2, x3, x4, x5) = U10_gaa(x1, x2, x5) find_all_vars2B_in_ga(x1, x2) = find_all_vars2B_in_ga(x1) appendC_in_gaa(x1, x2, x3) = appendC_in_gaa(x1) appendcC_in_gaa(x1, x2, x3) = appendcC_in_gaa(x1) appendcC_out_gaa(x1, x2, x3) = appendcC_out_gaa(x1) U13_gaa(x1, x2, x3, x4, x5) = U13_gaa(x1, x2, x5) INIT_VARSE_IN_GGAA(x1, x2, x3, x4) = INIT_VARSE_IN_GGAA(x1, x2) U6_GGAA(x1, x2, x3, x4, x5, x6, x7) = U6_GGAA(x1, x2, x3, x4, x7) APPENDA_IN_GAA(x1, x2, x3) = APPENDA_IN_GAA(x1) U1_GAA(x1, x2, x3, x4, x5) = U1_GAA(x1, x2, x5) U7_GGAA(x1, x2, x3, x4, x5, x6, x7) = U7_GGAA(x1, x2, x3, x4, x7) U8_GGAA(x1, x2, x3, x4, x5, x6, x7) = U8_GGAA(x1, x2, x3, x4, x7) FIND_ALL_VARS2B_IN_GA(x1, x2) = FIND_ALL_VARS2B_IN_GA(x1) U2_GA(x1, x2, x3, x4, x5) = U2_GA(x1, x2, x3, x5) APPENDC_IN_GAA(x1, x2, x3) = APPENDC_IN_GAA(x1) U5_GAA(x1, x2, x3, x4, x5) = U5_GAA(x1, x2, x5) U3_GA(x1, x2, x3, x4, x5) = U3_GA(x1, x2, x3, x5) U4_GA(x1, x2, x3, x4, x5) = U4_GA(x1, x2, x3, x5) We have to consider all (P,R,Pi)-chains ---------------------------------------- (5) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LOPSTR] contains 3 SCCs with 10 less nodes. ---------------------------------------- (6) Complex Obligation (AND) ---------------------------------------- (7) Obligation: Pi DP problem: The TRS P consists of the following rules: APPENDC_IN_GAA(.(X1, X2), X3, .(X1, X4)) -> APPENDC_IN_GAA(X2, X3, X4) The TRS R consists of the following rules: appendcA_in_gaa([], X1, X1) -> appendcA_out_gaa([], X1, X1) appendcA_in_gaa(.(X1, X2), X3, .(X1, X4)) -> U10_gaa(X1, X2, X3, X4, appendcA_in_gaa(X2, X3, X4)) U10_gaa(X1, X2, X3, X4, appendcA_out_gaa(X2, X3, X4)) -> appendcA_out_gaa(.(X1, X2), X3, .(X1, X4)) appendcC_in_gaa([], X1, X1) -> appendcC_out_gaa([], X1, X1) appendcC_in_gaa(.(X1, X2), X3, .(X1, X4)) -> U13_gaa(X1, X2, X3, X4, appendcC_in_gaa(X2, X3, X4)) U13_gaa(X1, X2, X3, X4, appendcC_out_gaa(X2, X3, X4)) -> appendcC_out_gaa(.(X1, X2), X3, .(X1, X4)) The argument filtering Pi contains the following mapping: .(x1, x2) = .(x1, x2) appendcA_in_gaa(x1, x2, x3) = appendcA_in_gaa(x1) [] = [] appendcA_out_gaa(x1, x2, x3) = appendcA_out_gaa(x1) U10_gaa(x1, x2, x3, x4, x5) = U10_gaa(x1, x2, x5) appendcC_in_gaa(x1, x2, x3) = appendcC_in_gaa(x1) appendcC_out_gaa(x1, x2, x3) = appendcC_out_gaa(x1) U13_gaa(x1, x2, x3, x4, x5) = U13_gaa(x1, x2, x5) APPENDC_IN_GAA(x1, x2, x3) = APPENDC_IN_GAA(x1) 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: APPENDC_IN_GAA(.(X1, X2), X3, .(X1, X4)) -> APPENDC_IN_GAA(X2, X3, X4) R is empty. The argument filtering Pi contains the following mapping: .(x1, x2) = .(x1, x2) APPENDC_IN_GAA(x1, x2, x3) = APPENDC_IN_GAA(x1) 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: APPENDC_IN_GAA(.(X1, X2)) -> APPENDC_IN_GAA(X2) 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: *APPENDC_IN_GAA(.(X1, X2)) -> APPENDC_IN_GAA(X2) The graph contains the following edges 1 > 1 ---------------------------------------- (13) YES ---------------------------------------- (14) Obligation: Pi DP problem: The TRS P consists of the following rules: FIND_ALL_VARS2B_IN_GA(.(=(X1, X2), X3), X4) -> U3_GA(X1, X2, X3, X4, appendcC_in_gaa(X1, X5, X4)) U3_GA(X1, X2, X3, X4, appendcC_out_gaa(X1, X5, X4)) -> FIND_ALL_VARS2B_IN_GA(X3, X5) The TRS R consists of the following rules: appendcA_in_gaa([], X1, X1) -> appendcA_out_gaa([], X1, X1) appendcA_in_gaa(.(X1, X2), X3, .(X1, X4)) -> U10_gaa(X1, X2, X3, X4, appendcA_in_gaa(X2, X3, X4)) U10_gaa(X1, X2, X3, X4, appendcA_out_gaa(X2, X3, X4)) -> appendcA_out_gaa(.(X1, X2), X3, .(X1, X4)) appendcC_in_gaa([], X1, X1) -> appendcC_out_gaa([], X1, X1) appendcC_in_gaa(.(X1, X2), X3, .(X1, X4)) -> U13_gaa(X1, X2, X3, X4, appendcC_in_gaa(X2, X3, X4)) U13_gaa(X1, X2, X3, X4, appendcC_out_gaa(X2, X3, X4)) -> appendcC_out_gaa(.(X1, X2), X3, .(X1, X4)) The argument filtering Pi contains the following mapping: .(x1, x2) = .(x1, x2) =(x1, x2) = =(x1, x2) appendcA_in_gaa(x1, x2, x3) = appendcA_in_gaa(x1) [] = [] appendcA_out_gaa(x1, x2, x3) = appendcA_out_gaa(x1) U10_gaa(x1, x2, x3, x4, x5) = U10_gaa(x1, x2, x5) appendcC_in_gaa(x1, x2, x3) = appendcC_in_gaa(x1) appendcC_out_gaa(x1, x2, x3) = appendcC_out_gaa(x1) U13_gaa(x1, x2, x3, x4, x5) = U13_gaa(x1, x2, x5) FIND_ALL_VARS2B_IN_GA(x1, x2) = FIND_ALL_VARS2B_IN_GA(x1) U3_GA(x1, x2, x3, x4, x5) = U3_GA(x1, x2, x3, x5) 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: FIND_ALL_VARS2B_IN_GA(.(=(X1, X2), X3), X4) -> U3_GA(X1, X2, X3, X4, appendcC_in_gaa(X1, X5, X4)) U3_GA(X1, X2, X3, X4, appendcC_out_gaa(X1, X5, X4)) -> FIND_ALL_VARS2B_IN_GA(X3, X5) The TRS R consists of the following rules: appendcC_in_gaa([], X1, X1) -> appendcC_out_gaa([], X1, X1) appendcC_in_gaa(.(X1, X2), X3, .(X1, X4)) -> U13_gaa(X1, X2, X3, X4, appendcC_in_gaa(X2, X3, X4)) U13_gaa(X1, X2, X3, X4, appendcC_out_gaa(X2, X3, X4)) -> appendcC_out_gaa(.(X1, X2), X3, .(X1, X4)) The argument filtering Pi contains the following mapping: .(x1, x2) = .(x1, x2) =(x1, x2) = =(x1, x2) [] = [] appendcC_in_gaa(x1, x2, x3) = appendcC_in_gaa(x1) appendcC_out_gaa(x1, x2, x3) = appendcC_out_gaa(x1) U13_gaa(x1, x2, x3, x4, x5) = U13_gaa(x1, x2, x5) FIND_ALL_VARS2B_IN_GA(x1, x2) = FIND_ALL_VARS2B_IN_GA(x1) U3_GA(x1, x2, x3, x4, x5) = U3_GA(x1, x2, x3, x5) 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: FIND_ALL_VARS2B_IN_GA(.(=(X1, X2), X3)) -> U3_GA(X1, X2, X3, appendcC_in_gaa(X1)) U3_GA(X1, X2, X3, appendcC_out_gaa(X1)) -> FIND_ALL_VARS2B_IN_GA(X3) The TRS R consists of the following rules: appendcC_in_gaa([]) -> appendcC_out_gaa([]) appendcC_in_gaa(.(X1, X2)) -> U13_gaa(X1, X2, appendcC_in_gaa(X2)) U13_gaa(X1, X2, appendcC_out_gaa(X2)) -> appendcC_out_gaa(.(X1, X2)) The set Q consists of the following terms: appendcC_in_gaa(x0) U13_gaa(x0, x1, x2) 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: *U3_GA(X1, X2, X3, appendcC_out_gaa(X1)) -> FIND_ALL_VARS2B_IN_GA(X3) The graph contains the following edges 3 >= 1 *FIND_ALL_VARS2B_IN_GA(.(=(X1, X2), X3)) -> U3_GA(X1, X2, X3, appendcC_in_gaa(X1)) The graph contains the following edges 1 > 1, 1 > 2, 1 > 3 ---------------------------------------- (20) YES ---------------------------------------- (21) Obligation: Pi DP problem: The TRS P consists of the following rules: APPENDA_IN_GAA(.(X1, X2), X3, .(X1, X4)) -> APPENDA_IN_GAA(X2, X3, X4) The TRS R consists of the following rules: appendcA_in_gaa([], X1, X1) -> appendcA_out_gaa([], X1, X1) appendcA_in_gaa(.(X1, X2), X3, .(X1, X4)) -> U10_gaa(X1, X2, X3, X4, appendcA_in_gaa(X2, X3, X4)) U10_gaa(X1, X2, X3, X4, appendcA_out_gaa(X2, X3, X4)) -> appendcA_out_gaa(.(X1, X2), X3, .(X1, X4)) appendcC_in_gaa([], X1, X1) -> appendcC_out_gaa([], X1, X1) appendcC_in_gaa(.(X1, X2), X3, .(X1, X4)) -> U13_gaa(X1, X2, X3, X4, appendcC_in_gaa(X2, X3, X4)) U13_gaa(X1, X2, X3, X4, appendcC_out_gaa(X2, X3, X4)) -> appendcC_out_gaa(.(X1, X2), X3, .(X1, X4)) The argument filtering Pi contains the following mapping: .(x1, x2) = .(x1, x2) appendcA_in_gaa(x1, x2, x3) = appendcA_in_gaa(x1) [] = [] appendcA_out_gaa(x1, x2, x3) = appendcA_out_gaa(x1) U10_gaa(x1, x2, x3, x4, x5) = U10_gaa(x1, x2, x5) appendcC_in_gaa(x1, x2, x3) = appendcC_in_gaa(x1) appendcC_out_gaa(x1, x2, x3) = appendcC_out_gaa(x1) U13_gaa(x1, x2, x3, x4, x5) = U13_gaa(x1, x2, x5) APPENDA_IN_GAA(x1, x2, x3) = APPENDA_IN_GAA(x1) We have to consider all (P,R,Pi)-chains ---------------------------------------- (22) UsableRulesProof (EQUIVALENT) For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. ---------------------------------------- (23) Obligation: Pi DP problem: The TRS P consists of the following rules: APPENDA_IN_GAA(.(X1, X2), X3, .(X1, X4)) -> APPENDA_IN_GAA(X2, X3, X4) R is empty. The argument filtering Pi contains the following mapping: .(x1, x2) = .(x1, x2) APPENDA_IN_GAA(x1, x2, x3) = APPENDA_IN_GAA(x1) We have to consider all (P,R,Pi)-chains ---------------------------------------- (24) PiDPToQDPProof (SOUND) Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. ---------------------------------------- (25) Obligation: Q DP problem: The TRS P consists of the following rules: APPENDA_IN_GAA(.(X1, X2)) -> APPENDA_IN_GAA(X2) R is empty. Q is empty. We have to consider all (P,Q,R)-chains. ---------------------------------------- (26) 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_GAA(.(X1, X2)) -> APPENDA_IN_GAA(X2) The graph contains the following edges 1 > 1 ---------------------------------------- (27) YES