{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T21:02:01Z","timestamp":1725483721652},"publisher-location":"Berlin, Heidelberg","reference-count":16,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540679011"},{"type":"electronic","value":"9783540446125"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2000]]},"DOI":"10.1007\/3-540-44612-5_60","type":"book-chapter","created":{"date-parts":[[2007,5,5]],"date-time":"2007-05-05T09:28:20Z","timestamp":1178357300000},"page":"650-659","source":"Crossref","is-referenced-by-count":7,"title":["A Hierarchy Result for Read-Once Branching Programs with Restricted Parity Nondeterminism"],"prefix":"10.1007","author":[{"given":"Petr","family":"Savick\u00fd","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Detlef","family":"Sieling","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2001,6,1]]},"reference":[{"key":"60_CR1","doi-asserted-by":"crossref","unstructured":"Ajtai, M. (1999). A non-linear time lower bound for Boolean branching programs. In Proc. of 40th Symposium on Foundations of Computer Science, 60\u201370.","DOI":"10.1109\/SFFCS.1999.814578"},{"key":"60_CR2","doi-asserted-by":"publisher","first-page":"487","DOI":"10.1007\/s002240000128","volume":"32","author":"B. Bollig","year":"1999","unstructured":"Bollig, B. and Wegener, I. (1999). Complexity theoretical results on partitioned (nondeterministic) binary decision diagrams. Theory of Computing Systems 32, 487\u2013503.","journal-title":"Theory of Computing Systems"},{"key":"60_CR3","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/BF01200404","volume":"3","author":"A. Borodin","year":"1993","unstructured":"Borodin, A., Razborov, A. and Smolensky, R. (1993). On lower bounds for read-k-times branching programs. Computational Complexity 3, 1\u201318.","journal-title":"Computational Complexity"},{"key":"60_CR4","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. (1986). Graph-based algorithms for Boolean function manipulation. IEEE Transactions on Computers 35, 677\u2013691.","journal-title":"IEEE Transactions on Computers"},{"key":"60_CR5","unstructured":"Jain, J., Bitner, J., Fussell, D.S. and Abraham, J.A. (1992). Functional partitioning for verification and related problems. Brown MIT VLSI Conference, 210\u2013226."},{"key":"60_CR6","doi-asserted-by":"publisher","first-page":"113","DOI":"10.1016\/0304-3975(88)90166-1","volume":"57","author":"S. Jukna","year":"1988","unstructured":"Jukna, S. (1988). Entropy of contact circuits and lower bounds on their complexity. Theoretical Computer Science 57, 113\u2013129.","journal-title":"Theoretical Computer Science"},{"key":"60_CR7","series-title":"Lect Notes Comput Sci","doi-asserted-by":"publisher","first-page":"319","DOI":"10.1007\/BFb0029975","volume-title":"Proc. of Mathematical Foundations of Computer Science","author":"S. Jukna","year":"1997","unstructured":"Jukna, S., Razborov, A., Savick\u00fd, P. and Wegener, I. (1997). On P versus NP\u2229 co-NP for decision trees and read-once branching programs. In Proc. of Mathematical Foundations of Computer Science, Springer, Lecture Notes in Computer Science 1295, 319\u2013326."},{"key":"60_CR8","series-title":"Lect Notes Comput Sci","doi-asserted-by":"publisher","first-page":"385","DOI":"10.1007\/BFb0029633","volume-title":"Proc. of Mathematical Foundations of Computer Science","author":"M. Krause","year":"1990","unstructured":"Krause, M. (1990). Separating \u2295L from L, NL, co-NL and AL (= P) for oblivious Turing machines of linear access time. In Proc. of Mathematical Foundations of Computer Science, Springer, Lecture Notes in Computer Science 452, 385\u2013391."},{"key":"60_CR9","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. and Waack, S. (1991). Separating the eraser Turing machine classes L\n                           e, NL\n                           e, co-NL\n                           e and P\n                           e. Theoretical Computer Science 86, 267\u2013275.","journal-title":"Theoretical Computer Science"},{"key":"60_CR10","doi-asserted-by":"publisher","first-page":"163","DOI":"10.1016\/0890-5401(90)90046-K","volume":"85","author":"C. Meinel","year":"1990","unstructured":"Meinel, C. (1990). Polynomial size \u03a9-branching programs and their computational power. Information and Computation 85, 163\u2013182.","journal-title":"Information and Computation"},{"key":"60_CR11","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"47","DOI":"10.1007\/3-540-54458-5_49","volume-title":"Proc. of Fundamentals in Computing Theory","author":"A. A. Razborov","year":"1991","unstructured":"Razborov, A. A. (1991). Lower bounds for deterministic and nondeterministic branching programs. In Proc. of Fundamentals in Computing Theory, Springer, Lecture Notes in Computer Science 529, 47\u201360."},{"key":"60_CR12","unstructured":"Sauerhoff, M. (1999). An improved hierarchy result for partitioned BDDs. To appear in Theory of Computing Systems."},{"key":"60_CR13","series-title":"Lect Notes Comput Sci","doi-asserted-by":"publisher","first-page":"342","DOI":"10.1007\/3-540-46691-6_28","volume-title":"Proc. of 19th Conference on Foundations of Software Technology and Theoretical Computer Science","author":"M. Sauerhoff","year":"1999","unstructured":"Sauerhoff, M. (1999). Computing with restricted nondeterminism: the dependence of the OBDD size on the number of nondeterministic variables. In Proc. of 19th Conference on Foundations of Software Technology and Theoretical Computer Science, Springer, Lecture Notes in Computer Science 1738, 342\u2013355."},{"key":"60_CR14","doi-asserted-by":"crossref","first-page":"461","DOI":"10.1145\/42282.46161","volume":"35","author":"I. Wegener","year":"1988","unstructured":"Wegener, I. (1988). On the complexity of branching programs and decision trees for clique functions. Journal of the Association for Computing Machinery 35, 461\u2013471.","journal-title":"Journal of the Association for Computing Machinery"},{"key":"60_CR15","unstructured":"Wegener, I. (2000). Branching Programs and Binary Decision Diagrams\u2014Theory and Applications. SIAM Monographs on Discrete Mathematics and Its Applications, in print."},{"key":"60_CR16","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"562","DOI":"10.1007\/BFb0030340","volume-title":"Proc. of Mathematical Foundations of Computer Science","author":"S. \u017d\u00e1k","year":"1984","unstructured":"\u017d\u00e1k, S. (1984). An exponential lower bound for one-time-only branching programs. In Proc. of Mathematical Foundations of Computer Science, Springer, Lecture Notes in Computer Science 176, 562\u2013566."}],"container-title":["Lecture Notes in Computer Science","Mathematical Foundations of Computer Science 2000"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-44612-5_60","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,2,16]],"date-time":"2019-02-16T09:43:59Z","timestamp":1550310239000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-44612-5_60"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2000]]},"ISBN":["9783540679011","9783540446125"],"references-count":16,"URL":"https:\/\/doi.org\/10.1007\/3-540-44612-5_60","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2000]]}}}