{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,5]],"date-time":"2026-10-05T20:06:38Z","timestamp":1791230798974,"version":"4.1.0"},"reference-count":24,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"2","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[1985,5]]},"abstract":"<jats:p>We look at a simple, but general model, of a systolic system called a trellis automaton (TA). A TA is equivalent in computational power to a one-dimensional unbounded cellular automaton (CA), a model of parallel computation which has been studied extensively in the literature. Different varieties of TA\u2019s are equivalent to corresponding variations of CA\u2019s. We present, for the first time, sequential machine characterizations of TA\u2019s (CA\u2019s). The sequential machines are useful and powerful tools for investigating properties of TA\u2019s (CA\u2019s). They ar easy to program because, unlike the parallel models, one does not have to deal with the problem of synchronization. Several applications are given. In particular, we prove a new speed-up theorem which is stronger than what has previously been shown.<\/jats:p>","DOI":"10.1137\/0214033","type":"journal-article","created":{"date-parts":[[2005,2,24]],"date-time":"2005-02-24T06:25:35Z","timestamp":1109226335000},"page":"426-447","source":"Crossref","is-referenced-by-count":48,"title":["Sequential Machine Characterizations of Trellis and Cellular Automata and Applications"],"prefix":"10.1137","volume":"14","author":[{"given":"Oscar H.","family":"Ibarra","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Sam M.","family":"Kim","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Shlomo","family":"Moran","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2006,7,13]]},"reference":[{"key":"R1","doi-asserted-by":"publisher","DOI":"10.1051\/ita\/1984180403071"},{"key":"R2","doi-asserted-by":"publisher","DOI":"10.1109\/T-C.1969.222663"},{"key":"R3","volume-title":"Introduction to VLSI Systems","author":"Conway L.","year":"1980"},{"key":"R4","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(73)80028-5"},{"key":"R5","doi-asserted-by":"crossref","unstructured":"K. Culik, II, J. Pachl,  Folding and unrolling systolic arrays,  ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing, Ottawa,  1982, August","DOI":"10.1145\/800220.806704"},{"key":"R6","unstructured":"K. Culik, II, J. Gruska, A. Salomaa,  Systolic trellis automata (for VLSI), Res. Rep., CS-81-34, Dept. Computer Science, Univ. Waterloo, Waterloo, Ontario, Canada,  1981"},{"key":"R7","unstructured":"K. Culik, II, J. Gruska, A. Salomaa,  Systolic trellis automata: stability, decidability and complexity, Res. Rep., CS-82-04, Dept. Computer Science, Univ. Waterloo, Waterloo, Ontario, Canada,  1982"},{"key":"R8","unstructured":"C. Choffrut, K. Culik, II,  On real-time cellular automata and trellis automata, Bericht, F114, Institute fur Informationsverarbeitung, Universitat Graz,  1983"},{"key":"R9","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(80)90164-3"},{"key":"R10","doi-asserted-by":"publisher","DOI":"10.7551\/mitpress\/3999.001.0001"},{"key":"R11","doi-asserted-by":"publisher","DOI":"10.1145\/321724.321727"},{"key":"R12","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(73)80048-0"},{"key":"R13","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(84)90015-X"},{"key":"R14","unstructured":"O. Ibarra, S. Kim, M. Palis,  Some results concerning linear iterative arrays, in preparation"},{"key":"R15","doi-asserted-by":"publisher","DOI":"10.1109\/T-C.1974.223995"},{"key":"R16","unstructured":"H. Kung,  Ch. L. Seitz,  Let's design algorithms for VLSI systems,  Proc. Caltech Conference on Very Large Scale Integration, Pasadena, CA,  1979,  65\u201369"},{"key":"R17","unstructured":"H. Kung,  The structure of parallel algorithms, Res. Rep., Department of Computer Science, Carnegie-Mellon University,  1979"},{"key":"R18","unstructured":"H. Kung, C. Leiserson,  I. S. Duff, G. W. Stewart,  Systolic arrays (for VLSI),  Sparse Matrix Proceedings 1978 (Sympos. Sparse Matrix Comput., Knoxville, Tenn., 1978), SIAM, Philadelphia, Pa.,  1979,  256\u2013282 81h:680040404.68037"},{"key":"R19","doi-asserted-by":"crossref","unstructured":"C. Leiserson, J. Saxe,  Optimizing synchronous systems,  Proc. 22nd Annual Symposium on Foundations of Computer Science, Nashville, Tennessee,  1981,  23\u201326","DOI":"10.1109\/SFCS.1981.34"},{"key":"R20","doi-asserted-by":"crossref","unstructured":"W. Paul,  On time hierarchies,  Conference Record of the Ninth Annual ACM Symposium on Theory of Computing (Boulder, Colo., 1977), Assoc. Comput. Mach., New York,  1977,  218\u2013222 57:18225","DOI":"10.1145\/800105.803411"},{"key":"R21","doi-asserted-by":"crossref","unstructured":"S. Ruby, P. Fischer,  Translational method and computational complexity,  Proc. Sixth Annual IEEE Symp. on Switching Circuit Theory and Logical Design,  1965,  173\u2013178","DOI":"10.1109\/FOCS.1965.33"},{"key":"R22","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(72)80004-7"},{"key":"R23","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(82)90028-X"},{"key":"R24","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(66)90110-0"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/0214033","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:42:57Z","timestamp":1787337777000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/0214033"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1985,5]]},"references-count":24,"journal-issue":{"issue":"2","published-print":{"date-parts":[[1985,5]]}},"alternative-id":["10.1137\/0214033"],"URL":"https:\/\/doi.org\/10.1137\/0214033","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[1985,5]]}}}