Programmable finite automata for VLSI†
K. Culik, Helmut Jürgensen · International Journal of Computer Mathematics · 1983
We describe a method VLSI for design of programmable finite automata. For any fixed k it can be programmed to deterministically simulate a non-deterministic finite auto- maton with at most k states. For some constant c it runs in time on inputs of length n>b and in time on inputs of length n≧b where b is a constant influencing the size of the realisation, which can be chosen so that ck is much smaller than b. The design is modular, it consists of 0(bk 2) identical processes connected in a uniform manner.