Complexity of perceptron recognition for a class of geometric patterns

Julio Aracena, Eric Goles

Research output: Contribution to journalArticlepeer-review

1 Scopus citations


In this paper, we study the recognition complexity of discrete geometric figures (rectangles, squares, circles, ellipses) on a retina by diameter-limited and order-restricted perceptrons. We construct a diameter-limited recognition perceptron for the family of rectangles, beginning with local configurations, which is different from the one shown by Minsky et al. (Perceptrons: An Introduction to Computational Geometry, extended edition, MIT Press, Cambridge, MA, 1988). In addition, we demonstrate the nonexistence of diameter-limited recognition perceptrons for squares, circles and ellipses. Finally, for squares and ellipses we construct an order-restricted perceptron with constant coefficients, using an original technique which decomposes the characterization of the figures into local and global features.

Original languageEnglish
Pages (from-to)65-79
Number of pages15
JournalTheoretical Computer Science
Issue number1-3
StatePublished - 18 Apr 2003
Externally publishedYes


  • Discrete figures
  • Perceptron
  • Recognition


Dive into the research topics of 'Complexity of perceptron recognition for a class of geometric patterns'. Together they form a unique fingerprint.

Cite this