Article
Lower Bounds on the Area of Finite-State Machines
Information Processing Letters
Document Type
Article
Publication Date
1-1-1989
Pages
1-7
Publisher Name
Elsevier
Disciplines
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.
Creative Commons License
Creative Commons Attribution-Noncommercial-No Derivative Works 3.0
Copyright Statement
Copyright © 1989 Elsevier B.V.
Citation Information
M. J. Foster and Ronald I Greenberg. "Lower Bounds on the Area of Finite-State Machines" Information Processing Letters Vol. 30 Iss. 1 (1989) Available at: http://works.bepress.com/ronald-greenberg/36/
Author Posting. © Elsevier, 1989. This is the author's version of the work. It is posted here by permission of Elsevier for personal use, not for redistribution. The definitive version was published in Information Processing Letters, Volume 30, Issue 1, 16 January 1989, Pages 1-7, http://dx.doi.org/10.1016/0020-0190(89)90165-8.