一个单向量子有限自动机接受概率问题的研究

单向量子有限自动机是实现量子计算机的最有可能的理论模型之一,其识别能力与其接受语言的概率之间存在矛盾,本文构造了一个特别的单向量子有限自动机充分说明了这一点.     

弱可逆有限自动机的分解

有限自动机公开钥密码体制的提出进一步激励了有限自动机可逆性的研究．在有限自动机公开钥密码体制中首次提出了自动机化合的概念．易知,两个弱可逆有限自动机的化合仍然是一个弱可逆有限自动机并且它的延迟步数不大于前两个有限自动机延迟步数之和．然而,另一方面,如何将一个弱可逆有限自动机分解为两个弱可逆有限自动机的化合却是一个非常困难的问题．该文主要考虑了一类n元严格延迟τ步弱可逆有限自动机M的延迟步数的分解问题．给出了一类特殊的n元弱可逆有限自动机分解的条件和结果．首先证明了如果对M中的每个状态s有T（s,τ）枝等,则M可分解为τ个延迟1步弱可逆有限自动机的化合．然后证明了M可分解为一个τ—m步弱可逆有限自动机和m阶延迟元的充要条件是对M中的每个状态s有T（s,m）枝等．     

概率有限状态自动机的代数性质

利用矩阵、同态、同构、同余等代数工具研究概率有限状态自动机的代数性质.首先定义了输入集上两个字符串同余的概念,并利用概率转移矩阵给出2个字符串同余的一些等价刻画.进而提出概率有限状态自动机同态和同构的概念,并给出了概率有限状态自动机同态定理.证明了2个概率有限状态自动机同构的充要条件是它们的概率转移矩阵可以通过第1种行列初等变换相互转化;同时提出了2个概率有限状态自动机积与和的概念,并得到了积自动机、和自动机的同态关系.最后将模糊自动机中交换的概念引入到概率有限状态自动机中,并利用概率转移矩阵给出了此类自动机交换的一些等价刻画以及和自动机、积自动机交换的充要条件.     

分解弱可逆有限自动机的两个结果

研究弱可逆有限自动机的分解可以为分析有限自动机公开钥密码体制的安全性提供一种重要途径.从输出权的角度研究了n元延迟τ步弱可逆有限自动机M的分解问题,首先证明了其可分 解为一个延迟0步弱可逆有限自动机和一个τ阶延迟元当且仅当M的所有状态的长τ输出权为 1. 其次, 在获得一类不可分解出延迟元的弱可逆有限自动机的基础上,构造出一个反例, 否 定回答了鲍丰在1993年提出的一个公开问题.同时给出了二元严格延迟τ 步强连通弱可逆有 限自动机可分解为一个严格延迟τ-1步弱可逆有限自动机和一个严格延迟1步弱可逆有限自 动机的一个充分条件.     

弱可逆线性有限自动机的一种分解

讨论有限自动机的分解有助于分析弱可逆有限自动机的结构和求解弱逆.首先证明了弱同构的弱可逆有限自动机具有相似的分解形式;接着考虑了一类特殊的弱可逆线性有限自动机的分解, 从状态输出权的角度刻画了该分解存在的一个充分条件;然后把这种分解形式推广到了一般的弱可逆线性有限自动机上, 即:延迟τ步弱可逆线性有限自动机分解成延迟0步弱可逆有限自动机和一种特殊的有限自动机M\\-D, 并得到了分解存在的充要条件;最后, 用输出序列的代数性质来刻画其中的充分条件, 并把它转化成了一个矩阵的秩的计算.这种分解形式并不局限于n元弱可逆有限自动机, 而且分解条件也比较简单, 仅与输出序列的性质有关.     

二元弱可逆有限自动机延迟步数的分解

