复合元胞自动机系统反向迭代加密技术研究

提出了元胞自动机的交叉复合在序列R下随机复合的思想,分析了复合元胞自动机系统的密码学特性,利用元胞自动机反向迭代加密技术,构造了两个基于复合元胞自动机的密码系统.新的复合元胞自动机密码系统很好地解决了单一元胞自动机密码系统中存在的误差单向扩散的问题,并且能够以较小的规则半径获得大密钥空间.计算机仿真结果表明,复合元胞自动机密码系统具有良好的扰乱和扩散性能,能够有效地抵抗蛮力攻击和差分分析. 关键词： 离散动力系统 复合元胞自动机 反向迭代 分组密码     

Continuity of Information Transport in Surjective Cellular Automata

We introduce a local version of the Shannon entropy in order to describe information transport in spatially extended dynamical systems, and to explore to what extent information can be viewed as a local quantity. Using an appropriately defined information current, this quantity is shown to obey a local conservation law in the case of one-dimensional reversible cellular automata with arbitrary initial measures. The result is also shown to apply to one-dimensional surjective cellular automata in the case of shift-invariant measures. Bounds on the information flow are also shown.     

Self-organisation in Cellular Automata with Coalescent Particles: Qualitative and Quantitative Approaches

This article introduces new tools to study self-organisation in a family of simple cellular automata which contain some particle-like objects with good collision properties (coalescence) in their time evolution. We draw an initial configuration at random according to some initial shift-ergodic measure, and use the limit measure to describe the asymptotic behaviour of the automata. We first take a qualitative approach, i.e. we obtain information on the limit measure(s). We prove that only particles moving in one particular direction can persist asymptotically. This provides some previously unknown information on the limit measures of various deterministic and probabilistic cellular automata: 3 and 4-cyclic cellular automata [introduced by Fisch (J Theor Probab 3(2):311–338, 1990; Phys D 45(1–3):19–25, 1990)], one-sided captive cellular automata [introduced by Theyssier (Captive Cellular Automata, 2004)], the majority-traffic cellular automaton, a self stabilisation process towards a discrete line [introduced by Regnault and Rémila (in: Mathematical Foundations of Computer Science 2015—40th International Symposium, MFCS 2015, Milan, Italy, Proceedings, Part I, 2015)]. In a second time we restrict our study to a subclass, the gliders cellular automata. For this class we show quantitative results, consisting in the asymptotic law of some parameters: the entry times [generalising K ?rka et al. (in: Proceedings of AUTOMATA, 2011)], the density of particles and the rate of convergence to the limit measure.     

Similar impact of topological and dynamic noise on complex patterns

Shortcuts in a regular architecture affect the information transport through the system due to the severe decrease in average path length. A fundamental new perspective in terms of pattern formation is the destabilizing effect of topological perturbations by processing distant uncorrelated information, similarly to stochastic noise. We study the functional coincidence of rewiring and noisy communication on patterns of binary cellular automata.     

Cellular automata for nanometer-scale computation

Cellular automata have recently been proposed as an architecture for dense, locally-interacting arrays of submicron devices. However, because conventional von Neumann cellular automata do not correctly reflect the long-range behavior of typical inter-device interactions, they do not provide a suitable theoretical model for the proposed device arrays. In this paper we define replica cellular automata, a class of cellular automata that can be generated from lattice-gas cellular automata. We show that for inter-device interactions that have a well-defined screening length D, replica cellular automata provide a suitable formal model. As an example of their applicability, we exhibit a computation-universal cellular automata architecture in which the cells consist of charge-transfer quantum dot devices.     

The dynamics of defect ensembles in one-dimensional cellular automata

We investigate the dynamics of ensembles of diffusive defects in one-dimensional deterministic cellular automata. The work builds on earlier results on individual random walks in cellular automata. Here we give a natural condition guaranteeing diffusive behavior also in the presence of other defects. Simple branching and birth mechanisms are introduced and prototype classes of cellular automata exhibiting weakly interacting walks capable of annihilation and coalescence are studied. Their equilibrium behavior is also characterized. The design principles of cellular automata with desired diffusive interaction properties become transparent from this analysis.     

