A low-cost neural sorting network with O(1) time complexity

Shun Shii Lin; Shen Hsuan Hsu

doi:10.1016/S0925-2312(96)00040-9

A low-cost neural sorting network with O(1) time complexity

Shun Shii Lin^*, Shen Hsuan Hsu

^*Corresponding author for this work

Department of Computer Science and Information Engineering

Research output: Contribution to journal › Article › peer-review

7 Citations (Scopus)

Abstract

In this paper, we present an O(1) time neural network with O(n(1+ε)) neurons and links to sort n data, ε > O. For large-size problems, it is desirable to have low-cost hardware solutions. In order to solve the sorting problem in constant time and with less hardware-cost, we adopt Leighton's column sort [5] as the main architecture. Then we use Chen and Hsieh's neural network [3] with O(n³) complexity as the lowest-level sub-networks. By using recursive techniques properly, we are able to explore constant-time, low-complexity neural sorting networks.

Original language	English
Pages (from-to)	289-299
Number of pages	11
Journal	Neurocomputing
Volume	14
Issue number	3
DOIs	https://doi.org/10.1016/S0925-2312(96)00040-9
Publication status	Published - 1997 Feb 28

Keywords

Complexity
Neural network
Parallel processing
Sorting

ASJC Scopus subject areas

Computer Science Applications
Cognitive Neuroscience
Artificial Intelligence

Access to Document

10.1016/S0925-2312(96)00040-9

Cite this

@article{25515e64128a458ebd910bb6e9e0db95,

title = "A low-cost neural sorting network with O(1) time complexity",

abstract = "In this paper, we present an O(1) time neural network with O(n(1+ε)) neurons and links to sort n data, ε > O. For large-size problems, it is desirable to have low-cost hardware solutions. In order to solve the sorting problem in constant time and with less hardware-cost, we adopt Leighton's column sort [5] as the main architecture. Then we use Chen and Hsieh's neural network [3] with O(n3) complexity as the lowest-level sub-networks. By using recursive techniques properly, we are able to explore constant-time, low-complexity neural sorting networks.",

keywords = "Complexity, Neural network, Parallel processing, Sorting",

author = "Lin, {Shun Shii} and Hsu, {Shen Hsuan}",

note = "Funding Information: * Corresponding author. Email: [email protected] {\textquoteright} This work was supported by the National Science Council of R.O.C. under grant NSC-84-25 1 l-S-003-089.",

year = "1997",

month = feb,

day = "28",

doi = "10.1016/S0925-2312(96)00040-9",

language = "English",

volume = "14",

pages = "289--299",

journal = "Neurocomputing",

issn = "0925-2312",

publisher = "Elsevier",

number = "3",

}

TY - JOUR

T1 - A low-cost neural sorting network with O(1) time complexity

AU - Lin, Shun Shii

AU - Hsu, Shen Hsuan

N1 - Funding Information: * Corresponding author. Email: [email protected] ’ This work was supported by the National Science Council of R.O.C. under grant NSC-84-25 1 l-S-003-089.

PY - 1997/2/28

Y1 - 1997/2/28

N2 - In this paper, we present an O(1) time neural network with O(n(1+ε)) neurons and links to sort n data, ε > O. For large-size problems, it is desirable to have low-cost hardware solutions. In order to solve the sorting problem in constant time and with less hardware-cost, we adopt Leighton's column sort [5] as the main architecture. Then we use Chen and Hsieh's neural network [3] with O(n3) complexity as the lowest-level sub-networks. By using recursive techniques properly, we are able to explore constant-time, low-complexity neural sorting networks.

AB - In this paper, we present an O(1) time neural network with O(n(1+ε)) neurons and links to sort n data, ε > O. For large-size problems, it is desirable to have low-cost hardware solutions. In order to solve the sorting problem in constant time and with less hardware-cost, we adopt Leighton's column sort [5] as the main architecture. Then we use Chen and Hsieh's neural network [3] with O(n3) complexity as the lowest-level sub-networks. By using recursive techniques properly, we are able to explore constant-time, low-complexity neural sorting networks.

KW - Complexity

KW - Neural network

KW - Parallel processing

KW - Sorting

UR - http://www.scopus.com/inward/record.url?scp=0031588794&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0031588794&partnerID=8YFLogxK

U2 - 10.1016/S0925-2312(96)00040-9

DO - 10.1016/S0925-2312(96)00040-9

M3 - Article

AN - SCOPUS:0031588794

SN - 0925-2312

VL - 14

SP - 289

EP - 299

JO - Neurocomputing

JF - Neurocomputing

IS - 3

ER -

A low-cost neural sorting network with O(1) time complexity

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this