/export/starexec/sandbox2/solver/bin/starexec_run_standard /export/starexec/sandbox2/benchmark/theBenchmark.pl /export/starexec/sandbox2/output/output_files -------------------------------------------------------------------------------- YES proof of /export/starexec/sandbox2/benchmark/theBenchmark.pl # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty Left Termination of the query pattern shapes(g,a) w.r.t. the given Prolog program could successfully be proven: (0) Prolog (1) PrologToDTProblemTransformerProof [SOUND, 19 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) QDPQMonotonicMRRProof [EQUIVALENT, 62 ms] (20) QDP (21) DependencyGraphProof [EQUIVALENT, 0 ms] (22) TRUE (23) PiDP (24) UsableRulesProof [EQUIVALENT, 0 ms] (25) PiDP (26) PiDPToQDPProof [SOUND, 0 ms] (27) QDP (28) QDPSizeChangeProof [EQUIVALENT, 0 ms] (29) YES (30) PiDP (31) UsableRulesProof [EQUIVALENT, 0 ms] (32) PiDP (33) PiDPToQDPProof [SOUND, 0 ms] (34) QDP (35) QDPSizeChangeProof [EQUIVALENT, 0 ms] (36) YES ---------------------------------------- (0) Obligation: Clauses: shapes(Matrix, N) :- ','(varmat(Matrix, MatrixWithVars), unif_matrx(MatrixWithVars)). varmat([], []). varmat(.(L, Ls), .(VL, VLs)) :- ','(varmat(L, VL), varmat(Ls, VLs)). varmat(.(black, Xs), .(black, VXs)) :- varmat(Xs, VXs). varmat(.(white, Xs), .(w(X1), VXs)) :- varmat(Xs, VXs). unif_matrx(.(L1, .(L2, Ls))) :- ','(unif_lines(L1, L2), unif_matrx(.(L2, Ls))). unif_matrx(.(X2, [])). unif_lines(.(W, .(X, L1s)), .(Y, .(Z, L2s))) :- ','(unif_pairs(.(W, .(X, .(Y, .(Z, .(W, .(Y, .(X, .(Z, .(W, .(Z, .(X, .(Y, []))))))))))))), unif_lines(.(X, L1s), .(Z, L2s))). unif_lines(.(X3, []), .(X4, [])). unif_pairs([]). unif_pairs(.(A, .(B, Pairs))) :- ','(unif(A, B), unif_pairs(Pairs)). unif(w(A), w(A)). unif(black, black). unif(black, w(X5)). unif(w(X6), black). Query: shapes(g,a) ---------------------------------------- (1) PrologToDTProblemTransformerProof (SOUND) Built DT problem from termination graph DT10. { "root": 3, "program": { "directives": [], "clauses": [ [ "(shapes Matrix N)", "(',' (varmat Matrix MatrixWithVars) (unif_matrx MatrixWithVars))" ], [ "(varmat ([]) ([]))", null ], [ "(varmat (. L Ls) (. VL VLs))", "(',' (varmat L VL) (varmat Ls VLs))" ], [ "(varmat (. (black) Xs) (. (black) VXs))", "(varmat Xs VXs)" ], [ "(varmat (. (white) Xs) (. (w X1) VXs))", "(varmat Xs VXs)" ], [ "(unif_matrx (. L1 (. L2 Ls)))", "(',' (unif_lines L1 L2) (unif_matrx (. L2 Ls)))" ], [ "(unif_matrx (. X2 ([])))", null ], [ "(unif_lines (. W (. X L1s)) (. Y (. Z L2s)))", "(',' (unif_pairs (. W (. X (. Y (. Z (. W (. Y (. X (. Z (. W (. Z (. X (. Y ([])))))))))))))) (unif_lines (. X L1s) (. Z L2s)))" ], [ "(unif_lines (. X3 ([])) (. X4 ([])))", null ], [ "(unif_pairs ([]))", null ], [ "(unif_pairs (. A (. B Pairs)))", "(',' (unif A B) (unif_pairs Pairs))" ], [ "(unif (w A) (w A))", null ], [ "(unif (black) (black))", null ], [ "(unif (black) (w X5))", null ], [ "(unif (w X6) (black))", null ] ] }, "graph": { "nodes": { "type": "Nodes", "750": { "goal": [ { "clause": 12, "scope": 10, "term": "(',' (unif T141 T142) (unif_pairs T143))" }, { "clause": 13, "scope": 10, "term": "(',' (unif T141 T142) (unif_pairs T143))" }, { "clause": 14, "scope": 10, "term": "(',' (unif T141 T142) (unif_pairs T143))" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "751": { "goal": [{ "clause": -1, "scope": -1, "term": "(unif_pairs T149)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "752": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "511": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "753": { "goal": [{ "clause": 12, "scope": 10, "term": "(',' (unif T141 T142) (unif_pairs T143))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "754": { "goal": [ { "clause": 13, "scope": 10, "term": "(',' (unif T141 T142) (unif_pairs T143))" }, { "clause": 14, "scope": 10, "term": "(',' (unif T141 T142) (unif_pairs T143))" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "755": { "goal": [{ "clause": -1, "scope": -1, "term": "(unif_pairs T150)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "756": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "757": { "goal": [{ "clause": 13, "scope": 10, "term": "(',' (unif T141 T142) (unif_pairs T143))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "758": { "goal": [{ "clause": 14, "scope": 10, "term": "(',' (unif T141 T142) (unif_pairs T143))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "759": { "goal": [{ "clause": -1, "scope": -1, "term": "(unif_pairs T156)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "760": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "3": { "goal": [{ "clause": -1, "scope": -1, "term": "(shapes T1 T2)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T1"], "free": [], "exprvars": [] } }, "762": { "goal": [{ "clause": -1, "scope": -1, "term": "(unif_pairs T160)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "246": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (varmat T5 X11) (unif_matrx X11))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T5"], "free": ["X11"], "exprvars": [] } }, "763": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "5": { "goal": [{ "clause": 0, "scope": 1, "term": "(shapes T1 T2)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T1"], "free": [], "exprvars": [] } }, "529": { "goal": [{ "clause": 2, "scope": 2, "term": "(',' (varmat T5 X11) (unif_matrx X11))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T5"], "free": ["X11"], "exprvars": [] } }, "770": { "goal": [{ "clause": 12, "scope": 8, "term": "(',' (unif T123 T124) (unif_pairs T125))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "771": { "goal": [ { "clause": 13, "scope": 8, "term": "(',' (unif T123 T124) (unif_pairs T125))" }, { "clause": 14, "scope": 8, "term": "(',' (unif T123 T124) (unif_pairs T125))" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "530": { "goal": [ { "clause": 3, "scope": 2, "term": "(',' (varmat T5 X11) (unif_matrx X11))" }, { "clause": 4, "scope": 2, "term": "(',' (varmat T5 X11) (unif_matrx X11))" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T5"], "free": ["X11"], "exprvars": [] } }, "772": { "goal": [{ "clause": -1, "scope": -1, "term": "(unif_pairs T161)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "773": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "774": { "goal": [{ "clause": 13, "scope": 8, "term": "(',' (unif T123 T124) (unif_pairs T125))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "775": { "goal": [{ "clause": 14, "scope": 8, "term": "(',' (unif T123 T124) (unif_pairs T125))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "259": { "goal": [ { "clause": 1, "scope": 2, "term": "(',' (varmat T5 X11) (unif_matrx X11))" }, { "clause": 2, "scope": 2, "term": "(',' (varmat T5 X11) (unif_matrx X11))" }, { "clause": 3, "scope": 2, "term": "(',' (varmat T5 X11) (unif_matrx X11))" }, { "clause": 4, "scope": 2, "term": "(',' (varmat T5 X11) (unif_matrx X11))" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T5"], "free": ["X11"], "exprvars": [] } }, "776": { "goal": [{ "clause": -1, "scope": -1, "term": "(unif_pairs T167)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "777": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "778": { "goal": [{ "clause": -1, "scope": -1, "term": "(unif_pairs T171)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "779": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "780": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "781": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "782": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "783": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "784": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "785": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "786": { "goal": [{ "clause": 3, "scope": 2, "term": "(',' (varmat T5 X11) (unif_matrx X11))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T5"], "free": ["X11"], "exprvars": [] } }, "787": { "goal": [{ "clause": 4, "scope": 2, "term": "(',' (varmat T5 X11) (unif_matrx X11))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T5"], "free": ["X11"], "exprvars": [] } }, "700": { "goal": [ { "clause": 7, "scope": 6, "term": "(unif_lines T56 T57)" }, { "clause": 8, "scope": 6, "term": "(unif_lines T56 T57)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "788": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (varmat T194 X245) (unif_matrx (. (black) X245)))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T194"], "free": ["X245"], "exprvars": [] } }, "789": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "705": { "goal": [{ "clause": 7, "scope": 6, "term": "(unif_lines T56 T57)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "706": { "goal": [{ "clause": 8, "scope": 6, "term": "(unif_lines T56 T57)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "790": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (varmat T197 X260) (unif_matrx (. (w X259) X260)))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T197"], "free": [ "X259", "X260" ], "exprvars": [] } }, "791": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "679": { "goal": [{ "clause": -1, "scope": -1, "term": "(varmat T16 X48)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T16"], "free": ["X48"], "exprvars": [] } }, "713": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (unif_pairs (. T103 (. T104 (. T105 (. T106 (. T103 (. T105 (. T104 (. T106 (. T103 (. T106 (. T104 (. T105 ([])))))))))))))) (unif_lines (. T104 T107) (. T106 T108)))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "318": { "goal": [{ "clause": -1, "scope": -1, "term": "(unif_matrx ([]))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "714": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "717": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (unif_pairs (. T103 T109)) (unif_lines (. T104 T107) (. T106 T108)))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "680": { "goal": [{ "clause": -1, "scope": -1, "term": "(unif_matrx (. T17 T37))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "286": { "goal": [{ "clause": 1, "scope": 2, "term": "(',' (varmat T5 X11) (unif_matrx X11))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T5"], "free": ["X11"], "exprvars": [] } }, "683": { "goal": [ { "clause": 5, "scope": 5, "term": "(unif_matrx (. T17 T37))" }, { "clause": 6, "scope": 5, "term": "(unif_matrx (. T17 T37))" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "686": { "goal": [{ "clause": 5, "scope": 5, "term": "(unif_matrx (. T17 T37))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "720": { "goal": [{ "clause": -1, "scope": -1, "term": "(unif_pairs (. T103 T109))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "688": { "goal": [{ "clause": 6, "scope": 5, "term": "(unif_matrx (. T17 T37))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "721": { "goal": [{ "clause": -1, "scope": -1, "term": "(unif_lines (. T110 T111) (. T112 T113))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "722": { "goal": [ { "clause": 9, "scope": 7, "term": "(unif_pairs (. T103 T109))" }, { "clause": 10, "scope": 7, "term": "(unif_pairs (. T103 T109))" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "602": { "goal": [ { "clause": 1, "scope": 4, "term": "(varmat T15 X47)" }, { "clause": 2, "scope": 4, "term": "(varmat T15 X47)" }, { "clause": 3, "scope": 4, "term": "(varmat T15 X47)" }, { "clause": 4, "scope": 4, "term": "(varmat T15 X47)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T15"], "free": ["X47"], "exprvars": [] } }, "723": { "goal": [{ "clause": 10, "scope": 7, "term": "(unif_pairs (. T103 T109))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "603": { "goal": [{ "clause": 1, "scope": 4, "term": "(varmat T15 X47)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T15"], "free": ["X47"], "exprvars": [] } }, "604": { "goal": [ { "clause": 2, "scope": 4, "term": "(varmat T15 X47)" }, { "clause": 3, "scope": 4, "term": "(varmat T15 X47)" }, { "clause": 4, "scope": 4, "term": "(varmat T15 X47)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T15"], "free": ["X47"], "exprvars": [] } }, "605": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "726": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (unif T123 T124) (unif_pairs T125))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "606": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "727": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "607": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "728": { "goal": [ { "clause": 11, "scope": 8, "term": "(',' (unif T123 T124) (unif_pairs T125))" }, { "clause": 12, "scope": 8, "term": "(',' (unif T123 T124) (unif_pairs T125))" }, { "clause": 13, "scope": 8, "term": "(',' (unif T123 T124) (unif_pairs T125))" }, { "clause": 14, "scope": 8, "term": "(',' (unif T123 T124) (unif_pairs T125))" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "608": { "goal": [{ "clause": 2, "scope": 4, "term": "(varmat T15 X47)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T15"], "free": ["X47"], "exprvars": [] } }, "609": { "goal": [ { "clause": 3, "scope": 4, "term": "(varmat T15 X47)" }, { "clause": 4, "scope": 4, "term": "(varmat T15 X47)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T15"], "free": ["X47"], "exprvars": [] } }, "290": { "goal": [ { "clause": 2, "scope": 2, "term": "(',' (varmat T5 X11) (unif_matrx X11))" }, { "clause": 3, "scope": 2, "term": "(',' (varmat T5 X11) (unif_matrx X11))" }, { "clause": 4, "scope": 2, "term": "(',' (varmat T5 X11) (unif_matrx X11))" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T5"], "free": ["X11"], "exprvars": [] } }, "571": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (',' (varmat T15 X47) (varmat T16 X48)) (unif_matrx (. X47 X48)))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T15", "T16" ], "free": [ "X47", "X48" ], "exprvars": [] } }, "692": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (unif_lines T56 T57) (unif_matrx (. T57 T58)))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "330": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "572": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "693": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "696": { "goal": [{ "clause": -1, "scope": -1, "term": "(unif_lines T56 T57)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "576": { "goal": [{ "clause": -1, "scope": -1, "term": "(varmat T15 X47)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T15"], "free": ["X47"], "exprvars": [] } }, "697": { "goal": [{ "clause": -1, "scope": -1, "term": "(unif_matrx (. T65 T66))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "577": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (varmat T16 X48) (unif_matrx (. T17 X48)))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T16"], "free": ["X48"], "exprvars": [] } }, "610": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (varmat T26 X77) (varmat T27 X78))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T26", "T27" ], "free": [ "X77", "X78" ], "exprvars": [] } }, "612": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "614": { "goal": [{ "clause": -1, "scope": -1, "term": "(varmat T26 X77)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T26"], "free": ["X77"], "exprvars": [] } }, "735": { "goal": [{ "clause": 11, "scope": 8, "term": "(',' (unif T123 T124) (unif_pairs T125))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "615": { "goal": [{ "clause": -1, "scope": -1, "term": "(varmat T27 X78)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T27"], "free": ["X78"], "exprvars": [] } }, "736": { "goal": [ { "clause": 12, "scope": 8, "term": "(',' (unif T123 T124) (unif_pairs T125))" }, { "clause": 13, "scope": 8, "term": "(',' (unif T123 T124) (unif_pairs T125))" }, { "clause": 14, "scope": 8, "term": "(',' (unif T123 T124) (unif_pairs T125))" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "738": { "goal": [{ "clause": -1, "scope": -1, "term": "(unif_pairs T131)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "739": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "619": { "goal": [{ "clause": 3, "scope": 4, "term": "(varmat T15 X47)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T15"], "free": ["X47"], "exprvars": [] } }, "740": { "goal": [ { "clause": 9, "scope": 9, "term": "(unif_pairs T131)" }, { "clause": 10, "scope": 9, "term": "(unif_pairs T131)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "620": { "goal": [{ "clause": 4, "scope": 4, "term": "(varmat T15 X47)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T15"], "free": ["X47"], "exprvars": [] } }, "741": { "goal": [{ "clause": 9, "scope": 9, "term": "(unif_pairs T131)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "742": { "goal": [{ "clause": 10, "scope": 9, "term": "(unif_pairs T131)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "743": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "623": { "goal": [{ "clause": -1, "scope": -1, "term": "(varmat T33 X93)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T33"], "free": ["X93"], "exprvars": [] } }, "744": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "624": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "745": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "746": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (unif T141 T142) (unif_pairs T143))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "747": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "748": { "goal": [ { "clause": 11, "scope": 10, "term": "(',' (unif T141 T142) (unif_pairs T143))" }, { "clause": 12, "scope": 10, "term": "(',' (unif T141 T142) (unif_pairs T143))" }, { "clause": 13, "scope": 10, "term": "(',' (unif T141 T142) (unif_pairs T143))" }, { "clause": 14, "scope": 10, "term": "(',' (unif T141 T142) (unif_pairs T143))" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "628": { "goal": [{ "clause": -1, "scope": -1, "term": "(varmat T36 X108)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T36"], "free": ["X108"], "exprvars": [] } }, "749": { "goal": [{ "clause": 11, "scope": 10, "term": "(',' (unif T141 T142) (unif_pairs T143))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "508": { "goal": [ { "clause": 5, "scope": 3, "term": "(unif_matrx ([]))" }, { "clause": 6, "scope": 3, "term": "(unif_matrx ([]))" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "629": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "509": { "goal": [{ "clause": 6, "scope": 3, "term": "(unif_matrx ([]))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } } }, "edges": [ { "from": 3, "to": 5, "label": "CASE" }, { "from": 5, "to": 246, "label": "ONLY EVAL with clause\nshapes(X9, X10) :- ','(varmat(X9, X11), unif_matrx(X11)).\nand substitutionT1 -> T5,\nX9 -> T5,\nT2 -> T6,\nX10 -> T6" }, { "from": 246, "to": 259, "label": "CASE" }, { "from": 259, "to": 286, "label": "PARALLEL" }, { "from": 259, "to": 290, "label": "PARALLEL" }, { "from": 286, "to": 318, "label": "EVAL with clause\nvarmat([], []).\nand substitutionT5 -> [],\nX11 -> []" }, { "from": 286, "to": 330, "label": "EVAL-BACKTRACK" }, { "from": 290, "to": 529, "label": "PARALLEL" }, { "from": 290, "to": 530, "label": "PARALLEL" }, { "from": 318, "to": 508, "label": "CASE" }, { "from": 508, "to": 509, "label": "BACKTRACK\nfor clause: unif_matrx(.(L1, .(L2, Ls))) :- ','(unif_lines(L1, L2), unif_matrx(.(L2, Ls)))because of non-unification" }, { "from": 509, "to": 511, "label": "BACKTRACK\nfor clause: unif_matrx(.(X2, []))because of non-unification" }, { "from": 529, "to": 571, "label": "EVAL with clause\nvarmat(.(X43, X44), .(X45, X46)) :- ','(varmat(X43, X45), varmat(X44, X46)).\nand substitutionX43 -> T15,\nX44 -> T16,\nT5 -> .(T15, T16),\nX45 -> X47,\nX46 -> X48,\nX11 -> .(X47, X48)" }, { "from": 529, "to": 572, "label": "EVAL-BACKTRACK" }, { "from": 530, "to": 786, "label": "PARALLEL" }, { "from": 530, "to": 787, "label": "PARALLEL" }, { "from": 571, "to": 576, "label": "SPLIT 1" }, { "from": 571, "to": 577, "label": "SPLIT 2\nnew knowledge:\nT15 is ground\nreplacements:X47 -> T17" }, { "from": 576, "to": 602, "label": "CASE" }, { "from": 577, "to": 679, "label": "SPLIT 1" }, { "from": 577, "to": 680, "label": "SPLIT 2\nnew knowledge:\nT16 is ground\nreplacements:X48 -> T37" }, { "from": 602, "to": 603, "label": "PARALLEL" }, { "from": 602, "to": 604, "label": "PARALLEL" }, { "from": 603, "to": 605, "label": "EVAL with clause\nvarmat([], []).\nand substitutionT15 -> [],\nX47 -> []" }, { "from": 603, "to": 606, "label": "EVAL-BACKTRACK" }, { "from": 604, "to": 608, "label": "PARALLEL" }, { "from": 604, "to": 609, "label": "PARALLEL" }, { "from": 605, "to": 607, "label": "SUCCESS" }, { "from": 608, "to": 610, "label": "EVAL with clause\nvarmat(.(X73, X74), .(X75, X76)) :- ','(varmat(X73, X75), varmat(X74, X76)).\nand substitutionX73 -> T26,\nX74 -> T27,\nT15 -> .(T26, T27),\nX75 -> X77,\nX76 -> X78,\nX47 -> .(X77, X78)" }, { "from": 608, "to": 612, "label": "EVAL-BACKTRACK" }, { "from": 609, "to": 619, "label": "PARALLEL" }, { "from": 609, "to": 620, "label": "PARALLEL" }, { "from": 610, "to": 614, "label": "SPLIT 1" }, { "from": 610, "to": 615, "label": "SPLIT 2\nnew knowledge:\nT26 is ground\nreplacements:X77 -> T28" }, { "from": 614, "to": 576, "label": "INSTANCE with matching:\nT15 -> T26\nX47 -> X77" }, { "from": 615, "to": 576, "label": "INSTANCE with matching:\nT15 -> T27\nX47 -> X78" }, { "from": 619, "to": 623, "label": "EVAL with clause\nvarmat(.(black, X91), .(black, X92)) :- varmat(X91, X92).\nand substitutionX91 -> T33,\nT15 -> .(black, T33),\nX92 -> X93,\nX47 -> .(black, X93)" }, { "from": 619, "to": 624, "label": "EVAL-BACKTRACK" }, { "from": 620, "to": 628, "label": "EVAL with clause\nvarmat(.(white, X104), .(w(X105), X106)) :- varmat(X104, X106).\nand substitutionX104 -> T36,\nT15 -> .(white, T36),\nX105 -> X107,\nX106 -> X108,\nX47 -> .(w(X107), X108)" }, { "from": 620, "to": 629, "label": "EVAL-BACKTRACK" }, { "from": 623, "to": 576, "label": "INSTANCE with matching:\nT15 -> T33\nX47 -> X93" }, { "from": 628, "to": 576, "label": "INSTANCE with matching:\nT15 -> T36\nX47 -> X108" }, { "from": 679, "to": 576, "label": "INSTANCE with matching:\nT15 -> T16\nX47 -> X48" }, { "from": 680, "to": 683, "label": "CASE" }, { "from": 683, "to": 686, "label": "PARALLEL" }, { "from": 683, "to": 688, "label": "PARALLEL" }, { "from": 686, "to": 692, "label": "EVAL with clause\nunif_matrx(.(X124, .(X125, X126))) :- ','(unif_lines(X124, X125), unif_matrx(.(X125, X126))).\nand substitutionT17 -> T56,\nX124 -> T56,\nX125 -> T57,\nX126 -> T58,\nT37 -> .(T57, T58),\nT53 -> T56,\nT54 -> T57,\nT55 -> T58" }, { "from": 686, "to": 693, "label": "EVAL-BACKTRACK" }, { "from": 688, "to": 783, "label": "EVAL with clause\nunif_matrx(.(X230, [])).\nand substitutionT17 -> T189,\nX230 -> T189,\nT37 -> []" }, { "from": 688, "to": 784, "label": "EVAL-BACKTRACK" }, { "from": 692, "to": 696, "label": "SPLIT 1" }, { "from": 692, "to": 697, "label": "SPLIT 2\nreplacements:T57 -> T65,\nT58 -> T66" }, { "from": 696, "to": 700, "label": "CASE" }, { "from": 697, "to": 680, "label": "INSTANCE with matching:\nT17 -> T65\nT37 -> T66" }, { "from": 700, "to": 705, "label": "PARALLEL" }, { "from": 700, "to": 706, "label": "PARALLEL" }, { "from": 705, "to": 713, "label": "EVAL with clause\nunif_lines(.(X163, .(X164, X165)), .(X166, .(X167, X168))) :- ','(unif_pairs(.(X163, .(X164, .(X166, .(X167, .(X163, .(X166, .(X164, .(X167, .(X163, .(X167, .(X164, .(X166, []))))))))))))), unif_lines(.(X164, X165), .(X167, X168))).\nand substitutionX163 -> T103,\nX164 -> T104,\nX165 -> T107,\nT56 -> .(T103, .(T104, T107)),\nX166 -> T105,\nX167 -> T106,\nX168 -> T108,\nT57 -> .(T105, .(T106, T108)),\nT97 -> T103,\nT98 -> T104,\nT100 -> T105,\nT101 -> T106,\nT99 -> T107,\nT102 -> T108" }, { "from": 705, "to": 714, "label": "EVAL-BACKTRACK" }, { "from": 706, "to": 780, "label": "EVAL with clause\nunif_lines(.(X223, []), .(X224, [])).\nand substitutionX223 -> T182,\nT56 -> .(T182, []),\nX224 -> T183,\nT57 -> .(T183, [])" }, { "from": 706, "to": 781, "label": "EVAL-BACKTRACK" }, { "from": 713, "to": 717, "label": "GENERALIZATION\nT109 <-- .(T104, .(T105, .(T106, .(T103, .(T105, .(T104, .(T106, .(T103, .(T106, .(T104, .(T105, [])))))))))))" }, { "from": 717, "to": 720, "label": "SPLIT 1" }, { "from": 717, "to": 721, "label": "SPLIT 2\nreplacements:T104 -> T110,\nT107 -> T111,\nT106 -> T112,\nT108 -> T113" }, { "from": 720, "to": 722, "label": "CASE" }, { "from": 721, "to": 696, "label": "INSTANCE with matching:\nT56 -> .(T110, T111)\nT57 -> .(T112, T113)" }, { "from": 722, "to": 723, "label": "BACKTRACK\nfor clause: unif_pairs([])because of non-unification" }, { "from": 723, "to": 726, "label": "EVAL with clause\nunif_pairs(.(X175, .(X176, X177))) :- ','(unif(X175, X176), unif_pairs(X177)).\nand substitutionT103 -> T123,\nX175 -> T123,\nX176 -> T124,\nX177 -> T125,\nT109 -> .(T124, T125),\nT120 -> T123,\nT121 -> T124,\nT122 -> T125" }, { "from": 723, "to": 727, "label": "EVAL-BACKTRACK" }, { "from": 726, "to": 728, "label": "CASE" }, { "from": 728, "to": 735, "label": "PARALLEL" }, { "from": 728, "to": 736, "label": "PARALLEL" }, { "from": 735, "to": 738, "label": "EVAL with clause\nunif(w(X182), w(X182)).\nand substitutionX182 -> T130,\nT123 -> w(T130),\nT124 -> w(T130),\nT125 -> T131" }, { "from": 735, "to": 739, "label": "EVAL-BACKTRACK" }, { "from": 736, "to": 770, "label": "PARALLEL" }, { "from": 736, "to": 771, "label": "PARALLEL" }, { "from": 738, "to": 740, "label": "CASE" }, { "from": 740, "to": 741, "label": "PARALLEL" }, { "from": 740, "to": 742, "label": "PARALLEL" }, { "from": 741, "to": 743, "label": "EVAL with clause\nunif_pairs([]).\nand substitutionT131 -> []" }, { "from": 741, "to": 744, "label": "EVAL-BACKTRACK" }, { "from": 742, "to": 746, "label": "EVAL with clause\nunif_pairs(.(X189, .(X190, X191))) :- ','(unif(X189, X190), unif_pairs(X191)).\nand substitutionX189 -> T141,\nX190 -> T142,\nX191 -> T143,\nT131 -> .(T141, .(T142, T143)),\nT138 -> T141,\nT139 -> T142,\nT140 -> T143" }, { "from": 742, "to": 747, "label": "EVAL-BACKTRACK" }, { "from": 743, "to": 745, "label": "SUCCESS" }, { "from": 746, "to": 748, "label": "CASE" }, { "from": 748, "to": 749, "label": "PARALLEL" }, { "from": 748, "to": 750, "label": "PARALLEL" }, { "from": 749, "to": 751, "label": "EVAL with clause\nunif(w(X196), w(X196)).\nand substitutionX196 -> T148,\nT141 -> w(T148),\nT142 -> w(T148),\nT143 -> T149" }, { "from": 749, "to": 752, "label": "EVAL-BACKTRACK" }, { "from": 750, "to": 753, "label": "PARALLEL" }, { "from": 750, "to": 754, "label": "PARALLEL" }, { "from": 751, "to": 738, "label": "INSTANCE with matching:\nT131 -> T149" }, { "from": 753, "to": 755, "label": "EVAL with clause\nunif(black, black).\nand substitutionT141 -> black,\nT142 -> black,\nT143 -> T150" }, { "from": 753, "to": 756, "label": "EVAL-BACKTRACK" }, { "from": 754, "to": 757, "label": "PARALLEL" }, { "from": 754, "to": 758, "label": "PARALLEL" }, { "from": 755, "to": 738, "label": "INSTANCE with matching:\nT131 -> T150" }, { "from": 757, "to": 759, "label": "EVAL with clause\nunif(black, w(X201)).\nand substitutionT141 -> black,\nX201 -> T155,\nT142 -> w(T155),\nT143 -> T156" }, { "from": 757, "to": 760, "label": "EVAL-BACKTRACK" }, { "from": 758, "to": 762, "label": "EVAL with clause\nunif(w(X204), black).\nand substitutionX204 -> T159,\nT141 -> w(T159),\nT142 -> black,\nT143 -> T160" }, { "from": 758, "to": 763, "label": "EVAL-BACKTRACK" }, { "from": 759, "to": 738, "label": "INSTANCE with matching:\nT131 -> T156" }, { "from": 762, "to": 738, "label": "INSTANCE with matching:\nT131 -> T160" }, { "from": 770, "to": 772, "label": "EVAL with clause\nunif(black, black).\nand substitutionT123 -> black,\nT124 -> black,\nT125 -> T161" }, { "from": 770, "to": 773, "label": "EVAL-BACKTRACK" }, { "from": 771, "to": 774, "label": "PARALLEL" }, { "from": 771, "to": 775, "label": "PARALLEL" }, { "from": 772, "to": 738, "label": "INSTANCE with matching:\nT131 -> T161" }, { "from": 774, "to": 776, "label": "EVAL with clause\nunif(black, w(X209)).\nand substitutionT123 -> black,\nX209 -> T166,\nT124 -> w(T166),\nT125 -> T167" }, { "from": 774, "to": 777, "label": "EVAL-BACKTRACK" }, { "from": 775, "to": 778, "label": "EVAL with clause\nunif(w(X212), black).\nand substitutionX212 -> T170,\nT123 -> w(T170),\nT124 -> black,\nT125 -> T171" }, { "from": 775, "to": 779, "label": "EVAL-BACKTRACK" }, { "from": 776, "to": 738, "label": "INSTANCE with matching:\nT131 -> T167" }, { "from": 778, "to": 738, "label": "INSTANCE with matching:\nT131 -> T171" }, { "from": 780, "to": 782, "label": "SUCCESS" }, { "from": 783, "to": 785, "label": "SUCCESS" }, { "from": 786, "to": 788, "label": "EVAL with clause\nvarmat(.(black, X243), .(black, X244)) :- varmat(X243, X244).\nand substitutionX243 -> T194,\nT5 -> .(black, T194),\nX244 -> X245,\nX11 -> .(black, X245)" }, { "from": 786, "to": 789, "label": "EVAL-BACKTRACK" }, { "from": 787, "to": 790, "label": "EVAL with clause\nvarmat(.(white, X256), .(w(X257), X258)) :- varmat(X256, X258).\nand substitutionX256 -> T197,\nT5 -> .(white, T197),\nX257 -> X259,\nX258 -> X260,\nX11 -> .(w(X259), X260)" }, { "from": 787, "to": 791, "label": "EVAL-BACKTRACK" }, { "from": 788, "to": 577, "label": "INSTANCE with matching:\nT16 -> T194\nX48 -> X245\nT17 -> black" }, { "from": 790, "to": 577, "label": "INSTANCE with matching:\nT16 -> T197\nX48 -> X260\nT17 -> w(X259)" } ], "type": "Graph" } } ---------------------------------------- (2) Obligation: Triples: varmatA(.(X1, X2), .(X3, X4)) :- varmatA(X1, X3). varmatA(.(X1, X2), .(X3, X4)) :- ','(varmatcA(X1, X3), varmatA(X2, X4)). varmatA(.(black, X1), .(black, X2)) :- varmatA(X1, X2). varmatA(.(white, X1), .(w(X2), X3)) :- varmatA(X1, X3). unif_matrxB(X1, .(X2, X3)) :- unif_linesC(X1, X2). unif_matrxB(X1, .(X2, X3)) :- ','(unif_linescC(X1, X2), unif_matrxB(X2, X3)). unif_linesC(.(X1, .(X2, X3)), .(X4, .(X5, X6))) :- pD(X1, .(X2, .(X4, .(X5, .(X1, .(X4, .(X2, .(X5, .(X1, .(X5, .(X2, .(X4, []))))))))))), X2, X3, X5, X6). unif_pairsE(.(w(X1), .(w(X1), X2))) :- unif_pairsE(X2). unif_pairsE(.(black, .(black, X1))) :- unif_pairsE(X1). unif_pairsE(.(black, .(w(X1), X2))) :- unif_pairsE(X2). unif_pairsE(.(w(X1), .(black, X2))) :- unif_pairsE(X2). pF(X1, X2, X3) :- varmatA(X1, X2). pF(X1, X2, X3) :- ','(varmatcA(X1, X2), unif_matrxB(X3, X2)). pD(w(X1), .(w(X1), X2), X3, X4, X5, X6) :- unif_pairsE(X2). pD(black, .(black, X1), X2, X3, X4, X5) :- unif_pairsE(X1). pD(black, .(w(X1), X2), X3, X4, X5, X6) :- unif_pairsE(X2). pD(w(X1), .(black, X2), X3, X4, X5, X6) :- unif_pairsE(X2). pD(X1, X2, X3, X4, X5, X6) :- ','(unif_pairscG(X1, X2), unif_linesC(.(X3, X4), .(X5, X6))). shapesH(.(X1, X2), X3) :- varmatA(X1, X4). shapesH(.(X1, X2), X3) :- ','(varmatcA(X1, X4), pF(X2, X5, X4)). shapesH(.(black, X1), X2) :- pF(X1, X3, black). shapesH(.(white, X1), X2) :- pF(X1, X3, w(X4)). Clauses: varmatcA([], []). varmatcA(.(X1, X2), .(X3, X4)) :- ','(varmatcA(X1, X3), varmatcA(X2, X4)). varmatcA(.(black, X1), .(black, X2)) :- varmatcA(X1, X2). varmatcA(.(white, X1), .(w(X2), X3)) :- varmatcA(X1, X3). unif_matrxcB(X1, .(X2, X3)) :- ','(unif_linescC(X1, X2), unif_matrxcB(X2, X3)). unif_matrxcB(X1, []). unif_linescC(.(X1, .(X2, X3)), .(X4, .(X5, X6))) :- qcD(X1, .(X2, .(X4, .(X5, .(X1, .(X4, .(X2, .(X5, .(X1, .(X5, .(X2, .(X4, []))))))))))), X2, X3, X5, X6). unif_linescC(.(X1, []), .(X2, [])). unif_pairscE([]). unif_pairscE(.(w(X1), .(w(X1), X2))) :- unif_pairscE(X2). unif_pairscE(.(black, .(black, X1))) :- unif_pairscE(X1). unif_pairscE(.(black, .(w(X1), X2))) :- unif_pairscE(X2). unif_pairscE(.(w(X1), .(black, X2))) :- unif_pairscE(X2). qcF(X1, X2, X3) :- ','(varmatcA(X1, X2), unif_matrxcB(X3, X2)). qcD(X1, X2, X3, X4, X5, X6) :- ','(unif_pairscG(X1, X2), unif_linescC(.(X3, X4), .(X5, X6))). unif_pairscG(w(X1), .(w(X1), X2)) :- unif_pairscE(X2). unif_pairscG(black, .(black, X1)) :- unif_pairscE(X1). unif_pairscG(black, .(w(X1), X2)) :- unif_pairscE(X2). unif_pairscG(w(X1), .(black, X2)) :- unif_pairscE(X2). Afs: shapesH(x1, x2) = shapesH(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: shapesH_in_2: (b,f) varmatA_in_2: (b,f) varmatcA_in_2: (b,f) pF_in_3: (b,f,b) unif_matrxB_in_2: (b,b) unif_linesC_in_2: (b,b) pD_in_6: (b,b,b,b,b,b) unif_pairsE_in_1: (b) unif_pairscG_in_2: (b,b) unif_pairscE_in_1: (b) unif_linescC_in_2: (b,b) qcD_in_6: (b,b,b,b,b,b) Transforming TRIPLES into the following Term Rewriting System: Pi DP problem: The TRS P consists of the following rules: SHAPESH_IN_GA(.(X1, X2), X3) -> U23_GA(X1, X2, X3, varmatA_in_ga(X1, X4)) SHAPESH_IN_GA(.(X1, X2), X3) -> VARMATA_IN_GA(X1, X4) VARMATA_IN_GA(.(X1, X2), .(X3, X4)) -> U1_GA(X1, X2, X3, X4, varmatA_in_ga(X1, X3)) VARMATA_IN_GA(.(X1, X2), .(X3, X4)) -> VARMATA_IN_GA(X1, X3) VARMATA_IN_GA(.(X1, X2), .(X3, X4)) -> U2_GA(X1, X2, X3, X4, varmatcA_in_ga(X1, X3)) U2_GA(X1, X2, X3, X4, varmatcA_out_ga(X1, X3)) -> U3_GA(X1, X2, X3, X4, varmatA_in_ga(X2, X4)) U2_GA(X1, X2, X3, X4, varmatcA_out_ga(X1, X3)) -> VARMATA_IN_GA(X2, X4) VARMATA_IN_GA(.(black, X1), .(black, X2)) -> U4_GA(X1, X2, varmatA_in_ga(X1, X2)) VARMATA_IN_GA(.(black, X1), .(black, X2)) -> VARMATA_IN_GA(X1, X2) VARMATA_IN_GA(.(white, X1), .(w(X2), X3)) -> U5_GA(X1, X2, X3, varmatA_in_ga(X1, X3)) VARMATA_IN_GA(.(white, X1), .(w(X2), X3)) -> VARMATA_IN_GA(X1, X3) SHAPESH_IN_GA(.(X1, X2), X3) -> U24_GA(X1, X2, X3, varmatcA_in_ga(X1, X4)) U24_GA(X1, X2, X3, varmatcA_out_ga(X1, X4)) -> U25_GA(X1, X2, X3, pF_in_gag(X2, X5, X4)) U24_GA(X1, X2, X3, varmatcA_out_ga(X1, X4)) -> PF_IN_GAG(X2, X5, X4) PF_IN_GAG(X1, X2, X3) -> U14_GAG(X1, X2, X3, varmatA_in_ga(X1, X2)) PF_IN_GAG(X1, X2, X3) -> VARMATA_IN_GA(X1, X2) PF_IN_GAG(X1, X2, X3) -> U15_GAG(X1, X2, X3, varmatcA_in_ga(X1, X2)) U15_GAG(X1, X2, X3, varmatcA_out_ga(X1, X2)) -> U16_GAG(X1, X2, X3, unif_matrxB_in_gg(X3, X2)) U15_GAG(X1, X2, X3, varmatcA_out_ga(X1, X2)) -> UNIF_MATRXB_IN_GG(X3, X2) UNIF_MATRXB_IN_GG(X1, .(X2, X3)) -> U6_GG(X1, X2, X3, unif_linesC_in_gg(X1, X2)) UNIF_MATRXB_IN_GG(X1, .(X2, X3)) -> UNIF_LINESC_IN_GG(X1, X2) UNIF_LINESC_IN_GG(.(X1, .(X2, X3)), .(X4, .(X5, X6))) -> U9_GG(X1, X2, X3, X4, X5, X6, pD_in_gggggg(X1, .(X2, .(X4, .(X5, .(X1, .(X4, .(X2, .(X5, .(X1, .(X5, .(X2, .(X4, []))))))))))), X2, X3, X5, X6)) UNIF_LINESC_IN_GG(.(X1, .(X2, X3)), .(X4, .(X5, X6))) -> PD_IN_GGGGGG(X1, .(X2, .(X4, .(X5, .(X1, .(X4, .(X2, .(X5, .(X1, .(X5, .(X2, .(X4, []))))))))))), X2, X3, X5, X6) PD_IN_GGGGGG(w(X1), .(w(X1), X2), X3, X4, X5, X6) -> U17_GGGGGG(X1, X2, X3, X4, X5, X6, unif_pairsE_in_g(X2)) PD_IN_GGGGGG(w(X1), .(w(X1), X2), X3, X4, X5, X6) -> UNIF_PAIRSE_IN_G(X2) UNIF_PAIRSE_IN_G(.(w(X1), .(w(X1), X2))) -> U10_G(X1, X2, unif_pairsE_in_g(X2)) UNIF_PAIRSE_IN_G(.(w(X1), .(w(X1), X2))) -> UNIF_PAIRSE_IN_G(X2) UNIF_PAIRSE_IN_G(.(black, .(black, X1))) -> U11_G(X1, unif_pairsE_in_g(X1)) UNIF_PAIRSE_IN_G(.(black, .(black, X1))) -> UNIF_PAIRSE_IN_G(X1) UNIF_PAIRSE_IN_G(.(black, .(w(X1), X2))) -> U12_G(X1, X2, unif_pairsE_in_g(X2)) UNIF_PAIRSE_IN_G(.(black, .(w(X1), X2))) -> UNIF_PAIRSE_IN_G(X2) UNIF_PAIRSE_IN_G(.(w(X1), .(black, X2))) -> U13_G(X1, X2, unif_pairsE_in_g(X2)) UNIF_PAIRSE_IN_G(.(w(X1), .(black, X2))) -> UNIF_PAIRSE_IN_G(X2) PD_IN_GGGGGG(black, .(black, X1), X2, X3, X4, X5) -> U18_GGGGGG(X1, X2, X3, X4, X5, unif_pairsE_in_g(X1)) PD_IN_GGGGGG(black, .(black, X1), X2, X3, X4, X5) -> UNIF_PAIRSE_IN_G(X1) PD_IN_GGGGGG(black, .(w(X1), X2), X3, X4, X5, X6) -> U19_GGGGGG(X1, X2, X3, X4, X5, X6, unif_pairsE_in_g(X2)) PD_IN_GGGGGG(black, .(w(X1), X2), X3, X4, X5, X6) -> UNIF_PAIRSE_IN_G(X2) PD_IN_GGGGGG(w(X1), .(black, X2), X3, X4, X5, X6) -> U20_GGGGGG(X1, X2, X3, X4, X5, X6, unif_pairsE_in_g(X2)) PD_IN_GGGGGG(w(X1), .(black, X2), X3, X4, X5, X6) -> UNIF_PAIRSE_IN_G(X2) PD_IN_GGGGGG(X1, X2, X3, X4, X5, X6) -> U21_GGGGGG(X1, X2, X3, X4, X5, X6, unif_pairscG_in_gg(X1, X2)) U21_GGGGGG(X1, X2, X3, X4, X5, X6, unif_pairscG_out_gg(X1, X2)) -> U22_GGGGGG(X1, X2, X3, X4, X5, X6, unif_linesC_in_gg(.(X3, X4), .(X5, X6))) U21_GGGGGG(X1, X2, X3, X4, X5, X6, unif_pairscG_out_gg(X1, X2)) -> UNIF_LINESC_IN_GG(.(X3, X4), .(X5, X6)) UNIF_MATRXB_IN_GG(X1, .(X2, X3)) -> U7_GG(X1, X2, X3, unif_linescC_in_gg(X1, X2)) U7_GG(X1, X2, X3, unif_linescC_out_gg(X1, X2)) -> U8_GG(X1, X2, X3, unif_matrxB_in_gg(X2, X3)) U7_GG(X1, X2, X3, unif_linescC_out_gg(X1, X2)) -> UNIF_MATRXB_IN_GG(X2, X3) SHAPESH_IN_GA(.(black, X1), X2) -> U26_GA(X1, X2, pF_in_gag(X1, X3, black)) SHAPESH_IN_GA(.(black, X1), X2) -> PF_IN_GAG(X1, X3, black) SHAPESH_IN_GA(.(white, X1), X2) -> U27_GA(X1, X2, pF_in_gag(X1, X3, w(X4))) SHAPESH_IN_GA(.(white, X1), X2) -> PF_IN_GAG(X1, X3, w(X4)) The TRS R consists of the following rules: varmatcA_in_ga([], []) -> varmatcA_out_ga([], []) varmatcA_in_ga(.(X1, X2), .(X3, X4)) -> U29_ga(X1, X2, X3, X4, varmatcA_in_ga(X1, X3)) varmatcA_in_ga(.(black, X1), .(black, X2)) -> U31_ga(X1, X2, varmatcA_in_ga(X1, X2)) varmatcA_in_ga(.(white, X1), .(w(X2), X3)) -> U32_ga(X1, X2, X3, varmatcA_in_ga(X1, X3)) U32_ga(X1, X2, X3, varmatcA_out_ga(X1, X3)) -> varmatcA_out_ga(.(white, X1), .(w(X2), X3)) U31_ga(X1, X2, varmatcA_out_ga(X1, X2)) -> varmatcA_out_ga(.(black, X1), .(black, X2)) U29_ga(X1, X2, X3, X4, varmatcA_out_ga(X1, X3)) -> U30_ga(X1, X2, X3, X4, varmatcA_in_ga(X2, X4)) U30_ga(X1, X2, X3, X4, varmatcA_out_ga(X2, X4)) -> varmatcA_out_ga(.(X1, X2), .(X3, X4)) unif_pairscG_in_gg(w(X1), .(w(X1), X2)) -> U44_gg(X1, X2, unif_pairscE_in_g(X2)) unif_pairscE_in_g([]) -> unif_pairscE_out_g([]) unif_pairscE_in_g(.(w(X1), .(w(X1), X2))) -> U36_g(X1, X2, unif_pairscE_in_g(X2)) unif_pairscE_in_g(.(black, .(black, X1))) -> U37_g(X1, unif_pairscE_in_g(X1)) unif_pairscE_in_g(.(black, .(w(X1), X2))) -> U38_g(X1, X2, unif_pairscE_in_g(X2)) unif_pairscE_in_g(.(w(X1), .(black, X2))) -> U39_g(X1, X2, unif_pairscE_in_g(X2)) U39_g(X1, X2, unif_pairscE_out_g(X2)) -> unif_pairscE_out_g(.(w(X1), .(black, X2))) U38_g(X1, X2, unif_pairscE_out_g(X2)) -> unif_pairscE_out_g(.(black, .(w(X1), X2))) U37_g(X1, unif_pairscE_out_g(X1)) -> unif_pairscE_out_g(.(black, .(black, X1))) U36_g(X1, X2, unif_pairscE_out_g(X2)) -> unif_pairscE_out_g(.(w(X1), .(w(X1), X2))) U44_gg(X1, X2, unif_pairscE_out_g(X2)) -> unif_pairscG_out_gg(w(X1), .(w(X1), X2)) unif_pairscG_in_gg(black, .(black, X1)) -> U45_gg(X1, unif_pairscE_in_g(X1)) U45_gg(X1, unif_pairscE_out_g(X1)) -> unif_pairscG_out_gg(black, .(black, X1)) unif_pairscG_in_gg(black, .(w(X1), X2)) -> U46_gg(X1, X2, unif_pairscE_in_g(X2)) U46_gg(X1, X2, unif_pairscE_out_g(X2)) -> unif_pairscG_out_gg(black, .(w(X1), X2)) unif_pairscG_in_gg(w(X1), .(black, X2)) -> U47_gg(X1, X2, unif_pairscE_in_g(X2)) U47_gg(X1, X2, unif_pairscE_out_g(X2)) -> unif_pairscG_out_gg(w(X1), .(black, X2)) unif_linescC_in_gg(.(X1, .(X2, X3)), .(X4, .(X5, X6))) -> U35_gg(X1, X2, X3, X4, X5, X6, qcD_in_gggggg(X1, .(X2, .(X4, .(X5, .(X1, .(X4, .(X2, .(X5, .(X1, .(X5, .(X2, .(X4, []))))))))))), X2, X3, X5, X6)) qcD_in_gggggg(X1, X2, X3, X4, X5, X6) -> U42_gggggg(X1, X2, X3, X4, X5, X6, unif_pairscG_in_gg(X1, X2)) U42_gggggg(X1, X2, X3, X4, X5, X6, unif_pairscG_out_gg(X1, X2)) -> U43_gggggg(X1, X2, X3, X4, X5, X6, unif_linescC_in_gg(.(X3, X4), .(X5, X6))) unif_linescC_in_gg(.(X1, []), .(X2, [])) -> unif_linescC_out_gg(.(X1, []), .(X2, [])) U43_gggggg(X1, X2, X3, X4, X5, X6, unif_linescC_out_gg(.(X3, X4), .(X5, X6))) -> qcD_out_gggggg(X1, X2, X3, X4, X5, X6) U35_gg(X1, X2, X3, X4, X5, X6, qcD_out_gggggg(X1, .(X2, .(X4, .(X5, .(X1, .(X4, .(X2, .(X5, .(X1, .(X5, .(X2, .(X4, []))))))))))), X2, X3, X5, X6)) -> unif_linescC_out_gg(.(X1, .(X2, X3)), .(X4, .(X5, X6))) The argument filtering Pi contains the following mapping: .(x1, x2) = .(x1, x2) varmatA_in_ga(x1, x2) = varmatA_in_ga(x1) varmatcA_in_ga(x1, x2) = varmatcA_in_ga(x1) [] = [] varmatcA_out_ga(x1, x2) = varmatcA_out_ga(x1, x2) U29_ga(x1, x2, x3, x4, x5) = U29_ga(x1, x2, x5) black = black U31_ga(x1, x2, x3) = U31_ga(x1, x3) white = white U32_ga(x1, x2, x3, x4) = U32_ga(x1, x4) w(x1) = w U30_ga(x1, x2, x3, x4, x5) = U30_ga(x1, x2, x3, x5) pF_in_gag(x1, x2, x3) = pF_in_gag(x1, x3) unif_matrxB_in_gg(x1, x2) = unif_matrxB_in_gg(x1, x2) unif_linesC_in_gg(x1, x2) = unif_linesC_in_gg(x1, x2) pD_in_gggggg(x1, x2, x3, x4, x5, x6) = pD_in_gggggg(x1, x2, x3, x4, x5, x6) unif_pairsE_in_g(x1) = unif_pairsE_in_g(x1) unif_pairscG_in_gg(x1, x2) = unif_pairscG_in_gg(x1, x2) U44_gg(x1, x2, x3) = U44_gg(x2, x3) unif_pairscE_in_g(x1) = unif_pairscE_in_g(x1) unif_pairscE_out_g(x1) = unif_pairscE_out_g(x1) U36_g(x1, x2, x3) = U36_g(x2, x3) U37_g(x1, x2) = U37_g(x1, x2) U38_g(x1, x2, x3) = U38_g(x2, x3) U39_g(x1, x2, x3) = U39_g(x2, x3) unif_pairscG_out_gg(x1, x2) = unif_pairscG_out_gg(x1, x2) U45_gg(x1, x2) = U45_gg(x1, x2) U46_gg(x1, x2, x3) = U46_gg(x2, x3) U47_gg(x1, x2, x3) = U47_gg(x2, x3) unif_linescC_in_gg(x1, x2) = unif_linescC_in_gg(x1, x2) U35_gg(x1, x2, x3, x4, x5, x6, x7) = U35_gg(x1, x2, x3, x4, x5, x6, x7) qcD_in_gggggg(x1, x2, x3, x4, x5, x6) = qcD_in_gggggg(x1, x2, x3, x4, x5, x6) U42_gggggg(x1, x2, x3, x4, x5, x6, x7) = U42_gggggg(x1, x2, x3, x4, x5, x6, x7) U43_gggggg(x1, x2, x3, x4, x5, x6, x7) = U43_gggggg(x1, x2, x3, x4, x5, x6, x7) unif_linescC_out_gg(x1, x2) = unif_linescC_out_gg(x1, x2) qcD_out_gggggg(x1, x2, x3, x4, x5, x6) = qcD_out_gggggg(x1, x2, x3, x4, x5, x6) SHAPESH_IN_GA(x1, x2) = SHAPESH_IN_GA(x1) U23_GA(x1, x2, x3, x4) = U23_GA(x1, x2, x4) VARMATA_IN_GA(x1, x2) = VARMATA_IN_GA(x1) U1_GA(x1, x2, x3, x4, x5) = U1_GA(x1, x2, x5) U2_GA(x1, x2, x3, x4, x5) = U2_GA(x1, x2, x5) U3_GA(x1, x2, x3, x4, x5) = U3_GA(x1, x2, x5) U4_GA(x1, x2, x3) = U4_GA(x1, x3) U5_GA(x1, x2, x3, x4) = U5_GA(x1, x4) U24_GA(x1, x2, x3, x4) = U24_GA(x1, x2, x4) U25_GA(x1, x2, x3, x4) = U25_GA(x1, x2, x4) PF_IN_GAG(x1, x2, x3) = PF_IN_GAG(x1, x3) U14_GAG(x1, x2, x3, x4) = U14_GAG(x1, x3, x4) U15_GAG(x1, x2, x3, x4) = U15_GAG(x1, x3, x4) U16_GAG(x1, x2, x3, x4) = U16_GAG(x1, x3, x4) UNIF_MATRXB_IN_GG(x1, x2) = UNIF_MATRXB_IN_GG(x1, x2) U6_GG(x1, x2, x3, x4) = U6_GG(x1, x2, x3, x4) UNIF_LINESC_IN_GG(x1, x2) = UNIF_LINESC_IN_GG(x1, x2) U9_GG(x1, x2, x3, x4, x5, x6, x7) = U9_GG(x1, x2, x3, x4, x5, x6, x7) PD_IN_GGGGGG(x1, x2, x3, x4, x5, x6) = PD_IN_GGGGGG(x1, x2, x3, x4, x5, x6) U17_GGGGGG(x1, x2, x3, x4, x5, x6, x7) = U17_GGGGGG(x2, x3, x4, x5, x6, x7) UNIF_PAIRSE_IN_G(x1) = UNIF_PAIRSE_IN_G(x1) U10_G(x1, x2, x3) = U10_G(x2, x3) U11_G(x1, x2) = U11_G(x1, x2) U12_G(x1, x2, x3) = U12_G(x2, x3) U13_G(x1, x2, x3) = U13_G(x2, x3) U18_GGGGGG(x1, x2, x3, x4, x5, x6) = U18_GGGGGG(x1, x2, x3, x4, x5, x6) U19_GGGGGG(x1, x2, x3, x4, x5, x6, x7) = U19_GGGGGG(x2, x3, x4, x5, x6, x7) U20_GGGGGG(x1, x2, x3, x4, x5, x6, x7) = U20_GGGGGG(x2, x3, x4, x5, x6, x7) U21_GGGGGG(x1, x2, x3, x4, x5, x6, x7) = U21_GGGGGG(x1, x2, x3, x4, x5, x6, x7) U22_GGGGGG(x1, x2, x3, x4, x5, x6, x7) = U22_GGGGGG(x1, x2, x3, x4, x5, x6, x7) U7_GG(x1, x2, x3, x4) = U7_GG(x1, x2, x3, x4) U8_GG(x1, x2, x3, x4) = U8_GG(x1, x2, x3, x4) U26_GA(x1, x2, x3) = U26_GA(x1, x3) U27_GA(x1, x2, x3) = U27_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: SHAPESH_IN_GA(.(X1, X2), X3) -> U23_GA(X1, X2, X3, varmatA_in_ga(X1, X4)) SHAPESH_IN_GA(.(X1, X2), X3) -> VARMATA_IN_GA(X1, X4) VARMATA_IN_GA(.(X1, X2), .(X3, X4)) -> U1_GA(X1, X2, X3, X4, varmatA_in_ga(X1, X3)) VARMATA_IN_GA(.(X1, X2), .(X3, X4)) -> VARMATA_IN_GA(X1, X3) VARMATA_IN_GA(.(X1, X2), .(X3, X4)) -> U2_GA(X1, X2, X3, X4, varmatcA_in_ga(X1, X3)) U2_GA(X1, X2, X3, X4, varmatcA_out_ga(X1, X3)) -> U3_GA(X1, X2, X3, X4, varmatA_in_ga(X2, X4)) U2_GA(X1, X2, X3, X4, varmatcA_out_ga(X1, X3)) -> VARMATA_IN_GA(X2, X4) VARMATA_IN_GA(.(black, X1), .(black, X2)) -> U4_GA(X1, X2, varmatA_in_ga(X1, X2)) VARMATA_IN_GA(.(black, X1), .(black, X2)) -> VARMATA_IN_GA(X1, X2) VARMATA_IN_GA(.(white, X1), .(w(X2), X3)) -> U5_GA(X1, X2, X3, varmatA_in_ga(X1, X3)) VARMATA_IN_GA(.(white, X1), .(w(X2), X3)) -> VARMATA_IN_GA(X1, X3) SHAPESH_IN_GA(.(X1, X2), X3) -> U24_GA(X1, X2, X3, varmatcA_in_ga(X1, X4)) U24_GA(X1, X2, X3, varmatcA_out_ga(X1, X4)) -> U25_GA(X1, X2, X3, pF_in_gag(X2, X5, X4)) U24_GA(X1, X2, X3, varmatcA_out_ga(X1, X4)) -> PF_IN_GAG(X2, X5, X4) PF_IN_GAG(X1, X2, X3) -> U14_GAG(X1, X2, X3, varmatA_in_ga(X1, X2)) PF_IN_GAG(X1, X2, X3) -> VARMATA_IN_GA(X1, X2) PF_IN_GAG(X1, X2, X3) -> U15_GAG(X1, X2, X3, varmatcA_in_ga(X1, X2)) U15_GAG(X1, X2, X3, varmatcA_out_ga(X1, X2)) -> U16_GAG(X1, X2, X3, unif_matrxB_in_gg(X3, X2)) U15_GAG(X1, X2, X3, varmatcA_out_ga(X1, X2)) -> UNIF_MATRXB_IN_GG(X3, X2) UNIF_MATRXB_IN_GG(X1, .(X2, X3)) -> U6_GG(X1, X2, X3, unif_linesC_in_gg(X1, X2)) UNIF_MATRXB_IN_GG(X1, .(X2, X3)) -> UNIF_LINESC_IN_GG(X1, X2) UNIF_LINESC_IN_GG(.(X1, .(X2, X3)), .(X4, .(X5, X6))) -> U9_GG(X1, X2, X3, X4, X5, X6, pD_in_gggggg(X1, .(X2, .(X4, .(X5, .(X1, .(X4, .(X2, .(X5, .(X1, .(X5, .(X2, .(X4, []))))))))))), X2, X3, X5, X6)) UNIF_LINESC_IN_GG(.(X1, .(X2, X3)), .(X4, .(X5, X6))) -> PD_IN_GGGGGG(X1, .(X2, .(X4, .(X5, .(X1, .(X4, .(X2, .(X5, .(X1, .(X5, .(X2, .(X4, []))))))))))), X2, X3, X5, X6) PD_IN_GGGGGG(w(X1), .(w(X1), X2), X3, X4, X5, X6) -> U17_GGGGGG(X1, X2, X3, X4, X5, X6, unif_pairsE_in_g(X2)) PD_IN_GGGGGG(w(X1), .(w(X1), X2), X3, X4, X5, X6) -> UNIF_PAIRSE_IN_G(X2) UNIF_PAIRSE_IN_G(.(w(X1), .(w(X1), X2))) -> U10_G(X1, X2, unif_pairsE_in_g(X2)) UNIF_PAIRSE_IN_G(.(w(X1), .(w(X1), X2))) -> UNIF_PAIRSE_IN_G(X2) UNIF_PAIRSE_IN_G(.(black, .(black, X1))) -> U11_G(X1, unif_pairsE_in_g(X1)) UNIF_PAIRSE_IN_G(.(black, .(black, X1))) -> UNIF_PAIRSE_IN_G(X1) UNIF_PAIRSE_IN_G(.(black, .(w(X1), X2))) -> U12_G(X1, X2, unif_pairsE_in_g(X2)) UNIF_PAIRSE_IN_G(.(black, .(w(X1), X2))) -> UNIF_PAIRSE_IN_G(X2) UNIF_PAIRSE_IN_G(.(w(X1), .(black, X2))) -> U13_G(X1, X2, unif_pairsE_in_g(X2)) UNIF_PAIRSE_IN_G(.(w(X1), .(black, X2))) -> UNIF_PAIRSE_IN_G(X2) PD_IN_GGGGGG(black, .(black, X1), X2, X3, X4, X5) -> U18_GGGGGG(X1, X2, X3, X4, X5, unif_pairsE_in_g(X1)) PD_IN_GGGGGG(black, .(black, X1), X2, X3, X4, X5) -> UNIF_PAIRSE_IN_G(X1) PD_IN_GGGGGG(black, .(w(X1), X2), X3, X4, X5, X6) -> U19_GGGGGG(X1, X2, X3, X4, X5, X6, unif_pairsE_in_g(X2)) PD_IN_GGGGGG(black, .(w(X1), X2), X3, X4, X5, X6) -> UNIF_PAIRSE_IN_G(X2) PD_IN_GGGGGG(w(X1), .(black, X2), X3, X4, X5, X6) -> U20_GGGGGG(X1, X2, X3, X4, X5, X6, unif_pairsE_in_g(X2)) PD_IN_GGGGGG(w(X1), .(black, X2), X3, X4, X5, X6) -> UNIF_PAIRSE_IN_G(X2) PD_IN_GGGGGG(X1, X2, X3, X4, X5, X6) -> U21_GGGGGG(X1, X2, X3, X4, X5, X6, unif_pairscG_in_gg(X1, X2)) U21_GGGGGG(X1, X2, X3, X4, X5, X6, unif_pairscG_out_gg(X1, X2)) -> U22_GGGGGG(X1, X2, X3, X4, X5, X6, unif_linesC_in_gg(.(X3, X4), .(X5, X6))) U21_GGGGGG(X1, X2, X3, X4, X5, X6, unif_pairscG_out_gg(X1, X2)) -> UNIF_LINESC_IN_GG(.(X3, X4), .(X5, X6)) UNIF_MATRXB_IN_GG(X1, .(X2, X3)) -> U7_GG(X1, X2, X3, unif_linescC_in_gg(X1, X2)) U7_GG(X1, X2, X3, unif_linescC_out_gg(X1, X2)) -> U8_GG(X1, X2, X3, unif_matrxB_in_gg(X2, X3)) U7_GG(X1, X2, X3, unif_linescC_out_gg(X1, X2)) -> UNIF_MATRXB_IN_GG(X2, X3) SHAPESH_IN_GA(.(black, X1), X2) -> U26_GA(X1, X2, pF_in_gag(X1, X3, black)) SHAPESH_IN_GA(.(black, X1), X2) -> PF_IN_GAG(X1, X3, black) SHAPESH_IN_GA(.(white, X1), X2) -> U27_GA(X1, X2, pF_in_gag(X1, X3, w(X4))) SHAPESH_IN_GA(.(white, X1), X2) -> PF_IN_GAG(X1, X3, w(X4)) The TRS R consists of the following rules: varmatcA_in_ga([], []) -> varmatcA_out_ga([], []) varmatcA_in_ga(.(X1, X2), .(X3, X4)) -> U29_ga(X1, X2, X3, X4, varmatcA_in_ga(X1, X3)) varmatcA_in_ga(.(black, X1), .(black, X2)) -> U31_ga(X1, X2, varmatcA_in_ga(X1, X2)) varmatcA_in_ga(.(white, X1), .(w(X2), X3)) -> U32_ga(X1, X2, X3, varmatcA_in_ga(X1, X3)) U32_ga(X1, X2, X3, varmatcA_out_ga(X1, X3)) -> varmatcA_out_ga(.(white, X1), .(w(X2), X3)) U31_ga(X1, X2, varmatcA_out_ga(X1, X2)) -> varmatcA_out_ga(.(black, X1), .(black, X2)) U29_ga(X1, X2, X3, X4, varmatcA_out_ga(X1, X3)) -> U30_ga(X1, X2, X3, X4, varmatcA_in_ga(X2, X4)) U30_ga(X1, X2, X3, X4, varmatcA_out_ga(X2, X4)) -> varmatcA_out_ga(.(X1, X2), .(X3, X4)) unif_pairscG_in_gg(w(X1), .(w(X1), X2)) -> U44_gg(X1, X2, unif_pairscE_in_g(X2)) unif_pairscE_in_g([]) -> unif_pairscE_out_g([]) unif_pairscE_in_g(.(w(X1), .(w(X1), X2))) -> U36_g(X1, X2, unif_pairscE_in_g(X2)) unif_pairscE_in_g(.(black, .(black, X1))) -> U37_g(X1, unif_pairscE_in_g(X1)) unif_pairscE_in_g(.(black, .(w(X1), X2))) -> U38_g(X1, X2, unif_pairscE_in_g(X2)) unif_pairscE_in_g(.(w(X1), .(black, X2))) -> U39_g(X1, X2, unif_pairscE_in_g(X2)) U39_g(X1, X2, unif_pairscE_out_g(X2)) -> unif_pairscE_out_g(.(w(X1), .(black, X2))) U38_g(X1, X2, unif_pairscE_out_g(X2)) -> unif_pairscE_out_g(.(black, .(w(X1), X2))) U37_g(X1, unif_pairscE_out_g(X1)) -> unif_pairscE_out_g(.(black, .(black, X1))) U36_g(X1, X2, unif_pairscE_out_g(X2)) -> unif_pairscE_out_g(.(w(X1), .(w(X1), X2))) U44_gg(X1, X2, unif_pairscE_out_g(X2)) -> unif_pairscG_out_gg(w(X1), .(w(X1), X2)) unif_pairscG_in_gg(black, .(black, X1)) -> U45_gg(X1, unif_pairscE_in_g(X1)) U45_gg(X1, unif_pairscE_out_g(X1)) -> unif_pairscG_out_gg(black, .(black, X1)) unif_pairscG_in_gg(black, .(w(X1), X2)) -> U46_gg(X1, X2, unif_pairscE_in_g(X2)) U46_gg(X1, X2, unif_pairscE_out_g(X2)) -> unif_pairscG_out_gg(black, .(w(X1), X2)) unif_pairscG_in_gg(w(X1), .(black, X2)) -> U47_gg(X1, X2, unif_pairscE_in_g(X2)) U47_gg(X1, X2, unif_pairscE_out_g(X2)) -> unif_pairscG_out_gg(w(X1), .(black, X2)) unif_linescC_in_gg(.(X1, .(X2, X3)), .(X4, .(X5, X6))) -> U35_gg(X1, X2, X3, X4, X5, X6, qcD_in_gggggg(X1, .(X2, .(X4, .(X5, .(X1, .(X4, .(X2, .(X5, .(X1, .(X5, .(X2, .(X4, []))))))))))), X2, X3, X5, X6)) qcD_in_gggggg(X1, X2, X3, X4, X5, X6) -> U42_gggggg(X1, X2, X3, X4, X5, X6, unif_pairscG_in_gg(X1, X2)) U42_gggggg(X1, X2, X3, X4, X5, X6, unif_pairscG_out_gg(X1, X2)) -> U43_gggggg(X1, X2, X3, X4, X5, X6, unif_linescC_in_gg(.(X3, X4), .(X5, X6))) unif_linescC_in_gg(.(X1, []), .(X2, [])) -> unif_linescC_out_gg(.(X1, []), .(X2, [])) U43_gggggg(X1, X2, X3, X4, X5, X6, unif_linescC_out_gg(.(X3, X4), .(X5, X6))) -> qcD_out_gggggg(X1, X2, X3, X4, X5, X6) U35_gg(X1, X2, X3, X4, X5, X6, qcD_out_gggggg(X1, .(X2, .(X4, .(X5, .(X1, .(X4, .(X2, .(X5, .(X1, .(X5, .(X2, .(X4, []))))))))))), X2, X3, X5, X6)) -> unif_linescC_out_gg(.(X1, .(X2, X3)), .(X4, .(X5, X6))) The argument filtering Pi contains the following mapping: .(x1, x2) = .(x1, x2) varmatA_in_ga(x1, x2) = varmatA_in_ga(x1) varmatcA_in_ga(x1, x2) = varmatcA_in_ga(x1) [] = [] varmatcA_out_ga(x1, x2) = varmatcA_out_ga(x1, x2) U29_ga(x1, x2, x3, x4, x5) = U29_ga(x1, x2, x5) black = black U31_ga(x1, x2, x3) = U31_ga(x1, x3) white = white U32_ga(x1, x2, x3, x4) = U32_ga(x1, x4) w(x1) = w U30_ga(x1, x2, x3, x4, x5) = U30_ga(x1, x2, x3, x5) pF_in_gag(x1, x2, x3) = pF_in_gag(x1, x3) unif_matrxB_in_gg(x1, x2) = unif_matrxB_in_gg(x1, x2) unif_linesC_in_gg(x1, x2) = unif_linesC_in_gg(x1, x2) pD_in_gggggg(x1, x2, x3, x4, x5, x6) = pD_in_gggggg(x1, x2, x3, x4, x5, x6) unif_pairsE_in_g(x1) = unif_pairsE_in_g(x1) unif_pairscG_in_gg(x1, x2) = unif_pairscG_in_gg(x1, x2) U44_gg(x1, x2, x3) = U44_gg(x2, x3) unif_pairscE_in_g(x1) = unif_pairscE_in_g(x1) unif_pairscE_out_g(x1) = unif_pairscE_out_g(x1) U36_g(x1, x2, x3) = U36_g(x2, x3) U37_g(x1, x2) = U37_g(x1, x2) U38_g(x1, x2, x3) = U38_g(x2, x3) U39_g(x1, x2, x3) = U39_g(x2, x3) unif_pairscG_out_gg(x1, x2) = unif_pairscG_out_gg(x1, x2) U45_gg(x1, x2) = U45_gg(x1, x2) U46_gg(x1, x2, x3) = U46_gg(x2, x3) U47_gg(x1, x2, x3) = U47_gg(x2, x3) unif_linescC_in_gg(x1, x2) = unif_linescC_in_gg(x1, x2) U35_gg(x1, x2, x3, x4, x5, x6, x7) = U35_gg(x1, x2, x3, x4, x5, x6, x7) qcD_in_gggggg(x1, x2, x3, x4, x5, x6) = qcD_in_gggggg(x1, x2, x3, x4, x5, x6) U42_gggggg(x1, x2, x3, x4, x5, x6, x7) = U42_gggggg(x1, x2, x3, x4, x5, x6, x7) U43_gggggg(x1, x2, x3, x4, x5, x6, x7) = U43_gggggg(x1, x2, x3, x4, x5, x6, x7) unif_linescC_out_gg(x1, x2) = unif_linescC_out_gg(x1, x2) qcD_out_gggggg(x1, x2, x3, x4, x5, x6) = qcD_out_gggggg(x1, x2, x3, x4, x5, x6) SHAPESH_IN_GA(x1, x2) = SHAPESH_IN_GA(x1) U23_GA(x1, x2, x3, x4) = U23_GA(x1, x2, x4) VARMATA_IN_GA(x1, x2) = VARMATA_IN_GA(x1) U1_GA(x1, x2, x3, x4, x5) = U1_GA(x1, x2, x5) U2_GA(x1, x2, x3, x4, x5) = U2_GA(x1, x2, x5) U3_GA(x1, x2, x3, x4, x5) = U3_GA(x1, x2, x5) U4_GA(x1, x2, x3) = U4_GA(x1, x3) U5_GA(x1, x2, x3, x4) = U5_GA(x1, x4) U24_GA(x1, x2, x3, x4) = U24_GA(x1, x2, x4) U25_GA(x1, x2, x3, x4) = U25_GA(x1, x2, x4) PF_IN_GAG(x1, x2, x3) = PF_IN_GAG(x1, x3) U14_GAG(x1, x2, x3, x4) = U14_GAG(x1, x3, x4) U15_GAG(x1, x2, x3, x4) = U15_GAG(x1, x3, x4) U16_GAG(x1, x2, x3, x4) = U16_GAG(x1, x3, x4) UNIF_MATRXB_IN_GG(x1, x2) = UNIF_MATRXB_IN_GG(x1, x2) U6_GG(x1, x2, x3, x4) = U6_GG(x1, x2, x3, x4) UNIF_LINESC_IN_GG(x1, x2) = UNIF_LINESC_IN_GG(x1, x2) U9_GG(x1, x2, x3, x4, x5, x6, x7) = U9_GG(x1, x2, x3, x4, x5, x6, x7) PD_IN_GGGGGG(x1, x2, x3, x4, x5, x6) = PD_IN_GGGGGG(x1, x2, x3, x4, x5, x6) U17_GGGGGG(x1, x2, x3, x4, x5, x6, x7) = U17_GGGGGG(x2, x3, x4, x5, x6, x7) UNIF_PAIRSE_IN_G(x1) = UNIF_PAIRSE_IN_G(x1) U10_G(x1, x2, x3) = U10_G(x2, x3) U11_G(x1, x2) = U11_G(x1, x2) U12_G(x1, x2, x3) = U12_G(x2, x3) U13_G(x1, x2, x3) = U13_G(x2, x3) U18_GGGGGG(x1, x2, x3, x4, x5, x6) = U18_GGGGGG(x1, x2, x3, x4, x5, x6) U19_GGGGGG(x1, x2, x3, x4, x5, x6, x7) = U19_GGGGGG(x2, x3, x4, x5, x6, x7) U20_GGGGGG(x1, x2, x3, x4, x5, x6, x7) = U20_GGGGGG(x2, x3, x4, x5, x6, x7) U21_GGGGGG(x1, x2, x3, x4, x5, x6, x7) = U21_GGGGGG(x1, x2, x3, x4, x5, x6, x7) U22_GGGGGG(x1, x2, x3, x4, x5, x6, x7) = U22_GGGGGG(x1, x2, x3, x4, x5, x6, x7) U7_GG(x1, x2, x3, x4) = U7_GG(x1, x2, x3, x4) U8_GG(x1, x2, x3, x4) = U8_GG(x1, x2, x3, x4) U26_GA(x1, x2, x3) = U26_GA(x1, x3) U27_GA(x1, x2, x3) = U27_GA(x1, x3) We have to consider all (P,R,Pi)-chains ---------------------------------------- (5) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LOPSTR] contains 4 SCCs with 35 less nodes. ---------------------------------------- (6) Complex Obligation (AND) ---------------------------------------- (7) Obligation: Pi DP problem: The TRS P consists of the following rules: UNIF_PAIRSE_IN_G(.(black, .(black, X1))) -> UNIF_PAIRSE_IN_G(X1) UNIF_PAIRSE_IN_G(.(w(X1), .(w(X1), X2))) -> UNIF_PAIRSE_IN_G(X2) UNIF_PAIRSE_IN_G(.(black, .(w(X1), X2))) -> UNIF_PAIRSE_IN_G(X2) UNIF_PAIRSE_IN_G(.(w(X1), .(black, X2))) -> UNIF_PAIRSE_IN_G(X2) The TRS R consists of the following rules: varmatcA_in_ga([], []) -> varmatcA_out_ga([], []) varmatcA_in_ga(.(X1, X2), .(X3, X4)) -> U29_ga(X1, X2, X3, X4, varmatcA_in_ga(X1, X3)) varmatcA_in_ga(.(black, X1), .(black, X2)) -> U31_ga(X1, X2, varmatcA_in_ga(X1, X2)) varmatcA_in_ga(.(white, X1), .(w(X2), X3)) -> U32_ga(X1, X2, X3, varmatcA_in_ga(X1, X3)) U32_ga(X1, X2, X3, varmatcA_out_ga(X1, X3)) -> varmatcA_out_ga(.(white, X1), .(w(X2), X3)) U31_ga(X1, X2, varmatcA_out_ga(X1, X2)) -> varmatcA_out_ga(.(black, X1), .(black, X2)) U29_ga(X1, X2, X3, X4, varmatcA_out_ga(X1, X3)) -> U30_ga(X1, X2, X3, X4, varmatcA_in_ga(X2, X4)) U30_ga(X1, X2, X3, X4, varmatcA_out_ga(X2, X4)) -> varmatcA_out_ga(.(X1, X2), .(X3, X4)) unif_pairscG_in_gg(w(X1), .(w(X1), X2)) -> U44_gg(X1, X2, unif_pairscE_in_g(X2)) unif_pairscE_in_g([]) -> unif_pairscE_out_g([]) unif_pairscE_in_g(.(w(X1), .(w(X1), X2))) -> U36_g(X1, X2, unif_pairscE_in_g(X2)) unif_pairscE_in_g(.(black, .(black, X1))) -> U37_g(X1, unif_pairscE_in_g(X1)) unif_pairscE_in_g(.(black, .(w(X1), X2))) -> U38_g(X1, X2, unif_pairscE_in_g(X2)) unif_pairscE_in_g(.(w(X1), .(black, X2))) -> U39_g(X1, X2, unif_pairscE_in_g(X2)) U39_g(X1, X2, unif_pairscE_out_g(X2)) -> unif_pairscE_out_g(.(w(X1), .(black, X2))) U38_g(X1, X2, unif_pairscE_out_g(X2)) -> unif_pairscE_out_g(.(black, .(w(X1), X2))) U37_g(X1, unif_pairscE_out_g(X1)) -> unif_pairscE_out_g(.(black, .(black, X1))) U36_g(X1, X2, unif_pairscE_out_g(X2)) -> unif_pairscE_out_g(.(w(X1), .(w(X1), X2))) U44_gg(X1, X2, unif_pairscE_out_g(X2)) -> unif_pairscG_out_gg(w(X1), .(w(X1), X2)) unif_pairscG_in_gg(black, .(black, X1)) -> U45_gg(X1, unif_pairscE_in_g(X1)) U45_gg(X1, unif_pairscE_out_g(X1)) -> unif_pairscG_out_gg(black, .(black, X1)) unif_pairscG_in_gg(black, .(w(X1), X2)) -> U46_gg(X1, X2, unif_pairscE_in_g(X2)) U46_gg(X1, X2, unif_pairscE_out_g(X2)) -> unif_pairscG_out_gg(black, .(w(X1), X2)) unif_pairscG_in_gg(w(X1), .(black, X2)) -> U47_gg(X1, X2, unif_pairscE_in_g(X2)) U47_gg(X1, X2, unif_pairscE_out_g(X2)) -> unif_pairscG_out_gg(w(X1), .(black, X2)) unif_linescC_in_gg(.(X1, .(X2, X3)), .(X4, .(X5, X6))) -> U35_gg(X1, X2, X3, X4, X5, X6, qcD_in_gggggg(X1, .(X2, .(X4, .(X5, .(X1, .(X4, .(X2, .(X5, .(X1, .(X5, .(X2, .(X4, []))))))))))), X2, X3, X5, X6)) qcD_in_gggggg(X1, X2, X3, X4, X5, X6) -> U42_gggggg(X1, X2, X3, X4, X5, X6, unif_pairscG_in_gg(X1, X2)) U42_gggggg(X1, X2, X3, X4, X5, X6, unif_pairscG_out_gg(X1, X2)) -> U43_gggggg(X1, X2, X3, X4, X5, X6, unif_linescC_in_gg(.(X3, X4), .(X5, X6))) unif_linescC_in_gg(.(X1, []), .(X2, [])) -> unif_linescC_out_gg(.(X1, []), .(X2, [])) U43_gggggg(X1, X2, X3, X4, X5, X6, unif_linescC_out_gg(.(X3, X4), .(X5, X6))) -> qcD_out_gggggg(X1, X2, X3, X4, X5, X6) U35_gg(X1, X2, X3, X4, X5, X6, qcD_out_gggggg(X1, .(X2, .(X4, .(X5, .(X1, .(X4, .(X2, .(X5, .(X1, .(X5, .(X2, .(X4, []))))))))))), X2, X3, X5, X6)) -> unif_linescC_out_gg(.(X1, .(X2, X3)), .(X4, .(X5, X6))) The argument filtering Pi contains the following mapping: .(x1, x2) = .(x1, x2) varmatcA_in_ga(x1, x2) = varmatcA_in_ga(x1) [] = [] varmatcA_out_ga(x1, x2) = varmatcA_out_ga(x1, x2) U29_ga(x1, x2, x3, x4, x5) = U29_ga(x1, x2, x5) black = black U31_ga(x1, x2, x3) = U31_ga(x1, x3) white = white U32_ga(x1, x2, x3, x4) = U32_ga(x1, x4) w(x1) = w U30_ga(x1, x2, x3, x4, x5) = U30_ga(x1, x2, x3, x5) unif_pairscG_in_gg(x1, x2) = unif_pairscG_in_gg(x1, x2) U44_gg(x1, x2, x3) = U44_gg(x2, x3) unif_pairscE_in_g(x1) = unif_pairscE_in_g(x1) unif_pairscE_out_g(x1) = unif_pairscE_out_g(x1) U36_g(x1, x2, x3) = U36_g(x2, x3) U37_g(x1, x2) = U37_g(x1, x2) U38_g(x1, x2, x3) = U38_g(x2, x3) U39_g(x1, x2, x3) = U39_g(x2, x3) unif_pairscG_out_gg(x1, x2) = unif_pairscG_out_gg(x1, x2) U45_gg(x1, x2) = U45_gg(x1, x2) U46_gg(x1, x2, x3) = U46_gg(x2, x3) U47_gg(x1, x2, x3) = U47_gg(x2, x3) unif_linescC_in_gg(x1, x2) = unif_linescC_in_gg(x1, x2) U35_gg(x1, x2, x3, x4, x5, x6, x7) = U35_gg(x1, x2, x3, x4, x5, x6, x7) qcD_in_gggggg(x1, x2, x3, x4, x5, x6) = qcD_in_gggggg(x1, x2, x3, x4, x5, x6) U42_gggggg(x1, x2, x3, x4, x5, x6, x7) = U42_gggggg(x1, x2, x3, x4, x5, x6, x7) U43_gggggg(x1, x2, x3, x4, x5, x6, x7) = U43_gggggg(x1, x2, x3, x4, x5, x6, x7) unif_linescC_out_gg(x1, x2) = unif_linescC_out_gg(x1, x2) qcD_out_gggggg(x1, x2, x3, x4, x5, x6) = qcD_out_gggggg(x1, x2, x3, x4, x5, x6) UNIF_PAIRSE_IN_G(x1) = UNIF_PAIRSE_IN_G(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: UNIF_PAIRSE_IN_G(.(black, .(black, X1))) -> UNIF_PAIRSE_IN_G(X1) UNIF_PAIRSE_IN_G(.(w(X1), .(w(X1), X2))) -> UNIF_PAIRSE_IN_G(X2) UNIF_PAIRSE_IN_G(.(black, .(w(X1), X2))) -> UNIF_PAIRSE_IN_G(X2) UNIF_PAIRSE_IN_G(.(w(X1), .(black, X2))) -> UNIF_PAIRSE_IN_G(X2) R is empty. The argument filtering Pi contains the following mapping: .(x1, x2) = .(x1, x2) black = black w(x1) = w UNIF_PAIRSE_IN_G(x1) = UNIF_PAIRSE_IN_G(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: UNIF_PAIRSE_IN_G(.(black, .(black, X1))) -> UNIF_PAIRSE_IN_G(X1) UNIF_PAIRSE_IN_G(.(w, .(w, X2))) -> UNIF_PAIRSE_IN_G(X2) UNIF_PAIRSE_IN_G(.(black, .(w, X2))) -> UNIF_PAIRSE_IN_G(X2) UNIF_PAIRSE_IN_G(.(w, .(black, X2))) -> UNIF_PAIRSE_IN_G(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: *UNIF_PAIRSE_IN_G(.(black, .(black, X1))) -> UNIF_PAIRSE_IN_G(X1) The graph contains the following edges 1 > 1 *UNIF_PAIRSE_IN_G(.(w, .(w, X2))) -> UNIF_PAIRSE_IN_G(X2) The graph contains the following edges 1 > 1 *UNIF_PAIRSE_IN_G(.(black, .(w, X2))) -> UNIF_PAIRSE_IN_G(X2) The graph contains the following edges 1 > 1 *UNIF_PAIRSE_IN_G(.(w, .(black, X2))) -> UNIF_PAIRSE_IN_G(X2) The graph contains the following edges 1 > 1 ---------------------------------------- (13) YES ---------------------------------------- (14) Obligation: Pi DP problem: The TRS P consists of the following rules: UNIF_LINESC_IN_GG(.(X1, .(X2, X3)), .(X4, .(X5, X6))) -> PD_IN_GGGGGG(X1, .(X2, .(X4, .(X5, .(X1, .(X4, .(X2, .(X5, .(X1, .(X5, .(X2, .(X4, []))))))))))), X2, X3, X5, X6) PD_IN_GGGGGG(X1, X2, X3, X4, X5, X6) -> U21_GGGGGG(X1, X2, X3, X4, X5, X6, unif_pairscG_in_gg(X1, X2)) U21_GGGGGG(X1, X2, X3, X4, X5, X6, unif_pairscG_out_gg(X1, X2)) -> UNIF_LINESC_IN_GG(.(X3, X4), .(X5, X6)) The TRS R consists of the following rules: varmatcA_in_ga([], []) -> varmatcA_out_ga([], []) varmatcA_in_ga(.(X1, X2), .(X3, X4)) -> U29_ga(X1, X2, X3, X4, varmatcA_in_ga(X1, X3)) varmatcA_in_ga(.(black, X1), .(black, X2)) -> U31_ga(X1, X2, varmatcA_in_ga(X1, X2)) varmatcA_in_ga(.(white, X1), .(w(X2), X3)) -> U32_ga(X1, X2, X3, varmatcA_in_ga(X1, X3)) U32_ga(X1, X2, X3, varmatcA_out_ga(X1, X3)) -> varmatcA_out_ga(.(white, X1), .(w(X2), X3)) U31_ga(X1, X2, varmatcA_out_ga(X1, X2)) -> varmatcA_out_ga(.(black, X1), .(black, X2)) U29_ga(X1, X2, X3, X4, varmatcA_out_ga(X1, X3)) -> U30_ga(X1, X2, X3, X4, varmatcA_in_ga(X2, X4)) U30_ga(X1, X2, X3, X4, varmatcA_out_ga(X2, X4)) -> varmatcA_out_ga(.(X1, X2), .(X3, X4)) unif_pairscG_in_gg(w(X1), .(w(X1), X2)) -> U44_gg(X1, X2, unif_pairscE_in_g(X2)) unif_pairscE_in_g([]) -> unif_pairscE_out_g([]) unif_pairscE_in_g(.(w(X1), .(w(X1), X2))) -> U36_g(X1, X2, unif_pairscE_in_g(X2)) unif_pairscE_in_g(.(black, .(black, X1))) -> U37_g(X1, unif_pairscE_in_g(X1)) unif_pairscE_in_g(.(black, .(w(X1), X2))) -> U38_g(X1, X2, unif_pairscE_in_g(X2)) unif_pairscE_in_g(.(w(X1), .(black, X2))) -> U39_g(X1, X2, unif_pairscE_in_g(X2)) U39_g(X1, X2, unif_pairscE_out_g(X2)) -> unif_pairscE_out_g(.(w(X1), .(black, X2))) U38_g(X1, X2, unif_pairscE_out_g(X2)) -> unif_pairscE_out_g(.(black, .(w(X1), X2))) U37_g(X1, unif_pairscE_out_g(X1)) -> unif_pairscE_out_g(.(black, .(black, X1))) U36_g(X1, X2, unif_pairscE_out_g(X2)) -> unif_pairscE_out_g(.(w(X1), .(w(X1), X2))) U44_gg(X1, X2, unif_pairscE_out_g(X2)) -> unif_pairscG_out_gg(w(X1), .(w(X1), X2)) unif_pairscG_in_gg(black, .(black, X1)) -> U45_gg(X1, unif_pairscE_in_g(X1)) U45_gg(X1, unif_pairscE_out_g(X1)) -> unif_pairscG_out_gg(black, .(black, X1)) unif_pairscG_in_gg(black, .(w(X1), X2)) -> U46_gg(X1, X2, unif_pairscE_in_g(X2)) U46_gg(X1, X2, unif_pairscE_out_g(X2)) -> unif_pairscG_out_gg(black, .(w(X1), X2)) unif_pairscG_in_gg(w(X1), .(black, X2)) -> U47_gg(X1, X2, unif_pairscE_in_g(X2)) U47_gg(X1, X2, unif_pairscE_out_g(X2)) -> unif_pairscG_out_gg(w(X1), .(black, X2)) unif_linescC_in_gg(.(X1, .(X2, X3)), .(X4, .(X5, X6))) -> U35_gg(X1, X2, X3, X4, X5, X6, qcD_in_gggggg(X1, .(X2, .(X4, .(X5, .(X1, .(X4, .(X2, .(X5, .(X1, .(X5, .(X2, .(X4, []))))))))))), X2, X3, X5, X6)) qcD_in_gggggg(X1, X2, X3, X4, X5, X6) -> U42_gggggg(X1, X2, X3, X4, X5, X6, unif_pairscG_in_gg(X1, X2)) U42_gggggg(X1, X2, X3, X4, X5, X6, unif_pairscG_out_gg(X1, X2)) -> U43_gggggg(X1, X2, X3, X4, X5, X6, unif_linescC_in_gg(.(X3, X4), .(X5, X6))) unif_linescC_in_gg(.(X1, []), .(X2, [])) -> unif_linescC_out_gg(.(X1, []), .(X2, [])) U43_gggggg(X1, X2, X3, X4, X5, X6, unif_linescC_out_gg(.(X3, X4), .(X5, X6))) -> qcD_out_gggggg(X1, X2, X3, X4, X5, X6) U35_gg(X1, X2, X3, X4, X5, X6, qcD_out_gggggg(X1, .(X2, .(X4, .(X5, .(X1, .(X4, .(X2, .(X5, .(X1, .(X5, .(X2, .(X4, []))))))))))), X2, X3, X5, X6)) -> unif_linescC_out_gg(.(X1, .(X2, X3)), .(X4, .(X5, X6))) The argument filtering Pi contains the following mapping: .(x1, x2) = .(x1, x2) varmatcA_in_ga(x1, x2) = varmatcA_in_ga(x1) [] = [] varmatcA_out_ga(x1, x2) = varmatcA_out_ga(x1, x2) U29_ga(x1, x2, x3, x4, x5) = U29_ga(x1, x2, x5) black = black U31_ga(x1, x2, x3) = U31_ga(x1, x3) white = white U32_ga(x1, x2, x3, x4) = U32_ga(x1, x4) w(x1) = w U30_ga(x1, x2, x3, x4, x5) = U30_ga(x1, x2, x3, x5) unif_pairscG_in_gg(x1, x2) = unif_pairscG_in_gg(x1, x2) U44_gg(x1, x2, x3) = U44_gg(x2, x3) unif_pairscE_in_g(x1) = unif_pairscE_in_g(x1) unif_pairscE_out_g(x1) = unif_pairscE_out_g(x1) U36_g(x1, x2, x3) = U36_g(x2, x3) U37_g(x1, x2) = U37_g(x1, x2) U38_g(x1, x2, x3) = U38_g(x2, x3) U39_g(x1, x2, x3) = U39_g(x2, x3) unif_pairscG_out_gg(x1, x2) = unif_pairscG_out_gg(x1, x2) U45_gg(x1, x2) = U45_gg(x1, x2) U46_gg(x1, x2, x3) = U46_gg(x2, x3) U47_gg(x1, x2, x3) = U47_gg(x2, x3) unif_linescC_in_gg(x1, x2) = unif_linescC_in_gg(x1, x2) U35_gg(x1, x2, x3, x4, x5, x6, x7) = U35_gg(x1, x2, x3, x4, x5, x6, x7) qcD_in_gggggg(x1, x2, x3, x4, x5, x6) = qcD_in_gggggg(x1, x2, x3, x4, x5, x6) U42_gggggg(x1, x2, x3, x4, x5, x6, x7) = U42_gggggg(x1, x2, x3, x4, x5, x6, x7) U43_gggggg(x1, x2, x3, x4, x5, x6, x7) = U43_gggggg(x1, x2, x3, x4, x5, x6, x7) unif_linescC_out_gg(x1, x2) = unif_linescC_out_gg(x1, x2) qcD_out_gggggg(x1, x2, x3, x4, x5, x6) = qcD_out_gggggg(x1, x2, x3, x4, x5, x6) UNIF_LINESC_IN_GG(x1, x2) = UNIF_LINESC_IN_GG(x1, x2) PD_IN_GGGGGG(x1, x2, x3, x4, x5, x6) = PD_IN_GGGGGG(x1, x2, x3, x4, x5, x6) U21_GGGGGG(x1, x2, x3, x4, x5, x6, x7) = U21_GGGGGG(x1, x2, x3, x4, x5, x6, x7) 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: UNIF_LINESC_IN_GG(.(X1, .(X2, X3)), .(X4, .(X5, X6))) -> PD_IN_GGGGGG(X1, .(X2, .(X4, .(X5, .(X1, .(X4, .(X2, .(X5, .(X1, .(X5, .(X2, .(X4, []))))))))))), X2, X3, X5, X6) PD_IN_GGGGGG(X1, X2, X3, X4, X5, X6) -> U21_GGGGGG(X1, X2, X3, X4, X5, X6, unif_pairscG_in_gg(X1, X2)) U21_GGGGGG(X1, X2, X3, X4, X5, X6, unif_pairscG_out_gg(X1, X2)) -> UNIF_LINESC_IN_GG(.(X3, X4), .(X5, X6)) The TRS R consists of the following rules: unif_pairscG_in_gg(w(X1), .(w(X1), X2)) -> U44_gg(X1, X2, unif_pairscE_in_g(X2)) unif_pairscG_in_gg(black, .(black, X1)) -> U45_gg(X1, unif_pairscE_in_g(X1)) unif_pairscG_in_gg(black, .(w(X1), X2)) -> U46_gg(X1, X2, unif_pairscE_in_g(X2)) unif_pairscG_in_gg(w(X1), .(black, X2)) -> U47_gg(X1, X2, unif_pairscE_in_g(X2)) U44_gg(X1, X2, unif_pairscE_out_g(X2)) -> unif_pairscG_out_gg(w(X1), .(w(X1), X2)) U45_gg(X1, unif_pairscE_out_g(X1)) -> unif_pairscG_out_gg(black, .(black, X1)) U46_gg(X1, X2, unif_pairscE_out_g(X2)) -> unif_pairscG_out_gg(black, .(w(X1), X2)) U47_gg(X1, X2, unif_pairscE_out_g(X2)) -> unif_pairscG_out_gg(w(X1), .(black, X2)) unif_pairscE_in_g([]) -> unif_pairscE_out_g([]) unif_pairscE_in_g(.(w(X1), .(w(X1), X2))) -> U36_g(X1, X2, unif_pairscE_in_g(X2)) unif_pairscE_in_g(.(black, .(black, X1))) -> U37_g(X1, unif_pairscE_in_g(X1)) unif_pairscE_in_g(.(black, .(w(X1), X2))) -> U38_g(X1, X2, unif_pairscE_in_g(X2)) unif_pairscE_in_g(.(w(X1), .(black, X2))) -> U39_g(X1, X2, unif_pairscE_in_g(X2)) U36_g(X1, X2, unif_pairscE_out_g(X2)) -> unif_pairscE_out_g(.(w(X1), .(w(X1), X2))) U37_g(X1, unif_pairscE_out_g(X1)) -> unif_pairscE_out_g(.(black, .(black, X1))) U38_g(X1, X2, unif_pairscE_out_g(X2)) -> unif_pairscE_out_g(.(black, .(w(X1), X2))) U39_g(X1, X2, unif_pairscE_out_g(X2)) -> unif_pairscE_out_g(.(w(X1), .(black, X2))) The argument filtering Pi contains the following mapping: .(x1, x2) = .(x1, x2) [] = [] black = black w(x1) = w unif_pairscG_in_gg(x1, x2) = unif_pairscG_in_gg(x1, x2) U44_gg(x1, x2, x3) = U44_gg(x2, x3) unif_pairscE_in_g(x1) = unif_pairscE_in_g(x1) unif_pairscE_out_g(x1) = unif_pairscE_out_g(x1) U36_g(x1, x2, x3) = U36_g(x2, x3) U37_g(x1, x2) = U37_g(x1, x2) U38_g(x1, x2, x3) = U38_g(x2, x3) U39_g(x1, x2, x3) = U39_g(x2, x3) unif_pairscG_out_gg(x1, x2) = unif_pairscG_out_gg(x1, x2) U45_gg(x1, x2) = U45_gg(x1, x2) U46_gg(x1, x2, x3) = U46_gg(x2, x3) U47_gg(x1, x2, x3) = U47_gg(x2, x3) UNIF_LINESC_IN_GG(x1, x2) = UNIF_LINESC_IN_GG(x1, x2) PD_IN_GGGGGG(x1, x2, x3, x4, x5, x6) = PD_IN_GGGGGG(x1, x2, x3, x4, x5, x6) U21_GGGGGG(x1, x2, x3, x4, x5, x6, x7) = U21_GGGGGG(x1, x2, x3, x4, x5, x6, x7) 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: UNIF_LINESC_IN_GG(.(X1, .(X2, X3)), .(X4, .(X5, X6))) -> PD_IN_GGGGGG(X1, .(X2, .(X4, .(X5, .(X1, .(X4, .(X2, .(X5, .(X1, .(X5, .(X2, .(X4, []))))))))))), X2, X3, X5, X6) PD_IN_GGGGGG(X1, X2, X3, X4, X5, X6) -> U21_GGGGGG(X1, X2, X3, X4, X5, X6, unif_pairscG_in_gg(X1, X2)) U21_GGGGGG(X1, X2, X3, X4, X5, X6, unif_pairscG_out_gg(X1, X2)) -> UNIF_LINESC_IN_GG(.(X3, X4), .(X5, X6)) The TRS R consists of the following rules: unif_pairscG_in_gg(w, .(w, X2)) -> U44_gg(X2, unif_pairscE_in_g(X2)) unif_pairscG_in_gg(black, .(black, X1)) -> U45_gg(X1, unif_pairscE_in_g(X1)) unif_pairscG_in_gg(black, .(w, X2)) -> U46_gg(X2, unif_pairscE_in_g(X2)) unif_pairscG_in_gg(w, .(black, X2)) -> U47_gg(X2, unif_pairscE_in_g(X2)) U44_gg(X2, unif_pairscE_out_g(X2)) -> unif_pairscG_out_gg(w, .(w, X2)) U45_gg(X1, unif_pairscE_out_g(X1)) -> unif_pairscG_out_gg(black, .(black, X1)) U46_gg(X2, unif_pairscE_out_g(X2)) -> unif_pairscG_out_gg(black, .(w, X2)) U47_gg(X2, unif_pairscE_out_g(X2)) -> unif_pairscG_out_gg(w, .(black, X2)) unif_pairscE_in_g([]) -> unif_pairscE_out_g([]) unif_pairscE_in_g(.(w, .(w, X2))) -> U36_g(X2, unif_pairscE_in_g(X2)) unif_pairscE_in_g(.(black, .(black, X1))) -> U37_g(X1, unif_pairscE_in_g(X1)) unif_pairscE_in_g(.(black, .(w, X2))) -> U38_g(X2, unif_pairscE_in_g(X2)) unif_pairscE_in_g(.(w, .(black, X2))) -> U39_g(X2, unif_pairscE_in_g(X2)) U36_g(X2, unif_pairscE_out_g(X2)) -> unif_pairscE_out_g(.(w, .(w, X2))) U37_g(X1, unif_pairscE_out_g(X1)) -> unif_pairscE_out_g(.(black, .(black, X1))) U38_g(X2, unif_pairscE_out_g(X2)) -> unif_pairscE_out_g(.(black, .(w, X2))) U39_g(X2, unif_pairscE_out_g(X2)) -> unif_pairscE_out_g(.(w, .(black, X2))) The set Q consists of the following terms: unif_pairscG_in_gg(x0, x1) U44_gg(x0, x1) U45_gg(x0, x1) U46_gg(x0, x1) U47_gg(x0, x1) unif_pairscE_in_g(x0) U36_g(x0, x1) U37_g(x0, x1) U38_g(x0, x1) U39_g(x0, x1) We have to consider all (P,Q,R)-chains. ---------------------------------------- (19) QDPQMonotonicMRRProof (EQUIVALENT) By using the Q-monotonic rule removal processor with the following ordering, at least one Dependency Pair or term rewrite system rule of this QDP problem can be strictly oriented such that it always occurs at a strongly monotonic position in a (P,Q,R)-chain. Strictly oriented dependency pairs: UNIF_LINESC_IN_GG(.(X1, .(X2, X3)), .(X4, .(X5, X6))) -> PD_IN_GGGGGG(X1, .(X2, .(X4, .(X5, .(X1, .(X4, .(X2, .(X5, .(X1, .(X5, .(X2, .(X4, []))))))))))), X2, X3, X5, X6) Used ordering: Polynomial interpretation [POLO]: POL(.(x_1, x_2)) = 1 + 2*x_1 + 2*x_2 POL(PD_IN_GGGGGG(x_1, x_2, x_3, x_4, x_5, x_6)) = 1 + 2*x_5 + 2*x_6 POL(U21_GGGGGG(x_1, x_2, x_3, x_4, x_5, x_6, x_7)) = 1 + 2*x_5 + 2*x_6 POL(U36_g(x_1, x_2)) = 0 POL(U37_g(x_1, x_2)) = 0 POL(U38_g(x_1, x_2)) = 0 POL(U39_g(x_1, x_2)) = 0 POL(U44_gg(x_1, x_2)) = 0 POL(U45_gg(x_1, x_2)) = 1 POL(U46_gg(x_1, x_2)) = 0 POL(U47_gg(x_1, x_2)) = 2 POL(UNIF_LINESC_IN_GG(x_1, x_2)) = x_2 POL([]) = 0 POL(black) = 2 POL(unif_pairscE_in_g(x_1)) = 0 POL(unif_pairscE_out_g(x_1)) = 0 POL(unif_pairscG_in_gg(x_1, x_2)) = x_2 POL(unif_pairscG_out_gg(x_1, x_2)) = 0 POL(w) = 0 ---------------------------------------- (20) Obligation: Q DP problem: The TRS P consists of the following rules: PD_IN_GGGGGG(X1, X2, X3, X4, X5, X6) -> U21_GGGGGG(X1, X2, X3, X4, X5, X6, unif_pairscG_in_gg(X1, X2)) U21_GGGGGG(X1, X2, X3, X4, X5, X6, unif_pairscG_out_gg(X1, X2)) -> UNIF_LINESC_IN_GG(.(X3, X4), .(X5, X6)) The TRS R consists of the following rules: unif_pairscG_in_gg(w, .(w, X2)) -> U44_gg(X2, unif_pairscE_in_g(X2)) unif_pairscG_in_gg(black, .(black, X1)) -> U45_gg(X1, unif_pairscE_in_g(X1)) unif_pairscG_in_gg(black, .(w, X2)) -> U46_gg(X2, unif_pairscE_in_g(X2)) unif_pairscG_in_gg(w, .(black, X2)) -> U47_gg(X2, unif_pairscE_in_g(X2)) U44_gg(X2, unif_pairscE_out_g(X2)) -> unif_pairscG_out_gg(w, .(w, X2)) U45_gg(X1, unif_pairscE_out_g(X1)) -> unif_pairscG_out_gg(black, .(black, X1)) U46_gg(X2, unif_pairscE_out_g(X2)) -> unif_pairscG_out_gg(black, .(w, X2)) U47_gg(X2, unif_pairscE_out_g(X2)) -> unif_pairscG_out_gg(w, .(black, X2)) unif_pairscE_in_g([]) -> unif_pairscE_out_g([]) unif_pairscE_in_g(.(w, .(w, X2))) -> U36_g(X2, unif_pairscE_in_g(X2)) unif_pairscE_in_g(.(black, .(black, X1))) -> U37_g(X1, unif_pairscE_in_g(X1)) unif_pairscE_in_g(.(black, .(w, X2))) -> U38_g(X2, unif_pairscE_in_g(X2)) unif_pairscE_in_g(.(w, .(black, X2))) -> U39_g(X2, unif_pairscE_in_g(X2)) U36_g(X2, unif_pairscE_out_g(X2)) -> unif_pairscE_out_g(.(w, .(w, X2))) U37_g(X1, unif_pairscE_out_g(X1)) -> unif_pairscE_out_g(.(black, .(black, X1))) U38_g(X2, unif_pairscE_out_g(X2)) -> unif_pairscE_out_g(.(black, .(w, X2))) U39_g(X2, unif_pairscE_out_g(X2)) -> unif_pairscE_out_g(.(w, .(black, X2))) The set Q consists of the following terms: unif_pairscG_in_gg(x0, x1) U44_gg(x0, x1) U45_gg(x0, x1) U46_gg(x0, x1) U47_gg(x0, x1) unif_pairscE_in_g(x0) U36_g(x0, x1) U37_g(x0, x1) U38_g(x0, x1) U39_g(x0, x1) We have to consider all (P,Q,R)-chains. ---------------------------------------- (21) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 0 SCCs with 2 less nodes. ---------------------------------------- (22) TRUE ---------------------------------------- (23) Obligation: Pi DP problem: The TRS P consists of the following rules: UNIF_MATRXB_IN_GG(X1, .(X2, X3)) -> U7_GG(X1, X2, X3, unif_linescC_in_gg(X1, X2)) U7_GG(X1, X2, X3, unif_linescC_out_gg(X1, X2)) -> UNIF_MATRXB_IN_GG(X2, X3) The TRS R consists of the following rules: varmatcA_in_ga([], []) -> varmatcA_out_ga([], []) varmatcA_in_ga(.(X1, X2), .(X3, X4)) -> U29_ga(X1, X2, X3, X4, varmatcA_in_ga(X1, X3)) varmatcA_in_ga(.(black, X1), .(black, X2)) -> U31_ga(X1, X2, varmatcA_in_ga(X1, X2)) varmatcA_in_ga(.(white, X1), .(w(X2), X3)) -> U32_ga(X1, X2, X3, varmatcA_in_ga(X1, X3)) U32_ga(X1, X2, X3, varmatcA_out_ga(X1, X3)) -> varmatcA_out_ga(.(white, X1), .(w(X2), X3)) U31_ga(X1, X2, varmatcA_out_ga(X1, X2)) -> varmatcA_out_ga(.(black, X1), .(black, X2)) U29_ga(X1, X2, X3, X4, varmatcA_out_ga(X1, X3)) -> U30_ga(X1, X2, X3, X4, varmatcA_in_ga(X2, X4)) U30_ga(X1, X2, X3, X4, varmatcA_out_ga(X2, X4)) -> varmatcA_out_ga(.(X1, X2), .(X3, X4)) unif_pairscG_in_gg(w(X1), .(w(X1), X2)) -> U44_gg(X1, X2, unif_pairscE_in_g(X2)) unif_pairscE_in_g([]) -> unif_pairscE_out_g([]) unif_pairscE_in_g(.(w(X1), .(w(X1), X2))) -> U36_g(X1, X2, unif_pairscE_in_g(X2)) unif_pairscE_in_g(.(black, .(black, X1))) -> U37_g(X1, unif_pairscE_in_g(X1)) unif_pairscE_in_g(.(black, .(w(X1), X2))) -> U38_g(X1, X2, unif_pairscE_in_g(X2)) unif_pairscE_in_g(.(w(X1), .(black, X2))) -> U39_g(X1, X2, unif_pairscE_in_g(X2)) U39_g(X1, X2, unif_pairscE_out_g(X2)) -> unif_pairscE_out_g(.(w(X1), .(black, X2))) U38_g(X1, X2, unif_pairscE_out_g(X2)) -> unif_pairscE_out_g(.(black, .(w(X1), X2))) U37_g(X1, unif_pairscE_out_g(X1)) -> unif_pairscE_out_g(.(black, .(black, X1))) U36_g(X1, X2, unif_pairscE_out_g(X2)) -> unif_pairscE_out_g(.(w(X1), .(w(X1), X2))) U44_gg(X1, X2, unif_pairscE_out_g(X2)) -> unif_pairscG_out_gg(w(X1), .(w(X1), X2)) unif_pairscG_in_gg(black, .(black, X1)) -> U45_gg(X1, unif_pairscE_in_g(X1)) U45_gg(X1, unif_pairscE_out_g(X1)) -> unif_pairscG_out_gg(black, .(black, X1)) unif_pairscG_in_gg(black, .(w(X1), X2)) -> U46_gg(X1, X2, unif_pairscE_in_g(X2)) U46_gg(X1, X2, unif_pairscE_out_g(X2)) -> unif_pairscG_out_gg(black, .(w(X1), X2)) unif_pairscG_in_gg(w(X1), .(black, X2)) -> U47_gg(X1, X2, unif_pairscE_in_g(X2)) U47_gg(X1, X2, unif_pairscE_out_g(X2)) -> unif_pairscG_out_gg(w(X1), .(black, X2)) unif_linescC_in_gg(.(X1, .(X2, X3)), .(X4, .(X5, X6))) -> U35_gg(X1, X2, X3, X4, X5, X6, qcD_in_gggggg(X1, .(X2, .(X4, .(X5, .(X1, .(X4, .(X2, .(X5, .(X1, .(X5, .(X2, .(X4, []))))))))))), X2, X3, X5, X6)) qcD_in_gggggg(X1, X2, X3, X4, X5, X6) -> U42_gggggg(X1, X2, X3, X4, X5, X6, unif_pairscG_in_gg(X1, X2)) U42_gggggg(X1, X2, X3, X4, X5, X6, unif_pairscG_out_gg(X1, X2)) -> U43_gggggg(X1, X2, X3, X4, X5, X6, unif_linescC_in_gg(.(X3, X4), .(X5, X6))) unif_linescC_in_gg(.(X1, []), .(X2, [])) -> unif_linescC_out_gg(.(X1, []), .(X2, [])) U43_gggggg(X1, X2, X3, X4, X5, X6, unif_linescC_out_gg(.(X3, X4), .(X5, X6))) -> qcD_out_gggggg(X1, X2, X3, X4, X5, X6) U35_gg(X1, X2, X3, X4, X5, X6, qcD_out_gggggg(X1, .(X2, .(X4, .(X5, .(X1, .(X4, .(X2, .(X5, .(X1, .(X5, .(X2, .(X4, []))))))))))), X2, X3, X5, X6)) -> unif_linescC_out_gg(.(X1, .(X2, X3)), .(X4, .(X5, X6))) The argument filtering Pi contains the following mapping: .(x1, x2) = .(x1, x2) varmatcA_in_ga(x1, x2) = varmatcA_in_ga(x1) [] = [] varmatcA_out_ga(x1, x2) = varmatcA_out_ga(x1, x2) U29_ga(x1, x2, x3, x4, x5) = U29_ga(x1, x2, x5) black = black U31_ga(x1, x2, x3) = U31_ga(x1, x3) white = white U32_ga(x1, x2, x3, x4) = U32_ga(x1, x4) w(x1) = w U30_ga(x1, x2, x3, x4, x5) = U30_ga(x1, x2, x3, x5) unif_pairscG_in_gg(x1, x2) = unif_pairscG_in_gg(x1, x2) U44_gg(x1, x2, x3) = U44_gg(x2, x3) unif_pairscE_in_g(x1) = unif_pairscE_in_g(x1) unif_pairscE_out_g(x1) = unif_pairscE_out_g(x1) U36_g(x1, x2, x3) = U36_g(x2, x3) U37_g(x1, x2) = U37_g(x1, x2) U38_g(x1, x2, x3) = U38_g(x2, x3) U39_g(x1, x2, x3) = U39_g(x2, x3) unif_pairscG_out_gg(x1, x2) = unif_pairscG_out_gg(x1, x2) U45_gg(x1, x2) = U45_gg(x1, x2) U46_gg(x1, x2, x3) = U46_gg(x2, x3) U47_gg(x1, x2, x3) = U47_gg(x2, x3) unif_linescC_in_gg(x1, x2) = unif_linescC_in_gg(x1, x2) U35_gg(x1, x2, x3, x4, x5, x6, x7) = U35_gg(x1, x2, x3, x4, x5, x6, x7) qcD_in_gggggg(x1, x2, x3, x4, x5, x6) = qcD_in_gggggg(x1, x2, x3, x4, x5, x6) U42_gggggg(x1, x2, x3, x4, x5, x6, x7) = U42_gggggg(x1, x2, x3, x4, x5, x6, x7) U43_gggggg(x1, x2, x3, x4, x5, x6, x7) = U43_gggggg(x1, x2, x3, x4, x5, x6, x7) unif_linescC_out_gg(x1, x2) = unif_linescC_out_gg(x1, x2) qcD_out_gggggg(x1, x2, x3, x4, x5, x6) = qcD_out_gggggg(x1, x2, x3, x4, x5, x6) UNIF_MATRXB_IN_GG(x1, x2) = UNIF_MATRXB_IN_GG(x1, x2) U7_GG(x1, x2, x3, x4) = U7_GG(x1, x2, x3, x4) We have to consider all (P,R,Pi)-chains ---------------------------------------- (24) UsableRulesProof (EQUIVALENT) For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. ---------------------------------------- (25) Obligation: Pi DP problem: The TRS P consists of the following rules: UNIF_MATRXB_IN_GG(X1, .(X2, X3)) -> U7_GG(X1, X2, X3, unif_linescC_in_gg(X1, X2)) U7_GG(X1, X2, X3, unif_linescC_out_gg(X1, X2)) -> UNIF_MATRXB_IN_GG(X2, X3) The TRS R consists of the following rules: unif_linescC_in_gg(.(X1, .(X2, X3)), .(X4, .(X5, X6))) -> U35_gg(X1, X2, X3, X4, X5, X6, qcD_in_gggggg(X1, .(X2, .(X4, .(X5, .(X1, .(X4, .(X2, .(X5, .(X1, .(X5, .(X2, .(X4, []))))))))))), X2, X3, X5, X6)) unif_linescC_in_gg(.(X1, []), .(X2, [])) -> unif_linescC_out_gg(.(X1, []), .(X2, [])) U35_gg(X1, X2, X3, X4, X5, X6, qcD_out_gggggg(X1, .(X2, .(X4, .(X5, .(X1, .(X4, .(X2, .(X5, .(X1, .(X5, .(X2, .(X4, []))))))))))), X2, X3, X5, X6)) -> unif_linescC_out_gg(.(X1, .(X2, X3)), .(X4, .(X5, X6))) qcD_in_gggggg(X1, X2, X3, X4, X5, X6) -> U42_gggggg(X1, X2, X3, X4, X5, X6, unif_pairscG_in_gg(X1, X2)) U42_gggggg(X1, X2, X3, X4, X5, X6, unif_pairscG_out_gg(X1, X2)) -> U43_gggggg(X1, X2, X3, X4, X5, X6, unif_linescC_in_gg(.(X3, X4), .(X5, X6))) unif_pairscG_in_gg(w(X1), .(w(X1), X2)) -> U44_gg(X1, X2, unif_pairscE_in_g(X2)) unif_pairscG_in_gg(black, .(black, X1)) -> U45_gg(X1, unif_pairscE_in_g(X1)) unif_pairscG_in_gg(black, .(w(X1), X2)) -> U46_gg(X1, X2, unif_pairscE_in_g(X2)) unif_pairscG_in_gg(w(X1), .(black, X2)) -> U47_gg(X1, X2, unif_pairscE_in_g(X2)) U43_gggggg(X1, X2, X3, X4, X5, X6, unif_linescC_out_gg(.(X3, X4), .(X5, X6))) -> qcD_out_gggggg(X1, X2, X3, X4, X5, X6) U44_gg(X1, X2, unif_pairscE_out_g(X2)) -> unif_pairscG_out_gg(w(X1), .(w(X1), X2)) U45_gg(X1, unif_pairscE_out_g(X1)) -> unif_pairscG_out_gg(black, .(black, X1)) U46_gg(X1, X2, unif_pairscE_out_g(X2)) -> unif_pairscG_out_gg(black, .(w(X1), X2)) U47_gg(X1, X2, unif_pairscE_out_g(X2)) -> unif_pairscG_out_gg(w(X1), .(black, X2)) unif_pairscE_in_g([]) -> unif_pairscE_out_g([]) unif_pairscE_in_g(.(w(X1), .(w(X1), X2))) -> U36_g(X1, X2, unif_pairscE_in_g(X2)) unif_pairscE_in_g(.(black, .(black, X1))) -> U37_g(X1, unif_pairscE_in_g(X1)) unif_pairscE_in_g(.(black, .(w(X1), X2))) -> U38_g(X1, X2, unif_pairscE_in_g(X2)) unif_pairscE_in_g(.(w(X1), .(black, X2))) -> U39_g(X1, X2, unif_pairscE_in_g(X2)) U36_g(X1, X2, unif_pairscE_out_g(X2)) -> unif_pairscE_out_g(.(w(X1), .(w(X1), X2))) U37_g(X1, unif_pairscE_out_g(X1)) -> unif_pairscE_out_g(.(black, .(black, X1))) U38_g(X1, X2, unif_pairscE_out_g(X2)) -> unif_pairscE_out_g(.(black, .(w(X1), X2))) U39_g(X1, X2, unif_pairscE_out_g(X2)) -> unif_pairscE_out_g(.(w(X1), .(black, X2))) The argument filtering Pi contains the following mapping: .(x1, x2) = .(x1, x2) [] = [] black = black w(x1) = w unif_pairscG_in_gg(x1, x2) = unif_pairscG_in_gg(x1, x2) U44_gg(x1, x2, x3) = U44_gg(x2, x3) unif_pairscE_in_g(x1) = unif_pairscE_in_g(x1) unif_pairscE_out_g(x1) = unif_pairscE_out_g(x1) U36_g(x1, x2, x3) = U36_g(x2, x3) U37_g(x1, x2) = U37_g(x1, x2) U38_g(x1, x2, x3) = U38_g(x2, x3) U39_g(x1, x2, x3) = U39_g(x2, x3) unif_pairscG_out_gg(x1, x2) = unif_pairscG_out_gg(x1, x2) U45_gg(x1, x2) = U45_gg(x1, x2) U46_gg(x1, x2, x3) = U46_gg(x2, x3) U47_gg(x1, x2, x3) = U47_gg(x2, x3) unif_linescC_in_gg(x1, x2) = unif_linescC_in_gg(x1, x2) U35_gg(x1, x2, x3, x4, x5, x6, x7) = U35_gg(x1, x2, x3, x4, x5, x6, x7) qcD_in_gggggg(x1, x2, x3, x4, x5, x6) = qcD_in_gggggg(x1, x2, x3, x4, x5, x6) U42_gggggg(x1, x2, x3, x4, x5, x6, x7) = U42_gggggg(x1, x2, x3, x4, x5, x6, x7) U43_gggggg(x1, x2, x3, x4, x5, x6, x7) = U43_gggggg(x1, x2, x3, x4, x5, x6, x7) unif_linescC_out_gg(x1, x2) = unif_linescC_out_gg(x1, x2) qcD_out_gggggg(x1, x2, x3, x4, x5, x6) = qcD_out_gggggg(x1, x2, x3, x4, x5, x6) UNIF_MATRXB_IN_GG(x1, x2) = UNIF_MATRXB_IN_GG(x1, x2) U7_GG(x1, x2, x3, x4) = U7_GG(x1, x2, x3, x4) We have to consider all (P,R,Pi)-chains ---------------------------------------- (26) PiDPToQDPProof (SOUND) Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. ---------------------------------------- (27) Obligation: Q DP problem: The TRS P consists of the following rules: UNIF_MATRXB_IN_GG(X1, .(X2, X3)) -> U7_GG(X1, X2, X3, unif_linescC_in_gg(X1, X2)) U7_GG(X1, X2, X3, unif_linescC_out_gg(X1, X2)) -> UNIF_MATRXB_IN_GG(X2, X3) The TRS R consists of the following rules: unif_linescC_in_gg(.(X1, .(X2, X3)), .(X4, .(X5, X6))) -> U35_gg(X1, X2, X3, X4, X5, X6, qcD_in_gggggg(X1, .(X2, .(X4, .(X5, .(X1, .(X4, .(X2, .(X5, .(X1, .(X5, .(X2, .(X4, []))))))))))), X2, X3, X5, X6)) unif_linescC_in_gg(.(X1, []), .(X2, [])) -> unif_linescC_out_gg(.(X1, []), .(X2, [])) U35_gg(X1, X2, X3, X4, X5, X6, qcD_out_gggggg(X1, .(X2, .(X4, .(X5, .(X1, .(X4, .(X2, .(X5, .(X1, .(X5, .(X2, .(X4, []))))))))))), X2, X3, X5, X6)) -> unif_linescC_out_gg(.(X1, .(X2, X3)), .(X4, .(X5, X6))) qcD_in_gggggg(X1, X2, X3, X4, X5, X6) -> U42_gggggg(X1, X2, X3, X4, X5, X6, unif_pairscG_in_gg(X1, X2)) U42_gggggg(X1, X2, X3, X4, X5, X6, unif_pairscG_out_gg(X1, X2)) -> U43_gggggg(X1, X2, X3, X4, X5, X6, unif_linescC_in_gg(.(X3, X4), .(X5, X6))) unif_pairscG_in_gg(w, .(w, X2)) -> U44_gg(X2, unif_pairscE_in_g(X2)) unif_pairscG_in_gg(black, .(black, X1)) -> U45_gg(X1, unif_pairscE_in_g(X1)) unif_pairscG_in_gg(black, .(w, X2)) -> U46_gg(X2, unif_pairscE_in_g(X2)) unif_pairscG_in_gg(w, .(black, X2)) -> U47_gg(X2, unif_pairscE_in_g(X2)) U43_gggggg(X1, X2, X3, X4, X5, X6, unif_linescC_out_gg(.(X3, X4), .(X5, X6))) -> qcD_out_gggggg(X1, X2, X3, X4, X5, X6) U44_gg(X2, unif_pairscE_out_g(X2)) -> unif_pairscG_out_gg(w, .(w, X2)) U45_gg(X1, unif_pairscE_out_g(X1)) -> unif_pairscG_out_gg(black, .(black, X1)) U46_gg(X2, unif_pairscE_out_g(X2)) -> unif_pairscG_out_gg(black, .(w, X2)) U47_gg(X2, unif_pairscE_out_g(X2)) -> unif_pairscG_out_gg(w, .(black, X2)) unif_pairscE_in_g([]) -> unif_pairscE_out_g([]) unif_pairscE_in_g(.(w, .(w, X2))) -> U36_g(X2, unif_pairscE_in_g(X2)) unif_pairscE_in_g(.(black, .(black, X1))) -> U37_g(X1, unif_pairscE_in_g(X1)) unif_pairscE_in_g(.(black, .(w, X2))) -> U38_g(X2, unif_pairscE_in_g(X2)) unif_pairscE_in_g(.(w, .(black, X2))) -> U39_g(X2, unif_pairscE_in_g(X2)) U36_g(X2, unif_pairscE_out_g(X2)) -> unif_pairscE_out_g(.(w, .(w, X2))) U37_g(X1, unif_pairscE_out_g(X1)) -> unif_pairscE_out_g(.(black, .(black, X1))) U38_g(X2, unif_pairscE_out_g(X2)) -> unif_pairscE_out_g(.(black, .(w, X2))) U39_g(X2, unif_pairscE_out_g(X2)) -> unif_pairscE_out_g(.(w, .(black, X2))) The set Q consists of the following terms: unif_linescC_in_gg(x0, x1) U35_gg(x0, x1, x2, x3, x4, x5, x6) qcD_in_gggggg(x0, x1, x2, x3, x4, x5) U42_gggggg(x0, x1, x2, x3, x4, x5, x6) unif_pairscG_in_gg(x0, x1) U43_gggggg(x0, x1, x2, x3, x4, x5, x6) U44_gg(x0, x1) U45_gg(x0, x1) U46_gg(x0, x1) U47_gg(x0, x1) unif_pairscE_in_g(x0) U36_g(x0, x1) U37_g(x0, x1) U38_g(x0, x1) U39_g(x0, x1) We have to consider all (P,Q,R)-chains. ---------------------------------------- (28) 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: *U7_GG(X1, X2, X3, unif_linescC_out_gg(X1, X2)) -> UNIF_MATRXB_IN_GG(X2, X3) The graph contains the following edges 2 >= 1, 4 > 1, 3 >= 2 *UNIF_MATRXB_IN_GG(X1, .(X2, X3)) -> U7_GG(X1, X2, X3, unif_linescC_in_gg(X1, X2)) The graph contains the following edges 1 >= 1, 2 > 2, 2 > 3 ---------------------------------------- (29) YES ---------------------------------------- (30) Obligation: Pi DP problem: The TRS P consists of the following rules: VARMATA_IN_GA(.(X1, X2), .(X3, X4)) -> U2_GA(X1, X2, X3, X4, varmatcA_in_ga(X1, X3)) U2_GA(X1, X2, X3, X4, varmatcA_out_ga(X1, X3)) -> VARMATA_IN_GA(X2, X4) VARMATA_IN_GA(.(X1, X2), .(X3, X4)) -> VARMATA_IN_GA(X1, X3) VARMATA_IN_GA(.(black, X1), .(black, X2)) -> VARMATA_IN_GA(X1, X2) VARMATA_IN_GA(.(white, X1), .(w(X2), X3)) -> VARMATA_IN_GA(X1, X3) The TRS R consists of the following rules: varmatcA_in_ga([], []) -> varmatcA_out_ga([], []) varmatcA_in_ga(.(X1, X2), .(X3, X4)) -> U29_ga(X1, X2, X3, X4, varmatcA_in_ga(X1, X3)) varmatcA_in_ga(.(black, X1), .(black, X2)) -> U31_ga(X1, X2, varmatcA_in_ga(X1, X2)) varmatcA_in_ga(.(white, X1), .(w(X2), X3)) -> U32_ga(X1, X2, X3, varmatcA_in_ga(X1, X3)) U32_ga(X1, X2, X3, varmatcA_out_ga(X1, X3)) -> varmatcA_out_ga(.(white, X1), .(w(X2), X3)) U31_ga(X1, X2, varmatcA_out_ga(X1, X2)) -> varmatcA_out_ga(.(black, X1), .(black, X2)) U29_ga(X1, X2, X3, X4, varmatcA_out_ga(X1, X3)) -> U30_ga(X1, X2, X3, X4, varmatcA_in_ga(X2, X4)) U30_ga(X1, X2, X3, X4, varmatcA_out_ga(X2, X4)) -> varmatcA_out_ga(.(X1, X2), .(X3, X4)) unif_pairscG_in_gg(w(X1), .(w(X1), X2)) -> U44_gg(X1, X2, unif_pairscE_in_g(X2)) unif_pairscE_in_g([]) -> unif_pairscE_out_g([]) unif_pairscE_in_g(.(w(X1), .(w(X1), X2))) -> U36_g(X1, X2, unif_pairscE_in_g(X2)) unif_pairscE_in_g(.(black, .(black, X1))) -> U37_g(X1, unif_pairscE_in_g(X1)) unif_pairscE_in_g(.(black, .(w(X1), X2))) -> U38_g(X1, X2, unif_pairscE_in_g(X2)) unif_pairscE_in_g(.(w(X1), .(black, X2))) -> U39_g(X1, X2, unif_pairscE_in_g(X2)) U39_g(X1, X2, unif_pairscE_out_g(X2)) -> unif_pairscE_out_g(.(w(X1), .(black, X2))) U38_g(X1, X2, unif_pairscE_out_g(X2)) -> unif_pairscE_out_g(.(black, .(w(X1), X2))) U37_g(X1, unif_pairscE_out_g(X1)) -> unif_pairscE_out_g(.(black, .(black, X1))) U36_g(X1, X2, unif_pairscE_out_g(X2)) -> unif_pairscE_out_g(.(w(X1), .(w(X1), X2))) U44_gg(X1, X2, unif_pairscE_out_g(X2)) -> unif_pairscG_out_gg(w(X1), .(w(X1), X2)) unif_pairscG_in_gg(black, .(black, X1)) -> U45_gg(X1, unif_pairscE_in_g(X1)) U45_gg(X1, unif_pairscE_out_g(X1)) -> unif_pairscG_out_gg(black, .(black, X1)) unif_pairscG_in_gg(black, .(w(X1), X2)) -> U46_gg(X1, X2, unif_pairscE_in_g(X2)) U46_gg(X1, X2, unif_pairscE_out_g(X2)) -> unif_pairscG_out_gg(black, .(w(X1), X2)) unif_pairscG_in_gg(w(X1), .(black, X2)) -> U47_gg(X1, X2, unif_pairscE_in_g(X2)) U47_gg(X1, X2, unif_pairscE_out_g(X2)) -> unif_pairscG_out_gg(w(X1), .(black, X2)) unif_linescC_in_gg(.(X1, .(X2, X3)), .(X4, .(X5, X6))) -> U35_gg(X1, X2, X3, X4, X5, X6, qcD_in_gggggg(X1, .(X2, .(X4, .(X5, .(X1, .(X4, .(X2, .(X5, .(X1, .(X5, .(X2, .(X4, []))))))))))), X2, X3, X5, X6)) qcD_in_gggggg(X1, X2, X3, X4, X5, X6) -> U42_gggggg(X1, X2, X3, X4, X5, X6, unif_pairscG_in_gg(X1, X2)) U42_gggggg(X1, X2, X3, X4, X5, X6, unif_pairscG_out_gg(X1, X2)) -> U43_gggggg(X1, X2, X3, X4, X5, X6, unif_linescC_in_gg(.(X3, X4), .(X5, X6))) unif_linescC_in_gg(.(X1, []), .(X2, [])) -> unif_linescC_out_gg(.(X1, []), .(X2, [])) U43_gggggg(X1, X2, X3, X4, X5, X6, unif_linescC_out_gg(.(X3, X4), .(X5, X6))) -> qcD_out_gggggg(X1, X2, X3, X4, X5, X6) U35_gg(X1, X2, X3, X4, X5, X6, qcD_out_gggggg(X1, .(X2, .(X4, .(X5, .(X1, .(X4, .(X2, .(X5, .(X1, .(X5, .(X2, .(X4, []))))))))))), X2, X3, X5, X6)) -> unif_linescC_out_gg(.(X1, .(X2, X3)), .(X4, .(X5, X6))) The argument filtering Pi contains the following mapping: .(x1, x2) = .(x1, x2) varmatcA_in_ga(x1, x2) = varmatcA_in_ga(x1) [] = [] varmatcA_out_ga(x1, x2) = varmatcA_out_ga(x1, x2) U29_ga(x1, x2, x3, x4, x5) = U29_ga(x1, x2, x5) black = black U31_ga(x1, x2, x3) = U31_ga(x1, x3) white = white U32_ga(x1, x2, x3, x4) = U32_ga(x1, x4) w(x1) = w U30_ga(x1, x2, x3, x4, x5) = U30_ga(x1, x2, x3, x5) unif_pairscG_in_gg(x1, x2) = unif_pairscG_in_gg(x1, x2) U44_gg(x1, x2, x3) = U44_gg(x2, x3) unif_pairscE_in_g(x1) = unif_pairscE_in_g(x1) unif_pairscE_out_g(x1) = unif_pairscE_out_g(x1) U36_g(x1, x2, x3) = U36_g(x2, x3) U37_g(x1, x2) = U37_g(x1, x2) U38_g(x1, x2, x3) = U38_g(x2, x3) U39_g(x1, x2, x3) = U39_g(x2, x3) unif_pairscG_out_gg(x1, x2) = unif_pairscG_out_gg(x1, x2) U45_gg(x1, x2) = U45_gg(x1, x2) U46_gg(x1, x2, x3) = U46_gg(x2, x3) U47_gg(x1, x2, x3) = U47_gg(x2, x3) unif_linescC_in_gg(x1, x2) = unif_linescC_in_gg(x1, x2) U35_gg(x1, x2, x3, x4, x5, x6, x7) = U35_gg(x1, x2, x3, x4, x5, x6, x7) qcD_in_gggggg(x1, x2, x3, x4, x5, x6) = qcD_in_gggggg(x1, x2, x3, x4, x5, x6) U42_gggggg(x1, x2, x3, x4, x5, x6, x7) = U42_gggggg(x1, x2, x3, x4, x5, x6, x7) U43_gggggg(x1, x2, x3, x4, x5, x6, x7) = U43_gggggg(x1, x2, x3, x4, x5, x6, x7) unif_linescC_out_gg(x1, x2) = unif_linescC_out_gg(x1, x2) qcD_out_gggggg(x1, x2, x3, x4, x5, x6) = qcD_out_gggggg(x1, x2, x3, x4, x5, x6) VARMATA_IN_GA(x1, x2) = VARMATA_IN_GA(x1) U2_GA(x1, x2, x3, x4, x5) = U2_GA(x1, x2, x5) We have to consider all (P,R,Pi)-chains ---------------------------------------- (31) UsableRulesProof (EQUIVALENT) For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. ---------------------------------------- (32) Obligation: Pi DP problem: The TRS P consists of the following rules: VARMATA_IN_GA(.(X1, X2), .(X3, X4)) -> U2_GA(X1, X2, X3, X4, varmatcA_in_ga(X1, X3)) U2_GA(X1, X2, X3, X4, varmatcA_out_ga(X1, X3)) -> VARMATA_IN_GA(X2, X4) VARMATA_IN_GA(.(X1, X2), .(X3, X4)) -> VARMATA_IN_GA(X1, X3) VARMATA_IN_GA(.(black, X1), .(black, X2)) -> VARMATA_IN_GA(X1, X2) VARMATA_IN_GA(.(white, X1), .(w(X2), X3)) -> VARMATA_IN_GA(X1, X3) The TRS R consists of the following rules: varmatcA_in_ga([], []) -> varmatcA_out_ga([], []) varmatcA_in_ga(.(X1, X2), .(X3, X4)) -> U29_ga(X1, X2, X3, X4, varmatcA_in_ga(X1, X3)) varmatcA_in_ga(.(black, X1), .(black, X2)) -> U31_ga(X1, X2, varmatcA_in_ga(X1, X2)) varmatcA_in_ga(.(white, X1), .(w(X2), X3)) -> U32_ga(X1, X2, X3, varmatcA_in_ga(X1, X3)) U29_ga(X1, X2, X3, X4, varmatcA_out_ga(X1, X3)) -> U30_ga(X1, X2, X3, X4, varmatcA_in_ga(X2, X4)) U31_ga(X1, X2, varmatcA_out_ga(X1, X2)) -> varmatcA_out_ga(.(black, X1), .(black, X2)) U32_ga(X1, X2, X3, varmatcA_out_ga(X1, X3)) -> varmatcA_out_ga(.(white, X1), .(w(X2), X3)) U30_ga(X1, X2, X3, X4, varmatcA_out_ga(X2, X4)) -> varmatcA_out_ga(.(X1, X2), .(X3, X4)) The argument filtering Pi contains the following mapping: .(x1, x2) = .(x1, x2) varmatcA_in_ga(x1, x2) = varmatcA_in_ga(x1) [] = [] varmatcA_out_ga(x1, x2) = varmatcA_out_ga(x1, x2) U29_ga(x1, x2, x3, x4, x5) = U29_ga(x1, x2, x5) black = black U31_ga(x1, x2, x3) = U31_ga(x1, x3) white = white U32_ga(x1, x2, x3, x4) = U32_ga(x1, x4) w(x1) = w U30_ga(x1, x2, x3, x4, x5) = U30_ga(x1, x2, x3, x5) VARMATA_IN_GA(x1, x2) = VARMATA_IN_GA(x1) U2_GA(x1, x2, x3, x4, x5) = U2_GA(x1, x2, x5) We have to consider all (P,R,Pi)-chains ---------------------------------------- (33) PiDPToQDPProof (SOUND) Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. ---------------------------------------- (34) Obligation: Q DP problem: The TRS P consists of the following rules: VARMATA_IN_GA(.(X1, X2)) -> U2_GA(X1, X2, varmatcA_in_ga(X1)) U2_GA(X1, X2, varmatcA_out_ga(X1, X3)) -> VARMATA_IN_GA(X2) VARMATA_IN_GA(.(X1, X2)) -> VARMATA_IN_GA(X1) VARMATA_IN_GA(.(black, X1)) -> VARMATA_IN_GA(X1) VARMATA_IN_GA(.(white, X1)) -> VARMATA_IN_GA(X1) The TRS R consists of the following rules: varmatcA_in_ga([]) -> varmatcA_out_ga([], []) varmatcA_in_ga(.(X1, X2)) -> U29_ga(X1, X2, varmatcA_in_ga(X1)) varmatcA_in_ga(.(black, X1)) -> U31_ga(X1, varmatcA_in_ga(X1)) varmatcA_in_ga(.(white, X1)) -> U32_ga(X1, varmatcA_in_ga(X1)) U29_ga(X1, X2, varmatcA_out_ga(X1, X3)) -> U30_ga(X1, X2, X3, varmatcA_in_ga(X2)) U31_ga(X1, varmatcA_out_ga(X1, X2)) -> varmatcA_out_ga(.(black, X1), .(black, X2)) U32_ga(X1, varmatcA_out_ga(X1, X3)) -> varmatcA_out_ga(.(white, X1), .(w, X3)) U30_ga(X1, X2, X3, varmatcA_out_ga(X2, X4)) -> varmatcA_out_ga(.(X1, X2), .(X3, X4)) The set Q consists of the following terms: varmatcA_in_ga(x0) U29_ga(x0, x1, x2) U31_ga(x0, x1) U32_ga(x0, x1) U30_ga(x0, x1, x2, x3) We have to consider all (P,Q,R)-chains. ---------------------------------------- (35) 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: *U2_GA(X1, X2, varmatcA_out_ga(X1, X3)) -> VARMATA_IN_GA(X2) The graph contains the following edges 2 >= 1 *VARMATA_IN_GA(.(X1, X2)) -> U2_GA(X1, X2, varmatcA_in_ga(X1)) The graph contains the following edges 1 > 1, 1 > 2 *VARMATA_IN_GA(.(X1, X2)) -> VARMATA_IN_GA(X1) The graph contains the following edges 1 > 1 *VARMATA_IN_GA(.(black, X1)) -> VARMATA_IN_GA(X1) The graph contains the following edges 1 > 1 *VARMATA_IN_GA(.(white, X1)) -> VARMATA_IN_GA(X1) The graph contains the following edges 1 > 1 ---------------------------------------- (36) YES