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.

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.

Creative Commons License

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

Share

COinS