{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,4,3]],"date-time":"2022-04-03T18:57:52Z","timestamp":1649012272256},"reference-count":26,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[1995,6,1]],"date-time":"1995-06-01T00:00:00Z","timestamp":801964800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Comput Complexity"],"published-print":{"date-parts":[[1995,6]]},"DOI":"10.1007\/bf01268142","type":"journal-article","created":{"date-parts":[[2005,3,23]],"date-time":"2005-03-23T22:03:06Z","timestamp":1111615386000},"page":"132-154","source":"Crossref","is-referenced-by-count":0,"title":["PI k mass production and an optimal circuit for the Ne?iporuk slice"],"prefix":"10.1007","volume":"5","author":[{"given":"Alain P.","family":"Hiltgen","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mike S.","family":"Paterson","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"1","key":"CR1","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/BF02579196","volume":"7","author":"N. Alon","year":"1987","unstructured":"N. Alon andR. B. Boppana, The monotone circuit complexity of Boolean functions.Combinatorica 7:1 (1987), 1?22.","journal-title":"Combinatorica"},{"key":"CR2","first-page":"1033","volume":"282","author":"A. E. Andreev","year":"1985","unstructured":"A. E. Andreev, On a method for obtaining lower bounds for the complexity of individual monotone functions.Dokl. Akad. Nauk 282 (1985), 1033?1037. English Translation:Sov. Math. Dokl. 31 (1985), 530?534.","journal-title":"Dokl. Akad. Nauk"},{"key":"CR3","unstructured":"S. J. Berkowitz, On some relationships between monotone and non-monotone circuit complexity.Technical Report, University of Toronto, 1982."},{"key":"CR4","unstructured":"S. W. Boyack,The Robustness of Combinatorial Measures of Boolean Matrix Complexity. Ph.D. thesis, Massachusetts Institute of Technology, 1985."},{"key":"CR5","unstructured":"P. E. Dunne,Techniques for the Analysis of Monotone Boolean Networks. Ph.D. thesis, University of Warwick, 1984."},{"key":"CR6","doi-asserted-by":"crossref","first-page":"247","DOI":"10.1016\/0304-3975(86)90122-2","volume":"44","author":"P. E. Dunne","year":"1986","unstructured":"P. E. Dunne, The complexity of central slice functions.Theoret. Comput. Sci. 44 (1986), 247?257.","journal-title":"Theoret. Comput. Sci."},{"key":"CR7","doi-asserted-by":"crossref","first-page":"15","DOI":"10.1016\/0304-3975(89)90142-4","volume":"66","author":"P. E. Dunne","year":"1989","unstructured":"P. E. Dunne, On monotone simulations of nonmonotone networks.Theoret. Comput. Sci. 66 (1989), 15?25.","journal-title":"Theoret. Comput. Sci."},{"key":"CR8","doi-asserted-by":"crossref","first-page":"177","DOI":"10.1016\/0304-3975(81)90074-8","volume":"16","author":"G. Galbiati","year":"1981","unstructured":"G. Galbiati andM. J. Fischer, On the complexity of 2-output Boolean networks.Theoret. Comput. Sci. 16 (1981), 177?185.","journal-title":"Theoret. Comput. Sci."},{"key":"CR9","volume-title":"Cryptographically Relevant Contributions to Combinational Complexity Theory, vol. 3 ofETH Series in Information Processing","author":"A. P. Hiltgen","year":"1994","unstructured":"A. P. Hiltgen,Cryptographically Relevant Contributions to Combinational Complexity Theory, vol. 3 ofETH Series in Information Processing, ed.J. L. Massey. Hartung-Gorre, Konstanz, 1994. Reprint of: Ph.D thesis no. 10382, Swiss Federal Institute of Technology, ETH-Z\ufffdrich, 1993."},{"key":"CR10","volume-title":"On the logical complexity of symmetric switching functions in monotone and complete bases","author":"E. A. Lamagna","year":"1973","unstructured":"E. A. Lamagna andJ. E. Savage, On the logical complexity of symmetric switching functions in monotone and complete bases.Technical Report, Brown University, Providence RI, 1973."},{"key":"CR11","doi-asserted-by":"crossref","unstructured":"E. A. Lamagna and J. E. Savage, Combinational complexity of some monotone functions.Proc. 15th Ann. Symp. Switching and Automata Theory (1974), 140?144.","DOI":"10.1109\/SWAT.1974.9"},{"key":"CR12","doi-asserted-by":"crossref","first-page":"371","DOI":"10.1007\/BF00268321","volume":"12","author":"K. Mehlhorn","year":"1979","unstructured":"K. Mehlhorn, Some remarks on Boolean sums.Acta Informatica 12 (1979), 371?375.","journal-title":"Acta Informatica"},{"key":"CR13","first-page":"237","volume":"21","author":"E. I. Ne?iporuk","year":"1969","unstructured":"E. I. Ne?iporuk, On a Boolean matrix.Probl. Kibern. 21 (1969), 237?240. English Translation:Systems Theory Res. 21 (1971), 236?239.","journal-title":"Probl. Kibern."},{"key":"CR14","doi-asserted-by":"crossref","first-page":"383","DOI":"10.1016\/0304-3975(76)90089-X","volume":"2","author":"W. J. Paul","year":"1976","unstructured":"W. J. Paul, Realizing Boolean functions on disjoint sets of variables.Theoret. Comput. Sci. 2 (1976), 383?396.","journal-title":"Theoret. Comput. Sci."},{"key":"CR15","doi-asserted-by":"crossref","first-page":"49","DOI":"10.1016\/0304-3975(80)90034-1","volume":"11","author":"N. Pippenger","year":"1980","unstructured":"N. Pippenger, On another Boolean matrix.Theoret. Comput. Sci. 11 (1980), 49?56. Reprint of: IBM Research Report, Yorktown Heights, 1977.","journal-title":"Theoret. Comput. Sci."},{"key":"CR16","first-page":"887","volume":"37","author":"A. A. Razborov","year":"1985","unstructured":"A. A. Razborov, Lower bounds on monotone complexity of the logical permanent.Matemat. Zametki 37 (1985a), 887?900. English Translation:Math. Notes of the Academy of Sciences of the USSR 37 (1985), 485?493.","journal-title":"Matemat. Zametki"},{"key":"CR17","first-page":"798","volume":"281","author":"A. A. Razborov","year":"1985","unstructured":"A. A. Razborov, Lower bounds for the monotone complexity of some Boolean functions.Dokl. Akad. Nauk 281 (1985b), 798?801. English Translation:Sov. Math. Dokl. 31 (1985), 354?357.","journal-title":"Dokl. Akad. Nauk"},{"key":"CR18","volume-title":"The Complexity of Computing","author":"J. E. Savage","year":"1987","unstructured":"J. E. Savage,The Complexity of Computing. Krieger Publishing Co., Malabar FL, 1987. Reprint of: First edition published by Wiley, New York, 1976."},{"key":"CR19","doi-asserted-by":"crossref","first-page":"323","DOI":"10.1007\/BF01683282","volume":"10","author":"L. J. Stockmeyer","year":"1977","unstructured":"L. J. Stockmeyer, On the combinational complexity of certain symmetric Boolean functions.Math. Systems Theory 10 (1977), 323?336.","journal-title":"Math. Systems Theory"},{"key":"CR20","doi-asserted-by":"crossref","first-page":"121","DOI":"10.1016\/S0167-5060(08)70326-1","volume":"2","author":"R. E. Tarjan","year":"1978","unstructured":"R. E. Tarjan, Complexity of monotone networks for computing conjunctions.Ann. Disc. Math 2 (1978), 121?133.","journal-title":"Ann. Disc. Math"},{"issue":"6","key":"CR21","first-page":"937","volume":"15","author":"D. Uhlig","year":"1974","unstructured":"D. Uhlig, On the synthesis of self-correcting schemes from functional elements with a small number of reliable elements.Matemat. Zametki 15:6 (1974), 937?944. English Translation:Math. Notes of the Academy of Sciences of the USSR 15 (1974), 558?562.","journal-title":"Matemat. Zametki"},{"issue":"2","key":"CR22","doi-asserted-by":"crossref","first-page":"531","DOI":"10.1137\/0215037","volume":"15","author":"L. G. Valiant","year":"1986","unstructured":"L. G. Valiant, Negation is powerless for Boolean slice functions.SIAM J. Comput. 15:2 (1986), 531?535.","journal-title":"SIAM J. Comput."},{"key":"CR23","doi-asserted-by":"crossref","first-page":"109","DOI":"10.1007\/BF00263988","volume":"13","author":"I. Wegener","year":"1980","unstructured":"I. Wegener, A new lower bound on the monotone network complexity of Boolean sums.Acta Informatica 13 (1980), 109?114.","journal-title":"Acta Informatica"},{"key":"CR24","doi-asserted-by":"crossref","first-page":"55","DOI":"10.1016\/0304-3975(85)90209-9","volume":"38","author":"I. Wegener","year":"1985","unstructured":"I. Wegener, On the complexity of slice functions.Theoret. Comput. Sci. 38 (1985), 55?68.","journal-title":"Theoret. Comput. Sci."},{"key":"CR25","doi-asserted-by":"crossref","first-page":"201","DOI":"10.1016\/0304-3975(86)90176-3","volume":"43","author":"I. Wegener","year":"1986","unstructured":"I. Wegener, More on the complexity of slice functions.Theoret. Comput. Sci. 43, (1986), 201?211.","journal-title":"Theoret. Comput. Sci."},{"key":"CR26","volume-title":"The Complexity of Boolean Functions","author":"I. Wegener","year":"1987","unstructured":"I. Wegener,The Complexity of Boolean Functions. New York: Wiley (Stuttgart: Teubner), 1987."}],"container-title":["Computational Complexity"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01268142.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF01268142\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01268142","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,4,30]],"date-time":"2019-04-30T14:13:47Z","timestamp":1556633627000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF01268142"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1995,6]]},"references-count":26,"journal-issue":{"issue":"2","published-print":{"date-parts":[[1995,6]]}},"alternative-id":["BF01268142"],"URL":"https:\/\/doi.org\/10.1007\/bf01268142","relation":{},"ISSN":["1016-3328","1420-8954"],"issn-type":[{"value":"1016-3328","type":"print"},{"value":"1420-8954","type":"electronic"}],"subject":[],"published":{"date-parts":[[1995,6]]}}}