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

fYear

1993

fDate

3-6 May 1993

Firstpage

2564

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;

fLanguage

English

Publisher

ieee

Conference_Titel

Circuits and Systems, 1993., ISCAS '93, 1993 IEEE International Symposium on

Conference_Location

Chicago, IL

Print_ISBN

0-7803-1281-3

Type

conf

DOI

10.1109/ISCAS.1993.394289

Filename

394289

Link To Document

https://search.isc.ac/dl/search/defaultta.aspx?DTC=49&DC=2614256