Efficient Simulation of Finite Automata by Neural Nets

Noga Alon, A. K. Dewdney, Teunis J. Ott

Research output: Contribution to journalArticlepeer-review

74 Scopus citations


Let K1991 denote the smallest number with the property that every m-state finite automaton can be built as a neural net using K(m) or fewer neurons. A counting argument shows that K(m) is at least Ω((m log m)1/3), and a construction shows that K(m) is at most O(m3/4). The counting argument and the construction allow neural nets with arbitrarily complex local structure and thus may require neurons that themselves amount to complicated networks. Mild, and in practical situations almost necessary, constraints on the local structure of the network give, again by a counting argument and a construction, lower and upper bounds for K(m) that are both linear in m.

Original languageEnglish (US)
Pages (from-to)495-514
Number of pages20
JournalJournal of the ACM (JACM)
Issue number2
StatePublished - Jan 4 1991
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Software
  • Control and Systems Engineering
  • Information Systems
  • Hardware and Architecture
  • Artificial Intelligence


  • Mealy
  • machines


Dive into the research topics of 'Efficient Simulation of Finite Automata by Neural Nets'. Together they form a unique fingerprint.

Cite this