Abstract
In this article, we present an algorithm for conjunctive bi–decomposition of boolean polynomials where decomposition components share only prescribed variables. It is based on the polynomial–time algorithm of disjoint decomposition developed before. Some examples and evaluation of the algorithm are given.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
\(\mathcal{U}_F\) is also called the support of function supp(F). Its cardinality is also called the weight of function wt(F).
- 2.
To exclude polynomials with trivial divisors they have to be relative prime.
References
Perkowski, M.A., Grygiel, S.: A survey of literature on function decomposition, Version IV. PSU Electrical Engineering Department Report, Portland State University, Portland, Oregon, USA, November 1995
Khatri, S.P., Gulati, K. (eds.): Advanced Techniques in Logic Synthesis, Optimizations and Applications. Springer, New York (2011)
Mishchenko, A., Sasao, T.: Large-scale SOP minimization using decomposition and functional properties. In: Proceedings of the 40th ACM/IEEE Design Automation Conference (DAC ’03), pp. 149–154. ACM, New York (2003)
Steinbach, B., Lang, C.: Exploiting functional properties of Boolean functions for optimal multi-level design by bi-decomposition. Artif. Intell. Rev. 20(3–4), 319–360 (2003)
Bioch, J.C.: The complexity of modular decomposition of Boolean functions. Discrete Appl. Math. 149(1–3), 1–13 (2005)
Bioch, J.C.: Decomposition of Boolean functions. In: Crama, Y., Hammer, P.L. (eds.) Boolean Models and Methods in Mathematics, Computer Science, and Engineering. Encyclopedia of Mathematics and its Applications, vol. 134, pp. 39–78. Cambridge University Press, New York (2010)
Choudhury, M., Mohanram, K.: Bi-decomposition of large Boolean functions using Blocking Edge Graphs. In: Proceedings of the 2010 IEEE/ACM International Conference on Computer-Aided Design (ICCAD ’10), pp. 586–591. IEEE Press, Piscataway (2010)
Mishchenko, A., Steinbach, B., Perkowski, M.A.: An algorithm for bi-decomposition of logic functions. In: Proceedings of the 38th ACM/IEEE Design Automation Conference (DAC ’01), pp. 103–108. ACM, New York (2001)
Emelyanov, P., Ponomaryov, D.: On tractability of disjoint AND-decomposition of Boolean formulas. In: Voronkov, A., Virbitskaite, I. (eds.) PSI 2014. LNCS, vol. 8974, pp. 92–101. Springer, Heidelberg (2015)
Emelyanov, P., Ponomaryov, D.: Algorithmic issues of conjunctive decomposition of boolean formulas. Programming and Computer Software 41(3) (2015) 162–169 Translated: Programmirovanie, vol. 41, No. 3, pp. 62–72 (2015)
Shpilka, A., Volkovich, I.: On the relation between polynomial identity testing and finding variable disjoint factors. In: Abramsky, S., Gavoille, C., Kirchner, C., Meyer auf der Heide, F., Spirakis, P.G. (eds.) ICALP 2010. LNCS, vol. 6198, pp. 408–419. Springer, Heidelberg (2010)
Zhegalkin, I.: Arithmetization of symbolic logics. Sb. Math. 35(1), 311–377 (1928). In Russian
von zur Gathen, J., Gerhard, J.: Modern Computer Algebra, 3rd edn. Cambridge University Press, New York (2013)
Ponomaryov, D.: On decomposability in logical calculi. Bull. Novosibirsk Comput. Cent. 28, 111–120 (2008)
Kuon, I., Tessier, R., Rose, J.: FPGA Architecture: Survey and Challenges. Now Publishers Inc., Boston - Delft (2008)
Kopparty, S., Saraf, S., Shpilka, A.: Equivalence of polynomial identity testing and polynomial factorization. Comput. Complex. 24(2), 295–331 (2015)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2016 Springer International Publishing Switzerland
About this paper
Cite this paper
Emelyanov, P. (2016). AND–Decomposition of Boolean Polynomials with Prescribed Shared Variables. In: Govindarajan, S., Maheshwari, A. (eds) Algorithms and Discrete Applied Mathematics. CALDAM 2016. Lecture Notes in Computer Science(), vol 9602. Springer, Cham. https://doi.org/10.1007/978-3-319-29221-2_14
Download citation
DOI: https://doi.org/10.1007/978-3-319-29221-2_14
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-29220-5
Online ISBN: 978-3-319-29221-2
eBook Packages: Computer ScienceComputer Science (R0)