Phân loại Định thức Boolean Phổ quát theo Nhóm Affine

Acta Applicandae Mathematicae - Tập 46 - Trang 147-167 - 1997
I. Strazdins1
1Riga Technical University, Riga, Latvia

Tóm tắt

Trong bài báo này, chúng tôi đưa ra một giải pháp thực tiễn cho bài toán phân loại các hàm Boolean bằng nhóm affine – nhóm biến đổi tuyến tính lớn nhất của các biến. Chúng tôi chỉ ra rằng các loại affine (các lớp tương đương) có thể được sắp xếp trong một chuỗi vô hạn duy nhất chứa tất cả các danh sách loại trước đó. Các loại này được xác định bởi các đại diện tối thiểu của chúng, các bất biến quang phổ và thứ tự ổn định. Một khảo sát ngắn gọn về các nhóm biến đổi cơ bản cũng được đưa vào.

Từ khóa

#Phân loại hàm Boolean #nhóm affine #biến đổi tuyến tính #đại diện tối thiểu #bất biến quang phổ.

Tài liệu tham khảo

Berger, T. and Charpin, P.: The automorphism group of generalized Reed-Muller codes, Discrete Math. 117 (1993), 1–17. Berlekamp, E. R. and Welch, L. R.: Weight distributions of the cosets of the (32, 6) Reed-Muller code, IEEE Trans. Inform. Theory 18 (1972), 203–207. Clote, P. and Kranakis, E.: Boolean functions, invariance groups, and parallel complexity, SIAM J. Comput. 20 (1991), 553–590. Delsarte, P.: On cyclic codes that are invariant under the general linear group, IEEE Trans. Inform. Theory 16 (1970), 760–769. Golomb, S.: On the classification of Boolean functions, IRE Trans. Circuit Theory 6 (1959), 176–186. Harrison, M. A.: On the classification of Boolean functions by the general linear and affine groups, J. Soc. Indust. Appl. Math. 12 (1964), 285–299. Harrison, M. A.: Counting theorems and their applications to classification of switching functions, in A. Mukhopadhyay (ed.), Recent Developments in Switching Theory, Academic, Press, New York, London, 1971, pp. 85–120. Hoffman, F. and Welch, L. R.: Totally variant sets in finite groups and vector spaces, Canad. J. Math. 20 (1968), 701–710. Hoffman, F.: Maximal orbits under affine groups, in Proc. 5th Southeastern Conf. on Combinatorics, Graph Theory and Computing, Florida Atlantic Univ., Boca Raton, Fla., 1974, pp. 493–499. Hoffman, F.: Orbits under action of affine group over GF(2), Linear Algebra Appl. 13 (1976), 173–176. Kasami, T., Lin, S., and Peterson, W. W.: Some results on cyclic codes which are invariant under the affine group and their applications, Inform. and Control 11 (1967), 475–496. Lechner, R. J.: A correspondence between equivalence classes of functions and group codes, IEEE Trans. Electron. Comput. 16 (1967), 621–624. Lechner, R. J.: A transform approach to logic design, IEEE Trans. Comput. 19 (1970), 627–640. Lechner, R. J.: Harmonic analysis of switching functions, in A. Mukhopadhyay (ed.), Recent Developments in Switching Theory, Academic Press, New York, London, 1971, pp. 121–228. Leon, J. S.: An algorithm for computing the automorphism group of a Hadamard matrix, J. Comb. Theory A 27 (1979), 289–306. Leon, J. S.: Computing automorphisms of error-correcting codes, IEEE Trans. Inform. Theory 28 (1982), 496–511. Maiorana, J. A.: A classification of the cosets of the Reed-Muller code ℜ(1, 6), Math. Comp. 57 (1991), 403–414. Nechiporuk, E. I.: On the synthesis of networks using linear transformations of argument variables, Dokl. Akad. Nauk SSSR 123 (1958), 610–612 (English transl. Automat. Express, April, 1959, 12–13). Ninomiya, I.: A theory of the coordinate representation of switching functions, Mem. Fac. Engng. Nagoya Univ. 10 (1958), 115–124. Ninomiya, I.: A study of the structures of Boolean functions and its application to the synthesis of switching circuits, Mem. Fac. Engng. Nagoya Univ. 13 (1961), 149–363. Post, E. L.: The Two-valued Iterative Systems of Mathematical Logic, Princeton Univ. Press, Princeton, London, 1941. Robbins, W. E. and Rudolph, L. D.: On two-level EXCLUSIVE-OR majority networks, IEEE Trans. Comput. 23 (1974), 34–41. Slepian, D.: Some further theory of group codes, Bell Syst. Tech. J. 39 (1960), 1219–1252. Stone, H. S. and Jackson, C. L.: Structures of the affine families of switching functions, IEEE Trans. Comput. 18 (1969), 251–257. Strazdin', I. E.: Affine classification of Boolean functions of five variables, Automat. Control Comput. Sci. 9 (1975), 1–7. Strazdins, I.: On fundamental transformation groups in the algebra of logic, in Coll. Math. Soc. J. Bolyai, Vol. 28, North-Holland, Amsterdam, 1981, pp. 669–691. Strazdins, I.: The infinite sequence of affine types of Boolean functions, in K. Chimev and S. Shtrakov (eds), Discrete Mathematics and Applications, N. Rilsky Univ., Blagoevgrad, 1993, pp. 47–51. Strazdins, I.: On examples of variant functions in linear classifications of Boolean functions, in S. Shtrakov and I. Mirchev (eds), Discrete Mathematics and Applications, N. Rilsky Univ., Blagoevgrad, 1995, pp. 28–31. Aiken, H. et al.: Synthesis of Electronic Computing and Control Circuits, Ann. Comput. Lab. Harvard Univ., Vol. 27, Harvard Univ. Press, Cambridge, MA, 1951.