Periodicity in generations of automata

A class of automata which build other automata is defined. These automata are called Turing machine automata because each one contains a Turing machine which acts as its computer-brain and which completely determines what its offspring, if any, will be. We show that for the descendants of an arbitrary progenitor Turing machine automaton there are exactly three possibilities: (1) there is a sterile descendant after an arbitrary number of generations, (2) after a delay of an arbitrary number of generations, the descendants repeat in generations with an arbitrary period, or (3) the descendants are aperiodic. We also show what sort of computing ability may be realized by the descendants in each of the possibilities. Furthermore, it is determined whether there are effective procedures for distinguishing between the various possibilities, and the exact degree of unsolvability is computed for those decision problems for which there is no effective procedure. Lastly, we discuss the relevance of the results to biology and pose several questions.Department of Computer Science. The research for this paper was supported in part by Kansas General Research Grant 3683-5038.     

MINIMAL VALID AUTOMATA OF SAMPLE SEQUENCES FOR DISCRETE EVENT SYSTEMS

Minimal valid automata (MVA) refer to valid automata models that fit a given input‐output sequence sample from a Mealy machine model. They are minimal in the sense that the number of states in these automata is minimal. Critical to system identification problems of discrete event systems, MVA can be considered as a special case of the minimization problem for incompletely specified sequential machine (ISSM). While the minimization of ISSM in general is an NP‐complete problem, various approaches have been proposed to alleviate computational requirement by taking special structural properties of the ISSM at hand. In essence, MVA is to find the minimal realization of an ISSM where each state only has one subsequent state transition defined. This paper presents an algorithm that divides the minimization process into two phases: first to give a reduced machine for the equivalent sequential machine, and then to minimize the reduced machine into minimal realization solutions. An example with comprehensive coverage on how the associated minimal valid automata are derived is also included.     

元胞自动机与软计算的集成及其应用

介绍了元胞自动机的思想来源和基本原理，对元胞自动机与敦计算的人工智能技术进行比较并加以集成，讨论了近年来它在混沌分形、图像处理、智能材料、机器学习、模拟复杂现象等领域中的应用成果，并对进一步研究进行展望。     

On synchronized evolution of the network of automata

One of the tasks in machine learning is to build a device that predicts each next input symbol of a sequence as it takes one input symbol from the sequence. We studied new approaches to this task. We suggest that deterministic finite automata (DFA) are good building blocks for this device, together with genetic algorithms (GAs), which let these automata "evolve" to predict each next input symbol of the sequence. Moreover, we study how to combine these highly fit automata so that a network of them would compensate for each others' weaknesses and predict better than any single automaton. We studied the simplest approaches to combine automata: building trees of automata with special-purpose automata, which may be called switchboards. These switchboard automata are located on the internal nodes of the tree, take an input symbol from the input sequence just as other automata do, and predict which subtree will make a correct prediction on each next input symbol. GAs again play a crucial role in searching for switchboard automata. We studied various ways of growing trees of automata and tested them on sample input sequences, mainly note pitches, note durations and up/down notes of Bach's Fugue IX. The test results show that DFAs together with GAs seem to be very effective for this type of pattern learning task     

Fusion of learning automata theory and granular inference systems: ANLAGIS. Applications to pattern recognition and machine learning

In this paper the fusion of artificial neural networks, granular computing and learning automata theory is proposed and we present as a final result ANLAGIS, an adaptive neuron-like network based on learning automata and granular inference systems. ANLAGIS can be applied to both pattern recognition and learning control problems. Another interesting contribution of this paper is the distinction between pre-synaptic and post-synaptic learning in artificial neural networks. To illustrate the capabilities of ANLAGIS some experiments on knowledge discovery in data mining and machine learning are presented. The main, novel contribution of ANLAGIS is the incorporation of Learning Automata Theory within its structure; the paper includes also a novel learning scheme for stochastic learning automata.     

极限学习机集成在骨髓细胞分类中的应用

骨髓细胞的分类有重要的医学诊断意义。先对骨髓细胞图像分割和特征提取,用提取出来的训练集对极限学习机训练,再用该分类器对未知样本识别。针对单个分类器性能的不稳定,提出基于元胞自动机的极限学习机集成算法。通过元胞自动机抽样策略构建差异大的训练子集,多个分类器并行学习,多数投票法联合决策。实验结果表明,与BP、支持向量机比较,该算法基本无参数调整,学习速度快,分类精度高能达到97.33%,且有效克服了神经网络分类器不稳定的缺点。     

Some properties of four-dimensional parallel Turing machines

