Affiliations: [a] FB 4 – Abteilung Informatikwissenschaften, Universität Trier, D-54296 Trier, Germany. [email protected] | [b] Institut für Computersprachen, Technische Universität Wien, A-1040 Wien, Austria. [email protected] | [c] Chennai Mathematical Institute, Kelambakkam 603103, India. [email protected] | [d] Department of Mathematics and Computer Science, Faculty of Science, Liverpool Hope University, Liverpool, L16 9JD, Great Britain. [email protected]
Correspondence:
[*]
Address for correspondence: FB 4 – Abteilung Informatikwissenschaften, Universität Trier, D-54296 Trier, Germany
Abstract: We consider the external variant of non-isometric d-dimensional contextual array grammars with regular control together with local selectors allowing for controlling how d-dimensional arrays are evolving by adjoining rectangular (d–1)-dimensional arrays. In the 1-dimensional case, the computational power of these non-isometric contextual array grammars with regular control and local selectors equals the computational power of isometric contextual array grammars with regular control. The string images of the languages of 1-dimensional arrays generated by these contextual array grammars exactly yield the linear languages. In the more-dimensional case, non-isometric d-dimensional contextual array grammars with regular control and local selectors can simulate the computations of (d – 1)-dimensional array grammars or Turing machines. Hence, for example, the emptiness problem for non-isometric d-dimensional contextual array grammars with regular control and local selectors for d > 1 is undecidable. We also compare the computational power of all variants of non-isometric d-dimensional contextual array grammars that we introduce to each other.
Keywords: Array languages, isometric versus non-isometric variants, contextual grammars
