Wyniki wyszukiwania - BazTech

Ograniczanie wyników

1 Fundamenta Informaticae

1 2017

Znaleziono wyników: 1

Liczba wyników na stronie

Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych: array languages

Sortuj według:

Ogranicz wyniki do:

Non-Isometric Contextual Array Grammars and the Role of Regular Control and Local Selectors

Fernau H., Siromoney R., Freund R., Subramanian K. G.

Fundamenta Informaticae

2017

Vol. 155, nr 1/2

209--232

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.