Search

Nilpotent cellular automata have the simplest possible dynamics: all initial configurations lead in bounded time into the unique fixed point of the system. We investigate nilpotency in the setup of one-dimensional non-uniform cellular automata (NUCA) where different cells may use different local rules. There are infinitely many cells in NUCA but only a finite number of different local rules. Changing the distribution of the local rules in the system may drastically change the dynamics. We prove that if the available local rules are such that every periodic distribution of the rules leads to nilpotent behavior then so do also all eventually periodic distributions. However, in some cases there may be non-periodic distributions that are not nilpotent even if all periodic distributions are nilpotent. We demonstrate such a possibility using aperiodic Wang tile sets. We also investigate temporally periodic points in NUCA. In contrast to classical uniform cellular automata, there are NUCA—even reversible equicontinuous ones—that do not have any temporally periodic points. We prove the undecidability of this property: there is no algorithm to determine if a NUCA with a given finite distribution of local rules has a periodic point.

A recently introduced representation by a set of Wang tiles—a generalization of the traditional Periodic Unit Cell-based approach—serves as a reduced geometrical model for materials with stochastic heterogeneous microstructure, enabling an efficient synthesis of microstructural realizations. To facilitate macroscopic analyses with a fully resolved microstructure generated with Wang tiles, we develop a reduced order modelling scheme utilizing pre-computed characteristic features of the tiles. In the offline phase, inspired by computational homogenization, we extract continuous fluctuation fields from the compressed microstructural representation as responses to generalized loading represented by the first- and second-order macroscopic gradients. In the online phase, using the ansatz of the generalized finite element method, we combine these fields with a coarse finite element discretization to create microstructure-informed reduced modes specific for a given macroscopic problem. Considering a two-dimensional scalar elliptic problem, we demonstrate that our scheme delivers less than 3% error in both the relative $$L_2$$ and energy norms with only 0.01% of the unknowns when compared to the fully resolved problem. Accuracy can be further improved by locally refining the macroscopic discretization and/or employing more pre-computed fluctuation fields. Finally, unlike standard snapshot-based reduced-order approaches, our scheme handles significant changes in the macroscopic geometry or loading without the need for recalculating the offline phase, because the fluctuation fields are extracted without any prior knowledge of the macroscopic problem.

Jeandel and Rao proved that 11 is the size of the smallest set of Wang tiles, i.e., unit squares with colored edges, that admit valid tilings (contiguous edges of adjacent tiles have the same color) of the plane, none of them being invariant under a nontrivial translation. We study herein the Wang shift $\Omega_0$ made of all valid tilings using the set $\mathcal{T}_0$ of 11 aperiodic Wang tiles discovered by Jeandel and Rao. We show that there exists a minimal subshift $X_0$ of $\Omega_0$ such that every tiling in $X_0$ can be decomposed uniquely into 19 distinct patches of sizes ranging from 45 to 112 that are equivalent to a set of 19 self-similar and aperiodic Wang tiles. We suggest that this provides an almost complete description of the substitutive structure of Jeandel-Rao tilings, as we believe that $\Omega_0\setminus X_0$ is a null set for any shift-invariant probability measure on $\Omega_0$. The proof is based on 12 elementary steps, 10 of which involve the same procedure allowing one to desubstitute Wang tilings from the existence of a subset of marker tiles. The 2 other steps involve the addition of decorations to deal with fault lines and changing the base of the $\mathbb{Z}^2$-action through a shear conjugacy. Algorithms are provided to find markers, recognizable substitutions, and shear conjugacy from a set of Wang tiles., Comment: v1: 38p., 18 Fig. arXiv admin note: text overlap with arXiv:1802.03265 (the preliminaries). v2: 42p. Substitutions and Wang tile sets now appears directly in the proofs. Image of letters are now sorted by length and then lexicographically. v3+v4: 48p., corrections after review. Jupyter notebook available at https://nbviewer.jupyter.org/url/www.slabbe.org/Publications/arxiv_1808_07768_v4.ipynb

