加权有穷自动机的代数性质

在加权有穷自动机理论基础上,利用强同态的概念,证明两个加权有穷自动机在计算能力上是等价的,并在加权有穷自动机的状态集上建立一种等价关系,得到加权有穷自动机的商自动机,证明加权有穷自动机与其商自动机在计算能力上也是等价的。并通过引入加权有穷自动机的可交换性、分离性、(强)连通性及层的概念,讨论在(强)同态的条件下,两个加权有限状态机之间的可交换性、分离性、(强)连通性及层的关系。关键词：     

Efficient instruction scheduling using finite state automata

Modern compilers employ sophisticated instruction scheduling techniques to shorten the number of cycles taken to execute the instruction stream. In addition to correctness, the instruction scheduler must also ensure that hardware resources are not oversubscribed in any cycle. For a contemporary processor implementation with multiple pipelines and complex resource usage restrictions, this is not an easy task. The complexity involved in reasoning about such resource hazards is one of the primary factors that constrain the instruction scheduler from performing certain kinds of transformations that can result in improved schedules. We extend a technique for detecting pipeline resource hazards based on finite state automata, to support the efficient implementation of such transformations that are essential for aggressive instruction scheduling beyond basic blocks. Although similar code transformations can be supported by other schemes such as reservation tables, our scheme is superior in terms of space and time. A global instruction scheduler using these techniques was implemented in the KSR compiler. This work was begun while the authors were at Kendall Square Research (KSR).     

Mathematical logic and quantum finite state automata

This paper is a review of the connection between formulas of logic and quantum finite-state automata in respect to the language recognition and acceptance probability of quantum finite-state automata. As is well known, logic has had a great impact on classical computation, it is promising to study the relation between quantum finite-state automata and mathematical logic. After a brief introduction to the connection between classical computation and logic, the required background of the logic and quantum finite-state automata is provided and the results of the connection between quantum finite-state automata and logic are presented.     

Complexity of control on finite automata

We consider control questions for finite automata viewed as input/output systems. In particular, we find estimates of the minimal number of states of an automaton able to control a given automaton. We prove that, on average, feedback closed-loop control automata do not have fewer states than open-loop control automata when the control objective is to steer the controlled automaton to a target state. We compare our approach to other ways of formalizing of formalizing analogous control objectives.     

Optimal supervisory control under partial observation

In this paper, we formulate the optimal supervisory control problem (OSCP) under partial observation and propose an algorithm to design the optimal nonblocking supervisor (ONS). In addition, we introduce an extended net cost including the observation cost of the events which is taken into account for the cost of setting up a mechanism to sense the events and solve the OSCP with the extended net cost.     

Vector space formulation of probabilistic finite state automata

This paper develops a vector space model of a class of probabilistic finite state automata (PFSA) that are constructed from finite-length symbol sequences. The vector space is constructed over the real field, where the algebraic operations of vector addition and the associated scalar multiplication operations are defined on a probability measure space, and implications of these algebraic operations are interpreted. The zero element of this vector space is semantically equivalent to a PFSA, referred to as symbolic white noise. A norm is introduced on the vector space of PFSA, which provides a measure of the information content. An application example is presented in the framework of pattern recognition for identification of robot motion in a laboratory environment.     

Using finite state automata to produce self-optimization andself-control

A simple game provides a framework within which agents can spontaneously self-organize. In this paper, we present this game, and develop basic theory underlying a robust method for distributed coordination based on this game. This method makes use of finite state automata-one associated with each agent-which guide the agents. We give a new, general method of analysis of these systems, which previously had been studied only in limited cases. We also provide a physical example, which should hint at the type of problems resolvable using this method     

A state space approach to the finite automata

