无穷自动机的几个等价命题

本文证明了具有无穷栈符合的实时确定下推自动机与无穷自动机的等价性，并且将有限状态自动机的Ｍｙｈｉｌｌ－Ｎｅｒｏｄｅ定理推广到了无穷自动机和具有无穷栈符号的实时确定下推自动机。     

模糊Rabin自动机和模糊Game自动机的等价性

自动机是理论计算机的一个重要的研究内容.模糊Rabin自动机和模糊Game自动机是经典自动机的延续,给出了模糊Rabin自动机和模糊Game自动机的相关定义,讨论各自的内在性质,并得到了二者的等价关系.这进一步丰富了模糊自动机理论.     

Integral Reverse Estimates for Logarithmic Bloch Spaces in the Ball

In this note, we focus again on the basics of triangular product of automata construction and to introduce the notion of linear automata complexity. It contains three main results. (1) For any two pure automata we consider the category of their cascade connections. It possesses the universal terminal object. This object is the wreath product of the automata. Hence, every cascade connection admits a natural embedding into the wreath product of automata. (2) A similar theory is developed for linear automata, where we also consider the category of cascade connections. It also has the terminal object. This object is the triangular product of linear automata. (3) Triangular products have various applications. This construction is used in linear automata decomposition theory and in the definition of complexity of a linear automaton. We consider a special linear complexity and give the rule for its calculation.     

基于格半群的有限状态自动机的同态

本文研究了格值有限状态自动机(LFSA)的同态和强同态及其性质.利用强同态概念,在格值有限状态自动机的状态集上建立了一种等价关系,得到了格值有限状态自动机的商自动机,证明了商自动机与强同态像自动机同构.     

具有输出字符功能的模糊自动机的最小化问题

通过文献[8]中两类具有输出字符功能的Fuzzy自动机和Fuzzy有限状态自动机的强等价性,等价性和弱等价性的条件,在以往仅仅给出的Fuzzy有限状态自动机的最小化问题基础上,讨论了具有更广泛意义的具有输出字符功能的Fuzzy自动机的最小化问题,以及其最小化自动机与Fuzzy有限状态自动机的最小化自动机在不同条件下的关系。     

Automata transformations of prefix decidable and decidable by Buchi superwords

We show that the set of prefix decidable superwords is closed under finite automata and asynchronous automata transformations. We prove that structures of degrees of finite automata and asynchronous automata transformations contain an atom which consists of prefix decidable superwords with undecidable monadic theory (or undecidable by Buchi). Also we prove that the structure of degrees of asynchronous automata transformations contains an atom which consists of superwords with decidable monadic theory (decidable by Buchi).     

Bottom-up design of strategic options as finite automata

In this paper we look at the problem of strategic decision making. We start by presenting a new formalisation of strategic options as finite automata. Then, we show that these finite automata can be used to develop complex models of interacting options, such as option combinations and product options. Finally, we analyse real option games, presenting an algorithm to generate option games (based on automata).     

基于模糊字符串的Mealy格值有限自动机及其最小化

提出取值为格半群的Mealy格值有限自动机的概念,进而得到基于模糊字符串的Mealy格值有限自动机的扩张模型,并较详细讨论了其性质. 同时定义了扩张的完备Mealy格值有限自动机的行为矩阵, 在此基础上给出了其最小化算法.     

Edge-minimization of non-deterministic finite automata

In this paper we consider non-deterministic finite Rabin-Scott’s automata. We use a special structure to describe all the possible edges of non-deterministic finite automaton defining the given regular language. Such structure can be used for solving various problems of finite automata theory. One of these problems is edge-minimization of non-deterministic automata. As we have not touched this problem before, we obtain here two versions of the algorithm for solving this problem to continue previous series of articles.     

模糊无限状态自动机及其收敛性

到目前为止,我们所研究的模糊或非模糊的自动机都是有限状态自动机.然而,关于无限状态自动机的定义及它的稳定性和收敛性都没有被讨论过.本文中,我们使用离散的反馈神经网络及网络输出空间划分方法,同时,在梯度更新算法中使用伪梯度方法,给出了模糊无限状态自动机收敛到模糊有限状态自动机的证明.     

Weighted automata and weighted logics on infinite words

We introduce weighted automata over infinite words with Muller acceptance condition and we show that their behaviors coincide with the semantics of weighted restricted MSO-sentences. Furthermore, we establish an equivalence property of weighted Muller and weighted Büchi automata over certain semirings.     

Automata in Groups and Dynamics and Induced Systems of PDE in Tropical Geometry