The Wang tiling is a classical problem in combinatorics. A major theoretical question is to find a (small) set of tiles which tiles the plane only aperiodically. In this case, resulting tilings are rather restrictive. On the other hand, Wang tiles are used as a tool to generate textures and patterns in computer graphics. In these applications, a set of tiles is normally chosen so that it tiles the plane or its sub-regions easily in many different ways. With computer graphics applications in mind, we introduce a class of such tileset, which we call sequentially permissive tilesets, and consider tiling problems with constrained boundary. We apply our methodology to a special set of Wang tiles, called Brick Wang tiles, introduced by Derouet-Jourdan et al. in 2016 to model wall patterns. We generalise their result by providing a linear algorithm to decide and solve the tiling problem for arbitrary planar regions with holes.

A [Wang tile](https://en.wikipedia.org/wiki/Wang_tile) is a square tile such that each of its edges is colored. The plane can be _tiled_ with a set of Wang tiles if tiles contained in the set can be placed in the plane without rotations and reflections such that the whole plane is covered and the colors of their edges match at adjacent tiles. Wang tiles were introduced by [Wang](https://en.wikipedia.org/wiki/Hao_Wang_(academic)) in 1961 to study decidability in mathematical logic, and they are also of relevance to other areas of theoretical computer science. Wang conjectured that if the plane can be tiled with a set of Wang tiles, then it can be tiled in a periodic way. This was refuted by [Berger](https://en.wikipedia.org/wiki/Robert_Berger_(mathematician)) in 1966 who described how a Turing machine computation can be emulated by Wang tilings and constructed a set of 104 Wang tiles for which the plane can be tiled with the set but only aperiodically. In the first volume of [The Art of Computer Programming](https://en.wikipedia.org/wiki/The_Art_of_Computer_Programming), Knuth presented a simplified version of Berger's set with 92 Wang tiles. Smaller sets of Wang tiles that tile the plane only aperiodically were subsequently constructed with the smallest set containing 13 Wang tiles, found by Culik II in 1996. The authors construct a set of 11 Wang tiles with edges colored with four colors such that the plane can be tiled with the set but each tiling is aperiodic. Moreover, they establish that there is no set of at most 10 Wang tiles with this property. The number of colors is also the best possible as it is known that every set of Wang tiles with edges colored with at most three colors either can tile the plane periodically or cannot tile the plane at all.

Motivated by the study of Fibonacci-like Wang shifts, we define a numeration system for \(\mathbb {Z}\) and \(\mathbb {Z}^2\) based on the binary alphabet \(\{0,1\}\). We introduce a set of 16 Wang tiles that admits a valid tiling of the plane described by a deterministic finite automaton taking as input the representation of a position \((m,n)\in \mathbb {Z}^2\) and outputting a Wang tile.

This investigation studies the nonemptiness problems of Wang cubes with two colors. Wang cubes are unit cubes with colored faces, which are generalized from Wang tiles. For a set $B$ of Wang cubs, $\Sigma(B)$ is the set of all global patterns on $\mathbb{Z}^3$ that can be constructed by the cubes in $B$. The nonemptiness problem is to determine whether $\Sigma(B) \neq \emptyset$ or not. Denote by $\mathcal{P}(B)$ the set of all periodic patterns on $\mathbb{Z}^3$ that can be constructed by the cubes in $B$. For Wang cubes, the corresponding Wang's conjecture is that if $\Sigma(B) \neq \emptyset$, then $\mathcal{P}(B) \neq \emptyset$. ¶ We introduce the transition matrices and trace operators to determine whether $\Sigma(B) \neq \emptyset$ and $\mathcal{P}(B) \neq \emptyset$ or not, respectively. A basic set $B$ is called a minimal cycle generator if $\mathcal{P}(B) \neq \emptyset$ but $\mathcal{P}(B') = \emptyset$ for all $B' \subsetneqq B$. By computer computation, there exist $86$ equivalence classes of minimal cycle generators with two colors. By verifying that the basic sets $B$ that contains no minimal cycle generators satisfy $\Sigma(B) = \emptyset$, we prove that the Wang's conjecture for Wang cubes with two colors is true.

In this paper we present our recent work focused on the analysis of the abilities of Wang Tiles method and Automatic tile design method to synthesize the micro-structure of cellular materials, especially particular type of metal foam.Wang Tiles method stores and compress the micro-structure in a set of Wang Tiles and by the means of stochastic tiling algorithms the planar domain is reconstructed. The used tiles are created by the Automatic tile design method from respective number of small specimens extracted from the original micro-structure image. As an additional step the central areas of automatically designed tiles are patched to suppress the influence of repeating tile edges (and relevant tile quarters) on inducing artifacts. In the presented analysis the performance of raw and patched tiles of different sizes in conjunction of various tile sets is investigated.

