{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,9]],"date-time":"2026-05-09T04:13:15Z","timestamp":1778299995456,"version":"3.51.4"},"publisher-location":"Berlin\/Heidelberg","reference-count":116,"publisher":"Springer-Verlag","isbn-type":[{"value":"354051516X","type":"print"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/bfb0015929","type":"book-chapter","created":{"date-parts":[[2005,11,23]],"date-time":"2005-11-23T06:25:05Z","timestamp":1132727105000},"page":"72-91","source":"Crossref","is-referenced-by-count":9,"title":["A survey of two-dimensional automata theory"],"prefix":"10.1007","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":"297","reference":[{"issue":"3","key":"7_CR1","first-page":"123","volume":"15","author":"H. Antelmann","year":"1979","unstructured":"H. Antelmann, L. Budach and H.A. Rollik, On universal traps, EIK 15, 3 (1979), 123\u2013131.","journal-title":"EIK"},{"key":"7_CR2","unstructured":"T.Beyer, Recognition of topological invariants by iterative arrays, Ph.D.Thesis, MIT, 1970."},{"key":"7_CR3","doi-asserted-by":"crossref","unstructured":"M.Blum and C.Hewitt, Automata on a two-dimensional tape, IEEE Symposium on Switching and Automata Theory, 1967, 155\u2013160.","DOI":"10.1109\/FOCS.1967.6"},{"key":"7_CR4","unstructured":"M.Blum and D.Kozen, On the power of the compass, Proc. of the 19th Annual Symp. on Foundations of Computer Science, 1978"},{"key":"7_CR5","doi-asserted-by":"crossref","unstructured":"M.Blum and W.J.Sakoda, On the capability of finite automata in 2 and 3 dimensional space, Proc. of the 18th Annual Symp. on Foundations of Computer Science, 1977, 147\u2013161.","DOI":"10.1109\/SFCS.1977.20"},{"key":"7_CR6","unstructured":"W.Bucher and K.Culik II, On real time and linear time cellular automata, Research Report 115, Institute fur Informationsverarbeitung, Technical University of Graz, 1983."},{"key":"7_CR7","doi-asserted-by":"crossref","unstructured":"L.Budach, Environments, labyrinths and Automata, Lecture Notes in Computer Science 56, Springer Verlag, 1977.","DOI":"10.1007\/3-540-08442-8_70"},{"key":"7_CR8","doi-asserted-by":"crossref","first-page":"195","DOI":"10.1002\/mana.19780860120","volume":"86","author":"L. Budach","year":"1978","unstructured":"\u2014, Automata and Labyrinths, Math. Nachr. 86 (1978), 195\u2013282.","journal-title":"Math. Nachr."},{"issue":"1\/2","key":"7_CR9","first-page":"13","volume":"18","author":"L. Budach","year":"1982","unstructured":"L. Budach and C. Meinel, Environments and automata I, EIK 18, 1\/2 (1982), 13\u201340.","journal-title":"EIK"},{"issue":"3","key":"7_CR10","first-page":"115","volume":"18","author":"L. Budach","year":"1982","unstructured":"\u2014, Environments and automata II, EIK 18, 3 (1982), 115\u2013139.","journal-title":"EIK"},{"issue":"1","key":"7_CR11","doi-asserted-by":"crossref","first-page":"114","DOI":"10.1145\/322234.322243","volume":"28","author":"A.K. Chandra","year":"1981","unstructured":"A.K. Chandra, D.C. Kozen and L.J. Stockmeyer, Alternation, J.Assoc.Comput.Mach. 28, 1 (1981), 114\u2013133.","journal-title":"J.Assoc.Comput.Mach."},{"key":"7_CR12","unstructured":"C.Choffrut and K.Culik II, On real-time cellular automata and trellis automata, Research Report F114, Institute fur Informationsverarbeitung, Technical University of Graz, 1983."},{"key":"7_CR13","first-page":"111","volume":"2","author":"P. Dietz","year":"1980","unstructured":"P. Dietz and S.R. Kosaraju, Recognition of topological equivalence of patterns by array automata, JCSS 2 (1980), 111\u2013116.","journal-title":"JCSS"},{"key":"7_CR14","doi-asserted-by":"crossref","first-page":"261","DOI":"10.1016\/S0019-9958(80)90164-3","volume":"44","author":"C.R. Dyer","year":"1980","unstructured":"C.R. Dyer, One-way bounded cellular automata, Information and Control 44 (1980),261\u2013281.","journal-title":"Information and Control"},{"key":"7_CR15","doi-asserted-by":"crossref","first-page":"25","DOI":"10.1016\/0020-0255(81)90038-4","volume":"23","author":"C.R. Dyer","year":"1981","unstructured":"\u2014, Relation of one-way parallel\/sequential automata to 2-d finite automata, Information Sciences 23 (1981), 25\u201330.","journal-title":"Information Sciences"},{"key":"7_CR16","doi-asserted-by":"crossref","unstructured":"C.R.Dyer and A.Rosenfeld, Cellular pyramids for image analysis, University of Maryland, Computer Science Center, TR-544, AFOSR-77-3271, 1977.","DOI":"10.21236\/ADA042156"},{"issue":"1","key":"7_CR17","doi-asserted-by":"crossref","first-page":"29","DOI":"10.1109\/TPAMI.1981.4767048","volume":"PAMI-3","author":"C.R. Dyer","year":"1981","unstructured":"\u2014, Parallel image processing by memory-augmented cellular automata, IEEE Trans. on Pattern Analysis and Machine Intelligence, PAMI-3, 1 (1981), 29\u201341.","journal-title":"IEEE Trans. on Pattern Analysis and Machine Intelligence"},{"key":"7_CR18","doi-asserted-by":"crossref","first-page":"54","DOI":"10.1016\/S0019-9958(81)90598-2","volume":"48","author":"C.R. Dyer","year":"1981","unstructured":"\u2014, Triangle cellular automata, Information and Control 48 (1981), 54\u201369.","journal-title":"Information and Control"},{"key":"7_CR19","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/0020-0255(87)90013-2","volume":"42","author":"E.M. Ehlers","year":"1987","unstructured":"E.M. Ehlers and S.H. Von Solms, A hierarchy of random context grammars and automata, Information Sciences 42 (1987), 1\u201329.","journal-title":"Information Sciences"},{"key":"7_CR20","doi-asserted-by":"crossref","unstructured":"M.J.Fisher, Two characterizations of the context sensitive languages, IEEE Symp. on Switching and Automata Theory (1969), 149\u2013156.","DOI":"10.1109\/SWAT.1969.29"},{"key":"7_CR21","first-page":"26","volume":"33","author":"J. Hartmanis","year":"1987","unstructured":"J. Hartmanis, The structural complexity column, Bulletin of the EATCS, 33 (October 1987), 26\u201339.","journal-title":"Bulletin of the EATCS"},{"issue":"8\/9","key":"7_CR22","first-page":"453","volume":"23","author":"A. Hemmerling","year":"1987","unstructured":"A. Hemmerling, Normed two-plane traps for finite systems of cooperating compass automata, EIK 23, 8\/9 (1987),, 453\u2013470.","journal-title":"EIK"},{"key":"7_CR23","doi-asserted-by":"crossref","first-page":"433","DOI":"10.1007\/3-540-10854-8_47","volume":"117","author":"F. Hoffmann","year":"1981","unstructured":"F. Hoffmann, One pebble does not suffice to search plane labyrinths, Lecture Notes in Computer Science 117 (Fundamentals of Computation Theory), 1981, 433\u2013444.","journal-title":"Lecture Notes in Computer Science"},{"issue":"2","key":"7_CR24","doi-asserted-by":"crossref","first-page":"283","DOI":"10.1145\/321694.321701","volume":"19","author":"J.E. Hopcroft","year":"1972","unstructured":"J.E. Hopcroft and J.D. Ullman, Some results on tape-bounded Turing machines, J.Assoc.Comput.Math. 19, 2 (1972), 283\u2013295.","journal-title":"J.Assoc.Comput.Math."},{"key":"7_CR25","volume-title":"Introduction to Automata Theory, Languages, and Computation","author":"J.E. Hopcroft","year":"1979","unstructured":"\u2014 Introduction to Automata Theory, Languages, and Computation, Addison-Wesley, Reading, Mass. 1979."},{"key":"7_CR26","unstructured":"J.Hromkovic, K.Inoue and I.Takanami, Lower bounds for language recognition on two-dimensional alternating multihead machines, To appear in JCSS."},{"key":"7_CR27","doi-asserted-by":"crossref","first-page":"269","DOI":"10.1080\/00207167408803092","volume":"4-A","author":"O.H. Ibarra","year":"1974","unstructured":"O.H. Ibarra and R.T. Melson, Some results concerning automata on two-dimensional tapes, Intern.J.Computer Math. 4-A (1974), 269\u2013279.","journal-title":"Intern.J.Computer Math."},{"key":"7_CR28","unstructured":"N.Immerman, Nondeterministic space is closed under complement, submitted for publication."},{"key":"7_CR29","doi-asserted-by":"crossref","unstructured":"K.Inoue, Investigations of two-dimensional on-line tessellation acceptors (in Japanese), Ph.D.Thesis, Nagoya University, 1977.","DOI":"10.1016\/0020-0255(77)90023-8"},{"key":"7_CR30","unstructured":"K.Inoue and A.Nakamura, Some notes on parallel sequential array acceptors (in Japanese), IECE of Japan Trans.(D), March 1975, 167\u2013169."},{"key":"7_CR31","unstructured":"\u2014, On the relation between two-dimensional on-line tessellation acceptors and one-dimensional bounded cellular acceptors (in Japanese), IECE of Japan Trans.(D), September 1976, 613\u2013620."},{"key":"7_CR32","unstructured":"\u2014, Some properties of one-way parallel sequential array acceptors and two-dimensional one-marker automata (in Japanese), IECE of Japan Trans.(D), September 1976, 682\u2013683."},{"key":"7_CR33","unstructured":"\u2014, Some properties of parallel sequential array acceptors and two-dimensional two-marker automata (in Japanese), IECE of Japan Trans.(D), September 1976, 680\u2013681."},{"key":"7_CR34","unstructured":"\u2014, Some properties of two-dimensional on-line tessellation acceptors (in Japanese), IECE of Japan Trans.(D), October 1976, 695\u2013702."},{"key":"7_CR35","doi-asserted-by":"crossref","first-page":"95","DOI":"10.1016\/0020-0255(77)90023-8","volume":"13","author":"K. Inoue","year":"1977","unstructured":"\u2014, Some properties of two-dimensional on-line tessellation acceptors, Information Sciences 13 (1977), 95\u2013121.","journal-title":"Information Sciences"},{"key":"7_CR36","unstructured":"\u2014, Some properties of two-dimensional automata with a one-letter alphabet-Recognizability of functions by two-dimensional automata-(in Japanese), IECE of Japan Trans.(D), September 1977, 679\u2013686."},{"key":"7_CR37","unstructured":"\u2014, Nonclosure properties of two-dimensional on-line tessellation acceptors and one-way parallel sequential array acceptors, IECE of Japan Trans. (E), September 1977, 475\u2013476."},{"key":"7_CR38","unstructured":"\u2014, Some properties on two-dimensional nondeterministic finite automata and parallel sequential array acceptors (in Japanese), IECE of Japan Trans. (D), November 1977, 990\u2013997."},{"issue":"3","key":"7_CR39","doi-asserted-by":"crossref","first-page":"305","DOI":"10.1016\/S0019-9958(79)90604-1","volume":"41","author":"K. Inoue","year":"1979","unstructured":"\u2014, Two-dimensional multipass on-line tessellation acceptors, Information and Control 41, 3 (June 1979), 305\u2013323.","journal-title":"Information and Control"},{"issue":"7","key":"7_CR40","doi-asserted-by":"crossref","first-page":"207","DOI":"10.1080\/00207167908803172","volume":"A","author":"K. Inoue","year":"1979","unstructured":"\u2014, Two-dimensional finite automata and unacceptable functions, Intern.J.Computer Math. Section A, 7 (1979), 207\u2013213.","journal-title":"Intern.J.Computer Math."},{"issue":"1","key":"7_CR41","doi-asserted-by":"crossref","first-page":"143","DOI":"10.1016\/0020-0255(78)90004-X","volume":"15","author":"K. Inoue","year":"1978","unstructured":"K. Inoue and I. Takanami, A note on closure properties of the classes of sets accepted by tape-bounded two-dimensional Turing machines, Information Sciences 15, 1 (1978), 143\u2013158.","journal-title":"Information Sciences"},{"issue":"1","key":"7_CR42","doi-asserted-by":"crossref","first-page":"229","DOI":"10.1016\/0020-0255(78)90049-X","volume":"15","author":"K. Inoue","year":"1978","unstructured":"\u2014, Cyclic closure properties of automata on a two-dimensional tape, Information Sciences 15, 1 (1978), 229\u2013242.","journal-title":"Information Sciences"},{"issue":"1","key":"7_CR43","doi-asserted-by":"crossref","first-page":"34","DOI":"10.1016\/0020-0190(79)90089-9","volume":"8","author":"K. Inoue","year":"1979","unstructured":"\u2014, A note on bottom-up pyramid acceptors, Information Processing Letters 8, 1 (1979), 34\u201337.","journal-title":"Information Processing Letters"},{"issue":"3","key":"7_CR44","doi-asserted-by":"crossref","first-page":"195","DOI":"10.1016\/0020-0255(79)90017-3","volume":"17","author":"K. Inoue","year":"1979","unstructured":"\u2014, Three-way tape-bounded two-dimensional Turing machines, Information Sciences 17, 3 (1979), 195\u2013220.","journal-title":"Information Sciences"},{"issue":"3","key":"7_CR45","doi-asserted-by":"crossref","first-page":"247","DOI":"10.1016\/0020-0255(79)90048-3","volume":"18","author":"K. Inoue","year":"1979","unstructured":"\u2014, Closure properties of three-way and four-way tape-bounded two-dimensional Turing machines, Information Sciences 18, 3 (1979), 247\u2013265.","journal-title":"Information Sciences"},{"issue":"1","key":"7_CR46","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/0020-0255(79)90029-X","volume":"19","author":"K. Inoue","year":"1979","unstructured":"\u2014, Three-way two-dimensional multicounter automata, Information Sciences 19, 1 (1979), 1\u201320.","journal-title":"Information Sciences"},{"key":"7_CR47","unstructured":"\u2014, Some properties of three-way two-dimensional multicounter automata over square tapes (in Japanese), IECE of Japan Trans. (D), October 1979, 673\u2013680."},{"issue":"1","key":"7_CR48","doi-asserted-by":"crossref","first-page":"41","DOI":"10.1016\/0020-0255(80)90023-7","volume":"20","author":"K. Inoue","year":"1980","unstructured":"\u2014, A note on deterministic three-way tape-bounded two-dimensional Turing machines, Information Sciences 20, 1 (1980), 41\u201355.","journal-title":"Information Sciences"},{"issue":"5","key":"7_CR49","doi-asserted-by":"crossref","first-page":"245","DOI":"10.1016\/0020-0190(80)90151-9","volume":"10","author":"K. Inoue","year":"1980","unstructured":"\u2014, A note on decision problems for three-way two-dimensional finite automata, Information Processing Letters 10, 5 (July 1980), 245\u2013248.","journal-title":"Information Processing Letters"},{"key":"7_CR50","doi-asserted-by":"crossref","unstructured":"K.Inoue, I.Takanami and J.Hromkovic, A leaf-size hierarchy of two-dimensional alternating Turing machines, Discrete Algorithms and Complexity, Academic Press (1987), 389\u2013404.","DOI":"10.1016\/B978-0-12-386870-1.50027-7"},{"issue":"1","key":"7_CR51","doi-asserted-by":"crossref","first-page":"49","DOI":"10.1016\/0020-0190(78)90040-6","volume":"7","author":"K. Inoue","year":"1978","unstructured":"K. Inoue, I. Takanami and A. Nakamura, A note on two-dimensional finite automata, Information Processing Letters 7, 1 (1978), 49\u201352.","journal-title":"Information Processing Letters"},{"issue":"1","key":"7_CR52","doi-asserted-by":"crossref","first-page":"45","DOI":"10.1016\/S0020-0255(80)80023-5","volume":"22","author":"K. Inoue","year":"1980","unstructured":"\u2014, Nonclosure property of nondeterministic two-dimensional finite automata under cyclic closure, Information Sciences 22, 1 (1980), 45\u201350.","journal-title":"Information Sciences"},{"key":"7_CR53","doi-asserted-by":"crossref","first-page":"126","DOI":"10.1016\/0734-189X(84)90134-8","volume":"26","author":"K. Inoue","year":"1984","unstructured":"\u2014, Connected pictures are not recognizable by deterministic two-dimensional on-line tessellation acceptors, Computer Vision, Graphics, and Image Processing 26 (1984), 126\u2013129.","journal-title":"Computer Vision, Graphics, and Image Processing"},{"key":"7_CR54","unstructured":"\u2014, A note on time-bounded bottom-up pyramid cellular acceptors, To appear in Information Sciences."},{"key":"7_CR55","unstructured":"K.Inoue, I.Takanami and H.Taniguchi, Three-way two-dimensional simple multihead finite automata-Hierarchical properties-(in Japanese), IECE of Japan Trans. (D), February 1979, 65\u201372."},{"key":"7_CR56","unstructured":"\u2014, Three-way two-dimensional simple multihead finite automata-Closure properties-(in Japanese), IECE of Japan Trans. (D), April 1979, 273\u2013280."},{"key":"7_CR57","unstructured":"\u2014, The accepting powers of two-dimensional automata over square tapes (in Japanese), IECE of Japan Trans. (D), February 1980, 113\u2013120."},{"key":"7_CR58","doi-asserted-by":"crossref","first-page":"61","DOI":"10.1016\/0304-3975(83)90093-2","volume":"27","author":"K. Inoue","year":"1983","unstructured":"\u2014, Two-dimensional alternating Turing machines, Theoretical Computer Science 27 (1983), 61\u201383.","journal-title":"Theoretical Computer Science"},{"issue":"1\u20133","key":"7_CR59","doi-asserted-by":"crossref","first-page":"193","DOI":"10.1016\/S0019-9958(82)90572-1","volume":"55","author":"A. Ito","year":"1982","unstructured":"A. Ito, k. Inoue, I. Takanami and H. Taniguchi, Two-dimensional alternating Turing machines with only universal states, Information and Control 55, 1\u20133 (1982), 193\u2013221.","journal-title":"Information and Control"},{"key":"7_CR60","unstructured":"\u2014, A note on space complexity of nondeterministic two-dimensional Turing machines, IECE of Japan Trans. (E), August 1983, 508\u2013509."},{"key":"7_CR61","unstructured":"\u2014, Hierarchy of the accepting power of cellular space based on the number of state changes (in Japanese), IECE of Japan Trans. (D), September 1985, 1553\u20131561."},{"key":"7_CR62","unstructured":"\u2014, Relationships of the accepting powers between cellular space with bounded number of state-changes and other automata (in Japanese), IECE of Japan Trans. (D), September 1985, 1562\u20131570."},{"key":"7_CR63","unstructured":"\u2014, State-change bounded rectangular array cellular space acceptors with three-neighbor (in Japanese), IEICE of Japan Trans. (D), December 1987, 2339\u20132347."},{"issue":"1","key":"7_CR64","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/0020-0255(88)90005-9","volume":"45","author":"A. Ito","year":"1988","unstructured":"A. Ito, K. Inoue and I. Takanami, A note on three-way two-dimensional alternating Turing machines, Information Sciences 45, 1 (1988), 1\u201322.","journal-title":"Information Sciences"},{"key":"7_CR65","unstructured":"\u2014, Deterministic on-line tessellation acceptors are equivalent to two-way two-dimensional alternating finite automata through 180\u00b0 rotations, to appear in Theoretical Computer Science."},{"key":"7_CR66","unstructured":"\u2014, A relationship between one-dimensional bounded cellular acceptors and two-dimensional alternating finite automata, manuscript (1987)."},{"key":"7_CR67","unstructured":"\u2014, The simulation of two-dimensional one-marker automata by three-way two-dimensional Turing machines, to appear in the fifth International Meeting of Young Computer Scientists, November 14\u201318, 1988, Czechoslovakia."},{"key":"7_CR68","unstructured":"\u2014, Some closure properties of the class of sets accepted by three-way two-dimensional alternating finite automata, submitted for publication."},{"key":"7_CR69","unstructured":"K.Iwama, ASPACE(o(loglog n)) is regular, Research Report, KSU\/ICS, Institute of Computer Sciences, Kyoto Sangyo University, March 1986."},{"key":"7_CR70","doi-asserted-by":"crossref","first-page":"61","DOI":"10.1016\/0020-0255(85)90041-6","volume":"35","author":"E.B. Kinber","year":"1985","unstructured":"E.B. Kinber, Three-way automata on rectangular tapes over a one-letter alphabet, Information Sciences 35 (1985), 61\u201377.","journal-title":"Information Sciences"},{"issue":"6","key":"7_CR71","doi-asserted-by":"crossref","first-page":"561","DOI":"10.1109\/T-C.1974.223995","volume":"C-23","author":"S.R. Kosaraju","year":"1974","unstructured":"S.R. Kosaraju, On some open problems in the theory of cellular automata, IEEE Trans. on Computers C-23, 6 (1974), 561\u2013565.","journal-title":"IEEE Trans. on Computers"},{"key":"7_CR72","doi-asserted-by":"crossref","unstructured":"\u2014, Fast parallel processing array algorithms for some graph problems, Proc. of the 11th Annual ACM Symp. on Theory of Computing (1979), 231\u2013236.","DOI":"10.1145\/800135.804417"},{"key":"7_CR73","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1080\/00207167408803078","volume":"4-A","author":"K. Krithivasan","year":"1974","unstructured":"K. Krithivasan and R. Siromoney, Array automata and operations on array languages, Intern.J.Computer Math. 4-A (1974), 3\u201330.","journal-title":"Intern.J.Computer Math."},{"key":"7_CR74","doi-asserted-by":"crossref","unstructured":"R.E.Ladner, R.J.Lipton and L.J.Stockmeyer, Alternating pushdown automata, Proc. of the 19th IEEE Symp. on Foundations of Computer Science (1978), 92\u2013106.","DOI":"10.1109\/SFCS.1978.6"},{"issue":"7\/8","key":"7_CR75","first-page":"419","volume":"18","author":"C. Meinel","year":"1982","unstructured":"C. Meinel, The importance of plane labyrinths, EIK 18, 7\/8 (1982), 419\u2013422.","journal-title":"EIK"},{"key":"7_CR76","first-page":"166","volume":"71","author":"D.L. Milgram","year":"1971","unstructured":"D.L. Milgram and A. Rosenfeld, Array automata and array grammars, IFIP Congress 71 (1971), Booklet Ta2, 166\u2013173.","journal-title":"IFIP Congress"},{"key":"7_CR77","doi-asserted-by":"crossref","first-page":"147","DOI":"10.1016\/S0019-9958(76)80004-6","volume":"31","author":"D.L. Milgram","year":"1976","unstructured":"D.L. Milgram, A region crossing problem for array-bounded automata, Information and Control 31 (1976), 147\u2013152.","journal-title":"Information and Control"},{"key":"7_CR78","unstructured":"K.Morita, Computational complexity in one-and two-dimensional tape automata, Ph.D. Thesis, Osaka University, 1978."},{"key":"7_CR79","unstructured":"K.Morita and K.Sugata, Three-way horizontally context-sensitive array grammars (in Japanese), Technical Report No.AL80-66, IECE of Japan (1981)."},{"key":"7_CR80","unstructured":"K.Morita, H.Umeo and K.Sugata, Computational complexity of L(m,n) tape-bounded two-dimensional tape Turing machines (in Japanese), IECE of Japan Trans. (D), November 1977, 982\u2013989."},{"key":"7_CR81","unstructured":"\u2014, Language recognition abilities of several two-dimensional tape automata and their relation to tape complexities (in Japanese), IECE of Japan Trans. (D), December 1977, 1077\u20131084."},{"key":"7_CR82","unstructured":"K.Morita, H.Umeo, H.Ebi and K.Sugata, Lower bounds on tape complexity of two-dimensional tape Turing machines (in Japanese), IECE of Japan Trans. (D), 1978, 381\u2013386."},{"key":"7_CR83","unstructured":"K.Morita, H.Umeo and K.Sugata, Accepting capability of offside-free two-dimensional marker automata-the simulation of four-way automata by three-way tape-bounded Turing machines-(in Japanese), Technical Report No.AL79-2, IECE of Japan, 1979."},{"issue":"4\u20135","key":"7_CR84","doi-asserted-by":"crossref","first-page":"182","DOI":"10.1016\/0020-0190(81)90054-5","volume":"13","author":"A. Nakamura","year":"1981","unstructured":"A. Nakamura and K. Aizawa, Acceptors for isometric parallel context-free array languages, Information Processing Letters 13, Nos4\u20135 (1981), 182\u2013186.","journal-title":"Information Processing Letters"},{"key":"7_CR85","unstructured":"A.Nakamura and C.R.Dyer, Bottom-up cellular pyramids for image analysis, Proc. of the 4th Int.Joint Conf.Pattern Recognition, 1978."},{"key":"7_CR86","unstructured":"K.Nakazono, K.Morita and K.Sugata, Accepting ability of linear time nondeterministic bottom-up pyramid cellular automata (in japanese), IEICE of Trans. (D), February 1988, 458\u2013461."},{"issue":"4","key":"7_CR87","doi-asserted-by":"crossref","first-page":"325","DOI":"10.1016\/0031-3203(86)90058-0","volume":"19","author":"J. Pecht","year":"1986","unstructured":"J. Pecht, T-recognition of T-languages, a new approach to describe and program the parallel pattern recognition capabilities of d-dimensional tessellation structures, Pattern Recognition 19, 4 (1986), 325\u2013338.","journal-title":"Pattern Recognition"},{"key":"7_CR88","doi-asserted-by":"crossref","first-page":"177","DOI":"10.1016\/S0019-9958(76)80006-X","volume":"31","author":"A. Rosenfeld","year":"1976","unstructured":"A. Rosenfeld, Some notes on finite-state picture languages, Information and Control 31 (1976), 177\u2013184.","journal-title":"Information and Control"},{"key":"7_CR89","volume-title":"Picture Languages (Formal Models for Picture Recognition)","author":"A. Rosenfeld","year":"1977","unstructured":"\u2014, Picture Languages (Formal Models for Picture Recognition), Academic Press, New York, 1977."},{"key":"7_CR90","doi-asserted-by":"crossref","first-page":"43","DOI":"10.1016\/0020-0190(73)90011-2","volume":"2","author":"A. Rosenfeld","year":"1973","unstructured":"A. Rosenfeld and D.L. Milgram, Parallel\/sequential array automata, Information Processing Letters 2 (1973), 43\u201346.","journal-title":"Information Processing Letters"},{"key":"7_CR91","first-page":"177","volume":"4","author":"W.J. Savitch","year":"1970","unstructured":"W.J. Savitch, Relationships between nondeterministic and deterministic tape complexities, JCSS 4 (1970), 177\u2013192.","journal-title":"JCSS"},{"key":"7_CR92","doi-asserted-by":"crossref","first-page":"179","DOI":"10.1016\/0020-0255(79)90021-5","volume":"19","author":"S. Seki","year":"1979","unstructured":"S. Seki, Real-time recognition of two-dimensional tapes by cellular automata, Information Sciences 19 (1979), 179\u2013198.","journal-title":"Information Sciences"},{"issue":"2","key":"7_CR93","doi-asserted-by":"crossref","first-page":"283","DOI":"10.1145\/321694.321701","volume":"19","author":"S.M. Selkow","year":"1972","unstructured":"S.M. Selkow, One-pass complexity of digital picture properties, J.Assoc.Comput.Math. 19(2) (1972), 283\u2013295.","journal-title":"J.Assoc.Comput.Math."},{"key":"7_CR94","doi-asserted-by":"crossref","first-page":"236","DOI":"10.1016\/0146-664X(74)90017-3","volume":"3","author":"A.N. Shah","year":"1974","unstructured":"A.N. Shah, Pebble automata on arrays, Computer Graphics and Image Processing 3 (1974), 236\u2013246.","journal-title":"Computer Graphics and Image Processing"},{"key":"7_CR95","doi-asserted-by":"crossref","first-page":"175","DOI":"10.1016\/0020-0255(81)90023-2","volume":"25","author":"A.N. Shah","year":"1981","unstructured":"\u2014, Pushdown automata on arrays, Information Sciences 25 (1981), 175\u2013193.","journal-title":"Information Sciences"},{"key":"7_CR96","doi-asserted-by":"crossref","first-page":"335","DOI":"10.1016\/0304-3975(80)90053-5","volume":"10","author":"M. Sipser","year":"1980","unstructured":"M. Sipser, Halting space-bounded computations (Note), Theoretical Computer Science 10 (1980), 335\u2013338.","journal-title":"Theoretical Computer Science"},{"key":"7_CR97","volume-title":"The Book of L","author":"R. Siromoney","year":"1985","unstructured":"R. Siromoney, Array languages and Lindenmayer systems \u2014 a survey, in\u2019 The Book of L\u2019 (eds. G. Rozenberg and A. Salomaa), Springer-Verlag, Berlin, 1985."},{"key":"7_CR98","doi-asserted-by":"crossref","unstructured":"\u2014, Advances in array languages, Lecture Notes in Computer Science 291 (Graph-Grammars and Their Application to Computer Science), Ehrig et al. (Eds.), 1987, 549\u2013563.","DOI":"10.1007\/3-540-18771-5_75"},{"key":"7_CR99","doi-asserted-by":"crossref","first-page":"119","DOI":"10.1016\/S0019-9958(77)90337-0","volume":"35","author":"R. Siromoney","year":"1977","unstructured":"R. Siromoney and G. Siromoney, Extended controlled table L-arrays, Information and Control 35 (1977), 119\u2013138.","journal-title":"Information and Control"},{"key":"7_CR100","doi-asserted-by":"crossref","unstructured":"A.R.Smith III, Two-dimensional formal languages and pattern recognition by cellular automata, Proc. of the 12th Switching and Automata Theory (1971), 144\u2013152.","DOI":"10.1109\/SWAT.1971.29"},{"key":"7_CR101","first-page":"233","volume":"6","author":"A.R. Smith III","year":"1972","unstructured":"\u2014, Real-time language recognition by one-dimensional cellular automata, JCSS 6 (1972), 233\u2013253.","journal-title":"JCSS"},{"key":"7_CR102","doi-asserted-by":"crossref","unstructured":"R.E.Stearns, J.Hartmanis and P.M.Lewis II,, Hierarchies of memory limited computations, IEEE Conf.Rec.on Switching Circuit Theory and Logical Design (1965),, 179\u2013190.","DOI":"10.1109\/FOCS.1965.11"},{"key":"7_CR103","unstructured":"R.Szelepcsenyi, The method of forcing for nondeterministic automata, submitted for publication."},{"issue":"5","key":"7_CR104","doi-asserted-by":"crossref","first-page":"199","DOI":"10.1016\/0020-0190(82)90117-X","volume":"15","author":"A. Szepietowski","year":"1982","unstructured":"A. Szepietowski, A finite 5-pebble automaton can search every maze, Information Processing Letters 15, 5 (December 1982), 199\u2013204.","journal-title":"Information Processing Letters"},{"issue":"6","key":"7_CR105","doi-asserted-by":"crossref","first-page":"361","DOI":"10.1016\/0020-0190(87)90111-6","volume":"24","author":"A. Szepietowski","year":"1987","unstructured":"\u2014, There are no fully space constructible functions between loglog n and log n, Information Processing Letters 24, 6 (April 1987), 361\u2013362.","journal-title":"Information Processing Letters"},{"key":"7_CR106","unstructured":"\u2014, On three-way two-dimensional Turing machines, manuscript (1987)."},{"key":"7_CR107","unstructured":"H.Taniguchi, K.Inoue, I.Takanami and S.Seki, (k,1)-neighborhood template-type bounded cellular acceptors (in Japanese), IECE of Japan Trans. (D), March 1981, 244\u2013251."},{"key":"7_CR108","unstructured":"\u2014, (k,1)-neighborhood template-type bounded cellular acceptors-refinements of hierarchical properties-(in Japanese), IECE of Japan Trans. (D), September 1983, 1062\u20131069."},{"key":"7_CR109","unstructured":"\u2014, Relationship between the accepting powers of (k,1)-neighborhood template-type 1-dimensional bounded cellular acceptors and other types of 2-dimensional automata (in Japanese), IECE of Japan Trans. (D), October 1985, 1711\u20131718."},{"key":"7_CR110","unstructured":"\u2014, Closure properties of (k,1)-neighborhood template-type 1-dimensional bounded cellular acceptors (in Japanese), IECE of Japan Trans. (D), March 1986, 279\u2013290."},{"key":"7_CR111","unstructured":"K.Taniguchi and T.Kasami, Some decision problems for two-dimensional nonwriting automata (in Japanese), IECE of Japan Trans. (C), 1971, 578\u2013585."},{"key":"7_CR112","doi-asserted-by":"crossref","first-page":"179","DOI":"10.1016\/0304-3975(83)90048-8","volume":"24","author":"M. Toda","year":"1983","unstructured":"M. Toda, K. Inoue and I. Takanami, Two-dimensional pattern matching by two-dimensional on-line tessellation acceptors, Theoretical Computer Science 24 (1983), 179\u2013194.","journal-title":"Theoretical Computer Science"},{"key":"7_CR113","unstructured":"H.Umeo, K.Morita and K.Sugata, Pattern recognition by automata on a two-dimensional tape, IECE of Japan Trans. (D), November 1976, 817\u2013824."},{"key":"7_CR114","doi-asserted-by":"crossref","first-page":"181","DOI":"10.1007\/978-3-7091-8596-4_13","volume":"3","author":"R. Vollmar","year":"1981","unstructured":"R. Vollmar, On cellular automata with a finite number of state changes, Comput.Suppl. 3 (1981), 181\u2013191.","journal-title":"Comput.Suppl."},{"issue":"5","key":"7_CR115","doi-asserted-by":"crossref","first-page":"366","DOI":"10.1109\/TC.1981.1675797","volume":"C-30","author":"P.S.P. Wang","year":"1981","unstructured":"P.S.P. Wang, Finite-turn repetitive checking automata and sequential\/parallel matrix languages, IEEE Trans. on Computers C-30, 5 (May 1981), 366\u2013370.","journal-title":"IEEE Trans. on Computers"},{"key":"7_CR116","unstructured":"Y.Yamamoto, K.Morita and K.Sugata, Space complexity for recognizing connectedness in three-dimensional patterns, IECE of Japan Trans. (E), 1981, 778\u2013785."}],"container-title":["Lecture Notes in Computer Science","Machines, Languages, and Complexity"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/www.springerlink.com\/index\/pdf\/10.1007\/BFb0015929","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,5]],"date-time":"2025-01-05T21:30:27Z","timestamp":1736112627000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BFb0015929"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["354051516X"],"references-count":116,"URL":"https:\/\/doi.org\/10.1007\/bfb0015929","relation":{},"subject":[]}}