The minimal number of layers of a perceptron that sorts

P.J. Zwietering, E.H.L. Aarts, J. Wessels

Research output: Contribution to journalArticleScientificpeer-review

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.
Original languageEnglish
Pages (from-to)380-387
Number of pages8
JournalJournal of Parallel and Distributed Computing
Volume20
Issue number3
DOIs
Publication statusPublished - 1994
Externally publishedYes

Fingerprint

Perceptron
Sort
Sorting
Scientific notation
Response Function
Limiting
Formulation

Cite this

@article{7d1818c918af404abd91a4bbfebfddb0,
title = "The minimal number of layers of a perceptron that sorts",
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.",
author = "P.J. Zwietering and E.H.L. Aarts and J. Wessels",
year = "1994",
doi = "10.1006/jpdc.1994.1034",
language = "English",
volume = "20",
pages = "380--387",
journal = "Journal of Parallel and Distributed Computing",
issn = "0743-7315",
publisher = "Academic Press Inc.",
number = "3",

}

The minimal number of layers of a perceptron that sorts. / Zwietering, P.J.; Aarts, E.H.L.; Wessels, J.

In: Journal of Parallel and Distributed Computing, Vol. 20, No. 3, 1994, p. 380-387.

Research output: Contribution to journalArticleScientificpeer-review

TY - JOUR

T1 - The minimal number of layers of a perceptron that sorts

AU - Zwietering, P.J.

AU - Aarts, E.H.L.

AU - Wessels, J.

PY - 1994

Y1 - 1994

N2 - 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.

AB - 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.

U2 - 10.1006/jpdc.1994.1034

DO - 10.1006/jpdc.1994.1034

M3 - Article

VL - 20

SP - 380

EP - 387

JO - Journal of Parallel and Distributed Computing

JF - Journal of Parallel and Distributed Computing

SN - 0743-7315

IS - 3

ER -