{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,15]],"date-time":"2026-10-15T13:23:13Z","timestamp":1792070593579,"version":"4.4.0"},"publisher-location":"Berlin, Heidelberg","reference-count":24,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783642248962","type":"print"},{"value":"9783642248979","type":"electronic"}],"license":[{"start":{"date-parts":[[2011,1,1]],"date-time":"2011-01-01T00:00:00Z","timestamp":1293840000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2011]]},"DOI":"10.1007\/978-3-642-24897-9_9","type":"book-chapter","created":{"date-parts":[[2011,11,5]],"date-time":"2011-11-05T03:47:48Z","timestamp":1320464868000},"page":"183-213","source":"Crossref","is-referenced-by-count":15,"title":["A Survey on Picture-Walking Automata"],"prefix":"10.1007","author":[{"given":"Jarkko","family":"Kari","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ville","family":"Salo","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","reference":[{"key":"9_CR1","first-page":"155","volume-title":"FOCS","author":"M. Blum","year":"1967","unstructured":"Blum, M., Hewitt, C.: Automata on a 2-dimensional tape. In: FOCS, pp. 155\u2013160. IEEE, Los Alamitos (1967)"},{"key":"9_CR2","first-page":"215","volume-title":"Two-dimensional languages","author":"D. Giammarresi","year":"1997","unstructured":"Giammarresi, D., Restivo, A.: Two-dimensional languages, pp. 215\u2013267. Springer-Verlag New York, Inc., New York (1997), \n                  \n                    http:\/\/portal.acm.org\/citation.cfm?id=267871.267875"},{"key":"9_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"221","DOI":"10.1007\/3-540-54345-7_65","volume-title":"Mathematical Foundations of Computer Science 1991","author":"O.H. Ibarra","year":"1991","unstructured":"Ibarra, O.H., Jiang, T., Wang, H.: Some results concerning 2-d on-line tessellation acceptors and 2-d alternating finite automata. In: Tarlecki, A. (ed.) MFCS 1991. LNCS, vol.\u00a0520, pp. 221\u2013230. Springer, Heidelberg (1991)"},{"issue":"3","key":"9_CR4","doi-asserted-by":"publisher","first-page":"195","DOI":"10.1016\/0020-0255(79)90017-3","volume":"17","author":"K. Inoue","year":"1979","unstructured":"Inoue, K., Takanami, I.: Three-way tape-bounded two-dimensional turing machines. Inf. Sci.\u00a017(3), 195\u2013220 (1979)","journal-title":"Inf. Sci."},{"issue":"4\/5","key":"9_CR5","doi-asserted-by":"publisher","first-page":"245","DOI":"10.1016\/0020-0190(80)90151-9","volume":"10","author":"K. Inoue","year":"1980","unstructured":"Inoue, K., Takanami, I.: A note on decision problems for three-way two-dimensional finite automata. Inf. Process. Lett.\u00a010(4\/5), 245\u2013248 (1980)","journal-title":"Inf. Process. Lett."},{"issue":"1-3","key":"9_CR6","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1016\/0020-0255(91)90008-I","volume":"55","author":"K. Inoue","year":"1991","unstructured":"Inoue, K., Takanami, I.: A survey of two-dimensional automata theory. Inf. Sci.\u00a055(1-3), 99\u2013121 (1991)","journal-title":"Inf. Sci."},{"key":"9_CR7","doi-asserted-by":"publisher","first-page":"61","DOI":"10.1016\/0304-3975(83)90093-2","volume":"27","author":"K. Inoue","year":"1983","unstructured":"Inoue, K., Takanami, I., Taniguchi, H.: Two-dimensional alternating turing machines. Theor. Comput. Sci.\u00a027, 61\u201383 (1983)","journal-title":"Theor. Comput. Sci."},{"issue":"1","key":"9_CR8","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/0020-0255(88)90005-9","volume":"45","author":"A. Ito","year":"1988","unstructured":"Ito, A., Inoue, K., Takanami, I.: A note on three-way two-dimensional alternating turing machines. Inf. Sci.\u00a045(1), 1\u201322 (1988)","journal-title":"Inf. Sci."},{"issue":"3","key":"9_CR9","doi-asserted-by":"publisher","first-page":"273","DOI":"10.1016\/0304-3975(89)90154-0","volume":"66","author":"A. Ito","year":"1989","unstructured":"Ito, A., Inoue, K., Takanami, I.: Deterministic two-dimensional on-line tessellation acceptors are equivalent to two-way two-dimensional alternating finite automata through 180-rotation. Theor. Comput. Sci.\u00a066(3), 273\u2013287 (1989)","journal-title":"Theor. Comput. Sci."},{"issue":"1-3","key":"9_CR10","doi-asserted-by":"publisher","first-page":"193","DOI":"10.1016\/S0019-9958(82)90572-1","volume":"55","author":"A. Ito","year":"1982","unstructured":"Ito, A., Inoue, K., Takanami, I., Taniguchi, H.: Two-dimensional alternating turing machines with only universal states. Information and Control\u00a055(1-3), 193\u2013221 (1982)","journal-title":"Information and Control"},{"key":"9_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"396","DOI":"10.1007\/3-540-44693-1_35","volume-title":"STACS 2001","author":"J. Kari","year":"2001","unstructured":"Kari, J., Moore, C.: New results on alternating and non-deterministic two-dimensional finite-state automata. In: Ferreira, A., Reichel, H. (eds.) STACS 2001. LNCS, vol.\u00a02010, pp. 396\u2013406. Springer, Heidelberg (2001)"},{"key":"9_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"134","DOI":"10.1007\/978-3-540-27812-2_13","volume-title":"Theory Is Forever","author":"J. Kari","year":"2004","unstructured":"Kari, J., Moore, C.: Rectangles and squares recognized by two-dimensional automata. In: Karhum\u00e4ki, J., Maurer, H., P\u0103un, G., Rozenberg, G. (eds.) Theory Is Forever. LNCS, vol.\u00a03113, pp. 134\u2013144. Springer, Heidelberg (2004)"},{"issue":"1","key":"9_CR13","doi-asserted-by":"publisher","first-page":"61","DOI":"10.1016\/0020-0255(85)90041-6","volume":"35","author":"E.B. Kinber","year":"1985","unstructured":"Kinber, E.B.: Three-way automata on rectangular tapes over a one-letter alphabet. Inf. Sci.\u00a035(1), 61\u201377 (1985)","journal-title":"Inf. Sci."},{"issue":"1","key":"9_CR14","doi-asserted-by":"publisher","first-page":"135","DOI":"10.1137\/0213010","volume":"13","author":"R.E. Ladner","year":"1984","unstructured":"Ladner, R.E., Lipton, R.J., Stockmeyer, L.J.: Alternating pushdown and stack automata. SIAM J. Comput.\u00a013(1), 135\u2013155 (1984)","journal-title":"SIAM J. Comput."},{"key":"9_CR15","doi-asserted-by":"publisher","first-page":"909","DOI":"10.1023\/A:1023027932419","volume":"91","author":"K. Lindgren","year":"1998","unstructured":"Lindgren, K., Moore, C., Nordahl, M.: Complexity of two-dimensional patterns. Journal of Statistical Physics\u00a091, 909\u2013951 (1998), \n                  \n                    http:\/\/dx.doi.org\/10.1023\/A:1023027932419","journal-title":"Journal of Statistical Physics"},{"key":"9_CR16","volume-title":"Computation: finite and infinite machines","author":"M.L. Minsky","year":"1967","unstructured":"Minsky, M.L.: Computation: finite and infinite machines. Prentice-Hall, Inc., Englewood Cliffs (1967)"},{"issue":"3-4","key":"9_CR17","doi-asserted-by":"publisher","first-page":"303","DOI":"10.1016\/S0020-0255(98)00008-5","volume":"110","author":"T. Okazaki","year":"1998","unstructured":"Okazaki, T., Zhang, L., Inoue, K., Ito, A., Wang, Y.: A note on two-dimensional probabilistic finite automata. Inf. Sci.\u00a0110(3-4), 303\u2013314 (1998)","journal-title":"Inf. Sci."},{"issue":"4","key":"9_CR18","doi-asserted-by":"publisher","first-page":"570","DOI":"10.1145\/321356.321364","volume":"13","author":"R. Parikh","year":"1966","unstructured":"Parikh, R.: On context-free languages. J. ACM\u00a013(4), 570\u2013581 (1966)","journal-title":"J. ACM"},{"key":"9_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"374","DOI":"10.1007\/3-540-60249-6_69","volume-title":"Fundamentals of Computation Theory","author":"H. Petersen","year":"1995","unstructured":"Petersen, H.: Some results concerning two-dimensional turing machines and finite automata. In: Reichel, H. (ed.) FCT 1995. LNCS, vol.\u00a0965, pp. 374\u2013382. Springer, Heidelberg (1995)"},{"key":"9_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"760","DOI":"10.1007\/BFb0055827","volume-title":"Mathematical Foundations of Computer Science 1998","author":"K. Reinhardt","year":"1998","unstructured":"Reinhardt, K.: On some recognizable picture-languages. In: Brim, L., Gruska, J., Zlatu\u0161ka, J. (eds.) MFCS 1998. LNCS, vol.\u00a01450, pp. 760\u2013770. Springer, Heidelberg (1998)"},{"key":"9_CR21","volume-title":"Picture Languages: Formal Models for Picture Recognition","author":"A. Rosenfeld","year":"1979","unstructured":"Rosenfeld, A.: Picture Languages: Formal Models for Picture Recognition. Academic Press, Inc., Orlando (1979)"},{"key":"9_CR22","unstructured":"Salo, V.: Classes of picture languages defined by tiling systems, automata and closure properties. Master\u2019s thesis, University of Turku (2011)"},{"key":"9_CR23","first-page":"73","volume-title":"FOCS","author":"M. Sipser","year":"1978","unstructured":"Sipser, M.: Halting space-bounded computations. In: FOCS, pp. 73\u201374. IEEE, Los Alamitos (1978)"},{"issue":"1-2","key":"9_CR24","doi-asserted-by":"publisher","first-page":"183","DOI":"10.1016\/0020-0255(92)90068-J","volume":"63","author":"A. Szepietowski","year":"1992","unstructured":"Szepietowski, A.: Some remarks on two-dimensional finite automata. Inf. Sci.\u00a063(1-2), 183\u2013189 (1992)","journal-title":"Inf. Sci."}],"container-title":["Lecture Notes in Computer Science","Algebraic Foundations in Computer Science"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-24897-9_9","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,4,15]],"date-time":"2019-04-15T12:29:32Z","timestamp":1555331372000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-24897-9_9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011]]},"ISBN":["9783642248962","9783642248979"],"references-count":24,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-24897-9_9","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2011]]}}}