Conţinutul numărului revistei |
Articolul precedent |
Articolul urmator |
722 0 |
SM ISO690:2012 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 |
|
|
Google Scholar Export
<meta name="citation_title" content="Contextual array grammars with matrix control, regular control languages, and tissue P systems control"> <meta name="citation_author" content="Alhazov Artiom"> <meta name="citation_author" content="Fernau Henning"> <meta name="citation_author" content="Freund Rudolf"> <meta name="citation_author" content="Ivanov Sergiu"> <meta name="citation_author" content="Siromoney Rani S."> <meta name="citation_author" content="Subramanian K.G."> <meta name="citation_publication_date" content="2017/06/19"> <meta name="citation_journal_title" content="Theoretical Computer Science"> <meta name="citation_issue" content="682"> <meta name="citation_firstpage" content="5"> <meta name="citation_lastpage" content="21"> <meta name="citation_pdf_url" content="https://www.sciencedirect.com/science/article/pii/S0304397517302062?via%3Dihub">