Information Processing Letters
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.
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 © 1989 Elsevier B.V.