Procedural noise functions have many applications in computer graphics, ranging from texture synthesis to atmospheric effect simulation or to landscape geometry specification. Noise can either be precomputed and stored into a texture, or evaluated directly at application runtime. This choice offers a tradeoff between image variance, memory consumption and performance. Advanced tiling algorithms can be used to decrease visual repetition. Wang tiles allow a plane to be tiled in a non-periodic way, using a relatively small set of textures. Tiles can be arranged in a single texture map to enable the GPU to use hardware filtering. In this paper, we present modifications to several popular procedural noise functions that directly produce texture maps containing the smallest complete Wang tile set. The findings presented in this paper enable non-periodic tiling of these noise functions and textures based on them, both at runtime and as a preprocessing step. These findings also allow decreasing repetition of noise-based effects in computer-generated images at a small performance cost, while maintaining or even reducing the memory consumption.

Wang tile based representation of a heterogeneous material facilitates fast synthesis of non-periodic microstructure realizations. In this paper, we apply the tiling approach in numerical homogenization to determine the Representative Volume Element size related to the user-defined significance level and the discrepancy between bounds on the apparent properties. First, the tiling concept is employed to efficiently generate arbitrarily large, statistically consistent realizations of investigated microstructures. Second, benefiting from the regular structure inherent to the tiling concept, the Partition theorem, and statistical sampling, we construct confidence intervals of the apparent properties related to the size of a microstructure specimen. Based on the interval width and the upper and lower bounds on the apparent properties, we adaptively generate additional microstructure realizations in order to arrive at an RVE satisfying the prescribed tolerance. The methodology is illustrated with the homogenization of thermo-mechanical properties of three two-dimensional microstructure models: a microstructure with mono-disperse elliptic inclusions, foam, and sandstone., 19 pages, 22 figures, post-print version

Inspired by the first order numerical homogenization, we present a method for extracting continuous fluctuation fields from the Wang tile based compression of a material microstructure. The fluctuation fields are then used as enrichment basis in Extended Finite Element Method (XFEM) to reduce number of unknowns in problems with fully resolved microstructural geometry synthesized by means of the tiling concept. In addition, the XFEM basis functions are taken as reduced modes of a detailed discretization in order to circumvent the need for non-standard numerical quadratures. The methodology is illustrated with a scalar steady-state problem.

Wang tiles proved to be a convenient tool for the design of aperiodic tilings in computer graphics and in materials engineering. While there are several algorithms for generation of finite-sized tilings, they exploit the specific structure of individual tile sets, which prevents their general usage. In this contribution, we reformulate the NP-complete tiling generation problem as a binary linear program, together with its linear and semidefinite relaxations suitable for the branch and bound method. Finally, we assess the performance of the established formulations on generations of several aperiodic tilings reported in the literature, and conclude that the linear relaxation is better suited for the problem.

In this contribution, we present the concept of Wang Tiles as a surrogate of the periodic unit cell method (PUC) for modelling of materials with heterogeneous microstructures and for synthesis of micro-mechanical fields. The concept is based on a set of specifically designed cells that compresses the stochastic microstructure into a small set of statistical volume elements – tiles. Tiles are placed side by side according to matching edges like in a game of domino. Opposite to the repeating pattern of PUC the Wang Tiles method with the stochastic tiling algorithm preserves the randomness for reconstructed microstructures. The same process is applied to obtain the micro-mechanical response of domains where the evaluation as one piece would be time consuming. Therefore the micro-mechanical quantities are evaluated only on tiles (with surrounding layers of tiles of each addressed tile included into the evaluation) and then synthesized to the micro-mechanical field of whole domain.

This contribution deals with algorithms for the generation of modified Wang tiles as a tool for the heterogeneous materials modelling. The proposed approach considers material domains only with 2D hard discs of both equal and different radii distributed within a matrix. Previous works showed potential of the Wang tile principles for reconstruction of heterogeneous materials. The main advantage of the tiling theory for material modelling is to stack large/infinite areas with relative small set of tiles with emphasis on a periodicity reduction in comparison with the traditional Periodic Unit Cell (PUC) concept. The basic units of the Wang Tiling are tiles with codes (colors) on edges. The algorithm for distribution of hard discs is based on the molecular dynamics to avoid particles overlapping. Unfortunately the nature of the Wang tiling together with molecular dynamics algorithms cause periodicity artefacts especially in tile corners of a composed material domain. In this paper a new algorithm with adaptive tile boundaries is presented in order to avoid edge and corner periodicity.

