{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,15]],"date-time":"2024-09-15T14:52:57Z","timestamp":1726411977792},"reference-count":20,"publisher":"Springer Science and Business Media LLC","issue":"1-4","license":[{"start":{"date-parts":[[1987,11,1]],"date-time":"1987-11-01T00:00:00Z","timestamp":562723200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[1987,11]]},"DOI":"10.1007\/bf01840352","type":"journal-article","created":{"date-parts":[[2005,6,28]],"date-time":"2005-06-28T23:41:00Z","timestamp":1120002060000},"page":"97-111","source":"Crossref","is-referenced-by-count":11,"title":["On problem transformability in VLSI"],"prefix":"10.1007","volume":"2","author":[{"given":"Scot","family":"Hornick","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Majid","family":"Sarrafzadeh","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"BF01840352_CR1","doi-asserted-by":"crossref","first-page":"20","DOI":"10.1145\/358808.358814","volume":"23","author":"H. Abelson","year":"1980","unstructured":"H. Abelson and P. Andreae, Information transfer and area-time trade-offs for VLSI multiplication,Comm. ACM,23 (1980), 20\u201322.","journal-title":"Comm. ACM"},{"key":"BF01840352_CR2","doi-asserted-by":"crossref","first-page":"65","DOI":"10.1007\/BF01840437","volume":"1","author":"G. Bilardi","year":"1986","unstructured":"G. Bilardi and F. P. Preparata, Tessellation techniques for area-time lower bounds with applications to sorting,Algorithmica 1 (1986), 65\u201391.","journal-title":"Algorithmica"},{"key":"BF01840352_CR3","doi-asserted-by":"crossref","first-page":"521","DOI":"10.1145\/322261.322269","volume":"28","author":"R. P. Brent","year":"1981","unstructured":"R. P. Brent and H. T. Kung, The chip complexity of binary arithmetic,J. Assoc. Comput. Mach.,28 (1981) 521\u2013534.","journal-title":"J. Assoc. Comput. Mach."},{"key":"BF01840352_CR4","doi-asserted-by":"crossref","first-page":"24","DOI":"10.1287\/opre.31.1.24","volume":"31","author":"E. Dekel","year":"1983","unstructured":"E. Dekel and S. Sahni, Parallel scheduling algorithms,Oper. Res. 31 (1983), 24\u201349.","journal-title":"Oper. Res."},{"key":"BF01840352_CR5","doi-asserted-by":"crossref","unstructured":"P. \u010euri\u0161, Z. Galil, and G. Schnitger, Lower bounds on communication complexity,Proceedings of the 16th Annual ACM Symposium on the Theory of Computing, Washington, DC 1984, pp. 81\u201391.","DOI":"10.1145\/800057.808668"},{"key":"BF01840352_CR6","doi-asserted-by":"crossref","first-page":"245","DOI":"10.1016\/0020-0190(85)90092-4","volume":"21","author":"P. \u010euri\u0161","year":"1985","unstructured":"P. \u010euri\u0161, O. S\u00fdkora, I. Vrt'o, and C. D. Thompson, Tight chip area lower bounds for discrete Fourier and Walsh-Hadamard transformations,Inform. Process. Lett. 21 (1985), 245\u2013247.","journal-title":"Inform. Process. Lett."},{"key":"BF01840352_CR7","unstructured":"E. Gafni, M. C. Loui, P. Tiwari, D. B. West, and S. Zaks, Lower bounds on common knowledge in distributed algorithms, Technical Report ACT-50, Coordinated Science Laboratory, University of Illinois, 1984."},{"key":"BF01840352_CR8","volume-title":"Computers and Intractability","author":"M. R. Garey","year":"1979","unstructured":"M. R. Garey and D. S. Johnson,Computers and Intractability, W. H. Freeman, San Francisco, 1979."},{"key":"BF01840352_CR9","doi-asserted-by":"crossref","unstructured":"F. T. Leighton, Tight bounds on the complexity of parallel sorting,Proceedings of the 16th Annual ACM Symposium on the Theory of Computing, Washington, DC, 1984, pp. 71\u201380.","DOI":"10.1145\/800057.808667"},{"key":"BF01840352_CR10","first-page":"125","volume-title":"VLSI: Algorithms and Architectures","author":"E. Lodi","year":"1984","unstructured":"E. Lodi and L. Pagli, A VLSI solution to the vertical segment visibility problem, inVLSI: Algorithms and Architectures, North-Holland, Amsterdam, 1984, pp. 125\u2013134 (a preliminary version)."},{"key":"BF01840352_CR11","doi-asserted-by":"crossref","unstructured":"K. Mehlhorn and E. M. Schmidt, Las Vegas is better than determinism in VLSI and distributed computing,Proceedings of the 14th Annual ACM Symposium on the Theory of Computing, San Francisco, CA, 1982, pp. 330\u2013337.","DOI":"10.1145\/800070.802208"},{"key":"BF01840352_CR12","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-1098-6","volume-title":"Computational Geometry","author":"F. P. Preparata","year":"1985","unstructured":"F. P. Preparata and M. Shamos,Computational Geometry, Springer-Verlag, New York, 1985."},{"key":"BF01840352_CR13","doi-asserted-by":"crossref","first-page":"355","DOI":"10.1109\/TC.1985.5009386","volume":"34","author":"A. R. Siegel","year":"1985","unstructured":"A. R. Siegel, Minimum storage sorting networks,IEEE Trans. Comput.,34 (1985), 355\u2013361.","journal-title":"IEEE Trans. Comput."},{"key":"BF01840352_CR14","doi-asserted-by":"crossref","unstructured":"A. R. Siegel, Aspects of information flow in VLSI circuits,Proceedings of the 18th Annual ACM Symposium on the Theory of Computing, Berkeley, CA, 1986, pp. 448\u2013459.","DOI":"10.1145\/12130.12177"},{"key":"BF01840352_CR15","unstructured":"C. D. Thompson, A complexity theory for VLSI, Ph.D. Thesis, Department of Computer Science, Carnegie-Mellon University, 1980."},{"key":"BF01840352_CR16","unstructured":"J. D. Ullman,Computational Aspects of VLSI, Computer Science Press, 1983."},{"key":"BF01840352_CR17","doi-asserted-by":"crossref","first-page":"294","DOI":"10.1109\/TC.1983.1676221","volume":"32","author":"J. Vuillemin","year":"1983","unstructured":"J. Vuillemin, A combinatorial limit to the computing power of VLSI circuits,IEEE Trans. Comput.,32 (1983), 294\u2013300.","journal-title":"IEEE Trans. Comput."},{"key":"BF01840352_CR18","unstructured":"I.-C. Wu, Area-time tradeoffs in VLSI algorithms, M.Sc. Thesis, National Taiwan University, 1984."},{"key":"BF01840352_CR19","doi-asserted-by":"crossref","unstructured":"A. C. Yao, Some complexity questions related to distributive computing,Proceedings of the 11th Annual ACM Symposium on the Theory of Computing, Atlanta, GA, 1979, pp. 209\u2013213.","DOI":"10.1145\/800135.804414"},{"key":"BF01840352_CR20","doi-asserted-by":"crossref","unstructured":"A. C. Yao, The entropic limitations on VLSI computations,Proceedings of the 13th Annual ACM Symposium on the Theory of Computing, Milwaukee, WI, 1981, pp. 308\u2013311.","DOI":"10.1145\/800076.802483"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01840352.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF01840352\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01840352","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,4,7]],"date-time":"2020-04-07T21:48:43Z","timestamp":1586296123000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF01840352"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1987,11]]},"references-count":20,"journal-issue":{"issue":"1-4","published-print":{"date-parts":[[1987,11]]}},"alternative-id":["BF01840352"],"URL":"https:\/\/doi.org\/10.1007\/bf01840352","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[1987,11]]}}}