Learning Sorting Networks by Grammars

Kammeyer, Thomas E.; Belew, Richard K.

Learning Sorting Networks by Grammars

AAAI 1994 pp. 1466

/aaai/1994/kammeyer1994aaai-learning/

Abstract

A compare-exchange network, or CMPX-net, is a se-quence of operations of the form [i: j], each of which operates on an array, D, of length N. The network is said to have width N. The length of the network is the number of CMPX’s in the network. For each [i: j], we have i &lt; j and i, j E [0, N- 11. To apply a CMPX-net to an array, swap O[i] and O[j] if D[i]&gt; O[j] for each [i: j] in the sequence. A sorting networlc(SNet) is a CMPX-net which will sort D’s contents into nonde-creasing order no matter how D’s contents are ordered initially. A merging network (MNet) is a pair contain-ing a CMPX-net of even width, N, and a partition of the indices into two equal-size sets or “sides. ” If the data on each side of the partition are sorted initially then the output will be sorted. The space of CMPX-

PDF AAAI Semantic Scholar

Cite

Text

Kammeyer and Belew. "Learning Sorting Networks by Grammars." AAAI Conference on Artificial Intelligence, 1994.

Markdown

[Kammeyer and Belew. "Learning Sorting Networks by Grammars." AAAI Conference on Artificial Intelligence, 1994.](https://mlanthology.org/aaai/1994/kammeyer1994aaai-learning/)

BibTeX

@inproceedings{kammeyer1994aaai-learning,
  title     = {{Learning Sorting Networks by Grammars}},
  author    = {Kammeyer, Thomas E. and Belew, Richard K.},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year      = {1994},
  pages     = {1466},
  url       = {https://mlanthology.org/aaai/1994/kammeyer1994aaai-learning/}
}