Doubles and negatives are positive (in self-assembly)

In the abstract Tile Assembly Model (aTAM), the phenomenon of cooperation occurs when the attachment of a new tile to a growing assembly requires it to bind to more than one tile already in the assembly. Often referred to as “temperature-2” systems, those which employ cooperation are known to be quite powerful (i.e. they are computationally universal and can build an enormous variety of shapes and structures). Conversely, aTAM systems which do not enforce cooperative behavior, a.k.a. “temperature-1” systems, are conjectured to be relatively very weak, likely to be unable to perform complex computations or algorithmically direct the process of self-assembly. Nonetheless, a variety of models based on slight modifications to the aTAM have been developed in which temperature-1 systems are in fact capable of Turing universal computation through a restricted notion of cooperation. Despite that power, though, several of those models have previously been proven to be unable to perform or simulate the stronger form of cooperation exhibited by temperature-2 aTAM systems. In this paper, we first prove that another model in which temperature-1 systems are computationally universal, namely the restricted glue TAM (rgTAM) in which tiles are allowed to have edges which exhibit repulsive forces, is also unable to simulate the strongly cooperative behavior of the temperature-2 aTAM. We then show that by combining the properties of two such models, the Dupled Tile Assembly Model (DTAM) and the rgTAM into the DrgTAM, we derive a model which is actually more powerful at temperature-1 than the aTAM at temperature-2. Specifically, the DrgTAM, at temperature-1, can simulate any aTAM system of any temperature, and it also contains systems which cannot be simulated by any system in the aTAM.     

Hierarchical growth is necessary and (sometimes) sufficient to self-assemble discrete self-similar fractals

Natural Computing - In this paper, we prove that in the abstract Tile Assembly Model (aTAM), an accretion-based model which only allows for a single tile to attach to a growing assembly at each...     

Activatable tiles for compact robust programmable molecular assembly and other applications

Algorithmic DNA self-assembly is capable of forming complex patterns and shapes, that have been shown theoretically, and experimentally. Its experimental demonstrations, although improving over recent years, have been limited by significant assembly errors. Since 2003 there have been several designs of error-resilient tile sets but all of these existing error-resilient tile systems assumed directional growth of the tiling assembly. This is a very strong assumption because experiments show that tile self-assembly does not necessarily behave in such a fashion, since they may also grow in the reverse of the intended direction. The assumption of directional growth of the tiling assembly also underlies the growth model in theoretical assembly models such as the TAM. What is needed is a means for enforce this directionality constraint, which will allow us to reduce assembly errors. In this paper we describe a protection/deprotection strategy to strictly enforce the direction of tiling assembly growth so that the assembly process is robust against errors. Initially, we start with (1) a single “activated” tile with output pads that can bind with other tiles, along with (2) a set of “deactivated” tiles, meaning that the tile’s output pads are protected and cannot bind with other tiles. After other tiles bind to a “deactivated” tile’s input pads, the tile transitions to an active state and its output pads are exposed, allowing further growth. When these are activated in a desired order, we can enforce a directional assembly at the same scale as the original one. Such a system can be built with minimal modifications of existing DNA tile nanostructures. We propose a new type of tiles called activatable tiles and its role in compact proofreading. Activatable tiles can be thought of as a particular case of the more recent signal tile assembly model, where signals transmit binding/unbinding instructions across tiles on binding to one or more input sites. We describe abstract and kinetic models of activatable tile assembly and show that the error rate can be decreased significantly with respect to Winfree’s original kinetic tile assembly model without considerable decrease in assembly growth speed. We prove that an activatable tile set is an instance of a compact, error-resilient and self-healing tile-set. We describe a DNA design of activatable tiles and a mechanism of deprotection using DNA polymerization and strand displacement. We also perform detailed stepwise simulations using a DNA Tile simulator Xgrow, and show that the activatable tiles mechanism can reduce error rates in self assembly. We conclude with a brief discussion on some applications of activatable tiles beyond computational tiling, both as (1) a novel system for concentration of molecules, and (2) a catalyst in sequentially triggered chemical reactions.     

Capabilities and Limits of Compact Error Resilience Methods for Algorithmic Self-Assembly