一种基于误差快速扩散元胞自动机的加密技术

构造了一个具有较大密钥空间的新型一维元胞自动机. 在该元胞自动机中,密钥为采用移位映射的伪随机序列及受控扰动项,避免了数据膨胀,元胞自动机具有随机性触发规则. 该元胞自动机一次处理信息量大,避免了复杂的计算过程. 所生成的流密码在理论上被证明了具有理想的随机性与雪崩效应,误差扩散速度快. 实证分析研究表明,流密码不仅在全局上、而且在局部上都具有良好的随机性能,通过测试长度为24000的流密码在400次迭代产生的数据表明,经χ²检验,在显著性水平为5%时,频数检验通过率超 关键词： 保密通信 元胞自动机 伪随机序列     

Outer-totalistic cellular automata on graphs

We present an intuitive formalism for implementing cellular automata on arbitrary topologies. By that means, we identify a symmetry operation in the class of elementary cellular automata. Moreover, we determine the subset of topologically sensitive elementary cellular automata and find that the overall number of complex patterns decreases under increasing neighborhood size in regular graphs. As exemplary applications, we apply the formalism to complex networks and compare the potential of scale-free graphs and metabolic networks to generate complex dynamics.     

A geometrical interpretation of the chaotic state of inhomogeneous deterministic cellular automata

We propose a geometrical interpretation of the chaotic state of inhomogeneous cellular automata. From the rules of the cellular automaton we construct a network. The percolating phase of this network coincides with the chaotic phase of the cellular automaton. We also report numerical tests of these ideas on several cellular automata.     

Universally programmable quantum cellular automaton

We discuss the role of classical control in the context of reversible quantum cellular automata. Employing the structure theorem for quantum cellular automata, we give a general construction scheme to turn an arbitrary cellular automaton with external classical control into an autonomous one, thereby proving the computational equivalence of these two models. We use this technique to construct a universally programmable cellular automaton on a one-dimensional lattice with single cell dimension 12.     

Algebraic properties of cellular automata

Cellular automata are discrete dynamical systems, of simple construction but complex and varied behaviour. Algebraic techniques are used to give an extensive analysis of the global properties of a class of finite cellular automata. The complete structure of state transition diagrams is derived in terms of algebraic and number theoretical quantities. The systems are usually irreversible, and are found to evolve through transients to attractors consisting of cycles sometimes containing a large number of configurations.Address from January 1983     

基于压缩表示的离子刻蚀仿真三维表面演化方法

为了研究表面演化过程的机理, 提出了一种基于压缩表示的三维表面演化方法来模拟等离子体刻蚀工艺,并着重探讨了对离子刻蚀的仿真. 为了解决三维元胞自动机内存需求量大的问题, 该方法将二维数组和动态存储方式相结合, 既实现元胞信息的无损压缩存储, 又保持三维元胞间的空间相关性. 实验结果也表明该方法不仅节省了大量内存, 而且在高分辨率条件下查找离子初始碰撞的表面元胞效率较高, 满足高分辨率仿真的要求. 将该方法应用于实现刻蚀工艺三维表面仿真中, 模拟结果与实验结果对比验证了该方法的有效性. 关键词： 等离子体刻蚀 元胞自动机 表面演化方法 高分辨率仿真     

Quantifying self-organization with optimal predictors

Despite broad interest in self-organizing systems, there are few quantitative, experimentally applicable criteria for self-organization. The existing criteria all give counter-intuitive results for important cases. In this Letter, we propose a new criterion, namely, an internally generated increase in the statistical complexity, the amount of information required for optimal prediction of the system's dynamics. We precisely define this complexity for spatially extended dynamical systems, using the probabilistic ideas of mutual information and minimal sufficient statistics. This leads to a general method for predicting such systems and a simple algorithm for estimating statistical complexity. The results of applying this algorithm to a class of models of excitable media (cyclic cellular automata) strongly support our proposal.     

