基于元胞自动机模型的域间路由仿真分析

由于域间路由系统的大规模性和拓扑关系的复杂性,使得分析宏观路由行为成为一个难题。提出一种基于元胞自动机模型的域间路由仿真模型,用于分析域间路由系统的宏观行为。研究结果表明,仿真模型在一定程度上可以较好地反映域间路由系统的宏观行为特征。仿真结果发现,在域间路由系统中,小范围短时间的不稳定路由行为经过广泛传播,会导致整个路由系统出现不良系统行为。     

Efficient mode enumeration of compositional hybrid systems

A hyperplane arrangement is a polyhedral cell complex where the relative position of each cell of the arrangement and the composing hyperplanes are summarised by a sign vector computable in polynomial time. This tool from computational geometry enables the development of a fast and efficient algorithm to translate the composition of discrete-time linear hybrid systems into an equivalent piecewise affine model and to determine if the composition is well posed. The tool also provides information on the real combinatorial degree of the system which can be used to reduce the size of the search tree and the computation time of the optimisation algorithms underlying optimal and model predictive control. Examples are presented illustrating the algorithm and showing its computational effectiveness.     

模糊Büchi自动机的等价刻画

模糊语言的研究是形式语言研究的焦点之一,然而如何对模糊语言进行刻画甚至更好地分类是其中一个重要研究方向.文章在模糊ω-语言的研究基础上,从模糊逻辑角度研究了模糊ω-正则语言的等价刻画.首先借助广义子集构造方法,证明了任一模糊Büchi自动机与具有分明初始状态和状态转移函数且具有模糊终状态的模糊Büchi自动机是等价的,藉此研究了模糊ω-正则语言的代数刻画和层次刻画,讨论了模糊ω-正则语言关于正则运算的封闭性;其次引入单体二阶(L)ukasiewicz逻辑的概念,给出模糊Büchi自动机识别语言的等价逻辑刻画;最后通过引入ω-星自由和ω-非周期模糊ω-语言,利用“层次化”处理技巧得到了多值逻辑意义下的分类定理,对模糊ω-正则语言给出了一种分类方法.     

Positive expansiveness versus network dimension in symbolic dynamical systems

A symbolic dynamical system is a continuous transformation Φ:X?X of closed subset X⊆A^V, where A is a finite set and V is countable (examples include subshifts, odometers, cellular automata, and automaton networks). The function Φ induces a directed graph (‘network’) structure on V, whose geometry reveals information about the dynamical system (X,Φ). The dimensiondim(V) is an exponent describing the growth rate of balls in this network as a function of their radius. We show that, if X has positive entropy and dim(V)>1, and the system (A^V,X,Φ) satisfies minimal symmetry and mixing conditions, then (X,Φ) cannot be positively expansive; this generalizes a well-known result of Shereshevsky about multidimensional cellular automata. We also construct a counterexample to a version of this result without the symmetry condition. Finally, we show that network dimension is invariant under topological conjugacies which are Hölder-continuous.     

Simulating reversible Turing machines and cyclic tag systems by one-dimensional reversible cellular automata

In this paper, we investigate how 1-D reversible cellular automata (RCAs) can simulate reversible Turing machines (RTMs) and cyclic tag systems (CTSs). A CTS is a universal string rewriting system proposed by M. Cook. First, we show that for any m-state n-symbol RTM there is a 1-D 2-neighbor RCA with a number of states less than (m+2n+1)(m+n+1) that simulates it. It improves past results both in the number of states and in the neighborhood size. Second, we study the problem of finding a 1-D RCA with a small number of states that can simulate any CTS. So far, a 30-state RCA that can simulate any CTS and works on ultimately periodic infinite configurations has been given by K. Morita. Here, we show there is a 24-state 2-neighbor RCA with this property.     

Special factors and the combinatorics of suffix and factor automata

The suffix automaton (resp. factor automaton) of a finite word w is the minimal deterministic automaton recognizing the set of suffixes (resp. factors) of w. We study the relationships between the structure of the suffix and factor automata and classical combinatorial parameters related to the special factors of w. We derive formulae for the number of states of these automata. We also characterize the languages L_SA and L_FA of words having respectively suffix automaton and factor automaton with the minimal possible number of states.     

Decision problems for convex languages

We examine decision problems for various classes of convex languages, previously studied by Ang and Brzozowski, originally under the name “continuous languages”. We can decide whether a language L is prefix-, suffix-, factor-, or subword-convex in polynomial time if L is represented by a DFA, but these problems become PSPACE-complete if L is represented by an NFA. If a regular language is not convex, we find tight upper bounds on the length of the shortest words demonstrating this fact, in terms of the number of states of an accepting DFA. Similar results are proved for some subclasses of convex languages: the prefix-, suffix-, factor-, and subword-closed languages, and the prefix-, suffix-, factor-, and subword-free languages. Finally, we briefly examine these questions where L is represented by a context-free grammar.     

一种基于元胞自动机的无线传感器网络拓扑控制方法

设计良好的网络拓扑控制方法能够减少能量消耗,实现网络能量的高效利用.利用二维元胞自动机,考虑节点的随机分布和工作/休眠/失效三态,建立无线传感器网络系统拓扑的演化规则.在设定初始条件下研究得到了演化规则的最佳控制参数,利用该参数的仿真表明,优化的元胞自动机网络拓扑控制在保证覆盖率和连通度的前提下延长了网络寿命.     

高性能正则表达式匹配算法评估

为对现有的高性能正则表达式匹配算法进行综合比较与分析,实现诸如DFA、D2FA、CD2FA、mDFA及XFA等最新算法,采用Snort规则集综合评估这些算法的存储空间和匹配时间。实验结果表明,在存储空间方面,与mDFA相比,XFA的存储空间减少84.9%~89.9%;在匹配效率方面,与mDFA相比,XFA的匹配时间增加了38.9%~174.6%;XFA在存储空间和匹配效率上具有良好的可伸缩性,即当规则数增加到8倍时,mDFA的存储空间增长了64倍,而XFA的存储空间仅增加了16倍,匹配时间仅增加了61.3%。     

基于元胞自动机的动态云模拟

针对动态云在快速模拟下的真实感缺乏问题,提出一种改进的动态云的模拟方法。该方法在Nagel方法模拟云的基础上,考虑到大气压对自然云形状的影响,通过建立上下气流动力学方程,实现具有真实感的动态云的模拟。结果证明,与常规方法相比,该方法具有运算速度快、模拟效果逼真等优点。