×
Latteux, M.; Simplot, D.

Context-sensitive string languages and recognizable picture languages. (English) Zbl 0895.68083

Inf. Comput. 138, No. 2, 160-169 (1997).
Summary: The theorem stating that the family of frontiers of recognizable tree languages is exactly the family of context-free languages [see J. Mezei and J. B. Wright, Inf. Control 11, 3-29 (1967; Zbl 0155.34301)], is a basic result in the theory of formal languages. In this article, we prove a similar result: the family of frontiers of recognizable picture languages is exactly the family of context-sensitive languages.

Cited in 8 Documents

MSC:

68Q45 Formal languages and automata

Keywords:

recognizable tree languages; context-free languages

Citations:

Zbl 0155.34301
PDF BibTeX XML Cite
\textit{M. Latteux} and \textit{D. Simplot}, Inf. Comput. 138, No. 2, 160--169 (1997; Zbl 0895.68083)
Full Text: DOI Link
  • logo of hbz
  • logo of WorldCat

References:

[1] M. Blum, C. Hewitt, 1967, Automata on 2-dimensional tape, Conference Record of 1967 Eighth Annual Symposium on Switching and Automata Theory, 155, 160, IEEE Press, New York
[2] Giammarresi, D.; Restivo, A., Recognizable picture languages, Internat. J. pattern recognition artificial intelligence, 31-46, (1992)
[3] Giammarresi, D.; Restivo, A., Two-dimensional languages, Handbook of formal languages, (1996), Springer-Verlag Berlin/New York
[4] Giammarresi, D.; Restivo, A.; Seibert, S.; Thomas, W., Monadic second-order logic over rectangular pictures and recognizability by tiling systems, Inform. and comput., 125, 32-45, (1996) · Zbl 0853.68131
[5] Ginsburg, S., Algebraic and automata-theoretic properties of formal languages, (1975), North-Holland Amsterdam · Zbl 0325.68002
[6] Inoue, K.; Nakamura, A., Some properties of two-dimensional on-line tessellation acceptors, Inform. sci., 13, 95-121, (1977) · Zbl 0371.94067
[7] K. Inoue, I. Takanami, 1990, A survey of two-dimensional automata theory, Proc. Aspects and Prospects of Theoretical Computer Science, 5th International Meeting of Young Computer Scientists, J. DassowJ. Kelemen, Lecture Notes in Computer Science, 381, 2, 91, Springer-Verlag, Berlin
[8] Latteux, M.; Simplot, D., Recognizable picture languages and domino tiling, Theoret. comput. sci., 178, 275-283, (1997) · Zbl 0912.68106
[9] Mezei, J.; Wright, J.B., Algebraic automata and context-free sets, Inform. and comput., 11, 3-29, (1967) · Zbl 0155.34301
[10] Rosenfeld, A., Picture languages, (1979), Academic Press New York · Zbl 0471.68074
[11] Siromoney, G.; Siromoney, R.; Krithivasan, K., Picture languages with array rewriting rules, Inform. and comput., 22, 447-470, (1973) · Zbl 0266.68037
[12] H. Sperber, 1985, Idealautomaten, Technische Fakultät der Universität Erlangen-Nürnberg
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.