YES proof of /export/starexec/sandbox2/benchmark/theBenchmark.pl # AProVE Commit ID: 794c25de1cacf0d048858bcd21c9a779e1221865 marcel 20200619 unpublished dirty Left Termination of the query pattern transpose(g,a) w.r.t. the given Prolog program could successfully be proven: (0) Prolog (1) PrologToDTProblemTransformerProof [SOUND, 40 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) PiDPToQDPProof [SOUND, 0 ms] (16) QDP (17) QDPSizeChangeProof [EQUIVALENT, 0 ms] (18) YES ---------------------------------------- (0) Obligation: Clauses: transpose(A, B) :- transpose_aux(A, [], B). transpose_aux(.(R, Rs), X1, .(C, Cs)) :- ','(row2col(R, .(C, Cs), Cols1, Accm), transpose_aux(Rs, Accm, Cols1)). transpose_aux([], X, X). row2col(.(X, Xs), .(.(X, Ys), Cols), .(Ys, Cols1), .([], As)) :- row2col(Xs, Cols, Cols1, As). row2col([], [], [], []). Query: transpose(g,a) ---------------------------------------- (1) PrologToDTProblemTransformerProof (SOUND) Built DT problem from termination graph DT10. { "root": 2, "program": { "directives": [], "clauses": [ [ "(transpose A B)", "(transpose_aux A ([]) B)" ], [ "(transpose_aux (. R Rs) X1 (. C Cs))", "(',' (row2col R (. C Cs) Cols1 Accm) (transpose_aux Rs Accm Cols1))" ], [ "(transpose_aux ([]) X X)", null ], [ "(row2col (. X Xs) (. (. X Ys) Cols) (. Ys Cols1) (. ([]) As))", "(row2col Xs Cols Cols1 As)" ], [ "(row2col ([]) ([]) ([]) ([]))", null ] ] }, "graph": { "nodes": { "27": { "goal": [{ "clause": -1, "scope": -1, "term": "(row2col T24 (. T28 T29) X35 X36)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T24"], "free": [ "X35", "X36" ], "exprvars": [] } }, "28": { "goal": [{ "clause": -1, "scope": -1, "term": "(transpose_aux T25 T35 T34)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T25", "T35" ], "free": [], "exprvars": [] } }, "290": { "goal": [{ "clause": 4, "scope": 4, "term": "(row2col T57 T60 X91 X92)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T57"], "free": [ "X91", "X92" ], "exprvars": [] } }, "type": "Nodes", "293": { "goal": [{ "clause": -1, "scope": -1, "term": "(row2col T82 T85 X139 X140)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T82"], "free": [ "X139", "X140" ], "exprvars": [] } }, "294": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "351": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (row2col T115 (. T120 T121) X185 X186) (transpose_aux T116 X186 X185))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T115", "T116" ], "free": [ "X185", "X186" ], "exprvars": [] } }, "352": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "353": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "354": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "311": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "355": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "356": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "313": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "357": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "358": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "315": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "10": { "goal": [{ "clause": 2, "scope": 2, "term": "(transpose_aux T5 ([]) T7)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T5"], "free": [], "exprvars": [] } }, "11": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (row2col T24 (. T28 T29) X35 X36) (transpose_aux T25 X36 X35))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T24", "T25" ], "free": [ "X35", "X36" ], "exprvars": [] } }, "12": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "37": { "goal": [ { "clause": 3, "scope": 3, "term": "(row2col T24 (. T28 T29) X35 X36)" }, { "clause": 4, "scope": 3, "term": "(row2col T24 (. T28 T29) X35 X36)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T24"], "free": [ "X35", "X36" ], "exprvars": [] } }, "121": { "goal": [{ "clause": 3, "scope": 3, "term": "(row2col T24 (. T28 T29) X35 X36)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T24"], "free": [ "X35", "X36" ], "exprvars": [] } }, "122": { "goal": [{ "clause": 4, "scope": 3, "term": "(row2col T24 (. T28 T29) X35 X36)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T24"], "free": [ "X35", "X36" ], "exprvars": [] } }, "287": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "2": { "goal": [{ "clause": -1, "scope": -1, "term": "(transpose T1 T2)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T1"], "free": [], "exprvars": [] } }, "288": { "goal": [ { "clause": 3, "scope": 4, "term": "(row2col T57 T60 X91 X92)" }, { "clause": 4, "scope": 4, "term": "(row2col T57 T60 X91 X92)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T57"], "free": [ "X91", "X92" ], "exprvars": [] } }, "289": { "goal": [{ "clause": 3, "scope": 4, "term": "(row2col T57 T60 X91 X92)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T57"], "free": [ "X91", "X92" ], "exprvars": [] } }, "4": { "goal": [{ "clause": 0, "scope": 1, "term": "(transpose T1 T2)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T1"], "free": [], "exprvars": [] } }, "248": { "goal": [{ "clause": -1, "scope": -1, "term": "(row2col T57 T60 X91 X92)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T57"], "free": [ "X91", "X92" ], "exprvars": [] } }, "7": { "goal": [{ "clause": -1, "scope": -1, "term": "(transpose_aux T5 ([]) T7)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T5"], "free": [], "exprvars": [] } }, "326": { "goal": [ { "clause": 1, "scope": 5, "term": "(transpose_aux T25 T35 T34)" }, { "clause": 2, "scope": 5, "term": "(transpose_aux T25 T35 T34)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T25", "T35" ], "free": [], "exprvars": [] } }, "8": { "goal": [ { "clause": 1, "scope": 2, "term": "(transpose_aux T5 ([]) T7)" }, { "clause": 2, "scope": 2, "term": "(transpose_aux T5 ([]) T7)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T5"], "free": [], "exprvars": [] } }, "327": { "goal": [{ "clause": 1, "scope": 5, "term": "(transpose_aux T25 T35 T34)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T25", "T35" ], "free": [], "exprvars": [] } }, "9": { "goal": [{ "clause": 1, "scope": 2, "term": "(transpose_aux T5 ([]) T7)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T5"], "free": [], "exprvars": [] } }, "328": { "goal": [{ "clause": 2, "scope": 5, "term": "(transpose_aux T25 T35 T34)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T25", "T35" ], "free": [], "exprvars": [] } }, "309": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } } }, "edges": [ { "from": 2, "to": 4, "label": "CASE" }, { "from": 4, "to": 7, "label": "ONLY EVAL with clause\ntranspose(X4, X5) :- transpose_aux(X4, [], X5).\nand substitutionT1 -> T5,\nX4 -> T5,\nT2 -> T7,\nX5 -> T7,\nT6 -> T7" }, { "from": 7, "to": 8, "label": "CASE" }, { "from": 8, "to": 9, "label": "PARALLEL" }, { "from": 8, "to": 10, "label": "PARALLEL" }, { "from": 9, "to": 11, "label": "EVAL with clause\ntranspose_aux(.(X30, X31), X32, .(X33, X34)) :- ','(row2col(X30, .(X33, X34), X35, X36), transpose_aux(X31, X36, X35)).\nand substitutionX30 -> T24,\nX31 -> T25,\nT5 -> .(T24, T25),\nX32 -> [],\nX33 -> T28,\nX34 -> T29,\nT7 -> .(T28, T29),\nT26 -> T28,\nT27 -> T29" }, { "from": 9, "to": 12, "label": "EVAL-BACKTRACK" }, { "from": 10, "to": 356, "label": "EVAL with clause\ntranspose_aux([], X200, X200).\nand substitutionT5 -> [],\nX200 -> [],\nT7 -> []" }, { "from": 10, "to": 357, "label": "EVAL-BACKTRACK" }, { "from": 11, "to": 27, "label": "SPLIT 1" }, { "from": 11, "to": 28, "label": "SPLIT 2\nnew knowledge:\nT24 is ground\nT35 is ground\nreplacements:X35 -> T34,\nX36 -> T35" }, { "from": 27, "to": 37, "label": "CASE" }, { "from": 28, "to": 326, "label": "CASE" }, { "from": 37, "to": 121, "label": "PARALLEL" }, { "from": 37, "to": 122, "label": "PARALLEL" }, { "from": 121, "to": 248, "label": "EVAL with clause\nrow2col(.(X85, X86), .(.(X85, X87), X88), .(X87, X89), .([], X90)) :- row2col(X86, X88, X89, X90).\nand substitutionX85 -> T56,\nX86 -> T57,\nT24 -> .(T56, T57),\nX87 -> T58,\nT28 -> .(T56, T58),\nT29 -> T60,\nX88 -> T60,\nX89 -> X91,\nX35 -> .(T58, X91),\nX90 -> X92,\nX36 -> .([], X92),\nT59 -> T60" }, { "from": 121, "to": 287, "label": "EVAL-BACKTRACK" }, { "from": 122, "to": 315, "label": "BACKTRACK\nfor clause: row2col([], [], [], [])because of non-unification" }, { "from": 248, "to": 288, "label": "CASE" }, { "from": 288, "to": 289, "label": "PARALLEL" }, { "from": 288, "to": 290, "label": "PARALLEL" }, { "from": 289, "to": 293, "label": "EVAL with clause\nrow2col(.(X133, X134), .(.(X133, X135), X136), .(X135, X137), .([], X138)) :- row2col(X134, X136, X137, X138).\nand substitutionX133 -> T81,\nX134 -> T82,\nT57 -> .(T81, T82),\nX135 -> T83,\nX136 -> T85,\nT60 -> .(.(T81, T83), T85),\nX137 -> X139,\nX91 -> .(T83, X139),\nX138 -> X140,\nX92 -> .([], X140),\nT84 -> T85" }, { "from": 289, "to": 294, "label": "EVAL-BACKTRACK" }, { "from": 290, "to": 309, "label": "EVAL with clause\nrow2col([], [], [], []).\nand substitutionT57 -> [],\nT60 -> [],\nX91 -> [],\nX92 -> []" }, { "from": 290, "to": 311, "label": "EVAL-BACKTRACK" }, { "from": 293, "to": 248, "label": "INSTANCE with matching:\nT57 -> T82\nT60 -> T85\nX91 -> X139\nX92 -> X140" }, { "from": 309, "to": 313, "label": "SUCCESS" }, { "from": 326, "to": 327, "label": "PARALLEL" }, { "from": 326, "to": 328, "label": "PARALLEL" }, { "from": 327, "to": 351, "label": "EVAL with clause\ntranspose_aux(.(X180, X181), X182, .(X183, X184)) :- ','(row2col(X180, .(X183, X184), X185, X186), transpose_aux(X181, X186, X185)).\nand substitutionX180 -> T115,\nX181 -> T116,\nT25 -> .(T115, T116),\nT35 -> T117,\nX182 -> T117,\nX183 -> T120,\nX184 -> T121,\nT34 -> .(T120, T121),\nT118 -> T120,\nT119 -> T121" }, { "from": 327, "to": 352, "label": "EVAL-BACKTRACK" }, { "from": 328, "to": 353, "label": "EVAL with clause\ntranspose_aux([], X197, X197).\nand substitutionT25 -> [],\nT35 -> T128,\nX197 -> T128,\nT34 -> T128" }, { "from": 328, "to": 354, "label": "EVAL-BACKTRACK" }, { "from": 351, "to": 11, "label": "INSTANCE with matching:\nT24 -> T115\nT28 -> T120\nT29 -> T121\nX35 -> X185\nX36 -> X186\nT25 -> T116" }, { "from": 353, "to": 355, "label": "SUCCESS" }, { "from": 356, "to": 358, "label": "SUCCESS" } ], "type": "Graph" } } ---------------------------------------- (2) Obligation: Triples: row2colA(.(X1, X2), .(.(X1, X3), X4), .(X3, X5), .([], X6)) :- row2colA(X2, X4, X5, X6). pB(.(X1, X2), .(X1, X3), X4, .(X3, X5), .([], X6), X7) :- row2colA(X2, X4, X5, X6). pB(X1, X2, X3, .(X4, X5), X6, .(X7, X8)) :- ','(row2colcC(X1, X2, X3, .(X4, X5), X6), pB(X7, X4, X5, X9, X10, X8)). transposeD(.(X1, X2), .(X3, X4)) :- pB(X1, X3, X4, X5, X6, X2). Clauses: row2colcA(.(X1, X2), .(.(X1, X3), X4), .(X3, X5), .([], X6)) :- row2colcA(X2, X4, X5, X6). row2colcA([], [], [], []). qcB(X1, X2, X3, .(X4, X5), X6, .(X7, X8)) :- ','(row2colcC(X1, X2, X3, .(X4, X5), X6), qcB(X7, X4, X5, X9, X10, X8)). qcB(X1, X2, X3, X4, X4, []) :- row2colcC(X1, X2, X3, X4, X4). row2colcC(.(X1, X2), .(X1, X3), X4, .(X3, X5), .([], X6)) :- row2colcA(X2, X4, X5, X6). Afs: transposeD(x1, x2) = transposeD(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: transposeD_in_2: (b,f) pB_in_6: (b,f,f,f,f,b) row2colA_in_4: (b,f,f,f) row2colcC_in_5: (b,f,f,f,f) row2colcA_in_4: (b,f,f,f) Transforming TRIPLES into the following Term Rewriting System: Pi DP problem: The TRS P consists of the following rules: TRANSPOSED_IN_GA(.(X1, X2), .(X3, X4)) -> U5_GA(X1, X2, X3, X4, pB_in_gaaaag(X1, X3, X4, X5, X6, X2)) TRANSPOSED_IN_GA(.(X1, X2), .(X3, X4)) -> PB_IN_GAAAAG(X1, X3, X4, X5, X6, X2) PB_IN_GAAAAG(.(X1, X2), .(X1, X3), X4, .(X3, X5), .([], X6), X7) -> U2_GAAAAG(X1, X2, X3, X4, X5, X6, X7, row2colA_in_gaaa(X2, X4, X5, X6)) PB_IN_GAAAAG(.(X1, X2), .(X1, X3), X4, .(X3, X5), .([], X6), X7) -> ROW2COLA_IN_GAAA(X2, X4, X5, X6) ROW2COLA_IN_GAAA(.(X1, X2), .(.(X1, X3), X4), .(X3, X5), .([], X6)) -> U1_GAAA(X1, X2, X3, X4, X5, X6, row2colA_in_gaaa(X2, X4, X5, X6)) ROW2COLA_IN_GAAA(.(X1, X2), .(.(X1, X3), X4), .(X3, X5), .([], X6)) -> ROW2COLA_IN_GAAA(X2, X4, X5, X6) PB_IN_GAAAAG(X1, X2, X3, .(X4, X5), X6, .(X7, X8)) -> U3_GAAAAG(X1, X2, X3, X4, X5, X6, X7, X8, row2colcC_in_gaaaa(X1, X2, X3, .(X4, X5), X6)) U3_GAAAAG(X1, X2, X3, X4, X5, X6, X7, X8, row2colcC_out_gaaaa(X1, X2, X3, .(X4, X5), X6)) -> U4_GAAAAG(X1, X2, X3, X4, X5, X6, X7, X8, pB_in_gaaaag(X7, X4, X5, X9, X10, X8)) U3_GAAAAG(X1, X2, X3, X4, X5, X6, X7, X8, row2colcC_out_gaaaa(X1, X2, X3, .(X4, X5), X6)) -> PB_IN_GAAAAG(X7, X4, X5, X9, X10, X8) The TRS R consists of the following rules: row2colcC_in_gaaaa(.(X1, X2), .(X1, X3), X4, .(X3, X5), .([], X6)) -> U11_gaaaa(X1, X2, X3, X4, X5, X6, row2colcA_in_gaaa(X2, X4, X5, X6)) row2colcA_in_gaaa(.(X1, X2), .(.(X1, X3), X4), .(X3, X5), .([], X6)) -> U7_gaaa(X1, X2, X3, X4, X5, X6, row2colcA_in_gaaa(X2, X4, X5, X6)) row2colcA_in_gaaa([], [], [], []) -> row2colcA_out_gaaa([], [], [], []) U7_gaaa(X1, X2, X3, X4, X5, X6, row2colcA_out_gaaa(X2, X4, X5, X6)) -> row2colcA_out_gaaa(.(X1, X2), .(.(X1, X3), X4), .(X3, X5), .([], X6)) U11_gaaaa(X1, X2, X3, X4, X5, X6, row2colcA_out_gaaa(X2, X4, X5, X6)) -> row2colcC_out_gaaaa(.(X1, X2), .(X1, X3), X4, .(X3, X5), .([], X6)) The argument filtering Pi contains the following mapping: .(x1, x2) = .(x1, x2) pB_in_gaaaag(x1, x2, x3, x4, x5, x6) = pB_in_gaaaag(x1, x6) row2colA_in_gaaa(x1, x2, x3, x4) = row2colA_in_gaaa(x1) row2colcC_in_gaaaa(x1, x2, x3, x4, x5) = row2colcC_in_gaaaa(x1) U11_gaaaa(x1, x2, x3, x4, x5, x6, x7) = U11_gaaaa(x1, x2, x7) row2colcA_in_gaaa(x1, x2, x3, x4) = row2colcA_in_gaaa(x1) U7_gaaa(x1, x2, x3, x4, x5, x6, x7) = U7_gaaa(x1, x2, x7) [] = [] row2colcA_out_gaaa(x1, x2, x3, x4) = row2colcA_out_gaaa(x1, x4) row2colcC_out_gaaaa(x1, x2, x3, x4, x5) = row2colcC_out_gaaaa(x1, x5) TRANSPOSED_IN_GA(x1, x2) = TRANSPOSED_IN_GA(x1) U5_GA(x1, x2, x3, x4, x5) = U5_GA(x1, x2, x5) PB_IN_GAAAAG(x1, x2, x3, x4, x5, x6) = PB_IN_GAAAAG(x1, x6) U2_GAAAAG(x1, x2, x3, x4, x5, x6, x7, x8) = U2_GAAAAG(x1, x2, x7, x8) ROW2COLA_IN_GAAA(x1, x2, x3, x4) = ROW2COLA_IN_GAAA(x1) U1_GAAA(x1, x2, x3, x4, x5, x6, x7) = U1_GAAA(x1, x2, x7) U3_GAAAAG(x1, x2, x3, x4, x5, x6, x7, x8, x9) = U3_GAAAAG(x1, x7, x8, x9) U4_GAAAAG(x1, x2, x3, x4, x5, x6, x7, x8, x9) = U4_GAAAAG(x1, x6, x7, x8, x9) 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: TRANSPOSED_IN_GA(.(X1, X2), .(X3, X4)) -> U5_GA(X1, X2, X3, X4, pB_in_gaaaag(X1, X3, X4, X5, X6, X2)) TRANSPOSED_IN_GA(.(X1, X2), .(X3, X4)) -> PB_IN_GAAAAG(X1, X3, X4, X5, X6, X2) PB_IN_GAAAAG(.(X1, X2), .(X1, X3), X4, .(X3, X5), .([], X6), X7) -> U2_GAAAAG(X1, X2, X3, X4, X5, X6, X7, row2colA_in_gaaa(X2, X4, X5, X6)) PB_IN_GAAAAG(.(X1, X2), .(X1, X3), X4, .(X3, X5), .([], X6), X7) -> ROW2COLA_IN_GAAA(X2, X4, X5, X6) ROW2COLA_IN_GAAA(.(X1, X2), .(.(X1, X3), X4), .(X3, X5), .([], X6)) -> U1_GAAA(X1, X2, X3, X4, X5, X6, row2colA_in_gaaa(X2, X4, X5, X6)) ROW2COLA_IN_GAAA(.(X1, X2), .(.(X1, X3), X4), .(X3, X5), .([], X6)) -> ROW2COLA_IN_GAAA(X2, X4, X5, X6) PB_IN_GAAAAG(X1, X2, X3, .(X4, X5), X6, .(X7, X8)) -> U3_GAAAAG(X1, X2, X3, X4, X5, X6, X7, X8, row2colcC_in_gaaaa(X1, X2, X3, .(X4, X5), X6)) U3_GAAAAG(X1, X2, X3, X4, X5, X6, X7, X8, row2colcC_out_gaaaa(X1, X2, X3, .(X4, X5), X6)) -> U4_GAAAAG(X1, X2, X3, X4, X5, X6, X7, X8, pB_in_gaaaag(X7, X4, X5, X9, X10, X8)) U3_GAAAAG(X1, X2, X3, X4, X5, X6, X7, X8, row2colcC_out_gaaaa(X1, X2, X3, .(X4, X5), X6)) -> PB_IN_GAAAAG(X7, X4, X5, X9, X10, X8) The TRS R consists of the following rules: row2colcC_in_gaaaa(.(X1, X2), .(X1, X3), X4, .(X3, X5), .([], X6)) -> U11_gaaaa(X1, X2, X3, X4, X5, X6, row2colcA_in_gaaa(X2, X4, X5, X6)) row2colcA_in_gaaa(.(X1, X2), .(.(X1, X3), X4), .(X3, X5), .([], X6)) -> U7_gaaa(X1, X2, X3, X4, X5, X6, row2colcA_in_gaaa(X2, X4, X5, X6)) row2colcA_in_gaaa([], [], [], []) -> row2colcA_out_gaaa([], [], [], []) U7_gaaa(X1, X2, X3, X4, X5, X6, row2colcA_out_gaaa(X2, X4, X5, X6)) -> row2colcA_out_gaaa(.(X1, X2), .(.(X1, X3), X4), .(X3, X5), .([], X6)) U11_gaaaa(X1, X2, X3, X4, X5, X6, row2colcA_out_gaaa(X2, X4, X5, X6)) -> row2colcC_out_gaaaa(.(X1, X2), .(X1, X3), X4, .(X3, X5), .([], X6)) The argument filtering Pi contains the following mapping: .(x1, x2) = .(x1, x2) pB_in_gaaaag(x1, x2, x3, x4, x5, x6) = pB_in_gaaaag(x1, x6) row2colA_in_gaaa(x1, x2, x3, x4) = row2colA_in_gaaa(x1) row2colcC_in_gaaaa(x1, x2, x3, x4, x5) = row2colcC_in_gaaaa(x1) U11_gaaaa(x1, x2, x3, x4, x5, x6, x7) = U11_gaaaa(x1, x2, x7) row2colcA_in_gaaa(x1, x2, x3, x4) = row2colcA_in_gaaa(x1) U7_gaaa(x1, x2, x3, x4, x5, x6, x7) = U7_gaaa(x1, x2, x7) [] = [] row2colcA_out_gaaa(x1, x2, x3, x4) = row2colcA_out_gaaa(x1, x4) row2colcC_out_gaaaa(x1, x2, x3, x4, x5) = row2colcC_out_gaaaa(x1, x5) TRANSPOSED_IN_GA(x1, x2) = TRANSPOSED_IN_GA(x1) U5_GA(x1, x2, x3, x4, x5) = U5_GA(x1, x2, x5) PB_IN_GAAAAG(x1, x2, x3, x4, x5, x6) = PB_IN_GAAAAG(x1, x6) U2_GAAAAG(x1, x2, x3, x4, x5, x6, x7, x8) = U2_GAAAAG(x1, x2, x7, x8) ROW2COLA_IN_GAAA(x1, x2, x3, x4) = ROW2COLA_IN_GAAA(x1) U1_GAAA(x1, x2, x3, x4, x5, x6, x7) = U1_GAAA(x1, x2, x7) U3_GAAAAG(x1, x2, x3, x4, x5, x6, x7, x8, x9) = U3_GAAAAG(x1, x7, x8, x9) U4_GAAAAG(x1, x2, x3, x4, x5, x6, x7, x8, x9) = U4_GAAAAG(x1, x6, x7, x8, x9) 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: ROW2COLA_IN_GAAA(.(X1, X2), .(.(X1, X3), X4), .(X3, X5), .([], X6)) -> ROW2COLA_IN_GAAA(X2, X4, X5, X6) The TRS R consists of the following rules: row2colcC_in_gaaaa(.(X1, X2), .(X1, X3), X4, .(X3, X5), .([], X6)) -> U11_gaaaa(X1, X2, X3, X4, X5, X6, row2colcA_in_gaaa(X2, X4, X5, X6)) row2colcA_in_gaaa(.(X1, X2), .(.(X1, X3), X4), .(X3, X5), .([], X6)) -> U7_gaaa(X1, X2, X3, X4, X5, X6, row2colcA_in_gaaa(X2, X4, X5, X6)) row2colcA_in_gaaa([], [], [], []) -> row2colcA_out_gaaa([], [], [], []) U7_gaaa(X1, X2, X3, X4, X5, X6, row2colcA_out_gaaa(X2, X4, X5, X6)) -> row2colcA_out_gaaa(.(X1, X2), .(.(X1, X3), X4), .(X3, X5), .([], X6)) U11_gaaaa(X1, X2, X3, X4, X5, X6, row2colcA_out_gaaa(X2, X4, X5, X6)) -> row2colcC_out_gaaaa(.(X1, X2), .(X1, X3), X4, .(X3, X5), .([], X6)) The argument filtering Pi contains the following mapping: .(x1, x2) = .(x1, x2) row2colcC_in_gaaaa(x1, x2, x3, x4, x5) = row2colcC_in_gaaaa(x1) U11_gaaaa(x1, x2, x3, x4, x5, x6, x7) = U11_gaaaa(x1, x2, x7) row2colcA_in_gaaa(x1, x2, x3, x4) = row2colcA_in_gaaa(x1) U7_gaaa(x1, x2, x3, x4, x5, x6, x7) = U7_gaaa(x1, x2, x7) [] = [] row2colcA_out_gaaa(x1, x2, x3, x4) = row2colcA_out_gaaa(x1, x4) row2colcC_out_gaaaa(x1, x2, x3, x4, x5) = row2colcC_out_gaaaa(x1, x5) ROW2COLA_IN_GAAA(x1, x2, x3, x4) = ROW2COLA_IN_GAAA(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: ROW2COLA_IN_GAAA(.(X1, X2), .(.(X1, X3), X4), .(X3, X5), .([], X6)) -> ROW2COLA_IN_GAAA(X2, X4, X5, X6) R is empty. The argument filtering Pi contains the following mapping: .(x1, x2) = .(x1, x2) [] = [] ROW2COLA_IN_GAAA(x1, x2, x3, x4) = ROW2COLA_IN_GAAA(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: ROW2COLA_IN_GAAA(.(X1, X2)) -> ROW2COLA_IN_GAAA(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: *ROW2COLA_IN_GAAA(.(X1, X2)) -> ROW2COLA_IN_GAAA(X2) The graph contains the following edges 1 > 1 ---------------------------------------- (13) YES ---------------------------------------- (14) Obligation: Pi DP problem: The TRS P consists of the following rules: PB_IN_GAAAAG(X1, X2, X3, .(X4, X5), X6, .(X7, X8)) -> U3_GAAAAG(X1, X2, X3, X4, X5, X6, X7, X8, row2colcC_in_gaaaa(X1, X2, X3, .(X4, X5), X6)) U3_GAAAAG(X1, X2, X3, X4, X5, X6, X7, X8, row2colcC_out_gaaaa(X1, X2, X3, .(X4, X5), X6)) -> PB_IN_GAAAAG(X7, X4, X5, X9, X10, X8) The TRS R consists of the following rules: row2colcC_in_gaaaa(.(X1, X2), .(X1, X3), X4, .(X3, X5), .([], X6)) -> U11_gaaaa(X1, X2, X3, X4, X5, X6, row2colcA_in_gaaa(X2, X4, X5, X6)) row2colcA_in_gaaa(.(X1, X2), .(.(X1, X3), X4), .(X3, X5), .([], X6)) -> U7_gaaa(X1, X2, X3, X4, X5, X6, row2colcA_in_gaaa(X2, X4, X5, X6)) row2colcA_in_gaaa([], [], [], []) -> row2colcA_out_gaaa([], [], [], []) U7_gaaa(X1, X2, X3, X4, X5, X6, row2colcA_out_gaaa(X2, X4, X5, X6)) -> row2colcA_out_gaaa(.(X1, X2), .(.(X1, X3), X4), .(X3, X5), .([], X6)) U11_gaaaa(X1, X2, X3, X4, X5, X6, row2colcA_out_gaaa(X2, X4, X5, X6)) -> row2colcC_out_gaaaa(.(X1, X2), .(X1, X3), X4, .(X3, X5), .([], X6)) The argument filtering Pi contains the following mapping: .(x1, x2) = .(x1, x2) row2colcC_in_gaaaa(x1, x2, x3, x4, x5) = row2colcC_in_gaaaa(x1) U11_gaaaa(x1, x2, x3, x4, x5, x6, x7) = U11_gaaaa(x1, x2, x7) row2colcA_in_gaaa(x1, x2, x3, x4) = row2colcA_in_gaaa(x1) U7_gaaa(x1, x2, x3, x4, x5, x6, x7) = U7_gaaa(x1, x2, x7) [] = [] row2colcA_out_gaaa(x1, x2, x3, x4) = row2colcA_out_gaaa(x1, x4) row2colcC_out_gaaaa(x1, x2, x3, x4, x5) = row2colcC_out_gaaaa(x1, x5) PB_IN_GAAAAG(x1, x2, x3, x4, x5, x6) = PB_IN_GAAAAG(x1, x6) U3_GAAAAG(x1, x2, x3, x4, x5, x6, x7, x8, x9) = U3_GAAAAG(x1, x7, x8, x9) We have to consider all (P,R,Pi)-chains ---------------------------------------- (15) PiDPToQDPProof (SOUND) Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. ---------------------------------------- (16) Obligation: Q DP problem: The TRS P consists of the following rules: PB_IN_GAAAAG(X1, .(X7, X8)) -> U3_GAAAAG(X1, X7, X8, row2colcC_in_gaaaa(X1)) U3_GAAAAG(X1, X7, X8, row2colcC_out_gaaaa(X1, X6)) -> PB_IN_GAAAAG(X7, X8) The TRS R consists of the following rules: row2colcC_in_gaaaa(.(X1, X2)) -> U11_gaaaa(X1, X2, row2colcA_in_gaaa(X2)) row2colcA_in_gaaa(.(X1, X2)) -> U7_gaaa(X1, X2, row2colcA_in_gaaa(X2)) row2colcA_in_gaaa([]) -> row2colcA_out_gaaa([], []) U7_gaaa(X1, X2, row2colcA_out_gaaa(X2, X6)) -> row2colcA_out_gaaa(.(X1, X2), .([], X6)) U11_gaaaa(X1, X2, row2colcA_out_gaaa(X2, X6)) -> row2colcC_out_gaaaa(.(X1, X2), .([], X6)) The set Q consists of the following terms: row2colcC_in_gaaaa(x0) row2colcA_in_gaaa(x0) U7_gaaa(x0, x1, x2) U11_gaaaa(x0, x1, x2) We have to consider all (P,Q,R)-chains. ---------------------------------------- (17) 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_GAAAAG(X1, X7, X8, row2colcC_out_gaaaa(X1, X6)) -> PB_IN_GAAAAG(X7, X8) The graph contains the following edges 2 >= 1, 3 >= 2 *PB_IN_GAAAAG(X1, .(X7, X8)) -> U3_GAAAAG(X1, X7, X8, row2colcC_in_gaaaa(X1)) The graph contains the following edges 1 >= 1, 2 > 2, 2 > 3 ---------------------------------------- (18) YES