In this paper, we present the concept of the Wang tiles method that compresses the stochastic microstructure into a small set of statistical volume elements – tiles. These tiles are then used for modeling of materials with heterogeneous stochastic microstructures and to streamline the calculations on the micro-scale level. In the following text, we focus on the fluctuation fields that are obtained as the main tiling reconstructed from the micro-mechanical quantities evaluated on individual tiles. But because of the non-local character of mechanical quantities the synthesized fluctuation field contain jumps between adjacent tiles. To prevent this phenomenon, the nearest surrounding tiles are included into the evaluation for each tile from the main tiling. Then the mechanical response is solved on these small so-called local tilings and results for middle tiles are saved. The main tiling is then synthesized using these results and further can be utilized as an enrichment functions for the finite element method.

We define a Wang tile set $\mathcal{U}$ of cardinality 19 and show that the set $\Omega_\mathcal{U}$ of all valid Wang tilings $\mathbb{Z}^2\to\mathcal{U}$ is self-similar, aperiodic and is a minimal subshift of $\mathcal{U}^{\mathbb{Z}^2}$. Thus $\mathcal{U}$ is the second smallest self-similar aperiodic Wang tile set known after Ammann's set of 16 Wang tiles. The proof is based on the unique composition property. We prove the existence of an expansive, primitive and recognizable $2$-dimensional morphism $\omega:\Omega_\mathcal{U}\to\Omega_\mathcal{U}$ that is onto up to a shift. The proof of recognizability is done in two steps using at each step the same criteria (the existence of marker tiles) for proving the existence of a recognizable one-dimensional substitution that sends each tile either on a single tile or on a domino of two tiles., Comment: Version 1: 30 pages, 8 figures. Version 2: 27 pages, 9 figures, results are now based on the notion of marker tiles which simplifies greatly the presentation while reducing its size. Version 3: fixed a typo in Figure 9

Microstructural geometry plays a critical role in the response of heterogeneous materials. Consequently, methods for generating microstructural samples are increasingly crucial to advanced numerical analyses. We extend Sonon et al.'s unified framework, developed originally for generating particulate and foam-like microstructural geometries of Periodic Unit Cells, to non-periodic microstructural representations based on the formalism of Wang tiles. This formalism has been recently proposed in order to generalize the Periodic Unit Cell approach, enabling a fast synthesis of arbitrarily large, stochastic microstructural samples from a handful of domains with predefined compatibility constraints. However, a robust procedure capable of designing complex, three-dimensional, foam-like and cellular morphologies of Wang tiles has not yet been proposed. This contribution fills the gap by significantly broadening the applicability of the tiling concept. Since the original Sonon et al.'s framework builds on a random sequential addition of particles enhanced with an implicit representation of particle boundaries by the level-set field, we first devise an analysis based on a connectivity graph of a tile set, resolving the question where a particle should be copied when it intersects a tile boundary. Next, we introduce several modifications to the original algorithm that are necessary to ensure microstructural compatibility in the generalized periodicity setting of Wang tiles. Having established a universal procedure for generating tile morphologies, we compare strictly aperiodic and stochastic sets with the same cardinality in terms of reducing the artificial periodicity in reconstructed microstructural samples. We demonstrate the superiority of the vertex-defined tile sets for two-dimensional problems and illustrate the capabilities of the algorithm with two- and three-dimensional examples., 16 pages, 16 figures. Abstract has been shortened to match the arXiv.org's limit of 1920 characters

The Kari–Culik tilings are formed from a set of 13 Wang tiles that tile the plane only aperiodically. They are the smallest known set of Wang tiles to do so and are not as well understood as other examples of aperiodic Wang tiles. We show that the $\mathbb{Z}^{2}$ action by translation on a certain subset of the Kari–Culik tilings, namely those whose rows can be interpreted as Sturmian sequences (rotation sequences), is minimal. We give a characterization of this space as a skew product as well as explicit bounds on the waiting time between occurrences of $m\times n$ configurations.

