| Autor: |
Rudolf Freund, Sergiu Ivanov, Marion Oswald, K.G. Subramanian |
| Jazyk: |
angličtina |
| Rok vydání: |
2013 |
| Předmět: |
|
| Zdroj: |
Electronic Proceedings in Theoretical Computer Science, Vol 128, Iss Proc. MCU 2013, Pp 62-75 (2013) |
| Druh dokumentu: |
article |
| ISSN: |
2075-2180 |
| DOI: |
10.4204/EPTCS.128.14 |
| Popis: |
We consider the (one-dimensional) array counterpart of contextual as well as insertion and deletion string grammars and consider the operations of array insertion and deletion in array grammars. First we show that the emptiness problem for P systems with (one-dimensional) insertion rules is undecidable. Then we show computational completeness of P systems using (one-dimensional) array insertion and deletion rules even of norm one only. The main result of the paper exhibits computational completeness of one-dimensional array grammars using array insertion and deletion rules of norm at most two. |
| Databáze: |
Directory of Open Access Journals |
| Externí odkaz: |
|
