准移动闭塞系统的元胞自动机模型及列车延迟传播规律的研究

在NaSch模型的基础上，针对铁路交通的特点提出一种用于模拟准移动闭塞系统的元胞自动机模型.应用该模型模拟了准移动闭塞系统列车延迟传播的交通现象，分析了准移动闭塞系统中的轨道定位单元长度、发车时间间隔、初始延迟时间等因素对列车延迟传播的影响. 关键词： 元胞自动机 交通流 准移动闭塞     

Ergodic properties and thermodynamic behavior of elementary reversible cellular automata. I. Basic properties

This is the first part of a series devoted to the study of thermodynamic behavior of large dynamical systems with the use of a family of fully-discrete and conservative models named elementary reversible cellular automata (ERCAs). In this paper, basic properties such as conservation laws and phase space structure are investigated in preparation for the later studies. ERCAs are a family of one-dimensional reversible cellular automata having two Boolean variables on each site. Reflection and Boolean conjugation symmetries divide them into 88 equivalence classes. For each rule, additive conserved quantities written in a certain form are regarded as a kind of energy, if they exist. By the aid of the discreteness of the variables, every ERCA satisfies the Liouville theorem or the preservation of phase space volume. Thus, if an energy exists in the above sense, statistical mechanics of the model can formally be constructed. If a locally defined quantity is conserved, however, it prevents the realization of statistical mechanics. The existence of such a quantity is examined for each class and a number of rules which have at least one energy but no local conservation laws are selected as hopeful candidates for the realization of thermodynamic behavior. In addition, the phase space structure of ERCAs is analyzed by enumerating cycles exactly in the phase space for systems of comparatively small sizes. As a result, it is revealed that a finite ERCA is not ergodic, that is, a large number of orbits coexist on an energy surface. It is argued that this fact does not necessarily mean the failure of thermodynamic behavior on the basis of an analogy with the ergodic nature of infinite systems.     

交通灯控制下城市主干道双车道多速元胞自动机交通流模型研究

提出一个城市主干道双车道多速元胞自动机交通流模型，此模型采用开放性 边界条件，在考虑诸多实际因素影响情况下，研究了主干道中车站的设置、交通灯绿信比对 车流量和车流速度的影响.计算机模拟所得到的基本图（流量 速度图）能较好地反映在交 通灯控制下城市主干道交通流真实状况. 关键词： 元胞自动机模型 交通流 主干道     

A cellular automaton technique for modelling of a binary dendritic growth with convection

A two-dimensional model for the simulation of a binary dendritic growth with convection has been developed in order to investigate the effects of convection on dendritic morphologies. The model is based on a cellular automaton (CA) technique for the calculation of the evolution of solid/liquid (s/l) interface. The dynamics of the interface controlled by temperature, solute diffusion and Gibbs–Thomson effects, is coupled with the continuum model for energy, solute and momentum transfer with liquid convection. The solid fraction is calculated by a governing equation, instead of some approximate methods such as lever rule method [A. Jacot, M. Rappaz, Acta Mater. 50 (2002) 1909–1926.] or interface velocity method [L. Nastac, Acta Mater. 47 (1999) 4253; L. Beltran-Sanchez, D.M. Stefanescu, Mat. and Mat. Trans. A 26 (2003) 367.]. For the dendritic growth without convection, mesh independency of simulation results is achieved. The simulated steady-state tip velocity are compared with the predicted values of LGK theory [Lipton, M.E. Glicksmanm, W. Kurz, Metall. Trans. 18(A) (1987) 341.] as a function of melt undercooling, which shows good agreement. The growth of dendrite arms in a forced convection has been investigated. It was found that the dendritic growth in the upstream direction was amplified, due to larger solute gradient in the liquid ahead of the s/l interface caused by melt convection. In the isothermal environment, the calculated results under very fine mesh are in good agreement with the Oseen–Ivanstov solution for the concentration-driven growth in a forced flow.     

On a free group of transformations defined by an automaton

We prove that three automorphisms of the rooted binary tree defined by a certain 3-state automaton generate a free non-Abelian group of rank 3. Both authors are supported by the NSF grants DMS-0308985 and DMS-0456185. Yaroslav Vorobets is supported by a Clay Research Scholarship.     

Cardy's formula for some dependent percolation models

We prove Cardy's formula for rectangular crossing probabilities in dependent site percolation models that arise from a deterministic cellular automaton with a random initial state. The cellular automaton corresponds to the zero-temperature case of Domany's stochastic Ising ferromagnet on the hexagonal lattice  (with alternating updates of two sublattices) [7]; it may also be realized on the triangular lattice 𝕋 with flips when a site disagrees with six, five and sometimes four of its six neighbors. Received: 24 December 2001     

The kink of cellular automaton rule 18 performs a random walk

We give an exact characterization of the movement of a single kink in the elementary cellular automaton Rule 18. It is a random walk with independent increments as well as independent delay times. Its statistical parameters are computed to confirm the earlier simulation results by Grassberger.     

基于自动机技术的XML复杂数据类型验证

复杂数据类型验证是XML文档验证的主要内容,是检查XML文档结构是否符合模式规则的关键.根据Schema规范中复杂数据类型的描述和自动机理论,提出了一种称为模式自动机的数据结构,讨论了将XML复杂数据类型结构转换成模式自动机的方法,并设计了用来验证文档结构的算法.使用模式自动机验证算法可以全面地发现XML文档中的结构错误并准确地给出相应的错误信息,在实际应用中具有很高的效率.     

细胞自动机的演化与计算理论’

本文介绍一细胞自动机的基础原理，讨论了细胞自动演化位形序列与形式语言的等价性，并给出９０规则与１５０规则的正则语言集，则时还建立了Ｔｕｒｉｎｇ机仿真９０规则的程序并给出相应的状态转移图。     

一种改进的实时系统可达性分析算法

首先简介了时间自动机、时钟区域、区域等价、时钟带的概念.利用时钟带,可以将时间自动机的无穷状态空间转化为有穷.实时系统的绝大多数安全性和部分活性可以通过可达性分析算法来验证.然而,当系统时钟个数较多时,用DBM存储时钟带,会造成内存空间的很大耗费.该文提出了用邻接表存储时钟带,给出了改进的算法,并对算法的空间复杂度作了分析.实验表明,当时钟个数大于5时能节约很大的内存空间,从而在一定程度上缓解了状态爆炸.