Abstract
The aim of this chapter is to generalize concepts and techniques of formal language theory to two dimensions. Informally, a two-dimensional string is called a picture and is defined as a rectangular array of symbols taken from a finite alphabet. A two-dimensional language (or picture language) is a set of pictures.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
M. Blum and C. Hewitt. Automata on a two-dimensional tape. IEEE Symposium on Switching and Automata Theory,pp. 155–160, 1967.
J. Berstel. Transductions and Contex-Pree Languages. Teubner, Stuttgart, 1979.
J. R. Büchi. Weak second-order arithmetic and finite automata. Z. Math, Logik Grundlagen Math., vol. 6, pp. 66–92, 1960.
J. R. Büchi. On a decision methods in restricted second oreder arithmetic. Proc. Intern. Cong. In Logic, Methodology and Philosophy of Science. E. Nagel et al. (Eds.), Stanford Univ. Press, CA. pp. 1–11, 1961.
N. Chomsky and M. P. Shützenberger. The algebraic theory of context-free languages. In Computer Programming and Formal Systems. P. Bradford and D. Hirschberg. (Eds.), North Holland, Amsterdam, 1963, pp. 118–161.
B. Courcelle. Graph rewriting: An algebraic and logic approach. In: Handbook of Theoretical Computer Science,Vol. B. J. V. Leeuwen, (Ed.), Elsevier, Amsterdam, 1990, pp. 193–242.
S. Eilenberg. Automata, Languages and Machines. Vol. A, Academic Press, New York, 1974.
H. D. Ebbinghaus, J. Flum and W. Thomas. Mathematical Logic, Springer-Verlag, Berlin, 1984.
R. Fagin. Monadic generalized spectra, Z. math. Logik Grandi. Math. 21 (1975), pp. 89–96.
R. Fagin, L. Stockmeyer and M. Y. Vardi. On monadic NP vs. monadic co-NP. In Proc. 8th IEEE Conf. on Structure in Complexity Theory, 1993, pp. 19–30.
K. S. Fu. Syntactic methods in pattern recognition. Academic Press, New York 1974.
D. Giammarresi. Two-dimensional languages and recognizable functions. In Proc. Developments in Language Theory, Finland, 1993. G. Rozenberg and A. Salomaa (Eds). World Scientific Publishing Co., Singapore, 1994, pp. 290–301.
D. Giammarresi and A. Restivo. Recognizable picture languages. International Journal Pattern Recognition and Artificial Intelligence. Special issue on Parallel Image Processing. M. Nivat, A. Saoudi and P. S. P. Wang (Eds.), pp. 31–46, 1992. Also in Proc. First International Colloquium on Parallel Image Processing, 1991. Same journal, Vol. 6, No. 2& 3, pp. 241–256, 1992.
D. Giammarresi and A. Restivo. Two-dimensional finite state recognizability. Fundamenta Informaticae. Special Issue: Formal Language Theory, Vol. 25, no. 3, 4, (1996), pp. 399–422.
D. Giammarresi, A. Restivo, S. Seibert and W. Thomas. Monadic second order logic over rectangular pictures and recognizability by tiling systems. Information and Computation, vol. 125, no. 1, pp. 32–45, 1996. An abstract appeared also in Proc. XI Symposium on Theoretical Aspect of Computer Science (STACS) 1994 Lecture Notes in Computer Science 775, pp. 365–376, Springer-Verlag, Berlin, 1994.
A. Gilon. Langages d’images Mémoire de Licenciée en Science Mathématiques réalisé sous la direction de V. Bruyere. Université de Mons-Hainaut, 1995.
J. E. Hoperoft, and J. D. Ullman. Introduction to Automata Theory, Languages and Computation. Addison-Wesley, Reading, MA, 1979.
K. Inoue and A. Nakamura. Some properties of two-dimensional on-line tessellation acceptors. Information Sciences,Vol. 13, pp. 95–121, 1977.
K. Inoue and A. Nakamura. Nonclosure properties of two-dimensional on-line tessellation acceptors and one-way parallel/sequential array acceptors. Transaction of IECE of Japan, Vol. 6, pp. 475–476, 1977.
K. Inoue and A. Nakamura. Two-dimensional finite automata and unacceptable functions. Intern. J. Comput. Math., Sec. A, Vol. 7, pp. 207–213, 1979.
K. Inoue and I. Takanami. A Survey of two-dimensional automata theory. In Proc. 5th Int. Meeting of Young Computer Scientists, J. Dasson and J. Kelemen (Eds.), pp. 72–91. Lecture Notes in Computer Science 381, Springer-Verlag, Berlin, 1990.
K. Inoue and I. Takanami. A Characterization of recognizable picture languages. In Proc. Second International Colloquium on Parallel Image Processing, A. Nakamura et al. (Eds.), Lecture Notes in Computer Science 654, Springer-Verlag, Berlin 1993.
K. Inoue, I. Takanami and A. Nakamura. A note on two-dimensional finite automata. Information Processing Letters, Vol. 7, No. 1, pp. 49–52, 1978.
E. B. Kinber. Three-way automata on rectangular tapes over a one-letter alphabet. Information Sciences, Vol. 35, pp. 61–77, 1985.
M. Latteux and D. Simplot. Recognizable Picture Languages and Domino Tiling Internal Report IT-94–264. Laboratoire d’Informatique Fondamentale de Lille. Université de Lille, France.
O. Matz. Classification of Picture Languages with Rational Expressions, Grammars and Logic Formulas. Diploma thesis. Christian Albrechts Universität Institut für Informatik und Praktische Mathematik Kiel, Germany, 1996. (In German).
R. Mc Naughton and S. Papert. Counter-free Automata. M. I. T. Press, 1971.
M. Minski and S. Papert. Perceptron. M. I. T. Press, 1969.
M. Nivat, A. Saoudi and V. R. Dare. Parallel generation of finite images. International Journal of Pattern Recognition and Artificial Intelligence, Vol. 3, No. 3 & 4, pp. 279–294, 1989.
M. Nivat, A. Saoudi and V. R. Dare. Parallel generation of infinite images. International Journal of Computer Math, Vol. 35, pp. 25–42, 1990.
A. Rosenfeld. Picture Languages (Formal Models for Picture Recognition). Academic Press, New York, 1979.
R. Siromoney. On equal matrix languages. Info. and Control 14, pp. 135–151, 1969.
R. Siromoney. Advances in array languages. In Graph-Grammars and Their Applications to Computer Science, Ehrig et al. (Eds.), pp. 549–563. Lecture Notes in Computer Science 291, Springer-Verlag, Berlin, 1987.
R. Siromoney and K. Krithivasan. Parallel context-free languages. Info. and Control 24, pp. 155–162, 1974.
G. Siromoney, R. Siromoney, K. Krithivasan. Picture languages with array rewriting rules. Info. and Control 22, pp. 447–470, 1973.
R. Siromoney, K. Subramanian, K. Rangarajan. Parallel/Sequential rectangular arrays with tables. Intern. Journ. Computer Math. 6, pp. 143–158. 1977.
H. Straubing. Finite automata, Formal logic and Circuit complexity. Birkhäuser, Basel, 1994.
W. Thomas. On Logics, Tilings, and Automata. In Proc. 18th Int. Colloquium on Automata, Languages and Programming, pp. 441–453. Lecture Notes in Computer Science 510, Springer-Verlag, Berlin, 1991.
P. S. Wang. Sequential/Parallel matrix array languages. Journal of Cybernetics, vol. 5, pp. 19–36, 1975.
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 1997 Springer-Verlag Berlin Heidelberg
About this chapter
Cite this chapter
Giammarresi, D., Restivo, A. (1997). Two-Dimensional Languages. In: Rozenberg, G., Salomaa, A. (eds) Handbook of Formal Languages. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-59126-6_4
Download citation
DOI: https://doi.org/10.1007/978-3-642-59126-6_4
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-63859-6
Online ISBN: 978-3-642-59126-6
eBook Packages: Springer Book Archive