Document Type
Article
Publication Date
1-1989
Publication Title
Information Processing Letters
Volume
30
Issue
1
Pages
1-7
Publisher Name
Elsevier
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.
Recommended Citation
Foster, M. J. and Greenberg, Ronald I.. Lower Bounds on the Area of Finite-State Machines. Information Processing Letters, 30, 1: 1-7, 1989. Retrieved from Loyola eCommons, Computer Science: Faculty Publications and Other Works, http://dx.doi.org/10.1016/0020-0190(89)90165-8
Creative Commons License
This work is licensed under a Creative Commons Attribution-Noncommercial-No Derivative Works 3.0 License.
Copyright Statement
Copyright © 1989 Elsevier B.V.
Comments
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.