{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,1]],"date-time":"2026-04-01T18:37:36Z","timestamp":1775068656993,"version":"3.50.1"},"reference-count":116,"publisher":"Elsevier BV","issue":"1-3","license":[{"start":{"date-parts":[[1991,6,1]],"date-time":"1991-06-01T00:00:00Z","timestamp":675734400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Information Sciences"],"published-print":{"date-parts":[[1991,6]]},"DOI":"10.1016\/0020-0255(91)90008-i","type":"journal-article","created":{"date-parts":[[2003,6,30]],"date-time":"2003-06-30T17:28:37Z","timestamp":1056994117000},"page":"99-121","source":"Crossref","is-referenced-by-count":52,"title":["A survey of two-dimensional automata theory"],"prefix":"10.1016","volume":"55","author":[{"given":"Katsushi","family":"Inoue","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Itsuo","family":"Takanami","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"78","reference":[{"issue":"3","key":"10.1016\/0020-0255(91)90008-I_BIB1","first-page":"123","article-title":"On universal traps","volume":"15","author":"Antelmann","year":"1979","journal-title":"EIK"},{"key":"10.1016\/0020-0255(91)90008-I_BIB2","article-title":"Recognition of topological invariants by iterative arrays","author":"Beyer","year":"1970"},{"key":"10.1016\/0020-0255(91)90008-I_BIB3","series-title":"IEEE Symp. Switching Automata Theory","first-page":"155","article-title":"Automata on a two-dimensional tape","author":"Blum","year":"1967"},{"key":"10.1016\/0020-0255(91)90008-I_BIB4","series-title":"Proceedings of the 19th Annual Symposium on Foundations of Computer Science","article-title":"On the power of the compass","author":"Blum","year":"1978"},{"key":"10.1016\/0020-0255(91)90008-I_BIB5","series-title":"Proceedings of the 18th Annual Symposium on Foundations of Computer Science","first-page":"147","article-title":"On the capability of finite automata in 2 and 3 dimensional space","author":"Blum","year":"1977"},{"key":"10.1016\/0020-0255(91)90008-I_BIB6","article-title":"On real time and linear time cellular automata","author":"Bucher","year":"1983"},{"key":"10.1016\/0020-0255(91)90008-I_BIB7","article-title":"Environments, Labyrinths and Automata","volume":"56","author":"Budach","year":"1977"},{"key":"10.1016\/0020-0255(91)90008-I_BIB8","doi-asserted-by":"crossref","first-page":"195","DOI":"10.1002\/mana.19780860120","article-title":"Automata and labyrinths","volume":"86","author":"Budach","year":"1978","journal-title":"Math. Nachr."},{"issue":"1\/2","key":"10.1016\/0020-0255(91)90008-I_BIB9","first-page":"13","article-title":"Environments and automata I","volume":"18","author":"Budach","year":"1982","journal-title":"EIK"},{"issue":"3","key":"10.1016\/0020-0255(91)90008-I_BIB10","first-page":"115","article-title":"Environments and automata II","volume":"18","author":"Budach","year":"1982","journal-title":"EIK"},{"issue":"1","key":"10.1016\/0020-0255(91)90008-I_BIB11","doi-asserted-by":"crossref","first-page":"114","DOI":"10.1145\/322234.322243","article-title":"Alternation","volume":"28","author":"Chandra","year":"1981","journal-title":"J. Assoc. Comput. Mach."},{"key":"10.1016\/0020-0255(91)90008-I_BIB12","article-title":"On real-time cellular automata and trellis automata","author":"Choffrut","year":"1983"},{"key":"10.1016\/0020-0255(91)90008-I_BIB13","first-page":"111","article-title":"Recognition of topological equivalence of patterns by array automata","volume":"2","author":"Dietz","year":"1980","journal-title":"JCSS"},{"key":"10.1016\/0020-0255(91)90008-I_BIB14","doi-asserted-by":"crossref","first-page":"261","DOI":"10.1016\/S0019-9958(80)90164-3","article-title":"One-way bounded cellular automata","volume":"44","author":"Dyer","year":"1980","journal-title":"Inform. Control"},{"key":"10.1016\/0020-0255(91)90008-I_BIB15","doi-asserted-by":"crossref","first-page":"25","DOI":"10.1016\/0020-0255(81)90038-4","article-title":"Relation of one-way parallel\/sequential automata to 2-d finite automata","volume":"23","author":"Dyer","year":"1981","journal-title":"Inform. Sci."},{"key":"10.1016\/0020-0255(91)90008-I_BIB16","article-title":"Cellular pyramids for image analysis","author":"Dyer","year":"1977"},{"issue":"1","key":"10.1016\/0020-0255(91)90008-I_BIB17","doi-asserted-by":"crossref","first-page":"29","DOI":"10.1109\/TPAMI.1981.4767048","article-title":"Parallel image processing by memory-augmented cellular automata","volume":"PAMI-3","author":"Dyer","year":"1981","journal-title":"IEEE Trans. Pattern Anal. Mach. Intell."},{"key":"10.1016\/0020-0255(91)90008-I_BIB18","doi-asserted-by":"crossref","first-page":"54","DOI":"10.1016\/S0019-9958(81)90598-2","article-title":"Triangle cellular automata","volume":"48","author":"Dyer","year":"1981","journal-title":"Inform. Control"},{"key":"10.1016\/0020-0255(91)90008-I_BIB19","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/0020-0255(87)90013-2","article-title":"A hierarchy of random context grammars and automata","volume":"42","author":"Ehlers","year":"1987","journal-title":"Inform. Sci."},{"key":"10.1016\/0020-0255(91)90008-I_BIB20","series-title":"IEEE Symp. Switching Automata Theory","first-page":"149","article-title":"Two characterizations of the context sensitive languages","author":"Fisher","year":"1969"},{"key":"10.1016\/0020-0255(91)90008-I_BIB21","first-page":"26","article-title":"The structural complexity column","volume":"33","author":"Hartmanis","year":"1987","journal-title":"Bull. EATCS"},{"issue":"8\/9","key":"10.1016\/0020-0255(91)90008-I_BIB22","first-page":"453","article-title":"Normed two-plane traps for finite systems of cooperating compass automata","volume":"23","author":"Hemmerling","year":"1987","journal-title":"EIK"},{"key":"10.1016\/0020-0255(91)90008-I_BIB23","series-title":"Fundamentals of Computation Theory","first-page":"433","article-title":"One pebble does not suffice to search plane labyrinths","volume":"117","author":"Hoffmann","year":"1981"},{"issue":"2","key":"10.1016\/0020-0255(91)90008-I_BIB24","first-page":"283","article-title":"Some results on tape-bounded Turing macnhines","volume":"19","author":"Hopcroft","year":"1972","journal-title":"J. Assoc. Comput. Math."},{"key":"10.1016\/0020-0255(91)90008-I_BIB25","series-title":"Introduction to Automata Theory, Languages, and Computation","author":"Hopcroft","year":"1979"},{"issue":"3","key":"10.1016\/0020-0255(91)90008-I_BIB26","first-page":"431","article-title":"Lower bounds for language recognition on two-dimensional alternating multihead machines","volume":"38","author":"Hromkovic","year":"1989","journal-title":"JCSS"},{"key":"10.1016\/0020-0255(91)90008-I_BIB27","doi-asserted-by":"crossref","first-page":"269","DOI":"10.1080\/00207167408803092","article-title":"Some results concerning automata on two-dimensional tapes","volume":"4-A","author":"Ibarra","year":"1974","journal-title":"Int. J. Comput. Math."},{"key":"10.1016\/0020-0255(91)90008-I_BIB28","doi-asserted-by":"crossref","first-page":"935","DOI":"10.1137\/0217058","article-title":"Nondeterministic space is closed under complement","volume":"17","author":"Immerman","year":"1988","journal-title":"SIAM J. on Comput."},{"key":"10.1016\/0020-0255(91)90008-I_BIB29","article-title":"Investigations of two-dimensional on-line tessellation acceptors(Japanese)","author":"Inoue","year":"1977"},{"key":"10.1016\/0020-0255(91)90008-I_BIB30","first-page":"167","article-title":"Some notes on parallel sequential array acceptors","author":"Inoue","year":"1975","journal-title":"IECE Jpn. Trans. (D)"},{"key":"10.1016\/0020-0255(91)90008-I_BIB31","first-page":"613","article-title":"On the relation between two-dimensional on-line tessellation acceptors and one-dimensional bounded cellular acceptors","author":"Inoue","year":"1976","journal-title":"IECE Jpn. Trans. (D)"},{"key":"10.1016\/0020-0255(91)90008-I_BIB32","first-page":"682","article-title":"Some properties of one-way parallel sequential array acceptors and two-dimensional one-marker automata","author":"Inoue","year":"1976","journal-title":"IECE Jpn. Trans. (D)"},{"key":"10.1016\/0020-0255(91)90008-I_BIB33","first-page":"680","article-title":"Some properties of parallel sequential array acceptors and two-dimensional two-marker automata","author":"Inoue","year":"1976","journal-title":"IECE Jpn. Trans. (D)"},{"key":"10.1016\/0020-0255(91)90008-I_BIB34","first-page":"695","article-title":"Some properties of two-dimensional on-line tessellation acceptors","author":"Inoue","year":"1976","journal-title":"IECE Jpn. Trans. (D)"},{"key":"10.1016\/0020-0255(91)90008-I_BIB35","doi-asserted-by":"crossref","first-page":"95","DOI":"10.1016\/0020-0255(77)90023-8","article-title":"Some properties of two-dimensional on-line tessellation acceptors","volume":"13","author":"Inoue","year":"1977","journal-title":"Inform. Sci."},{"key":"10.1016\/0020-0255(91)90008-I_BIB36","first-page":"679","article-title":"Some properties of two-dimensional automata with a one-letter alphabet\u2014recognizability of functions by two-dimensional automata","author":"Inoue","year":"1977","journal-title":"IECE Jpn. Trans. (D)"},{"key":"10.1016\/0020-0255(91)90008-I_BIB37","first-page":"475","article-title":"Nonclosure properties of two-dimensional on-line tessellation acceptors and one-way parallel sequential array acceptors","author":"Inoue","year":"1977","journal-title":"IECE Jpn. Trans. (E)"},{"key":"10.1016\/0020-0255(91)90008-I_BIB38","first-page":"990","article-title":"Some properties on two-dimensional nondeterministic finite automata and parallel sequential array acceptors","author":"Inoue","year":"1977","journal-title":"IECE Jpn. Trans. (D)"},{"issue":"3","key":"10.1016\/0020-0255(91)90008-I_BIB39","doi-asserted-by":"crossref","first-page":"305","DOI":"10.1016\/S0019-9958(79)90604-1","article-title":"Two-dimensional multipass on-line tessellation acceptors","volume":"41","author":"Inoue","year":"1979","journal-title":"Inform. Control"},{"key":"10.1016\/0020-0255(91)90008-I_BIB40","doi-asserted-by":"crossref","first-page":"207","DOI":"10.1080\/00207167908803172","article-title":"Two-dimensional finite automata and unacceptable functions","volume":"A7","author":"Inoue","year":"1979","journal-title":"Int. J. Comput. Math. Sec."},{"issue":"1","key":"10.1016\/0020-0255(91)90008-I_BIB41","doi-asserted-by":"crossref","first-page":"143","DOI":"10.1016\/0020-0255(78)90004-X","article-title":"A note on closure properties of the classes of sets accepted by tape-bounded two-dimensional Turing machines","volume":"15","author":"Inoue","year":"1978","journal-title":"Inform. Sci."},{"issue":"1","key":"10.1016\/0020-0255(91)90008-I_BIB42","doi-asserted-by":"crossref","first-page":"229","DOI":"10.1016\/0020-0255(78)90049-X","article-title":"Cyclic closure properties of automata on a two-dimensional tape","volume":"15","author":"Inoue","year":"1978","journal-title":"Inform. Sci."},{"issue":"1","key":"10.1016\/0020-0255(91)90008-I_BIB43","doi-asserted-by":"crossref","first-page":"34","DOI":"10.1016\/0020-0190(79)90089-9","article-title":"A note on bottom-up pyramid acceptors","volume":"8","author":"Inoue","year":"1979","journal-title":"Inform. Process. Lett."},{"issue":"3","key":"10.1016\/0020-0255(91)90008-I_BIB44","doi-asserted-by":"crossref","first-page":"195","DOI":"10.1016\/0020-0255(79)90017-3","article-title":"Three-way tape-bounded two-dimensional Turing machines","volume":"17","author":"Inoue","year":"1979","journal-title":"Inform. Sci."},{"issue":"3","key":"10.1016\/0020-0255(91)90008-I_BIB45","doi-asserted-by":"crossref","first-page":"247","DOI":"10.1016\/0020-0255(79)90048-3","article-title":"Closure properties of three-way and four-way tape-bounded two-dimensional Turing machines","volume":"18","author":"Inoue","year":"1979","journal-title":"Inform. Sci."},{"issue":"1","key":"10.1016\/0020-0255(91)90008-I_BIB46","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/0020-0255(79)90029-X","article-title":"Three-way two-dimensional multicounter automata","volume":"19","author":"Inoue","year":"1979","journal-title":"Inform. Sci."},{"key":"10.1016\/0020-0255(91)90008-I_BIB47","first-page":"673","article-title":"Some properties of three-way two-dimensional multicounter automata over square tapes","author":"Inoue","year":"1979","journal-title":"IECE Jpn. Trans. (D)"},{"issue":"1","key":"10.1016\/0020-0255(91)90008-I_BIB48","doi-asserted-by":"crossref","first-page":"41","DOI":"10.1016\/0020-0255(80)90023-7","article-title":"A note on deterministic three-way tape-bounded two-dimensional Turing machines","volume":"20","author":"Inoue","year":"1980","journal-title":"Inform. Sci."},{"issue":"5","key":"10.1016\/0020-0255(91)90008-I_BIB49","doi-asserted-by":"crossref","first-page":"245","DOI":"10.1016\/0020-0190(80)90151-9","article-title":"A note on decision problems for three-way two-dimensional finite automata","volume":"10","author":"Inoue","year":"1980","journal-title":"Inform. Process. Lett."},{"key":"10.1016\/0020-0255(91)90008-I_BIB50","series-title":"Discrete Algorithms and Complexity","first-page":"389","article-title":"A leaf-size hierarchy of two-dimensional alternating Turing machines","author":"Inoue","year":"1987"},{"issue":"1","key":"10.1016\/0020-0255(91)90008-I_BIB51","doi-asserted-by":"crossref","first-page":"49","DOI":"10.1016\/0020-0190(78)90040-6","article-title":"A note on two-dimensional finite automata","volume":"7","author":"Inoue","year":"1978","journal-title":"Inform. Process. Lett."},{"issue":"1","key":"10.1016\/0020-0255(91)90008-I_BIB52","doi-asserted-by":"crossref","first-page":"45","DOI":"10.1016\/S0020-0255(80)80023-5","article-title":"Nonclosure property of nondeterministic two-dimensional finite automata under cyclic closure","volume":"22","author":"Inoue","year":"1980","journal-title":"Inform. Sci."},{"key":"10.1016\/0020-0255(91)90008-I_BIB53","doi-asserted-by":"crossref","first-page":"126","DOI":"10.1016\/0734-189X(84)90134-8","article-title":"Connected pictures are not recognizable by deterministic two-dimensional on-line tessellation acceptors","volume":"26","author":"Inoue","year":"1984","journal-title":"Comput. Vision Graphics Image Process."},{"key":"10.1016\/0020-0255(91)90008-I_BIB54","doi-asserted-by":"crossref","unstructured":"K. Inoue, I. Takanami, and A. Nakamura, A note on time-bounded bottom-up pyramid cellular acceptors, Inform. Sci., forthcoming.","DOI":"10.1016\/0020-0255(90)90021-2"},{"key":"10.1016\/0020-0255(91)90008-I_BIB55","first-page":"65","article-title":"Three-way two-dimensional simple multihead finite automata\u2014hierarchical properties","author":"Inoue","year":"1979","journal-title":"IECE Jpn. Trans. (D)"},{"key":"10.1016\/0020-0255(91)90008-I_BIB56","first-page":"273","article-title":"Three-way two-dimensional simple multihead finite automata\u2014closure properties","author":"Inoue","year":"1979","journal-title":"IECE Jpn. Trans. (D)"},{"key":"10.1016\/0020-0255(91)90008-I_BIB57","first-page":"113","article-title":"The accepting powers of two-dimensional automata over square tapes","author":"Inoue","year":"1980","journal-title":"IECE Jpn. Trans. (D)"},{"key":"10.1016\/0020-0255(91)90008-I_BIB58","doi-asserted-by":"crossref","first-page":"61","DOI":"10.1016\/0304-3975(83)90093-2","article-title":"Two-dimensional alternating Turing machines","volume":"27","author":"Inoue","year":"1983","journal-title":"Theoret. Comput. Sci."},{"issue":"1\u20133","key":"10.1016\/0020-0255(91)90008-I_BIB59","doi-asserted-by":"crossref","first-page":"193","DOI":"10.1016\/S0019-9958(82)90572-1","article-title":"Two-dimensional alternating Turing machines with only universal states","volume":"55","author":"Ito","year":"1982","journal-title":"Inform. Control"},{"key":"10.1016\/0020-0255(91)90008-I_BIB60","first-page":"508","article-title":"A note on space complexity of nondeterministic two-dimensional Turing machines","author":"Ito","year":"1983","journal-title":"IECE Jpn. Trans. (E)"},{"key":"10.1016\/0020-0255(91)90008-I_BIB61","first-page":"1553","article-title":"Hierarchy of the accepting power of cellular space based on the number of state changes","author":"Ito","year":"1985","journal-title":"IECE Jpn. Trans. (D)"},{"key":"10.1016\/0020-0255(91)90008-I_BIB62","first-page":"1562","article-title":"Relationships of the accepting powers between cellular space with bounded number of state-changes and other automata","author":"Ito","year":"1985","journal-title":"IECE Jpn. Trans. (D)"},{"key":"10.1016\/0020-0255(91)90008-I_BIB63","first-page":"2339","article-title":"State-change bounded rectangular array cellular space acceptors with three-neighbor","author":"Ito","year":"1987","journal-title":"IEICE Jpn. Trans. (D)"},{"issue":"1","key":"10.1016\/0020-0255(91)90008-I_BIB64","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/0020-0255(88)90005-9","article-title":"A note on three-way two-dimensional alternating Turing machines","volume":"45","author":"Ito","year":"1988","journal-title":"Inform. Sci."},{"key":"10.1016\/0020-0255(91)90008-I_BIB65","doi-asserted-by":"crossref","first-page":"273","DOI":"10.1016\/0304-3975(89)90154-0","article-title":"Deterministic on-line tessellation acceptors are equivalent to two-way two-dimensional alternating finite automata through 180\u00b0 rotations","volume":"66","author":"Ito","year":"1989","journal-title":"Theoret. Comput. Sci."},{"key":"10.1016\/0020-0255(91)90008-I_BIB66","series-title":"A relationship between one-dimensional bounded cellular acceptors and two-dimensional alternating finite automata, manuscript","author":"Ito","year":"1987"},{"key":"10.1016\/0020-0255(91)90008-I_BIB67","series-title":"Fifth International Meeting of Young Computer Scientists","article-title":"The simulation of two-dimensional one-marker automata by three-way two-dimensional Turing machines","author":"Ito","year":"1988"},{"issue":"4","key":"10.1016\/0020-0255(91)90008-I_BIB68","first-page":"348","article-title":"Some closure properties of the class of sets accepted by three-way two-dimensional alternating finite automata","volume":"E72","author":"Ito","year":"1989","journal-title":"IEICE Jpn. Trans."},{"key":"10.1016\/0020-0255(91)90008-I_BIB69","article-title":"ASPACE(o(log log n)) is regular","author":"Iwama","year":"1986"},{"key":"10.1016\/0020-0255(91)90008-I_BIB70","doi-asserted-by":"crossref","first-page":"61","DOI":"10.1016\/0020-0255(85)90041-6","article-title":"Three-way automata on rectangular tapes over a one-letter alphabet","volume":"35","author":"Kinber","year":"1985","journal-title":"Inform. Sci."},{"issue":"6","key":"10.1016\/0020-0255(91)90008-I_BIB71","doi-asserted-by":"crossref","first-page":"561","DOI":"10.1109\/T-C.1974.223995","article-title":"On some open problems in the theory of cellular automata","volume":"C-23","author":"Kosaraju","year":"1974","journal-title":"IEEE Trans. Comput."},{"key":"10.1016\/0020-0255(91)90008-I_BIB72","series-title":"Proceedings of the 11th Annual ACM Symposium On Theory of Computing","first-page":"231","article-title":"Fast parallel processing array algorithms for some graph problems","author":"Kosaraju","year":"1979"},{"key":"10.1016\/0020-0255(91)90008-I_BIB73","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1080\/00207167408803078","article-title":"Array automata and operations on array languages","volume":"4-A","author":"Krithivasan","year":"1974","journal-title":"Int. J. Compu. Math."},{"key":"10.1016\/0020-0255(91)90008-I_BIB74","series-title":"Proceedings of the 19th IEEE Symposium on Foundations of Computer Science","first-page":"92","article-title":"Alternating pushdown automata","author":"Ladner","year":"1978"},{"issue":"7\/8","key":"10.1016\/0020-0255(91)90008-I_BIB75","first-page":"419","article-title":"The importance of plane labyrinths","volume":"18","author":"Meinel","year":"1982","journal-title":"EIK"},{"key":"10.1016\/0020-0255(91)90008-I_BIB76","series-title":"IFIP Congress 71","first-page":"166","article-title":"Array automata and array grammars","author":"Milgram","year":"1971"},{"key":"10.1016\/0020-0255(91)90008-I_BIB77","doi-asserted-by":"crossref","first-page":"147","DOI":"10.1016\/S0019-9958(76)80004-6","article-title":"A region crossing problem for array-bounded automata","volume":"31","author":"Milgram","year":"1976","journal-title":"Inform. Control"},{"key":"10.1016\/0020-0255(91)90008-I_BIB78","article-title":"Computational complexity in one- and two-dimensional tape automata","author":"Morita","year":"1978"},{"key":"10.1016\/0020-0255(91)90008-I_BIB79","article-title":"Three-way horizontally context-sensitive array grammars","author":"Morita","year":"1981"},{"key":"10.1016\/0020-0255(91)90008-I_BIB80","first-page":"982","article-title":"Computational complexity of L(m, n) tape-bounded two-dimensional tape Turing machines","author":"Morita","year":"1977","journal-title":"IECE Jpn. Trans. (D)"},{"key":"10.1016\/0020-0255(91)90008-I_BIB81","first-page":"1077","article-title":"Language recognition abilities of several two-dimensional tape automata and their relation to tape complexities","author":"Morita","year":"1977","journal-title":"IECE Jpn. Trans. (D)"},{"key":"10.1016\/0020-0255(91)90008-I_BIB82","first-page":"381","article-title":"Lower bounds on tape complexity of two-dimensional tape Turing machines","author":"Morita","year":"1978","journal-title":"IECE Jpn. Trans. (D)"},{"key":"10.1016\/0020-0255(91)90008-I_BIB83","article-title":"Accepting capability of offside-free two-dimensional marker automata\u2014the simulation of four-way automata by three-way tape-bounded Turing machines","author":"Morita","year":"1979"},{"issue":"4\u20135","key":"10.1016\/0020-0255(91)90008-I_BIB84","doi-asserted-by":"crossref","first-page":"182","DOI":"10.1016\/0020-0190(81)90054-5","article-title":"Acceptors for isometric parallel context-free array languages","volume":"13","author":"Nakamura","year":"1981","journal-title":"Inform. Process. Lett."},{"key":"10.1016\/0020-0255(91)90008-I_BIB85","series-title":"Proceedings of the 4th International Joint Conference on Pattern Recognition","article-title":"Bottom-up cellular pyramids for image analysis","author":"Nakamura","year":"1978"},{"key":"10.1016\/0020-0255(91)90008-I_BIB86","first-page":"458","article-title":"Accepting ability of linear time nondeterministic bottom-up pyramid cellular automata","author":"Nakazono","year":"1988","journal-title":"IEICE Trans. (D)"},{"issue":"4","key":"10.1016\/0020-0255(91)90008-I_BIB87","doi-asserted-by":"crossref","first-page":"325","DOI":"10.1016\/0031-3203(86)90058-0","article-title":"T-recognition of T-languages, a new approach to describe and program the parallel pattern recognition capabilities of d-dimensional tessellation structures","volume":"19","author":"Pecht","year":"1986","journal-title":"Pattern Recognition"},{"key":"10.1016\/0020-0255(91)90008-I_BIB88","doi-asserted-by":"crossref","first-page":"177","DOI":"10.1016\/S0019-9958(76)80006-X","article-title":"Some notes on finite-state picture languages","volume":"31","author":"Rosenfeld","year":"1976","journal-title":"Inform. Control"},{"key":"10.1016\/0020-0255(91)90008-I_BIB89","series-title":"Picture Languages (Formal Models for Picture Recognition)","author":"Rosenfeld","year":"1977"},{"key":"10.1016\/0020-0255(91)90008-I_BIB90","doi-asserted-by":"crossref","first-page":"43","DOI":"10.1016\/0020-0190(73)90011-2","article-title":"Parallel\/sequential array automata","volume":"2","author":"Rosenfeld","year":"1973","journal-title":"Inform. Process. Lett."},{"key":"10.1016\/0020-0255(91)90008-I_BIB91","first-page":"177","article-title":"Relationships between nondeterministic and deterministic tape complexities","volume":"4","author":"Savitch","year":"1970","journal-title":"JCSS"},{"key":"10.1016\/0020-0255(91)90008-I_BIB92","doi-asserted-by":"crossref","first-page":"179","DOI":"10.1016\/0020-0255(79)90021-5","article-title":"Real-time recognition of two-dimensional tapes by cellular automata","volume":"19","author":"Seki","year":"1979","journal-title":"Inform. Sci."},{"issue":"2","key":"10.1016\/0020-0255(91)90008-I_BIB93","doi-asserted-by":"crossref","first-page":"283","DOI":"10.1145\/321694.321701","article-title":"One-pass complexity of digital picture properties","volume":"19","author":"Selkow","year":"1972","journal-title":"J. Assoc. Comput. Math."},{"key":"10.1016\/0020-0255(91)90008-I_BIB94","doi-asserted-by":"crossref","first-page":"236","DOI":"10.1016\/0146-664X(74)90017-3","article-title":"Pebble automata on arrays","volume":"3","author":"Shah","year":"1974","journal-title":"Comput. Graphics Image Process."},{"key":"10.1016\/0020-0255(91)90008-I_BIB95","doi-asserted-by":"crossref","first-page":"175","DOI":"10.1016\/0020-0255(81)90023-2","article-title":"Pushdown automata on arrays","volume":"25","author":"Shah","year":"1981","journal-title":"Inform. Sci."},{"key":"10.1016\/0020-0255(91)90008-I_BIB96","doi-asserted-by":"crossref","first-page":"335","DOI":"10.1016\/0304-3975(80)90053-5","article-title":"Halting space-bounded computations (Note)","volume":"10","author":"Sipser","year":"1980","journal-title":"Theoret. Comput. Sci."},{"key":"10.1016\/0020-0255(91)90008-I_BIB97","article-title":"Array languages and Lindenmayer systems\u2014a survey","author":"Siromoney","year":"1985"},{"key":"10.1016\/0020-0255(91)90008-I_BIB98","series-title":"Graph-Grammars and Their Application to Computer Science","first-page":"549","article-title":"Advances in array languages","volume":"291","author":"Siromoney","year":"1987"},{"key":"10.1016\/0020-0255(91)90008-I_BIB99","doi-asserted-by":"crossref","first-page":"119","DOI":"10.1016\/S0019-9958(77)90337-0","article-title":"Extended controlled table L-arrays","volume":"35","author":"Siromoney","year":"1977","journal-title":"Inform. Control"},{"key":"10.1016\/0020-0255(91)90008-I_BIB100","series-title":"Proceedings of the 12th Switching and Automata Theory","first-page":"144","article-title":"Two-dimensional formal languages and pattern recognition by cellular automata","author":"Smith","year":"1971"},{"key":"10.1016\/0020-0255(91)90008-I_BIB101","first-page":"233","article-title":"Real-time language recognition by one-dimensional cellular automata","volume":"6","author":"Smith","year":"1972","journal-title":"JCSS"},{"key":"10.1016\/0020-0255(91)90008-I_BIB102","series-title":"IEEE Conference Rec. on Switching Circuit Theory and Logical Design","first-page":"179","article-title":"Hierarchies of memory limited computations","author":"Stearns","year":"1965"},{"key":"10.1016\/0020-0255(91)90008-I_BIB103","doi-asserted-by":"crossref","first-page":"279","DOI":"10.1007\/BF00299636","article-title":"The method of forcing for nondeterministic automata","volume":"26","author":"Szelepcsenyi","year":"1988","journal-title":"Acta Informatica"},{"issue":"5","key":"10.1016\/0020-0255(91)90008-I_BIB104","doi-asserted-by":"crossref","first-page":"199","DOI":"10.1016\/0020-0190(82)90117-X","article-title":"A finite 5-pebble automaton can search every maze","volume":"15","author":"Szepietowski","year":"1982","journal-title":"Inform. Process. Lett."},{"issue":"6","key":"10.1016\/0020-0255(91)90008-I_BIB105","doi-asserted-by":"crossref","first-page":"361","DOI":"10.1016\/0020-0190(87)90111-6","article-title":"There are no fully space constructible functions between log log n and log n","volume":"24","author":"Szepietowski","year":"1987","journal-title":"Inform. Process. Lett."},{"key":"10.1016\/0020-0255(91)90008-I_BIB106","series-title":"On three-way two-dimensional Turing machines, manuscript","author":"Szepietowski","year":"1987"},{"key":"10.1016\/0020-0255(91)90008-I_BIB107","first-page":"244","article-title":"(k, l)-neighborhood template A-type bounded cellular acceptors","author":"Taniguchi","year":"1981","journal-title":"IECE Jpn. Trans. (D)"},{"key":"10.1016\/0020-0255(91)90008-I_BIB108","first-page":"1062","article-title":"(k, l)-neighborhood template A-type bounded cellular acceptors\u2014refinements of hierarchical properties","author":"Taniguchi","year":"1983","journal-title":"IECE Jpn. Trans. (D)"},{"key":"10.1016\/0020-0255(91)90008-I_BIB109","first-page":"1711","article-title":"Relationship between the accepting powers of (k, l)-neighborhood template A-type 1-dimensional bounded cellular acceptors and other types of 2-dimensional automata","author":"Taniguchi","year":"1985","journal-title":"IECE Jpn. Trans. (D)"},{"key":"10.1016\/0020-0255(91)90008-I_BIB110","first-page":"279","article-title":"Closure properties of (k, l)-neighborhood template A-type 1-dimensional bounded cellular acceptors","author":"Taniguchi","year":"1986","journal-title":"IECE Jpn. Trans. (D)"},{"issue":"C","key":"10.1016\/0020-0255(91)90008-I_BIB111","first-page":"578","article-title":"Some decision problems for two-dimensional nonwriting automata","author":"Taniguchi","year":"1971","journal-title":"IECE Jpn. Trans."},{"key":"10.1016\/0020-0255(91)90008-I_BIB112","doi-asserted-by":"crossref","first-page":"179","DOI":"10.1016\/0304-3975(83)90048-8","article-title":"Two-dimensional pattern matching by two-dimensional on-line tessellation acceptors","volume":"24","author":"Toda","year":"1983","journal-title":"Theoret. Comput. Sci."},{"key":"10.1016\/0020-0255(91)90008-I_BIB113","first-page":"817","article-title":"Pattern recognition by automata on a two-dimensional tape","author":"Umeo","year":"1976","journal-title":"IECE Jpn. Trans. (D)"},{"key":"10.1016\/0020-0255(91)90008-I_BIB114","doi-asserted-by":"crossref","first-page":"181","DOI":"10.1007\/978-3-7091-8596-4_13","article-title":"On cellular automata with a finite number of state changes","volume":"3","author":"Vollmar","year":"1981","journal-title":"Comput. Suppl."},{"issue":"5","key":"10.1016\/0020-0255(91)90008-I_BIB115","doi-asserted-by":"crossref","first-page":"366","DOI":"10.1109\/TC.1981.1675797","article-title":"Finite-turn repetitive checking automata and sequential\/parallel matrix languages","volume":"C-30","author":"Wang","year":"1981","journal-title":"IEEE Trans. Comput."},{"key":"10.1016\/0020-0255(91)90008-I_BIB116","first-page":"778","article-title":"Space complexity for recognizing connectedness in three-dimensional patterns","author":"Yamamoto","year":"1981","journal-title":"IECE Jpn. Trans. (E)"}],"container-title":["Information Sciences"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:002002559190008I?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:002002559190008I?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2019,3,18]],"date-time":"2019-03-18T13:23:49Z","timestamp":1552915429000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/002002559190008I"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1991,6]]},"references-count":116,"journal-issue":{"issue":"1-3","published-print":{"date-parts":[[1991,6]]}},"alternative-id":["002002559190008I"],"URL":"https:\/\/doi.org\/10.1016\/0020-0255(91)90008-i","relation":{},"ISSN":["0020-0255"],"issn-type":[{"value":"0020-0255","type":"print"}],"subject":[],"published":{"date-parts":[[1991,6]]}}}