The paper deals with a modelling of random heterogeneous materials composed of circular solid particles within a matrix. The concept of Wang tiling is utilized to generate material patterns. Wang tiling principles enable to create random heterogeneous structures with high reduction of periodicity artefacts in comparison with the traditional approach of the Periodic Unit Cell (PUC). A packing algorithm based on molecular dynamics for Wang tiles generation is introduced. During the process of generation particles grow, move and collide with tile edges and with each other in order to achieve required or optimal particle placements without an overlapping. A set of Wang tiles include eight different tiles with specific boundary conditions which allow composing of random heterogeneous materials applying a stochastic tiling algorithm. An optimization technique based on the Particle Swarm Optimization (PSO) is utilized to get a material model with similar statistical information compared with a reference pattern. Due to the nature of investigated materials the Radial Distribution Function (RDF) was chosen as a tool for statistical description.

This contribution presents a statistical evaluation of microstructures assembled by means of2D Wang tiles, morphology of which is designed employing an algorithm based on Discrete ElementMethod. Comparison between realization of Wang tiling and Periodic Unit Cell representation is providedin terms of spatial descriptors. Namely, radial distribution function g2 and two-point probabilityfunction S2 are used to assess the artefacts related to periodicity in synthesized microstructures. Wedemonstrate significant reduction in periodicity achieved with Wang tiling (compared to the periodicsynthesis) in both the microstructures and results of numerical simulations.

Material behavior and microstructure geometries at small scales strongly influence the physical behavior at higher scales. For example, defects like cracks and dislocations evolve at lower scales and will strongly impact the material properties (mechanical, electrical, thermal, and chemical) at the macroscale. We summarize the recent developments in computational methods to simulate material behavior on multiple scales. We provide details on different techniques at various length scales: quantum, atomistic and coarse-grained models, and various continuum-based models. Furthermore, multiscale methods are broadly divided into: hierarchical, semiconcurrent, and concurrent techniques, and we review a number of modern hierarchical and semiconcurrent multiscale methods such as virtual atom cluster model, homogenization techniques, representative volume element-based methods and structural reconstruction based on Wang tiles. We also go through popular concurrent multiscale methods for fracture applications, such as extended bridging scale and extended bridging domain methods and discuss in detail adaptivity, coarse graining techniques, and their interactions. Computer implementation aspects of specific problems in the context of molecular as well as multiscale framework are also addressed for two- and three-dimensional crack growth problems. The chapter ends with conclusions and future prospects of multiscale methods.

This paper aims at a reduction of periodicity artefacts during a generation of random heterogeneous material models. The traditional concept of the Periodic Unit Cell is compared with a novel approach of the stochastic Wang tiling. Since modelled structures consist of hard circular/spherical particles in a matrix, the algorithm for placement of inclusions is based on the modified molecular dynamics. We introduce two types of Wang tile boundary conditions to decrease periodicity artefacts. Tested samples for 2D applications form sets of both monodisperse and polydisperse microstructures. The overall volume fractions of these samples are approximately 0.2, 0.4, and 0.6, respectively. The generated sets are analysed both visually and statistically via a two-point probability function. An extension of the stochastic Wang tiling enables to create 3D structures, as well. Therefore, artificial periodicity is also investigated on a 3D sample consisting of spherical particles of identical radii distributed in a continuous phase.

