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

Algebraic Properties of Probabilistic Finite Automata

研究了概率有限自动机的同态(弱同态)、有效划分等代数性质.首先,提出了完全的、不可约的概率有限自动机,概率有限自动机的并积等概念.然后,讨论了两个概率有限自动机的级联积、圈积、并积的有效划分与其因子的有效划分之间的关系,证明了在一定条件下两个概率有限自动机的级联积(并积)的商概率有限自动机与其因子的商概率有限自动机的级联积(并积)是相等的.最后,得到了概率有限自动机的极大有效划分的一个刻画.

In this paper,algebraic properties such as homomorphism（weak homomorphism）,effectively partition of probabilistic finite automata are investigated.Firstly,the concepts of complete and irreducible probabilistic finite automata,join of probabilistic finite automata and so on are put forward.Then,the relationship between the effectively partitions of cascade product,wreath product,join of probabilistic finite automata and their factors are given,quotient probabilistic finite automata of cascade product（join） of probabilistic finite automata is equal to cascade product（join） of their factor＇ s quotient probabilistic finite automata under certain conditions is proved.Finally,a characterization on maximum effectively partition of probabilistic finite automata is obtained.