Neural Networks: Automata and Formal Models of Computation

Mikel L. Forcada
Universitat d'Alacant,
Dept. Llenguatges i Sistemes Informàtics,
E-03071 Alacant (Spain).

• Contents
• Preface
  • Status of this document
  • Motivation^1.1
• Introduction
  • Neural networks and formal models of language and computation
  • Organization of the document
• Finite-state machines and neural nets
  • McCulloch and Pitts' neural logical calculus
  • What functions can a neuron compute?
  • Nets with circles and finite-state machines
    • Mealy machines
    • Moore machines
    • Deterministic finite-state automata
    • Minsky's neural automata
  • Finite-state automata and regular languages
• Sequence processing with neural nets
  • Processing sequences
    • State-based sequence processors
  • Discrete-time recurrent neural networks
    • Neural Mealy machines
    • Neural Moore machines
    • Other architectures without hidden state
  • Application of DTRNN to sequence processing
  • Learning algorithms for DTRNN
    • Gradient-based algorithms
      • Backpropagation through time
      • Real-time recurrent learning
      • Other derivative-based methods
    • Non-gradient methods
    • Architecture-coupled methods
      • Recurrent cascade correlation
  • Learning problems
  • Papers
• Computational capabilities of DTRNN
  • Languages, grammars and automata
    • Grammars and Chomsky's hierarchy.
      • Grammars
    • Chomsky's hierarchy of grammars
  • DTRNN behaving as finite-state machines
    • DTRNN based on threshold units
    • DTRNN based on sigmoid units
      • Some DTRNN architectures cannot implement all FSM
    • Featured papers
  • Turing computability with DTRNN
    • Turing machines
      • Linearly-bounded automata
      • Turing computability with DTRNN
  • Super-Turing capabilities of DTRNN
• Grammatical inference with DTRNN
  • Grammatical inference (GI)
  • Discrete-time recurrent neural networks for grammatical inference
  • Representing and learning
    • Open questions on grammatical inference with DTRNN
    • Stability and generalization
  • Automaton extraction algorithms
    • State-space partition methods
    • Clustering methods
    • Using Kohonen's self-organizing maps
  • Featured papers
    • Inference of finite-state machines
    • Inference of context-free grammars
• Index
• List of abbreviations
• Bibliography