The complexity of language recognition by neural networks

Hava T. Siegelmann, C. Lee Giles

Research output: Contribution to journalArticlepeer-review

3 Scopus citations


Neural networks are frequently used as adaptive classifiers. This research represents an attempt to measure the 'neural complexity' of any regular set of binary strings, that is, to quantify the size of a recurrent continuous-valued neural network that is needed for correctly classifying the given regular set. Our estimate provides a predictor that is superior to the size of the minimal automaton that was used as an upper bound so far. Moreover, it is easily computable, using techniques from the theory of rational power series in non-commuting variables.

Original languageEnglish (US)
Pages (from-to)327-345
Number of pages19
Issue number3-4
StatePublished - Jun 1997

All Science Journal Classification (ASJC) codes

  • Computer Science Applications
  • Cognitive Neuroscience
  • Artificial Intelligence


Dive into the research topics of 'The complexity of language recognition by neural networks'. Together they form a unique fingerprint.

Cite this