Representations of Recursively Enumerable Array Languages by Contextual Array Grammars

• Autorzy: Fernau H. , Freund R. , Holzer M.
• Języki publikacji: EN

Abstrakty

EN

The main result proved in this paper shows that the natural embedding of any recursively enumerable one-dimensional array language in the two-dimensional space can be characterized by the projection of a two-dimensional array language generated by a contextual array grammar working in the t-mode and with norm one. Moreover, we show that any recursively enumerable one-dimensional array language can even be characterized by the projection of a two-dimensional array language generated by a contextual array grammar working in the t-mode where in the selectors of the contextual array productions only the ability to distinguish between blank and non-blank positions is necessary; in that case, the norm of the two-dimensional contextual array grammar working in the t-mode cannot be bounded.

Słowa kluczowe

EN

arrays; array grammars; contextual grammars; shape

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2005
• Tom: Vol. 64, nr 1-4
• Strony: 159--170
• Opis fizyczny: Bibliogr. 20 poz.

Twórcy

autor

Fernau H.

• Institut für Computersprachen, Fakultät für Informatik, Technische Universität Wien, Favoritenstr. 9-11, A-1040 Wien, Austria

autor

Freund R.

• Institut für Computersprachen, Fakultät für Informatik, Technische Universität Wien Favoritenstr. 9-11, A-1040 Wien, Austria

autor

Holzer M.

• Technische Universität München, Institut für Informatik Boltzmannstr. 3, D-85748 Garching bei München, Germany

Bibliografia

• [1] Cook, C. R., Wang, P. S.-P.: A Chomsky hierarchy of isotonic array grammars and languages, Computer Graphics and Image Processing, 8, 1978, 144–152.
• [2] Csuhaj-Varjù, E., Dassow, J., Kelemen, J., Păun, Gh.: Grammar Systems. A Grammatical Approach to Distribution and Cooperation, Gordon and Breach, London, 1994.
• [3] Dassow, J., Freund, R., Păun, Gh.: Cooperating array grammar systems, International Journal of Pattern Recognition and Artificial Intelligence, 9, 1995, 1–25.
• [4] Ehrenfeucht, A., Păun, Gh., Rozenberg, G.: On representing recursively enumerable languages by internal contextual languages, Theoretical Computer Science 205, 1998, 61–83.
• [5] Ehrenfeucht, A., Mateescu, A., Păun, Gh., Rozenberg, G., Salomaa, A.: On representing RE languages by one-sided internal contextual languages, Acta Cybernetica, 12, 1996, 217–233.
• [6] Ehrenfeucht, A., Păun, Gh., Rozenberg, G.: The linear landscape of external contextual languages, Acta Informatica, 33, 1996, 571–593.
• [7] Ehrenfeucht, A., Păun, Gh., Rozenberg, G.: Contextual grammars and formal languages, in: Handbook of Formal Languages, Volume 2 (G. Rozenberg, A. Salomaa, Eds.), Springer-Verlag, Berlin, 1997, 237–293.
• [8] Fernau, H., Freund, R., Holzer, M.: The generative power of d-dimensional #-context-free array grammars, Proceedings of MCU’98, Volume 2, Metz, France, 1998, 43–56.
• [9] Freund, R., Păun, Gh., Rozenberg, G.: Contextual array grammars, Technical Report 95-38, Rijksuniversiteit Leiden, 1995.
• [10] Inoue, K., Takanami, I.: A survey of two-dimensional automata theory, in: Machines, Languages, and Complexity IMYCS’88 (J. Dassow, J. Kelemen, Eds.), LNCS 381, 1988, 72–91.
• [11] Marcus, S.: Contextual grammars, Rev. Roum. Math. Pures Appl., 14, 1969, 1525–1534.
• [12] Marcus, S.: Contextual grammars and natural languages, in: Handbook of Formal Languages, Volume 2 (G. Rozenberg, A. Salomaa, Eds.), Springer-Verlag, Berlin, 1997, 215–235.
• [13] Păun, Gh., Nguyen, X. M.: On the inner contextual grammars, Rev. Roum. Math. Pures Appl., 25, 1980, 641–651.
• [14] Păun, Gh., Rozenberg, G., Salomaa, A.: Contextual grammars: erasing, determinism, one-sided contexts, in: Developments in Language Theory (G. Rozenberg, A. Salomaa, Eds.),World Scientific Publ., Singapore, 1994, 370–388.
• [15] Păun, Gh., Rozenberg, G., Salomaa, A.: Contextual grammars: parallelism and blocking of derivation, Fundamenta Informaticae, 41, 1996, 83–108.
• [16] Păun, Gh.: Marcus Contextual Grammars, Studies in Linguistics and Philosophy, Kluwer Academic Publishers, Dordrecht,1997.
• [17] Rosenfeld, A.: Picture Languages, Academic Press, Reading, MA, 1979.
• [18] Vicolov-Dumitrescu, S.: On parallel contextual grammars, in: Mathematical Linguistics and Related Topics (Gh. Păun, Ed.), The Publ. House of the Romanian Academy of Science, Bucharest, 1994.
• [19] Wang, P. S.-P.: Some new results on isotonic array grammars, Information Processing Letters, 10, 1980, 129–131.
• [20] Yodogawa, E.: A note on array grammars, Information Processing Letters, 18, 1984, 51–54