Name
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 langauges 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. |
Year | DOI | Venue |
|---|---|---|
2015 | 10.1007/978-3-319-23111-2_5 | Lecture Notes in Computer Science |
Field | DocType | Volume |
Tree-adjoining grammar,Rule-based machine translation,Discrete mathematics,Computer science,Theoretical computer science,Turing machine,Computation,Undecidable problem | Conference | 9288 |
ISSN | Citations | PageRank |
0302-9743 | 2 | 0.41 |
References | Authors | |
6 | 4 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Henning Fernau | 1 | 1646 | 162.68 |
| Rudolf Freund | 2 | 12 | 2.39 |
| Rani Siromoney | 3 | 459 | 76.25 |
| K. G. Subramanian | 4 | 339 | 59.27 |