This paper proposes a state space approach for analyzing the finite automata. A Ψ-representation transforms a set of words into a formal power series for establishing the state equation of a finite automaton. We investigate the structure of the automaton via its corresponding state equation. It is shown that the solution of the state equation always exists and is unique. Furthermore, we prove that the solution field is a separable algebraic extension of the coefficient field. Finally, the concept of the substitution property of a partition is shown to be equivalent to that of invariant subspaces of the associated state space.     

Nonblocking supervisory control of state tree structures

It is well known that the nonblocking supervisory control problem is NP-hard, subject in particular to state space explosion that is exponential in the number of system components. In this paper we propose to manage complexity by organizing the system as a state tree structure (STS). STS are an adaptation of statecharts to supervisory control theory. Based on STS we present an efficient recursive symbolic algorithm that can perform nonblocking supervisory control design (in reasonable time and memory) for systems of state size 10/sup 24/ and higher. The resulting controllers are tractable and readily comprehensible.     

Grid automata and supervisory control of dense real-time discrete event systems

We present a generalization of the classical supervisory control theory for discrete event systems to a setting of dense real-time systems modeled by Alur and Dill timed automata. The main problem involved is that in general the state space of a timed automaton is (uncountably) infinite. The solution is to reduce the dense time transition system to an appropriate finite discrete subautomaton, the grid automaton, which contains enough information to deal with the timed supervisory control problem (TSCP). The plant and the specifications region graphs are sampled for a granularity defined in a way that each state has an outgoing transition labeled with the same time amount. We redefine the controllability concept in the context of grid automata, and we provide necessary and sufficient solvability conditions under which the optimal solution to centralized supervisory control problems in timed discrete event systems under full observation can be obtained. The enhanced setting admits subsystem composition and the concept of forcible event. A simple example illustrates how the new method can be used to solve the TSCP.     

Magic numbers in the state hierarchy of finite automata

A number d is magic for n, if there is no regular language for which an optimal nondeterministic finite state automaton (nfa) uses exactly n states and, at the same time, the optimal deterministic finite state automaton (dfa) uses exactly d states. We show that, in the case of unary regular languages, the state hierarchy of dfa’s, for the family of languages accepted by n-state nfa’s, is not contiguous. There are some “holes” in the hierarchy, i.e., magic numbers in between values that are not magic. This solves, for automata with a single letter input alphabet, an open problem of existence of magic numbers. Actually, most of the numbers is magic in the unary case. As an additional bonus, we also get a new universal lower bound for the conversion of unary d-state dfa’s into equivalent nfa’s: nondeterminism does not reduce the number of states below log² d, not even in the best case.     

Variable lookahead supervisory control with state information

In cases where the discrete-event system model has an infinite or large state space, or when it is not completely specified a priori, applying the traditional off-line methods for computing the control policy may be impractical, if not infeasible. We adopt an online limited lookahead approach. Under this approach, the next control action is determined based on an N-step ahead projection of the system behavior and on one of two attitudes-conservative or optimistic. We extend this approach to incorporate knowledge of the system state in the computation. This has the potential of improving the efficiency of the computation as well as the quality of the control policy. There are five specific contributions presented in this paper: 1) a new algorithm for the online computation of supervisory controls with worst case complexity that is quadratic in the number of “expanded” states, 2) an algorithmic proof of the correctness of this algorithm that avoids using fixed point methods and offers new insight into the structure of the supremal controllable sublanguage, 3) an off-line version based on a forward search technique that has the same worst case complexity as existing off-line algorithms but is potentially more efficient, 4) a formal proof of the fact that when the languages of interest are livelock free the computations are performed in linear complexity, and 5) new bounds on the depth of the lookahead window that guarantee optimality     

Some tractable supervisory control problems for discrete-eventsystems modeled by Buchi automata

