{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,1]],"date-time":"2026-04-01T14:37:32Z","timestamp":1775054252456,"version":"3.50.1"},"publisher-location":"Berlin, Heidelberg","reference-count":15,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783662468227","type":"print"},{"value":"9783662468234","type":"electronic"}],"license":[{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2015]]},"DOI":"10.1007\/978-3-662-46823-4_8","type":"book-chapter","created":{"date-parts":[[2015,4,18]],"date-time":"2015-04-18T01:40:54Z","timestamp":1429321254000},"page":"92-101","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":7,"title":["On Tractability of Disjoint AND-Decomposition of Boolean Formulas"],"prefix":"10.1007","author":[{"given":"Pavel","family":"Emelyanov","sequence":"first","affiliation":[]},{"given":"Denis","family":"Ponomaryov","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2015,4,19]]},"reference":[{"key":"8_CR1","unstructured":"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\u201355 (2002)"},{"key":"8_CR2","series-title":"Encyclopedia of Mathematics and its Applications","doi-asserted-by":"publisher","first-page":"39","DOI":"10.1017\/CBO9780511780448.005","volume-title":"Boolean Models and Methods in Mathematics, Computer Science, and Engineering","author":"JC Bioch","year":"2010","unstructured":"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\u201378. Cambridge University Press, New York (2010)"},{"key":"8_CR3","doi-asserted-by":"crossref","unstructured":"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\u2013819. IEEE (2012)","DOI":"10.1109\/DATE.2012.6176606"},{"key":"8_CR4","doi-asserted-by":"crossref","unstructured":"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\u2013591. IEEE Press, Piscataway (2010)","DOI":"10.1109\/ICCAD.2010.5654210"},{"key":"8_CR5","volume-title":"Advanced Techniques in Logic Synthesis, Optimizations and Applications.","year":"2011","unstructured":"Khatri, S.P., Gulati, K. (eds.): Advanced Techniques in Logic Synthesis, Optimizations and Applications. Springer, New York (2011)"},{"key":"8_CR6","unstructured":"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)"},{"key":"8_CR7","volume-title":"FPGA architecture: survey and challenges","author":"I Kuon","year":"2008","unstructured":"Kuon, I., Tessier, R., Rose, J.: FPGA architecture: survey and challenges. Now Publishers Inc, Boston - Delft (2008)"},{"key":"8_CR8","doi-asserted-by":"crossref","unstructured":"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\u2013154. ACM, New York (2003)","DOI":"10.1145\/775832.775872"},{"key":"8_CR9","doi-asserted-by":"crossref","unstructured":"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\u2013108. ACM, New York (2001)","DOI":"10.1145\/378239.378353"},{"issue":"4","key":"8_CR10","doi-asserted-by":"publisher","first-page":"667","DOI":"10.1007\/s11202-010-0068-6","volume":"51","author":"A Morozov","year":"2010","unstructured":"Morozov, A., Ponomaryov, D.: On decidability of the decomposability problem for finite theories. Siberian Math. J. 51(4), 667\u2013674 (2010)","journal-title":"Siberian Math. J."},{"key":"8_CR11","unstructured":"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"},{"key":"8_CR12","first-page":"111","volume":"28","author":"D Ponomaryov","year":"2008","unstructured":"Ponomaryov, D.: On decomposability in logical calculi. Bull. Novosib. Comput. Cent. 28, 111\u2013120 (2008). http:\/\/persons.iis.nsk.su\/files\/persons\/pages\/delta-decomp.pdf","journal-title":"Bull. Novosib. Comput. Cent."},{"key":"8_CR13","unstructured":"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"},{"key":"8_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"408","DOI":"10.1007\/978-3-642-14165-2_35","volume-title":"Automata, Languages and Programming","author":"A Shpilka","year":"2010","unstructured":"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\u2013419. Springer, Heidelberg (2010)"},{"issue":"3\u20134","key":"8_CR15","doi-asserted-by":"publisher","first-page":"319","DOI":"10.1023\/B:AIRE.0000006606.01771.8f","volume":"20","author":"B Steinbach","year":"2003","unstructured":"Steinbach, B., Lang, C.: Exploiting functional properties of Boolean functions for optimal multi-level design by bi-decomposition. Artif. Intell. Rev. 20(3\u20134), 319\u2013360 (2003)","journal-title":"Artif. Intell. Rev."}],"container-title":["Lecture Notes in Computer Science","Perspectives of System Informatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-662-46823-4_8","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,5,22]],"date-time":"2025-05-22T18:24:23Z","timestamp":1747938263000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-662-46823-4_8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015]]},"ISBN":["9783662468227","9783662468234"],"references-count":15,"URL":"https:\/\/doi.org\/10.1007\/978-3-662-46823-4_8","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015]]},"assertion":[{"value":"19 April 2015","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}