Closed Partition Lattice and Machine Decomposition

Finite state machines are widely used to model systems in diverse areas. Often the modeling machines can be decomposed into smaller component machines, and this decomposition can facilitate the system design, implementation and analysis. Hartmanis and Stearns developed an elegant algebraic theory for machine decomposition that is based on the closed partition lattice of a machine. In this paper we study the computation of the closed partition lattice of finite state machines for the application to their decomposition. We present efficient algorithms for constructing the closed partition lattice and for machine decomposition.