×

On permutations of wires and states. (English) Zbl 0575.94038

We characterize a permutation as a sequence of wire-cycle periods and a sequence of state-cycle periods. These sequences are called a wire- sequence and a state-sequence, respectively. A relation between wire- cycles and state-cycles is discussed and some combinatorial problems on cycle periods of permutations are solved. An efficient method for constructing the state-sequence corresponding to a given wire-sequence is also described.

MSC:

94C99 Circuits, networks
05A05 Permutations, words, matrices
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Afshar, S. K., On the complexity of permutation network design, SIGACT NEWS, 14, 3, 31-35 (1982)
[2] Berge, C., Principles of Combinatorics (1971), Academic Press: Academic Press New York · Zbl 0227.05002
[3] Birkhoff, G.; Maclane, S., A Survey of Modern Algebra (1953), Macmillan: Macmillan New York · Zbl 0052.25402
[4] Booth, T. L., Sequential Machines and Automata Theory (1967), Wiley: Wiley New York · Zbl 0165.02303
[5] Elspas, B., The theory of autonomous linear sequential networks, IRE Trans. Circuit Theory, 6, 44-60 (1959)
[6] Lev, G. F.; Pippenger, N.; Valiant, L. G., A fast parallel algorithm for routing in permutation networks, IEEE Trans. Computers, 30, 93-100 (1981) · Zbl 0455.94047
[7] Nijenhuis, A.; Wilf, H. S., Combinatorial Algorithms (1978), Academic Press: Academic Press New York · Zbl 0298.05015
[8] Rota, G., On the foundations of combinatorial theory I, Z. Wahrscheinlichkeitstheorie, 2, 340-368 (1964), Theory of Möbius functions · Zbl 0121.02406
[9] Waksman, A., A permutation network, J. Assoc. Comput. Mach., 15, 159-163 (1968) · Zbl 0157.23702
[10] Zierler, N., Linear recurring sequences, J. Soc. Indust. Appl. Math., 3, 31-48 (1959) · Zbl 0096.33804
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.