zbMATH — the first resource for mathematics

Examples
Geometry Search for the term Geometry in any field. Queries are case-independent.
Funct* Wildcard queries are specified by * (e.g. functions, functorial, etc.). Otherwise the search is exact.
"Topological group" Phrases (multi-words) should be set in "straight quotation marks".
au: Bourbaki & ti: Algebra Search for author and title. The and-operator & is default and can be omitted.
Chebyshev | Tschebyscheff The or-operator | allows to search for Chebyshev or Tschebyscheff.
"Quasi* map*" py: 1989 The resulting documents have publication year 1989.
so: Eur* J* Mat* Soc* cc: 14 Search for publications in a particular source with a Mathematics Subject Classification code (cc) in 14.
"Partial diff* eq*" ! elliptic The not-operator ! eliminates all results containing the word elliptic.
dt: b & au: Hilbert The document type is set to books; alternatively: j for journal articles, a for book articles.
py: 2000-2015 cc: (94A | 11T) Number ranges are accepted. Terms can be grouped within (parentheses).
la: chinese Find documents in a given language. ISO 639-1 language codes can also be used.

Operators
a & b logic and
a | b logic or
!ab logic not
abc* right wildcard
"ab c" phrase
(ab c) parentheses
Fields
any anywhere an internal document identifier
au author, editor ai internal author identifier
ti title la language
so source ab review, abstract
py publication year rv reviewer
cc MSC code ut uncontrolled term
dt document type (j: journal article; b: book; a: book article)
Gray codes for reflection groups. (English) Zbl 0684.20036
It is shown that in a finite group generated by reflections R 1 ,···,R n the elements can be arranged in order a 0 ,a 1 ,···,a g-1 so that for each i there is a j such that a i+1 =a i R j (where a g =a 0 ). Such an arrangement is called a Gray code, the classical example being the conventional binary Gray code, which is a Hamiltonian circuit through the n-cube. Specific Gray codes are computed for a number of examples.
Reviewer: F.D.Veldkamp

