On Cellular Automata rules of molecular arrays

Cellular Automata (CA) have long attracted interest as abstract computation models, but only in the last few years have serious attempts started to implement them in terms of molecules. Such nano-technological innovations promise very cost-effective fabrication because of the regular structure of CA, which allows assembly through molecular self-organization. The small sizes of molecules combined with their availability in Avogadro-scale numbers promises a huge computational power, in which the massive parallelism inherent in CA can be effectively exploited. This paper discusses the molecular CA in (Bandyopadhyay et?al., Nature Physics 2010) and shows novel features that have never been proposed in conventional CA models. The interaction rules in the molecular CA are found to be of a mixed variety, ranging from conventional direct-neighborhood type of rules to rules with long-distance interactions between cells. The probabilities according to which rules are applied in the molecular CA are dynamically influenced by the patterns on the cellular space. This results in extremely rich behavior, as compared to conventional models, which has the potential to be utilized for efficient configuration of patterns on the cellular space.     

On the undecidability of splicing systems

The notion of splicing system has been used to abstract the process of DNA digestion by restriction enzymes and subsequent religation. A splicing system language is the formal language of all DNA strings producible by such a process. The membership problem is to devise an algorithm (if possible) to answer the question of whether or not a given DNA string belongs to a splicing system language given by initial strings and enzymes.

In this paper the concept of a sequential splicing system is introduced. A sequential splicing system differs from a splicing system in that the latter allows arbitrarily many copies of any string in the initial set whereas the sequential splicing system may restrict the initial number of copies of some strings. The main result is that there exist sequential splicing systems with recursively unsolvable membership problem. The technique of the proof is to embed Turing machine computations in the languages.     

Computations on Nondeterministic Cellular Automata

This work concerns the trade-offs between the dimension and the time and space complexity of computations on nondeterministic cellular automata. We assume that the space complexity is the diameter of area in space involved in computation. It is proved that (1) every nondeterministic cellular automata (NCA) of dimensionr, computing a predicatePwith time complexityT(n) and space complexityS(n) can be simulated byr-dimensional NCA with time and space complexityO(T^1/(r+1)S^r/(r+1)) and byr+1 dimensional NCA with time and space complexityO(T^1/2+S), whereTandSare functions constructible in time, (2) for any predicatePand integerr>1 if is a fastestr-dimensional NCA computingPwith time complexityT(n) and space complexityS(n), thenT=O(S), and (3) ifT_{r, P}is the time complexity of a fastestr-dimensional NCA computing predicatePthenT_r+1,P=O((T_{r, P})^1−r/(r+1)2),T_r+1,P=O((T_{r, P})^1+2/r).Similar problems for deterministic cellular automata (CA) are discussed.     

元胞自动机可逆性研究

元胞自动机是对复杂适应系统建模的重要理论工具。可逆性是元胞自动机的一个重要属性,是模拟物理可逆空间的必要条件。本文介绍元胞自动机的基本概念、可逆性和可计算性,并介绍一维可逆元胞自动机可计算的证明思路。     

利用广义细胞自动机实现的智能数据聚类

现有的数据聚类方法仍存在着各种不足,聚类速度和结果的质量不能满足大型、高维数据库上的聚类需求。本文提出了一种新的基于广义细胞自动机的数据聚类算法,利用细胞自动机的自组织能力对数据进行聚类分析。聚类结果的质量不受聚类大小和聚类形状的影响,可以通过随机抽样应用于大数据集。文章在细胞结构及细胞动力学规则中引入了细胞核的概念,让细胞自动机利用自身的演化找出数据中的聚类信息。文章通过分析证明了本文方法的有效性,并通过模拟软件对算法性能进行了详细的实验,证明了算法的实用性和高效性。     

细胞自动机置换群加密技术研究

1.引言信息技术的发展对信息安全提出了更高的要求,并使得作为信息安全核心的加密技术及其实现变得越来越复杂。所以,人们开始探索简化加密系统实现的新方法,以满足现代信息技术发展对全方位多层次信息安全的要求。1948年,Von Neumann在研究具有自组织特性的系统时引入了细胞自动机的概念,后经S.Wolfram对其结构进行简化,从而极大地推动了细胞自动机理论及其应用的发展。细胞自动机具有组成单元的简单性、单元之间作用的局部性和信息处理的高度     

