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.     

Synchronic and Diachronic Emergence

I discuss here a number of different kinds of diachronic emergence, noting that they differ in important ways from synchronic conceptions. I argue that Bedau’s weak emergence has an essentially historical aspect, in that there can be two indistinguishable states, one of which is weakly emergent, the other of which is not. As a consequence, weak emergence is about tokens, not types, of states. I conclude by examining the question of whether the concept of weak emergence is too weak and note that there is at present no unifying account of diachronic and synchronic concepts of emergence.

Fault Diagnosis of Discretely Controlled Continuous Systems by Means of Discrete-Event Models

Discretely controlled continuous systems consist of continuous plants whose operation mode is switched by a feedback controller. Fault diagnosis has to use the measured switching sequence and the measured continuous movement to detect and identify faults. In order to get the diagnostic algorithm with the least possible complexity, the kind of measurement information and the granularity of the model have to be chosen in accordance with the faults to be detected. The paper presents five diagnostic methods in a uniform way, which differ with respect to the model and the measurement information used. From the hybrid model of discretely controlled continuous systems, four more abstract representations are derived, which have the form of embedded maps, semi-Markov processes, timed automata and nondeterministic automata. The validity of the diagnostic result is ensured by the claim that the models should be complete and, hence, consistent with all the input-output sequences of the discretely controlled system in the appropriate fault case. In this way a hierarchy of models and of diagnostic results is obtained. The methods are illustrated by an example.

基于Mealy机的多主体演化博弈仿真研究

针对经济学研究中演化博弈建模表示与实现问题,提出构建一种基于Mealy有限自动机的经济学多主体博弈仿真系统.该系统用Mealy自限自动机表示组织和个人行为,采用面向对象的可视化界面控制技术构造有限自动机,利用人工智能中的语言翻译技术把有限自动机翻译成线程,并用并发调度和串行调度的方式对线程进行处理.在博弈过程中采用遗传算法产生新的有限自动机.用一个三人重复囚徒困境演化博弈实例,输入状态转换图,给出博弈均衡的结果.仿真实例表明系统方法是有效的.     

基于模糊控制规则的元胞自动机模型

针对单车道道路交通流提出了一种新的基于模糊控制规则的元胞自动机模型。与NaSch模型不同,新模型中的随机慢化概率是根据模糊控制规则计算得来的。在新模型的模糊控制规则中,将当前车辆的车间距以及其与前车的速度差作为输入因素,经过模糊推理从而计算出当前车辆本时间步的随机慢化概率。经过计算机仿真发现,新模型的基本图和时空图较好地重现了现实道路交通流中的某些宏观特性,如时走时停波、回滞以及亚稳态等现象。     

基于有限自动机的XML过滤技术研究综述

介绍了基于有限自动机的XML过滤技术的研究现状,依据自动机的特点进行分类,分析了其中几种典型算法,并对XML过滤算法的优缺点进行了深入讨论和比较.     

定性推理在矩形phase—portrait近似中的应用

抽象近似是验证混合系统安全性的主要方法,矩形phase-portrait近似是通过构造简单的线性混合自动机来近似原混合自动机.phase-portrait近似的关键步骤是如何划分状态空间.本文采用定性推理的方法,叙述了如何根据系统动态特征来划分状态空间及如何精化抽象模型.     

The faster higher-order cellular automaton for hyper-parallel undistorted data compression

This paper defines second-order and third-order permutation global functions and presents the corresponding higher-order cellular automaton approach to the hyper-parallel undistorted data compression.The genetic algorithm is successfully devoted to finding out all the correct local compression rules for the higher-order cellualr automaton.The correctness of the higher-order compression rules,the time complexity,and the systolic hardware implementation issue are discussed.In comparison with the first-order automation method reported,the proposed higher-order approach has much faster compression speed with almost the same degree of cellular structure complexity for hardware implementation.