Affiliations: Wilhelm-Schickard-Institut für Informatik,
Universität Tübingen, Sand 13, D-72076 Tübingen, Germany.
fernau@informatik.uni-tuebingen.de | Institut für Computersprachen, Fakultät
für Informatik, Technische Universität Wien, Favoritenstr. 9-11,
A-1040 Wien, Austria. rudi@emcc.at | Technische Universität München, Institut
für Informatik, Boltzmannstr. 3, D-85748 Garching bei München,
Germany. holzer@in.tum.de
Note: [] Address for correspondence: Institut für Computersprachen,
Fakultät für Informatik, Technische Universität Wien,
Favoritenstr. 9-11, A-1040 Wien, Austria
Abstract: 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 -mode cannot be bounded.
