High Accuracy Asymptotic Bounds on the BDD Size and Weight of the Hardest Functions

• Autorzy: Lozhkin S.A. , Shiganov A.E.
• Języki publikacji: EN

Abstrakty

EN

In this paper we study the representation of Boolean functions by general binary decision diagrams (BDDs). We investigate the size L(Σ) (number of inner nodes) of BDD Σ with different constraints on the number M(Σ) of its merged nodes. Furthermore, we introduce a weighted complexity measure W(Σ) = L(Σ) + ωM(Σ), where ω > 0. For the hardest Boolean function on n input variables we define the weight WBDD(n) and the size LBDD(n, t), where t limits the number of merged nodes. By using a new synthesis method and appropriate restrictions for the number t of merged nodes, we are able to prove tight upper and lower asymptotic bounds: [formula] which have a relative error of O(1/n). Our results show how weight and structural restrictions of general BDDs influence the complexity of the hardest function in terms of high accuracy asymptotic bounds.

Słowa kluczowe

EN

Boolean function; circuits; binary decision diagrams; complexity; high accuracy asymptotic bound

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2010
• Tom: Vol. 104, nr 3
• Strony: 239--253
• Opis fizyczny: Bibliogr. 19 poz.

Twórcy

autor

Lozhkin S.A.

autor

Shiganov A.E.

• Faculty of Computational Mathematics and Cybernetics, Lomonosov Moscow State University, MGU, Vorobjovy Gory, Moscow, 119899, Russia,

Bibliografia

• [1] Frandsen, G. S., Miltersen, P. B.: Reviewing bounds on the circuit size of the hardest functions. Information Processing Letters, Volume 95, Issue 2, 2005, 354-357.
• [2] Hromkovich, J., Lozhkin, S. A., Rybko, A. I., Sapozhenko, A. A., Shkalikova, N. A.: Lower bounds on the area complexity of Boolean circuits, Theoretical Computer Science, 97, 1992, 285-300.
• [3] Kuzmin, V. A.: The bound on the complexity of realization of Boolean functions by programs of simple types. Met. Diskr. Anal., 29, 1976, 11-39.
• [4] Lee, C. Y.: Representation of switching circuits by binary-decision programs, Bell. Sys. Tech. J., vol. 38, 1959, 985-999.
• [5] Lozhkin, S. A.: On the synthesis of oriented switching circuits, Moscow Univ. Comput. Math. Cybernet., 1995, N. 2, 32-37.
• [6] Lozhkin, S. A.: On the synthesis of certain types of circuits based on translation partitions generated by universal matrices, Moscow Univ. Comput. Math Cybernet., 1996, N. 1, 57-63.
• [7] Lozhkin, S. A.: High accuracy bounds on the complexity of circuits of some types, Mat. Probl. Kibern., 6, 1996, 189-214.
• [8] Lozhkin, S. A.: Asymptotic bounds of high accuracy on the complexity of control systems, Doctor thesis, Moscow State University, 1997.
• [9] Lozhkin, S. A.: On the complexity of realization of Boolean functions by circuits and formulas over gates having direct and iterative inputs, Proc. III International Conference on Discrete Models in Conrol System Theory, Moscow, Dialogue-MSU, 1998, 72-73.
• [10] Lozhkin, S. A.: Lekcii po Osnovam Kibernetiki, Moscow State University, 2004.
• [11] Lupanov, O. B.: Synthesis of contact circuits, Dokl. AN SSSR, 119, N. 1, 1958, 23-26.
• [12] Lupanov, O. B.: A method of circuit synthesis, Izv. VUZ Radiofiz., 1, 1958, 120-140.
• [13] Lupanov, O. B.: Complexity of relay-contact realization of functions of logical algebra, Probl. Kibern., 11, 1964, 25-48.
• [14] Lupanov, O. B.: On a certain approach to the synthesis of control systems - the local coding principle, Probl. Kibern., 14, 1965, 31-110.
• [15] Lupanov, O. B.: Asimptoticheskie otsenki slozhnosti upravlyaushchikh sistyem, Moscow State University, 1984.
• [16] Shannon, C. E.: The synthesis of two-terminal switching circuits, Bell Syst. Techn. J., 1949, v.28, N-l, 59-98.
• [17] Ullman, J. D.: Computational aspects of VLSI, Computer Science Press, 1984.
• [18] Wegener, I.: The complexity of Boolean functions, Teubner (Stuttgart)/Wiley (Chichester), 1987.
• [19] Wegener, I.: Branching programs and binary decision diagrams, SIAM Publisher, 2000.