Data Portal @ linkeddatafragments.org

Matches in DBpedia 2014 for { <http://dbpedia.org/resource/Wang_tile> ?p ?o. }

• Wang_tile abstract "Wang tiles (or Wang dominoes), first proposed by mathematician, logician, and philosopher Hao Wang in 1961, are a class of formal systems. They are modelled visually by equal-sized squares with a color on each edge which can be arranged side by side (on a regular square grid) so that abutting edges of adjacent tiles have the same color; the tiles cannot be rotated or reflected. The basic question about a set of Wang tiles is whether it can tile the plane or not, i.e., whether copies of the tiles can be arranged to fill an infinite plane, following the adjacency rules.In 1961, Wang conjectured that if a finite set of tiles can tile the plane, then there exists also a periodic tiling, i.e., a tiling that is invariant under translations by vectors in a 2-dimensional lattice, like a wallpaper pattern. He also observed that this conjecture would imply the existence of an algorithm to decide whether a given finite set of tiles can tile the plane.But in 1966, Robert Berger proved that no such algorithm existed, by showing how to translate any Turing machine into a set of Wang tiles that tiles the plane if and only if the Turing machine does not halt. The undecidability of the halting problem then implies the undecidability of Wang's tiling problem. Combining this with Wang's observation shows that there must exist a finite set of Wang tiles that tiles the plane, but only aperiodically. This is similar to a Penrose tiling, or the arrangement of atoms in a quasicrystal. Although Berger's original set contained 20,426 tiles, he conjectured that smaller sets would work, including subsets of his set. In later years, increasingly smaller sets were found. For example, the set of 13 tiles given above is an aperiodic set published by Karel Culik II in 1996. It can tile the plane, but not periodically. Wang tiles can be generalized in various ways, all of which are also undecidable in the above sense. For example, Wang cubes are equal-sized cubes with colored faces and side colors can be matched on any polygonal tessellation. Culik and Kari have demonstrated aperiodic sets of Wang cubes. Winfree et al. have demonstrated the feasibility of creating molecular "tiles" made from DNA (deoxyribonucleic acid) that can act as Wang tiles. Mittal et al. have shown that these tiles can also be composed of peptide nucleic acid (PNA), a stable artificial mimic of DNA.Wang tiles have recently become a popular tool for procedural synthesis of textures, heightfields, and other large and nonrepeating bidimensional data sets; a small set of precomputed or hand-made source tiles can be assembled very cheaply without too obvious repetitions and without periodicity.In this case, traditional aperiodic tilings would show their very regular structure; much less constrained sets that guarantee at least two tile choices for any two given side colors are common because tileability is easily ensured and each tile can be selected pseudorandomly.Papers about this application include: Jos Stam (1997), Aperiodic Texture Mapping introduces the idea of using Wang tiles for texture variation, with a deterministic substitution system. Michael F. Cohen, Jonathan Shade, Stefan Hiller, Oliver Deussen (2003), Wang Tiles for Image and Texture Generation introduces stochastic tiling and is very popular. Li-Yi Wei (2004), "Tile-Based Texture Mapping on Graphics Hardware" applies Wang Tiles for real-time texturing on a GPU Johannes Kopf, Daniel Cohen-Or, Oliver Deussen, Dani Lischinski (2006), Recursive Wang Tiles for Real-Time Blue Noise shows advanced applications.Wang tiles have been extensively used in cellular automata theory decidability proofs; see for example.The short story Wang's Carpets, later expanded to the novel Diaspora, by Greg Egan, postulates a universe, complete with resident organisms and intelligent beings, embodied as Wang tiles implemented by patterns of complex molecules.".
• Wang_tile thumbnail Wang_tiles.svg?width=300.
• Wang_tile wikiPageExternalLink tile_mapping_gh2004.
• Wang_tile wikiPageExternalLink blue_noise.
• Wang_tile wikiPageExternalLink WangFinal.pdf.
• Wang_tile wikiPageExternalLink R046.pdf.
• Wang_tile wikiPageExternalLink aperiod.htm.
• Wang_tile wikiPageID "65798".
• Wang_tile wikiPageRevisionID "568787080".
• Wang_tile hasPhotoCollection Wang_tile.
• Wang_tile subject Category:Tessellation.
• Wang_tile subject Category:Theory_of_computation.
• Wang_tile comment "Wang tiles (or Wang dominoes), first proposed by mathematician, logician, and philosopher Hao Wang in 1961, are a class of formal systems. They are modelled visually by equal-sized squares with a color on each edge which can be arranged side by side (on a regular square grid) so that abutting edges of adjacent tiles have the same color; the tiles cannot be rotated or reflected.".
• Wang_tile label "Wang tile".
• Wang_tile label "Wang-Parkettierung".
• Wang_tile label "Wang-betegeling".
• Wang_tile sameAs Wang-Parkettierung.
• Wang_tile sameAs Wang-betegeling.
• Wang_tile sameAs m.0hfsz.
• Wang_tile sameAs Q474147.
• Wang_tile sameAs Q474147.
• Wang_tile wasDerivedFrom Wang_tile?oldid=568787080.
• Wang_tile depiction Wang_tiles.svg.
• Wang_tile isPrimaryTopicOf Wang_tile.