Asynchronous Mappings and Asynchronous Cellular Automata

The aim of this paper is the study of asynchronous automata, a special kind of automata which encode the independency relation between actions and which enable their concurrent execution. These automata, introduced by Zielonka (RAIRO Inform. Theor. Appl.21, 99-135 (1987)), constitute a natural extension of finite automata to the case of asynchronous parallelism. Their behaviour is described by trace languages, subsets of partially commutative monoids. The main result concerning this class of automata states that they accept exactly all recognizable trace languages. In this paper we give new improved constructions of asynchronous automata. In the final part of the paper we present a distributed system of messages with bounded time-stamps based on asynchronous automata.     

Hierarchical Cellular Automata for Visual Saliency

Saliency detection, finding the most important parts of an image, has become increasingly popular in computer vision. In this paper, we introduce Hierarchical Cellular Automata (HCA)—a temporally evolving model to intelligently detect salient objects. HCA consists of two main components: Single-layer Cellular Automata (SCA) and Cuboid Cellular Automata (CCA). As an unsupervised propagation mechanism, Single-layer Cellular Automata can exploit the intrinsic relevance of similar regions through interactions with neighbors. Low-level image features as well as high-level semantic information extracted from deep neural networks are incorporated into the SCA to measure the correlation between different image patches. With these hierarchical deep features, an impact factor matrix and a coherence matrix are constructed to balance the influences on each cell’s next state. The saliency values of all cells are iteratively updated according to a well-defined update rule. Furthermore, we propose CCA to integrate multiple saliency maps generated by SCA at different scales in a Bayesian framework. Therefore, single-layer propagation and multi-scale integration are jointly modeled in our unified HCA. Surprisingly, we find that the SCA can improve all existing methods that we applied it to, resulting in a similar precision level regardless of the original results. The CCA can act as an efficient pixel-wise aggregation algorithm that can integrate state-of-the-art methods, resulting in even better results. Extensive experiments on four challenging datasets demonstrate that the proposed algorithm outperforms state-of-the-art conventional methods and is competitive with deep learning based approaches.     

基于多耦合元胞自动机的加密算法

提出了耦合系数的概念,构造了一个新的耦合元胞自动机模型,并分析了耦合系数对耦合元胞自动机时空演化的影响。针对已有的单耦合元胞自动机加密系统中存在的不足,提出了基于多耦合元胞自动机的加密算法,该算法将多个元胞进行耦合,增强了两个元胞自动机之间的作用,扩大了相互影响的范围,使得误差扩散更为快速。仿真结果表明,该算法具有更为理想的扩散和扰乱特性,可抵抗蛮力攻击和差分分析攻击。     

技术创新扩散的元胞自动机仿真

首先通过对Bass模型进行参数估计,建立了基于元胞自动机的技术创新扩散模型,然后基于仿真软件Agentsheets设计和实现了仿真,最后以中国互联网络技术扩散为对象进行了实证研究,并将CA模型、Bass模型和实际数据进行了对比分析,对未来的网民数扩散的趋势进行了预测。该元胞自动机模型将网民数扩散的过程直观展示出来,仿真结果符合实际情况。     

薄膜生长的元胞自动机模型

在一定条件下,单个原子或原子团簇在液体基底表面无规律扩散和凝聚,并形成具有分形结构的分枝状凝聚体,形成此类凝聚体所需的时间非常短(约1—10s),直接观察原子或原子团簇在液体表面的成核、扩散及凝聚过程十分困难。元胞自动机是研究复杂体系的一种理想化模型,特别适合那些难以用数学定量描述的复杂动态体系实施计算机模拟。针对在液体基底表面的金属原子会凝聚形成具有特殊结构的分形凝聚体这一实验结果,建立了团簇一团簇凝聚的元胞自动机模型,对此类液体基底表面的金属原子分枝状凝聚体的生长过程进行了计算机模拟。模拟结果表明,凝聚体的分形维数和回旋半径都与实验结果相一致,为研究薄膜生长机理提供了一种新的方法。     