Tile-based self-assembly is a model of “algorithmic crystal growth” in which square “tiles” represent molecules that bind to each other via specific and variable-strength bonds on their four sides, driven by random mixing in solution but constrained by the local binding rules of the tile bonds. In the late 1990s, Erik Winfree introduced a discrete mathematical model of DNA tile assembly called the abstract Tile Assembly Mode. Winfree proved that the Tile Assembly Model is computationally universal, i.e., that any Turing machine can be encoded into a finite set of tile types whose self-assembly simulates that Turing machine. In this thesis, we investigate tile-based self-assembly systems that exhibit Turing universality, geometric universality and intrinsic universality. We first establish a novel characterization of the computably enumerable languages in terms of self-assembly—the proof of which is a novel proof of the Turing-universality of the Tile Assembly Model in which a particular Turing machine is simulated on all inputs in parallel in the two-dimensional discrete Euclidean plane. Then we prove that the multiple temperature tile assembly model (introduced by Aggarwal, Cheng, Goldwasser, Kao, and Schweller) exhibits a kind of “geometric universality” in the sense that there is a small (constant-size) universal tile set that can be programmed via deliberate changes in the system temperature to uniquely produce any finite shape. Just as other models of computation such as the Turing machine and cellular automaton are known to be “intrinsically universal,” (e.g., Turing machines can simulate other Turing machines, and cellular automata other cellular automata), we show that tile assembly systems satisfying a natural condition known as local consistency are able to simulate other locally consistent tile assembly systems. In other words, we exhibit a particular locally consistent tile assembly system that can simulate the behavior—as opposed to only the final result—of any other locally consistent tile assembly system. Finally, we consider the notion of universal fault-tolerance in algorithmic self-assembly with respect to the two-handed Tile Assembly Model, in which large aggregations of tiles may attach to each other, in contrast to the seeded Tile Assembly Model, in which tiles aggregate one at a time to a single specially-designated “seed” assembly. We introduce a new model of fault-tolerance in self-assembly: the fuzzy temperature model of faults having the following informal characterization: the system temperature is normally 2, but may drift down to 1, allowing unintended temperature-1 growth for an arbitrary period of time. Our main construction, which is a tile set capable of uniquely producing an n × n square with O(log n) unique tile types in the fuzzy temperature model, is not universal but presents novel technique that we hope will ultimately pave the way for a “universal fuzzy-fault-tolerant” tile assembly system in the future.

An algorithm generating morphology of 2D and 3D stochastic Wang tiles is presented in thiscontribution. The algorithm is based on the discrete element method (DEM) and is therefore applicableprimarily for matrix-based microstructures with separate inclusions with emphasis on producingmaximally random dense packings. An open-source free DEM code YADE was used for all the computations.The method is illustrated with a 2D exemplary realization of Wang tiling and comparisonagainst Periodic Unit Cell representation in terms of spatial statistics is provided.

Rendering textures in real-time environments is a key task in computer graphics. This paper presents a new parallel patch-based method which allows repeatable sampling without cache, and does not create visual repetitions. Interchangeable patches of arbitrary shape are prepared in a preprocessing step, such that patches may lie over the boundary of other patches in a repeating tile. This compresses the example texture into an infinite texture map with small memory requirements, suitable for GPU and ray-tracing applications. The quality of textures rendered with this method can be tuned in the offline preprocessing step, and they can then be rendered in times comparable to Wang tiles. Experimental results demonstrate combined benefits in speed, memory requirements, and quality of randomisation when compared to previous methods.

Tile Pasting P System is a computational model, based on the P System model, to generate two-dimensional tiling patterns using pasting rules at the edges of the regular polygons. Computational mechanism plays an important role in understanding the various complexities involved in the formation of complex patterns. In this paper we study the construction of non-periodic tiling patterns using corner tiles and aperiodic Wang tiles using the computational model Tile Pasting P System. We show that the Tile Pasting P System requires a minimum of four membranes to generate the non-periodic Wang tiling.

This investigation studies nonemptiness problems of plane edge coloring with three colors. In the edge coloring (or Wang tiles) of a plane, unit squares with colored edges that have one of p colors are arranged side by side such that the touching edges of the adjacent tiles have the same colors. Given a basic set B of Wang tiles, the nonemptiness problem is to determine whether or not @S(B) @A, where @S(B) is the set of all global patterns on Z^2 that can be constructed from the Wang tiles in B. Wang's conjecture is that for any B of Wang tiles, @S(B) @A if and only if P(B) @A, where P(B) is the set of all periodic patterns on Z^2 that can be generated by the tiles in B. When p>=5, Wang's conjecture is known to be wrong. When p=2, the conjecture is true. This study proves that when p=3, the conjecture is also true. If P(B) @A, then B has a subset B^' of minimal cycle generators such that P(B^') @A and P(B^'')=@A for B^''@?B^'. This study demonstrates that the set C(3) of all minimal cycle generators contains 787,605 members that can be classified into 2,906 equivalence classes. N(3) is the set of all maximal non-cycle generators: if B@?N(3), then P(B)=@A and P(B@?) @A for B@?@?B. Wang's conjecture is shown to be true by proving that B@?N(3) implies @S(B)=@A.

