Automaton recognition of doubly connected labyrinths with finite cyclic diameter

The problem of existence of a recognizing automaton for a subclass of an infinite class of chess labyrinths (denoted as C ₀) is studied. It is proved in [1] that, for C ₀, there does not exist a recognizing automaton. In [2], it is proved that there exists a recognizing collective of type (1, 1) (collective consisting of an automaton and stone). In this paper, it is proved that there exists a recognizing automaton for some subclass of the class of chess labyrinths with finite cyclic diameter.     

The dynamics of digital circuits with memory for ternary signals

The paper examines a digital automaton with memory operating in the ternary alphabet (0, 1, ). The problem of analytical determination of ternary processes on automaton outputs and inside the automaton from given ternary processes on the automaton inputs is considered. An algorithm is proposed reducing this problem to standard determination of the processes in an automaton with the alphabet (0, 1).Translated from Kibernetika, No. 4, pp. 19–25, July–August, 1989.     

New means of cybernetics,informatics, computer engineering,and systems analysis

The class of combinatorial problems equivalent to the problem of determination of relative positions of n interval sequences is formulated. It is shown that an adequate mathematical model of solving a stated problem is a finite dynamic memoryless automaton and that the adequate mathematical apparatus is continuous logic. Algorithms that solve the problem are constructed. Misc  Translated from Kibernetika i Sistemnyi Analiz, No. 3, pp. 173–181, May-June 2009. Original article submitted July 4, 2007.     

Method of accommodation to the defects in finite automata

Consideration was given to accommodation to the defects in controllable systems described by the finite automaton model. Solution of this problem was related with generation of the control ensuring total decoupling from the actions caused by the defects. For determination of the control law, the existence conditions were formulated, and the design formulas were proposed.     

有限自动机在复合事件检测中的应用

针对早期系统只提供原子事件的检测机制,不能检测由原子事件组成的复合事件的问题,提出了用有限自动机来检测复合事件的方法.说明了复合事件的组成和表达式,利用自动机原理对复合事件的检测模式进行了分析,给出了复合事件检测的具体过程:从事件表达式到不确定的有限自动机,从不确定的有限自动机到最小化确定的有限自动机,再用程序实现了确定的有限自动机.实例表明,自动机模型是检测复合事件的一种有效实现方式.     

Functional Renewal of Behavior of Systems: Numerical Methods

The principles of functional renewal of the behavior of technical systems based on the functional capabilities in the design are stated. A finite deterministic automaton is used as the model. The functional renewal problem is solved within the framework of the theory of universal automata. A class of automata admitting modeling by a family of polynomials is described. The numerical model of automaton behavior is helpful in applying algebraic tools to solve the functional behavior renewal problem. For this automaton class, a universal enumerator is designed and analyzed, and a method of constructing a renewal sequence is described.     

A learning automata-based algorithm for determination of the number of hidden units for three-layer neural networks

There is no method to determine the optimal topology for multi-layer neural networks for a given problem. Usually the designer selects a topology for the network and then trains it. Since determination of the optimal topology of neural networks belongs to class of NP-hard problems, most of the existing algorithms for determination of the topology are approximate. These algorithms could be classified into four main groups: pruning algorithms, constructive algorithms, hybrid algorithms and evolutionary algorithms. These algorithms can produce near optimal solutions. Most of these algorithms use hill-climbing method and may be stuck at local minima. In this article, we first introduce a learning automaton and study its behaviour and then present an algorithm based on the proposed learning automaton, called survival algorithm, for determination of the number of hidden units of three layers neural networks. The survival algorithm uses learning automata as a global search method to increase the probability of obtaining the optimal topology. The algorithm considers the problem of optimization of the topology of neural networks as object partitioning rather than searching or parameter optimization as in existing algorithms. In survival algorithm, the training begins with a large network, and then by adding and deleting hidden units, a near optimal topology will be obtained. The algorithm has been tested on a number of problems and shown through simulations that networks generated are near optimal.     

Recognition of directed acyclic graphs by spanning tree automata