Winfree’s pioneering work led the foundations in the area of error-reduction in algorithmic self-assembly (Winfree and Bekbolatov in DNA Based Computers 9, LNCS, vol. 2943, pp. 126–144, [2004]), but the construction resulted in increase of the size of assembly. Reif et al. (Nanotechnol. Sci. Comput. 79–103, [2006]) contributed further in this area with compact error-resilient schemes that maintained the original size of the assemblies, but required certain restrictions on the Boolean functions to be used in the algorithmic self-assembly. It is a critical challenge to improve these compact error resilient schemes to incorporate arbitrary Boolean functions, and to determine how far these prior results can be extended under different degrees of restrictions on the Boolean functions. In this work we present a considerably more complete theory of compact error-resilient schemes for algorithmic self-assembly in two and three dimensions. In our error model, ε is defined to be the probability that there is a mismatch between the neighboring sides of two juxtaposed tiles and they still stay together in the equilibrium. This probability is independent of any other match or mismatch and hence we term this probabilistic model as the independent error model. In our model all the error analysis is performed under the assumption of kinetic equilibrium. First we consider two-dimensional algorithmic self-assembly. We present an error correction scheme for reduction of errors from ε to ε ² for arbitrary Boolean functions in two dimensional algorithmic self-assembly. Then we characterize the class of Boolean functions for which the error can be reduced from ε to ε ³, and present an error correction scheme that achieves this reduction. Then we prove ultimate limits on certain classes of compact error resilient schemes: in particular we show that they can not provide reduction of errors from ε to ε ⁴ is for any Boolean functions. Further, we develop the first provable compact error resilience schemes for three dimensional tiling self-assemblies. We also extend the work of Winfree on self-healing in two-dimensional self-assembly (Winfree in Nanotechnol. Sci. Comput. 55–78, [2006]) to obtain a self-healing tile set for three-dimensional self-assembly.     

Implementation of self-healing function in ATM networks

This paper proposes an implementation scheme for the self-healing function in ATM (Asynchronous Transfer Mode) networks and assesses its performance in a developed experimental system. First, our proposed ATM self-healing scheme is described. This scheme realizes more rapid restoration of failed Virtual Paths than other self-healing algorithms, supports the node failure case, and minimizes the spare resources required. Next, an implementation scheme is proposed. We propose that the self-healing function can be implemented as a software process, and that OAM (Operation, Administration, and Maintenance) cells be utilized for fast message transmission. Next, results of a prototype system that we implemented on an ATM cross-connect system are discussed. The fundamental characteristics of restoration performance are measured using the experimental system. Based on these results, restoration characteristics of real world scale networks are estimated by computer simulations. The simulation results indicate that any-one link failure is completely restored within 2 seconds.     

Building a production planning process with an approach based on CIMOSA and workflow management systems

Nowadays, one of the major challenges for enterprises is to stay competitive in today's changing market environment. This can be supported by business process models which on one hand are consistent and adequate (requirement #1), and on the other hand can be enacted and operated in an easy, fast, straightforward and integrated way (requirement #2). The CIMOSA architecture provides the basis for business process modelling to fulfil both of the above requirements. It supports the creation of consistent process models and allows to identify almost all the information required for the development of a workflow model. These models can be implemented using one of the commercial workflow management systems. In this paper we present the methodology based on the CIMOSA architecture that we have developed to build a workflow model in ©Lotus Notes for the forecasting and production planning processes in a tiles manufacturing enterprise. The CIMOSA approach has also been used to design the necessary software applications for processing the information of the resulting workflow system.     

The effect of malformed tiles on tile assemblies within the kinetic tile assembly model

Many different constructions of proofreading tile sets have been proposed in the literature to reduce the effect of deviations from ideal behaviour of the dynamics of the molecular tile self-assembly process. In this paper, we consider the effect on the tile assembly process of a different kind of non-ideality, namely, imperfections in the tiles themselves. We assume a scenario in which some small proportion of the tiles in a tile set are “malformed”. We study, through simulations, the effect of such malformed tiles on the self-assembly process within the kinetic Tile Assembly Model (kTAM). Our simulation results show that some tile set constructions show greater error-resilience in the presence of malformed tiles than others. For example, the 2- and 3-way overlay compact proofreading tile sets of Reif et al. (DNA Computing 10, Lecture Notes in Computer Science, vol 3384. Springer, 2005) are able to handle malformed tiles quite well. On the other hand, the snaked proofreading tile set of Chen and Goel (DNA Computing 10, Lecture Notes in Computer Science, vol 3384. Springer, 2005) fails to form even moderately sized tile assemblies when malformed tiles are present. We show how the Chen–Goel construction may be modified to yield new snaked proofreading tile sets that are resilient not only to errors intrinsic to the assembly process, but also to errors caused by malformed tiles.     

A survey on self-healing systems: approaches and systems

Present large-scale information technology environments are complex, heterogeneous compositions often affected by unpredictable behavior and poor manageability. This fostered substantial research on designs and techniques that enhance these systems with an autonomous behavior. In this survey, we focus on the self-healing branch of the research and give an overview of the current existing approaches. The survey is introduced by an outline of the origins of self-healing. Based on the principles of autonomic computing and self-adapting system research, we identify self-healing systems’ fundamental principles. The extracted principles support our analysis of the collected approaches. In a final discussion, we summarize the approaches’ common and individual characteristics. A comprehensive tabular overview of the researched material concludes the survey.     