Renormalization of Cellular Automata and Self-Similarity

We study self-similarity in one-dimensional probabilistic cellular automata (PCA) using the renormalization technique. We introduce a general framework for algebraic construction of renormalization groups (RG) on cellular automata and apply it to exhaustively search the rule space for automata displaying dynamic criticality.     

Two-dimensional cellular automata

A largely phenomenological study of two-dimensional cellular automata is reported. Qualitative classes of behavior similar to those in one-dimensional cellular automata are found. Growth from simple seeds in two-dimensiona! cellular automata can produce patterns with complicated boundaries, characterized by a variety of growth dimensions. Evolution from disordered states can give domains with boundaries that execute effectively continuous motions. Some global properties of cellular automata can be described by entropies and Lyapunov exponents. Others are undecidable.This work was supported in part by the U.S. Office of Naval Research under Contract No. N00014-80-C-0657.     

基于元胞自动机的复杂信息系统安全风险传播研究

基于元胞自动机建立复杂信息系统安全风险传播模型, 研究复杂信息系统安全风险在最近邻耦合网络、 随机网络,　Watts-Strogatz 小世界网络和Barabasi-Albert无标度网络 四种网络拓扑下的传播问题. 通过研究安全风险传播模型在四种网络拓扑下安全风险的传播阈值, 与现有的传播阈值研究成果进行比较, 验证模型的正确性, 并分析验证网络拓扑结构中度分布的异质化程度越高传播阈值越小的结论. 通过对安全风险的传播演化趋势进行研究, 分析验证网络度分布的异质化程度越高、安全风险影响范围越小、传播速度越快的结论, 并指出度分布的异质化程度越高、模型后期的免疫机制对控制安全风险传播的效果越缓慢. 通过对安全风险在传播最早期就趋于消亡的情况进行研究, 分析得出安全风险在传播之初就趋于消亡的消亡率与传播率之间呈现近似负指数的关系, 并且初期的感染源越多安全风险的消亡率越低. 分析了影响复杂信息系统安全风险传播的关键要素, 对复杂信息系统中安全风险传播的控制具有指导作用. 关键词： 复杂信息系统 复杂网络 安全风险传播 元胞自动机     

Stair evacuation simulation based on cellular automata considering evacuees' walk preferences

As a physical model,the cellular automata(CA) model is widely used in many areas,such as stair evacuation.However,existing CA models do not consider evacuees' walk preferences nor psychological status,and the structure of the basic model is unapplicable for the stair structure.This paper is to improve the stair evacuation simulation by addressing these issues,and a new cellular automata model is established.Several evacuees' walk preference and how evacuee's psychology influences their behaviors are introduced into this model.Evacuees' speeds will be influenced by these features.To validate this simulation,two fire drills held in two high-rise buildings are video-recorded.It is found that the simulation results are similar to the fire drill results.The structure of this model is simple,and it is easy to further develop and utilize in different buildings with various kinds of occupants.     

A new cellular automata model of traffic flow with negative exponential weighted look-ahead potential

With the development of traffic systems, some issues such as traffic jams become more and more serious. Efficient traffic flow theory is needed to guide the overall controlling, organizing and management of traffic systems. On the basis of the cellular automata model and the traffic flow model with look-ahead potential, a new cellular automata traffic flow model with negative exponential weighted look-ahead potential is presented in this paper. By introducing the negative exponential weighting coefficient into the look-ahead potential and endowing the potential of vehicles closer to the driver with a greater coefficient, the modeling process is more suitable for the driver's random decision-making process which is based on the traffic environment that the driver is facing. The fundamental diagrams for different weighting parameters are obtained by using numerical simulations which show that the negative exponential weighting coefficient has an obvious effect on high density traffic flux. The complex high density non-linear traffic behavior is also reproduced by numerical simulations.