Title

Lower bounds on the area of finite-state machines

Document Type

Article

Publication Date

1-1989

Publication Title

Information Processing Letters

Volume

30

Issue

1

Pages

1-7

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.

Identifier

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

Creative Commons License

Creative Commons License
This work is licensed under a Creative Commons Attribution-Noncommercial-No Derivative Works 3.0 License.