本文考虑二元严格延迟τ步弱可逆有限自动机Ｍ的延迟步数的分解问题。首先证明如果Ｍ强连通且所有状态的延迟步数不小于τ－１，则Ｍ一定能分解为一个延迟０步弱可逆有限自动机和一个τ阶延迟元。然后证明如果Ｍ所有状态延迟步数均不小于ｍ，那么Ｍ可以分解为一个严格延τ－ｍ步弱可逆有限自动机和一个ｍ阶延迟元。最后考虑了Ｍ可分解为一个严格延迟τ－１步和一个严格延迟１步弱可逆有限自动机的条件。     

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

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

关于弱可逆有限自动机延迟步数分解的两个结果

本文证明存在(任意元)延迟2步弱可逆有限自动机不等价于任何两个延迟1步弱可逆有限自动机的化合的任何子自动机。因而说明了不是对所有的弱可逆有限自动机,延迟步数都是可分解的,但对所有状态的延迟步数均为2的二元延迟2步弱可逆有限自动机,则分解是可行的。     

有限自动机定义函数的线性本原圈积分解

本文讨论有限自动机显表出定义函数ｆ的线性本原圈积分解问题。在该圈积分解之下,函数ｆ被表成线性外函数因子ｆＬ与线性本原内涵数因子ｆＮ的圈积,这里函数ｆＬ定义了一个线性弱可逆有限自动机ＭｆＬ,而函数ｆＮ定义了一个非线性有限自动机ＭｆＮ且其不能再分解成一非平凡的线性外函数与一非线性内函数的圈积。本文证明了一函数ｆ的任两线性本原内因子互为对方的线性本原内因子,从而证明了函数ｆ的线性本原圈积分解的唯一性。本     

A note on two-dimensional probabilistic finite automata

This note introduces two-dimensional probabilistic finite automata (2-pfa's), and investigates several properties of them. We first show that the class of sets recognized by 2-pfa's with bounded error probability, 2-PFA, is incomparable with the class of sets accepted by two-dimensional alternating finite automata. We then show that 2-PFA is not closed under row catenation, column catenation, row +, and column + operations in Siromoney et al. (G. Siromoney, R. Siromoney, K. Krithivasan, Inform. and Control 22 (1973) 447).     

Reachability and controllability analysis of probabilistic finite automata via a novel matrix method

Probabilistic finite automata (PFAs) can exhibit a stochastic behavior, and its reachability and controllability is viewed as the first necessary step of supervisory control and stabilization. In this paper, the problems of reachability and controllability of PFAs are investigated under the framework of semi‐tensor product (STP) of matrices. First, a matrix‐based modeling approach to PFAs is proposed, and the dynamics of PFAs can be described as a discrete‐time bilinear expression. Meanwhile, the notions of reachability with a probability of one is formally defined, and F‐reachability with a probability of one is introduced. With the algebraic expression, necessary and sufficient conditions of such reachability are provided systematically. Second, F‐set controllability with a probability of one of PFAs is developed by introducing the F‐reachability with a probability of one, and the associated algebraic condition to verify such controllability are given. Finally, a simple example is illustrated to validate the proposed results.     

Wavelet-based feature extraction using probabilistic finite state automata for pattern classification

Real-time data-driven pattern classification requires extraction of relevant features from the observed time series as low-dimensional and yet information-rich representations of the underlying dynamics. These low-dimensional features facilitate in situ decision-making in diverse applications, such as computer vision, structural health monitoring, and robotics. Wavelet transforms of time series have been widely used for feature extraction owing to their time-frequency localization properties. In this regard, this paper presents a symbolic dynamics-based method to model surface images, generated by wavelet coefficients in the scale-shift space. These symbolic dynamics-based models (e.g., probabilistic finite state automata (PFSA)) capture the relevant information, embedded in the sensor data, from the associated Perron-Frobenius operators (i.e., the state-transition probability matrices). The proposed method of pattern classification has been experimentally validated on laboratory apparatuses for two different applications: (i) early detection of evolving damage in polycrystalline alloy structures, and (ii) classification of mobile robots and their motion profiles.     

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-dimensional finite automata and unacceptable functions

In this note, we first introduce the concept of “functions acceptable by two-dimensional finite automata” and then give several functions unacceptable by two-dimensional finite automata.     

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.     

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

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