Chemical self-replicators are of considerable interest in the field of nanomanufacturing and as a model for evolution. We introduce the problem of self-replication of rectangular two-dimensional patterns in the practically motivated signal tile assembly model (STAM) (Padilla et al. Asynchronous signal passing for tile self-assembly: fuel efficient computation and efficient assembly of shapes, 2013). The STAM is based on the tile assembly model (TAM) which is a mathematical model of self-assembly in which DNA tile monomers may attach to other DNA tile monomers in a programmable way. More abstractly, four-sided tiles are assigned glue types to each edge, and self-assembly occurs when singleton tiles bind to a growing assembly, if the glue types match and the glue binding strength exceeds some threshold. The signal tile extension of the TAM allows signals to be propagated across assemblies to activate glues or break apart assemblies. Here, we construct a pattern replicator that replicates a two-dimensional input pattern over some fixed alphabet of size $$\phi $$? with $$O(\phi )$$O(?) tile types, $$O(\phi )$$O(?) unique glues, and a signal complexity of $$O(1)$$O(1). Furthermore, we show that this replication system displays exponential growth in $$n$$n, the number of replicates of the initial patterned assembly.

Patterned self-assembly is a process whereby coloured tiles self-assemble to build a rectangular coloured pattern. We propose self-assembly (SA) hypergraph automata as an automata-theoretic model for patterned self-assembly. We investigate the computational power of SA-hypergraph automata and show that for every recognizable picture language, there exists an SA-hypergraph automaton that accepts this language. Conversely, we prove that for any restricted SA-hypergraph automaton, there exists a Wang Tile System, a model for recognizable picture languages, that accepts the same language. The advantage of SA-hypergraph automata over Wang automata, acceptors for the class of recognizable picture languages, is that they do not rely on an a priori defined scanning strategy, Comment: 25 pages

We investigate the relation between Combinatory Logic and Wang Tiles with the aim of studying Combinators as a programming language for Self-Assembly and DNA computing. We introduce a subset of Combinatory Logic, SKI#, which is Turing Complete, includes simply Typed Combinatory Logic and contains only combinators whose computations require finitely many different redexes. Then, we define a language of Tiles, SKI-Tile, for the representation and the computation of the terms of SKI# in Self-Assembly. Moreover, we introduce a program development methodology that given any computable function, expressed in SKI#, provides a finite set of Tiles that self-assemble to return the computations of the function applications. Finally, the methodology is applied to the derivation of a SKI-Tile program that self-assemble to compute the factorial function.

The present study is on the concept of modeling of heterogeneous materials by means of Wang tilings. The central idea is to store a microstructural information within a finite set of Wang Tiles, which allow for reconstructing heterogeneity patterns of random media in planar domains of arbitrary sizes. The particular objective of presented work is our automatic tile set designer in conjunction with stochastic tiling synthesis algorithm. The proposed methodology is demonstrated on different examples. The proximity of synthesized microstructures to reference media is explored by statistical descriptors and discussed in terms of parasitic spatial orientation orders that may occur.

We exhibit a weakly aperiodic tile set for Baumslag-Solitar groups, and prove that the domino problem is undecidable on these groups. A consequence of our construction is the existence of an arecursive tile set on Baumslag-Solitar groups., Comment: In Proceedings MCU 2013, arXiv:1309.1043

We first give an introduction to the field of tile-based self-assembly, focusing primarily on theoretical models and their algorithmic nature. We start with a description of Winfree’s abstract Tile Assembly Model (aTAM) and survey a series of results in that model, discussing topics such as the shapes which can be built and the computations which can be performed, among many others. Next, we introduce the more experimentally realistic kinetic Tile Assembly Model (kTAM) and provide an overview of kTAM results, focusing especially on the kTAM’s ability to model errors and several results targeted at preventing and correcting errors. We then describe the 2-Handed Assembly Model (2HAM), which allows entire assemblies to combine with each other in pairs (as opposed to the restriction of single-tile addition in the aTAM and kTAM) and doesn’t require a specified seed. We give overviews of a series of 2HAM results, which tend to make use of geometric techniques not applicable in the aTAM. Finally, we discuss and define a wide array of more recently developed models and discuss their various tradeoffs in comparison to the previous models and to each other.