MSC:
20H15Other geometric groups, including crystallographic groups
05B45Tessellation and tiling problems
94B25Combinatorial codes
20D60Arithmetic and combinatorial problems on finite groups
20F05Generators, relations, and presentations of groups
References:
[1]Abbott, H.L.: Hamiltonian circuits and paths on then-cube. Canad. Math. Bull.9, 557–562 (1966) · Zbl 0148.17904 · doi:10.4153/CMB-1966-068-6
[2]Afriat, S.N.: The Ring of Linked Rings. London: Duckworth 1982
[3]Agrawal, D.P.: Signed modified reflected binary code. IEEE Trans. Comput.25, 549–552 (1976) · doi:10.1109/TC.1976.1674648
[4]Arazi, B.: An approach to generating different types of Gray codes. Inf. Control63, 1–10 (1984) · doi:10.1016/S0019-9958(84)80038-8
[5]Berlekamp, E.R., Conway, J.H., Guy, R.K.: Winning Ways. NY: Academic Press 1982
[6]Bitner, J.R., Ehrlich, G., Reingold, E.M.: Efficient generation of the binary reflected Gray code and its applications. Commun. ACM19, 517–521 (1976) · Zbl 0333.94006 · doi:10.1145/360336.360343
[7]Bourbaki, N.: Groupes et Algèbres de Lie. Chapitres 4, 5 et 6. Paris: Hermann 1968
[8]Buck, M., Wiedemann, D.: Gray codes with restricted density. Discrete Math.48, 163–171 (1984) · Zbl 0572.05042 · doi:10.1016/0012-365X(84)90179-1
[9]Caviour, S.R.: An upper bound associated with errors in Gray code. IEEE Trans. Inf. Theory21, 596 (1975) · Zbl 0308.94007 · doi:10.1109/TIT.1975.1055424
[10]Chamberlain, R.M.: Gray codes, Fast Fourier Transforms and hypercubes. Parallel Computing6, 225–233 (1988) · Zbl 0635.65145 · doi:10.1016/0167-8191(88)90087-7
[11]Cohn, M.: Affinem-ary Gray codes. Inf. Control6, 70–78 (1963) · Zbl 0202.50303 · doi:10.1016/S0019-9958(63)90119-0
[12]Cohn, M., Even, S.: A Gray code counter. IEEE Trans. Comput.18, 662–664 (1969) · doi:10.1109/T-C.1969.222736
[13]Conway, J.H., Sloane, N.J.A.: Sphere Packings, Lattices and Groups. NY: Springer-Verlag 1988
[14]Coxeter, H.S.M.: Regular Polytopes. 3rd ed. NY: Dover 1973
[15]Coxeter, H.S.M., Moser, W.O.J.: Generators and Relations for Discrete Groups. 4th ed. NY: Springer-Verlag 1980
[16]Crowe, D.W.: Then-dimensional cube and the tower of Hanoi. Amer. Math. Mon.63, 29–30 (1956) · Zbl 0070.01202 · doi:10.2307/2308050
[17]Darwood, N.: Using the decimal Gray code. Electronic Engineering. 28–29 (Feb. 1972)
[18]Dershowitz, N.: A simplified loop-free algorithm for generating permutations. BIT15, 158–164 (1975) · Zbl 0317.05006 · doi:10.1007/BF01932689
[19]Dixon, E., Goodman, S.: On the number of Hamiltonian circuits in then-cube. Proc. Amer. Math. Soc.50, 500–504 (1975)
[20]Dobkin, D.P., Levy, V.F., Thurston, W.P., Wilks, A.R.: Contour tracing by piecewise linear approximations. Transactions on Graphics9 (1990), to appear
[21]Douglas, R.J.: Bounds on the number of Hamiltonian circuits in then-cube. Discrete Math.17, 143–146 (1977) · Zbl 0352.05042 · doi:10.1016/0012-365X(77)90143-1
[22]Ehrlich, G.: Loopless algorithms for generating permutations, combinations, and other combinatorial configurations. J. ACM20, 500–513 (1973) · Zbl 0266.68018 · doi:10.1145/321765.321781
[23]Er, M.C.: On generating then-ary reflected Gray codes. IEEE Trans. Comput.33, 739–741 (1984) · Zbl 0542.94016 · doi:10.1109/TC.1984.5009360
[24]Er, M.C.: Two recursive algorithms for generating the binary reflected Gray code. J. Inf. Optimization Sci.6, 213–216 (1985)
[25]Flores, I.: Reflected number systems. IRE Trans. Electronic Computers5, 79–82 (1956) · doi:10.1109/TEC.1956.5219803
[26]Gardner, M.: The curious properties of the Gray code and how it can be used to solve puzzles. Scientific American227, 106–109 (No. 2, August 1972) · doi:10.1038/scientificamerican0872-106
[27]Gilbert, E.N.: Gray codes and paths on then-cube. Bell Syst. Tech. J.37, 815–826 (1958)
[28]Gray, F.: Pulse Code Communication. U.S. Patent 2632058, March 17, 1953
[29]Gros, L.: Theorie de Baguenodier. Lyons: Aimé Vingtrinier 1872
[30]Grossman, I., Magnus, W.: Groups and Their Graphs. NY: Random House 1964
[31]Grove, L.C., Benson, C.T.: Finite Reflection Groups. 2nd ed. NY: Springer-Verlag 1985
[32]Johnson, S.M.: Generation of permutations by adjacent transpositions. Math. Comput.17, 282–285 (1963) · doi:10.1090/S0025-5718-1963-0159764-2
[33]Joichi, J.T., White, D.E.: Gray codes in graphs of subsets. Discrete Math.31, 29–41 (1980) · Zbl 0449.05043 · doi:10.1016/0012-365X(80)90169-7
[34]Joichi, J.T., White, D.E., Williamson, S.G.: Combinatorial Gray codes. SIAM J. Comput.9, 130–141 (1980) · Zbl 0452.05009 · doi:10.1137/0209013
[35]Kaye, R.: A Gray code for set partitions. Info. Process Lett.5, 171–173 (1976) · Zbl 0357.94010 · doi:10.1016/0020-0190(76)90014-4
[36]Klee, V.: Long paths and circuits on polytopes. Chap. 17 of B. Grünbaum, Convex Polytopes. NY: Wiley 1967
[37]Klingsberg, P.: A Gray code for compositions. J. Algorithms3, 41–44 (1982) · Zbl 0477.68071 · doi:10.1016/0196-6774(82)90006-2
[38]van Lantschoot, E.J.M.: A systematic method for designing Gray code counters. Comput. J. 43 (1973)
[39]Levy, S.V.F., Wilks, A.R.: Computing the contour of a piecewise linear function (to appear)
[40]Lucal, H.M.: Arithmetic operations for digital computers using a modified reflected binary code. IRE Trans. Electronic Computers8, 449–459 (1959) · doi:10.1109/TEC.1959.5222057
[41]Ludman, J.E., Sampson, J.L.: A technique for generating Gray codes. J. Stat. Plann. Inference5, 171–180 (1981) · Zbl 0459.94023 · doi:10.1016/0378-3758(81)90027-6
[42]Lüneburg, H.: Gray-codes. Abh. Math. Semin. Univ. Hamb.52, 208–227 (1982) · Zbl 0519.94013 · doi:10.1007/BF02941878
[43]MacWilliams, F.J., Sloane, N.J.A.: The Theory of Error Correcting Codes. Amsterdam: North-Holland 1977
[44]Mathialagan, A., Vaidehi, V.: Reduced look-up table for Gray to Binary conversion. J. Inst. Electron. Telecommun. Eng.32, 76–77 (1986)
[45]Mills, W.H.: Some complete cycles on then-cube. Proc. Amer. Math. Soc.14, 640–643 (1963)
[46]Oberman, R.M.M.: A new explanation of the reflected binary code. IEEE Trans. Comput.23, 641–642 (1974) · doi:10.1109/T-C.1974.224004
[47]Prodinger, H.: Nonrepetitive sequences and Gray code. Discrete Math.43, 113–116 (1983) · Zbl 0492.68058 · doi:10.1016/0012-365X(83)90027-4
[48]Proskurowski, A., Ruskey, F.: Binary tree Gray codes. J. Algorithms6, 225–238 (1985) · Zbl 0593.68050 · doi:10.1016/0196-6774(85)90040-9
[49]Rankin, R.A.: A campanological problem in group theory. Proc. Comb. Phil. Soc.44, 17–25 (1948) · doi:10.1017/S030500410002394X
[50]Sharma, B.D., Khanna, R.K.: Onm-ary Gray codes. Inf. Sci.15, 31–43 (1978) · Zbl 0436.94028 · doi:10.1016/0020-0255(78)90020-8
[51]Smith, D.H.: Hamiltonian circuits on then-cube. Canad. Math. Bull.17, 759–761 (1975) · Zbl 0304.05116 · doi:10.4153/CMB-1974-137-9
[52]Tang, D.T., Liu, C.N.: Distance 2 cyclic chaining of constant weight codes. IEEE Trans. Comput.22, 176–180 (1973) · doi:10.1109/T-C.1973.223681
[53]Trotter, H.F.: Algorithm 115, PERM. Commun. ACM5, 434–435 (1962) · doi:10.1145/368637.368660
[54]Vickers, V.E., Silverman, J.: A technique for generating specialized Gray codes. IEEE Trans. Comput.29, 329–331 (1980) · doi:10.1109/TC.1980.1675573
[55]Wang, M.C.: An algorithm for Gray-to-binary conversion. IEEE Trans. Comput.15, 659–660 (1966) · doi:10.1109/PGEC.1966.264390
[56]White, A.T.: Graphs, Groups and Surfaces. Amsterdam: North-Holland 1973
[57]White, A.T.: Graphs of groups on surfaces. In: Combinatorial Surveys (P.J. Cameron, ed.) pp. 165–197. NY: Academic Press 1977
[58]White, A.T.: Ringing the changes. Math. Proc. Comb. Philos. Soc.94, 203–215 (1983) · Zbl 0528.05025 · doi:10.1017/S0305004100061053
[59]White, A.T.: Ringing the changes II. Ars Comb.A20, 65–75 (1985)
[60]White, A.T.: Ringing the cosets. Amer. Math. Mon.94, 721–746 (1987) · Zbl 0632.20002 · doi:10.2307/2323414
[61]Yuen, C.K.: The separability of Gray code. IEEE Trans. Inf. Theory20, 668 (1974) · Zbl 0295.94014 · doi:10.1109/TIT.1974.1055275
[62]Yuen, C.K.: Fast analog-to-Gray code converter. Proc. IEEE65, 1510–1511 (1977) · doi:10.1109/PROC.1977.10754