Informally, the parallel Turing machine (PTM) proposed by Wiedermann is a set of identical usual sequential Turing machines (STMs) cooperating on two common tapes: a storage tape and an input tape. Moreover, STMs which represent the individual processors of a parallel computer can multiply themselves in the course of computation. On the other hand, during the past 7 years or so, automata on a four-dimensional tape have been proposed as computational models of four-dimensional pattern processing, and several properties of such automata have been obtained. We proposed a four-dimensional parallel Turing machine (4-PTM), and dealt with a hardware-bounded 4-PTM in which each side-length of each input tape is equivalent. We believe that this machine is useful in measuring the parallel computational complexity of three-dimensional images. In this work, we continued the study of the 3-PTM, in which each side-length of each input tape is equivalent, and investigated some of its accepting powers.     

Improved undecidability results on weighted timed automata

In this paper, we strengthen two recent undecidability results about weighted timed automata, an extension of timed automata with cost variables. More precisely, we propose new encodings of a Minsky machine that only require three clocks and one stopwatch cost, while previous reductions required five clocks and one stopwatch cost.     

On the computational power of totalistic cellular automata

Totalistic cellular automata, introduced by S. Wolfram, are cellular automata in which the state transition function depends only on the sum of the states in a cell's neighborhood. Each state is considered as a nonnegative integer and the sum includes the cell's own state. It is shown that one-dimensional totalistic cellular automata can simulate an arbitrary Turing machine in linear time, even when the neighborhood is restricted to one cell on each side. This result settles Wolfram's conjecture that totalistic cellular automata are computation-universal.Research performed while visiting the Department of Computer Science, University of Cincinnati, 1984/85.     

A Kleene theorem and model checking algorithms for existentially bounded communicating automata

The behavior of a network of communicating automata is called existentially bounded if communication events can be scheduled in such a way that the number of messages in transit is always bounded by a value that depends only on the machine, not the run itself. We show a Kleene theorem for existentially bounded communicating automata, namely the equivalence between communicating automata, globally cooperative compositional message sequence graphs, and monadic second order logic. Our characterization extends results for universally bounded models, where for each and every possible scheduling of communication events, the number of messages in transit is uniformly bounded. As a consequence, we give solutions in spirit of Madhusudan (2001) for various model checking problems on networks of communicating automata that satisfy our optimistic restriction.     

基于量子逻辑的自动机和文法理论

