Analyzing the structure of a class of linear automata over a ring $$ Z_{p^k } $$

Basic finite-automaton characteristics are established for the class of all linear automata and information-lossless automata over a ring. The complexities of solving problems of parametric identification and initial-state identification are analyzed. The sets of fixed points for mappings realized by initial automata are characterized. Canonical forms are proposed for linear automata over the ring. __________ Translated from Kibernetika i Sistemnyi Analiz, No. 3, pp. 60–74, May–June 2008.     

Bottom-up pyramid cellular acceptors with three-dimensional layers

In 1997, C.R. Dyer and A. Rosenfeld introduced an acceptor on a two-dimensional pattern (or tape), called the pyramid cellular acceptor, and demonstrated that many useful recognition tasks are executed by pyramid cellular acceptors in time proportional to the logarithm of the diameter of the input. They also introduced a bottom-up pyramid cellular acceptor which is a restricted version of the pyramid cellular acceptor, and proposed some interesting open problems of the bottom-up pyramid cellular acceptors. On the other hand, we think that the study of threedimensional automata has been meaningful as the computational model of three-dimensional information processing such as computer vision, robotics, and so forth. In this paper, we investigate about bottom-up pyramid cellular acceptors with three-dimensional layers, and show their some accepting powers. This work was presented in part at the 13th International Symposium on Artificial Life and Robotics, Oita, Japan, January 31–February 2, 2008     

基于形式化方法的航空电子系统检测

随着航空型号的快速发展,航空电子系统的数字化程度越来越高,软件在其中所占的比例越来越大.对航空电子系统中的软件进行测试和检测是保证航空电子系统质量及可信运行的基础.通过分析航空电子系统软件体系结构,对航空电子系统进行形式化建模,并在此基础上,提出了一种形式化的系统级综合检测方法,从静态和动态两个方面对航空电子系统进行检测,最后通过设计并实现一个综合检测系统来验证该方法的有效性.     

基于场景的车载设备测试用例自动生成方法研究

列控车载子系统是确保列车的安全运行的关键设备,对车载子系统进行测试是保证功能实现与系统规范一致性的重要手段。针对传统手工测试用例生成的效率低、耗时长、工作量繁杂、可重用性低等缺陷,提出一种基于场景的车载系统测试用例自动生成方法,依据CTCS-3级列控系统技术规范构造车载子系统场景树模型,由实时系统测试用例自动生成工具Co Ver对列车运行模式转换自动机网模型生成基于场景的测试用例,并由运行模式最小重复度选择算法生成全模式覆盖的测试序列。结论证明,基于场景自动生成的测试用例能够覆盖全部车载模式,并提高了模式转换测试序列生成效率。     

有穷自动机的Linux多点触摸屏中间件设计

多点触摸屏的应用程序开发是当前的研究热点.Linux multi-touch (MT)协议是Linux输入子系统的一个标准协议,定义了多点触摸设备驱动程序的数据传输规范,有着广泛的使用范围.识别和处理多点触摸屏驱动程序的数据是多点触摸屏应用最基本的功能.本文采用有穷自动机的思想,设计了一个可以识别符合Linux multi-touch协议规范数据的多点触摸屏中间件.中间件提供外部接口供应用程序使用,可以减少程序开发人员的重复工作,提高开发效率.     

基于时态逻辑的UML交互模型检测研究

该文详细介绍了统一建模语言和模型检测技术,在此基础上,该文研究了基于交互自动机和时态逻辑的UML交互模型性质检测方法,提出了模型检测所需的Marking算法。该算法通过对交互自动机全部状态的遍历,检测各状态的时态逻辑公式(CTL公式)的真值,以判断用户设计的UML交互模型是否符合计算机软件系统应满足的性质及规范。     

利用自动机研究描述逻辑的推理问题

首先介绍如何把描述逻辑转化为一个不确定型有穷自动机,分析这种转化过程中存在的问题,在B．Nebel的基础上提出了利用自动机的最小化理论对上述得到的自动机进行优化处理,以提高推理的效率。     

网络入侵检测系统模式匹配算法研究

模式匹配算法是网络入侵检测中的关键所在,它直接影响到网络入侵检测系统的实时检测性能.引入4种模式匹配算法,分析其工作原理,通过实验对上述4种算法进行了性能测试.根据实验结果,得出了不同算法的应用范围,为今后入侵检测系统开发者选择模式匹配算法提供了有价值的参考.     

A generalization of the Curtis–Hedlund theorem

Let A be a set and let G be a group, and equip A^G with its prodiscrete uniform structure. Let τ:A^G→A^G be a map. We prove that τ is a cellular automaton if and only if τ is uniformly continuous and G-equivariant. We also give an example showing that a continuous and G-equivariant map τ:A^G→A^G may fail to be a cellular automaton when the alphabet set A is infinite.     

移动计算中安全策略的进程表示

安全策略为移动计算的安全性提供了必要的保证,而其表达和移动计算的形式化模型往往采用不同的技术实现。该文给出安全策略的一种进程表示方法,通过安全策略的进程表示,很容易将移动计算模型及移动计算的安全性问题在统一的框架下实现。为实现移动计算及其安全性提供了一种简单、可行的方法。