Probabilistic finite-state machines - Part I

Probabilistic finite- state machines are 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 Part I of this paper, we survey these generative objects and study their definitions and properties. In Part II, we will study the relation of probabilistic finite- state automata with other well- known devices that generate strings as hidden Markov models and n- grams and provide theorems, algorithms, and properties that represent a current state of the art of these objects.