The minimal number of layers of a perceptron that sorts

Zwietering, P.J., Aarts, E.H.L., & Wessels, J. (1994). The minimal number of layers of a perceptron that sorts. Journal of Parallel and Distributed Computing 20 (3) 380-387. 10.1006/jpdc.1994.1034.

Full text not available from this repository.

Abstract

In this paper we consider the problem of determining the minimal number of layers required by a multilayered perceptron for solving the problem of sorting a set of real-valued numbers. We discuss two formulations of the sorting problem; ABSSORT, which can be considered as the standard form of the sorting problem, and for which, given an array of numbers, a new array with the original numbers in ascending order is requested, and RELSORT, for which, given an array of numbers, one wants first to find the smallest number, and then for each number-except the largest-one wants to find the number that comes next in size. We show that, if one uses classical multilayered perceptrons with the hard-limiting response function, the minimal numbers of layers needed are 3 and 2 for solving ABSSORT and RELSORT, respectively.

Item Type:	Article
Research Programs:	Methodology of Decision Analysis (MDA)
Bibliographic Reference:	Journal of Parallel and Distributed Computing; 20:380-387 [1994]
Depositing User:	IIASA Import
Date Deposited:	15 Jan 2016 02:03
Last Modified:	27 Aug 2021 17:35
URI:	https://pure.iiasa.ac.at/3869

Actions (login required)

View Item