Algebraic Properties of Probabilistic Finite State Automata

Probabilistic finite state automata(PFA)is widely used today in a variety of areas in pattern recognition, or in fields to which pattern recognition is linked：computational linguistics, machine learning, time series analysis, circuit testing, computational biology, speech recognition, and machine translation are some of them. In this paper, algebraic properties of PFA are studied by using algebraic tools such as matrices, homomorphisms, isomorphisms, congruences, and so on. Firstly, the concept of congruences of two strings over input alphabet is defined, and some equivalent characterizations of congruences of two strings are given by probabilistic transition matrices.Secondly, notions of homomorphisms and isomorphisms of PFA are introduced, and homomorphism theorem of PFA is shown. It is also proved that two PFA are isomorphic if and only if their probabilistic transition matrices can be transformed into each other by the first kind of elementary transformation of rows and columns. The concept of products and sums of PFA is defined, and the homomorphism relationships between products and sums of PFA are investigated. Finally, the concept of commutativity of fuzzy finite state machines is introduced for PFA, and several equivalent characterizations of commutativity of PFA are obtained as well as the sufficient and necessary conditions of the commutativity of products and sums of PFA by probabilistic transition matrices.