Discrete-event systems (DES) are modeled by Buchi automata together with a means of online control. In this setting the concept of a controllable language is extended to infinite strings, and conditions for the existence of a supervisor (controller) to implement a prescribed closed-loop behavior are derived. The focus is on a class of DES called product systems. These are DES composed of a finite set of asynchronous components. A control problem for such a system typically requires the synthesis of an online controller so as to achieve some prescribed coordinated behavior of the component subsystems. One of the principal difficulties in this task is that the size of the state space increases exponentially with the number of components. It is shown that despite this fact several interesting control synthesis problems for such systems are computationally feasible, and algorithms are developed for solution     

Head and state hierarchies for unary multi-head finite automata

Unary deterministic one-way multi-head finite automata characterize the unary regular languages. Here they are studied with respect to the existence of head and state hierarchies. It turns out that for any fixed number of states, there is an infinite proper head hierarchy. In particular, the head hierarchy for stateless deterministic one-way multi-head finite automata is obtained using unary languages. On the other hand, it is shown that for a fixed number of heads, \(m+1\) states are more powerful than \(m\) states. Finally, the open question of whether emptiness is undecidable for stateless one-way two-head finite automata is addressed and, as a partial answer, undecidability can be shown if at least four states are provided.     

基于有限状态自动机的服务组合模型

分析了目前服务计算的研究现状和存在的问题，在D Berardi和A Wombacher的基础上提出了一种带条件的有限状态自动机模型cFSA（Finite State Automata with condition），并给出了基于cFSA的服务理论模型．在该服务理论模型的基础上提出了一种基于有限状态自动机的服务组合形式化模型，并给出了该模型的代数性质和实现方法．     

Optimal adaptive LQG control for systems with finite state process parameters

The situation where a totally observed process ytis generated by a stochastic differential equation whose parameters evolve on a finite set{1, ... N}according to a stochastic differential equation is considered. The optimal control law is sought with respect to quadratic loss functions on ytand the control ut. The auxiliary P.D.E. technique of Hijab [6] is used together with a nonlinear filter to obtain the solution whose existence depends upon that of a smooth solution to the auxiliary P.D.E. and strong solutions to the system S.D.E. under the given control inputs.     

Performing automatic target detection with evolvable finite state automata

In this paper, a novel approach for performing classification is presented. Discriminant functions are constructed by combining selected features from the feature set with simple mathematical functions such as +, −, ×, ÷ , max, min. These discriminant functions are capable of forming non-linear discontinuous hypersurfaces. For multimodal data, more than one discriminant function may be combined with logical operators before classification is performed. An algorithm capable of making decisions as to whether a combination of discriminant functions is needed to classify a data sample, or whether a single discriminant function will suffice, is developed. The algorithms used to perform classification are not written by a human. The algorithms are learnt, or rather evolved, using evolutionary computing techniques.     

基于有限状态自动机的藏文音节组织研究

通过对藏文的字形特征、拼写规律,以及文法规则的分析和研究,实现藏文词语的实时检错.借助形式语言有限状态自动机的方法,对藏文字结构中的基字、前加字、上加字、下加字、后加字、再后加字之间的搭配规则设计了状态图和邻接矩阵.该方法提高了藏文文本质量,使原本复杂的书面语法规则变得简单直观,从而使符合现代藏文音节组织结构的词语能实时检错.该研究为实现藏文的自动校对提供了基础.     

时钟有限自动机模型及其演化算法

传统分布仿真系统时钟不一致影响因素分析方法,已不能满足当前面向服务分布仿真的时钟状态分析需要。从系统全局时钟演化出发,阐述了时钟状态演化内涵与过程;在此基础上,基于有限自动机理论,提出了用于时钟不一致影响因素量化分析的动态演化模型及其算法:时钟有限自动机CFSA和时钟一致性演化算法CCEA。仿真实验表明:相比传统的分析方法,使用CFSA模型及其CCEA演化算法刻画系统时钟一致性状态变迁过程,探寻各种不一致因素的影响机理,量化分析各因素的影响程度等具有可行性、有效性和新颖性,可为面向服务分布仿真中时钟同步算法设计提供指导性建议。