continuous vs symbolic: a more concrete problem

[Jordan B Pollack]

       How does one go about constructing a neural network that can
       recognize a reasonably large (infinite and nontrivial) *class*
       of formal languages?

Lev, 

Maybe I'm missing something here, but it has been known since
Mcculloch and Pitts 1943, and reiterated by Minsky 1967, that the
simplest NN's can behave like finite state machines. FSM's can specify
regular languages. 

By trivial construction, almost any NN capable of arbitrary
(sum-of-products) boolean functions are able to represent the
"infinite, but TRIVIAL *class*" of regular languages, simply by
recurrent use of a set of arbitrary boolean functions.  The "next
state" vector is just a vector boolean function of the "current state"
and "input token" vectors.

Since McCullogh-Pitts neurons, two layers of linear-threshold
units, or two layers of quasi-linear feedforward networks are are all
capable of sum-of-product logical forms, they are all capable of
simple solutions to regular language recognition. 

But if the next state is only a first-order function of the current
state and input (such as in Elman's SRN), then all even RL's cannot be
in general recognized. Consider the regular "odd parity" language,
where the next state is the exclusive-or of the current state and
input.

The more interesting question is how neural-LIKE architectures can
deal NATURALLY with *NONTRIVIAL* grammatical systems, such as the
context free, indexed CF (thought by many to be the proper category of
natural languages), or context sensitive. We can always solve these
problems by adding an external stack or a production rule interpreter,
but these solutions do not seem very natural. I'd be very interested
if your formalism can solve any of these classes in a routine manner.

Jordan Pollack                            Assistant Professor
CIS Dept/OSU                              Laboratory for AI Research
2036 Neil Ave                             Email: pollack at cis.ohio-state.edu
Columbus, OH 43210                        Fax/Phone: (614) 292-4890