期刊名称：International Journal of Computer Science and Management Studies
电子版ISSN：2231-5268
出版年度：2012
卷号：12
期号：3
出版社：Imperial Foundation
摘要：This paper comparator networks - a well-known model of parallel computation. This model is used extensively for keys arrangement tasks such as sorting and selection. This work investigates several aspects of comparator networks. It starts with presenting handy tools for analysis of comparator networks in the form of conclusive sets - non-binary vectors that verify a specific functionality. The 0-1 principle introduced by Knuth states that a comparator network is a sorting network if and only if it sorts all binary inputs. Hence, it points out a certain binary conclusive set. We compare these two models by considering several 0-1 -like principles and show that the min-max model is the ‘strongest’ model of computation which obeys our principles. That is, if a function is computable in a model of computation in which any of these principles holds, a min-max network can compute this function.
