{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T13:25:44Z","timestamp":1725456344271},"publisher-location":"Berlin, Heidelberg","reference-count":20,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540634379"},{"type":"electronic","value":"9783540695479"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1997]]},"DOI":"10.1007\/bfb0029991","type":"book-chapter","created":{"date-parts":[[2005,12,1]],"date-time":"2005-12-01T06:24:59Z","timestamp":1133418299000},"page":"478-487","source":"Crossref","is-referenced-by-count":2,"title":["A hierarchy for (1, +k)-branching programs with respect to k"],"prefix":"10.1007","author":[{"given":"P.","family":"Savick\u00fd","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"S.","family":"\u017d\u00e1k","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,6,17]]},"reference":[{"key":"48_CR1","unstructured":"N. Alon, M. B. Nathanson and 1. Z. Ruzsa, The polynomial method and restricted sums of congruence classes, J. Number Theory, to appear."},{"key":"48_CR2","doi-asserted-by":"publisher","first-page":"153","DOI":"10.1016\/0022-0000(87)90010-9","volume":"35","author":"L. Babai","year":"1987","unstructured":"L. Babai, P. Hajnal, E. Szemeredi and G. Turan, A lower bound for read-once-only branching programs, Journal of Computer and Systems Sciences, vol. 35 (1987), 153\u2013162.","journal-title":"Journal of Computer and Systems Sciences"},{"key":"48_CR3","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/BF01200404","volume":"3","author":"A. Borodin","year":"1993","unstructured":"A. Borodin, A. Razborov and R. Smolensky, On Lower Bounds for Read-k-times Branching Programs, Computational Complexity 3 (1993) 1\u201318.","journal-title":"Computational Complexity"},{"key":"48_CR4","doi-asserted-by":"crossref","first-page":"140","DOI":"10.1112\/blms\/26.2.140","volume":"26","author":"J. A. Dias da Silva","year":"1994","unstructured":"J. A. Dias da Silva and Y. O. Hamidoune, Cyclic spaces for Grassmann derivatives and additive theory, Bull. London Math. Soc., 26 (1994), 140\u2013146.","journal-title":"Bull. London Math. Soc."},{"key":"48_CR5","doi-asserted-by":"crossref","first-page":"90","DOI":"10.1007\/BFb0028795","volume":"199","author":"P. E. Dunne","year":"1985","unstructured":"P. E. Dunne, Lower bounds on the complexity of one-time-only branching programs, In Proceedings of the FCT, Lecture Notes in Computer Science, 199 (1985), 90\u201399.","journal-title":"Proceedings of the FCT, Lecture Notes in Computer Science"},{"issue":"1","key":"48_CR6","doi-asserted-by":"crossref","first-page":"75","DOI":"10.1051\/ita\/1995290100751","volume":"29","author":"S. Jukna","year":"1995","unstructured":"S. Jukna, A Note on Read-k-times Branching Programs, RAIRO Theoretical Informatics and Applications, vol. 29, Nr. 1 (1995), pp. 75\u201383.","journal-title":"RAIRO Theoretical Informatics and Applications"},{"key":"48_CR7","doi-asserted-by":"publisher","first-page":"113","DOI":"10.1016\/0304-3975(88)90166-1","volume":"57","author":"S. Jukna","year":"1988","unstructured":"S. Jukna, Entropy of Contact Circuits and Lower Bounds on Their Complexity, Theoretical Computer Science, 57 (1988), pp. 113\u2013129.","journal-title":"Theoretical Computer Science"},{"key":"48_CR8","unstructured":"S. Jukna, A. A. Razborov, Neither Reading Few Bits Twice nor Reading Illegally Helps Much, TR96-037, ECCC, Trier."},{"key":"48_CR9","first-page":"61","volume":"51","author":"E. A. Okolnishnikova","year":"1991","unstructured":"E. A. Okolnishnikova, Lower bounds for branching programs computing characteristic functions of binary codes (in Russian), Metody diskretnogo Analiza, 51 (1991), 61\u201383.","journal-title":"Metody diskretnogo Analiza"},{"issue":"4","key":"48_CR10","first-page":"54","volume":"2","author":"E. A. Okolnishnikova","year":"1995","unstructured":"E. A. Okolnishnikova, Comparing the complexity of binary k-programs (in Russian), Diskretnyj analiz i issledovanije operacij, 1995. Vol. 2, No. 4, pp. 54\u201373.","journal-title":"Diskretnyj analiz i issledovanije operacij"},{"key":"48_CR11","doi-asserted-by":"crossref","unstructured":"S. J. Ponzio, A lower bound for integer multiplication with read-once branching programs, Proceedings of 27 Annual ACM Symposium on the Theory of Computing, Las Vegas, 1995, pp. 130\u2013139.","DOI":"10.1145\/225058.225098"},{"key":"48_CR12","series-title":"Primzahlverteilung","volume-title":"Distribution of Prime Numbers","author":"K. Prachar","year":"1957","unstructured":"K. Prachar, Distribution of Prime Numbers (in German), Primzahlverteilung, Springer-Verlag, Berlin-G\u00f6ttingen-Heidelberg, 1957."},{"key":"48_CR13","unstructured":"P. Savick\u00fd, S. \u017e\u00e1k, A Lower Bound on Branching Programs Reading Some Bits Twice, to appear in TCS."},{"key":"48_CR14","unstructured":"P. Savick\u00fd, S. \u017e\u00e1k, A Large Lower bound for 1-branching programs, TR96-036, ECCC, Trier."},{"key":"48_CR15","unstructured":"D. Sieling, New Lower Bounds and Hierarchy Results for Restricted Branching Programs, TR 494, 1993, Univ. Dortmund, to appear in J. of Computer and System Sciences."},{"key":"48_CR16","series-title":"Lecture Notes in Computer Science","first-page":"359","volume-title":"Proc. of Workshop on Graph-Theoretic Concepts in Computer Science WG'94","author":"D. Sieling","year":"1994","unstructured":"D. Sieling and I. Wegener, New Lower bounds and hierarchy results for Restricted Branching Programs, in Proc. of Workshop on Graph-Theoretic Concepts in Computer Science WG'94, Lecture Notes in Computer Science Vol. 903 (Springer,Berlin, 1994) 359\u2013370."},{"key":"48_CR17","unstructured":"J. Simon, M. Szegedy, A New Lower Bound Theorem for Read Only Once Branching Programs and its Applications, Advances in Computational Complexity Theory (J. Cai, editor), DIMACS Series, Vol. 13, AMS (1993) pp. 183\u2013193."},{"key":"48_CR18","doi-asserted-by":"publisher","first-page":"461","DOI":"10.1145\/42282.46161","volume":"35","author":"I. Wegener","year":"1988","unstructured":"I. Wegener, On the Complexity of Branching Programs and Decision Trees for Clique Functions, JACM 35 (1988) 461\u2013471.","journal-title":"JACM"},{"key":"48_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"562","DOI":"10.1007\/BFb0030340","volume-title":"Proc. MFCS'84","author":"S. \u017e\u00e1k","year":"1984","unstructured":"S. \u017e\u00e1k, An Exponential Lower Bound for One-time-only Branching Programs, in Proc. MFCS'84, Lecture Notes in Computer Science Vol. 176 (Springer, Berlin, 1984) 562\u2013566."},{"key":"48_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"319","DOI":"10.1007\/3-540-60246-1_138","volume-title":"Proc. MFCS'95","author":"S. \u017e\u00e1k","year":"1995","unstructured":"S. \u017e\u00e1k, A superpolynomial lower bound for (1,+k(n))-branching programs, in Proc. MFCS'95, Lecture Notes in Computer Science Vol. 969 (Springer, Berlin, 1995) 319\u2013325."}],"container-title":["Lecture Notes in Computer Science","Mathematical Foundations of Computer Science 1997"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BFb0029991","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,2,6]],"date-time":"2019-02-06T06:35:16Z","timestamp":1549434916000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BFb0029991"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1997]]},"ISBN":["9783540634379","9783540695479"],"references-count":20,"URL":"https:\/\/doi.org\/10.1007\/bfb0029991","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1997]]}}}