概率有限自动机的积和分解

给出几种概率有限自动机的积,讨论了他们之间的相互关系,并在文献[1]的基础上利用这些积给出匀概率有限自动机的分解,证明了一个匀概率有限自动机可以分解为一个随机编码源、一个伯努利过程和一些确定有限自动机的串联积。     

On the efficient construction of quasi-reversible automata for reversible languages

Quasi-reversible automata is a suitable representation for reversible languages. In this work a method is proposed to obtain such an automaton for any given reversible language represented by its minimal DFA. Our method runs in polynomial time respect to the size of the minimal DFA and improves a previous exponential method. Previous bound for the size of quasi-reversible automata is also reduced.     

On characteristic sets and degrees of finite automata

The characteristic sets and degrees of finite automata are notions used by Biermann for his finite automaton learner. Some fundamental properties and relations of these notions are considered. A necessary and sufficient condition under which his learner converges to an expected automaton is given.     

Inequality of finite behaviors of rational weight finite automata is in R

Inequivalence of finite automata accepting finite languages over a non-unary alphabet is NP-complete. However, the inequality of their behaviors does not appear to have been carefully investigated. In the simplest case, the behavior of a finite automaton is the formal series f such that the coefficient f(w) of a word w is the number of distinct accepting computations on w. This notion will be generalized in the paper to finite automata with rational weights. The main result is that inequality of rational weight finite automata with finite behaviors is in R, random polynomial time.     

The formal definition of semantics by string automata

An abstract machine called a string automaton (SA) is introduced in this paper. SAs are motivated by the need to formally define the semantics of programming languages in a manner accessible to the users of the language. The SA notation can be used to represent functions and computations in a clear, concise, graphical, and natural manner. After the class of SAs has been formally defined, it is shown how logic modules (resembling hardware circuit elements) and function modules (which define functions) can be expressed by SAs. Networks of SAs and their application to the construction of parsers is discussed. The definition of the language and hardware components of an interactive programming system by means of SAs is outlined.     

General method of testing the compatibility of interacting automata with finite memory

A method is proposed for compatibility analysis of two interacting partial nondeterministic automata A and B specified in a first-order language with monadic predicates. In contrast to a method proposed earlier, no restrictions are imposed on the form of specification of the automaton B. These investigations were partially supported by INTAS grant 96-0760. Translated from Kibernetika i Sistemnyi Analiz, No. 6, pp. 25–37, November–December, 1999.     

RaRb Transformation of Compound Finite Automata over Commutative Rings

Some results on RaRb transformation of compound finite automata over finite field are generalized to the case of commutative rings.Properties of RaRb transformation are discussed and applied to the inversion problem for compound finite automata.     

Input-trees of finite automata and application to cryptanalysis

In this paper,Weights of output set and of input set for finite automata are discussed.For a weakly invertible finite automaton,we prove that for states with minimal output weight,the distruibution of input sets is uniform.Then for a kind of compound finite automata,we give weights of output set and of input set explicitly,and a characterization of their input-trees.For finite automaton public key cryptosystems,of which automata in public keys belong to such a kind of compound finite automata,we evaluate search amounts of exhaust search algorithms in average case and in worse case for both encryption and signature,and success ful probabilities of stochastic search algorithms for both encryption and signature.In addition,a result on mutual invertibility of inite automata is also given.     

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.     

格值有限状态自动机的半群

提出了格值有限状态自动机的定义,给出了格值有限状态自动机的两种同余关系,研究了格值有限状态自动机的半群的若干性质,最后给出了两种有限半群E(A)和E(A)的关系。     

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

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

Performance of hardcoded finite automata

We study the performance of a hardcoded algorithm for recognizing strings of a finite automaton's language and compare it with the use of the more conventional table‐driven algorithm. In both cases, performance depends on the finite automaton's dimensions such as alphabet size and the number of states. However, the respective processing mechanisms that influence the performance, in particular cache memory usage, depend on the details of the processor's underlying architecture. In the hardcoded case, the automaton's dimensions determine the size of the code which is, in turn, the primary determinant of the way in which cache memory is used. In the table‐driven case, cache memory usage is primarily determined by the way in which portions of the transition table are stored in it. Using statistical regression analysis, we provide multivariate equations to model the observed time efficiency of both methods. The equations obtained are cross‐compared and conclusions are drawn. Copyright © 2006 John Wiley & Sons, Ltd.     

Structure of Weakly Invertible Semi-Input-Memory Finite Automata with Delay 1

Semi-input-memory finite automata,a kind of finite automata introduced by the first author of this paper for studying error propagation ,are a generalization of inputmemory finite automata ,by appending an autonomous finite automation component .In this paper,we give a characterization of the structure of weakly invertible semi-input-memory finite automata with delay 1,in which the state graph of each autonomous finite automation is cycle,From a result on mutual invertibility of finite automata obtained by th authors recently,it leads to a characerization of the structure of feedfoward inverse finite automata with delay 1.     

一类格值自动机的极小化

给出了格值自动机的同余和同态,从代数角度出发详细研究了同余和同态关系的代数性质,揭示了格值自动机的代数性质和取值格半群的紧密联系,利用同余和同态关系最终研究了格值自动机的极小化问题,在正则同余下给出了可在有限步实现具有模糊初始状态和特殊模糊终状态的自动机极小化的算法。     

Temporal determinization of mutating finite automata: Reconstructing or restructuring

A mutating finite automaton (MFA) is a nondeterministic finite automaton (NFA) that changes its morphology over discrete time by a sequence of mutations. This results in a sequence of NFAs, the initial NFA, and one mutated NFA for each mutation. Some application domains, including model-based diagnosis of discrete-event systems in artificial intelligence and model-based testing in software engineering, require temporal determinization of MFAs. Determinizing an MFA temporally means generating a deterministic finite automaton (DFA) that is equivalent to the mutated NFA as soon as a mutation occurs. Since, in computation time, the classical Subset Construction determinization algorithm may be less than optimal when applied to MFAs, a conservative algorithm is proposed, called Subset Restructuring, which, instead of constructing the new DFA from scratch based on the mutated NFA, generates the new DFA by updating the previous DFA based on the mutation occurred. Subset Restructuring is sound and complete, thereby yielding the same DFA generated by Subset Construction. Results from massive experimentation indicate the viability of Subset Restructuring, especially so when large MFAs change by small mutations.     

Structure of weakly invertible semi-input-memory finite automata with delay 2

Semi-input-memory finite automata,a kind of finite automata introduced by the author of this paper for studying error propagation,are a generalization of input-memory finite automata by appending an autonomous finite automaton component.This paper gives a characterization on the structure of weakly invertible semi-input-memory finite automata with delay 2 in which input alphabets and output alphabets have two elements and autonomous finite automata are cyclic.For the structure of feedforward inverse finite automata with delay 2,Zhu first gave a characterization;from a result on mutual invertibility of finite automata,the result mentioned above also leads to a different characterization on the structure of feedforward result mentioned above also leads to a different characterization on the structure of feedforward inverse finite automata with delay 2.