Conţinutul numărului revistei |
Articolul precedent |
Articolul urmator |
![]() ![]() |
![]() ALHAZOV, Artiom, FERNAU, Henning, FREUND, Rudolf, IVANOV, Sergiu, SIROMONEY, Rani S., SUBRAMANIAN, K.G.. Contextual array grammars with matrix control, regular control languages, and tissue P systems control. In: Theoretical Computer Science, 2017, nr. 682, pp. 5-21. ISSN 0304-3975. DOI: https://doi.org/10.1016/j.tcs.2017.03.012 |
EXPORT metadate: Google Scholar Crossref CERIF DataCite Dublin Core |
Theoretical Computer Science | |
Numărul 682 / 2017 / ISSN 0304-3975 /ISSNe 1879-2294 | |
|
|
DOI:https://doi.org/10.1016/j.tcs.2017.03.012 | |
Pag. 5-21 | |
Rezumat | |
We consider d-dimensional contextual array grammars and investigate their computational power when using various control mechanisms – matrices, regular control languages, and tissue P systems, which work like regular control languages, but may end up with a final check for the non-applicability of some rules. For d≥2, d-dimensional contextual array grammars are less powerful than matrix contextual array grammars, which themselves are less powerful than contextual array grammars with regular control languages. The use of tissue P systems with their final non-applicability check even yields some additional computational power. In the 1-dimensional case, the family of 1-dimensional array languages generated by contextual array grammars with regular control languages can be characterized as the family of array images of the linear languages, which for a one-letter alphabet means that it coincides with the family of regular 1-dimensional array languages. |
|
Cuvinte-cheie Array grammar, Matrix control, Regular control, Tissue P system |
|
|