Abstract
The row projection (resp., column projection) of a given two-dimensional language L is the one-dimensional language consisting of first rows (resp., first columns) of all two-dimensional words in L. The operation of row projection has previously been studied under the name “frontier language”, and previous work in this area has focused primarily on one- and two-dimensional language classes.
In this paper, we study projections of languages recognized by various two-dimensional automaton classes. We show that both the row and column projections of languages recognized by (four-way) two-dimensional automata are exactly context-sensitive. We also show that the column projections of languages recognized by unary three-way two-dimensional automata can be recognized using nondeterministic logspace. Finally, we study the state complexity of projection languages for two-way two-dimensional automata, focusing on the language operations of union and diagonal concatenation.
Smith and Salomaa were supported by Natural Sciences and Engineering Research Council of Canada Grant OGP0147224.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Anselmo, M., Giammarresi, D., Madonia, M.: Deterministic and unambiguous families within recognizable two-dimensional languages. Fund. Inform. 98(2–3), 143–166 (2010)
Anselmo, M., Giammarresi, D., Madonia, M.: Classification of string languages via tiling recognizable picture languages. In: Dediu, A.-H., Inenaga, S., Martín-Vide, C. (eds.) LATA 2011. LNCS, vol. 6638, pp. 105–116. Springer, Heidelberg (2011). https://doi.org/10.1007/978-3-642-21254-3_7
Blum, M., Hewitt, C.: Automata on a 2-dimensional tape. In: Miller, R.E. (ed.) SWAT 1967, pp. 155–160 (1967)
Giammarresi, D., Restivo, A.: Recognizable picture languages. Int. J. Pattern Recogn. Artif. Intell. 6(2–3), 241–256 (1992)
Giammarresi, D., Restivo, A.: Two-dimensional languages. In: Rozenberg, G., Salomaa, A. (eds.) Handbook of Formal Languages, pp. 215–267. Springer, Heidelberg (1997). https://doi.org/10.1007/978-3-642-59126-6_4
Hartmanis, J., Shank, H.: On the recognition of primes by automata. J. ACM 15(3), 382–389 (1968)
Holzer, M., Kutrib, M.: Nondeterministic descriptional complexity of regular languages. Int. J. Found. Comput. Sci. 14(6), 1087–1102 (2003)
Hopcroft, J.E., Ullman, J.D.: Introduction to Automata Theory, Languages, and Computation. Addison-Wesley, Reading (1979)
Inoue, K., Takanami, I.: A survey of two-dimensional automata theory. Inf. Sci. 55(1–3), 99–121 (1991)
Inoue, K., Takanami, I.: A characterization of recognizable picture languages. In: Nakamura, A., Nivat, M., Saoudi, A., Wang, P.S.P., Inoue, K. (eds.) ICPIA 1992. LNCS, vol. 654, pp. 133–143. Springer, Heidelberg (1992). https://doi.org/10.1007/3-540-56346-6_35
Kari, J., Moore, C.: Rectangles and squares recognized by two-dimensional automata. In: Karhumäki, J., Maurer, H., Păun, G., Rozenberg, G. (eds.) Theory Is Forever. LNCS, vol. 3113, pp. 134–144. Springer, Heidelberg (2004). https://doi.org/10.1007/978-3-540-27812-2_13
Kuroda, S.Y.: Classes of languages and linear-bounded automata. Inf. Control 7(2), 207–223 (1965)
Latteux, M., Simplot, D.: Context-sensitive string languages and recognizable picture languages. Inf. Comput. 138(2), 160–169 (1997)
Morita, K.: Two-dimensional languages. In: Martín-Vide, C., Mitrana, V., Păun, G. (eds.) Formal Languages and Applications, Studies in Fuzziness and Soft Computing, vol. 148, pp. 427–437. Springer, Heidelberg (2004). https://doi.org/10.1007/978-3-540-39886-8_22
Rosenfeld, A.: Picture Languages: Formal Models for Picture Recognition. Computer Science and Applied Mathematics. Academic Press, New York (1979)
Salomaa, A.: Theory of Automata, International Series of Monographs in Pure and Applied Mathematics, vol. 100. Pergamon Press, Oxford (1969)
Salomaa, A.: Formal Languages. Academic Press, New York (1973)
Shepherdson, J.C.: The reduction of two-way automata to one-way automata. IBM J. Res. Dev. 3(2), 198–200 (1959)
Smith, T.J.: Two-dimensional automata. Technical report 2019–637. Queen’s University, Kingston (2019)
Smith, T.J., Salomaa, K.: Decision problems for restricted variants of two-dimensional automata. In: Hospodár, M., Jirásková, G. (eds.) CIAA 2019. LNCS, vol. 11601, pp. 222–234. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-23679-3_18
Smith, T.J., Salomaa, K.: Concatenation operations and restricted variants of two-dimensional automata. arXiv:2008.11164 (2020)
Wood, D.: Theory of Computation. Computer Science and Technology Series. Harper & Row, New York (1987)
Author information
Authors and Affiliations
Corresponding authors
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2020 Springer Nature Switzerland AG
About this paper
Cite this paper
Smith, T.J., Salomaa, K. (2020). Recognition and Complexity Results for Projection Languages of Two-Dimensional Automata. In: Jirásková, G., Pighizzini, G. (eds) Descriptional Complexity of Formal Systems. DCFS 2020. Lecture Notes in Computer Science(), vol 12442. Springer, Cham. https://doi.org/10.1007/978-3-030-62536-8_17
Download citation
DOI: https://doi.org/10.1007/978-3-030-62536-8_17
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-62535-1
Online ISBN: 978-3-030-62536-8
eBook Packages: Computer ScienceComputer Science (R0)