{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T22:58:56Z","timestamp":1725663536676},"publisher-location":"Berlin, Heidelberg","reference-count":21,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540180883"},{"type":"electronic","value":"9783540477471"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1987]]},"DOI":"10.1007\/3-540-18088-5_48","type":"book-chapter","created":{"date-parts":[[2012,2,25]],"date-time":"2012-02-25T14:27:49Z","timestamp":1330180069000},"page":"550-562","source":"Crossref","is-referenced-by-count":3,"title":["On the computing power of one-way cellular arrays"],"prefix":"10.1007","author":[{"given":"Oscar H.","family":"Ibarra","sequence":"first","affiliation":[]},{"given":"Tao","family":"Jiang","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,5,29]]},"reference":[{"key":"48_CR1","doi-asserted-by":"crossref","first-page":"114","DOI":"10.1145\/322234.322243","volume":"28-1","author":"A. Chandra","year":"1981","unstructured":"Chandra, A., D. Kozen and L. Stockmeyer, Alternation, J. ACM 28-1, 1981, pp. 114\u2013133.","journal-title":"J. ACM"},{"key":"48_CR2","doi-asserted-by":"crossref","first-page":"708","DOI":"10.1137\/0212048","volume":"12-4","author":"T. Chan","year":"1983","unstructured":"Chan, T. and O. Ibarra, On the space and time complexity of functions computable by simple programs, SICOMP 12-4, 1983, pp. 708\u2013716.","journal-title":"SICOMP"},{"key":"48_CR3","unstructured":"Chang, J., O. Ibarra and M. Palis, Efficient simulations of simple models of parallel computation by space-bounded TMs and time-bounded alternating TMs, Revision of Tech. Rep. 85-47, Department of Computer Science, University of Minnesota, Nov. 1985; submitted to Theoretical Computer Science."},{"key":"48_CR4","doi-asserted-by":"crossref","unstructured":"Chang, J., O. Ibarra and A. Vergis, On the power of one-way communication, Proceedings of the 27th IEEE Annual Symposium on Foundations of Computer Science, 1986, pp. 455\u2013464.","DOI":"10.1109\/SFCS.1986.37"},{"key":"48_CR5","doi-asserted-by":"publisher","first-page":"393","DOI":"10.1007\/BF00264617","volume":"21","author":"C. Choffrut","year":"1984","unstructured":"Choffrut, C. and K. Culik II, On real-time cellular automata and trellis automata, Acta Inform. 21, 1984, pp. 393\u2013409.","journal-title":"Acta Inform."},{"key":"48_CR6","doi-asserted-by":"publisher","first-page":"4","DOI":"10.1145\/321623.321625","volume":"18-1","author":"S. Cook","year":"1971","unstructured":"Cook, S., Characterizations of pushdown machines in terms of time-bounded computers, J. ACM 18-1, 1971, pp. 4\u201318.","journal-title":"J. ACM"},{"key":"48_CR7","doi-asserted-by":"crossref","first-page":"195","DOI":"10.1080\/00207168408803410","volume":"15","author":"K. Culik II","year":"1984","unstructured":"Culik II, K., J. Gruska and A. Salomaa, Systolic trellis aotumata; Part I, Internat. J. Comput. Math. 15, 1984, pp. 195\u2013212.","journal-title":"Internat. J. Comput. Math."},{"key":"48_CR8","doi-asserted-by":"publisher","first-page":"54","DOI":"10.1016\/S0019-9958(80)90164-3","volume":"44","author":"C. Dyer","year":"1980","unstructured":"Dyer, C., One-way bounded cellular automata, Information and Control 44, 1980, pp. 54\u201369.","journal-title":"Information and Control"},{"key":"48_CR9","doi-asserted-by":"crossref","unstructured":"Gurari, E. and O. Ibarra, The complexity of the equivalence problem for two characterizations of Presburger sets, Theoretical Computer Science 13, pp. 295\u2013314.","DOI":"10.1016\/S0304-3975(81)80003-5"},{"key":"48_CR10","doi-asserted-by":"publisher","first-page":"433","DOI":"10.1016\/S0019-9958(68)90901-7","volume":"13","author":"M. Harrison","year":"1968","unstructured":"Harrison, M. and O. Ibarra, Multitape and Multihead pushdown automata, Information and Control 13, 1968, pp. 433\u2013470.","journal-title":"Information and Control"},{"key":"48_CR11","unstructured":"Harrison, M., Introduction to formal language theory, Addison-Wesley, 1978."},{"key":"48_CR12","doi-asserted-by":"crossref","DOI":"10.7551\/mitpress\/3999.001.0001","volume-title":"Iterative arrays of logical circuits","author":"F. Hennie","year":"1961","unstructured":"Hennie, F., Iterative arrays of logical circuits, MIT Press, Cambridge, Mass., 1961."},{"key":"48_CR13","unstructured":"Hopcroft, J. and J. Ullman, Introduction to automata theory, languages, and computation, Addison-Wesley, 1979."},{"key":"48_CR14","doi-asserted-by":"publisher","first-page":"25","DOI":"10.1016\/0020-0190(74)90043-X","volume":"3","author":"O. Ibarra","year":"1974","unstructured":"Ibarra, O., A note on semilinear sets and bounded-reversal multihead pushdown automata, Inform. Process. lett. 3, 1974, pp. 25\u201328.","journal-title":"Inform. Process. lett."},{"key":"48_CR15","unstructured":"Ibarra O., and M. Palis, Two-dimensional systolic arrays: characterizations and applications, Tech. Rep. 85-1, Department of Computer Science, University of Minnesota, Jan. 1985; to appear in Theoretical Computer Science."},{"key":"48_CR16","doi-asserted-by":"publisher","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, J. of Parallel and Distributed Computing 2, 1985, pp. 182\u2013218.","journal-title":"J. of Parallel and Distributed Computing"},{"key":"48_CR17","first-page":"31","volume":"C35-6","author":"O. Ibarra","year":"1986","unstructured":"Ibarra, O., S. Kim and M. Palis, Designing Systolic Algorithms using sequential machines, IEEE Trans. on Computers C35-6, June 1986, pp. 31\u201342; extended abstract in Proc. 25th IEEE Symposium on Foundations of Computer Science, 1984, pp. 46\u201355.","journal-title":"IEEE Trans. on Computers"},{"key":"48_CR18","unstructured":"Seidel, S., Language recognition and the synchronization of cellular automata, Tech. Rep. 79-02, Department of Computer Science, University of Iowa, 1979."},{"key":"48_CR19","doi-asserted-by":"crossref","unstructured":"Smith, A., III, Cellular automata and formal languages, Proc. 11th IEEE Ann. Symp. on Switching and Automata Theory, 1970, pp. 216\u2013224.","DOI":"10.1109\/SWAT.1970.4"},{"key":"48_CR20","doi-asserted-by":"publisher","first-page":"466","DOI":"10.1016\/S0019-9958(71)90501-8","volume":"18","author":"A. Smith III","year":"1971","unstructured":"Smith, A., III, Cellular automata complexity trade-offs, Information and Control 18, 1971, pp. 466\u2013482.","journal-title":"Information and Control"},{"key":"48_CR21","doi-asserted-by":"publisher","first-page":"159","DOI":"10.1016\/0020-0190(82)90028-X","volume":"14","author":"H. Umeo","year":"1982","unstructured":"Umeo, H., K. Morita, and K. Sugata, Deterministic one-way simulation of two-way real-time cellular automata and its related problems, Inform. Process. Lett. 14, 1982, pp. 159\u2013161.","journal-title":"Inform. Process. Lett."}],"container-title":["Lecture Notes in Computer Science","Automata, Languages and Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-18088-5_48.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T15:14:11Z","timestamp":1605626051000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-18088-5_48"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1987]]},"ISBN":["9783540180883","9783540477471"],"references-count":21,"URL":"https:\/\/doi.org\/10.1007\/3-540-18088-5_48","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1987]]}}}