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.     

Inclusion dynamics hybrid automata

Hybrid systems are dynamical systems with the ability to describe mixed discrete-continuous evolution of a wide range of systems. Consequently, at first glance, hybrid systems appear powerful but recalcitrant, neither yielding to analysis and reasoning through a purely continuous-time modeling as with systems of differential equations, nor open to inferential processes commonly used for discrete state-transition systems such as finite state automata. A convenient and popular model, called hybrid automata, was introduced to model them and has spurred much interest on its tractability as a tool for inference and model checking in a general setting. Intuitively, a hybrid automaton is simply a “finite-state” automaton with each state augmented by continuous variables, which evolve according to a set of well-defined continuous laws, each specified separately for each state. This article investigates both the notion of hybrid automaton and the model checking problem over such a structure. In particular, it relates first-order theories and analysis results on multivalued maps and reduces the bounded reachability problem for hybrid automata whose continuous laws are expressed by inclusions (x′f(x,t)) to a decidability problem for first-order formulæ over the reals. Furthermore, the paper introduces a class of hybrid automata for which the reachability problem can be decided and shows that the problem of deciding whether a hybrid automaton belongs to this class can be again decided using first-order formulæ over the reals. Despite the fact that the bisimulation quotient for this class of hybrid automata can be infinite, we show that our techniques permit effective model checking for a nontrivial fragment of CTL.     

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.     

DTD可选的XML访问控制研究

为解决XML管理安全问题,提出了DTD可选的XML访问控制系统OD-XACS(XML Access Control System with Optional DTD),并给出了安全性分析.OD-XACS支持访问控制规则中带有{//,*,[ ]}的复杂XPath式.有DTD时,ODXACS利用XPath式对DTD的可满足性验证访问控制规则的有效性,并对由规则中XPath式构造的不确定有限自动机进行具体化,消除了这些XPath式中的冗余.实验表明,访问控制规则的验证和具体化可以极大地减轻XML查询引擎的负担.     

改进的模糊交叉算子及其在CGA中的应用

基于标准化适应值信息,提出改进的模糊交叉算子,并应用到细胞状遗传算法(CGA)中。在具有局部搜索倾向的交叉操作中,该算子能使后代更偏向于适应值高的父体。在具有全局搜索倾向的交叉操作中,能使较差个体在更大范围内进行搜索,有效地引导CGA算法向全局最优解的方向收敛。仿真实验结果表明,基于改进模糊交叉算子的CGA算法性能更好。     

实例化过程模型的时间自动机描述方法研究

语法结构正确的过程模型并不能保证过程运作的实际执行,因为没有考虑实例化阶段的时间资源安排.传统的过程自动机描述法不足以分析实例化过程模型.针对这种情况,提出用时间自动机描述过程模型语义的方法,设计了生成时间自动机的算法,分析了这种描述方法在模型检验中的应用.     

正规文法与有限自动机的等价构造

在功能上,正规文法与有限自动机描述和识别语言是等价的,它们之间也存在等价构造算法,但这些构造算法有些复杂.对其算法进行了简化且给以了证明,并提出了一个从有限自动机构造等价左线性正规文法的算法,同时也进行了证明,最后给出了该算法的一个实例.     

拟（h,k）存贮有限自动机的可逆性

主要研究拟（h,k）阶存贮有限自动机的延迟k步与k＋1步弱可逆性,以及它的弱逆,得到了拟（h,k）阶存贮有限自动机的延迟k步与k＋1步弱可逆的充分必要条件,并且通过所得结果可以比较简便地构造出延迟k步与k＋1步弱可逆拟（h,k）阶存贮有限自动机的延迟k步与k＋1步弱逆。     

拟(h,k)存贮有限自动机的可逆性

主要研究拟(h,k)阶存贮有限自动机的延迟k步与k+1步弱可逆性,以及它的弱逆,得到了拟(h,k)阶存贮有限自动机的延迟k步与k+1步弱可逆的充分必要条件,并且通过所得结果可以比较简便地构造出延迟k步与k+1步弱可逆拟(h,k)阶存贮有限自动机的延迟k步与k+1步弱逆.     

基于细胞神经网络的视频分割算法研究

细胞神经网络（CNN）是一种局部互连的非线性并行模拟视觉处理系统,具有适合硬件实现处理速度快的优点,被广泛地应用于图像处理的各个方面。针对目前大多数视频分割算法难以满足实时性要求的缺点,将细胞神经网络应用到视频分割当中．提出了一种改进的基于细胞神经网络的视频分割算法,并通过仿真实验证明了其可行性。