Lower bounds on the area of finite-state machines (Q1115595)

There are certain straightforward algorithms for laying out finite-state machines. This paper shows that these algorithms 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 \(\Omega\) (ks log s) area to lay out its realization. Similarly, any layout algorithm requires \(\Omega (ks^ 2)\) area in the worst case for nondeterministic finite-state machines with s states and k symbols.