Title :
Application of the principal partition and principal lattice of partitions of a graph to the problem of decomposition of a finite state machine
Author :
Narayanan, Subir Roy H
Author_Institution :
Dept. of Electr. Eng., Indian Inst. of Technol., Bombay, India
Abstract :
The authors relate the principal partition of a graph G to the problem of finite state machine (FSM) decomposition by modeling the FSM as a state transition graph (STG) and using the underlying graph of its STG. They obtain efficient algorithms to decompose a FSM by relating the principal partition to the more general notion of the principal lattice of partitions of an appropriately defined submodular function
Keywords :
finite state machines; graph theory; logic partitioning; state assignment; decomposition; finite state machine; principal lattice of partitions; principal partition; state transition graph; submodular function; Bipartite graph; Buildings; Cellular neural networks; Identity-based encryption; Lattices; Prototypes;
Conference_Titel :
Circuits and Systems, 1993., ISCAS '93, 1993 IEEE International Symposium on
Conference_Location :
Chicago, IL
Print_ISBN :
0-7803-1281-3
DOI :
10.1109/ISCAS.1993.394289
