R. A. Legenstein and W. Maass
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 much fewer threshold gates are needed if one employs in addition a small
number of winner-take-all gates. In either case the circuits that are
constructed have linear or almost linear total wire length, and are therefore
not unrealistic from the point of view of physical implementations.