On building minimal automaton for subset matching queries

We address the problem of building an index for a set D of n strings, where each string location is a subset of some finite integer alphabet of size σ, so that we can answer efficiently if a given simple query string (where each string location is a single symbol) p occurs in the set. That is, we need to efficiently find a string d∈D such that p[i]∈d[i] for every i. We show how to build such index in O(nlogσ/Δ(σ)log(n)) average time, where Δ is the average size of the subsets. Our methods have applications e.g. in computational biology (haplotype inference) and music information retrieval.     

Formal power series and regular operations on fuzzy languages

In this paper we study formal power series over a quantale with coefficients in the algebra of all languages over a given alphabet, and representation of fuzzy languages by these formal power series. This representation generalizes the well-known representation of fuzzy languages by their cut and kernel languages. We show that regular operations on fuzzy languages can be represented by regular operations on power series which are defined by means of operations on ordinary languages. We use power series in study of fuzzy languages which are recognized by fuzzy finite automata and deterministic finite automata, and we study closure properties of the set of polynomials and the set of polynomials with regular coefficients under regular operations on power series.     

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

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

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

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

考虑动态速度上限的车辆行驶虚坡模型

研究交通管理问题,针对元胞自动机模型被广泛用于交通流的仿真,但它具有其自身固有的离散性。对仿真中车辆以跬跳的方式前进,使得难以用实验手段检验其计算结果。另外,元胞自动机难以处理道路宽度连续变化的情形。而以固支梁挠度曲线为基础的虚坡模型能有效地体现车辆行驶的连续性并能自然推广于道路宽度变化的情形。但以往虚坡模型中采用的车辆速度上限保持不变,驾驶缺乏灵活性。为解决上述问题,提出通过用固支梁挠度曲线表示不同阶段内的动态速度上限,以表示车辆的源于动力的加减速行为。对一个大规模问题进行了计算,结果表明模型能给出连续的车辆速度,并且能适用于道路宽度变化时的情形,能反映车辆行驶随意性,经仿真结果表明改进模型的优越性。     

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

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

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

为对现有的高性能正则表达式匹配算法进行综合比较与分析,实现诸如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%。     

模糊操作条件概率自动机仿生自主学习系统和机器人自平衡控制

为了实现两轮机器人的自平衡控制, 利用Skinner操作条件反射机理, 以概率自动机为平台, 融入模糊推理, 构造了模糊操作条件概率自动机(OCPA)仿生自主学习系统. 该学习系统是一个从状态集合到操作行为集合的随机映射, 采用操作条件反射学习机制, 从操作行为集合中随机学习作为控制系统控制信号的最优行为, 并利用学习到的操作行为取向值信息, 调整操作条件反射学习算法. 此外, 学习系统还引入行为熵, 以验证其自学习和自组织能力. 应用于两轮机器人自平衡控制的仿真结果, 验证了模糊OCPA学习系统的可行性.     

The impact of requirements changes on specifications and state machines

Requirements change both during and after a phase of development for a variety of reasons, including error correction and feature changes. Requirements change management is one of the most complex and difficult problems to deal with in requirements elicitation and tracking. It is generally not understood how a specific change propagates through the specification and into the code. In this paper we capture requirements changes as series of atomic changes in specifications. Using a rigorous specification method called sequence‐based specification, we propose a set of algorithms for managing all possible atomic requirements changes. The algorithms have been formulated within an axiom system for sequence‐based specification and proven for correctness. They have also been implemented in a prototype tool with which users are able to push requirements changes through to changes in specifications, maintain old specifications over time and evolve them into new specifications with the least amount of human interaction and rework. The approach of utilizing state machines to model and manage requirements changes guarantees strong evidence about the correctness and completeness of the proposed theory that will lead to more reliable software in the presence of change, especially with embedded systems and safety‐critical systems. The solution described is general enough for adoption by software and system developers, and well suited for incremental development. Copyright © 2008 John Wiley & Sons, Ltd.     

考虑个体行为的改进CA模型人员疏散研究

为更好模拟行人疏散过程中微观个体行为,考虑行人身材半径及在疏散过程中行人步行速度随运动状态变化,将社会力模型运行规则引入元胞自动机模型,建立了一种社会力模型计算步行速度、空间离散化程度和步行速度较高的疏散模型,用于模拟紧急情况下的行人疏散过程。在该模型中空间划分为更小网格,每个行人占用一到多个单元格,行人的身材半径不再不变,每个行人移动的距离由其速度决定,根据基于速度的出口选择方法和行人运动规律,通过数值模拟分析,研究了疏散过程中的动态性。研究表明基于速度的网格移动数量、行人数量、期望速度、行人身材半径、松弛时间等参数影响疏散效率,结合连续模型的优点能够更加客观真实刻画疏散过程,有助于离散模型描述行人疏散微观行为特征。