YES proof of /export/starexec/sandbox2/benchmark/theBenchmark.pl # AProVE Commit ID: 794c25de1cacf0d048858bcd21c9a779e1221865 marcel 20200619 unpublished dirty Left Termination of the query pattern reverse(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, 1 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: app(.(X, Xs), Ys, .(X, Zs)) :- app(Xs, Ys, Zs). app([], Ys, Ys). reverse(.(X, Xs), Ys) :- ','(reverse(Xs, Zs), app(Zs, .(X, []), Ys)). reverse([], []). Query: reverse(g,a) ---------------------------------------- (1) PrologToDTProblemTransformerProof (SOUND) Built DT problem from termination graph DT10. { "root": 3, "program": { "directives": [], "clauses": [ [ "(app (. X Xs) Ys (. X Zs))", "(app Xs Ys Zs)" ], [ "(app ([]) Ys Ys)", null ], [ "(reverse (. X Xs) Ys)", "(',' (reverse Xs Zs) (app Zs (. X ([])) Ys))" ], [ "(reverse ([]) ([]))", null ] ] }, "graph": { "nodes": { "191": { "goal": [{ "clause": -1, "scope": -1, "term": "(app T22 (. T18 ([])) X30)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T18", "T22" ], "free": ["X30"], "exprvars": [] } }, "192": { "goal": [{ "clause": -1, "scope": -1, "term": "(app T28 (. T6 ([])) T9)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T6", "T28" ], "free": [], "exprvars": [] } }, "193": { "goal": [ { "clause": 0, "scope": 3, "term": "(app T28 (. T6 ([])) T9)" }, { "clause": 1, "scope": 3, "term": "(app T28 (. T6 ([])) T9)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T6", "T28" ], "free": [], "exprvars": [] } }, "type": "Nodes", "194": { "goal": [{ "clause": 0, "scope": 3, "term": "(app T28 (. T6 ([])) T9)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T6", "T28" ], "free": [], "exprvars": [] } }, "195": { "goal": [{ "clause": 1, "scope": 3, "term": "(app T28 (. T6 ([])) T9)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T6", "T28" ], "free": [], "exprvars": [] } }, "196": { "goal": [{ "clause": -1, "scope": -1, "term": "(app T53 (. T54 ([])) T56)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T53", "T54" ], "free": [], "exprvars": [] } }, "197": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "198": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "199": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "31": { "goal": [ { "clause": -1, "scope": -1, "term": "(',' (reverse T7 X7) (app X7 (. T6 ([])) T9))" }, { "clause": 3, "scope": 1, "term": "(reverse (. T6 T7) T2)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T6", "T7" ], "free": ["X7"], "exprvars": [] } }, "32": { "goal": [{ "clause": 3, "scope": 1, "term": "(reverse T1 T2)" }], "kb": { "nonunifying": [[ "(reverse T1 T2)", "(reverse (. X4 X5) X6)" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T1"], "free": [ "X4", "X5", "X6" ], "exprvars": [] } }, "33": { "goal": [ { "clause": 2, "scope": 2, "term": "(',' (reverse T7 X7) (app X7 (. T6 ([])) T9))" }, { "clause": 3, "scope": 2, "term": "(',' (reverse T7 X7) (app X7 (. T6 ([])) T9))" }, { "clause": -1, "scope": 2, "term": null }, { "clause": 3, "scope": 1, "term": "(reverse (. T6 T7) T2)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T6", "T7" ], "free": ["X7"], "exprvars": [] } }, "34": { "goal": [{ "clause": 2, "scope": 2, "term": "(',' (reverse T7 X7) (app X7 (. T6 ([])) T9))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T6", "T7" ], "free": ["X7"], "exprvars": [] } }, "13": { "goal": [ { "clause": 2, "scope": 1, "term": "(reverse T1 T2)" }, { "clause": 3, "scope": 1, "term": "(reverse T1 T2)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T1"], "free": [], "exprvars": [] } }, "35": { "goal": [ { "clause": 3, "scope": 2, "term": "(',' (reverse T7 X7) (app X7 (. T6 ([])) T9))" }, { "clause": -1, "scope": 2, "term": null }, { "clause": 3, "scope": 1, "term": "(reverse (. T6 T7) T2)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T6", "T7" ], "free": ["X7"], "exprvars": [] } }, "36": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (',' (reverse T19 X29) (app X29 (. T18 ([])) X30)) (app X30 (. T6 ([])) T9))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T6", "T18", "T19" ], "free": [ "X30", "X29" ], "exprvars": [] } }, "38": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "39": { "goal": [{ "clause": -1, "scope": -1, "term": "(reverse T19 X29)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T19"], "free": ["X29"], "exprvars": [] } }, "200": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "3": { "goal": [{ "clause": -1, "scope": -1, "term": "(reverse T1 T2)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T1"], "free": [], "exprvars": [] } }, "201": { "goal": [{ "clause": 3, "scope": 2, "term": "(',' (reverse T7 X7) (app X7 (. T6 ([])) T9))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T6", "T7" ], "free": ["X7"], "exprvars": [] } }, "202": { "goal": [ { "clause": -1, "scope": 2, "term": null }, { "clause": 3, "scope": 1, "term": "(reverse (. T6 T7) T2)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T6", "T7" ], "free": [], "exprvars": [] } }, "203": { "goal": [{ "clause": -1, "scope": -1, "term": "(app ([]) (. T6 ([])) T9)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T6"], "free": [], "exprvars": [] } }, "204": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "205": { "goal": [{ "clause": 3, "scope": 1, "term": "(reverse (. T6 T7) T2)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T6", "T7" ], "free": [], "exprvars": [] } }, "206": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "207": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "208": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "209": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "40": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (app T22 (. T18 ([])) X30) (app X30 (. T6 ([])) T9))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T6", "T18", "T22" ], "free": ["X30"], "exprvars": [] } } }, "edges": [ { "from": 3, "to": 13, "label": "CASE" }, { "from": 13, "to": 31, "label": "EVAL with clause\nreverse(.(X4, X5), X6) :- ','(reverse(X5, X7), app(X7, .(X4, []), X6)).\nand substitutionX4 -> T6,\nX5 -> T7,\nT1 -> .(T6, T7),\nT2 -> T9,\nX6 -> T9,\nT8 -> T9" }, { "from": 13, "to": 32, "label": "EVAL-BACKTRACK" }, { "from": 31, "to": 33, "label": "CASE" }, { "from": 32, "to": 207, "label": "EVAL with clause\nreverse([], []).\nand substitutionT1 -> [],\nT2 -> []" }, { "from": 32, "to": 208, "label": "EVAL-BACKTRACK" }, { "from": 33, "to": 34, "label": "PARALLEL" }, { "from": 33, "to": 35, "label": "PARALLEL" }, { "from": 34, "to": 36, "label": "EVAL with clause\nreverse(.(X26, X27), X28) :- ','(reverse(X27, X29), app(X29, .(X26, []), X28)).\nand substitutionX26 -> T18,\nX27 -> T19,\nT7 -> .(T18, T19),\nX7 -> X30,\nX28 -> X30" }, { "from": 34, "to": 38, "label": "EVAL-BACKTRACK" }, { "from": 35, "to": 201, "label": "PARALLEL" }, { "from": 35, "to": 202, "label": "PARALLEL" }, { "from": 36, "to": 39, "label": "SPLIT 1" }, { "from": 36, "to": 40, "label": "SPLIT 2\nnew knowledge:\nT19 is ground\nT22 is ground\nreplacements:X29 -> T22" }, { "from": 39, "to": 3, "label": "INSTANCE with matching:\nT1 -> T19\nT2 -> X29" }, { "from": 40, "to": 191, "label": "SPLIT 1" }, { "from": 40, "to": 192, "label": "SPLIT 2\nnew knowledge:\nT22 is ground\nT18 is ground\nT28 is ground\nreplacements:X30 -> T28" }, { "from": 191, "to": 192, "label": "INSTANCE with matching:\nT28 -> T22\nT6 -> T18\nT9 -> X30" }, { "from": 192, "to": 193, "label": "CASE" }, { "from": 193, "to": 194, "label": "PARALLEL" }, { "from": 193, "to": 195, "label": "PARALLEL" }, { "from": 194, "to": 196, "label": "EVAL with clause\napp(.(X71, X72), X73, .(X71, X74)) :- app(X72, X73, X74).\nand substitutionX71 -> T52,\nX72 -> T53,\nT28 -> .(T52, T53),\nT6 -> T54,\nX73 -> .(T54, []),\nX74 -> T56,\nT9 -> .(T52, T56),\nT55 -> T56" }, { "from": 194, "to": 197, "label": "EVAL-BACKTRACK" }, { "from": 195, "to": 198, "label": "EVAL with clause\napp([], X81, X81).\nand substitutionT28 -> [],\nT6 -> T63,\nX81 -> .(T63, []),\nT9 -> .(T63, [])" }, { "from": 195, "to": 199, "label": "EVAL-BACKTRACK" }, { "from": 196, "to": 192, "label": "INSTANCE with matching:\nT28 -> T53\nT6 -> T54\nT9 -> T56" }, { "from": 198, "to": 200, "label": "SUCCESS" }, { "from": 201, "to": 203, "label": "EVAL with clause\nreverse([], []).\nand substitutionT7 -> [],\nX7 -> []" }, { "from": 201, "to": 204, "label": "EVAL-BACKTRACK" }, { "from": 202, "to": 205, "label": "FAILURE" }, { "from": 203, "to": 192, "label": "INSTANCE with matching:\nT28 -> []" }, { "from": 205, "to": 206, "label": "BACKTRACK\nfor clause: reverse([], [])because of non-unification" }, { "from": 207, "to": 209, "label": "SUCCESS" } ], "type": "Graph" } } ---------------------------------------- (2) Obligation: Triples: appB(.(X1, X2), X3, .(X1, X4)) :- appB(X2, X3, X4). reverseA(.(X1, .(X2, X3)), X4) :- reverseA(X3, X5). reverseA(.(X1, .(X2, X3)), X4) :- ','(reversecA(X3, X5), appB(X5, X2, X6)). reverseA(.(X1, .(X2, X3)), X4) :- ','(reversecA(X3, X5), ','(appcB(X5, X2, X6), appB(X6, X1, X4))). reverseA(.(X1, []), X2) :- appB([], X1, X2). Clauses: reversecA(.(X1, .(X2, X3)), X4) :- ','(reversecA(X3, X5), ','(appcB(X5, X2, X6), appcB(X6, X1, X4))). reversecA(.(X1, []), X2) :- appcB([], X1, X2). reversecA([], []). appcB(.(X1, X2), X3, .(X1, X4)) :- appcB(X2, X3, X4). appcB([], X1, .(X1, [])). Afs: reverseA(x1, x2) = reverseA(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: reverseA_in_2: (b,f) reversecA_in_2: (b,f) appcB_in_3: (b,b,f) appB_in_3: (b,b,f) Transforming TRIPLES into the following Term Rewriting System: Pi DP problem: The TRS P consists of the following rules: REVERSEA_IN_GA(.(X1, .(X2, X3)), X4) -> U2_GA(X1, X2, X3, X4, reverseA_in_ga(X3, X5)) REVERSEA_IN_GA(.(X1, .(X2, X3)), X4) -> REVERSEA_IN_GA(X3, X5) REVERSEA_IN_GA(.(X1, .(X2, X3)), X4) -> U3_GA(X1, X2, X3, X4, reversecA_in_ga(X3, X5)) U3_GA(X1, X2, X3, X4, reversecA_out_ga(X3, X5)) -> U4_GA(X1, X2, X3, X4, appB_in_gga(X5, X2, X6)) U3_GA(X1, X2, X3, X4, reversecA_out_ga(X3, X5)) -> APPB_IN_GGA(X5, X2, X6) APPB_IN_GGA(.(X1, X2), X3, .(X1, X4)) -> U1_GGA(X1, X2, X3, X4, appB_in_gga(X2, X3, X4)) APPB_IN_GGA(.(X1, X2), X3, .(X1, X4)) -> APPB_IN_GGA(X2, X3, X4) U3_GA(X1, X2, X3, X4, reversecA_out_ga(X3, X5)) -> U5_GA(X1, X2, X3, X4, appcB_in_gga(X5, X2, X6)) U5_GA(X1, X2, X3, X4, appcB_out_gga(X5, X2, X6)) -> U6_GA(X1, X2, X3, X4, appB_in_gga(X6, X1, X4)) U5_GA(X1, X2, X3, X4, appcB_out_gga(X5, X2, X6)) -> APPB_IN_GGA(X6, X1, X4) REVERSEA_IN_GA(.(X1, []), X2) -> U7_GA(X1, X2, appB_in_gga([], X1, X2)) REVERSEA_IN_GA(.(X1, []), X2) -> APPB_IN_GGA([], X1, X2) The TRS R consists of the following rules: reversecA_in_ga(.(X1, .(X2, X3)), X4) -> U9_ga(X1, X2, X3, X4, reversecA_in_ga(X3, X5)) reversecA_in_ga(.(X1, []), X2) -> U12_ga(X1, X2, appcB_in_gga([], X1, X2)) appcB_in_gga(.(X1, X2), X3, .(X1, X4)) -> U13_gga(X1, X2, X3, X4, appcB_in_gga(X2, X3, X4)) appcB_in_gga([], X1, .(X1, [])) -> appcB_out_gga([], X1, .(X1, [])) U13_gga(X1, X2, X3, X4, appcB_out_gga(X2, X3, X4)) -> appcB_out_gga(.(X1, X2), X3, .(X1, X4)) U12_ga(X1, X2, appcB_out_gga([], X1, X2)) -> reversecA_out_ga(.(X1, []), X2) reversecA_in_ga([], []) -> reversecA_out_ga([], []) U9_ga(X1, X2, X3, X4, reversecA_out_ga(X3, X5)) -> U10_ga(X1, X2, X3, X4, appcB_in_gga(X5, X2, X6)) U10_ga(X1, X2, X3, X4, appcB_out_gga(X5, X2, X6)) -> U11_ga(X1, X2, X3, X4, appcB_in_gga(X6, X1, X4)) U11_ga(X1, X2, X3, X4, appcB_out_gga(X6, X1, X4)) -> reversecA_out_ga(.(X1, .(X2, X3)), X4) The argument filtering Pi contains the following mapping: reverseA_in_ga(x1, x2) = reverseA_in_ga(x1) .(x1, x2) = .(x1, x2) reversecA_in_ga(x1, x2) = reversecA_in_ga(x1) U9_ga(x1, x2, x3, x4, x5) = U9_ga(x1, x2, x3, x5) [] = [] U12_ga(x1, x2, x3) = U12_ga(x1, x3) appcB_in_gga(x1, x2, x3) = appcB_in_gga(x1, x2) U13_gga(x1, x2, x3, x4, x5) = U13_gga(x1, x2, x3, x5) appcB_out_gga(x1, x2, x3) = appcB_out_gga(x1, x2, x3) reversecA_out_ga(x1, x2) = reversecA_out_ga(x1, x2) U10_ga(x1, x2, x3, x4, x5) = U10_ga(x1, x2, x3, x5) U11_ga(x1, x2, x3, x4, x5) = U11_ga(x1, x2, x3, x5) appB_in_gga(x1, x2, x3) = appB_in_gga(x1, x2) REVERSEA_IN_GA(x1, x2) = REVERSEA_IN_GA(x1) U2_GA(x1, x2, x3, x4, x5) = U2_GA(x1, x2, x3, 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) APPB_IN_GGA(x1, x2, x3) = APPB_IN_GGA(x1, x2) U1_GGA(x1, x2, x3, x4, x5) = U1_GGA(x1, x2, x3, x5) U5_GA(x1, x2, x3, x4, x5) = U5_GA(x1, x2, x3, x5) U6_GA(x1, x2, x3, x4, x5) = U6_GA(x1, x2, x3, x5) U7_GA(x1, x2, x3) = U7_GA(x1, x3) 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: REVERSEA_IN_GA(.(X1, .(X2, X3)), X4) -> U2_GA(X1, X2, X3, X4, reverseA_in_ga(X3, X5)) REVERSEA_IN_GA(.(X1, .(X2, X3)), X4) -> REVERSEA_IN_GA(X3, X5) REVERSEA_IN_GA(.(X1, .(X2, X3)), X4) -> U3_GA(X1, X2, X3, X4, reversecA_in_ga(X3, X5)) U3_GA(X1, X2, X3, X4, reversecA_out_ga(X3, X5)) -> U4_GA(X1, X2, X3, X4, appB_in_gga(X5, X2, X6)) U3_GA(X1, X2, X3, X4, reversecA_out_ga(X3, X5)) -> APPB_IN_GGA(X5, X2, X6) APPB_IN_GGA(.(X1, X2), X3, .(X1, X4)) -> U1_GGA(X1, X2, X3, X4, appB_in_gga(X2, X3, X4)) APPB_IN_GGA(.(X1, X2), X3, .(X1, X4)) -> APPB_IN_GGA(X2, X3, X4) U3_GA(X1, X2, X3, X4, reversecA_out_ga(X3, X5)) -> U5_GA(X1, X2, X3, X4, appcB_in_gga(X5, X2, X6)) U5_GA(X1, X2, X3, X4, appcB_out_gga(X5, X2, X6)) -> U6_GA(X1, X2, X3, X4, appB_in_gga(X6, X1, X4)) U5_GA(X1, X2, X3, X4, appcB_out_gga(X5, X2, X6)) -> APPB_IN_GGA(X6, X1, X4) REVERSEA_IN_GA(.(X1, []), X2) -> U7_GA(X1, X2, appB_in_gga([], X1, X2)) REVERSEA_IN_GA(.(X1, []), X2) -> APPB_IN_GGA([], X1, X2) The TRS R consists of the following rules: reversecA_in_ga(.(X1, .(X2, X3)), X4) -> U9_ga(X1, X2, X3, X4, reversecA_in_ga(X3, X5)) reversecA_in_ga(.(X1, []), X2) -> U12_ga(X1, X2, appcB_in_gga([], X1, X2)) appcB_in_gga(.(X1, X2), X3, .(X1, X4)) -> U13_gga(X1, X2, X3, X4, appcB_in_gga(X2, X3, X4)) appcB_in_gga([], X1, .(X1, [])) -> appcB_out_gga([], X1, .(X1, [])) U13_gga(X1, X2, X3, X4, appcB_out_gga(X2, X3, X4)) -> appcB_out_gga(.(X1, X2), X3, .(X1, X4)) U12_ga(X1, X2, appcB_out_gga([], X1, X2)) -> reversecA_out_ga(.(X1, []), X2) reversecA_in_ga([], []) -> reversecA_out_ga([], []) U9_ga(X1, X2, X3, X4, reversecA_out_ga(X3, X5)) -> U10_ga(X1, X2, X3, X4, appcB_in_gga(X5, X2, X6)) U10_ga(X1, X2, X3, X4, appcB_out_gga(X5, X2, X6)) -> U11_ga(X1, X2, X3, X4, appcB_in_gga(X6, X1, X4)) U11_ga(X1, X2, X3, X4, appcB_out_gga(X6, X1, X4)) -> reversecA_out_ga(.(X1, .(X2, X3)), X4) The argument filtering Pi contains the following mapping: reverseA_in_ga(x1, x2) = reverseA_in_ga(x1) .(x1, x2) = .(x1, x2) reversecA_in_ga(x1, x2) = reversecA_in_ga(x1) U9_ga(x1, x2, x3, x4, x5) = U9_ga(x1, x2, x3, x5) [] = [] U12_ga(x1, x2, x3) = U12_ga(x1, x3) appcB_in_gga(x1, x2, x3) = appcB_in_gga(x1, x2) U13_gga(x1, x2, x3, x4, x5) = U13_gga(x1, x2, x3, x5) appcB_out_gga(x1, x2, x3) = appcB_out_gga(x1, x2, x3) reversecA_out_ga(x1, x2) = reversecA_out_ga(x1, x2) U10_ga(x1, x2, x3, x4, x5) = U10_ga(x1, x2, x3, x5) U11_ga(x1, x2, x3, x4, x5) = U11_ga(x1, x2, x3, x5) appB_in_gga(x1, x2, x3) = appB_in_gga(x1, x2) REVERSEA_IN_GA(x1, x2) = REVERSEA_IN_GA(x1) U2_GA(x1, x2, x3, x4, x5) = U2_GA(x1, x2, x3, 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) APPB_IN_GGA(x1, x2, x3) = APPB_IN_GGA(x1, x2) U1_GGA(x1, x2, x3, x4, x5) = U1_GGA(x1, x2, x3, x5) U5_GA(x1, x2, x3, x4, x5) = U5_GA(x1, x2, x3, x5) U6_GA(x1, x2, x3, x4, x5) = U6_GA(x1, x2, x3, x5) U7_GA(x1, x2, x3) = U7_GA(x1, x3) We have to consider all (P,R,Pi)-chains ---------------------------------------- (5) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LOPSTR] contains 2 SCCs with 10 less nodes. ---------------------------------------- (6) Complex Obligation (AND) ---------------------------------------- (7) Obligation: Pi DP problem: The TRS P consists of the following rules: APPB_IN_GGA(.(X1, X2), X3, .(X1, X4)) -> APPB_IN_GGA(X2, X3, X4) The TRS R consists of the following rules: reversecA_in_ga(.(X1, .(X2, X3)), X4) -> U9_ga(X1, X2, X3, X4, reversecA_in_ga(X3, X5)) reversecA_in_ga(.(X1, []), X2) -> U12_ga(X1, X2, appcB_in_gga([], X1, X2)) appcB_in_gga(.(X1, X2), X3, .(X1, X4)) -> U13_gga(X1, X2, X3, X4, appcB_in_gga(X2, X3, X4)) appcB_in_gga([], X1, .(X1, [])) -> appcB_out_gga([], X1, .(X1, [])) U13_gga(X1, X2, X3, X4, appcB_out_gga(X2, X3, X4)) -> appcB_out_gga(.(X1, X2), X3, .(X1, X4)) U12_ga(X1, X2, appcB_out_gga([], X1, X2)) -> reversecA_out_ga(.(X1, []), X2) reversecA_in_ga([], []) -> reversecA_out_ga([], []) U9_ga(X1, X2, X3, X4, reversecA_out_ga(X3, X5)) -> U10_ga(X1, X2, X3, X4, appcB_in_gga(X5, X2, X6)) U10_ga(X1, X2, X3, X4, appcB_out_gga(X5, X2, X6)) -> U11_ga(X1, X2, X3, X4, appcB_in_gga(X6, X1, X4)) U11_ga(X1, X2, X3, X4, appcB_out_gga(X6, X1, X4)) -> reversecA_out_ga(.(X1, .(X2, X3)), X4) The argument filtering Pi contains the following mapping: .(x1, x2) = .(x1, x2) reversecA_in_ga(x1, x2) = reversecA_in_ga(x1) U9_ga(x1, x2, x3, x4, x5) = U9_ga(x1, x2, x3, x5) [] = [] U12_ga(x1, x2, x3) = U12_ga(x1, x3) appcB_in_gga(x1, x2, x3) = appcB_in_gga(x1, x2) U13_gga(x1, x2, x3, x4, x5) = U13_gga(x1, x2, x3, x5) appcB_out_gga(x1, x2, x3) = appcB_out_gga(x1, x2, x3) reversecA_out_ga(x1, x2) = reversecA_out_ga(x1, x2) U10_ga(x1, x2, x3, x4, x5) = U10_ga(x1, x2, x3, x5) U11_ga(x1, x2, x3, x4, x5) = U11_ga(x1, x2, x3, x5) APPB_IN_GGA(x1, x2, x3) = APPB_IN_GGA(x1, x2) 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: APPB_IN_GGA(.(X1, X2), X3, .(X1, X4)) -> APPB_IN_GGA(X2, X3, X4) R is empty. The argument filtering Pi contains the following mapping: .(x1, x2) = .(x1, x2) APPB_IN_GGA(x1, x2, x3) = APPB_IN_GGA(x1, x2) 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: APPB_IN_GGA(.(X1, X2), X3) -> APPB_IN_GGA(X2, X3) 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: *APPB_IN_GGA(.(X1, X2), X3) -> APPB_IN_GGA(X2, X3) 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: REVERSEA_IN_GA(.(X1, .(X2, X3)), X4) -> REVERSEA_IN_GA(X3, X5) The TRS R consists of the following rules: reversecA_in_ga(.(X1, .(X2, X3)), X4) -> U9_ga(X1, X2, X3, X4, reversecA_in_ga(X3, X5)) reversecA_in_ga(.(X1, []), X2) -> U12_ga(X1, X2, appcB_in_gga([], X1, X2)) appcB_in_gga(.(X1, X2), X3, .(X1, X4)) -> U13_gga(X1, X2, X3, X4, appcB_in_gga(X2, X3, X4)) appcB_in_gga([], X1, .(X1, [])) -> appcB_out_gga([], X1, .(X1, [])) U13_gga(X1, X2, X3, X4, appcB_out_gga(X2, X3, X4)) -> appcB_out_gga(.(X1, X2), X3, .(X1, X4)) U12_ga(X1, X2, appcB_out_gga([], X1, X2)) -> reversecA_out_ga(.(X1, []), X2) reversecA_in_ga([], []) -> reversecA_out_ga([], []) U9_ga(X1, X2, X3, X4, reversecA_out_ga(X3, X5)) -> U10_ga(X1, X2, X3, X4, appcB_in_gga(X5, X2, X6)) U10_ga(X1, X2, X3, X4, appcB_out_gga(X5, X2, X6)) -> U11_ga(X1, X2, X3, X4, appcB_in_gga(X6, X1, X4)) U11_ga(X1, X2, X3, X4, appcB_out_gga(X6, X1, X4)) -> reversecA_out_ga(.(X1, .(X2, X3)), X4) The argument filtering Pi contains the following mapping: .(x1, x2) = .(x1, x2) reversecA_in_ga(x1, x2) = reversecA_in_ga(x1) U9_ga(x1, x2, x3, x4, x5) = U9_ga(x1, x2, x3, x5) [] = [] U12_ga(x1, x2, x3) = U12_ga(x1, x3) appcB_in_gga(x1, x2, x3) = appcB_in_gga(x1, x2) U13_gga(x1, x2, x3, x4, x5) = U13_gga(x1, x2, x3, x5) appcB_out_gga(x1, x2, x3) = appcB_out_gga(x1, x2, x3) reversecA_out_ga(x1, x2) = reversecA_out_ga(x1, x2) U10_ga(x1, x2, x3, x4, x5) = U10_ga(x1, x2, x3, x5) U11_ga(x1, x2, x3, x4, x5) = U11_ga(x1, x2, x3, x5) REVERSEA_IN_GA(x1, x2) = REVERSEA_IN_GA(x1) 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: REVERSEA_IN_GA(.(X1, .(X2, X3)), X4) -> REVERSEA_IN_GA(X3, X5) R is empty. The argument filtering Pi contains the following mapping: .(x1, x2) = .(x1, x2) REVERSEA_IN_GA(x1, x2) = REVERSEA_IN_GA(x1) 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: REVERSEA_IN_GA(.(X1, .(X2, X3))) -> REVERSEA_IN_GA(X3) 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: *REVERSEA_IN_GA(.(X1, .(X2, X3))) -> REVERSEA_IN_GA(X3) The graph contains the following edges 1 > 1 ---------------------------------------- (20) YES