In this paper, we study tree automata for directed acyclic graphs (DAGs). We define the movement of a tree automaton on a DAG so that a DAG is accepted by a tree automaton if and only if the DAG has a spanning tree accepted by the tree automaton. We call this automaton a spanning tree automaton. The NP-completeness of the membership problem of DAGs for spanning tree automata is shown. However, if inputs are restricted to series–parallel graphs or generalized series–parallel graphs, it is shown that the membership problem for spanning tree automata is solvable in linear time.     

基于实时自动机的连续时段演算的验证

时段演算是描述和推导嵌入式实时系统和混成系统性质的一种区间时态逻辑.扩展线性时段不变式是时段演算的重要子集.针对实时自动机,提出一种连续时间语义下扩展线性时段不变式的有界模型检验方法.该方法将扩展线性时段不变式的有界模型检验问题转化为量词线性算术公式的正确性问题,从而可以采用量词消去技术进行求解.首先,运用符号化的思想,在实时自动机上利用深度优先搜索找到所有满足观测时长约束的符号化路径片段;然后,将每条符号化路径片段转化为一个量词线性算术公式;最后,利用量词消去工具求解.与已有工作相比,基于实时自动机设计了验证算法.另外,降低了验证复杂度,并且加速了验证过程的实际速度.     

Application of finite automatons for program testing

The application of the finite automaton theory to the problem of program testing is discussed. The problem is reduced to testing a finite automaton. Testing of automatons using their state graphs, factor graphs, testing using factor graphs, and methods for factor graphs construction are discussed.     

Path-planning strategies for a point mobile automaton moving amidst unknown obstacles of arbitrary shape

The problem of path planning for an automaton moving in a two-dimensional scene filled with unknown obstacles is considered. The automaton is presented as a point; obstacles can be of an arbitrary shape, with continuous boundaries and of finite size; no restriction on the size of the scene is imposed. The information available to the automaton is limited to its own current coordinates and those of the target position. Also, when the automaton hits an obstacle, this fact is detected by the automaton's “tactile sensor.” This information is shown to be sufficient for reaching the target or concluding in finite time that the target cannot be reached. A worst-case lower bound on the length of paths generated by any algorithm operating within the framework of the accepted model is developed; the bound is expressed in terms of the perimeters of the obstacles met by the automaton in the scene. Algorithms that guarantee reaching the target (if the target is reachable), and tests for target reachability are presented. The efficiency of the algorithms is studied, and worst-case upper bounds on the length of generated paths are produced.     

An adaptive automaton controller for discrete-time markov processes

The computation of an optimal feedback controller characteristic for a non-linear stochastic system may be facilitated by the use of a stochastic automaton as a system model. A problem of particular interest is that of a long duration stationary Markov process in which the state is observable but the process dynamics and disturbance characteristics are initially unknown. The determination of a suitable control algorithm, in the form of an adaptive automation in the feedback loop, is considered in this paper for such a process.

Since the algorithm is to be used on-line to perform simultaneously the functions of estimation and control, it must constitute an efficient convergent multi-stage dual control strategy. It is shown that an existing method for dual control of a repetitive single-stage stochastic process may be extended to apply to the present case. A method is introduced of calculating successive policy estimates recursively, so that the task of updating the estimated optimal feedback policy at each stage of the process is rendered feasible. The application of the automaton controller is illustrated by the simulated adaptive control of a non-linear conditionally stable heat treatment process disturbed by multiplicative noise.     

Fuzzy automaton finite state recognition

The fuzzy automaton finite state recognition problem is investigated. We introduced a generalized definition of a homing sequence for fuzzy automaton (FA). The investigated problem for FA belongs to the class of multicriteria problems, which distinguishes it from the analogous problem for classical finite state automatons. Algorithms for constructing generalized homing sequences that are optimal according to various criteria are proposed.     

Deterministic finite automata representation for model predictive control of hybrid systems