Achieving self-healing in service delivery software systems by means of case-based reasoning

Self-healing, i.e. the capability of a system to autonomously detect failures and recover from them, is a very attractive property that may enable large-scale software systems, aimed at delivering services on a 24/7 fashion, to meet their goals with little or no human intervention. Achieving self-healing requires the elicitation and maintenance of domain knowledge in the form of 〈service failure diagnosis, repair plan〉 patterns, a task which can be overwhelming. Case-Based Reasoning (CBR) is a lazy learning paradigm that largely reduces this kind of knowledge acquisition bottleneck. Moreover, the application of CBR for failure diagnosis and remediation in software systems appears to be very suitable, as in this domain most errors are re-occurrences of known problems. In this paper, we describe a CBR approach for providing large-scale, distributed software systems with self-healing capabilities, and demonstrate the practical applicability of our methodology by means of some experimental results on a real world application.     

Playware technology for physically activating play

We present and use the robotic building block concept to create playware. Playware is the use of intelligent technology to create the kinds of leisure activity we normally label play, i.e., intelligent hard- and software that aims at producing play and playful experiences among users. The technological concept of physical building blocks with processing, input, and output (including communication) is derived from embodied artificial intelligence that emphasizes the role of interplay between morphology and control. We exemplify the building block concept with the tangible tiles that we created as components for a new kind of playground on which children can experience immediate feedback on their motions. Hence, this kind of playground allows the implementation of games and plays that demand physical activity amongst the users, and thereby contribute as a new tool in the fight against obesity. The tangible tiles are homogenous building blocks, which gives assembly, substitution, and production advantages. However, we may also create a system of heterogeneous building blocks, e.g., by adding special-purpose tiles such as loud-speaker tiles. We performed tests with the tangible tiles placed at a school for 2 months' continuous use.     

Convergence rates of Markov chains for some self-assembly and non-saturated Ising models

Algorithms based on Markov chains are ubiquitous across scientific disciplines as they provide a method for extracting statistical information about large, complicated systems. For some self-assembly models, Markov chains can be used to predict both equilibrium and non-equilibrium dynamics. In fact, the efficiency of these self-assembly algorithms can be related to the rate at which simple chains converge to their stationary distribution. We give an overview of the theory of Markov chains and show how many natural chains, including some relevant in the context of self-assembly, undergo a phase transition as a parameter representing temperature is varied in the model. We illustrate this behavior for the non-saturated Ising model in which there are two types of tiles that prefer to be next to other tiles of the same type. Unlike the standard Ising model, we also allow empty spaces that are not occupied by either type of tile. We prove that for a local Markov chain that allows tiles to attach and detach from the lattice, the rate of convergence is fast at high temperature and slow at low temperature.     

Towards a neighborhood simplification of tile systems: From Moore to quasi-linear dependencies

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.     

DIG: Degree of inter-reference gap for a dynamic buffer cache management

The effectiveness of the buffer cache replacement is critical to the performance of I/O systems. In this paper, we propose a degree of inter-reference gap (DIG) based block replacement scheme. This scheme keeps the simplicity of the least recently used (LRU) scheme and does not depend on the detection of access regularities. The proposed scheme is based on the low inter-reference recency set (LIRS) scheme, which is currently known to be very effective. However, the proposed scheme employs several history information items whereas the LIRS scheme uses only one history information item. The overhead of the proposed scheme is almost negligible. To evaluate the performance of the proposed scheme, the comprehensive trace-driven computer simulation is used in general access patterns. Our simulation results show that the cache hit ratio (CHR) in the proposed scheme is improved as much as 65.3% (with an average of 26.6%) compared to the LRU for the same workloads, and up to 6% compared to the LIRS in multi3 trace.     

HNCP: A many-core microprocessor ASIC approach dedicated to embedded image processing applications

Highly regular many-core architectures tend to be more and more popular as they are suitable for inherently highly parallelizable applications such as most of the image and video processing domain. In this article, we present a novel architecture for many-core microprocessor ASIC dedicated to embedded video and image processing applications. We propose a flexible many-core approach with two architectures one implemented in CMOS 65 nm technology containing 16 open-source tiles and the other implemented in CMOS FD-SOI 28 nm technology containing 64 open-source tiles. Each tile of these architectures can choose its communication links depending on the most relevant overall parallelism scheme for a targeted application. Both chips are fully functional in simulation. The layouts are presented with frequency, area and power consumption results. Various case studies are presented to illustrate the proposed flexible many-core architectures and enable to focus on architecture exploration, instantiated scheme of parallelization and timing performance.     

Efficient, self-contained handling of identity in peer-to-peer systems

