基于元胞自动机的多车道机非混合道路交通流

车辆的行驶受到本车道以及邻近车道前后邻近车辆的影响,在城市交通中机非混合对车辆行走的影响尤为复杂。通过研究路段上机非混合通行交通流的本质特性,综合考虑非机动车对机动车换道规则及加减速规则的"摩擦"和"阻滞"干扰影响,建立描述路段混合通行道路交通流的元胞自动机(CA)模型,从不同的机非混合比例下道路交通流的流量、速度变化情况,流量与车辆到达率关系,交通流相位相变等方面仿真模拟混合交通流的机非干扰机理。     

A Parallel Implementation of Multiple Secret Image Sharing Based on Cellular Automata

Recently, a multisecret sharing scheme for secret color images among a set of users was proposed, which allows that each participant to share secret color images with the rest of participants in such way that all of them can recover all secret color images only if all participants pool their shares. In this work a parallel implementation of the cellular automata-based multisecret sharing scheme is proposed, in which the technology of CUDA （Compute Unified Device Architecture） is used in parallelization, taking advantage that each cell of cellular automata can be processed independently. The processing time of the proposed scheme is analyzed and it is proved that the proposed parallel algorithm using the CUDA structure is more than 12 times faster than the conventional sequential algorithm. This reduction of temporal complexity allows the practical use of the secret sharing scheme in many information security fields.     

Fault tolerance in cellular automata at high fault rates

A commonly used model for fault-tolerant computation is that of cellular automata. The essential difficulty of fault-tolerant computation is present in the special case of simply remembering a bit in the presence of faults, and that is the case we treat in this paper. We are concerned with the degree (the number of neighboring cells on which the state transition function depends) needed to achieve fault tolerance when the fault rate is high (nearly 1/2). We consider both the traditional transient fault model (where faults occur independently in time and space) and a recently introduced combined fault model which also includes manufacturing faults (which occur independently in space, but which affect cells for all time). We also consider both a purely probabilistic fault model (in which the states of cells are perturbed at exactly the fault rate) and an adversarial model (in which the occurrence of a fault gives control of the state to an omniscient adversary). We show that there are cellular automata that can tolerate a fault rate 1/2−ξ (with ξ>0) with degree O((1/ξ²)log(1/ξ)), even with adversarial combined faults. The simplest such automata are based on infinite regular trees, but our results also apply to other structures (such as hyperbolic tessellations) that contain infinite regular trees. We also obtain a lower bound of Ω(1/ξ²), even with only purely probabilistic transient faults.     

Interference automata

We propose a computing model, the Two-Way Optical Interference Automata (2OIA), that makes use of the phenomenon of optical interference. We introduce this model to investigate the increase in power, in terms of language recognition, of a classical Deterministic Finite Automaton (DFA) when endowed with the facility of interference. The question is in the spirit of Two-Way Finite Automata With Quantum and Classical States (2QCFA) [A. Ambainis, J. Watrous, Two-way finite automata with quantum and classical states, Theoret. Comput. Sci. 287 (1) (2002) 299–311] wherein the classical DFA is augmented with a quantum component of constant size. We test the power of 2OIA against the languages mentioned in the above paper. We give efficient 2OIA algorithms to recognize languages for which 2QCFA machines have been shown to exist, as well as languages whose status vis-a-vis 2QCFA has been posed as open questions. Having a DFA as a component, it trivially recognizes regular languages. We show that our model can recognize all languages recognized by 1-way deterministic blind counter automata. Finally we show the existence of a language that cannot be recognized by a 2OIA but which can be recognized by an O(n³)$O\left(n^3\right)$ space Turing machine.     

Reversible computing and cellular automata—A survey

Reversible computing is a paradigm where computing models are defined so that they reflect physical reversibility, one of the fundamental microscopic physical property of Nature. In this survey/tutorial paper, we discuss how computation can be carried out in a reversible system, how a universal reversible computer can be constructed by reversible logic elements, and how such logic elements are related to reversible physical phenomena. We shall see that, in reversible systems, computation can often be carried out in a very different manner from conventional (i.e., irreversible) computing systems, and even very simple reversible systems or logic elements have computation- or logical-universality. We discuss these problems based on reversible logic elements/circuits, reversible Turing machines, reversible cellular automata, and some other related models of reversible computing.     

Optimal infinite scheduling for multi-priced timed automata

This paper is concerned with the derivation of infinite schedules for timed automata that are in some sense optimal. To cover a wide class of optimality criteria we start out by introducing an extension of the (priced) timed automata model that includes both costs and rewards as separate modelling features. A precise definition is then given of what constitutes optimal infinite behaviours for this class of models. We subsequently show that the derivation of optimal non-terminating schedules for such double-priced timed automata is computable. This is done by a reduction of the problem to the determination of optimal mean-cycles in finite graphs with weighted edges. This reduction is obtained by introducing the so-called corner-point abstraction, a powerful abstraction technique of which we show that it preserves optimal schedules. This work has been mostly done while visiting CISS at Aalborg University in Denmark and has been supported by CISS and by ACI Cortos, a program of the French Ministry of Research.     

采用动态邻域扩展算法的非一致CA低功耗确定TPG

针对确定内建自测试向量发生器设计中常存在着对冗余向量依赖,导致测试应用时间增长,并产生额外的测试功耗等问题,提出一种新的低功耗确定测试向量发生器的综合算法.该向量发生器采用非一致细胞自动机的结构实现,利用基于模拟退火的动态邻域扩展算法寻找优化的细胞自动机的拓扑连接关系.对标准组合电路仿真实验的结果表明,所综合出的向量发生器可有效地产生给定的低功耗确定向量集,并且不影响原有的故障覆盖率和测试时间.     

基于无秩树自动机的信息抽取技术研究

针对目前基于网页结构的信息抽取方法的缺陷,提出了一种基于无秩树自动机的信息抽取技术,其核心思想是通过将结构化(半结构化)文档转换成无秩树,然后利用(k,l)-contextual树构造样本自动机,依据树自动机接收和拒绝状态来对网页进行数据的抽取.该方法充分利用结构,依托树自动机将传统的以单一结构途径的信息抽取方法与文法推理原则相结合,得到信息抽取规则.实验结果表明,该方法与同类抽取方法相比在准确率、召回率以及抽取所需时间上均有所提高.     

Active XML文档安全重写判定算法

研究了AXML文档安全重写判定问题,即判定给定AXML文档通过触发其包含的服务调用生成的文档集合是否能够全部重写为符合目标模式的文档实例.基于树自动机理论,定义了用于抽象AXML文档的树自动机--ATA机(AXML treeautomata),ATA机等价于给定AXML文档通过触发其包含的服务调用所能生成的文档集合.基于ATA机,提出一个AXML文档安全重写判定算法,表明了该算法的正确性及有效性.     

Symbolic Algorithmic Analysis of Rectangular Hybrid Systems

This paper investigates symbolic algorithmic analysis of rectangular hybrid systems.To deal with the symbolic reachability problem,a restricted constraint system called hybrid zone is formalized for the representation and manipulation of rectangular automata state-spaces.Hybrid zones are proved to be closed over symbolic reachability operations of rectangular hybrid systems.They are also applied to model-checking procedures for verifying some important classes of timed computation tree logic formulas.To ...