{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T13:10:18Z","timestamp":1725455418207},"publisher-location":"Berlin\/Heidelberg","reference-count":47,"publisher":"Springer-Verlag","isbn-type":[{"type":"print","value":"3540167838"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/bfb0016239","type":"book-chapter","created":{"date-parts":[[2005,11,13]],"date-time":"2005-11-13T05:39:17Z","timestamp":1131860357000},"page":"140-153","source":"Crossref","is-referenced-by-count":4,"title":["Systolic arrays: Characterizations and complexity"],"prefix":"10.1007","author":[{"given":"Oscar H.","family":"Ibarra","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"10_CR1","doi-asserted-by":"crossref","unstructured":"Aggarwal, A., A comparative study of X-tree, pyramid and related machines, Proc. 25th IEEE Annual Symp. on Foundation of Computer Science, (1984), 89\u201399.","DOI":"10.1109\/SFCS.1984.715905"},{"issue":"2","key":"10_CR2","doi-asserted-by":"crossref","first-page":"151","DOI":"10.1109\/TC.1985.1676551","volume":"C-34","author":"M. Atallah","year":"1985","unstructured":"Atallah, M. and S.R. Kosaraju, A Generalized dictionary machine for VLSI, IEEE Trans. Comput. C-34, 2 (1985), 151\u2013155.","journal-title":"IEEE Trans. Comput."},{"key":"10_CR3","unstructured":"Bucher, W. and K. Culik II, On real time and linear time cellular automata, RAIRO, Inf. Theoretique, in press."},{"key":"10_CR4","unstructured":"Cappello, P.R. and Steiglitz, K., Using VLSI array designs with geometric transformation, IEEE, (1983)."},{"key":"10_CR5","doi-asserted-by":"crossref","first-page":"114","DOI":"10.1145\/322234.322243","volume":"28-1","author":"A. Chandra","year":"1981","unstructured":"Chandra, A., Kozen, D., and Stockmeyer, L., Alternation, JACM, 28-1 (1981), 114\u2013133.","journal-title":"JACM"},{"key":"10_CR6","unstructured":"Chang, J., O. Ibarra, and M. Palis, Parallel parsing on a one-way array of finite-state machines, Computer Science Department, University of Minnesota, Tech. Rep., May 1985; submitted to IEEE Trans. on Comput."},{"key":"10_CR7","unstructured":"Chang, J., O. Ibarra, and M. Palis, Efficient simulations of simple models of parallel computation by space-bounded TM's and time-bounded alternating TM's, submitted to TCS."},{"key":"10_CR8","unstructured":"Chang, J., M. Chung, O. Ibarra, and K. Rao, Systolic tree implementations of data structures, Computer Science Department, University of Minnesota, Tech. Rep. TR 85-32, Sept. 1985, submitted to IEEE Trans. Comput."},{"key":"10_CR9","unstructured":"Chang, J. and O. Ibarra, A simple sytolic tree algorithm for solving recurrence equations, submitted to IPL."},{"key":"10_CR10","unstructured":"Chen, M., Synthesizing systolic design, International Conference on VLSI, Taiwan, ROC, (1985), 209\u2013215."},{"issue":"3","key":"10_CR11","doi-asserted-by":"crossref","first-page":"302","DOI":"10.1109\/TPAMI.1984.4767522","volume":"6","author":"Y. Chiang","year":"1984","unstructured":"Chiang, Y. and K. Fu, Parallel parsing and VLSI implementations for syntactic pattern recognition, IEEE Trans. on Pattern Analysis and Machine Intelligence, 6, 3 (1984), 302\u2013313.","journal-title":"IEEE Trans. on Pattern Analysis and Machine Intelligence"},{"key":"10_CR12","doi-asserted-by":"crossref","unstructured":"Choffrut, C. and K. Culik II, On real-time cellular automata and trellis automata, Acta Inform., in press.","DOI":"10.1007\/BF00264617"},{"key":"10_CR13","doi-asserted-by":"crossref","first-page":"349","DOI":"10.1109\/T-C.1969.222663","volume":"c-18","author":"S.N. Cole","year":"1969","unstructured":"Cole, S.N., Real-time computation by n-dimensional iterative arrays of finite-state machines, IEEE Trans. on Comp. Vol. c-18, 349\u2013365, (1969).","journal-title":"IEEE Trans. on Comp."},{"key":"10_CR14","doi-asserted-by":"crossref","first-page":"227","DOI":"10.1016\/0304-3975(84)90043-4","volume":"32","author":"K. Culik II","year":"1984","unstructured":"Culik II, K. and S. Yu, Iterative tree automata, TCS, 32 (1984), 227\u2013247.","journal-title":"TCS"},{"key":"10_CR15","unstructured":"Culik II, K., O. Ibarra, and S. Yu, Iterative tree arrays with logarithmic depth, to appear in International Journal of Computer Mathematics; also Department of Computer Science, University of Waterloo, Tech. Rep. CS-85-03, (1985)."},{"key":"10_CR16","doi-asserted-by":"crossref","first-page":"261","DOI":"10.1016\/S0019-9958(80)90164-3","volume":"44","author":"C.R. Dyer","year":"1980","unstructured":"Dyer, C.R., One-way bounded cellular automata, Info. and Control. 44, (1980), 261\u2013281.","journal-title":"Info. and Control."},{"key":"10_CR17","doi-asserted-by":"crossref","first-page":"54","DOI":"10.1016\/S0019-9958(81)90598-2","volume":"48","author":"C.R. Dyer","year":"1981","unstructured":"Dyer, C.R. and A. Rosenfeld, Triangle cellular automata, Info. and Control, 48 (1981), pp. 54\u201369.","journal-title":"Info. and Control"},{"key":"10_CR18","doi-asserted-by":"crossref","first-page":"1073","DOI":"10.1145\/322344.322353","volume":"29-3","author":"L. Goldschlager","year":"1982","unstructured":"Goldschlager, L., A universal interconnection pattern for parallel computers, J. ACM, 29-3 (1982), pp. 1073\u20131086.","journal-title":"J. ACM"},{"key":"10_CR19","unstructured":"Harrison, M.A., Introduction to Formal language Theory, Addision Wesley (1978)."},{"key":"10_CR20","doi-asserted-by":"crossref","unstructured":"Ibarra, O., S. Kim, and M. Palis, Designing systolic algorithms using sequential machines, Proc. 25th IEEE Annual Symp. on Found. of Comput. Sci., 1984, 46\u201355. Full paper to appear in IEEE Trans. Comput.","DOI":"10.1109\/SFCS.1984.715900"},{"key":"10_CR21","doi-asserted-by":"crossref","first-page":"123","DOI":"10.1016\/0304-3975(84)90015-X","volume":"29","author":"O. Ibarra","year":"1984","unstructured":"Ibarra, O. and S. Kim, Characterizations and computational complexity of systolic trellis automata, TCS 29 (1984), 123\u2013153.","journal-title":"TCS"},{"key":"10_CR22","unstructured":"Ibarra, O. and M. Palis, A tool for designing systolic algorithms in linear algebra, submitted to Parallel Computing."},{"key":"10_CR23","unstructured":"Ibarra, O and M. Palis, Two-dimensional systolic arrays: characterizations and applications, submitted to Journal of Parallel and Distributed Computing."},{"key":"10_CR24","doi-asserted-by":"crossref","first-page":"182","DOI":"10.1016\/0743-7315(85)90034-6","volume":"2","author":"O. Ibarra","year":"1985","unstructured":"Ibarra, O., M. Palis, and S. Kim, Some results concerning linear iterative (systolic) arrays, Journal of Parallel and Distributed Computing 2 (1985), 182\u2013218.","journal-title":"Journal of Parallel and Distributed Computing"},{"key":"10_CR25","unstructured":"Ibarra, O. and M. palis, VLSI algorithms for solving recurrence equations and applications, submitted to J. of VLSI and Systems."},{"key":"10_CR26","doi-asserted-by":"crossref","unstructured":"Ibarra, O. and M. Palis, On efficient simulations of systolic arrays by random-access machines, submitted to SIAM J. on Computing.","DOI":"10.1137\/0216027"},{"key":"10_CR27","unstructured":"Kung, H., Let's design algorithms for VLSI systems, Proceedings Caltech Conference on VLSI: Architecture, Design, Fabrication, (1979), 65\u201390."},{"key":"10_CR28","doi-asserted-by":"crossref","first-page":"37","DOI":"10.1109\/MC.1982.1653825","volume":"15","author":"H. Kung","year":"1982","unstructured":"Kung, H., Why systolic architectures?, Computer, Vol. 15, (1982), 37\u201346.","journal-title":"Computer"},{"key":"10_CR29","unstructured":"Kung, H., An algebra for VLSI algorithm design, CMU Tech. Report, (1983)."},{"key":"10_CR30","unstructured":"Kung, H., A listing of systolic papers, Department of Computer Science, Carnegie-Mellon University, May 1984."},{"key":"10_CR31","unstructured":"Leiserson, C., Systolic priority queues, Report CMU-CS-79-115, Dept. of Computer Science, CMU, (1979)."},{"key":"10_CR32","doi-asserted-by":"crossref","unstructured":"Leiserson, C. and J. Saxe, Optimizing synchronous sytems, Proc. 22nd Annual Symp. Foundations of Computer Science, Oct. (1981), 23\u201336.","DOI":"10.1109\/SFCS.1981.34"},{"key":"10_CR33","doi-asserted-by":"crossref","first-page":"66","DOI":"10.1109\/TC.1985.1676516","volume":"C-34","author":"G.-J. Li","year":"1985","unstructured":"Li, G.-J. and B. Wah, The design of optimal systolic arrays, IEEE Trans. Comput., C-34, (1985), 66\u201377.","journal-title":"IEEE Trans. Comput."},{"key":"10_CR34","unstructured":"Lin, T.Z. and C.A. Mead, The application of group theory in classifying systolic arrays, Display File 5006, Caltech, (1982)."},{"key":"10_CR35","doi-asserted-by":"crossref","first-page":"18","DOI":"10.1016\/0022-0000(80)90002-1","volume":"20","author":"W. Masek","year":"1980","unstructured":"Masek, W. and M. Paterson, A faster algorithm for computing string-edit distances, Journal of Computer and System Sciences, 20 (1980), pp. 18\u201331.","journal-title":"Journal of Computer and System Sciences"},{"key":"10_CR36","doi-asserted-by":"crossref","unstructured":"Miranker, W.L., Space time representations of computational structures, Computing, (1984), 93\u2013114.","DOI":"10.1007\/BF02253685"},{"key":"10_CR37","doi-asserted-by":"crossref","unstructured":"Moldovan, D., On the design of algorithms for VLSI systolic arrays, Proc. IEEE, (1983).","DOI":"10.1109\/PROC.1983.12532"},{"key":"10_CR38","doi-asserted-by":"crossref","first-page":"892","DOI":"10.1109\/TC.1982.1676104","volume":"C-32","author":"T. Ottman","year":"1982","unstructured":"Ottman, T., Rosenberg, A.L. and Stockmeyer, L.J., Dictionary machine for VLSI, IEEE Trans. Computers, Vol. C-32, 892\u2013897, 1982. MST 10 (1977), 239\u2013251.","journal-title":"IEEE Trans. Computers"},{"key":"10_CR39","doi-asserted-by":"crossref","unstructured":"Quinton, P., Automatic synthesis of systolic arrays from uniform recurrent equations, Proc. of 11th Annual Symp. on Computer Architecture, (1984), 208\u2013214.","DOI":"10.1145\/800015.808184"},{"key":"10_CR40","first-page":"365","volume":"22","author":"W. Ruzzo","year":"1981","unstructured":"Ruzzo, W., On uniform circuit complexity, JCSS 22 (1981), 365\u2013383.","journal-title":"JCSS"},{"key":"10_CR41","doi-asserted-by":"crossref","first-page":"177","DOI":"10.1007\/BF00289248","volume":"8","author":"J. Seiferas","year":"1977","unstructured":"Seiferas, J., Iterative arrays with direct central control, Acta Inform., 8 (1977), 177\u2013192.","journal-title":"Acta Inform."},{"key":"10_CR42","first-page":"233","volume":"6","author":"A.R. Smith III","year":"1972","unstructured":"Smith III, A.R., Real-time language recognition by one-dimensional cellular automata, JCSS 6 (1972), 233\u2013253.","journal-title":"JCSS"},{"issue":"9","key":"10_CR43","doi-asserted-by":"crossref","first-page":"841","DOI":"10.1109\/TC.1985.1676640","volume":"C-34","author":"A. Somani","year":"1985","unstructured":"Somani, A. and Agarwal, V., An Efficient unsorted VLSI dictionary machine, IEEE Trans. Comput. C-34, 9 (1985), 841\u2013852.","journal-title":"IEEE Trans. Comput."},{"key":"10_CR44","doi-asserted-by":"crossref","first-page":"409","DOI":"10.1137\/0213027","volume":"13-2","author":"L. Stockmeyer","year":"1984","unstructured":"Stockmeyer, L. and U. Vishkin, Simulation of parallel random-access machines by circuits, SIAM J. Computing, 13-2 (1984), 409\u2013422.","journal-title":"SIAM J. Computing"},{"key":"10_CR45","doi-asserted-by":"crossref","first-page":"158","DOI":"10.1016\/0020-0190(82)90028-X","volume":"14","author":"H. Umeo","year":"1982","unstructured":"Umeo, H., Morita, K., and Sugata, K., Deterministic one-way si, Deterministic one-way simulation of two-way real-time cellular automata and its related problems, IPL 14 (1982), 158\u2013161.","journal-title":"IPL"},{"key":"10_CR46","doi-asserted-by":"crossref","first-page":"168","DOI":"10.1145\/321796.321811","volume":"21","author":"R. Wagner","year":"1974","unstructured":"Wagner, R. and M. Fischer, The string-to-string correction problem, Journal of the Association for Computing Machinery, 21 (1974), pp. 168\u2013173.","journal-title":"Journal of the Association for Computing Machinery"},{"key":"10_CR47","doi-asserted-by":"crossref","unstructured":"Weiser, U. and A. Davis, A wavefront notation tool for VLSI array design, VLSI Systems and Computations, Computer Science Press, 1981.","DOI":"10.1007\/978-3-642-68402-9_25"}],"container-title":["Lecture Notes in Computer Science","Mathematical Foundations of Computer Science 1986"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BFb0016239.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,12,9]],"date-time":"2020-12-09T21:35:32Z","timestamp":1607549732000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BFb0016239"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["3540167838"],"references-count":47,"URL":"https:\/\/doi.org\/10.1007\/bfb0016239","relation":{},"subject":[]}}