初步建立了基于量子逻辑的自动机和文法理论的基本框架.引入了量子文法(称为l值文法),特别是证明了任意l值正规文法生成的语言(称为量子语言)等价于某种基于量子逻辑且含动作(的自动机(称为l值自动机)识别的语言,反之,任意l值自动机识别的语言等价于某l值正规文法生成的语言.建立了l值泵引理,并得到量子语言的判定性刻画.最后简要讨论了正规文法与量子文法(即l值正规文法)的关系.因此,为进一步研究更复杂的量子自动机(如量子下推自动机和Turing机)和量子文法(如量子上下文无关文法和上下文有关文法)奠定了基础.     

Distance automata having large finite distance or finite ambiguity

A distance automaton is a (nondeterministic finite) automaton which is equipped with a nonnegative cost function on its transitions. The distance of a word recognized by such a machine quantifies the expenses associated with the recognition of this word. The distance of a distance automaton is the maximal distance of a word recognized by this machine or is infinite, depending on whether or not a maximum exists. We present distance automata havingn states and distance 2 ⁿ – 2. As a by-product we obtain regular languages having exponential finite order. Given a finitely ambiguous distance automaton withn states, we show that either its distance is at most 3 ⁿ – 1, or the growth of the distance in this machine is linear in the input length. The infinite distance problem for these distance automata is NP-hard and solvable in polynomial space. The infinite-order problem for regular languages is PSPACE-complete.A preliminary version of this article appeared in theProceedings of the 15th Symposium on Mathematical Foundations of Computer Science, 1990.     

模型驱动的嵌入式系统设计安全性验证方法研究

基于模型的嵌入式系统安全性分析与验证方法是近年来在安全攸关系统工程领域中出现的一个重要研究热点。提出一种基于模型驱动架构的面向SysML/MARTE状态机的系统安全性验证方法,具体包括:构建了具备SysML/MARTE扩展语义的状态机元模型,以及安全性建模与分析语言AltaRica的语义模型GTS的元模型;然后建立了从SysML/MARTE状态机模型分别到时间自动机模型以及AltaRica模型的语义映射模型转换规则,并基于AMMA平台和时间自动机验证工具UPPAAL设计实现了对SysML/MARTE状态机的模型转换与系统安全性形式化验证的框架。最后给出了一个飞机着陆控制系统设计模型的安全性验证实例分析。     

Adaptive behaviorin cellular automata using rough set theory

The paper uses ideas from machine learning and artificial intelligence to provide the model of cellular automata based on rough set theory and the response to it in simulated cars. Recently, the examination and modeling of vehicular traffic has become an important subject of research. We propose in this paper, a road-traffic system based on two-dimensional cellular automata combined with rough set theory, to model the flow and jamming that is common in an urban environment. The modeled development process in this paper involves simulated processes of evolution, learning, and self-organization. The main value of the model is that it provides an illustration of how simple learning processes may lead to the formation of the state machine behavior, which can give emergence to the model.     

主动自动机学习中的等价查询算法优化

模型学习是一种获取黑盒软件系统行为模型的有效方法,可分为主动学习和被动学习.主动学习是基于字母表构造测试用例,通过与黑盒系统主动交互,可在多项式时间内得到目标系统的最小完备自动机,其中等价查询仍是开发和应用主动自动机学习工具的障碍之一.通过探讨反例对于学习算法的影响,定义假设的比较规则,提出测试用例构造的两个原则,同时依据原则对Wp-method等价查询算法改进,产生更优的假设,有效降低查询的数量,并基于LearnLib开源工具,分别以3类自动机为实验对象验证原则和改进算法的有效性.     

Three-dimensional parallel Turing machines

Informally, the parallel Turing machine (PTM) proposed by Wiedermann is a set of identical usual sequential Turing machines (STMs) cooperating on two common tapes: storage tape and input tape. Moreover, STMs which represent the individual processors of a parallel computer can multiply themselves in the course of computation. On the other hand, during the past 25 years or so, automata on a three-dimensional tape have been proposed as computational models of three-dimensional pattern processing, and several properties of such automata have been obtained. We proposed a three-dimensional parallel Turing machine (3-PTM), and dealt with a hardware-bounded 3-PTM whose inputs are restricted to cubic ones. We believe that this machine is useful in measuring the parallel computational complexity of three-dimensional images. In this article, we continue the study of 3-PTM, whose inputs are restricted to cubic ones, and investigate some of its accepting powers. This work was presented in part at the 12th International Symposium on Artificial Life and Robotics, Oita, Japan, January 25–27, 2007     

Automata in random environments with application to machine intelligence

Computers and brains are modeled by finite and probabilistic automata, respectively. Probabilistic automata are known to be strictly more powerful than finite automata. The observation that the environment affects behavior of both computer and brain is made. Automata are then modeled in an environment. Theorem 1 shows that useful environmental models are those which are infinite sets. A probabilistic structure is placed on the environment set. Theorem 2 compares the behavior of finite (deterministic) and probabilistic automata in random environments. Several interpretations of Theorem 2 are discussed which offer some insight into some mathematical limits of machine intelligence.     

Comparing Verboseness for Finite Automata and Turing Machines

A language is called (m,n)-verbose if there exists a Turing machine that enumerates for any n words at most m possibilities for their characteristic string. This notion is compared with (m,n)-fa-verboseness, where instead of a Turing machine a finite automaton is used. By use of a new diagonalisation method, where finite automata trick Turing machines, it is shown that all (m,n)-verbose languages are (h,k)-verbose iff all (m,n)-fa-verbose languages are (h,k)-fa-verbose. In other words, Turing machines and finite automata behave exactly the same way with respect to inclusion of verboseness classes. This identical behaviour implies that the nonspeedup theorem also holds for finite automata. As an application of the theoretical framework, a lower bound is derived on the number of bits that need to be communicated to finite automata protocol checkers for nonregular protocols.     

A continuum of discrete systems

We show how to regard covered logic programs as cellular automata. Covered logic programs are ones for which every variable occurring in the body of a given clause also occurs in the head of the same clause. We generalize the class of register machine programs to permit negative literals and characterize the members of this class of programs as n-state 2-dimensional cellular automata. We show how monadic covered programs, the class of which is computationally universal, can be regarded as 1-dimensional cellular automata. We show how to continuously (and differentiably) deform 1-dimensional cellular automata from one to another and understand the arrangement of these cellular automata in a separable Hilbert space over the real numbers. The embedding of the cellular automata of fixed radius r is a linear mapping into R^{2 2r+1} in which a cellular automaton's transition function is the attractor of a state-governed iterated function system of affine contraction mappings. The class of covered monadic programs having a particular fixed point has a uniform arrangement in an affine subspace of the Hilbert space l². Furthermore, these programs are construable as almost everywhere continuous functions from the unit interval {x | 0 ≤ x ≤ 1} to the real numbers R. As one consequence, in particular, we can define a variety of natural metrics on the class of these programs. Moreover, for each program in this class, the set of initial segments of the program's fixed points, with respect to an ordering induced by the program's dependency relation, is a regular set. This revised version was published online in June 2006 with corrections to the Cover Date.