State splitting and state merging in probabilistic finite state automata

Patrick Adenis, Kushal Mukherjee, Asok Ray

Research output: Chapter in Book/Report/Conference proceedingConference contribution

11 Scopus citations


Probabilistic finite state automata (PFSA) are constructed from symbol sequences for modeling the behavior of dynamical systems. This paper presents construction of finite history automata from symbol sequences; such automata, called D-Markov machines, are structurally simple and computationally efficient. The construction procedure is based on: (i) state splitting that generates symbol blocks of different lengths according to their relative importance; and (ii) state merging that assimilates histories from symbol blocks leading to the same symbolic behavior. A metric on probability distribution of symbol blocks is introduced for trade-off between modeling performance and the number of PFSA states. These algorithms have been tested by two examples.

Original languageEnglish (US)
Title of host publicationProceedings of the 2011 American Control Conference, ACC 2011
PublisherInstitute of Electrical and Electronics Engineers Inc.
Number of pages6
ISBN (Print)9781457700804
StatePublished - 2011

Publication series

NameProceedings of the American Control Conference
ISSN (Print)0743-1619

All Science Journal Classification (ASJC) codes

  • Electrical and Electronic Engineering


Dive into the research topics of 'State splitting and state merging in probabilistic finite state automata'. Together they form a unique fingerprint.

Cite this