As is well known, the computational complexity in the mixed integer programming (MIP) problem is one of the main issues in model predictive control (MPC) of hybrid systems such as mixed logical dynamical systems. Thus several efficient MIP solvers such as multi-parametric MIP solvers have been extensively developed to cope with this problem. On the other hand, as an alternative approach to this issue, this paper addresses how a deterministic finite automaton, which is a part of a hybrid system, should be expressed to efficiently solve the MIP problem to which the MPC problem is reduced. More specifically, a modeling method to represent a deterministic finite automaton in the form of a linear state equation with a smaller set of binary input variables and binary linear inequalities is proposed. After a motivating example is described, a derivation procedure of a linear state equation with linear inequalities representing a deterministic finite automaton is proposed as three steps; modeling via an implicit system, coordinate transformation to a linear state equation, and state feedback binarization. Various significant properties on the proposed modeling are also presented throughout the proofs on the derivation procedure.     

Inclusion dynamics hybrid automata

Hybrid systems are dynamical systems with the ability to describe mixed discrete-continuous evolution of a wide range of systems. Consequently, at first glance, hybrid systems appear powerful but recalcitrant, neither yielding to analysis and reasoning through a purely continuous-time modeling as with systems of differential equations, nor open to inferential processes commonly used for discrete state-transition systems such as finite state automata. A convenient and popular model, called hybrid automata, was introduced to model them and has spurred much interest on its tractability as a tool for inference and model checking in a general setting. Intuitively, a hybrid automaton is simply a “finite-state” automaton with each state augmented by continuous variables, which evolve according to a set of well-defined continuous laws, each specified separately for each state. This article investigates both the notion of hybrid automaton and the model checking problem over such a structure. In particular, it relates first-order theories and analysis results on multivalued maps and reduces the bounded reachability problem for hybrid automata whose continuous laws are expressed by inclusions (x′f(x,t)) to a decidability problem for first-order formulæ over the reals. Furthermore, the paper introduces a class of hybrid automata for which the reachability problem can be decided and shows that the problem of deciding whether a hybrid automaton belongs to this class can be again decided using first-order formulæ over the reals. Despite the fact that the bisimulation quotient for this class of hybrid automata can be infinite, we show that our techniques permit effective model checking for a nontrivial fragment of CTL.     

基于混杂模型的上下文相关主机入侵检测系统

主机入侵检测的关键是监测进程的运行是否正常.现有的基于静态分析建模的方法具有零虚警的优良特性,但是,由于缺乏精确性或者效率的问题仍然不能实际使用,先前的工作试图在这两者之间寻找平衡点.基于NFA(nondeterministic finite automaton)的方法高效但是不够精确,基于PDA(push down automaton)的方法比较精确但却由于无限的资源消耗而不能应用.其他模型,例如Dyck模型、VPStatic模型和IMA模型使用一些巧妙的方法提高了精确性又不过分降低可用性,但是都回避了静态分析中遇到的间接函数调用/跳转问题.提出一种静态分析-动态绑定的混杂模型(hybrid finite automaton,简称HFA)可以获得更好的精确性并且解决了这一问题.形式化地与典型的上下文相关模型作比较并且证明HFA更为精确,而且HFA更适合应用于动态链接的程序.还给出了基于Linux的原型系统的一些实现细节和实验结果.     

基于元胞自动机模型的域间路由仿真分析

由于域间路由系统的大规模性和拓扑关系的复杂性,使得分析宏观路由行为成为一个难题。提出一种基于元胞自动机模型的域间路由仿真模型,用于分析域间路由系统的宏观行为。研究结果表明,仿真模型在一定程度上可以较好地反映域间路由系统的宏观行为特征。仿真结果发现,在域间路由系统中,小范围短时间的不稳定路由行为经过广泛传播,会导致整个路由系统出现不良系统行为。     

有限自动机可识别语言的基数

利用有向图的邻接矩阵研究有限自动机的可识别语言的基数问题。通过建立有限自动机的可识别语言与其有向图中从初始结点（有限自动机的初始状态）到终止结点（有限自动机的终止状态）的路的一一对应关系,利用邻接矩阵给出了有限自动机的可识别语言的基数公式,研究了两个自动机不等价的充分条件。