Czasopismo
2005
|
Vol. 64, nr 1-4
|
159-170
Tytuł artykułu
Autorzy
Wybrane pełne teksty z tego czasopisma
Warianty tytułu
Języki publikacji
Abstrakty
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
Czasopismo
Rocznik
Tom
Strony
159-170
Opis fizyczny
Bibliogr. 20 poz.
Twórcy
autor
- Institut für Computersprachen, Fakultät für Informatik, Technische Universität Wien, Favoritenstr. 9-11, A-1040 Wien, Austria, fernau@informatik.uni-tuebingen.de
autor
- Institut für Computersprachen, Fakultät für Informatik, Technische Universität Wien Favoritenstr. 9-11, A-1040 Wien, Austria , rudi@emcc.at
autor
- Technische Universität München, Institut für Informatik Boltzmannstr. 3, D-85748 Garching bei München, Germany , holzer@in.tum.de
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
Typ dokumentu
Bibliografia
Identyfikatory
Identyfikator YADDA
bwmeta1.element.baztech-article-BUS2-0005-0119