基于元胞自动机模型的礼堂人群疏散仿真

为了消除礼堂的安全隐患,制定行之有效的应急预案,有必要对礼堂人群疏散运动进行研究,掌握礼堂人群疏散的一般特点和规律。采用基于二维元胞自动机模型对某高校礼堂发生人群疏散运动进行仿真,找出影响礼堂人群疏散效率的关键因素,为高校礼堂设计提供支持;为高校礼堂制定突发事件应急预案提供参考。     

细胞自动机反向迭代加密技术研究

细胞自动机固有的组成单元的简单性、单元之间作用的局部性和信息处理的高度并行性 ,并表现出复杂的全局特性等特点使得细胞自动机尤其适合于密码学中的应用 .该文简述了细胞自动机的基本概念 ,研究了基于细胞自动机反向迭代的输出序列熵最大化加密技术 ,并对系统保密性进行了分析 .     

利用细胞自动机模型约减最近邻分类规则

目前常见的最近邻分类规则约减算法,只注重约减后分类器的分类精度和被约减的规则数量,而不注重约减效率和约减后分类器的泛化能力。针对该问题,提出了一种细胞自动机(cellular automata,CA)基础上的最近邻分类规则约减方法。该方法只保留不同类边界上的样本点,约减规则的数量可以由细胞自动机网格的粒度动态调节。其优势在于:在给定的大数据集前提下,可以利用较少的运行时间来约减给定的规则样本;可以利用积累或迭代的方式来分步获得原给定样本集的一致性子集。采用13个不同的数据集进行仿真实验,结果显示该算法简单、有效,较好地解决了大样本集的约减问题。     

On the undecidability of the equivalence of second-order tuple generating dependencies

Second-order tuple generating dependencies (SO tgds) were introduced by Fagin et al. to capture the composition of simple schema mappings. Testing the equivalence of SO tgds would be important for applications like model management and mapping optimization. However, we prove the undecidability of the logical equivalence of SO tgds. Moreover, under weak additional assumptions, we also show the undecidability of a relaxed notion of equivalence between two SO tgds, namely the so-called conjunctive query equivalence.     

对称耦合式触发细胞自动机在加密中的应用

提出一种基于一维触发细胞自动机的数据加密算法.待加密的数据块被分成两个等长的子块在两个触发细胞自动机上并行加密.细胞自动机之间采用对称耦合结构,每个细胞自动机迭代时采用的反转规则不仅依赖于其自身的状态,也依赖于与其耦合的细胞自动机以及密钥流的状态.这种结构降低了硬件的实现代价并实现了密钥分存,确保只有在同时获得一对密文时才能正确解密,而且两个子数据块并行加密提高了加密效率.触发细胞自动机的反转规则由子密钥流和数据本身共同决定.密钥空间,即反转规则表,随着细胞自动机邻居半径增大呈指数增长,所以可以根据不同的安全性要求,通过增加细胞自动机的邻居半径来实现.     

Stochastic Cellular Automata Solutions to the Density Classification Problem

In the density classification problem, a binary cellular automaton (CA) should decide whether an initial configuration contains more 0s or more 1s. The answer is given when all cells of the CA agree on a given state. This problem is known for having no exact solution in the case of binary deterministic one-dimensional CA. We investigate how randomness in CA may help us solve the problem. We analyse the behaviour of stochastic CA rules that perform the density classification task. We show that describing stochastic rules as a “blend” of deterministic rules allows us to derive quantitative results on the classification time and the classification time of previously studied rules. We introduce a new rule whose effect is to spread defects and to wash them out. This stochastic rule solves the problem with an arbitrary precision, that is, its quality of classification can be made arbitrarily high, though at the price of an increase of the convergence time. We experimentally demonstrate that this rule exhibits good scaling properties and that it attains qualities of classification never reached so far.