On computation with pulses

We explore the computational power of formal models for computation with pu lses. Such models are motivated by realistic models for biological neurons and by related new types of VLSI ("pulse stream VLSI"). In preceding work i t was shown that the computational power of formal models for computation w ith pulses is quite high if the pulses arriving at a computational unit hav e an approximately linearly rising or linearly decreasing initial segment. This property is satisfied by common models for biological neurons. On the other hand, several implementations of pulse stream VLSI employ pulses that are approximately piecewise constant (i.e., step functions). In this artic le we investigate the relevance of the shape of pulses in formal models for computation with pulses. The results show that the computational power dro ps significantly if one replaces pulses with linearly rising or decreasing initial segments by piecewise constant pulses. We provide an exact characte rization of the latter model in terms of a weak version of a random access machine (RAM). We also compare the language recognition capability of a rec urrent version of this model with that of deterministic finite automata and Turing machines. (C) 1999 Academic Press.