{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T17:48:17Z","timestamp":1725558497472},"publisher-location":"Berlin, Heidelberg","reference-count":26,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540406716"},{"type":"electronic","value":"9783540451389"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2003]]},"DOI":"10.1007\/978-3-540-45138-9_23","type":"book-chapter","created":{"date-parts":[[2010,6,22]],"date-time":"2010-06-22T18:41:48Z","timestamp":1277232108000},"page":"290-299","source":"Crossref","is-referenced-by-count":0,"title":["Lower Bounds for General Graph\u2013Driven Read\u2013Once Parity Branching Programs"],"prefix":"10.1007","author":[{"given":"Henrik","family":"Brosenne","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Matthias","family":"Homeister","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Stephan","family":"Waack","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"23_CR1","doi-asserted-by":"crossref","unstructured":"Ajtai, M.: A non-linear time lower bound for Boolean branching programs. In: Proceedings, 40th FOCS, pp. 60\u201370 (1999)","DOI":"10.1109\/SFFCS.1999.814578"},{"key":"23_CR2","doi-asserted-by":"crossref","unstructured":"Beame, P., Saks, M., Sun, X., Vee, E.: Super\u2013linear time-space tradeoff lower bounds for randomized computations. In: Proceedings, 41st FOCS, pp. 169\u2013179 (2000)","DOI":"10.1109\/SFCS.2000.892078"},{"key":"23_CR3","doi-asserted-by":"crossref","unstructured":"Beame, P., Vee, E.: Time-space trade-offs, multiparty communication complexity, and nearest neighbour problems. In: Proceedings, 34th STOC, pp. 688\u2013697 (2002)","DOI":"10.1145\/509907.510006"},{"key":"23_CR4","doi-asserted-by":"crossref","unstructured":"Bollig, B., Waack, S., Woelfel, P.: Parity graph-driven read-once branching programs and an exponential lower bound for integer multiplication. In: Proceedings 2nd IFIP International Conference on Theoretical Computer Science (2002)","DOI":"10.1007\/978-0-387-35608-2_8"},{"key":"23_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"491","DOI":"10.1007\/3-540-60922-9_40","volume-title":"STACS 96","author":"B. Bollig","year":"1996","unstructured":"Bollig, B., Wegener, I.: Read-once projections and formal circuit verification with binary decision diagrams. In: Puech, C., Reischuk, R. (eds.) STACS 1996. LNCS, vol.\u00a01046, pp. 491\u2013502. Springer, Heidelberg (1996)"},{"key":"23_CR6","series-title":"Lecture Notes in Computer Science","volume-title":"Proceedings, 27th MFCS","author":"B. Bollig","year":"2002","unstructured":"Bollig, B., Woelfel, P.: A lower bound technique for nondeterministic graphdriven read-once branching programs and its applications. In: Proceedings, 27th MFCS. LNCS, Springer, Heidelberg (2002)"},{"key":"23_CR7","doi-asserted-by":"publisher","first-page":"45","DOI":"10.1016\/0304-3975(94)00181-H","volume":"145","author":"Y. Breitbart","year":"1995","unstructured":"Breitbart, Y., Hunt, H.B., Rosenkrantz, D.: The size of binary decision diagrams representing Boolean functions. Theoretical Computer Science\u00a0145, 45\u201369 (1995)","journal-title":"Theoretical Computer Science"},{"key":"23_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"212","DOI":"10.1007\/3-540-44683-4_19","volume-title":"Mathematical Foundations of Computer Science 2001","author":"H. Brosenne","year":"2001","unstructured":"Brosenne, H., Homeister, M., Waack, S.: Graph-driven free parity BDDs: Algorithms and lower bounds. In: Sgall, J., Pultr, A., Kolman, P. (eds.) MFCS 2001. LNCS, vol.\u00a02136, pp. 212\u2013223. Springer, Heidelberg (2001)"},{"key":"23_CR9","first-page":"688","volume-title":"Proceedings, 22nd DAC","author":"R.E. Bryant","year":"1985","unstructured":"Bryant, R.E.: Symbolic manipulation of Boolean functions using a graphical representation. In: Proceedings, 22nd DAC, Piscataway, pp. 688\u2013694. IEEE, Los Alamitos (1985)"},{"key":"23_CR10","doi-asserted-by":"publisher","first-page":"677","DOI":"10.1109\/TC.1986.1676819","volume":"35","author":"R.E. Bryant","year":"1986","unstructured":"Bryant, R.E.: Graph-based algorithms for Boolean function manipulation. IEEE Transactions on Computers\u00a035, 677\u2013691 (1986)","journal-title":"IEEE Transactions on Computers"},{"key":"23_CR11","doi-asserted-by":"publisher","first-page":"205","DOI":"10.1109\/12.73590","volume":"40","author":"R. Bryant","year":"1991","unstructured":"Bryant, R.: On the complexity of VLSI implementations of Boolean functions with applications to integer multiplication. IEEE Transactions on Computers\u00a040, 205\u2013213 (1991)","journal-title":"IEEE Transactions on Computers"},{"key":"23_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"576","DOI":"10.1007\/3-540-56503-5_57","volume-title":"STACS 93","author":"J. Gergov","year":"1993","unstructured":"Gergov, J., Meinel, C.: Frontiers of feasible and probabilistic feasible Boolean manipulation with branching programs. In: Enjalbert, P., Wagner, K.W., Finkel, A. (eds.) STACS 1993. LNCS, vol.\u00a0665, pp. 576\u2013585. Springer, Heidelberg (1993)"},{"key":"23_CR13","doi-asserted-by":"publisher","first-page":"273","DOI":"10.1007\/BF00709139","volume":"8","author":"J. Gergov","year":"1996","unstructured":"Gergov, J., Meinel, C.: Mod-2-OBDDs \u2013 a data structure that generalizes exor-sum-of-products and ordered binary decision diagrams. Formal Methods in System Design\u00a08, 273\u2013282 (1996)","journal-title":"Formal Methods in System Design"},{"key":"23_CR14","doi-asserted-by":"publisher","first-page":"267","DOI":"10.1016\/S0020-0190(99)00027-7","volume":"69","author":"S. Jukna","year":"1999","unstructured":"Jukna, S.: Linear codes are hard for oblivious read-once parity branching programs. Information Processing Letters\u00a069, 267\u2013269 (1999)","journal-title":"Information Processing Letters"},{"key":"23_CR15","doi-asserted-by":"publisher","first-page":"267","DOI":"10.1016\/0304-3975(91)90021-S","volume":"86","author":"M. Krause","year":"1991","unstructured":"Krause, M., Meinel, C., Waack, S.: Separating the eraser Turing machine classes Le, NLe, co-NLe, and Pe. Theoretical Computer Science\u00a086, 267\u2013275 (1991)","journal-title":"Theoretical Computer Science"},{"key":"23_CR16","first-page":"99","volume":"24","author":"M. Krause","year":"1988","unstructured":"Krause, M.: Exponential lower bounds on the complexity of local and real-time branching programs. Journal of Information Processing and Cybernetics (EIK)\u00a024, 99\u2013110 (1988)","journal-title":"Journal of Information Processing and Cybernetics (EIK)"},{"key":"23_CR17","volume-title":"The Theory of Error\u2013Correcting Codes","author":"E.J. MacWilliams","year":"1977","unstructured":"MacWilliams, E.J., Sloane, N.J.A.: The Theory of Error\u2013Correcting Codes. Elsevier, Amsterdam (1977)"},{"key":"23_CR18","unstructured":"Meinel, C., Sack, H.: Heuristics for \u2295-OBDDs. In: Proceedings, IEEE\/ACM International Workshop of Logig and Synthesis, pp. 304\u2013309 (2001)"},{"key":"23_CR19","unstructured":"Meinel, C., Sack, H.: Improving XOR-node placements for \u2295-OBDDs. In: Proceedings, 5th International Workshop of Reed-Muller Expansion in Circuit Design, pp. 51\u201355 (2001)"},{"key":"23_CR20","first-page":"999","volume":"7","author":"\u00c8.I. Nechiporuk","year":"1966","unstructured":"Nechiporuk, \u00c8.I.: A Boolean function. Sov. Math. Doklady\u00a07, 999\u20131000 (1966)","journal-title":"Sov. Math. Doklady"},{"key":"23_CR21","unstructured":"Sack, H.: Improving the Power of OBDDs by Integrating Parity Nodes. PhD thesis, Univ. Trier (2001)"},{"key":"23_CR22","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"650","DOI":"10.1007\/3-540-44612-5_60","volume-title":"Mathematical Foundations of Computer Science 2000","author":"P. Savick\u00fd","year":"2000","unstructured":"Savick\u00fd, P., Sieling, D.: A hierarchy result for read\u2013once branching programs with restricted parity nondeterminism. In: Nielsen, M., Rovan, B. (eds.) MFCS 2000. LNCS, vol.\u00a01893, pp. 650\u2013659. Springer, Heidelberg (2000)"},{"key":"23_CR23","doi-asserted-by":"publisher","first-page":"238","DOI":"10.1016\/0304-3975(94)00078-W","volume":"141","author":"D. Sieling","year":"1995","unstructured":"Sieling, D., Wegener, I.: Graph driven BDDs \u2013 a new data structure for Boolean functions. Theoretical Computer Science\u00a0141, 238\u2013310 (1995)","journal-title":"Theoretical Computer Science"},{"key":"23_CR24","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"356","DOI":"10.1007\/3-540-46691-6_29","volume-title":"Foundations of Software Technology and Theoretical Computer Science","author":"D. Sieling","year":"1999","unstructured":"Sieling, D.: Lower bounds for linear transformed OBDDs and FBDDs. In: Pandu Rangan, C., Raman, V., Sarukkai, S. (eds.) FST TCS 1999. LNCS, vol.\u00a01738, pp. 356\u2013368. Springer, Heidelberg (1999)"},{"key":"23_CR25","doi-asserted-by":"publisher","first-page":"61","DOI":"10.1006\/inco.2000.3022","volume":"166","author":"S.. Waack","year":"2001","unstructured":"Waack, S.: On the descriptive and algorithmic power of parity ordered binary decision diagrams. Information and Computation\u00a0166, 61\u201370 (2001)","journal-title":"Information and Computation"},{"key":"23_CR26","series-title":"SIAM Monographs on Discrete Mathematics and Applications","doi-asserted-by":"publisher","DOI":"10.1137\/1.9780898719789","volume-title":"Branching Programs and Binary Decision Diagrams \u2013 Theory and Applications","author":"I. Wegener","year":"2000","unstructured":"Wegener, I.: Branching Programs and Binary Decision Diagrams \u2013 Theory and Applications. SIAM Monographs on Discrete Mathematics and Applications. SIAM, Philadelphia (2000)"}],"container-title":["Lecture Notes in Computer Science","Mathematical Foundations of Computer Science 2003"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-45138-9_23","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,30]],"date-time":"2019-05-30T05:53:45Z","timestamp":1559195625000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-45138-9_23"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2003]]},"ISBN":["9783540406716","9783540451389"],"references-count":26,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-45138-9_23","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2003]]}}}