In this article, we propose the rendering framework for painting-like image generation and general system architecture for mobile device. Especially, we focused on a color division method for generating neo-impressionist images. The French painter, George Seurat, introduced pointillism under the theory that the individual pigments of colors on the canvas are reconstructed on the human retina. Pointillism is a painting technique in which many small brush strokes are combined to form a picture and determines the color of brush strokes based on the optical mixing of juxtaposed colors. In order to express countless separate dots, we form hierarchical points using Wang Tiles contained points. Also palette will be constructed using neo-impressionist colors. Based on this palette, we propose color division algorithm that distributes hierarchical point's color to pointillist colors using probability function. Finally, hierarchical points set that applied proposed color division rule is converted into brush strokes that possesses properties such as shape and direction. This rendering algorithm is performed in our proposed system. Our scheme is able to produce a painting with artistic style and be applied to the various platform having the different computing performance and display resolution. This system also can be extended to various imaging devices (IPTV, camera, smart phone, digital photo frame and so on).

In a previous work we have reported on the evolutionary design optimisation of self-assembling Wang tiles capable of arranging themselves together into a target structure. Apart from the significant findings on how self-assembly is achieved, nothing has been yet said about the efficiency by which individuals were evolved. Specially in light that the mapping from genotype to phenotype and from this to fitness is clearly a complex, stochastic and non-linear relationship. One of the most common procedures would suggest running many experiments for different configurations followed by a fitness comparison, which is not only time-consuming but also inaccurate for such intricate mappings. In this paper we aim to report on a complementary dual assessment protocol to analyse whether our genetic algorithm, using morphological image analyses as fitness function, is an effective methodology. Thus, we present here fitness distance correlation to measure how effectively the fitness of an individual correlates to its genotypic distance to a known optimum, and introduce clustering as a mechanism to verify how the objective function can effectively differentiate between dissimilar phenotypes and classify similar ones for the purpose of selection.

Self-assembly is fundamental to both biological processes and nanoscience. Key features of self-assembly are its probabilistic nature and local programmability. These features can be leveraged to design better self-assembled systems. The conventional tile assembly model (TAM) developed by Winfree using Wang tiles is a powerful, Turing-universal theoretical framework which models varied self-assembly processes. A particular challenge in DNA nanoscience is to form linear assemblies or rulers of a specified length using the smallest possible tile set, where any tile type may appear more than once in the assembly. The tile complexity of a linear assembly is the cardinality of the tile set that produces it. These rulers can then be used as components for construction of other complex structures. While square assemblies have been extensively studied, many questions remain about fixed length linear assemblies, which are more basic constructs yet fundamental building blocks for molecular architectures. In this wo...

A set of natural numbers tiles the plane if a square-tiling of the plane exists using exactly one square of sidelength n for every n in the set. From Ref. 8 we know that ℕ itself tiles the plane. From that and Ref. 9 we know that the set of even numbers tiles the plane while the set of odd numbers doesn't. In this paper we explore the nature of this property. We show, for example, that neither tiling nor non-tiling is preserved by superset. We show that a set with one or three odd numbers may tile the plane—but a set with two odd numbers can't. We find examples of both tiling and non-tiling sets that can be partitioned into tiling sets, non-tiling sets or a combination. We show that any set growing faster than the Fibonacci numbers cannot tile the plane.

Wang tiles are unit-size squares with coloured edges. In this paper, we approach one aspect of the study of tiling computability: the quest for a universal tile set. Using a complex construction, based on Robinson's classical construction and its different modifications, we build a tile set (pronounced ayin) that almost always simulates any tile set. By way of Banach–Mazur games on tilings topological spaces, we prove that the set of -tilings that do not satisfy the universality condition is meagre in the set of -tilings.

Self-assembly is the process by which objects aggregate independently and form complex structures. One of the theoretical frameworks in which the process of self-assembly can be embedded and formally studied is that of tile systems. A Wang tile is a square unit, with glues on its edges, attaching to other tiles which have matching glues, and forming larger and larger structures. In this paper we concentrate over two basic, but essential, self-assembling structures done by Wang tiles. The first one, called ribbon, is a non-self-crossing wire-like structure, in which successive tiles are adjacent along an edge, and where tiles are glued to their predecessor and successor by use of matching glues. The second one, called zipper, is a similar contiguous structure, only that here, all touching tiles must have matching glues on their abutting edges, independently of their position in the structure. In case of Wang tiles, it has been shown that these two structures are equivalent. Here we generalize this result for the case when the tiles have eight glues, four on their edges and four on their corners. Thus we show that an eight neighborhood dependency, namely the Moore neighborhood, can be simulated by a quasi-linear dependency.