Incremental encoding for optimal implementation and decomposition of FSM's. Algorithms for encoding states of FSMs often use dichotomy-based based techniques. At each step one more bit of the encoding is specified by choosing a two-block partition of the set of states. Incremental encoding is a technique based on constructing the final code space from smaller code spaces . At each step of the algorithm, submachines are merged and then the FSM obtained by merging is re-encoded.
Incremental encoding has three advantages.
First, at each stage the submachines are encoded and so it is possible to evaluate precisely the quality of the encoding being constructed. Second, we have a lot of freedom in choosing which submachines to merge, allowing the exploration of a large solution space. Third, when merging submachines it is possible to transform the encodings chosen for the submachines in order to improve the encoding of the machine after merging No algorithm has ever made use of these three advantages of incremental encoding. Algoritmy sinteza avtomatov. Radio i Svyaz, Moskva, 1987.