Abstract
Disjoint AND-decomposition of a boolean formula means its representation as a conjunction of two (or several) formulas having disjoint sets of variables. We show that deciding AND-decomposability is intractable in general for boolean formulas given in CNF or DNF and prove tractability of computing AND-decompositions of boolean formulas given in positive DNF, Full DNF, and ANF. The results follow from tractability of multilinear polynomial factorization over the finite field of order 2, for which we provide a polytime factorization algorithm based on identity testing for partial derivatives of multilinear polynomials.
An extended version of the paper containing proofs is available from http://persons.iis.nsk.su/files/persons/pages/and-decomp-full.pdf.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Bengtsson, T., Martinelli, A., Dubrova, E.: A fast heuristic algorithm for disjoint decomposition of Boolean functions. In: Notes of the 11th IEEE/ACM International Workshop on Logic & Synthesis (IWLS 2002), pp. 51–55 (2002)
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)
Chen, H., Janota, M., Marques-Silva, J.: QBF-based boolean function bi-decomposition. In: Proceedings of the Design, Automation & Test in Europe Conference (DATE 2012), pp. 816–819. IEEE (2012)
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 2010), pp. 586–591. IEEE Press, Piscataway (2010)
Khatri, S.P., Gulati, K. (eds.): Advanced Techniques in Logic Synthesis, Optimizations and Applications. Springer, New York (2011)
Konev, B., Lutz, C., Ponomaryov, D., Wolter, F.: Decomposing description logic ontologies. In: Proceedings of the Twelfth International Conference on Principles of Knowledge Representation and Reasoning (KR 2010). AAAI Press, Palo Alto (2010)
Kuon, I., Tessier, R., Rose, J.: FPGA architecture: survey and challenges. Now Publishers Inc, Boston - Delft (2008)
Mishchenko, A., Sasao, T.: Large-scale SOP minimization using decomposition and functional properties. In: Proceedings of the 40th ACM/IEEE Design Automation Conference (DAC 2003), pp. 149–154. ACM, New York (2003)
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 2001), pp. 103–108. ACM, New York (2001)
Morozov, A., Ponomaryov, D.: On decidability of the decomposability problem for finite theories. Siberian Math. J. 51(4), 667–674 (2010)
Perkowski, M.A., Grygiel, S.: A survey of literature on function decomposition, Version IV. PSU Electrical Engineering Department report, Department of Electrical Engineering, Portland State University, Portland, Oregon, USA, November 1995
Ponomaryov, D.: On decomposability in logical calculi. Bull. Novosib. Comput. Cent. 28, 111–120 (2008). http://persons.iis.nsk.su/files/persons/pages/delta-decomp.pdf
Ponomaryov, D.: The algorithmic complexity of decomposability in fragments of first-order logic, Research Note. In: Abstract appears in Proceedings Logic Colloquium (2014). http://persons.iis.nsk.su/files/persons/pages/sigdecomp.pdf
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)
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)
Acknowledgements
The first author was supported by the Russian Foundation for Humanities, grant No. 13-01-12003B. The second author was supported by the German Research Foundation within the Transregional Collaborative Research Center SFB/TRR 62 “Companion-Technology for Cognitive Technical Systems”.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2015 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Emelyanov, P., Ponomaryov, D. (2015). On Tractability of Disjoint AND-Decomposition of Boolean Formulas. In: Voronkov, A., Virbitskaite, I. (eds) Perspectives of System Informatics. PSI 2014. Lecture Notes in Computer Science(), vol 8974. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-662-46823-4_8
Download citation
DOI: https://doi.org/10.1007/978-3-662-46823-4_8
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-662-46822-7
Online ISBN: 978-3-662-46823-4
eBook Packages: Computer ScienceComputer Science (R0)