Wolfram Library Archive

Courseware Demos MathSource Technical Notes
All Collections Articles Books Conference Proceedings

Universality of Iterated Networks

R. Chamberlain
C. Fiduccia
Journal / Anthology

Mathematical Systems Theory
Year: 1994
Volume: 27
Page range: 381-430

The multistage shuffle-exchange network is generalized, by replacing the perfect shuffle with an arbitrary permutation pi, in order to pass all permutations using a minimal number of stages. The universality of such a network is shown to be equivalent to the primitivity of a related regular digraph, thus showing that universality is decidable in polynomial time. Extensive computational results are presented that characterize all nonisomorphic minimal networks with up to 12 inputs. In addition, strong evidence is presented relating the minimal number of network stages needed to achieve universality to twice the index of primitivity of the corresponding digraph.

*Applied Mathematics > Computer Science