TR available - Noisy nets cannot recognize regular languages

[Eduardo Sontag]

TR available:

  ANALOG NEURAL NETS WITH GAUSSIAN OR OTHER COMMON NOISE DISTRIBUTIONS
	    CANNOT RECOGNIZE ARBITRARY REGULAR LANGUAGES

		   Wolfgang Maass, Graz, Austria
                  Eduardo D. Sontag, Rutgers, USA

			   ABSTRACT

  We consider recurrent analog neural nets where the output of each
  gate is subject to Gaussian noise, or any other common noise
  distribution that is nonzero on a large set.
  We show that many regular languages cannot be recognized by networks 
  of this type, and we give a precise characterization of those languages
  which can be recognized. 
  This result implies severe constraints on possibilities for constructing
  recurrent analog neural nets that are robust against realistic types
  of analog noise.
  On the other hand, we present a method for constructing feedforward
  analog neural nets that are robust with regard to analog noise of this type.

The paper can be retrieved from

    http://www.math.rutgers.edu/~sontag

(follow link to "online papers").
The file is a gzipped postscript file.

If Web access if inconvenient, it is also possible to use anonymous FTP:

   ftp math.rutgers.edu
   login: anonymous
   cd pub/sontag
   bin
   get noisy-nets.ps.gz
   quit
   gunzip noisy-nets.ps.gz
   lpr noisy-nets.ps