In this paper we develop a dynamical scaling limit from rational dynamics to automata in tropical geometry. We compare these dynamics and induce uniform estimates of their orbits. We apply these estimates to introduce a comparison analysis of theory of automata groups in geometric group theory with analysis of rational dynamics and some hyperbolic PDE systems. Frameworks of characteristic properties of automata groups are inherited to the corresponding rational or PDE dynamics. As an application we study the Burnside problem in group theory and translate the property as the infinite quasi-recursiveness in rational dynamics.     

Bisimulations for fuzzy automata

Bisimulations have been widely used in many areas of computer science to model equivalence between various systems, and to reduce the number of states of these systems, whereas uniform fuzzy relations have recently been introduced as a means to model the fuzzy equivalence between elements of two possible different sets. Here we use the conjunction of these two concepts as a powerful tool in the study of equivalence between fuzzy automata. We prove that a uniform fuzzy relation between fuzzy automata A and B is a forward bisimulation if and only if its kernel and co-kernel are forward bisimulation fuzzy equivalence relations on A and B and there is a special isomorphism between factor fuzzy automata with respect to these fuzzy equivalence relations. As a consequence we get that fuzzy automata A and B are UFB-equivalent, i.e., there is a uniform forward bisimulation between them, if and only if there is a special isomorphism between the factor fuzzy automata of A and B with respect to their greatest forward bisimulation fuzzy equivalence relations. This result reduces the problem of testing UFB-equivalence to the problem of testing isomorphism of fuzzy automata, which is closely related to the well-known graph isomorphism problem. We prove some similar results for backward-forward bisimulations, and we point to fundamental differences. Because of the duality with the studied concepts, backward and forward-backward bisimulations are not considered separately. Finally, we give a comprehensive overview of various concepts on deterministic, nondeterministic, fuzzy, and weighted automata, which are related to bisimulations.     

Didactic approach for teaching nondeterminism in automata theory

Nondeterminism plays a central role in almost all fields of computer science. It has been incorporated naturally as well as in the theory of automata as a generalization of determinism. Although nondeterministic finite automata do not have more recognition power than deterministic ones their importance and usefulness is of no doubt.Unfortunately, the operation of the mathematical model of nondeterministic automata is difficult to understand which means a didactic challenge for every teacher and lecturer. This paper gives a didactic approach to introduce the notion of finite (deterministic and) nondeterministic automata.As a teaching tool we make use of the automata theory package developed in Maple. We put emphasis on the process character of learning and work out a method that promotes the repetitive experiments.     

On the free automata and tensor product

In this paper we shall introduce the algebraic structure of a tensor product for arbitrarily given automata, giving a defintion of the tensor product for automata. We introduce and study that for any setX there always exists a free automaton onX. The existence of a tensor product for automata will be investigated in the same way like modules do.     

Fuzzy automata based on lattice-ordered monoid with algebraic and topological aspects

The purpose of this work is to study some algebraic and topological concepts of fuzzy automata with the membership values in lattice-ordered monoids. Unlike the usual fuzzy automata, we show that such concepts are affected by the associated monoid structure.     

Deformations of Real Rational Dynamics in Tropical Geometry

In this paper we study analytic properties of orbits given by real rational functions. We introduce some comparison methods which allow us to compare the real rational dynamics with automata given by (max, +) functions, passing through a kind of scale transform in tropical geometry. Such a scale transform gives a one-to-one correspondence of presentations between automata and real rational functions. We study invariant properties of the real rational dynamics under change of presentations of automata.     

Bootstrap percolation,and other automata

Many fundamental and important questions from statistical physics lead to beautiful problems in extremal and probabilistic combinatorics. One particular example of this phenomenon is the study of bootstrap percolation, which is motivated by a variety of ‘real-world’ cellular automata, such as the Glauber dynamics of the Ising model of ferromagnetism, and kinetically constrained spin models of the liquid–glass transition.In this review article, we will describe some dramatic recent developments in the theory of bootstrap percolation (and, more generally, of monotone cellular automata with random initial conditions), and discuss some potential extensions of these methods and results to other automata. In particular, we will state numerous conjectures and open problems.     

Hybrid Dynamics of Stochastic π-Calculus

In this paper we describe a method to map stochastic π-calculus processes in chemical ground form into hybrid automata. Hybrid automata are tools widely employed to model systems characterized by both discrete and continuous evolution and their use in the context of Systems Biology allows us to address rather fundamental issues. Specifically, the key ingredient we use in this work is the possibility granted by hybrid automata to implement a separation of control and molecular terms in biochemical systems. The computational counterpart of our analysis turns out to be related to the determination of conservation properties of the system.      

模糊有限自动机的乘积覆盖性

推广模糊有限自动机的有限积,包括direct infinite乘积、cascade infinite乘积和wreath infinite 来积.进而讨论它们之间的关系,得到乘积覆盖性等代数性质.