Structural transformations of probabilistic finite state machines

Abstract

Probabilistic finite state machines have recently emerged as a viable tool for modelling and analysis of complex non-linear dynamical systems. This paper rigorously establishes such models as finite encodings of probability measure spaces defined over symbol strings. The well known Nerode equivalence relation is generalized in the probabilistic setting and pertinent results on existence and uniqueness of minimal representations of probabilistic finite state machines are presented. The binary operations of probabilistic synchronous composition and projective composition, which have applications in symbolic model-based supervisory control and in symbolic pattern recognition problems, are introduced. The results are elucidated with numerical examples and are validated on experimental data for statistical pattern classification in a laboratory environment.

Acknowledgements

The authors would like to thank Dr. Eric Keller for his valuable contribution in obtaining the experimental results.

This work has been supported in part by the U.S. Army Research Office under Grant Nos. W911NF-06-1-0469 and W911NF-07-1-0376.