Lower Bounds on the Area of Finite-State Machines

M. J. Foster; Ronald I Greenberg

doi:10.1016/0020-0190(89)90165-8

Lower Bounds on the Area of Finite-State Machines

M. J. Foster, Ronald I Greenberg

Department of Computer Science

Research output: Contribution to journal › Article › peer-review

Abstract

There are certain straightforward algorithms for laying out finite-state machines. This paper shows that these algorithm are optimal in the worst case for machines with fixed alphabets. That is, for any s and k , there is a deterministic finite-state machine with s states and k symbols such that any layout algorithm requires Ω(ks log s) area to lay out its realization. Similarly, any layout algorithm requires Ω(ks^2) area in the worst case for nondeterministic finite-state machines with s states and k symbols.

Original language	American English
Journal	Computer Science: Faculty Publications and Other Works
Volume	30
Issue number	1
DOIs	https://doi.org/10.1016/0020-0190(89)90165-8
State	Published - Jan 1 1989

Keywords

Custom VLSI
layout algorithms
regular languages
finite-state machines
lower bounds
silicon compilers

Disciplines

Computer Sciences
Theory and Algorithms
VLSI and Circuits, Embedded and Hardware Systems

Access to Document

10.1016/0020-0190(89)90165-8License: Unspecified

Lower Bounds on the Area of Finite-State MachinesFinal published version, 3.22 MBLicense: Unspecified

http://dx.doi.org/10.1016/0020-0190(89)90165-8

Cite this

@article{f4659305bbd34bb68a6ee8ec0801ad97,

title = "Lower Bounds on the Area of Finite-State Machines",

abstract = " There are certain straightforward algorithms for laying out finite-state machines. This paper shows that these algorithm are optimal in the worst case for machines with fixed alphabets. That is, for any s and k , there is a deterministic finite-state machine with s states and k symbols such that any layout algorithm requires Ω(ks log s) area to lay out its realization. Similarly, any layout algorithm requires Ω(ks^2) area in the worst case for nondeterministic finite-state machines with s states and k symbols.",

keywords = "Custom VLSI, layout algorithms, regular languages, finite-state machines, lower bounds, silicon compilers",

author = "Foster, {M. J.} and Greenberg, {Ronald I}",

year = "1989",

month = jan,

day = "1",

doi = "10.1016/0020-0190(89)90165-8",

language = "American English",

volume = "30",

journal = "Computer Science: Faculty Publications and Other Works",

number = "1",

}

TY - JOUR

T1 - Lower Bounds on the Area of Finite-State Machines

AU - Foster, M. J.

AU - Greenberg, Ronald I

PY - 1989/1/1

Y1 - 1989/1/1

N2 - There are certain straightforward algorithms for laying out finite-state machines. This paper shows that these algorithm are optimal in the worst case for machines with fixed alphabets. That is, for any s and k , there is a deterministic finite-state machine with s states and k symbols such that any layout algorithm requires Ω(ks log s) area to lay out its realization. Similarly, any layout algorithm requires Ω(ks^2) area in the worst case for nondeterministic finite-state machines with s states and k symbols.

AB - There are certain straightforward algorithms for laying out finite-state machines. This paper shows that these algorithm are optimal in the worst case for machines with fixed alphabets. That is, for any s and k , there is a deterministic finite-state machine with s states and k symbols such that any layout algorithm requires Ω(ks log s) area to lay out its realization. Similarly, any layout algorithm requires Ω(ks^2) area in the worst case for nondeterministic finite-state machines with s states and k symbols.

KW - Custom VLSI

KW - layout algorithms

KW - regular languages

KW - finite-state machines

KW - lower bounds

KW - silicon compilers

UR - https://ecommons.luc.edu/cs_facpubs/95

U2 - 10.1016/0020-0190(89)90165-8

DO - 10.1016/0020-0190(89)90165-8

M3 - Article

VL - 30

JO - Computer Science: Faculty Publications and Other Works

JF - Computer Science: Faculty Publications and Other Works

IS - 1

ER -

Lower Bounds on the Area of Finite-State Machines

Abstract

Keywords

Disciplines

Access to Document

Other files and links

Cite this