Lower bound study on interconnect complexity of the decomposed finite state machines

W. L. Yang, R. M. Owens, M. J. Irwin

Research output: Contribution to journalArticlepeer-review


Various strategies for multiway general decomposition have been investigated in the past. These strategies differ in how they reflect the cost of a logic level implementation. In the paper the authors are concerned with the lower bound on the number of interconnecting wires that must exist when a machine is decomposed into several submachines. From a VLSI implementation point of view, having a cost function based at least in part on interconnect complexity would be advantageous. The authors present a way to establish this bound for the multiway decomposition of an arbitrary machine, and tabulate the bound for a number of benchmarks. This tabulation shows that many large benchmarks are highly decomposable from an interconnect point of view.

Original languageEnglish (US)
Pages (from-to)332-336
Number of pages5
JournalIEE Proceedings: Computers and Digital Techniques
Issue number5
StatePublished - Sep 1 1995

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Hardware and Architecture
  • Computational Theory and Mathematics


Dive into the research topics of 'Lower bound study on interconnect complexity of the decomposed finite state machines'. Together they form a unique fingerprint.

Cite this