ワンのタイルとは - わかりやすく解説 Weblio辞書

ワンのタイル

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2024/04/10 13:30 UTC 版)

ワンのタイル（英: Wang tiles, Wang dominoes,中: 王氏砖）とは、数学者、論理学者、哲学者であったハオ・ワン（王浩）が1961年に始めて提案した一種の形式体系である。視覚的には辺ごとに色付けされた正方形タイルとしてモデル化される。数種のタイルからなる集合を選び、隣り合う辺の色が一致するようにタイルのコピーを並べていく。このときタイルを回転・鏡映させてはいけない。

脚注

注釈

^ "Wang's Carpets", 『プランク・ダイヴ』（2011年、早川書房）収録

出典

^ Wang, Hao (1961), “Proving theorems by pattern recognition—II”, Bell System Technical Journal 40 (1): 1–41, doi:10.1002/j.1538-7305.1961.tb03975.x . Wang proposes his tiles, and conjectures that there are no aperiodic sets.
^ Wang, Hao (November 1965), “Games, logic and computers”, Scientific American: 98–106 . Presents the domino problem for a popular audience.
^ Renz, Peter (1981), “Mathematical proof: What it is and what it ought to be”, The Two-Year College Mathematics Journal 12 (2): 83–103, doi:10.2307/3027370 .
^ ^a ^b ^c ^d Berger, Robert (1966), “The undecidability of the domino problem”, Memoirs of the American Mathematical Society 66: 72, MR 0216954 . Berger coins the term "Wang tiles", and demonstrates the first aperiodic set of them.
^ Robinson, Raphael M. (1971), “Undecidability and nonperiodicity for tilings of the plane”, Inventiones Mathematicae 12: 177–209, Bibcode: 1971InMat..12..177R, doi:10.1007/bf01418780, MR0297572 .
^ ^a ^b Culik, Karel, II (1996), “An aperiodic set of 13 Wang tiles”, Discrete Mathematics 160 (1-3): 245–251, doi:10.1016/S0012-365X(96)00118-5, MR1417576 . (Showed an aperiodic set of 13 tiles with 5 colors).
^ Kari, Jarkko (1996), “A small aperiodic set of Wang tiles”, Discrete Mathematics 160 (1-3): 259–264, doi:10.1016/0012-365X(95)00120-L, MR1417578 .
^ ^a ^b Jeandel, Emmanuel; Rao, Michael (2015), “An aperiodic set of 11 Wang tiles”, CoRR, arXiv:1506.06492, Bibcode: 2015arXiv150606492J . (Showed an aperiodic set of 11 tiles with 4 colors)}
^ Culik, Karel, II; Kari, Jarkko (1995), “An aperiodic set of Wang cubes”, Journal of Universal Computer Science 1 (10): 675–686, doi:10.1007/978-3-642-80350-5_57, MR1392428 .
^ Winfree, E.; Liu, F.; Wenzler, L.A.; Seeman, N.C. (1998), “Design and self-assembly of two-dimensional DNA crystals”, Nature 394: 539–544, Bibcode: 1998Natur.394..539W, doi:10.1038/28998, PMID 9707114 .
^ Lukeman, P.; Seeman, N.; Mittal, A. (2002), “Hybrid PNA/DNA nanosystems”, 1st International Conference on Nanoscale/Molecular Mechanics (N-M2-I), Outrigger Wailea Resort, Maui, Hawaii .
^ Stam, Jos (1997), Aperiodic Texture Mapping . Introduces the idea of using Wang tiles for texture variation, with a deterministic substitution system.
^ Cohen, Michael F.; Shade, Jonathan; Hiller, Stefan; Deussen, Oliver (2003), “Wang tiles for image and texture generation”, ACM SIGGRAPH 2003, New York, NY, USA: ACM, pp. 287–294, doi:10.1145/1201775.882265, ISBN 1-58113-709-5 . Introduces stochastic tiling.
^ Wei, Li-Yi (2004), “Tile-based texture mapping on graphics hardware”, Proceedings of the ACM SIGGRAPH/EUROGRAPHICS Conference on Graphics Hardware (HWWS '04), New York, NY, USA: ACM, pp. 55–63, doi:10.1145/1058129.1058138, ISBN 3-905673-15-0 . Applies Wang Tiles for real-time texturing on a GPU.
^ . Kopf, Johannes; Cohen-Or, Daniel; Deussen, Oliver; Lischinski, Dani (2006), “Recursive Wang tiles for real-time blue noise”, ACM SIGGRAPH 2006, New York, NY, USA: ACM, pp. 509–518, doi:10.1145/1179352.1141916, ISBN 1-59593-364-6 . Shows advanced applications.
^ Kari, Jarkko (1990), “Reversibility of 2D cellular automata is undecidable”, Cellular automata: theory and experiment (Los Alamos, NM, 1989), Physica D: Nonlinear Phenomena, 45, pp. 379–385, Bibcode: 1990PhyD...45..379K, doi:10.1016/0167-2789(90)90195-U, MR1094882 .
^ Burnham, Karen (2014), Greg Egan, Modern Masters of Science Fiction, University of Illinois Press, pp. 72–73, ISBN 9780252096297 .