In this article we consider a basic problem in the layout of VLSI-circuits, the channel-routing problem in the knock-knee mode. We show that knock-knee channel routing with 3-terminal nets is NP-complete and thereby settling a problem that was open for more than a decade. In 1987, Sarrafzadeh showed that knock-knee ... more >>>

One of the most basic pattern recognition problems is whether a certain local feature occurs in some linear array to the left of some other local feature. We construct in this article circuits that solve this problem with an asymptotically optimal number of threshold gates. Furthermore it is shown that ... more >>>

We introduce em total wire length as salient complexity measure for analyzing the circuit complexity of sensory processing in biological neural systems and neuromorphic engineering. The new complexity measure is applied in this paper to two basic computational problems that arise in translation- and scale-invariant pattern recognition, and hence appear ... more >>>

It is shown that the total wire length of layouts of a balanced binary tree on a 2-dimensional grid can be reduced by 33% if one does not choose the obvious ``symmetric'' layout strategy. Furthermore it is shown that the more efficient layout strategy that is presented in this article ... more >>>