Representation beyond finite states: Alternatives to pushdown automata
Janet Wiles, Alan Blair, Mikael Bodén · 2001
It has been well established that Dynamical Recurrent Networks (DRNs) can act as deterministic finite-state automata (DFAs --- see Chapters 6 and 7). A DRN can reliably represent the states of a DFA as regions in its state space, and the DFA transitions as transitions between these regions. However, as we shall see in this chapter, DRNs can learn to process languages which are non-regular (and therefore cannot be processed by any DFA). Moreover, DRNs are capable of generalizing in ways which go beyond the DFA framework. We will show how DRNs can learn to predict context-free and context-sensitive languages, making use of the transient dynamics as the network activations move towards an attractor or away from a repeller. The resulting trajectory can be thought of as analogous to winding up a spring in one dimension and unwinding it in another. In contrast to push-down automata, which rely on unbounded external memory, DRNs must instead rely on arbi