Flip-pushdown automata with k pushdown reversals and E0L systems are incomparable

We prove that any propagating E0L system cannot generate the language {w#w|w∈{0,1}^?}$\{w\mathrm{\#}w|w\in {\{0,1\}}^{?}\}$. This result, together with some known ones, enables us to conclude that the flip-pushdown automata with k pushdown reversals, i.e., the pushdown automata with the ability to flip the pushdown, and E0L systems are incomparable. This result solves an open problem stated by Holzer and Kutrib in 2003.     

On probabilistic analog automata

We consider probabilistic automata on a general state space and study their computational power. The model is based on the concept of language recognition by probabilistic automata due to Rabin (Inform. Control 3 (1963) 230) and models of analog computation in a noisy environment suggested by Maass and Orponen (Neural Comput. 10 (1998) 1071), and Maass and Sontag (Neural Comput. 11 (1999) 771). Our main result is a generalization of Rabin's reduction theorem that implies that under very mild conditions, the computational power of such automata is limited to regular languages.     

Some Notes on Graph Automata, TilingSystems and Partition Logic

Introduce heuristically the newly definition(W.Thomas)for graph automata-using “tiles”to simulate the extension(over dag‘s) of the classical notions of transition moves;propose a sufficient condition for when graph automata can be reduced to (simpler)tiling systems,which is a generalization of a Thomas‘ result;and finally study the logic sepcification of tiling systems (particularly,over picture languages)by (existential)monadic partition logic,instead of the ususal and stronger framework(E)MSO.     

求解非线性方程组的元胞自动机方法及其全局收敛性证明

为了求得非线性方程组所有精确解,根据元胞自动机的特点构造了求解非线性方程组的全局收敛算法。在该算法中,将非线性方程组解的理论搜索空间划分为离散搜索空间,将离散搜索空间定义为元胞空间;离散搜索空间的每个点就是一个元胞,而一个元胞对应着非线性方程组的一个试探解;元胞的状态由其空间位置及位置修正量构成。将元胞空间划分为若干个非空子集,所有元胞的状态从一个非空子集转移到另一个非空子集的状态演化过程实现了元胞空间对理论搜索空间的搜索。在元胞状态演化过程中,元胞从一个状态转移到另一个状态的状态转移概率可以计算出来;元胞演化过程中的每个状态对应于有限Markov链上的一个状态。利用可归约随机矩阵的稳定性条件证明了该算法具有全局收敛性。仿真实例表明该算法是高效的。     

Murg term rewrite systems

The union of a monadic and a right-ground term rewrite system is called a murg term rewrite system. We show that for murg TRSs the ground common ancestor problem is undecidable. We show that for a murg term rewrite system it is undecidable whether the set of descendants of a ground tree is a recognizable tree language. We show that it is undecidable whether a murg term rewrite system over Σ preserves Σ-recognizability.     

基于ADL的物理信息系统的建模与分析

当前分析和设计物理信息系统的模型和方法通常是线性分离的,且由不同的数学形式化方法和工程与计算机科学中的不同方法定义。为便于处理,对关注点分离是必要的,但这种分析方式由于在系统设计时过早地将系统信息特征与物理特征分离,导致很难评估直接与这两个领域进行交互的可替换元素的影响和协调性。文中对围绕组成CPS系统的所有范围的元素的架构描述进行扩展,最终目的是能够建立一个可扩展的框架,包括一套可被创建的综合设计工具。由此文中提出这种物理信息系统建模方法并通过一个简单应用实例对方法进行说明。     

Simulation of one-way cellular automata by boolean circuits

We present a relationship between two major models of parallel computation: the one-way cellular automata and the boolean circuits. The starting point is the boolean circuit of small depth designed by Ladner and Fischer to simulate any rational transducer. We extend this construction to simulate one-way cellular automata by boolean circuits.     

演化元胞自动机函数优化算法案例研究

BUMP是一个超多维,超多峰,超非线性的问题,被广泛应用于各种演化算法的性能比较。但最好解是未知的。基于元胞自动机的遗传算法报告了BUMP曾经发表过的最好解。该文设计了基于演化元胞自动机的新算法(ECAA)并获得了更好的结果。文中详细讨论了算法中各算子的设计方法及其在算法中扮演的角色,分析了该算法的极度并行,天然局部搜索等重要特性。     

On transformations of formal power series

Formal power series are an extension of formal languages. Recognizable formal power series can be captured by the so-called weighted finite automata, generalizing finite state machines. In this paper, motivated by codings of formal languages, we introduce and investigate two types of transformations for formal power series. We characterize when these transformations preserve recognizability, generalizing the recent results of Zhang [16] to the formal power series setting. We show, for example, that the “square-root” operation, while preserving regularity for formal languages, preserves recognizability for formal power series when the underlying semiring is commutative or locally finite, but not in general.     

P systems without multiplicities of symbol-objects

In this paper we investigate P systems whose compartments contain sets of symbol-objects rather than multisets of objects, as it is common in membrane computing. If the number of membranes cannot grow, then in this framework we can characterize exactly the regular languages. If membrane creation or membrane division is allowed, then the Parikh sets of recursively enumerable languages can be generated. The last result also implies the universality of P systems with active membranes (with multisets of symbol-objects) without polarizations.     

Polynomial-time verification of diagnosability of fuzzy discrete event systems

A fuzzy approach to perform diagnosis of fuzzy discrete event systems(FDESs)is proposed by constructing diagnosers,which may more effectively cope with the problems of vagueness and fuzziness arising from failure diagnosis of fuzzy systems.However,the complexity of constructing this kind of diagnosers is exponential in the state space and the number of fuzzy events of the system.In this paper,we present an algorithm for verifying the diagnosability of FDESs based on the construction of a nondeterministic automaton called F-verifier instead of diagnosers.Both the construction of F-verifiers and the verification of diagnosability of FDESs can be realized with a polynomial-time complexity.     

Two-way deterministic automata with two reversals are exponentially more succinct than with one reversal

We prove that limiting the number of reversals from two to one can cause an exponential blow-up in the size of two-way deterministic automaton.     

HIGH-SPEED PCA ENCRYPTION ALGORITHM USING RECONFIGURABLE COMPUTING

In this work, an originally bio-inspired cryptosystem is developed. It is based on the use of cellular automata (CAs) as pseudorandom bit generators and programmable cellular automata (PCA) to construct the block ciphering functions of the proposed enciphering scheme. The cryptosystem is featured by resistance on different types of attacks and high speed due to the cellular automata's parallel information processing property. The proposed architecture could be efficiently implemented in reconfigurable hardware like field programmable gate arrays (FPGAs) and could be applied in high-speed data communication. The project was implemented in two experimental hardware platforms based on Spartan 3 XC3S400fg456-4 and XILINX Spartan 3E XC3S500E.     

离散事件系统N步稳定性分析

讨论基于自动机/形式语言模型的离散事件系统(DES)稳定性问题,引入了确定性离散事件系统N步稳定性定义,并得到了稳定性的判据定理,推导了具体的算法实现。该算法具有多项式复杂度。     

Model predictive control of directed‐graph constrained systems

This paper addresses a new type of model predictive control problem for a hybrid system that consists of a continuous‐time linear system and a temporal/spatial directed graph, called a directed‐graph constrained system. Motivated by the obstacle avoidance problem, the problem is newly formulated, where the continuous‐time control input and the waypoints of the state are simultaneously optimized under a temporal/spatial directed graph as well as input/state linear constraints, and a method for efficiently solving this problem is developed. Numerical examples are presented to verify that the proposed approach is effective. Copyright © 2013 John Wiley & Sons, Ltd.