Identification is an essential building block for many services in distributed information systems. The quality and purpose of identification may differ, but the basic underlying problem is always to bind a set of attributes to an identifier in a unique and deterministic way. Name/directory services, such as DNS, X.500, or UDDI, are a well-established concept to address this problem in distributed information systems. However, none of these services addresses the specific requirements of peer-to-peer systems with respect to dynamism, decentralization, and maintenance. We propose the implementation of directories using a structured peer-to-peer overlay network and apply this approach to support self-contained maintenance of routing tables with dynamic IP addresses in structured P2P systems. Thus, we keep routing tables intact without affecting the organization of the overlay networks, making it logically independent of the underlying network infrastructure. Even though the directory is self-referential, since it uses its own service to maintain itself, we show that it is robust due to a self-healing capability. For security, we apply a combination of PGP-like public key distribution and a quorum-based query scheme. We describe the algorithm as implemented in the P-Grid P2P lookup system (http:// www.p-grid.org/) and give a detailed analysis and simulation results demonstrating the efficiency and robustness of our approach.     

Parallel loop generation and scheduling

Loop tiling is an efficient loop transformation, mainly applied to detect coarse-grained parallelism in loops. It is a difficult task to apply n-dimensional non-rectangular tiles to generate parallel loops. This paper offers an efficient scheme to apply non-rectangular n-dimensional tiles in non-rectangular iteration spaces, to generate parallel loops. In order to exploit wavefront parallelism efficiently, all the tiles with equal sum of coordinates are assumed to reside on the same wavefront. Also, in order to assign parallelepiped tiles on each wavefront to different processors, an improved block scheduling strategy is offered in this paper.     

Interactive skills and individual differences in a word production task

In attempting to solve a wide variety of tasks, people naturally seek to modify their external environment such that the physical space in which they work is more amenable or ‘congenial’ to achieving a desired outcome. Attempts to determine the effectiveness of certain artifacts or spatial reorganizations in aiding reasoners solve problems must be relativised to the difficulty of the task and the cognitive abilities of the reasoners. These factors were examined using a simple word production task with letter tiles. Two sets of tiles that differed in terms of word production difficulty were selected. Participants were asked to produce as many words as they could within a finite time period for each letter set. In one group, participants were encouraged to rearrange or touch the tiles when producing words, and in the other group, participants could not interact with or point to the tiles. Participants were further split in a low and high verbal fluency group as a function of their score on the Thurstone word fluency test taken at the end of the experiment. In the high fluency group, letter rearrangement did not improve the participants’ ability to generate words. In contrast, in the low verbal fluency group, letter rearrangement significantly enhanced the ability to produce new words from both the hard and easy letter set. For these participants, the task was more taxing and the opportunity to restructure the letter set substantially elevated their performance. The advantages of a distributed cognition analysis of this and other reasoning tasks are discussed.     

Density‐enhanced perceptual mosaic on GPU

Image mosaic effects are wildly applied in print media, domestic decoration, and many image beautification applications. However, the current image mosaic methods are mostly based on fixed‐size image tiles, simple color adjustment, and irregular image segmentation, which are inaccurate and very time‐consuming. In this paper, we present a graphics processing unit‐accelerated perceptual mosaic using density tiles replacement and brightness lighting optimization, keeping original image structure details and providing more expressive visual effects. Automatic density replacement map segmentation and color‐based region tiles replacement are performed to facilitate the mosaic. Delicate brightness optimization and perceptual color correction are further applied to enhance expressive lighting effects. We also consider the salience perception of images and similarity correlation among neighboring tiles for our perceptual mosaic. The experimental results have shown the efficiency and high‐quality performance of our density‐enhanced perceptual mosaic on graphics processing unit. Copyright © 2016 John Wiley & Sons, Ltd.     

Impacts of sampling strategies in tournament selection for genetic programming

Tournament selection is one of the most commonly used parent selection schemes in genetic programming (GP). While it has a number of advantages over other selection schemes, it still has some issues that need to be thoroughly investigated. Two of the issues are associated with the sampling process from the population into the tournament. The first one is the so-called “multi-sampled” issue, where some individuals in the population are picked up (sampled) many times to form a tournament. The second one is the “not-sampled” issue, meaning that some individuals are never picked up when forming tournaments. In order to develop a more effective selection scheme for GP, it is necessary to understand the actual impacts of these issues in standard tournament selection. This paper investigates the behaviour of different sampling replacement strategies through mathematical modelling, simulations and empirical experiments. The results show that different sampling replacement strategies have little impact on selection pressure and cannot effectively tune the selection pressure in dynamic evolution. In order to conduct effective parent selection in GP, research focuses should be on developing automatic and dynamic selection pressure tuning methods instead of alternative sampling replacement strategies. Although GP is used in the empirical experiments, the findings revealed in this paper are expected to be applicable to other evolutionary algorithms.